Checking Each Reasoning Step Before It Becomes a Search Query

When a language model answers a multi-hop question such as "what country manufactured the roller coaster Lost Gravity?", it has to reason one hop at a time: first find the manufacturer, then find where that manufacturer is based. The strongest simple recipe interleaves the two activities. The model writes one sentence of reasoning, uses that sentence as the search query for the next round of documents, and repeats. This recipe has a structural weakness. If the sentence names the wrong manufacturer, the system searches for the wrong thing, and every later step is built on evidence about an entity that was never relevant. We propose to place a small, separately trained bidirectional text encoder at that point in the loop. A bidirectional encoder is a BERT-style model that reads a whole passage at once rather than left to right. Its job is to judge whether the candidate reasoning sentence is actually supported by the documents just retrieved. Only steps it accepts are allowed to become queries.

The two-sentence version is this. Interleaved retrieval lets one hallucinated intermediate entity steer all later searches, and self-checking by the same generator tends to rationalize its own errors. A cheap evidence-reading encoder, trained on step labels that one multi-hop dataset provides for free, can gate which reasoning steps are allowed to drive retrieval, and should cut this error propagation at a fraction of the cost of a second large model.

Core Claim

The claim is narrow and testable. On multi-hop question answering, the main avoidable failure of interleaved retrieval is query pollution: a wrong intermediate entity is written into a reasoning step and then used to search. A step verifier that reads the step together with its retrieved evidence, and runs before the step is used as a query, will reduce this failure. Concretely, the verifier is a DeBERTa-style cross-encoder, meaning it reads question, step, and passages jointly. It should beat equal-compute alternatives on final answer quality, and the gain should come specifically from evidence grounding and from the position of the check inside the loop.

This sits between three pieces of prior work, each in a different role. Interleaving Retrieval with Chain-of-Thought Reasoning for Knowledge-Intensive Multi-Step Questions (IRCoT) supplies the loop we modify. It alternates single reasoning sentences with retrieval, using each sentence as the next query. It reports retrieval recall gains of 11–21 points and answer F1 gains of up to 15 points over one-step retrieval. It has no check on whether a step is correct before that step is used to search.

Making Language Models Better Reasoners with Step-Aware Verifier (DIVERSE) supplies the verifier architecture. It fine-tunes DeBERTa-v3-large to score individual reasoning steps and uses those scores to weight votes over finished solutions, raising GSM8K accuracy from 74.4% to 83.2%. Its verifier sees only the reasoning text, with no external evidence, and it acts after generation rather than steering it.

Graph-Augmented Reasoning: Evolving Step-by-Step Knowledge Graph Retrieval for LLM Reasoning (KG-RAR) is the closest in spirit. It retrieves knowledge step by step and checks each step before continuing, but its checker is a frozen generative LLM, and it targets math with a procedural knowledge graph. GNNVerifier: Graph-based Verifier for LLM Task Planning constrains our design. It reports that verifiers built from generative LLMs are swayed by the plausible narration they are checking, and that a separately trained, non-generative verifier beat LLM refinement baselines on tool plans. That finding motivates using a different model family for the check, but it was obtained on tool plans, not open-domain text. Whether it transfers is something we test, not assume.

Research Program

The system keeps the IRCoT loop and changes one thing. At each step, the generator proposes $k$ candidate next sentences instead of one, and retrieval runs for each candidate. The verifier reads the question, the accepted steps so far, the candidate sentence, and that candidate's retrieved paragraphs, and outputs a probability that the candidate's factual claim is supported. The highest-scoring candidate above a threshold is accepted and becomes the query. If no candidate passes, the system falls back to retrieval conditioned on the question plus the last accepted step, then re-samples. The verifier also tags, token by token, which spans of a rejected step are unsupported, following the sequence-labeling setup that Enhancing Cross-Lingual Emotion Detection with Data Augmentation and Token-Label Mapping used to locate trigger words. These tags let the generator rewrite only the bad entity instead of the whole sentence, in the spirit of GNNVerifier's local edits.

The training signal is the part that makes this cheap. ♫ MuSiQue: Multihop Questions via Single-hop Question Composition builds every question by composing single-hop questions, so each hop has a gold intermediate answer. We run the generator under IRCoT on MuSiQue training questions and record every step. A step is labeled correct if the bridge entity it asserts matches the gold answer for that hop, and the entity span supplies token labels. This yields step-level supervision without human annotation, which DIVERSE lacked for open-domain questions. We then train once on MuSiQue and evaluate without retraining on 2WikiMultihopQA, HotpotQA, and IIRC. Those datasets do not provide clean per-hop labels, so this tests transfer rather than memorization of one dataset's style.

The analysis tracks three quantities beyond accuracy. The first is the hallucinated-bridge rate, the fraction of steps asserting a wrong intermediate entity. The second is the polluted-query rate, the fraction of retrieval calls issued from such steps. The third is how far an early error travels: the conditional probability of a wrong final answer given a wrong step at hop $j$. If the claim is right, verification should mostly reduce the second and third quantities, not only the first.

