Carrying Candidate Sets, Not Single Guesses, Through Multi-Hop Retrieval

Questions like "In what city was the director of Inception born?" cannot be answered with one search, because the second search depends on an intermediate answer, here the director's name. Iterative retrieval systems handle this by having a language model produce that intermediate answer, called the bridge entity, and then search with it. They commit to exactly one bridge entity per hop. If that guess is wrong, every later search is aimed at the wrong person, and the system confidently answers a different question.

We propose replacing this single guess with a small, calibrated candidate set of bridge entities. The set holds one entity when the model is sure and two or three when it is not. Each candidate drives the next search. Evidence found at the next hop then prunes candidates that the documents do not support. The idea is borrowed from classical NLP pipelines, where returning sets instead of single labels stopped upstream mistakes from blinding downstream modules. Because the method needs only sampling and retrieval, it works with closed API models.

Core Claim

Many terminal failures in multi-hop retrieval-augmented generation (RAG, where a model answers using passages fetched from an external index) are wrong bridge entities that the model had already considered. A sampled or alternative answer at that hop was correct, but it was discarded by the 1-best commitment. Two things follow if this is true. First, an adaptive candidate set calibrated on hop-level gold answers will recover a large share of these failures. Second, it should recover more of them per unit of compute than re-sampling whole reasoning chains, because it spends extra compute only at uncertain hops and lets retrieved evidence, rather than the model's own fluency, decide among candidates. We also claim that the benefit concentrates at hops whose errors amplify downstream. This should be predictable from a measured per-hop sensitivity, in the sense formalized by On the Design and Analysis of LLM-Based Algorithms.

Where This Sits

Three lines of prior work motivate the gap.

IRCoT interleaves chain-of-thought sentences with retrieval and gains 11–21 recall points. However, it is a linear chain, and its authors note that noisy intermediate retrievals send reasoning off course. CoRAG trains Llama-3.1-8B to produce sub-queries and sub-answers, and adds best-of-N and tree search at test time. Its chain scoring relies on a surface heuristic, the presence of "information not found" tokens. GRAT runs Monte Carlo tree search with process rewards over sub-question rollouts. All three diversify at the level of whole chains or sub-questions. None asks which specific intermediate commitment is uncertain, and none sizes the hedge to that uncertainty.

Two works supply the method. Heid et al. predict part-of-speech tags as sets, choosing set size with a utility that trades correctness against set size. Their sets average about two tags and keep pipelines usable when 1-best accuracy drops below 50%. That work is confined to token classification; we carry the same decision rule over to generated entities inside a retrieval loop. Li et al. model LLM pipelines as graphs in which a node's sensitivity $S$ governs whether its errors grow or shrink downstream. They validate this only on synthetic tasks, and we use it as a measurement tool on real multi-hop QA.

Two works constrain the design. Li et al.'s "Type-B trap" warns that finer decomposition hurts when intermediate nodes produce false positives. A candidate set is a deliberate injection of false positives, so pruning is not optional: without it, the proposal should fail exactly as their analysis predicts. FB-RAG appears to point the other way, since its wrong draft answers still guide retrieval well (its "imperfect guide" effect). We reconcile the two by distinguishing the kind of error. A draft can be factually wrong yet share terminology with the right evidence. A wrong bridge entity shares nothing with the right second-hop document. We test this distinction directly below.

Before Reasoning Can Fail shows that many agent failures are procedural: the agent never reads the documents at all. That class of failure is orthogonal to ours. We control for it by always reading the retrieved passages, and we report it separately.

Research Program

Diagnosing the failures. The first step is a hop-level error audit on MuSiQue (Trivedi et al. 2022). MuSiQue is built by composing single-hop questions, so every hop has a gold sub-answer. That lets us label, for each failed chain, the first hop where the bridge entity went wrong. For that hop we then measure coverage: the fraction of cases in which the gold entity appears among $K$ samples from the model. This coverage is the ceiling of the whole idea.

Measuring sensitivity. In the same audit we estimate per-hop sensitivity $S_t$ by intervention. We substitute a plausible wrong entity at hop $t$, holding everything else fixed, and measure the change in final-answer error. This turns Li et al.'s parameter into a quantity measured on natural-language QA.

Building the sets. At each hop we sample $K$ sub-answers, normalize them to entities, and estimate a probability $p(e)$ for each entity $e$ from its sample frequency. We then return the set that maximizes Heid et al.'s set utility. The utility's one free parameter is calibrated by split conformal prediction on MuSiQue training sub-answers, so that the set contains the gold bridge entity with a target probability $1-\alpha$. Here $\alpha$ is a chosen miss rate, for example 0.1.

