Pruning Dead-End Branches from the Working Memory of Iterative Retrieval

Systems that answer multi-hop questions ("In what city was the director of Inception born?") alternate between generating a sub-question, retrieving passages for it, and extracting a sub-answer that seeds the next sub-question. Every passage they retrieve stays in the prompt. When a hop goes wrong, for example by retrieving facts about the wrong actor or following a sub-question that leads nowhere, those passages keep shaping the later steps. This proposal borrows one exact result from probabilistic graphical models. In a Bayesian network, a "barren node" is an unobserved variable with no descendants that the query depends on. Such nodes can be deleted recursively without changing the answer, and what survives is the set of ancestors of the query and the evidence. We propose to record, during iterative retrieval, which passage supported which sub-answer and which sub-answer generated which later sub-question. Before each generation step, we would delete every node with no path to the current open question, then restore deleted nodes cheaply if a later hop links back to them.

The bet is that provenance can find a specific kind of distractor that relevance scoring cannot. Provenance here means the record of which earlier output each step actually used. Passages from an abandoned branch are often highly similar to the question, because they are about the right film and the wrong person, so a reranker keeps them. They are still structurally dead, because nothing downstream used them. If this holds, the gain should concentrate on long-hop questions and on trajectories that contain failed branches. Those are the places where distractors pile up and where single-path systems cannot recover.

Core Claim

Under a fixed token budget, deciding what to keep in the context by the trajectory's own dependency structure gives higher answer and support F1 on 3- and 4-hop questions than deciding by query-passage relevance. Recursive deletion of dead branches, together with restoration of deleted nodes, also lets a single-path reasoner backtrack without re-retrieving.

The graphical-model result is treated as a hypothesis, not a guarantee. An LLM is not a Bayesian network, and a "barren" passage might still help with disambiguation. Whether deletion preserves the answer is the first thing we measure.

Relation to Prior Work

The motivating evidence comes from iterative retrieval. IRCoT interleaves chain-of-thought sentences with retrieval and gains 11–21 recall points, but it accumulates every paragraph, and the file reports that context pollution remains an open problem for it. CoRAG fine-tunes models to emit sub-queries and sub-answers and searches over chains, raising MuSiQue retrieval recall from 29.0% to 47.1%. Branches that fail its tree search are dropped by score, with no structural sweep of what they left in memory. MEGRAG selects evidence at triple, sentence, or passage granularity and stops early once an "is the query resolved?" prompt says yes; its authors acknowledge that it follows a single path and cannot backtrack. We keep the single-path, low-cost regime but add backtracking through deletion and restoration.

The closest work is PAGE-RAG. It builds a disposable graph over a top-20 pool, penalizes hub entities, and greedily selects a minimal sufficient evidence set. It differs from our proposal in three ways. It operates once, after retrieval, on a static pool rather than on a growing multi-step trajectory. It scores paths with a weighted heuristic rather than by ancestry. It cannot revise decisions as new evidence arrives.

Stop-RAG learns a value function for the binary choice of continuing or stopping. It does not decide which accumulated items to keep, so it is complementary to this work rather than a substitute.

The method itself comes from the graphical-model literature. Baker and Boult define barren nodes, prove that recursive removal preserves the query posterior, and give an edge-linear algorithm. They also flag the open problem of restoring pruned nodes efficiently when evidence arrives incrementally, which is exactly the situation in iterative retrieval. Lin and Druzdzel show that relevance pruning gives over 20× speedups on the CPCS network. They also caution that the gains shrink in densely connected graphs. That caution is a real constraint here: on HotpotQA, where MEGRAG reports that nearly 90% of questions resolve in one hop, trajectories are too short to contain dead branches, and we predict little benefit. Bayes-Ball supplies the linear-time traversal if we later add observed-evidence blocking. The first version needs only ancestral closure.

Research Program

At each hop we maintain a directed graph called the trajectory graph. It has four kinds of nodes: the original question, which is always kept; sub-queries; retrieved passages; and sub-answers. Its edges run in the direction information flows. A sub-query points to the passages it retrieved, which in turn point to the sub-answer they support. A sub-answer points to any later sub-query that mentions its entity.

Two of these edges need care. The passage-to-sub-answer edges come from citations that the generator emits. We verify them by a string check that the sub-answer appears in the cited passage. The sub-answer-to-sub-query edges come from entity matching.

Let $F_t$ be the set of "open" nodes at hop $t$: the current frontier sub-query and the question. The kept context is the set of ancestors of $F_t$. This is exactly what Baker and Boult's recursive barren removal leaves behind, and it is computable in time linear in the graph size. Everything else is moved to an archive indexed by entity.

