advanced rag-information-theory 32 min read

Multi-Hop and Iterative Retrieval as Search over an Evidence Space

A compositional question — the revenue of the company that acquired Company A's primary supplier — hides its answer in a document the query cannot reach in one retrieval: near-orthogonal to the query on the embedding sphere, yet a short reformulation away through a bridge filing that names the supplier. Retrieval becomes a search over an evolving evidence space, where each hop is the previous topic's retrieve-and-select step, end-to-end recall is the product of per-hop recalls, an information-theoretic stopping rule decides when the marginal evidence no longer pays its cost, and — the climax — single-shot selection provably cannot shortcut the path because the bridge and answer form a supermodular synergy.

Part of the Information Theory of RAG track · View full curriculum →

Prerequisites: Context Selection: Submodular Coverage, MMR, and Determinantal Point Processes

From a fixed pool to a growing one

The previous topic ended on a sentence that pointed past itself. Having spent its length showing how to choose the best $k$ passages from a fixed candidate pool — coverage over relevance, the greedy choice provably within $1 - 1/e$ of optimal — it closed: “when one passage’s answer raises a new question, selection becomes a search over an evolving evidence space, which is where multi-hop and iterative retrieval take over.”

This is that search. Every topic in this layer so far has assumed one shot: retrieve a pool once, choose a subset, answer. That assumption holds for a question whose evidence sits in one place. It breaks for a compositional question — one whose answer is defined through an intermediate entity the query never names. Ask for the revenue of the company that acquired Company A’s primary supplier, and no single retrieval can return the answer: the document that reports that revenue is a filing of some company $C$ that the query, which only mentions $A$ , has no reason to be near. You must first find $A$ ‘s filing to learn the supplier $B$ , then find who acquired $B$ , then retrieve $C$ ‘s revenue. Retrieval becomes a loop — retrieve, read, reformulate the query from what you read, retrieve again — and the object of study is the loop, not the single step.

We will make four claims precise, on the same finance geometry the rest of the arc used. First, that the compositional answer is genuinely unreachable in one hop — a statement about the embedding sphere. Second, that the loop is a search over an evidence space, each hop the previous topic’s retrieve-and-select step. Third, that chaining is expensive: end-to-end recall multiplies across hops, so it decays. Fourth — the climax — that greedy single-shot selection provably cannot shortcut the path, because the bridge and the answer form a supermodular synergy, the exact failure mode of the diminishing-returns machinery the last topic relied on.

The compositional gap: an answer one hop cannot reach

Fix the geometry. Each company has a unit direction $u_X$ on the sphere; a filing of company $X$ that mentions company $Y$ is a document whose embedding leans mostly toward $X$ but carries a component toward $Y$ — the mention. We model it as

f_{X\to Y} \;=\; \cos\alpha \, u_X + \sin\alpha\, u_Y, \qquad \alpha \in (0, \tfrac{\pi}{2}),

so a query $q \approx u_X$ retrieves the filing ( $\langle q, f_{X\to Y}\rangle \approx \cos\alpha$ , large) while the mentioned company $Y$ , if it sits in a different sector, is near-orthogonal to $q$ ( $\langle q, u_Y\rangle \approx 0$ ). The terminal answer filing of the last company is just its own direction. This is the whole mechanism, and it lets us define the structure the question lives on.

Definition 1 (The retrieval graph and graph distance).

Let $V$ be the documents. Fix an edge threshold $\tau \in (0,1)$ and a reformulation map $\rho(\cdot)$ that turns a read document into the next query. The retrieval graph is the directed graph on $V$ with an edge $d_i \to d_j$ whenever $\langle \rho(d_i), d_j\rangle > \tau$ — ” $d_j$ is retrievable from a query formed by reading $d_i$ .” A query $q$ is a source: it reaches $\{d : \langle q, d\rangle > \tau\}$ in one step. The graph distance $d_G(q, d)$ of a document is the length of the shortest directed path from the query’s reachable set to $d$ .

A single-hop retriever returns the source’s one-step neighborhood. So a question is answerable in one hop exactly when its answer document sits at graph distance one. The compositional question is engineered so it does not.