Pruning. Each surviving candidate issues its own next-hop query. A candidate is pruned when its retrieved passages fail a check by the same model. The check asks whether a passage both mentions the candidate and answers the next sub-question about it. This is the backward signal that linear pipelines lack: downstream evidence revokes an upstream commitment. A global cap on live branches keeps cost bounded.

Everything above uses sampling and text only, unlike DRAGIN, which needs access to the model's attention and log-probabilities.

Baselines

The naive reference point is single-step RAG with the same retriever and reader. CoRAG reports single-step MuSiQue retrieval recall of 29.0% for this setting.

The linear iterative baseline is IRCoT run with our backbone. It isolates exactly what we change: one bridge entity per hop instead of a set.

The strongest competitor is CoRAG's best-of-N and tree-search decoding. It is the most direct alternative way to spend extra test-time compute on the same failure. CoRAG reports MuSiQue retrieval recall rising to 47.1% and gains of more than 10 exact-match points over IterDRAG and Search-o1-32B. We will use the released CoRAG-8B where possible, and otherwise Llama-3.1-8B-Instruct with matched prompting. Fairness rests on three controls: identical corpora and retriever, a matched budget of total generated tokens and retrieval calls (swept across five budget levels), and the same calibration data available to both methods. Beating CoRAG means a higher exact-match/F1 curve across matched budgets, not merely at one point.

For tree search we cite GRAT's reported 75.2% accuracy on 2WikiMultiHopQA with Llama3-70B, and 66.8% for Llama3-8B after self-training (60.6% before). For our 8B comparison the target to beat is GRAT's untrained 8B search at matched compute. We will rerun it rather than rely on the reported numbers, because its budget was not matched to ours. DRAGIN reports 2WikiMultiHopQA F1 of 0.3931 with LLaMA2-13B, which serves as a white-box reference.

Three ablations isolate the key ingredient. A fixed set of size $K$ at every hop tests whether adaptivity matters. Calibrated sets without evidence pruning test whether the backward signal matters; this variant should fall into the Type-B trap. Uncalibrated top-$K$ sets test whether conformal calibration matters.

Why not just…?

Why not just sample N whole chains and vote, as CoRAG does? This is the real threat. If wrong bridge entities are rare and uncorrelated, independent chains will cover them nearly as well. Our case rests on two mechanisms. Chain-level sampling spends compute on hops that were already certain, and it selects among chains by the model's own judgment rather than by whether the next hop's evidence exists. The matched-compute curves settle the question. If best-of-N matches us at every budget, the set-valued idea adds nothing, and we will report it that way.

Why not just retrieve more passages per hop? A larger top-$k$ helps when the right document is ranked low, but a wrong bridge entity makes the query itself wrong, so no depth of retrieval recovers the right document. We test this by sweeping $k$ for IRCoT, matched in passages read, and by splitting failures into "right entity, document ranked low" versus "wrong entity." Chawla et al. and Khattab et al. already document that very large contexts add noise.

Why not just use a bigger model? IRCoT showed that a 3B model with iterative retrieval beat 175B single-step retrieval, so scale does not replace structure. Scale might still shrink bridge-entity errors enough to make sets moot. We therefore run the audit and the main comparison at both 8B and 70B, and report whether the coverage gap narrows with scale.

Why not just use GRAT's tree search? Tree search does hedge, but it scores branches with one-step rollouts that can themselves hallucinate, at large token cost. Our sets are a targeted, evidence-pruned form of branching. The matched-budget comparison above decides between them.

Proposed Experiments

The main benchmarks are MuSiQue-Ans, chosen for its shortcut resistance and hop-level gold, and 2WikiMultiHopQA (Ho et al.), whose Wikidata triples give gold bridge entities. HotpotQA (Yang et al.) serves as a weaker-shortcut control. We report answer EM/F1, retrieval recall, the hop-level bridge-entity error rate, average set size, empirical set coverage against the target $1-\alpha$, and tokens per question.

The first decisive check is a pre-registered kill criterion. If the gold bridge entity appears in the $K=8$ samples for fewer than a quarter of first-error hops on MuSiQue, the ceiling is too low and we stop.

The second check is the matched-compute curve against CoRAG decoding.

The third check tests whether the gains are predictable. The measured $S_t$ should predict where the gains occur: hops with $S_t>1$ should account for most of the recovered errors, and on hops with $S_t<1$ the sets should give little benefit.

The fourth check tests the FB-RAG reconciliation by corrupting either the terminology or the entity of an intermediate draft. If the reconciliation is right, entity corruption should degrade retrieval sharply while terminology corruption degrades it only mildly.