Long prompts are expensive, so a common trick is to shorten them by deleting text: first throw away whole documents that look irrelevant to the question, then delete individual tokens from the documents that survive. This "extractive" approach only removes text and never rewrites it, so it cannot invent facts, and the result still works with any black-box language model. The weakness is the first step. Each document is judged against the question on its own. For a multi-hop question such as "Who directed the film that won the award the novelist received?", the paragraph that answers the last step barely relates to the question's wording. It only becomes relevant once you know the intermediate entity, which sits in a different paragraph. The coarse ranker drops that paragraph, and the token pruner downstream can never get it back. This is a textbook case of what the hierarchical-systems literature calls error propagation: a mistake at the coarse level sends the fine level to search in the wrong place.
We propose to measure this cascade directly and to repair it with one targeted mechanism. After token pruning, we re-score every discarded document against the compressed context itself, not against the bare question. The compressed context now contains the bridge entities found in the first hop. A discarded document is swapped back in, inside a fixed total token budget, when it adds more question likelihood than the least valuable retained tokens. The claim is specific. Coarse-stage false negatives on later hops are a measurable and dominant share of failures in extractive multi-hop compression. A single round of context-conditioned re-scoring recovers them. Simply keeping more documents at the coarse stage does not, at the same final budget.
What exists and where this sits
The coarse-to-fine design we target is LongLLMLingua. It ranks documents by how much each one lowers a small model's perplexity on the question. It then deletes tokens by contrastive perplexity, meaning the change in a token's probability when the question is present versus absent. It also restores entity fragments through "subsequence recovery." It reports a 21.4% accuracy gain for GPT-3.5-Turbo on NaturalQuestions using 25% of the tokens. However, its coarse filter is hard: a document ranked low is discarded or squeezed, and the paper does not measure how ranking errors reach final accuracy. This paper supplies our base pipeline and the gap we measure.
PartPrompt comes closest in spirit. It passes importance scores up and down a token→sentence→paragraph→document tree, and it beats LLMLingua-2 on RULER (69.0 vs 24.0). But its propagation is computed once, from local token entropy, before any pruning happens. Pruning is then greedy and has no way to revisit a deleted branch. Our re-scoring is different in kind: it happens after a first compression and is conditioned on what that compression kept.
COMI reallocates budget between segments using relevance minus redundancy. Its fine stage merges tokens into soft vectors, so it is not extractive, and its first stage cannot be revised by the second. HD-Gist unmasks fine-grained compressed tokens on demand. This is a form of fine-level recovery, but it uses learned gist vectors and fixed API schemas. Together these two motivate the idea that later stages should be able to request capacity. They also show that, so far, this has only been done outside the extractive setting.
From the hierarchical-error literature we borrow two methods. Stacked Hierarchical Labeling trains child classifiers on held-out parent predictions and passes soft label proportions downward, so the children learn to distrust their parents. We use this as an ablation: soft coarse priors without backtracking. BeamAggR keeps several candidate sub-answers per node of a question tree rather than committing greedily. It motivates keeping a small pool of discarded documents eligible for return instead of deleting them permanently. Finally, MuSiQue built its questions bottom-up from single-hop pieces, so a missing intermediate fact breaks the chain. It also annotates supporting paragraphs (human support F1 93.9), which is what lets us attribute each failure to a specific stage. This mirrors the inside-out failure that the layered nested-NER model names as its main bottleneck.
Core Claim
Let $q$ be the question and $C$ the compressed context after the coarse and fine passes. Let $d$ be a discarded document, and let $\log p(\cdot)$ be log-probability under the small scoring model. The coarse ranker effectively scores
$$s_{\text{coarse}}(d) = \log p(q \mid d) - \log p(q).$$
We instead score
$$s_{\text{back}}(d \mid C) = \log p(q \mid C \oplus \tilde d) - \log p(q \mid C),$$
where $\tilde d$ is $d$ token-pruned to a small fixed size $k$ by the same contrastive pruner, and $\oplus$ is concatenation.
A bridge-hop paragraph can have $s_{\text{coarse}}$ near zero and a large $s_{\text{back}}$, because its relevance depends on an entity that is now present in $C$. We swap $\tilde d$ in, and evict the $k$ lowest-scoring retained tokens, whenever $s_{\text{back}}$ exceeds the likelihood those tokens contribute. Total length never exceeds budget $B$. The output remains a strict subsequence of the source, so the method stays extractive.
Research Program
The first phase is diagnostic. We run LongLLMLingua and LLMLingua-2 on MuSiQue, HotpotQA, and 2WikiMQA at 2×, 4×, and 8× compression. For every wrong answer, we use the supporting-paragraph annotations to classify the cause. A failure is "coarse-dropped" if a gold paragraph was removed at the coarse stage, "fine-damaged" if the paragraph survived but the answer or bridge span was deleted, and "reader error" if all gold spans survived. We break this down by hop count and by which hop each lost paragraph serves. The hypothesis, which this phase can falsify, is that coarse drops of non-first-hop paragraphs dominate and grow with hop count. If they do not, the backtracking idea has nothing to fix and we stop. In that case we report the attribution study itself.
The second phase builds the backtracking step on top of LongLLMLingua's pipeline. We use one round by default and test up to three. To bound cost, only the top $m$ discarded documents by a cheap lexical overlap with $C$ are re-scored, with $m$ swept from 5 to 20. We report the added forward passes and wall-clock latency honestly. The method adds per-query computation and does nothing for the known problem that query-specific deletion masks prevent reusing a model's cached prompt computation across queries.
The third phase asks whether a learned single pass can absorb the benefit. We distill backtracked outputs into a token classifier in the style of LLMLingua-2 and check whether it retains the gains without the extra passes.
Baselines
The naive reference points are the uncompressed prompt and random token deletion at the same budget. The uncompressed prompt is the accuracy ceiling the field compares against. Random deletion shows how much any scoring helps.
The strongest existing competitor is LongLLMLingua, because it is the published extractive coarse-to-fine system built for question-conditioned long-context QA. It is exactly the architecture whose cascade we target. On its own benchmark it reports a 21.4% accuracy gain on NaturalQuestions with GPT-3.5-Turbo at 25% of tokens. For MuSiQue, the file notes that LongLLMLingua was evaluated but gives no score; there is no reported result found on Lacuna for LongLLMLingua on MuSiQue. We therefore rerun it ourselves with the same scoring model (Llama-2-7B), the same reader models, and the same budgets. Each method gets an equal hyperparameter search over compression-ratio and ranking settings on a shared development split.
LLMLingua-2 is the flat alternative that avoids any coarse stage. It reports exact match of 86.92 against 87.75 uncompressed on MeetingBank QA. PartPrompt is the hierarchical extractive alternative and reports 69.0 on RULER. Both are run under the same budgets.
Three ablations isolate the key ingredient. The first, larger coarse keep, retains twice as many documents at the coarse stage and prunes tokens harder, so the final budget is identical. The second, unconditioned backtracking, re-scores discarded documents with $s_{\text{coarse}}$ instead of $s_{\text{back}}$; it tests whether conditioning on $C$, rather than a second look alone, matters. The third, soft priors, follows Stacked Hierarchical Labeling: the fine pruner receives continuous coarse scores and is calibrated on held-out coarse outputs, with no swapping. An oracle that keeps all gold supporting paragraphs gives the ceiling for coarse-stage repair.
Beating the baselines means two things. Answer F1 on 3–4-hop MuSiQue questions must exceed both LongLLMLingua and the larger-coarse-keep ablation at equal token budget, with confidence intervals over three seeds and paired bootstrap tests. The measured coarse-dropped failure rate must also fall correspondingly.
Why not just…?
Why not just keep more documents at the coarse stage? This is the most serious threat. It is cheap, and it may recover bridge paragraphs simply by casting a wider net. The reason to expect it to fall short is that the bridge paragraph's question-only score is low by construction. Widening the net admits many distractors before it admits that paragraph, and at a fixed final budget those distractors dilute the token budget for everything else. The larger-coarse-keep ablation tests this directly. If it matches backtracking at equal budget, we will report that the cascade is a budget-allocation problem rather than an ordering problem, and the proposal's mechanism is unnecessary.
Why not just use a flat token classifier and skip the hierarchy? A flat tagger like LLMLingua-2 has no coarse stage, so it has no coarse cascade. But PartPrompt's RULER comparison (24.0 for LLMLingua-2 versus 69.0 for the hierarchical method) suggests that flat pruning loses long-range structure. A flat tagger also still scores every token without knowing what the other hops contain. Our phase-one attribution reports "fine-damaged" failures for LLMLingua-2 specifically. This shows whether it simply relocates the same loss from documents to spans.
Why not just use a soft or abstractive compressor that avoids hard deletions? COMI reports large gains, including 25 exact-match points on NaturalQuestions at 32× compression. However, its soft vectors require a model it was trained with. They cannot be sent to a black-box API, and they give up the guarantee that every output token appears in the source. We treat extractiveness as a deployment constraint, not something to optimize away. We include COMI's published numbers only as context, not as a like-for-like comparison.
Why not just do iterative retrieval with query reformulation? Re-querying a retriever with entities from the first hop is close in spirit to our method. The difference is that our setting has no retriever: the full context is given, and the task is to fit it into a budget. Backtracking is the compression-side version of that idea and keeps the budget fixed. If a reformulated-query reranking over the same discarded pool performs as well, it simply becomes an implementation of $s_{\text{back}}$, and we would adopt it.
Proposed Experiments
The main grid crosses MuSiQue, HotpotQA, and 2WikiMQA with the 2×, 4×, and 8× budgets. Metrics are answer exact match and F1, supporting-paragraph recall after compression, and the three-way failure attribution. Readers are one open model and GPT-3.5-Turbo. NaturalQuestions, a single-hop benchmark, serves as a negative control: backtracking should give near-zero gain there, because no hop depends on another. A gain on NQ would mean the mechanism is acting as generic extra compute rather than repairing a cascade. LongBench supplies latency measurements on prompts of about 10,000 tokens, where LongLLMLingua reports 1.4×–2.6× end-to-end speedups. We report how much of that speedup backtracking gives back.
Three checks decide the question. First, gains must concentrate on questions whose later-hop gold paragraph had a low question-only coarse rank. Second, gains should increase from 2-hop to 4-hop MuSiQue. Third, backtracking must beat the larger-coarse-keep and unconditioned-backtracking ablations at equal budget. If all three hold, coarse-stage path dependency is a real and fixable failure of extractive compression. If the larger-keep ablation ties, the honest conclusion is that budget allocation, not revisability, is what matters.
References
- LongLLMLingua: Accelerating and Enhancing LLMs in Long Context Scenarios via Prompt Compression
- Parse Trees Guided LLM Prompt Compression
- COMI: Coarse-to-fine Context Compression via Marginal Information Gain
- Hierarchical and Dynamic Prompt Compression for Efficient Zero-shot API Usage
- Stacked Hierarchical Labeling
- BeamAggR: Beam Aggregation Reasoning over Multi-source Knowledge for Multi-hop Question Answering
- ♫ MuSiQue: Multihop Questions via Single-hop Question Composition
- A Neural Layered Model for Nested Named Entity Recognition
- LLMLingua-2: Data Distillation for Efficient and Faithful Task-Agnostic Prompt Compression