Proposition 1 (The compositional gap).

Take a two-hop chain $q \approx u_A$ , a bridge filing $f_{A\to B} = \cos\alpha\,u_A + \sin\alpha\,u_B$ , and an answer filing $\approx u_B$ , with $A$ and $B$ in distinct sectors so $\langle u_A, u_B\rangle \approx 0$ . If $\cos\alpha > \tau > \langle u_A, u_B\rangle$ , then:

the bridge is reachable from the query, $\langle q, f_{A\to B}\rangle \approx \cos\alpha > \tau$ ;
the answer is not, $\langle q, u_B\rangle \approx \langle u_A, u_B\rangle < \tau$ — it sits at graph distance two;
the reformulated query reaches it: the operator $\rho(d) = \dfrac{d - \langle d, q\rangle\, q}{\lVert d - \langle d, q\rangle\, q\rVert}$ applied to the bridge returns $\rho(f_{A\to B}) \approx u_B$ , since removing the $u_A$ component of the bridge leaves the $\sin\alpha\,u_B$ mention; then $\langle \rho(f_{A\to B}), u_B\rangle \approx 1 > \tau$ .

Consequently single-hop recall of the answer is $\approx 0$ and two-hop recall is $\approx 1$ .

The reformulation operator is the heart of the construction and worth a sentence on its own. It is the projection of the read document onto the subspace orthogonal to the current query — the new direction the filing adds, the entity it names that the query did not. Reading $A$ ‘s filing and subtracting what the query already knew about $A$ leaves exactly the pointer to $B$ . That is what converts a document into the next query, and it is why the answer, invisible from $q$ , becomes reachable after one step. The lab’s first panel is this proposition: on the “cosine to the current query” axis the bridge sits above $\tau$ and the answer below it, until reformulation snaps the answer’s cosine to $\approx 1$ .

answer reachable now?

no ✗

single-hop answer recall

0.00

multi-hop answer recall

1.00

answer graph distance

2 hops

A 2-hop question hides its answer in a filing that is near-orthogonal to the query (cosine 0.19 < τ): single-hop retrieval never surfaces it, so single-hop answer recall is 0.00. The bridge filing — company A's, which names the supplier — is retrievable (cosine 0.82) and carries a component toward the answer (0.72). Reformulating from it, q' = normalize(d − ⟨d,q⟩q), points the next retrieval straight at the answer (cosine jumps to 0.98), so multi-hop recall is 1.00. The answer sits at graph distance 2: a path, not a point.

Finance vMF corpus on the shared dense-retrieval cloud (seed 7, dim 32): companies in distinct sectors are near-orthogonal, so a chain's answer company is invisible to its query; a bridge filing for company A that names company B is drawn around cos α·u_A + sin α·u_B with α = 40°, and the reformulation operator extracts the sin α mention. The answer is read through the imported answer_posterior (a synthetic softmax stand-in, not an LLM); the compounding/FKG demo reuses the capstone's cascade machinery. Numbers mirror multi_hop_iterative_retrieval.py (top-k = 3); the lab recomputes only ∏rᵢ, ρ^(1/k), the over-fetch reciprocal, and the threshold crossing.

On the constructed corpus the gap is total: averaged over the compositional chains, single-hop answer recall is $0.00$ and multi-hop is $1.00$ , while the one-hop control questions — whose answer is the query company’s own filing — are reachable in a single hop, recall $1.00$ . The point is not the precise decimals, which are exact for this synthetic answer model; it is that the gap is a property of the geometry, not of any decoder. No amount of reading more of the wrong neighborhood reaches a document that is near-orthogonal to the query.

Multi-hop as search over an evidence space

Once the answer is a path rather than a point, retrieval is a sequential decision problem. We give it the standard furniture.

Definition 2 (The evidence-space search problem).

A state is a belief $b \in \Delta(\mathcal{A})$ over the answer space — the posterior $p(a \mid q, D)$ given the documents $D$ read so far. An action is a reformulated query $q'$ . The transition is the previous topic’s retrieve-and-select step: from the $\tau$ -reachable pool of $q'$ , select a context $S$ by greedily maximizing the information gain $f_{\mathrm{IG}}(S) = H(b) - H(b \mid S)$ — the same monotone-greedy maximizer context selection certified — read $S$ , and update the belief. The reward of a hop is the information it adds. A trajectory is a path through the retrieval graph; the greedy policy takes, at each state, the action of maximal expected marginal information.

