Spend Compute Where the Chain Breaks: Hop-Level Allocation for Multi-Hop QA

Questions like "Where was the director of the film that won Best Picture in 1998 born?" can only be answered in stages. Each stage resolves a bridge entity, an intermediate answer such as the film or its director, and that entity becomes the search query for the next stage. Current systems that spend extra compute at answer time on these questions spend it at the level of whole questions. They sample many complete reasoning chains and vote, run tree search over every sub-question, or wrap every step in verification and rollback. Most hops in a multi-hop question are easy, though, and a chain usually fails at one identifiable hop, where the wrong bridge entity was retrieved and everything downstream inherited the mistake. We propose to treat the hop, not the question, as the unit of compute allocation. At each hop, a few cheap resolver agents independently propose the bridge entity. A small running statistic of their agreement decides whether to stop or to spend more samples and a verifier on that hop alone. The only state the system keeps per question is a short table of candidate entities and vote counts per hop, never full transcripts.

In two sentences: multi-hop errors are local, so extra compute should flow to the specific hop where independent agents disagree about the bridge entity. Doing this with an entity-level state table should match or beat whole-chain voting and full backtracking at a fraction of the calls and memory. The idea sits where four research threads meet. Answer-time compute scaling supplies the budget question. Multi-agent decomposition supplies independent resolvers and verifiers. Multi-hop QA supplies the failure mode. Per-sample state tracking, borrowed from training-time methods that keep one small statistic per example, supplies the bookkeeping, moved from "per training prompt" to "per hop of one test question."

Core Claim

Given a fixed budget of model calls, allocating calls across hops according to a per-hop agreement statistic will yield higher answer F1 on 3- and 4-hop MuSiQue questions than spending the same calls on whole-chain self-consistency or uniform per-hop search. The advantage should grow with hop count, because the fraction of wasted calls on easy hops grows with chain length. The per-question memory the controller needs should be bounded by (hops × candidate beam) short strings, not by the length of the reasoning transcript. The claim is falsifiable at the hop level, not only the answer level. MuSiQue is built by composing single-hop questions (MuSiQue), and 2WikiMultiHopQA ships gold evidence triples (Constructing A Multi-hop QA Dataset). We can therefore check directly whether disagreement fires on the hop whose bridge entity is actually wrong.

What Exists and How This Differs

The closest system is ReAgent. It splits multi-hop QA across decomposition, retrieval, verification and assembly agents, adds supervisor agents that roll the whole system back to earlier checkpoints, and reports HotpotQA F1 of 0.795 with GPT-4o against 0.661 for O1 and 0.696 for O3. That comes at an average of 29 model calls per question, with state held as uncompressed text logs. ReAgent motivates this proposal by showing that reversibility pays. It also constrains it: we must beat or match its accuracy per call, not just its accuracy. We differ in three ways. We never roll back the whole system; we re-open a single hop. We decide where to spend compute from an agreement statistic rather than always verifying. And our checkpoints are entity tables rather than transcripts.

GRAT frames retrieval-augmented reasoning as Monte Carlo tree search guided by a learned process-reward model, reaching 75.2% on 2WikiMultiHopQA with Llama3-70B. It searches every sub-question with the same machinery. Search-in-Context combines tree search with dynamic loading of cached attention states over long documents, and reports Llama-3.1-8B at 59.87 F1 on MuSiQue versus 40.75 for a full-context 70B model. Both show that search helps multi-hop QA. Neither asks which hops need search, and both require either a trained evaluator or architectural cache indexing. Our controller needs neither.

CMT-RAG keeps an addressable graph of sub-question traces alongside a recurrent memory. Its evidence that discrete, addressable traces matter for resolving bridges is why our state is a table of explicit entity strings rather than compressed vectors in the style of GradMem. Unlike CMT-RAG's graph, which only grows, our table supports pruning and re-opening a hop.

