Bridge Links: Letting Multi-Hop Question Traffic Rewire the Retrieval Index

Questions such as "In what city was the director of Inception born?" defeat ordinary search. The document holding the answer, Christopher Nolan's biography, looks nothing like the question, and it only becomes findable after an earlier step has resolved the middle entity. Today's multi-hop systems handle this by searching repeatedly. Each new question is broken into sub-questions, and each sub-question gets its own search over an index that never changes. That index has no memory: it never records that, across thousands of earlier questions, retrieving document A was repeatedly followed by needing document B. We propose to record exactly that. The index stores directed "bridge links" from a parent document to the child document a later sub-question turned out to need. A link is kept only if a cheap uncertainty signal says the child document actually made the language model more confident in its sub-answer, as opposed to merely looking similar.

In two sentences: decompose each incoming multi-hop question into a tree of sub-questions; whenever a child sub-question's evidence measurably reduces the model's uncertainty given its parent's evidence, add or strengthen a link between those two documents in the index, and weaken links that stop paying off. Later questions that reach the parent document can follow its links to bridge evidence that similarity search alone would miss. The intended result is higher recall of bridge evidence and fewer retrieval and model calls as traffic accumulates.

Core Claim

The claim is that a retrieval index for multi-hop question answering should be adapted by query traffic, and specifically by which evidence resolved which dependent sub-question. Neither raw query geometry nor retrieval latency is the right signal. This claim combines four directions, each in a different role. Multi-hop answering is the target failure. Adapting the index to live traffic is the operating regime. Hierarchical decomposition supplies the dependency labels that say which retrieval step depended on which. Uncertainty-based filtering is the gate that decides whether a candidate link is real.

Several pieces of prior work motivate the proposal. CrackIVF restructures a vector index around the queries that actually arrive. Its triggers are geometric, and it is evaluated only on single-vector search. HNSW-NGFix adds graph edges only in heavily queried, defective regions. Its notion of difficulty is graph navigation, not reasoning. We borrow its idea of adding edges selectively, but our edges repair reasoning reachability, the ability to get from one hop's evidence to the next, rather than nearest-neighbour navigability. SUNAR shows that walking a document-neighbourhood graph recovers bridge documents. On MuSiQue it reaches Recall@10 of 0.459 against 0.240 for standard retrieval. Its graph, however, is built offline from semantic clusters, carries no direction, and never changes. Its uncertainty check also needs several generations per document.

The closest work is GAM-RAG. It keeps per-sentence memory vectors on a fixed entity–sentence–passage co-occurrence graph and updates them with a gain rule inspired by the Kalman filter, using feedback from an external LLM judge. It reports an average 3.95% gain rising to 8.19% after five turns, plus a 61% reduction in inference cost. We differ in three ways. First, we change the graph's structure by adding and removing directed cross-hop edges, whereas GAM-RAG reweights fixed nodes. Second, each edge is tied to a parent→child dependency in a sub-question tree, so it encodes "after this, you will need that." Third, our feedback is a single-pass shift in the model's uncertainty rather than a judge call, and GAM-RAG's own evaluation stops at ten turns while we target streams of thousands of queries.

Research Program

Decomposition. Each question is broken into a shallow sub-question tree in the style of RoHT and Tree-of-Question. We need decomposition only to record dependencies, not to answer better, so the tree can be kept simple.

Retrieval for a child sub-question. Candidates are pooled from ordinary dense retrieval and from the outgoing bridge links of the documents that resolved its parent.

Uncertainty signal. For each candidate document $d$ used to answer sub-question $q$, we compute a gold-free information gain. This follows the document-level uncertainty idea in SGIC and the with-versus-without contrast in InfoGain-RAG:

$$g(q,d) = H(a \mid q, p) - H(a \mid q, p, d),$$

Here $H$ is the open-weight model's length-normalised predictive entropy over the sub-answer $a$, and $p$ is the parent's resolved evidence. InfoGain-RAG uses the gold answer to compute this quantity. We cannot at serving time, so we use entropy and, following InfoGain-RAG, apply its length-bias corrections.

Link updates. Each link $A \to B$ keeps a Beta posterior over whether following it produces positive gain. A use with $g > \tau$ counts as a success, where $\tau$ is a small threshold. A use with $g \le \tau$ counts as a failure. A link is followed when its posterior mean

$$s_{A\to B} = \frac{\alpha_{A\to B}}{\alpha_{A\to B} + \beta_{A\to B}}$$

exceeds a cutoff. Here $\alpha$ and $\beta$ are the decayed success and failure counts. Decay lets links go stale and be pruned under drift, which addresses the stale-edge problem Hua et al. leave open.