Two things deserve emphasis. The per-hop operator is literally the prerequisite’s: retrieve a pool, then select the covering subset under a budget, with greedy on a submodular oracle. Multi-hop does not replace selection; it iterates it, feeding each step’s reading into the next step’s query. And the reward is information, which ties the search to the bits the PMI and noisy-channel topics counted. What multi-hop adds is the control problem on top — which query to issue next, and when to stop.

The optimal control problem has a clean form and an unfortunate cost.

Remark (The optimal policy is a Bellman fixed point — and intractable).

The value of a belief under the optimal policy satisfies the Bellman recursion

V(b) \;=\; \max_{a}\Big[\, r(b, a) + \mathbb{E}_{b' \sim T(b, a)}\, V(b') \,\Big],

the fixed point of a contraction, reachable in principle by value iteration. But the state space is the simplex over answers and the action space is every reformulation, so computing $V$ is intractable. Every practical multi-hop method — the greedy max-information hop we analyze, and every system in the literature — is a heuristic approximation of this policy, not the policy itself. We will see in the last section that the greedy heuristic has no approximation guarantee here, for a reason specific to compositional structure.

Compounding recall: why hops decay geometrically

A path is only as strong as its weakest link, and “strong” here is recall. If hop $i$ retrieves its target with probability $r_i$ , and the hops were independent, the whole chain succeeds with the product.

Theorem 1 (The chain recall law and its over-fetch).

For a $k$ -hop chain with per-hop recalls $r_1, \dots, r_k$ and independent hops, the end-to-end recall is

R_{\mathrm{chain}} \;=\; \prod_{i=1}^{k} r_i .

To leave an end-to-end target $\rho$ , each hop must reach $r_i = \rho^{1/k}$ , which rises toward $1$ as $k$ grows; equivalently the front end of each hop must over-retrieve by $1/\prod_i r_i$ — one negative-binomial scan law on the composite retention, exactly as the capstone composed cascade stages, now composed over hops.

The consequences are stark and they are the lab’s second panel. With a modest per-hop recall of $0.7$ , a three-hop chain succeeds barely a third of the time ( $0.7^3 \approx 0.34$ ); to hold $\rho = 0.9$ end to end over three hops, each hop must individually reach $0.9^{1/3} \approx 0.965$ . Multi-hop is not free reach — it is reach bought at a geometric price, which is why a system that hops carelessly is worse than one that does not hop at all.

The independence assumption is, as ever, the soft spot — and as ever, it errs in the safe direction.

Proposition 2 (Positive dependence makes the product a lower bound (FKG)).

Hops share corpus geometry: a query that is hard at one hop tends to be hard at the next, so the per-hop success events are positively associated. By the FKG/Harris inequality, the realized chain recall is at least the product of the marginal recalls,

\Pr\!\Big[\textstyle\bigcap_i \{\text{hop } i \text{ succeeds}\}\Big] \;\ge\; \prod_i r_i .

The independent product is therefore a conservative lower bound; provisioning the over-fetch to $1/\prod_i r_i$ is safe, not exact.

We verify the direction rather than assume it, on the same bivariate-survival copula the capstone used: as the hop dependence $\rho$ runs from negative to positive, the gap between realized and independent chain recall runs from negative through zero to positive — the FKG sign, confirmed across both signs before being written down. (The measured per-hop recalls on this clean corpus are $\approx 1$ , which leaves no room for the product law or FKG to bite, so the panel uses illustrative middling retentions — a high-retention chain makes the law vacuous, the same caveat the capstone flagged.)

When to stop: marginal information versus cost

A search needs a stopping rule. The information-theoretic instinct is right: stop when the next hop’s expected marginal information falls below its cost. The subtlety is which signal measures that information — and the answer is not the one a naive reading suggests.

Definition 3 (The marginal information of a hop).