The allocation principle comes from Allocation, Not Volume. There, an orchestrator that stops early on easy forecasting questions and researches only uncertain ones reached 80.7% at $0.18 per question, against 78.1% at $0.90 for a static ensemble. That allocation is per question and on binary forecasts. We move it inside a question, to hops. The statistic comes from MoPPS, which keeps a Beta posterior per training prompt to predict difficulty online and cut RL rollouts by 78.46%. We reuse the same cheap Bayesian bookkeeping at test time, per hop. The verifier design follows Multi-Agent Verification, which scales committees of prompted aspect verifiers and itself names static verifier assignment as a limitation. We invoke a verifier only at contested hops.

Research Program

The system has three roles. A decomposer turns the question into a sequence of hop templates ("the film that won X" → "the director of [film]" → "birthplace of [director]"). Resolver agents each take a hop with its bridge slot filled, write their own retrieval query, retrieve, and return a candidate entity plus the supporting sentence. Resolvers are deliberately varied through different query rewrites, retrievers (sparse versus dense), and prompts, so that their errors are less correlated. An evidence verifier checks whether the quoted sentence actually supports the entity for the hop template. The verifier is called only when resolvers disagree.

The controller's state for hop $h$ is the list of candidate entities with vote counts. After $n_h$ resolver calls, with $k_h$ agreeing on the modal entity, it holds a Beta posterior over the resolvers' agreement rate $p_h$ and stops sampling that hop once

$$ \Pr\left(p_h > \tfrac{1}{2} \,\middle|\, k_h, n_h\right) = 1 - I_{1/2}(1+k_h,\, 1+n_h-k_h) > \tau , $$

where $I_{1/2}$ is the regularized incomplete Beta function evaluated at one half and $\tau$ is a confidence threshold tuned on a development split. Easy hops stop after two or three agreeing calls. Contested hops draw more resolvers, then the verifier, subject to a global per-question call budget $B$. If the answer-assembly step later finds a contradiction, for example when no resolver can fill the next hop from the current bridge, the controller re-opens the most recent hop with the lowest posterior and promotes its runner-up entity. This is local backtracking driven by the table, with no transcript replay. Memory per question is the table itself, a few dozen short strings. We will measure it in bytes against ReAgent-style transcript logs, since under batched serving of many questions the transcript approach is exactly the per-sample linear state overhead that training-time stateful methods struggle with.

The analysis program has three parts. We will first measure how localized multi-hop errors actually are, using gold intermediate answers: what fraction of wrong final answers trace to a single wrong bridge. We will then measure how well each candidate signal flags that hop. The candidates are resolver disagreement, token log-probability of the bridge entity, and verifier rejection. Finally, we will measure how accuracy trades against calls as $B$ varies.

Baselines

The naive reference point is single-pass iterative retrieval with chain-of-thought, IRCoT, which uses each intermediate reasoning step as the next search query in one thread. It fixes the floor at roughly five to ten calls. No reported result for IRCoT on these benchmarks was found on Lacuna in the file, so we will run it ourselves with the same backbone, retriever and corpus.

The strongest cheap competitor is whole-chain self-consistency: run $N$ independent IRCoT chains and majority-vote the final answer, with $N$ set so that total calls equal our budget $B$. This is the fairest direct test of our claim, because it spends identical compute without hop-level targeting. We beat it only if our F1 is higher at matched calls on 3- and 4-hop MuSiQue, with bootstrap confidence intervals that exclude zero difference.

The strongest existing method on the accuracy axis is ReAgent. Its reported HotpotQA F1 is 0.795 with GPT-4o at about 29 calls per question (ReAgent). No released code is listed in the file, so we will reimplement its local and global backtracking with our backbone and retriever. We will report our system's F1 at 29 calls and the number of calls it needs to reach ReAgent's F1. Beating it means equal F1 at clearly fewer calls, or higher F1 at equal calls. On 2WikiMultiHopQA, GRAT's 75.2% with Llama3-70B (GRAT) is the external reference. Because GRAT uses a trained process-reward model and self-training, we report it as context rather than a matched comparison. On MuSiQue, Search-in-Context's 59.87 F1 with Llama-3.1-8B (Search-in-Context) is the reference in its long-context setting. We will run our method in that same setting with the same 8B model for comparability.