Questions the program answers. We test whether learned links transfer to new questions that share a bridge document but ask a different relation. We test whether gating by uncertainty matters compared with gating by similarity. We measure how fast cost falls with traffic and how the graph behaves when the workload shifts.

Baselines

The naive reference point is one-shot dense retrieval of the top $k$ documents fed to the same reader model. Next is IRCoT, which alternates chain-of-thought steps with retrieval and reports 11–21 points of retrieval recall gain over one-shot retrieval. It is the standard linear interleaved method. Next is DRAGIN, which reports 2WikiMultiHopQA F1 of 0.3931 with LLaMA2-13B against 0.3076 for FLARE. All three are run with our reader model, our retriever and our corpus.

The strongest bridge-recall competitor is SUNAR's static neighbourhood graph, with its reported MuSiQue Cover-EM of 32.75 and Recall@10 of 0.459. We re-run SUNAR's neighbourhood expansion on our corpus and reader so that the only difference is a static graph versus a learned one.

The strongest adaptive competitor is GAM-RAG. It is run on the same query stream with the same number of LLM calls per query. If its judge exceeds that budget, we report its accuracy against total compute. The file gives no per-dataset GAM-RAG number on Lacuna, only the aggregate figures above.

RoHT reports 54.4 EM on MuSiQue. The file does not say under which retrieval setting, so we treat that number as context rather than a target.

Two ablations isolate the key ingredient. The first, "similarity links," uses the same update machinery but credits a link whenever the child document scores highly in retrieval, ignoring uncertainty. The second, "undirected co-retrieval links," credits any two documents that appear in the same answer path, ignoring the tree's direction.

Beating the baselines means two things. Bridge-document Recall@10 and final F1 must exceed SUNAR's re-run graph on queries arriving after a warm-up prefix. Retrieval and model calls per question must fall below IRCoT at equal or better accuracy. Each comparison uses matched seeds, three stream orderings, and paired bootstrap confidence intervals.

Why not just…?

Why not just cache sub-question answers? A semantic cache from sub-question text to answer is cheaper and is a real threat when sub-questions repeat verbatim. Bridge links aim at a different case: two questions that land on the same parent document but need different facts from it, or need it for a different second hop. We will split stream queries into those whose child sub-question matches an earlier one and those whose parent document matches but whose sub-question does not. If our gains come only from the first group, the method is a cache with extra steps, and we will say so.

Why not just use Wikipedia hyperlinks as the bridge graph? On Wikipedia this is the most dangerous alternative, because hyperlinks are a free, hand-made bridge graph. We therefore include hyperlink expansion as a baseline. We also evaluate on a hyperlink-stripped corpus, which stands in for enterprise text where such links do not exist. If hyperlink expansion matches learned links even on Wikipedia, the contribution narrows to "learn links where none exist." That narrower contribution would be real but smaller.

Why not just give a larger model more passages? IRCoT reports a 3B-parameter interleaved system beating 175B-parameter GPT-3 with one-step retrieval. SUNAR's low baseline recall also shows that bridge evidence often never reaches the prompt at all. We will still run a large-model, large-$k$ baseline at a matched token budget.

Why not just gate links with a cross-encoder reranker instead of uncertainty? InfoGain-RAG reports that its gain-trained reranker beats GTE-Reranker by 2.9% on TriviaQA with Qwen2.5-72B, because similar-looking passages often add nothing. That evidence is single-hop, so the similarity-links ablation is the experiment that settles whether the same holds across hops.

Proposed Experiments

We build query streams from MuSiQue-Ans, 2WikiMultiHopQA and HotpotQA in the full-Wikipedia setting. MuSiQue is the primary benchmark because its connectedness filtering blocks shortcuts. Questions are ordered so that shared bridge entities follow a Zipf-skewed popularity distribution. A drift variant switches entity clusters midway through the stream.

The metrics are bridge-document Recall@10, answer EM and F1, and retrieval plus LLM calls per question, all plotted against position in the stream. We also track graph size and the fraction of followed links whose gain is positive.

Three checks are decisive. The first is the transfer split from the cache comparison: learned links must raise recall on queries whose sub-question is new but whose parent document has been seen. The second is that the uncertainty-gated links must beat the similarity-gated links on MuSiQue recall and F1. The third is that after drift, decay must bring accuracy back to the pre-drift level within a bounded number of queries, while graph size stays bounded.

To guard against leakage, gain is computed without gold answers, and links are created only from queries earlier in the stream than the one being evaluated. If links fail to transfer, or similarity gating performs as well, the central claim is wrong.