The information a hop adds is the entropy it removes from the answer belief, $\Delta I_t = H(A \mid Q, D_{1:t-1}) - H(A \mid Q, D_{1:t})$ ; by the chain rule of mutual information these telescope to the total $I(A; D_{1:k} \mid Q)$ . Operationally, the new direction a read filing opens is its reformulation residual $\lVert d - \langle d, q\rangle q\rVert$ — the magnitude of the entity it names that the query did not. When the residual collapses, the filing names no one new and the next hop can only re-retrieve known evidence, so its expected marginal information is $\approx 0$ .

Algorithm 1 (Adaptive iterative retrieval with an information stopping rule).

Initialize $q \leftarrow q_0$ and the belief $b_0$ . Repeat: rank the corpus by $\langle q, \cdot\rangle$ ; read the top unread document $d$ ; update the belief; if the residual $\lVert d - \langle d, q\rangle q\rVert < \varepsilon$ — the filing names no new entity — stop and return the belief; otherwise set $q \leftarrow \rho(d)$ and continue. This is a heuristic, an SPRT / optimal-stopping analogue, not the Bellman-optimal policy.

The rule terminates correctly: through every bridge hop the residual clears the threshold (a new entity to chase), and at the terminal answer filing it collapses (it names no one), so the realized hop count equals the chain depth — one, two, three hops for one-, two-, three-hop questions. The lab’s third panel shows this on a worked three-hop trajectory: two bridge residuals well above the threshold, then a collapse, and the loop halts.

The panel also exposes a trap, and it is the bridge to the climax. The obvious stopping signal would be the belief movement — stop when reading another document no longer changes your answer distribution. On a compositional chain that signal is exactly backwards. The bridge hop barely moves the belief: reading $A$ ‘s filing only confirms what the query already implied about $A$ , a KL movement near $0.08$ . The decisive shift comes last, at the answer hop, with a KL movement above $9$ — the belief snaps from $\approx 0$ mass on the truth to $\approx 1$ . A myopic “stop when the belief stops moving” rule would halt at the worthless-looking bridge and never reach the answer. The decisive evidence arrives late, which is the operational face of the structure we turn to now.

Why greedy cannot shortcut: the supermodular synergy

The prerequisite leaned on submodularity — diminishing returns — to earn its $1 - 1/e$ guarantee, and flagged the one objective that breaks it: information gain. Multi-hop is where that break becomes the whole story.

Theorem 2 (Compositional information is supermodular).

For a compositional pair — a bridge document $d_{\mathrm{br}}$ and an answer document $d_{\mathrm{ans}}$ whose joint identifies the answer while neither does alone — the marginal information of the answer document increases with conditioning:

\Delta\big(d_{\mathrm{ans}} \mid \varnothing\big) \;=\; 0 \;<\; 1 \;=\; \Delta\big(d_{\mathrm{ans}} \mid \{d_{\mathrm{br}}\}\big).

This is the XOR witness: with $A = D_{\mathrm{br}} \oplus D_{\mathrm{ans}}$ , each observation alone carries zero information about $A$ while the two together carry one bit. A submodular gain would have the marginal decrease with conditioning; here it does the opposite — information gain is supermodular on the compositional pair, and so not submodular, the same witness context selection used to disqualify it as a greedy objective.

Submodularity was the hypothesis the Nemhauser–Wolsey–Fisher theorem needed. Without it, greedy carries no $1 - 1/e$ guarantee — and worse, on this structure greedy single-shot selection cannot reach the answer at all.

Corollary 1 (Multi-hop is the synergy-exploiting move).

Because the answer document’s marginal value is zero until the bridge is read, a single-shot selector optimizing a one-pass objective will never buy it — and in fact cannot: the answer is below the edge threshold from the query, so it is not even in the one-hop reachable pool. Only by reading the bridge and reformulating from its content does the answer enter a reachable pool. Multi-hop is precisely the move that converts the bridge’s named entity into a query that reaches the answer, harvesting a synergy no single-shot selection can.