Three ablations isolate the key ingredient. The first is uniform per-hop allocation: the same total calls spread evenly across hops. This tests whether targeting matters or whether hop-level voting alone explains the gains. The second swaps the trigger, replacing resolver disagreement with the log-probability of the bridge entity. The third removes local re-opening, so the system commits after each hop.

Why not just…?

Why not just sample more whole chains and vote? This is the most serious threat. If most failures are spread across hops rather than concentrated in one, or if a wrong early bridge usually produces diverse wrong final answers, final-answer voting may recover nearly as well. There is some evidence against pure volume. Multi2 sees gains plateau around five samples in multi-document settings. Zero-Overhead Introspection reports up to 12% absolute over majority voting on AIME 2024 at equal or lower compute by allocating adaptively. Inverse Scaling in Test-Time Compute warns that unverified extra generation can hurt. None of these is multi-hop QA, so the matched-budget curve against self-consistency is the decisive experiment. If the two curves overlap, we will report that hop targeting does not pay and the proposal reduces to an error-localization study.

Why not just trigger on the model's own token uncertainty, as DRAGIN does? DRAGIN decides when to retrieve from attention and token uncertainty. That signal is free, whereas disagreement costs two or three calls per hop. The worry about self-confidence is that a model reading a wrong but fluent passage becomes confidently wrong. ReAgent's motivation and the tension between Chen et al. and the unverified-scaling results both point to this weakness in multi-hop settings. The trigger-swap ablation and the per-hop error-flagging comparison against gold intermediate answers settle it. If log-probability flags bad hops as well as disagreement does, we adopt it and drop the extra calls, keeping the hop-level allocation and entity table as the contribution.

Why not just use full backtracking, or a stronger reasoning model? ReAgent already shows backtracking helps, and o-series models are one call. But ReAgent's own numbers put O1 and O3 below it on HotpotQA (0.661 and 0.696 versus 0.795), so a stronger single reasoner is not obviously enough. Its 29 calls per question are the cost we are trying to cut. The comparison at matched calls, and the calls-to-reach-0.795 measurement, answer this directly.

Proposed Experiments

We will use MuSiQue-Ans in both the distractor-paragraph setting and an open-corpus setting as the primary benchmark, stratified by 2, 3 and 4 hops. We will use 2WikiMultiHopQA and HotpotQA distractor as secondary benchmarks, and Bamboogle as a small held-out check (no reported result found on Lacuna for Bamboogle). Backbones are Llama-3.1-8B-Instruct and a 70B model, with a fixed retriever shared by all methods. Metrics are answer exact match and F1, per-hop bridge accuracy against gold intermediate answers, calls and tokens per question, and controller memory in bytes per question.

The first decisive check is localization. On questions a single IRCoT chain gets wrong, we measure the area under the ROC curve for identifying the first wrong hop with disagreement, log-probability and verifier signals. We also count "confidently wrong" hops where all resolvers agree on the wrong entity, since those set a ceiling on any disagreement-based method. If more than about half of failures are confidently wrong even with diverse retrievers, the method cannot work, and we will report that as the finding.

The second check is the accuracy-versus-calls curve for our method, self-consistency, uniform per-hop allocation and reimplemented ReAgent at budgets from 5 to 40 calls. The prediction is that the gap over self-consistency is near zero on 2-hop questions and widens on 4-hop ones.

The third check is memory and latency. We compare state size and wall-clock per question against transcript-based backtracking under batched serving of 1,000 questions. The prediction is that our state stays roughly constant in reasoning length while transcript state grows with calls.