Restoration works through the archive. When a new sub-query or sub-answer mentions an archived entity, the archived subgraph is re-linked and restored instead of being retrieved again. Backtracking also falls out of the graph. If a sub-answer is "not found", or a verifier rejects it, its node loses its outgoing edge, and the whole branch becomes non-ancestral and disappears in a single sweep. The next sub-query is then generated from the deepest surviving sub-answer.

We will host this procedure inside two existing loops without retraining them: an IRCoT-style prompted loop and a CoRAG-style fine-tuned Llama-3.1-8B-Instruct loop. This isolates the effect of context management.

Baselines

The naive reference point is full accumulation, meaning the host loop run unchanged with every retrieved passage kept. We will also run a recency window that keeps only the last $k$ hops' passages, with $k$ tuned on a development split. This is the cheapest structural heuristic and checks whether "recent" is already a good enough stand-in for "ancestral".

The strongest relevance-based competitor is a cross-encoder reranker. At each hop it scores every accumulated passage against the concatenation of the original question and the current sub-query, and it keeps the top passages up to the same token budget our method ends up using. We condition on the current sub-query because a reranker conditioned on the question alone is known to miss bridge documents; CoRAG reports 29.0% single-step recall on MuSiQue. A second strong competitor is PAGE-RAG's minimal sufficient selection, applied at every hop to the accumulated pool. Its reported average gains are 3.3 Answer F1 and 10.4 Support F1 (PAGE-RAG). We will re-implement it at matched budget, since the file reports no per-hop or per-dataset number for it.

For reference on the host loops, Stop-RAG reports MuSiQue F1 of 47.0, against 44.8 for LLM-prompted stopping. MEGRAG reports an 8.34-point MuSiQue F1 gain over its strongest baseline with Qwen3-8B. We will add Stop-RAG's stopping rule to our best configuration to test whether the two are additive. All methods share the retriever, corpus, generator, and maximum number of hops. Each method gets the same development-set tuning budget, and comparisons are made at matched average context tokens.

Three ablations isolate the key ingredients. The first is random removal of the same number of tokens. The second is single-pass (non-recursive) leaf removal. The third is our method without restoration. A fourth configuration replaces our edges with oracle edges built from MuSiQue's gold decompositions, which bounds how much error in the edges costs us.

Beating the reranker means a statistically significant gain in answer F1 on MuSiQue 3- and 4-hop questions at equal tokens, with paired bootstrap at $p<0.05$. Meeting this bar on 2-hop questions alone would not count.

Why not just…?

Why not just rerank the accumulated passages against the current sub-query? This is the real threat, and the proposal stands or falls on it. Our prediction is that dead-branch passages are topically close to the question, so rerankers keep them. The injection experiment below tests exactly this. If the reranker removes injected dead branches as well as ancestry does, the structural signal adds nothing beyond relevance. We would then report a negative result and keep only restoration as a contribution, judged on the retrieval calls it saves.

Why not just ask the LLM which passages it still needs? Self-assessment has been weak in the closest setting. LLM-prompted stopping trails learned control on MuSiQue, 44.8 versus 47.0 F1 (Stop-RAG). Asking the model to filter also costs an extra generation call per hop. We will include LLM self-filtering as an additional baseline, at matched tokens and with its calls counted.

Why not just keep everything in a long context window? Even with all gold facts present, eight distractor paragraphs pulled HotpotQA's baseline Answer F1 down to 58.28, against 91.40 for humans (HotpotQA). Full accumulation is our naive baseline, so this alternative is measured directly rather than argued away.

Why not just use MEGRAG-style sufficiency checks or Stop-RAG? Both decide when to stop, not what to keep, and neither can undo a wrong hop. We test them in combination with our method, not only as rivals.

Proposed Experiments

The datasets are MuSiQue-Ans, with results reported by hop count (MuSiQue), 2WikiMultiHopQA, and HotpotQA in the full-wiki setting, which serves as the regime where we expect no gain. For each method we measure answer EM and F1, support F1, average context tokens per hop, and the number of LLM and retrieval calls.

The first decisive check tests whether deletion preserves answers. On trajectories where the host already answers correctly, we measure how often deleting the non-ancestral set changes the answer, and compare this against random deletion of the same size. A flip rate near that of random deletion would falsify the premise.

The second check is the injection test. Into gold MuSiQue trajectories, we insert a realistic dead branch: a sub-query about a wrong-but-related entity, together with its top retrieved passages. We then measure two things for each method: what fraction of the injected tokens it removes, and how much F1 it recovers.

The third check is a natural-failure analysis. On trajectories where a branch actually failed, we report F1 gains together with the number of re-retrievals avoided by restoration.

Finally, we vary the quality of the edges from oracle to extracted. This shows how much of any gap is lost to errors in the citation and entity matching.