Overlap-Stratified Stopping for Multi-Hop Search Agents

Search agents answer multi-hop questions by retrieving a passage, reasoning, and retrieving again. Deciding when to stop matters for speed: every extra round of search and reasoning adds seconds. A recent approach trains a small checker model to stop the loop once retrieved text "matches" what the question needs.

The danger is that the checker learns a shortcut. It says "match" whenever a passage shares many words with the question, even if the passage does not contain the fact that links the two hops. When it errs this way, the agent stops early and answers confidently from the wrong evidence. Standard confidence thresholds are tuned on average error, and average error hides this failure. On shortcut-rich benchmarks, overlapping passages usually do contain the evidence, so the error never shows up in the calibration data.

We propose to certify the stopping checker separately within bins of lexical overlap. The overlap measure asks how many words a passage shares with the query. For the high-overlap bins, where the shortcut would fire, we build calibration and training negatives automatically. These are counterfactual passages that keep the overlap but remove the bridging fact. The same stratified error constraint then serves two purposes. It decides which of the checker's own predictions on unlabeled agent traces are trusted as training labels (pseudo-labels). It also decides when the agent is allowed to stop at inference time.

Core Claim

A stopping checker that meets an error budget on average will violate it badly on high-overlap, non-evidential passages. Enforcing the budget per overlap bin, using overlap-preserving counterfactuals as the calibration signal, should recover most of the latency savings of early stopping. It should do so without the premature, shortcut-driven stops that inflate results on HotpotQA and fail on MuSiQue.

Formally, let $g(x)$ be the checker's confidence that retrieved evidence $x$ completes the current hop. Let $b(x)$ be its lexical-overlap bin, and let $y(x)$ be whether $x$ truly contains the bridging fact. We choose a per-bin acceptance threshold $t_b$ for each bin $b$. Each threshold is set as low as possible (maximizing coverage) subject to

$$ \Pr\big[y(x)=0 \mid g(x)\ge t_b,\ b(x)=b\big]\le \epsilon \quad \text{for every bin } b, $$

where $\epsilon$ is a user-chosen false-stop budget. A single global threshold satisfies only the average of these constraints, and that average can be dominated by low-overlap bins where the checker is reliable.

Grounding in Prior Work

Two papers establish the problem this work addresses. Understanding Dataset Design Choices for Multi-hop Reasoning shows that sentence-factored models, which never see two sentences together, reach 57.2% on HotpotQA by matching question words to single sentences. MuSiQue builds questions from composed single-hop questions to remove such shortcuts. Single-hop models lose 30 F1 on it relative to HotpotQA. Together they suggest that any component trained or calibrated on HotpotQA-style data inherits an overlap prior.

HALT supplies the setting we build on. It uses a 3B checker that labels retrieved sentences against claims written up front for each hop, as MATCH, PARTIAL or NULL. With gold claims, it cuts search loops by 45% on HotpotQA, 37% on 2WikiMultiHopQA and only 20% on MuSiQue, with exact match within one point. It also reports a 35% wall-clock reduction on HotpotQA. We read the drop to 20% on MuSiQue as a hint that part of the HotpotQA saving comes from overlap-driven stops. HALT does not test this, and its checker has no protection against lexically similar non-evidence. We keep HALT's retrieval-side verification and change how the checker is trained and thresholded.

Two papers supply methods we reuse. PabLO learns a confidence function that maximizes pseudo-label coverage under an explicit error budget. On CIFAR-100 with 400 labels it lifts accuracy from FixMatch's 30.38% to 67.44%. It has only been applied to images, it applies a single global constraint, and it needs a clean labeled validation set. InstanT learns per-example thresholds from estimated noise rates, again only in vision. We borrow PabLO's constrained formulation. We replace its global constraint with the per-bin one above. We also pay its validation cost with generated counterfactuals rather than human labels.

The counterfactual idea comes from Robustifying Multi-hop QA through Pseudo-Evidentiality Training. That paper derives evidential and non-evidential sentence sets by ablating sentences. It raises challenge-set F1 from 30.07 to 44.57, but it needs costly erase-and-insert sweeps limited to five sentences, and it uses no formal threshold. We generate negatives from structure instead. MuSiQue's decompositions and 2WikiMultiHopQA's Wikidata triples identify the bridge fact directly. We then replace or delete only that fact in the gold passage, keeping the surrounding words. This costs one edit per passage.

Two results constrain the design. SOCRATES finds that models doing multi-hop reasoning silently, without written reasoning or retrieval, reach only about 6% on temporal bridges versus 70% when they write out their reasoning. This rules out removing the retrieval loop to save latency, so we save latency by stopping rather than by compressing reasoning. Estimating the Causal Effects of Natural Logic Features in Transformer-Based NLI Models documents shortcut-driven errors in transformer NLI models. Liang et al. show that models become confidently wrong under shift. Together these suggest that raising a global threshold will not remove shortcut errors, because those errors sit at high confidence.

Research Program

The system is a Self-Ask-style search agent with a stopping checker, following HALT's setup. The same 3B-class checker is initialized from a small set of gold hop labels.

The first step is building overlap-preserving negatives. For each gold hop passage in MuSiQue and 2WikiMultiHopQA training data, we produce counterfactual variants that keep lexical overlap with the query within a small tolerance but remove or swap the bridging entity or relation. We filter variants with an entailment check so that we do not create accidental positives. These pairs form the calibration pool for the high-overlap bins. We deliberately do not generate them from HotpotQA, so that HotpotQA remains a held-out test of transfer.

