Denoising Hop-Level Labels for Multi-Hop Retrieval Agents

When a question-answering system has to chain several searches together ("where was the director of Inception born?"), the error that matters most is usually an early search that misses the bridging document. Everything after that point is built on the wrong evidence. Training systems to notice and repair such failures needs labels for each search step saying whether that step found what it needed. Those labels almost never exist. Current practice instead copies the correctness of the final answer onto every step, or asks one model to judge each step. We propose borrowing the machinery of programmatic weak supervision. In that approach, people write many cheap, noisy rule-like checks called labeling functions, and a statistical label model combines their conflicting votes into calibrated probabilities without seeing any ground truth. We would apply it here to the hops of a search trajectory, producing a denoised probability that each hop is on track, off track, or complete.

The core object is a small hidden Markov model over hops. It extends the linked hidden Markov model of Weakly Supervised Sequence Tagging from Noisy Rules, a model that aggregates noisy rules over the tokens of a sentence. Here the sequence is instead one agent's sequence of retrieval actions. The resulting per-hop posteriors train a lightweight hop verifier. That verifier then does three jobs: it filters self-training trajectories, it triggers re-retrieval when a hop has probably failed, and it stops search once evidence is probably sufficient. If the approach works, agents can be taught to detect cascading retrieval failures in domains where no gold supporting facts or optimal hop counts exist.

Core Claim

Several weak signals are individually unreliable, but their errors are partly independent. Examples include "the sub-question's answer string appears in the retrieved passage," "this passage is hyperlinked from the previous hop's passage," "a small entailment model says the passage answers the sub-question," "this query retrieves documents already seen," "the final answer was correct," and "the answer can be re-derived with reasoning masked." A generative label model can estimate each signal's accuracy from the pattern of agreements across many unlabeled trajectories, as Data Programming: Creating Large Training Sets, Quickly showed for independent classification examples. We claim this estimation carries over to trajectories if the model encodes one structural fact: failure cascades. An off-track hop tends to stay off track unless the agent reformulates.

The per-hop labels this produces should be more accurate than outcome-only labels, more accurate than any single judge, and better calibrated than an unweighted vote. Better step labels should in turn yield better downstream agents at equal compute.

The motivation for doing better than outcome labels comes from Diagnosing Search Behavior and Failure Modes in Long-Horizon Search Agents. That study found that agents which retrieved gold evidence were correct 73.8% of the time and agents which missed it were correct 2.2% of the time. So outcome-derived step labels are wrong in both directions: a trajectory can fail after good retrieval, or succeed by luck after bad retrieval. The same paper found that incorrect trajectories run 2–3x longer, ending in a "wasted tail" of redundant searches. Stopping is therefore as important as recovery.

The Model

For a trajectory with hops $t = 1..T$, let $z_t \in \{\text{on-track}, \text{off-track}, \text{done}\}$ be the latent state of hop $t$, and let $\lambda_{m,t}$ be the vote (or abstention) of labeling function $m$ on that hop. The label model is

$$ p(z, \lambda) = p(z_1)\prod_{t=2}^{T} p(z_t \mid z_{t-1}) \prod_{t=1}^{T}\prod_{m} p(\lambda_{m,t} \mid z_t), $$

where the transition table $p(z_t \mid z_{t-1})$ captures cascading. Off-track is sticky and done is absorbing. Each emission table $p(\lambda_{m,t} \mid z_t)$ is one labeling function's unknown accuracy and abstention rate, fit by expectation-maximization on unlabeled trajectories.

Following the linked HMM, we add linking rules between adjacent hops. For example, "hop $t+1$ retrieved a document already retrieved at $t$" votes that the two hops share a state, and "the query at $t+1$ names an entity first seen in hop $t$'s passage" votes on-track for both. The final-answer check enters only as an emission on the last hop, so its evidence spreads backward through the transitions rather than being copied uniformly onto every step. Two existing heuristics become just two more labeling functions whose accuracies the model estimates rather than trusts: the masked re-derivation check from RASPberry, and the lexical grounding score behind retrieval-grounded voting.

Research Program

The work has three parts.

The first part builds a library of roughly 10–20 labeling functions across four families: lexical and entity checks, hyperlink and structure checks, small-model judgments (an entailment model and an 8B self-judge), and trajectory-level checks (redundancy, answer type, final correctness, masked re-derivation). We also fit the hop-level label model. Trajectories come from an off-the-shelf ReAct/IRCoT-style agent on the training splits of HotpotQA, 2WikiMultihopQA and MuSiQue. Gold supporting facts are withheld from everything except evaluation.

The second part distills the posteriors into a hop verifier, a small classifier over (question, prior hops, current passage), trained with soft cross-entropy. Distillation is the standard third stage of data programming. Here it matters because several labeling functions, such as final correctness, are unavailable at test time. The verifier learns to predict their consensus from the trajectory alone.

The third part uses the verifier in three places. It replaces final-answer filtering in self-training, where only trajectories whose hops are all likely on-track are kept. It triggers backtracking with re-retrieval when the probability of being off track crosses a threshold. It stops search when the probability of done is high. This last use targets the unsupervised stopping problem that FrugalRAG handles only by supervising against known optimal hop counts.

This differs from the closest work in specific ways. GRAT runs tree search with process scores but keeps self-training trajectories based on final-answer correctness. We replace that filter with estimated step labels. RASPberry validates candidates with a single consistency check at heavy tree-search cost; we treat that check as one noisy source among several. Beyond Confidence aggregates parallel rollouts by lexical overlap with retrieved text, after showing that token log-probabilities are inflated by copying (+0.50 nats on copied tokens). We keep its lesson not to trust raw confidence, but we model the grounding score's own error rate. That matters because it rewards "well-grounded but wrong" answers in about 4% of cases. Baleen uses a heuristic latent hop ordering for retriever training and needs sentence-level labels for its condenser, which its authors note are scarce outside HotpotQA and HoVer. Our method needs neither. MoPo requires clean posterior summaries of gold knowledge; we require none.