Baselines

The naive reference point is IRCoT exactly as published, with one sentence per step and no check, run with the same generator, retriever, and corpus as our system. As a lower anchor we also run one-step retrieval followed by chain-of-thought. The file gives only IRCoT's relative gains, so there is no reported result found on Lacuna for IRCoT's absolute F1 on MuSiQue, HotpotQA, 2WikiMultihopQA, or IIRC with any specific generator. We will reproduce these numbers ourselves and treat them as the bar. For calibration, MuSiQue reports human performance of 78.0 answer F1, which bounds how much headroom exists.

The strongest compute-matched competitor is self-consistency over IRCoT. We run $k$ independent IRCoT chains, where $k$ matches our number of candidates per step, and take a majority vote on the final answer. This spends the same number of generator samples but uses them only at the end. Beating it means a higher answer F1 at matched generator tokens, with a lower polluted-query rate.

The second strong competitor is a DIVERSE-style post-hoc verifier. We train the same DeBERTa model on the same MuSiQue step labels, but show it only the reasoning text, with no retrieved passages. We use it to weight votes over $k$ finished IRCoT chains. This competitor is the reason the proposal has two ablations. Feeding retrieved passages to this post-hoc verifier isolates the benefit of evidence. Running our gated system with a verifier that never sees passages isolates the benefit of checking inside the loop. The proposal survives only if the full system beats both ablations.

We also compare against a generator-as-judge gate. Here the same large model receives the identical inputs our encoder receives and is asked whether the step is supported, which is the KG-RAR "Critical Teacher" pattern moved to text. Finally, we test an untrained natural-language-inference cross-encoder used as the gate. All verifiers get the same passages and the same threshold-tuning budget on a held-out slice of MuSiQue development data, and we report wall-clock time and tokens for each.

Why not just…?

Why not just prompt the generator to check its own step against the retrieved passages? This is the most serious threat. With evidence in the prompt, the narration trap that GNNVerifier documented may weaken considerably. GNNVerifier's evidence comes from tool plans, where errors are type mismatches, so it does not settle the question for factual text. The generator-as-judge baseline above settles it directly. If the large-model judge matches our encoder's accuracy, the remaining argument is cost alone: one encoder pass versus one large-model call per candidate. We will report that cost difference honestly, and the claim would weaken to "same accuracy, much cheaper."

Why not just use an off-the-shelf entailment model and skip training? The task looks like entailment, so this could plausibly work. Our expectation is that the hard cases are bridge-entity errors where the passage is about a similarly named entity. MuSiQue's construction specifically filters out lexical shortcuts. General entailment models are not trained on that failure mode, while the MuSiQue step labels target it. The untrained-entailment gate measures how much the custom labels add. If the gap is small, we will report the simpler gate as the recommended method.

Why not just sample more full chains and vote? Voting over finished chains cannot repair a chain whose second search was already misdirected. It can only outvote it, and IRCoT chains sampled from the same prompt may share the same wrong bridge. The compute-matched self-consistency baseline and the polluted-query measurements test this. If voting closes the gap, the in-loop placement does not matter, and the post-hoc DIVERSE-with-evidence variant would be the better design.

Why not just use a larger generator? In IRCoT, a 3B Flan-T5-XL with interleaved retrieval beat 175B GPT-3 with one-step retrieval, and Can Large Language Models Always Solve Easy Problems if They Can Solve Harder Ones? found GPT-4 Turbo at only a 92.2% consistency score on easy versions of problems it solved. Scale therefore does not remove step errors. We still run the gate on two generator sizes to see whether its benefit shrinks as the generator grows. A shrinking benefit would be an informative result rather than a hidden one.

Proposed Experiments

The main experiment trains the verifier on MuSiQue-Ans step labels and evaluates all systems on MuSiQue-Ans, 2WikiMultihopQA, HotpotQA, and IIRC. It uses two open generators of different sizes, a fixed BM25-style retriever, and matched generator-token budgets. We report answer F1, supporting-paragraph recall, hallucinated-bridge rate, polluted-query rate, tokens, and latency.

The decisive check has three parts. First, the full gated system must beat compute-matched IRCoT self-consistency on answer F1 on at least the two datasets other than MuSiQue. Second, the evidence-free in-loop gate and the evidence-aware post-hoc verifier must each recover less of that gain than the full system. Third, the reduction in polluted queries must account for most of the F1 gain, which we test by stratifying questions by whether hop 1 was initially wrong.

A secondary check measures how the benefit scales with hop count, using MuSiQue's 2-, 3-, and 4-hop splits. If gating prevents error propagation, its advantage should grow with the number of hops. A flat advantage would suggest it is merely a better answer selector.

As an optional extension, we test on Complex WebQuestions. There, RGR-KBQA reports 72.1% F1 with single-pass logical-form generation (RGR-KBQA). The extension would show whether the same gate works when the evidence is knowledge-graph paths rendered as text rather than paragraphs.