Revising Early Evidence in Multi-Hop Retrieval by Split Gibbs Sampling

Questions like "in what city was the director of Inception born?" need a language model to retrieve and chain several facts. Current systems do this one hop at a time. They pick a passage, deduce a bridge fact (Christopher Nolan), search again, and keep going. If the first passage is a distractor, every later hop builds on it, and nothing later in the process can go back and fix it. This note proposes treating the reasoning chain and the per-hop evidence as two separate variables tied together by a soft agreement score. The system alternates between resampling each one given the other. This is the "split Gibbs" trick from Bayesian imaging, where a hard problem is split into two easy conditional steps linked by a coupling penalty. Its key property here is that the evidence for hop 1 can be resampled after hops 2 and 3 have been drafted. Downstream reasoning can therefore overturn an early bad retrieval.

In two sentences: today's multi-hop retrieval systems act as filters, using only past information at each hop. We build a smoother, which revises each hop's evidence using both earlier and later hops, and we test whether this beats forward-only search, independent resampling and tree search at the same number of model calls. A second benefit comes from the same split. The model reasoning at each hop sees only that hop's chosen passage, not a growing pile of retrieved text, so the distraction caused by accumulated irrelevant context is also reduced.

Core Claim

The failure this targets is well documented. Hop, Skip, and Overthink diagnoses multi-hop reasoning errors on MuSiQue and other benchmarks. It finds that "early irrelevance," an irrelevant step near the start of a chain, collapses downstream reasoning, while irrelevant text after the answer barely matters. It also finds that model scale helps two-hop questions but plateaus on four-hop ones. That paper is purely diagnostic. HANRAG and GRAT both identify the same cascading-error mechanism, and their remedies differ from ours:

  • HANRAG routes queries and drops passages with a trained relevance discriminator, which is a hard gate.
  • GRAT runs Monte Carlo tree search with process rewards. It can abandon a branch, but its information still flows forward only.

Our claim is specific. When evidence choices are latent variables and are resampled conditioned on the whole drafted chain, the system recovers from first-hop distractors at a rate that forward-only methods cannot match at equal compute. This recovery should show up mainly on three- and four-hop MuSiQue questions, where the diagnosis paper says scale stops helping.

The Model

Let $Q$ be the question. Let $x = (q_1, a_1, \dots, q_K, a_K)$ be the reasoning chain of sub-questions and bridge answers. Let $z = (d_1, \dots, d_K)$ be the passage chosen as evidence for each hop, drawn from a candidate pool retrieved with each $q_k$. We target

$$p_\lambda(x, z \mid Q) \propto p_{\mathrm{LM}}(x \mid Q)\, \prod_{k=1}^{K} r(d_k \mid q_k)\, \exp\bigl(-\lambda\,[1 - s(d_k, q_k, a_k)]\bigr),$$

The terms are as follows:

  • $p_{\mathrm{LM}}$ is the language model's probability of the chain.
  • $r$ is the retriever's normalized score.
  • $s \in [0,1]$ is a support score saying how well passage $d_k$ backs answer $a_k$ to sub-question $q_k$.
  • $\lambda > 0$ is the coupling strength.

The support score combines two quantities: the model's likelihood of $a_k$ given $(q_k, d_k)$, and the query-generation score $P(q_k \mid d_k)$ borrowed from DAS. This mirrors the split Gibbs construction of Dobigeon et al.: reasoning plays the role of the likelihood variable, evidence plays the auxiliary variable, and the quadratic tether is replaced by a support potential. That replacement is the same move SGDD makes when it uses a Hamming potential for discrete tokens.

As in SGDD and PnP-SGS, $\lambda$ is annealed upward. Early sweeps let evidence and reasoning disagree so the sampler can explore. Later sweeps force the chain to agree with its evidence. A disconnected shortcut, meaning an answer not supported by any hop's passage, becomes improbable. This is the failure the DiRe analysis in MuSiQue exposes.

The sampler alternates two steps.

The evidence step resamples each $d_k$ given the current chain. It needs only scoring calls over a candidate pool. The pool is the union of the passages retrieved for $q_k$ and the passages retrieved for the later hops' text. Including later hops' text is what lets hop 3 point back to the right hop-1 passage.

The reasoning step picks a hop $k$ and proposes a new $(q_k, a_k)$ and suffix from the language model, which sees only $Q$, the earlier bridge answers and $d_k$. The proposal is accepted with a Metropolis–Hastings correction against the target above.

We are not claiming the convergence guarantees of Vono et al. or Paulin et al. carry over. Their dimension-free rates hold for log-concave continuous targets. They motivate the split but do not certify this sampler, which we treat as a practical approximate posterior search. The number of hops $K$ comes from the decomposer's proposal and can be changed by merge and split moves. A per-hop penalty gives a stopping rule, which we measure directly against the overthinking rates reported by Hop, Skip, and Overthink.

Research Program

The work has three parts.

Build the sampler. We construct the sampler on open-weight backbones, Llama3-8B and Llama3-70B, chosen so results line up with GRAT's reported numbers. We use the same retriever across all methods.

Measure recovery directly. MuSiQue annotates the supporting paragraph for each hop. For every question we can therefore record:

  • whether the first-hop evidence is correct after the initial forward pass;
  • whether it is correct after sampling;
  • whether final-answer correctness follows the corrected evidence.

Isolate the two ingredients. The note bundles two separable ideas: backward revision of evidence, and isolation of each hop's context. We test them separately so that a win cannot be attributed to the wrong cause.