The second step is self-training under the stratified constraint. We run the agent on unlabeled questions, and the checker labels its own traces. A predicted MATCH enters the training set only if it clears its bin's threshold $t_b$, re-estimated each round on the calibration pool. This is where confirmation bias would otherwise enter: confident overlap-driven MATCH labels would be fed back into training and strengthen the shortcut.

The third step applies the same thresholds at inference. At each hop, the agent stops only when the checker clears the threshold for that passage's overlap bin. Because the checker judges evidence as it arrives, rather than only against fixed claims, we also test an extension. When a hop returns PARTIAL, the checker rewrites the remaining hop claims from the retrieved text, addressing HALT's static-claim limitation.

The fourth step is analysis. We measure false-stop rates per overlap bin. We also measure how much of each baseline's latency saving comes from stops that the counterfactual test shows to be non-evidential.

Baselines

The naive reference is a fixed-budget iterative agent that always runs the maximum number of hops. The closest published instance is IRCoT, which alternates written reasoning steps with retrieval and improves retrieval recall by 11–21 points and QA F1 by up to 15. It sets the accuracy ceiling and the latency floor. Every method will use the same retriever, corpus and reader model, with the same maximum number of hops.

The strongest competitor is HALT's checker with its own confidence threshold. Its reported figures are a 45% loop reduction on HotpotQA with exact match within one point, and a 35% time reduction, both from HALT. We will retrain it on the same gold data and give it the same threshold-tuning budget on a standard held-out split. We will report it both with gold claims and with generated claims, because our method uses generated claims. Beating it means the following. At matched average search loops, exact match on MuSiQue and on the challenge set from Robustifying Multi-hop QA through Pseudo-Evidentiality Training must be higher. At the same time, loop reduction on HotpotQA must stay within a few points of HALT's.

The generator-confidence competitor is DRAGIN. It decides when to retrieve from token entropy and attention, and reports F1 of 0.3931 on 2WikiMultiHopQA with LLaMA2-13B, versus 0.3076 for FLARE. We run it with the same reader and set its entropy threshold to the same loop budget.

The latency competitor is L-RAG. It retrieves the second hop from intermediate hidden states in about 2.8 seconds per query, where IterRetGen exceeds 20 seconds on 2WikiMultiHopQA. It reports 0.352 accuracy on MuSiQue. It anchors the fast end of the latency-accuracy curve.

We also run ablations that isolate each ingredient. The first applies the global PabLO-style constraint with the same counterfactual calibration data. It tests whether stratifying by overlap matters. The second applies the stratified constraint but calibrates on ordinary held-out gold rather than counterfactuals. It tests whether the counterfactual data matters. The third uses simple per-bin thresholds on the raw checker score instead of a learned confidence function. It tests whether learning $g$ matters at all.

Why not just…?

Why not just raise HALT's threshold? A stricter global threshold removes low-confidence errors first. The shortcut errors we target are high-confidence, which is the pattern shown by Liang et al.. A stricter threshold should therefore give up latency savings before it removes shortcut stops. We will plot the high-overlap false-stop rate against loop reduction as the global threshold moves. If that curve reaches our operating point, the proposal fails.

Why not just penalize lexical overlap directly, rejecting MATCH when overlap is high? True bridge sentences often share many words with the query, so a flat penalty would block correct stops. It also cannot tell an evidential high-overlap passage from a non-evidential one. Only a signal that tracks evidence, such as the counterfactual pairs, can make that distinction. The pseudo-evidentiality paper's result that ordinary training collapses to 30.07 F1 on its challenge set suggests that overlap-aware heuristics without evidential contrast are insufficient. We include an overlap-penalty baseline tuned to the same loop budget.

Why not just use per-bin thresholds on the raw score and skip the learned confidence function? This is a real threat, and it may be enough. If the per-bin-threshold ablation matches the full method, we will report the contribution as stratified certification with counterfactual calibration. The learned confidence function would then be an unnecessary extra. The ablation where calibration uses ordinary gold is the one that must fail for the core claim to hold.

Why not compress reasoning instead of stopping earlier? Methods like CoLaR cut MATH reasoning length by 82.8%, but they reason silently, and SOCRATES shows that silent multi-hop reasoning collapses on temporal bridges. Compression is complementary and could be layered on later. It does not solve the grounding problem.

Decisive Checks

We evaluate on HotpotQA distractor and full-wiki, 2WikiMultiHopQA, MuSiQue-Ans and MuSiQue-Full, and the pseudo-evidentiality challenge set. Metrics are exact match, F1, average search loops, wall-clock time per query, and false-stop rate per overlap bin on held-out counterfactual pairs.

Three results would decide the question. First, the baseline checker must show a false-stop rate in the top overlap bin well above its average rate. Without that, there is no problem to solve. Second, our method must bring the top-bin rate down to near $\epsilon$ while keeping most of HALT's loop reduction. Third, on MuSiQue, where shortcuts are removed, our method must match or exceed full-budget exact match with fewer loops, while the global-threshold ablation loses accuracy at the same loop count.

For MuSiQue under our exact protocol, no end-to-end exact-match number with early stopping was found on Lacuna. The fixed-budget agent will serve as that reference.