Calibrated Hop Likelihoods for Fast Multi-Hop Retrieval

Answering a question like "In what city was the director of Inception born?" takes two hops. The system must first find the director, and only then can it search for the birthplace. Current systems that answer such questions well pay for it at test time. Some interleave writing and searching step by step. Others go further and run a full tree search over alternative sub-questions, scored by a separate judge model. Machine translation has faced the same tension between quality and speed, and it found a cheaper fix: train the generator so that its own probability of an output tracks how good that output is. After that, a small beam search picks good outputs without any external scorer. We propose to carry this idea from translation into multi-hop question answering, one hop at a time.

The claim is concrete. Take each intermediate step: the sub-question the model writes and the bridge entity it proposes. Fine-tune the model so that its length-normalized likelihood for that step correlates with whether the step is actually supported by the evidence. Once that holds, a narrow beam search over hops, ranked only by the model's own scores, should recover most of the accuracy of process-reward tree search. It should do so with no verifier calls, and it should widen the search only at hops where the model's calibrated confidence is low. In two sentences: tree search wins because it explores alternatives and prunes them with a judge. If the generator's own probabilities become a trustworthy judge, a cheap beam can do that pruning.

Where this sits

The method comes from Calibrating Translation Decoding with Quality Estimation on LLMs. That paper traces the "beam search curse" to a mismatch between likelihood and quality: quality stops improving, or drops, as the beam widens. It fixes the mismatch by training a 7B model with a negative-Pearson loss against CometKiwi scores. With a beam of 5, that model matches a 70B model reranking 100 samples, which is about a 200x latency saving. That work ranks finished single outputs. It never faces the problem of a multi-step chain where a wrong step can derail every later step. A related translation result, Direct Preference Optimization for Neural Machine Translation with Minimum Bayes Risk Decoding, uses preference training to fold 32-candidate consensus decoding into the weights (62.3 versus 62.5 BLEURT on WMT21 zh-en). It also acts as a constraint on our design: its authors report that weak regularization produces overconfident, looping models, a failure we must watch for.

Several papers motivate the problem. GRAT frames multi-hop retrieval as Monte Carlo tree search with process rewards and backtracking. It reaches 75.2% on 2WikiMultiHopQA with Llama3-70B, and its ablations show that exploration and retrieval both matter. IRCoT shows that interleaving retrieval with reasoning beats one-shot retrieval, even against models far larger. Optimizing Multi-Hop Document Retrieval Through Intermediate Representations puts a number on the latency cost: iterative methods take more than 20 s per query on 2WikiMultiHopQA, against about 2.8 s for its layer-wise retrieval. That layer-wise method has no way to check a candidate path, though, and it has been shown mainly on two hops.

Three systems are closest to ours, and each differs in a specific way. Speculative RAG keeps a verifier at test time and states that it is weaker on bridge-type questions. EVO-RAG trains the policy with DPO to take fewer retrieval actions. It does not make step likelihoods meaningful as scores. DRAGIN triggers retrieval from raw entropy and attention. Nothing in DRAGIN trains that entropy signal to track correctness.

Our proposal differs from all of these in what is trained. We train the hop-level probability itself to be a calibrated measure of evidence support. That one trained signal is then used for three jobs: ranking candidate steps during search, deciding when to widen the beam, and deciding when to stop.

Core mechanism

Training starts with candidate generation. For each training question and each hop $t$, we sample $N$ candidate steps $z_1,\dots,z_N$. Each candidate is a short sub-question plus a proposed bridge entity, conditioned on the question $x$ and the evidence gathered so far, $c_{<t}$. Each candidate gets a teacher score $q_j \in [0,1]$ from two sources:

  • Gold annotations. MuSiQue and 2WikiMultiHopQA provide decompositions and supporting facts. A candidate scores on whether its bridge entity matches the gold intermediate answer and whether the passage it retrieves is a gold supporting paragraph.
  • A process-reward model. For questions without annotations, we use a GRAT-style process-reward model, queried offline only.

The training objective is

$$\mathcal{L} = \mathcal{L}_{\text{SFT}} - \lambda \,\rho\!\left(\left\{\tfrac{1}{|z_j|}\log p_\theta(z_j \mid x, c_{<t})\right\}_{j=1}^{N},\ \{q_j\}_{j=1}^{N}\right),$$

where $\mathcal{L}_{\text{SFT}}$ is ordinary fine-tuning on the best trajectory, $\rho$ is the Pearson correlation computed within each hop's candidate set, and $\lambda$ trades calibration against fluency. The $\mathcal{L}_{\text{SFT}}$ term plays the role the KL constraint plays in DPO-MBR: it guards against overconfidence.

Inference uses beam search over hops, not over tokens. At each hop the model proposes $B$ steps, with $B$ at most 5, and ranks them by calibrated likelihood. Each surviving step triggers one retrieval. The beam collapses to width 1 whenever the top candidate's normalized log-likelihood beats the runner-up by a margin $\delta$, tuned on held-out data. The answer is emitted when the calibrated likelihood of a final-answer step crosses a threshold. Hop texts are short, so the cost per hop is a few dozen decoded tokens and one retrieval call. There are no verifier forward passes and no rollouts.

Research program