The relationship to prior soft-evidence work is close and deserves stating. Claim-Dissector already treats sentence relevance as a latent variable to avoid pipeline cascades. It reaches a FEVER score of 76.5, but its authors report that it lags iterative systems on multi-hop HoVer because its relevance variables are independent across blocks. Our evidence variables are coupled through the chain, which is exactly what HoVer-style dependence requires. Superposition Prompting also isolates passages into parallel branches to suppress distraction. It does so only over a fixed, pre-retrieved set and cannot issue new hop-dependent queries. We keep its isolation idea and make it dynamic.

Baselines

The naive reference is single-shot retrieval followed by chain-of-thought answering with all retrieved passages in context. It is run with the same retriever and the same top-k.

The standard iterative baseline is IRCoT. It alternates one reasoning sentence with one retrieval and appends every passage to a growing context. It reports retrieval recall gains of 11–21 points and QA F1 gains of up to 15 points over one-step retrieval. We rerun it with our backbones and retriever.

The compute-matched sampling baseline is IRCoT with N independent sampled chains and a final selection by majority vote or by our support score. Here N is set so that the total number of generation calls and scoring calls equals our sampler's budget. We report budgets of 16, 32 and 64 calls per question and give every method the same prompt-tuning budget on a 200-question development split.

The strongest existing method is GRAT. Its reported number in the file is 75.2% accuracy on 2WikiMultihopQA with a Llama3-70B backbone, and 66.8% for a self-trained Llama3-8B. We rerun GRAT inference under our call budgets where its components can be reproduced, and otherwise compare against the reported figure with the backbone matched. On MuSiQue we found no absolute reported result on Lacuna for GRAT, IRCoT or HANRAG. HANRAG's reported MuSiQue gains are relative to Adaptive-RAG: nearly 7% EM and over 16% accuracy. The only absolute MuSiQue figure in the file is the original paper's 47.3 F1 for its best model. Every MuSiQue comparison will therefore use our own reruns.

Beating GRAT means matching its 2WikiMultihopQA accuracy at the 70B scale with fewer calls, or exceeding it at equal calls. It also means a statistically significant F1 gain on three- and four-hop MuSiQue at equal calls.

HANRAG's hard-gating design is reproduced as a baseline: a relevance classifier drops passages before the reader. This tests hard versus soft gating.

Three ablations isolate the key ingredients:

  • Forward-only. The candidate pool for $d_k$ excludes passages retrieved from later hops' text, and hops are only ever resampled left to right. This turns the method into a particle filter and isolates backward revision.
  • Hard coupling. $\lambda$ is fixed at its final value from the first sweep, which isolates annealing.
  • Accumulated context. The reasoner sees all chosen passages so far instead of only $d_k$, which isolates the context-isolation effect.

Why not just…?

Why not just sample many independent IRCoT chains and vote? This is the most serious threat. Independent sampling does reach chains with correct first-hop evidence some of the time, and voting may find them without any coupling. The compute-matched self-consistency baseline settles this. If it equals our sampler on three- and four-hop MuSiQue at every budget, the backward-revision story is wrong and we will report that. The proposal predicts the gap opens with hop count, because a correct first-hop draw becomes rarer under independent sampling as chains lengthen, while backward resampling targets the specific broken hop.

Why not just use tree search as GRAT does? Tree search backtracks by abandoning a branch and re-expanding from an earlier node. It throws away later hops that may have been correct, and its one-step rollouts read the noisy passage inside the node. Our forward-only ablation is close to a budget-matched search with no backward flow. The comparison against both it and GRAT shows whether reusing downstream hops to repair upstream evidence is worth anything beyond plain backtracking.

Why not just filter passages better before reasoning, as HANRAG does? A filter judges a bridge passage before the bridge entity is known. A passage about Nolan's filmography looks irrelevant to "what city?" until hop 2 asks about Nolan. The hard-gating baseline, together with the per-hop false-negative rate of its classifier on MuSiQue's annotated supporting paragraphs, measures how often that starvation happens. If false negatives are rare, soft coupling will add little, and the experiment will show it.

Why not just tell the model to say "unanswerable" when context is irrelevant? The DAS instructions of Cho et al. were validated on single-hop benchmarks. They cannot recognize an intermediate passage that answers nothing directly but is essential as a bridge. We fold the instruction into all baselines' prompts so that the comparison does not hand our method that advantage.

Proposed Experiments and Decisive Checks

We evaluate on four benchmarks. MuSiQue-Ans is reported in answer F1, broken down by hop count, with MuSiQue-Full used to test abstention on unanswerable contrast pairs. 2WikiMultihopQA and HotpotQA are reported in accuracy and EM. Bamboogle is included as a small out-of-distribution check.

The decisive check is a controlled distractor injection. For MuSiQue questions where all methods find correct first-hop evidence, we insert a hard negative at the top retrieval rank for hop 1: a passage about a same-type entity. We then measure the recovery rate, the fraction of questions whose final evidence and answer return to correct. Forward-only methods should recover only by chance. Our sampler should recover substantially more often at equal calls. If it does not, the central claim fails.

A second check uses the hop-level taxonomy of Hop, Skip, and Overthink to annotate a 300-chain sample for early-irrelevance errors and overthinking. We expect fewer early-irrelevance errors without a rise in hop count.

A third check tests disconnected reasoning. Using MuSiQue's DiRe-style probes, we test whether the annealed support potential lowers the rate of correct answers reached with unsupported hops.

Finally, we report wall-clock time and calls per question for every method. The proposal's practical value depends on the evidence step being scoring-only and therefore cheaper than the rollouts tree search needs.