Questions like "In what city was the director of Inception born?" need several lookups in sequence: find the director, then find his birthplace. Retrieval-augmented systems, meaning language models that fetch documents before answering, handle this by searching step by step. Each step is right only with some probability, and a wrong early step spoils everything after it. The common fix is to spend more inference compute, through more samples, wider trees, or more verifier calls. Nobody can say in advance how much compute a given accuracy target will cost, or where in the chain that compute should go.
This note proposes to measure and predict that cost. The theory of precision–complexity tradeoffs studies how an algorithm's cost grows as its allowed error $\epsilon$ shrinks. From that theory we take one lesson. Filtering only at the end of a long chain costs exponentially more as the chain gets longer. Filtering at each step costs roughly linearly in chain length, but it hits an error floor set by how often the step-checker wrongly accepts a bad step. We will write this down as a small predictive model, check it hop by hop on benchmarks that provide gold intermediate answers, and use it to set per-hop compute budgets for a target end-to-end error.
Core Claim
Treat a multi-hop answer as a chain of $H$ hops. At hop $h$ the generator–retriever pair produces a correct intermediate answer with probability $p_h$. A step-checker accepts wrong steps at rate $\alpha$ and rejects correct ones at rate $\beta$.
Take the most favourable case for outcome-only search: Best-of-N sampling of full chains, scored by a perfect final-answer selector. To reach failure probability $\epsilon$ it needs about
$$N_{\text{outcome}} \approx \frac{\ln(1/\epsilon)}{\prod_{h=1}^{H} p_h},$$
because a full chain succeeds only if every hop does. This cost is exponential in $H$.
Hop-gated resampling works differently: at each hop it redraws until the checker accepts. Its expected number of draws at hop $h$ is $1/(p_h(1-\beta)+(1-p_h)\alpha)$, which is linear in $H$ overall. Its end-to-end error, however, cannot fall below
$$\epsilon_{\text{floor}} = 1-\prod_{h=1}^{H}\Big(1-\frac{(1-p_h)\alpha}{p_h(1-\beta)+(1-p_h)\alpha}\Big),$$
the chance that some accepted step was wrong. Additional samples cannot reduce this floor.
This mirrors the contrast in Log-concave sampling: Metropolis-Hastings algorithms are fast!, which shows that an exact accept-reject step turns polynomial precision cost into logarithmic cost. The analogy breaks in exactly one place. A language-model checker is not an exact density ratio, so its acceptance carries bias, and that bias is the floor.
The claim has two testable parts. First, measured $(p_h, \alpha, \beta)$ predict the observed accuracy-versus-tokens curves of both regimes, stratified by hop count. Second, an allocator that uses these estimates matches the accuracy of uniform-budget tree search at substantially lower token cost. The allocator spends samples where $p_h$ is low and stops where the floor already dominates.
Relation to Prior Work
Several papers show that the gap is real. IRCoT interleaves reasoning sentences with retrieval and improves recall by 11–21 points. Two papers document that early errors cascade irreversibly: Chain-of-Retrieval Augmented Generation and Reasoning Court.
Two papers supply the methods we reuse and compete with. CoRAG trains models to emit sub-queries and sub-answers, and reports that accuracy grows log-linearly with test-time tokens under greedy decoding, Best-of-N, and tree search. That result is aggregated over questions; it does not separate cost by hop depth or by checker error, and that separation is our contribution. GRAT runs Monte Carlo tree search scored by a process reward model, that is, a model that rates each intermediate step. Its ablations show that retrieval quality, not simulation, carries most of the gain. This is consistent with our view that per-hop correctness $p_h$ is the quantity to model. GRAT spends a fixed search budget per question; we predict and adapt the budget per hop.
Reasoning Court constrains the design. It reports "consensus bias": a judge rarely overturns two agents that agree on the same wrong premise. In our terms, the checker's false-accept rate $\alpha$ is correlated with the generator's own errors. We therefore treat correlation between checker and generator as a measured quantity rather than assuming independence.
HopRAG builds a passage graph offline. It is orthogonal to our question and serves as an external reference point.
MuSiQue makes the study possible. Its 2–4 hop questions are composed from single-hop questions with gold intermediate answers, and its shortcut filtering means $p_h$ reflects genuine hops.
Research Program
The first component is measurement. On MuSiQue-Ans and 2WikiMultiHopQA, which both expose intermediate evidence, we run a fixed generator (Llama3-8B, matching GRAT's scale) with a fixed dense retriever over the standard corpora. We estimate $p_h$ for each hop position and question topology by scoring sub-answers against gold. For each candidate checker we estimate $\alpha$ and $\beta$, plus their correlation with generator errors. The candidates are an LLM self-check, a separately prompted judge, and a trained process reward model in the style of GRAT.
The second component is prediction. We plug the measured parameters into the two cost expressions and predict, before running any search, the accuracy-versus-tokens curves for 2-, 3-, and 4-hop questions. We then compare these predictions with empirical curves.
The third component is allocation. For a target $\epsilon$, the allocator chooses per-hop sample caps that minimize expected tokens subject to predicted error at most $\epsilon$. Where the predicted floor already exceeds $\epsilon$, it falls back to outcome-level resampling, so it never spends gated samples that cannot help. The parameters are estimated on a held-out calibration split. At test time they are conditioned on cheap features: hop index, retrieval score margin, and checker confidence.
The fourth component is a floor-lowering check. It targets $\alpha$ directly with a round-trip test that does not reuse the generator's reasoning. For a proposed bridge entity, the test retrieves with that entity alone and asks whether the returned evidence links back to the previous hop. We measure whether this check is less correlated with generator error than an LLM judge, since lower correlation would lower the floor.
Baselines
The naive reference is one-shot retrieval followed by a single answer, together with greedy IRCoT-style interleaving with no resampling. These anchor the zero-extra-compute end of every curve. IRCoT reports gains of up to 15 F1 over one-step retrieval, but the file gives no per-dataset absolute number.
The strongest existing competitor is CoRAG's test-time search, both Best-of-N and breadth-first tree search over sub-query chains. It is the published method that most directly trades tokens for multi-hop accuracy. On MuSiQue, CoRAG reports retriever recall rising from 29.0% for single-step retrieval to 47.1% with chain-of-retrieval, and EM gains of "over 10 points" over baselines. No exact CoRAG MuSiQue EM figure is available on Lacuna. We will therefore reimplement CoRAG-style search on the same 8B model, retriever, and corpus, and sweep its budget across the same token range as our method.
The second strong competitor is GRAT-style process-reward tree search. GRAT reports 66.8% accuracy on 2WikiMultiHopQA with Llama3-8B fine-tuned on 11,000 trajectories, and 75.2% with Llama3-70B. We will run it with the same checker used by our allocator, so that differences come from budget placement, not checker quality.
As external references on MuSiQue only, we will cite HopRAG at 42.20 EM and Reasoning Court at 36.0% EM; their setups differ and they are not controlled comparisons.
Every method receives the same calibration data, the same hyperparameter tuning budget, and is compared at matched total generated plus checker tokens. Beating a baseline means the allocator reaches the baseline's accuracy with at least 30% fewer tokens at two or more budget levels, or exceeds it at matched tokens beyond seed variance, on 3- and 4-hop MuSiQue questions.
The key ablation uses the identical gated resampler with uniform per-hop budgets. It isolates whether the cost model, rather than per-hop gating itself, produces the savings.
Why not just…?
Why not just use Best-of-N or self-consistency voting over full chains? Our first equation predicts that their cost grows like $\prod p_h^{-1}$, so they should do well on 2-hop questions and degrade sharply at 4 hops. Reasoning Court already notes that voting cannot recover when most chains share an error. Stratifying the token curves by hop count settles this question. If Best-of-N tracks the allocator at 4 hops, our central claim is false.
Why not just run process-reward tree search with a larger budget? This is the real threat, because tree search with a step scorer already gates hops implicitly. Our answer is narrower than "tree search is wrong." We claim that a uniform budget wastes tokens on easy hops and on hops already at the checker's floor. The uniform-budget ablation and the matched-token comparison against GRAT-style search test exactly this. If the savings vanish, the contribution reduces to the measured cost model, which remains useful as a predictive tool.
Why not just use a bigger model? A larger model raises $p_h$, which shrinks both costs, but it does not remove the floor if the checker shares the generator's errors. MultiHop-RAG shows open 70B-class models reaching only 0.32–0.36 accuracy even with gold evidence, so scale alone is not a reliable fix. We will fit the cost model at 8B and 70B and test whether the parameters measured at one scale predict curves at the other.
Decisive Checks
Three results would decide the proposal. First, the predicted curves must match observed accuracy versus tokens on held-out MuSiQue 2/3/4-hop questions within a few EM points; otherwise the model is wrong. Second, gated resampling must show a visible plateau near the predicted floor, and that plateau must move when the round-trip checker lowers $\alpha$. Third, the allocator must beat uniform gated search and CoRAG-style search at matched tokens on 3–4 hop questions. If only the first two hold, we still deliver a validated account of where multi-hop compute goes. If none hold, the precision–cost analogy does not transfer to language reasoning, and that negative result is also worth reporting.
References
- Log-concave sampling: Metropolis-Hastings algorithms are fast
- Interleaving Retrieval with Chain-of-Thought Reasoning for Knowledge-Intensive Multi-Step Questions
- Chain-of-Retrieval Augmented Generation
- Reasoning Court: Combining Reasoning, Action, and Judgment for Multi-Hop Reasoning
- GRAT: Guiding Retrieval-Augmented Reasoning through Process Rewards Tree Search
- HopRAG: Multi-Hop Reasoning for Logic-Aware Retrieval-Augmented Generation
- ♫ MuSiQue: Multihop Questions via Single-hop Question Composition
- MultiHop-RAG: Benchmarking Retrieval-Augmented Generation for Multi-Hop Queries