Baselines

The naive reference point is outcome labeling: every hop inherits the final-answer correctness of its trajectory, as in GRAT's filtering. For downstream results, the naive agent is IRCoT as specified in Interleaving Retrieval with Chain-of-Thought Reasoning. MoPo reports IRCoT at 56.2 F1 on downstream HotpotQA.

The strongest single-judge competitor is an LLM-as-judge that sees the hop and rates it directly. We run it at 8B, the size used inside our library, and again at 70B to test whether scale alone closes the gap. Both use the same prompts and the same trajectories.

The strongest existing systems are the following:

  • RASPberry on HotpotQA reports 68.89 F1 with LLaMA-3.1-8B.
  • FrugalRAG reports 68.47% model-based evaluation with 2.05 searches on HotpotQA.
  • GRAT self-training reports 2WikiMultiHopQA accuracy rising from 60.6% to 66.8% after fine-tuning Llama3-8B on 11,000 GRAT trajectories.
  • Retrieval-grounded voting reports up to +35% on minority-correct questions; we found no absolute HotpotQA number for it on Lacuna.
  • MuSiQue: we found no reported result on Lacuna for any of these systems.

For fairness, all systems share the same base model (Llama-3.1-8B), retriever, corpus and number of training questions. Test-time comparisons are matched on total LLM calls, so our backtracking controller gets the same call budget as RASPberry's rollouts.

Beating GRAT means a larger 2Wiki gain than 60.6→66.8 from the same 11,000-trajectory budget, with our filter substituted. Beating RASPberry means matching 68.89 F1 at clearly fewer LLM calls, or exceeding it at equal calls. Beating FrugalRAG means comparable accuracy at comparable search counts without using optimal hop counts in training.

Three ablations isolate the key ingredient:

  • Unweighted majority vote over the same labeling functions, which tests the label model.
  • An independent-hops label model with no transitions or linking rules, which tests the sequential structure.
  • The full model with the final-answer function removed, which tests how much the method depends on outcome supervision.

Why not just…?

Why not just use final-answer correctness as the step label? This is the default, and the Liu et al. numbers above bound how noisy it is: good retrieval followed by a wrong answer, and lucky answers after missed evidence, both produce wrong step labels. The first experiment measures this directly. Outcome labels and our posteriors are scored against gold supporting facts at the hop level. If outcome labels are nearly as accurate, the label model adds little and we would report that.

Why not just ask a strong LLM to judge each hop? This is the real threat. A 70B judge may be accurate enough that aggregation is unnecessary. The judge is included as a labeling function and as a standalone baseline, compared at matched inference cost. We expect aggregation to win because judges share failure modes with the agent, such as rewarding on-topic but non-bridging passages, the same "well-grounded but wrong" pattern documented in Beyond Confidence. But this is an empirical question. If the 70B judge alone matches the label model's hop-level accuracy, the contribution narrows to cost: combining cheap checks instead of running a 70B model on every hop.

Why not just vote over the heuristics? Data programming's central result is that correlated sources sharing the same bias fool unweighted voting. Our library is correlated by construction: the lexical and grounding checks overlap heavily. The majority-vote ablation tests this directly, measuring calibration and hop-level accuracy.

Why not just train on gold supporting facts? Where they exist, as in HotpotQA, they are the upper bound, and we report a verifier trained on them as an oracle. The point is that they do not exist in open-web or specialist domains. We therefore test transfer to BrowseComp-Plus, whose human relevance labels let us score hop labels even though we never train on them.

Why not just search with more rollouts or a tree? Tree search does help; RASPberry reports a scaling slope above 2.0. But Liu et al. found that extending sequential search without stopping discipline mostly buys wasted tails. Our controller is complementary. The compute-matched comparison with RASPberry decides whether a good verifier inside a cheap beam search beats heavier search guided by a single consistency check.

Decisive Experiments

The first test is label quality. On held-out HotpotQA, 2WikiMultihopQA and MuSiQue trajectories, we derive hop-level ground truth from gold supporting facts: a hop is on-track if it retrieves a not-yet-seen gold paragraph. We then compare the area under the ROC curve and the calibration error of outcome labels, the 8B and 70B judges, majority vote, the independent-hops model, and the full hop model.

The central prediction is that the full model beats outcome labels mainly on two kinds of trajectories: those that failed despite gold retrieval, and those that succeeded without it. Those are exactly the cases where outcome labels are wrong by construction. If the gain does not concentrate there, the mechanism is not what we claim.

The second test is downstream. We repeat GRAT's self-training setup (Llama3-8B, 11,000 trajectories, 2Wiki) with our filter in place of final-answer filtering. We then run the verifier-guided backtracking and stopping controller on HotpotQA, reporting F1, exact match, gold-evidence recall and searches per question against RASPberry, FrugalRAG and IRCoT under matched calls.

The third test is transfer. We apply the HotpotQA-fit labeling functions and label model, refit only on unlabeled trajectories, to BrowseComp-Plus. We score hop labels against its relevance labels and report whether the controller shortens incorrect trajectories' wasted tails without lowering accuracy.

The proposal fails cleanly if either of two things happens: the full model does not beat both outcome labels and the best single judge on hop-level accuracy on at least two of the three training benchmarks, or better hop labels do not translate into downstream gains at matched compute.