The first stage is a diagnosis, run before any training. On 2WikiMultiHopQA and MuSiQue dev sets, we measure how well the base model's hop likelihood and entropy correlate with hop correctness. We also measure accuracy as a function of hop-beam width, to test whether the multi-hop setting shows the same beam curse that translation does. If raw likelihood is already well correlated, the training stage is pointless, and we will report that result.

The second stage builds the calibrated model. We train Llama3-8B, the base GRAT also uses for self-training, on MuSiQue and 2WikiMultiHopQA training splits with the loss above, sweeping $\lambda$ and $N$. Bamboogle is held out entirely to test generalization.

The third stage isolates the ingredients. Holding the trajectories fixed, we compare four training variants: supervised fine-tuning only, fine-tuning plus calibration, DPO on best/worst hop pairs, and a hidden-state probe. Holding the trained model fixed, we vary the inference controller across greedy decoding, fixed beam, adaptive beam, and full tree search.

Baselines

The naive reference point is single-shot retrieval with greedy answering, plus the same 8B model with standard IRCoT interleaving. These show how much the multi-hop structure alone buys.

The strongest accuracy competitor is GRAT's tree search with process rewards. We will run it on the same 8B base, the same Contriever-style retriever, and the same index, so that accuracy and wall-clock latency are measured on identical hardware. The strongest efficient competitor is GRAT's self-trained 8B model. On 2WikiMultiHopQA, GRAT reports that fine-tuning Llama3-8B on 11,000 search trajectories raised accuracy from 60.6% to 66.8%. We will reproduce this on our exact trajectories, so that our method differs from it only by the calibration term and the hop-beam decoder.

Other reported numbers frame the comparison, though their settings differ. L-RAG reports 0.352 accuracy on MuSiQue and about 2.8 s per query. DRAGIN reports 0.3931 F1 on 2WikiMultiHopQA with LLaMA2-13B. EVO-RAG reports up to +4.6 Exact Match with 15% fewer retrievals. We will rerun L-RAG and DRAGIN on our 8B base where code permits. For HotpotQA and Bamboogle we found no absolute numbers for these baselines on Lacuna.

Every trained variant gets the same trajectories, the same number of gradient steps, and the same hyperparameter-search budget.

Beating the baselines means two things on 2WikiMultiHopQA and MuSiQue. First, accuracy within one point of 8B tree search at no more than one-fifth of its median latency. Second, a clear accuracy gain over the reproduced self-trained 8B model at comparable latency. The decisive ablation is supervised fine-tuning with versus without the calibration term, using the identical hop-beam decoder.

Why not just…?

Why not just use a larger model with one-shot retrieval? A bigger model cannot read a passage that was never retrieved. The bridge entity is absent from the question, and IRCoT shows a 3B interleaved model beating 175B GPT-3 with one-step retrieval. We include a 70B one-shot run as a reference point, but we do not expect it to threaten the result.

Why not just widen the beam? That only helps if likelihood tracks quality. The translation paper shows it does not without calibration, and HARP reports that beam search costs about 3x more compute for lower accuracy. Our first-stage diagnosis tests this directly in the multi-hop setting: accuracy as a function of beam width, before and after calibration.

Why not just fine-tune on tree-search trajectories? This is a real threat, since GRAT's self-training already closes much of the gap. Imitation teaches the model which path to take. It does not teach the model to recognize a wrong step it might still generate, so its probabilities cannot guide branching. The decisive ablation settles this: if fine-tuning alone plus a hop beam matches the calibrated model, calibration adds nothing.

Why not just bolt a cheap probe onto hidden states to score hops? This is the most serious alternative. A linear probe trained on the same scores $q_j$ costs almost nothing per candidate and could rerank as well as calibrated likelihood. Our hypothesis is that calibration also changes which candidates get generated, so fewer wrong bridge entities enter the beam at all. We will measure two things: how often the gold bridge entity appears among the top-$B$ candidates, and final accuracy, for probe reranking versus calibrated likelihood. If the probe matches on both, we will report that a probe is enough, and the contribution narrows to the diagnosis and the adaptive-width controller.

Why not just DPO the hop preferences, as in EVO-RAG or DPO-MBR? DPO pushes the preferred candidate above the rejected one. It does not make likelihood track how good a candidate is across the whole candidate set, and the DPO-MBR authors report overconfidence and loops when regularization is weak. We will run DPO on the same pairs, with a sweep over its regularization strength $\beta$, and compare how well each method's confidence matches actual hop accuracy, alongside final accuracy.

Decisive checks

Three checks decide whether the idea holds. First, calibration must raise the within-hop correlation between likelihood and correctness, and accuracy must then rise, rather than plateau, as the hop-beam widens. Second, at matched wall-clock budgets, the calibrated hop-beam must trace a better accuracy-versus-latency curve than both 8B tree search and the self-trained 8B model. We break results out by question type, because Speculative RAG reports weakness on bridge questions, and by the 2-, 3- and 4-hop subsets of MuSiQue, where errors compound. Third, the gains must hold on held-out Bamboogle, and the model must not show the looping that DPO-MBR warns about. We check for loops by tracking repetition rate and answer length across values of $\lambda$.

If the calibrated model fails the first check, the translation fix does not transfer to chains of reasoning. That would itself be a useful negative result about where likelihood-based search can and cannot replace a judge.