Judge-Free Backtracking Supervision for Small Multi-Hop Search Agents

A search agent answering a question like "where was the director of film X born?" must first find the director, then search for that person's birthplace. If the first search returns the wrong person, every later step builds on the error. The current fix is backtracking: the agent notices the bad step, returns to an earlier point in its search, and tries a different path. In today's systems, a large language model (LLM) usually decides when to backtrack. Either it acts as a judge that scores partial trajectories, or it acts as a privileged teacher whose verdicts are distilled into a small student model. We argue that this decision is where the student's performance cap actually comes from. A student can only learn to backtrack as well as its judge recognizes contamination. LLM judges are known to prefer fluent, authoritative-looking content over correct content, and they do not admit it.

This proposal measures that cap directly and then removes it. Multi-hop question-answering benchmarks are built from chained single-hop questions with gold intermediate answers. Final answers can also be checked by string match. Together, these let us label each "keep going" or "go back" decision without asking any LLM's opinion. We train small students on these verifiable rollback labels. We then test whether they beat students trained on judge-derived labels and whether they escape the judge's biases. We also check whether the benefit grows with the number of reasoning hops, as theory about search depth predicts.

Core Claim

Our claim is that a distilled search agent's backtracking quality is capped by the quality of the signal that labeled its backtrack decisions, not by the teacher's overall answer accuracy. When that signal comes from an LLM judge, the student inherits the judge's specific blind spots: wrong bridge entities that look coherent, and passages carrying authoritative or recent-looking metadata. Replacing judge labels with labels computed from gold decompositions and answer-checked rollouts should raise backtracking precision and recall above the judge's own, and should leave the student insensitive to injected surface cues. The advantage should be largest on deeper questions.

The motivating evidence comes from three papers. Local Coherence or Global Validity? Investigating RLVR Traces in Math Domains shows that a GPT-4o judge tagging step-level logic errors agrees with humans only 57.8% of the time. It also shows that reinforcement learning on final-answer rewards produces traces that look locally sound but are globally invalid. The Silent Judge: Unacknowledged Shortcut Bias in LLM-as-a-Judge shows that judges' verdicts shift when content is held fixed and only provenance or date labels change. For example, GPT-4o shows a +30% verdict shift on ELI5 from recency labels. These judges also cite the injected cue 0% of the time. Retrieved passages in a search agent routinely carry exactly this kind of metadata.

Neither paper studies search agents. The two closest systems put an LLM verdict at the backtracking decision without auditing it:

LoongReflect is the closest existing work. It differs from our proposal in where the backtrack signal comes from. In LoongReflect, an LLM teacher interprets the tree and says where things went wrong. Here, the location of the error is computed from gold intermediate answers and checked rollouts. We also measure how often the teacher's attribution is wrong and whether that error propagates into the student.

Research Program

Agent setup. The agent runs interleaved retrieval and reasoning in the style of Interleaving Retrieval with Chain-of-Thought Reasoning for Knowledge-Intensive Multi-Step Questions over a Wikipedia passage corpus. We add an explicit state tree. Each node records a sub-question, the retrieved passages, and a committed bridge answer. At each node the agent emits either continue or backtrack-to-ancestor. Returning to an ancestor discards the context added below it, which follows the context-isolation idea of the rollback in Smurfs: Multi-Agent System using Context-Efficient DFSDT for Tool Planning. Smurfs triggers rollback only on hard tool errors. It cannot handle our failure case, where retrieval succeeds but returns the wrong entity.

Two verifiable labels. We label backtrack decisions from two sources, neither of which involves an LLM verdict.

The first is a decomposition label. It applies where the agent's sub-questions align with the gold single-hop chain of ♫ MuSiQue: Multihop Questions via Single-hop Question Composition or with 2WikiMultiHopQA evidence triples. A state is contaminated from the earliest hop whose committed bridge answer fails an alias-aware match to the gold intermediate answer. That hop's parent becomes the backtrack target.

The second is a rollout label, which applies everywhere. From state $s$, we sample $k$ continuations and estimate $V(s)$, the fraction whose final answer exceeds an F1 threshold against gold. We label

$$ \text{backtrack}(s) = \mathbb{1}\left[\, V(\text{parent}(s)) - V(s) > \delta \,\right], $$

where $\delta$ is a margin set on held-out data to absorb noise from finite $k$. On aligned states, the decomposition label serves as a check on how noisy the rollout label is.

The audit. Before training anything, we compare LLM judge decisions against these labels on the same states. The judges are GRAT-style rollout scorers and a LoongReflect-style privileged teacher. We report the judges' backtracking precision and recall, which we call the judge's backtrack ceiling. We then run a cue-injection test modeled on the Silent Judge protocol. We prepend source and date metadata to distractor bridge passages, or paraphrase them into more fluent prose, holding facts fixed. We then measure how often the keep or backtrack verdict flips.

Distillation. Students at 1.5B, 3B, and 7–8B are trained on identical trajectories. The only difference is the source of the backtrack labels: judge, privileged teacher, decomposition, rollout, or decomposition plus rollout. All students then receive the same outcome-based Group Relative Policy Optimization (GRPO) stage, a reinforcement-learning method that rewards each sampled answer relative to the others in its group. Equalizing this stage matters because To Backtrack or Not to Backtrack: When Sequential Search Limits Model Reasoning shows that supervised backtracking traces lock models into the training search order unless reinforcement learning follows.