The lab’s fourth panel is this corollary as two bars and a toggle: the answer document alone contributes zero bits, given the bridge it contributes one — the marginal arrow points up — and the answer is in the single-hop reachable pool with frequency $0.00$ , in the reformulated pool with frequency $1.00$ . The supermodular synergy is not a curiosity at the edge of the theory; it is the reason multi-hop retrieval has to exist.

⚠ Rigor flag

Five honesty notes. First, greedy hopping has no $(1-1/e)$ guarantee: the per-hop objective is information gain, which is supermodular on the compositional pair, exactly the hypothesis the theorem rules out — so the prerequisite’s machinery does not transfer across hops. Second, the optimal policy is the fixed point of a Bellman recursion over the belief simplex and is intractable; the greedy max-information hop, and every cited system, is a heuristic. Third, the compounding-recall product holds under hop independence; positive dependence makes it a conservative lower bound (FKG/Harris), verified across both signs of a copula, so the over-retrieve provisioning is the safe direction, not an equality. Fourth, the stopping rule — stop when the read filing opens no new direction — is an optimal-stopping/SPRT analogue, not a derived optimum on this corpus; the threshold is tuned and the realized hop count is seed-dependent. Fifth, the answer model is a synthetic von Mises–Fisher softmax, exact for the model and illustrative of a real retriever, on one constructed corpus engineered to have a near-orthogonal answer reachable through a bridge — it demonstrates the mechanism, it does not claim every multi-hop question has this geometry.

What multi-hop retrieval trades, in one line

Multi-hop turns selection into search over an evolving evidence space: each hop is the certified retrieve-and-select step, the reformulation operator extracts the new entity a filing names, and the answer to a compositional question is a path, not a point. Recall compounds geometrically, so each hop must over-retrieve; the loop stops when a filing opens no new direction; and greedy earns no $1 - 1/e$ here because the compositional case is supermodular — which is the very reason iterative reformulation, not a bigger single-shot selection, is what reaches the answer.

§ The revenue of the company that acquired Company A's supplier text pdf news

A supply-chain question is rarely answerable from one filing. Ask for the revenue of the company that acquired Company A’s primary chip supplier, and the query mentions only $A$ . Hop one retrieves $A$ ‘s 10-K — the bridge — which discloses the supplier $B$ ; the reformulation strips away what the query already knew about $A$ and leaves the pointer to $B$ . Hop two, querying for $B$ , retrieves the acquisition news and the acquirer $C$ ; hop three retrieves $C$ ‘s revenue, the answer. No single retrieval could have surfaced $C$ ‘s filing: it never mentions $A$ , and on the embedding sphere it sits near-orthogonal to the original query. The discipline is to read the filing that names the next entity, reformulate, and retrieve again — paying the geometric recall cost and stopping once a hop names no one new. Once iterative retrieval has traversed these edges enough times, the relation “retrievable-from” has drawn a graph over the whole corpus, and the question shifts from finding a single path to understanding that graph’s global structure — its dense communities of mutually-retrievable filings. That global community structure is the object of GraphRAG and community detection, the next step in this arc.

Connections

the previous topic certified the per-hop operator — retrieve a candidate pool, then select the covering subset within budget, with greedy on a monotone submodular objective provably within 1−1/e of optimal; this topic makes that step the TRANSITION of a search, because when one selected passage raises a new question the pool itself grows, so selection iterates into multi-hop, and the very XOR witness that broke info-gain submodularity there is the supermodular synergy that forces a second hop here context-selection-submodular-dpp
PMI measured a single document's evidentiary value in bits and showed a redundant second filing adds almost none; this topic chains that measurement across hops — a hop's marginal information is the new belief it buys, diminishing as the trajectory saturates until the stopping rule fires, and the compositional case is precisely where two documents each worth nothing alone are worth the whole answer together pmi-retrieval-value
the noisy-channel topic priced answer error against the bits read through one retrieval and read the recall–precision point as rate–distortion; a multi-hop trajectory is that channel used in series, where each hop's recall is a per-stage retention and the end-to-end error is the composition, so chaining recalls geometrically is reading several noisy channels back to back retriever-as-noisy-channel
that topic showed a bigger single window does not reach an answer the retriever never surfaced, and answer quality peaks at the smallest covering context; multi-hop is the orthogonal fix — rather than enlarge one retrieval it issues another, reformulated query, reaching documents no single query could because they sit near-orthogonal to it on the sphere retrieval-vs-long-context
recall@k defined per-hop success as set membership; this topic composes those per-hop recalls into an end-to-end chain recall that decays as their product, and the over-retrieve-to-ρ^(1/k) provisioning is that set-recall target lifted from one retrieval to a sequence of them set-metrics-precision-recall-map-mrr
the dual-encoder sphere geometry is where the compositional gap lives — the answer document is near-orthogonal to the query while a bridge document sits at a positive cosine to both, so the same learned inner products that make single-hop fail are what make a two-hop path reachable, and the retrieval scores come from its dual_encoder_score dense-retrieval-dual-encoders
the capstone proved cascade recall is the product of per-stage retentions, a conservative lower bound the correlated real pipeline sits above by FKG, and over-fetch is the reciprocal of that composite retention; this topic reuses both laws over HOPS rather than stages — chain recall is the per-hop product, positive dependence makes it a lower bound, and the per-hop over-fetch follows the same negative-binomial scan law capstone-multimodal-financial-rag

References & Further Reading

paper HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering — Yang, Qi, Zhang, Bengio, Cohen, Salakhutdinov & Manning (2018) The defining multi-hop QA benchmark: bridge and comparison questions whose answer requires composing facts across two documents — the compositional gap this topic models geometrically; EMNLP 2018 (arXiv:1809.09600)
paper Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval — Xiong et al. (2021) Iterative dense retrieval: re-encode a query from the passage just read and retrieve again — the retrieve→read→reformulate loop this topic analyzes, with the reformulation operator made explicit; ICLR 2021
paper Interleaving Retrieval with Chain-of-Thought Reasoning for Knowledge-Intensive Multi-Step Questions (IRCoT) — Trivedi, Balasubramanian, Khot & Sabharwal (2023) Interleaving reasoning and retrieval: each reasoning step reformulates the next query — the search-over-an-evidence-space view in a modern LLM pipeline; ACL 2023 (arXiv:2212.10509)
paper Measuring and Narrowing the Compositionality Gap in Language Models (Self-Ask) — Press, Zhang, Min, Schmidt, Smith & Lewis (2023) Names and measures the 'compositionality gap' — the share of compositional questions a model answers from no single retrieval — the phenomenon this topic's Movement 1 formalizes; Findings of EMNLP 2023 (arXiv:2210.03350)
paper Active Retrieval Augmented Generation (FLARE) — Jiang et al. (2023) Retrieve only when the generation is uncertain — the information stopping rule made operational, deciding hop-by-hop whether another retrieval pays its cost; EMNLP 2023 (arXiv:2305.06983)
paper Self-RAG: Learning to Retrieve, Generate, and Critique through Self-Reflection — Asai, Wu, Wang, Sil & Hajishirzi (2024) Adaptive retrieve-and-critique: the model decides when to retrieve and whether to keep what it found — the decision-theoretic stopping this topic frames as an SPRT/optimal-stopping analogue; ICLR 2024
paper Sequential Tests of Statistical Hypotheses — Wald (1945) The sequential probability ratio test: accumulate evidence and stop at a decision boundary rather than at a fixed sample size — the stopping-rule analogue behind 'retrieve until the marginal evidence no longer pays'; Annals of Mathematical Statistics 16(2)
book Dynamic Programming — Bellman (1957) The value recursion and the principle of optimality behind the evidence-space search: the optimal policy is the fixed point of a Bellman operator over belief states, named here and intractable in general; Princeton University Press
paper Correlation Inequalities on Some Partially Ordered Sets (FKG) — Fortuin, Kasteleyn & Ginibre (1971) The positive-association inequality: monotone increasing events are positively correlated, so a true neighbor missed at one hop is likelier missed at the next — which makes the independent product of per-hop recalls a conservative lower bound; Communications in Mathematical Physics 22(2)
book Elements of Information Theory — Cover & Thomas (2006) The chain rule of mutual information behind a hop's marginal information, and the entropy framing of the belief carried over from the PMI and noisy-channel topics; 2nd edition, Wiley