Capacity sweep. The sweep tests a prediction drawn from Capacity-Dependent Effects of Data Selection for Reasoning and from the 0.6B collapse reported in AgentArk: Distilling Multi-Agent Intelligence into a Single LLM Agent. The prediction is that the smallest students may not absorb tree manipulation at all. For those students we filter trajectories to the student's high-likelihood subset, which is the regime where small models are reported to learn rather than fall into rote imitation.

Baselines

Naive references. The do-nothing reference is the same student running linear interleaved retrieval with no backtrack action. We give it parallel sampling plus majority vote at a matched token and retrieval-call budget. This compute-matched comparison is essential: on shallow, wide search trees, To Backtrack or Not to Backtrack finds that parallel sampling beats backtracking at equal compute. Any gain we report must survive it.

GRAT. GRAT is the strongest published system that uses a judge to decide branch abandonment and then distills into an 8B model. It reports 75.2% accuracy on 2WikiMultiHopQA with Llama3-70B, and an improvement from 60.6% to 66.8% when Llama3-8B is fine-tuned on 11,000 of its trajectories. We rerun its pipeline with our backbone, retriever, and corpus at matched search budget, and also report its published 8B number for reference. Beating it means a same-size student exceeding the self-trained GRAT student at equal or lower inference compute.

LoongReflect. LoongReflect is the strongest competitor on the core question, because it already distills explicit backtracking for search agents. It reports an average gain of 12.6 F1 over AgenticRAG-R1 across seven QA benchmarks. We found no per-dataset absolute number on Lacuna for LoongReflect on MuSiQue or HotpotQA. We will therefore reimplement its two channels: answer-masked privileged-teacher distillation plus GRPO. We hold backbone, data, rollout count, and tuning budget equal, so that the only difference is where the backtrack signal comes from. If no official code is available, we will treat our reimplementation's numbers as the reference and validate it against the published average gain direction. Beating it means higher MuSiQue answer F1 and higher backtrack F1 against decomposition labels, with the gap concentrated on 3- and 4-hop questions.

Debiased judge. This baseline asks whether a better-engineered judge closes the gap. Following AgentEval: DAG-Structured Step-Level Evaluation for Agentic Workflows with Error Propagation Tracking, we use a GPT-4o judge that scores each step against only its parent context. It uses a failure taxonomy and has all passage metadata stripped. AgentEval reports a Cohen's κ of 0.84 with humans on production traces, though not on retrieval agents.

Ablations. Swapping only the label source while holding everything else fixed isolates the proposal's key ingredient. A further ablation removes the backtrack action but keeps the verifiable step labels as an auxiliary loss. This separates "better credit signal" from "explicit rollback."

Why not just…?

Why not just train on final-answer reward and skip step labels entirely? This is the most serious alternative. Outcome reward involves no judge, and LoongReflect's slow channel already uses it. The concern is that outcome reward does not tell the model which hop to undo, and Local Coherence or Global Validity? shows it producing fluent but invalid chains. Our design settles the question directly: every arm gets the same GRPO stage, and one arm gets GRPO alone. If GRPO alone matches our labels in both answer F1 and backtrack F1 at equal compute, the dense verifiable signal is unnecessary, and we will report that result.

Why not just debias the judge by stripping metadata and calibrating it? Stripping metadata removes provenance and recency cues. It does not stop a judge from accepting a coherent passage about the wrong person, which is the error measured at 57.8% judge accuracy in the math setting. In addition, AgentEval reports that its advantage drops sharply on looping, dynamic topologies, and backtracking trees are exactly that kind of topology. The debiased-judge baseline above measures how much of the gap engineering closes.

Why not just use GRAT's rollouts with exact-match scoring instead of an LLM evaluator? This is essentially our rollout label, and we treat it as part of the method rather than a competitor. The novel contributions lie elsewhere. First, distilling the rollout signal into a single-pass student's backtrack decision removes tree search at inference. Second, we audit the judge-induced ceiling and show bias inheritance. Third, we validate rollout labels against gold decompositions. If decomposition labels add nothing over rollout labels, the method becomes simpler and more general, which is a welcome outcome.

Proposed Experiments

We evaluate on MuSiQue-Ans, split by 2-, 3-, and 4-hop questions. We also use 2WikiMultiHopQA, HotpotQA in the full-wiki setting, and Bamboogle as a held-out probe with no training labels. We report:

  • answer exact match and F1;
  • backtrack precision and recall against decomposition labels;
  • verdict shift rate under cue injection;
  • tokens and retrieval calls per question.

As a human reference, MuSiQue-Ans answer F1 is 78.0 according to the MuSiQue paper.

There are three decisive checks.

First, a ceiling check. Students trained on judge labels should have backtrack F1 bounded near their judge's audited F1. Students trained on verifiable labels should exceed it. If the two groups do not differ, the central claim is false.

Second, a bias-inheritance check. We inject provenance and recency cues into distractor bridge passages at test time. Judge-label students should show verdict shifts in the same direction as their judge. Verifiable-label students should show shifts near zero. This would be the first evidence that judge shortcut bias passes through distillation into an agent's control decisions.

Third, a depth check. Against compute-matched parallel sampling, our backtracking gain should grow from 2-hop to 4-hop MuSiQue questions. A flat or negative curve would mean backtracking itself, and not only who labels it, is the wrong tool for this regime.

The capacity sweep is read alongside all three checks. We expect the 7–8B student to show the largest gain from verifiable labels. We expect 1.5B students to need likelihood-filtered trajectories in order to benefit at all.