Where Search Agents Go Off the Rails: Graph-Grounded Step-Level Verification

Where Search Agents Go Off the Rails: Graph-Grounded Step-Level Verification Hyeseo Jeon∗1 , Seonho Yoo∗2 , Jay-Yoon Lee†1 1

arXiv:2611.06662v1 [cs.AI] 4 Nov 2026

Seoul National University 2 Korea University {doupari,lee.jayyoon}@snu.ac.kr, leoyoo2004@korea.ac.kr

Abstract

Question: Who is the spouse of the actress who plays the Queen of Hearts in Alice in Wonderland?

Search-augmented reasoning systems suffer from unsupported intermediate claims and evidence-use failures, even when yielding correct final answers. Reliable step-level auditing requires evaluating three distinct axes: whether the evidence D covers the question Q (Q ↔ D), whether the reasoning T addresses the question (Q ↔ T ), and whether the reasoning is factually grounded in the evidence (D ↔ T ). However, Existing methods typically assess either the intrinsic validity of reasoning steps or their support against a given evidence context, without jointly diagnosing question requirements, temporally available evidence, and reasoning claims over an evolving search trajectory. Although these verifiers often achieve high precision when predicting an error, they exhibit substantially lower recall and thus leave many erroneous trajectories undetected. This is particularly problematic for step-level auditing, where a missed error can propagate to subsequent retrieval and reasoning. We introduce GraphRail, a generative-judge-free framework that decomposes each question into structured requirement triples and represents retrieved evidence and reasoning claims in the same claim form across the Q–D–T relations. GraphRail diagnoses missing or unused evidence, unresolved requirements, and grounded, unsupported, or conflicting claims without using a gold answer or asking another LLM to generate a verification judgment. Across three multihop QA benchmarks and three search-augmented reasoning frameworks, GraphRail achieves the strongest Recall, F1 , F6 scores in all evaluated offline settings, substantially outperforming the generative verifier baselines in recall. Beyond offline auditing, the same diagnoses can be converted into structural feedback that improves online reasoning in several settings. These results demonstrate that restricting LLMs to structured extraction and verifying with explicit cross-graph comparisons provides an effective and traceable alternative to open-ended generative judgment.

Step 1 I need to find the spouse of the actress who plays the Queen of Hearts in Alice in Wonderland.

Introduction Search-augmented reasoning systems repeatedly alternate between reasoning and retrieval before producing a final answer. Frameworks such as Search-R1 (2025) and ReSearch (2026) allow large language models (LLMs) to generate search queries, inspect retrieved documents, and continue ∗ †

These authors contributed equally. Corresponding author.

Retrieve 1: Document Supported Queen of Hearts (Alice's Adventures in Wonderland): The Queen of Hearts is fictional character from the book "Alice's Adventures in Wonderland" by the writer Lewis Carroll. Queen of Hearts played by Helena Bonham Carter … Step 2: Grounded Reasoning I found out that the actress who plays the Queen of Hearts in Alice in Wonderland is Helena Bonham Carter. Now I need to find her spouse.

Retrieve 2: Document Unsupported (Helena Bonham Carter): Helena is descended on her father's side from John Bonham Carter, Member of Parliament. Helena's paternal great- grandfather was H. H. Asquith, 1st Earl of Oxford and Asquith and Prime Minister … Step 3: Ungrounded Reasoning I found out that the spouse of the actress who plays the Queen of Hearts in Alice in Wonderland is Tim Burton. Now I can provide answer. Predicted answer

Tim Burton correct, yet unsupported

Figure 1: An unsupported intermediate claim can influence subsequent retrieval and reasoning. Final-answer evaluation alone does not reveal when the trajectory loses evidence.

reasoning over multiple turns. At any turn, the trajectory may be in one of following states: the required evidence may not yet have been retrieved, the evidence may be available but unused in reasoning, or the model may have asserted an unsupported claim. These states call for different interventions—additional retrieval, reconsideration of the available evidence, or revision of the unsupported claim—yet current systems rarely distinguish among them. Evaluation of these states is obscured by final-answer metrics such as Exact Match and F1. Such metrics indicate whether an answer matches a reference, but not whether the evolving reasoning remains relevant to the question and supported by the retrieved context. Furthermore, a correct final answer may still be reached through an ungrounded shortcut such as Figure 1. Since an early unsupported claim can influence subsequent searches and conclusions, step-level verification is therefore important for auditing whether a trajectory remains aligned with the question requirements and grounded in the evidence available at each step. Thus, reliable step-level verification requires jointly considering three components: the question, the retrieved docu-

Question: Who is the spouse of the actress who plays the Queen of Hearts in Alice in Wonderland? Reasoning Model (T1)

Reasoning Model (T2)

I need to find the spouse of the actress who plays the Queen of Hearts in Alice in Wonderland. I’ll search for it.

Reasoning Model (T3)

I found out that the actress is Helena Bonham Carter. Now I need to find her spouse.

Doc (D1)

I found out that the spouse of the actress who plays the Queen of Hearts is Helena Bonham Carter is Tim Burton.

Doc (D2)

G{i}X : i-th triple in GX

Graph Extractor (Q, Tt , D≤ t → G{i}{Q, D, GQ extracted once at the start

GD extracted each turn and accumulates )

Question Graph (requirements)

GD ≤ t ← D1 ∪ D2∪ … ∪ Dt

Question Graph (requirements) G{1}Q : (Queen of Hearts, played by, ENT1) Queen of Hearts

Played by

ENT 1 (actress)

Q

Played by

G{1}T3

G{2}Q : (ENT1, spouse, ENT2[answer]) ENT 1 spouse ENT 2 (answer) (actress)

G{1}Q

Queen of Hearts

Helena

Q

G{2}Q

ENT 1 spouse ENT 2 (actress) (answer)

plays Queen of Hearts

Queen of Hearts

G{1}Q

Played by

G{1}Q :

Q Q D

G{n}D ≤ 2

plays

Queen of Hearts

Per-requirement Diagnosis GROUNDED

T Value Consistency

(Do the recovered values agree?)

Helena

plays Queen of Hearts

G{n}D ≤ 2 Helena

Spouse evidence not yet retrieved

T D T

Entity from Document

G{1}T3

G{2}Q

ENT 1 spouse ENT 2 (actress) (answer)

Helena

Entity from Reasoning

D

D Support

(Is the requirement supported by evidence?)

G{2}T3

Tim Helena spouse Burton

Both requirements addressed

ENT1, ENT2 are unknown entity slots and are excluded from all alignment scoring (Answer-agnostic)

GT extracted each turn Reasoning graph of current turn only

T}

T Coverage

(Does the current claim address the requirement?)

Entity from Question

G{2}Q :

G{2}T3

Tim Helena spouse Burton

plays

Queen of Hearts

Actress value agrees; spouse value not compared

Q Q D

T D T

UNSUPPORTED

Figure 2: Overview of GraphRail. Question requirements, retrieved evidence, and reasoning claims are compared through the three complementary Q–D–T graph relations, enabling answer-agnostic diagnosis of evidence support, reasoning coverage, and value consistency without relying on an LLM-as-a-judge.

ments, and the model’s reasoning. We represent these components as Q, D, and T respectively, and verify three relations: Q ↔ D, Q ↔ T , and T ↔ D. The Q ↔ D relation checks whether the retrieved documents contain the evidence required by the question. The Q ↔ T relation checks whether the reasoning addresses that requirement. The T ↔ D relation checks whether the claims made in the reasoning are supported by the retrieved evidence. To the best of our knowledge, existing methods verify only part of this structure by focusing on step-level reasoning, evidence grounding, or collapsing the three components into a single generative judgment. To address these limitations, we introduce GraphRail, a requirement-centered and temporally grounded auditing graph framework for step-level verification. GraphRail converts the question, retrieved documents, and reasoning statements into structured triple graphs. The question graph encodes the information required by the query, leaving answer entities as unknown entities; the document graph extracts facts in the retrieved evidence; and the reasoning graph extracts claims by the model. GraphRail then applies an explicit coarse-to-fine alignment procedure across the three Q–D–T relations. For each question requirement, GraphRail combines the three pairwise signals into an actionable diagnosis: evidence may be Missing or Unused, an unresolved requirement may remain Open, and a concrete claim may be Grounded, Unsupported, or in

Conflict with retrieved evidence. This alignment procedure is answer-independent: unknown answer slots are excluded from alignment, and no reference answer is used to select or verify a candidate. The same diagnosis supports both offline and online use. Offline auditing localizes where completed trajectories lose evidentiary support, while online verification provides structural feedback before the agent’s next reasoning step. Most importantly, GraphRail does not use LLM as a judge. The role of the LLM in GraphRail is restricted to constrained graph extraction. It is not asked to decide whether another model is correct or to generate an open-ended verification judgment. This design confines model uncertainty to a bounded information-extraction stage and makes the subsequent diagnosis traceable to explicit cross-graph comparisons. As a result, GraphRail provides verification diagnosis without introducing a second generative reasoning loop or relying on the verifier’s parametric knowledge. Our main contributions are as follows: • We formulate verification of evolving search trajectories as a requirement-centered diagnosis over question requirements, temporally available evidence, and current reasoning claims, separating missing or unused evidence from grounded, unsupported, and conflicting claims. • We propose GraphRail, a gold-answer-free verification framework that confines the LLM for structured graph

extraction and performs diagnosis through explicit crossgraph alignment. It can verify existing search-augmented reasoning models without modifying their parameters or architecture. • We present a failure-mode analysis across three multi-hop question-answering benchmarks and evaluate GraphRail as both an offline trajectory auditor and an online source of targeted structural feedback.

Related Works Process and Evidence Verification. Process verification evaluates intermediate reasoning rather than only final outputs. Foundational process reward models, developed and evaluated largely on mathematical reasoning, assign correctness scores to individual solution steps for verification or training (Lightman et al. 2024; Wang et al. 2024). Processreward-guided search uses such signals to select promising reasoning trajectories (Zhang et al. 2024), while graphbased verifiers model dependencies among steps or alternative reasoning paths (Cao 2024; Fang et al. 2026). SocraticPRMBench (2025) further evaluates whether process verifiers detect errors across systematic reasoning patterns. Complementary work examines whether a final prediction actually depends on the stated reasoning chain (Paul et al. 2024). These approaches primarily evaluate the internal correctness, structure, or causal use of reasoning, rather than whether a search agent’s verbal claims are supported by the evidence available when they are produced. Evidence-grounding methods instead connect generated content to external sources. Prior work evaluates citation support at the answer level (Gao et al. 2023), introduces selfreflection over retrieved evidence at the generation-segment level (Asai et al. 2024), or penalizes unsupported reasoning steps against a provided evidence set (Gui et al. 2026). Graphbased approaches also verify complex claims through multihop evidence (Jeon and Lee 2025) or interleave knowledgegraph retrieval with stepwise verification and plan revision (Zhao et al. 2026). While these works establish increasingly fine-grained grounding, they generally verify a step, segment, or claim against a given evidence context. GraphRail instead audits an evolving search trajectory by jointly comparing question requirements, temporally available retrieved evidence, and current reasoning claims. Its Q–D–T diagnosis distinguishes missing or unused evidence from open, grounded, unsupported, and conflicting reasoning rather than reducing verification to a single correctness or support judgment. Search-Process Control and External Feedback. Prior studies show that intrinsic self-correction can be unreliable or even degrade reasoning performance (Valmeekam, Marquez, and Kambhampati 2023; Stechly, Marquez, and Kambhampati 2023; Huang et al. 2024). External-feedback methods therefore use verbal reflection, iterative refinement, tool-assisted critique, or process rewards to revise model outputs and reasoning paths (Shinn et al. 2023; Madaan et al. 2023; Gou et al. 2024; Zhang et al. 2024). Searchspecific methods further learn when to stop retrieval (Park, Cho, and Lee 2025), supervise and refine intermediate

Hotpot 2Wiki Musique No Error

45.2

17.4

6.2

Error Cases Incorrect Reasoning Given gold document Given irrelevant document Given no evidence Search Query Failure Hop Decomposition Failure Decoding Failure Others

6.8 14.8 13.0 3.0 5.0 3.0 9.2

7.0 38.4 14.8 12.6 1.8 2.4 5.6

9.4 33.8 21.6 10.6 10.0 1.8 6.6

Accuracy (EM) Average Model Steps

56.2 2.57

38.8 3.53

11.2 3.58

Table 1: Reasoning analysis for all samples. Most step-level errors arise from document hallucinations and become more frequent as average model steps increase. Hotpot 2Wiki Musique No Error

80.4

44.9

56.3

3.6 29.9 21.6 0.0 0.0 0.0

0.0 9.1 31.0 0.0 3.6 0.0

Error Cases Incorrect Reasoning Given gold document Given irrelevant document Given no evidence Search Query Failure Hop Decomposition Failure Decoding Failure

2.5 4.3 11.3 0.4 0.7 0.4

Table 2: Step-level reasoning analysis among samples with correct final answers. EM does not imply grounded reasoning

search queries (Wen, Dong, and Dou 2026), or provide hopaware benchmarks for diagnosing retrieval–reasoning failures (You, Yu, and Zhang 2026). These approaches primarily target correction, policy control, or benchmark-specific analysis. GraphRail instead converts explicit Q–D–T diagnoses into predefined feedback templates, enabling online intervention without retraining the underlying agent or asking another LLM to generate an open-ended critique.

Failure Mode Analysis We analyze step-level reasoning failures across HotpotQA (2018), 2WikiMultihopQA (2020), and MuSiQue (2022) using Search-R1 (2025) with a BM25 retriever. With human evaluation of 500 samples per dataset guided by LLMgenerated pseudo-labels, we group trajectories into six highlevel categories. No Error denotes valid, evidence-grounded reasoning. Incorrect Reasoning is subdivided by the evidence source: given gold document covers insufficient reasoning while containing gold document; given retrieved document captures misattribution from the retrieved document; and given no evidence covers unsupported answers from fabricated claims (hallucination). Search Query Failure denotes

HotpotQA F1

F6

P

R

F1

F6

P

R

F1

F6

0.5B 4B 7B Self-RAG 7B IBM-Granite 8B GPT-4.1-mini –

56.0 90.1 58.1 96.0 57.7 95.3 66.5 60.9 73.9 63.1 82.8 56.2

69.1 72.4 71.9 63.6 68.1 67.0

88.6 94.3 93.7 61.0 63.4 56.7

86.3 90.1 87.4 90.8 87.1 90.1 87.4 78.9 92.3 86.7 97.0 62.2

88.2 89.1 88.6 82.9 89.4 75.8

90.0 90.7 90.0 79.1 86.8 62.8

94.4 97.2 94.3 98.5 94.6 96.8 95.6 87 97.1 79.7 98.0 61.2

95.8 96.4 95.7 91.1 87.5 75.3

97.1 98.4 96.7 87.2 80.1 61.8

0.5B 4B 7B Self-RAG 7B IBM-Granite 8B GPT-4.1-mini –

48.4 85.4 48.9 87.1 49.4 88.0 53.2 74.7 61.9 57.9 80.4 31.8

61.8 62.7 63.3 61.7 59.8 45.6

83.7 85.3 86.2 73.9 58.0 32.3

80.8 87.4 80.5 86.8 82.1 88.7 78.0 84.7 88.1 77.7 92.0 46.2

84.0 83.6 85.3 81.2 82.6 61.5

87.2 86.6 88.5 84.5 77.9 46.8

87.1 93.3 87.6 95.6 87.8 94.7 89 89.4 89.7 76.5 95.6 44.9

90.1 91.4 91.1 89.2 82.6 61.1

93.1 95.4 94.5 89.4 76.8 45.6

0.5B 4B 7B Self-RAG 7B IBM-Granite 8B GPT-4.1-mini –

63.6 87.7 65.0 93.4 65.6 92.8 62.8 47.8 65.6 46.2 85.2 38.1

73.7 76.6 76.8 54.3 54.2 52.6

86.8 92.3 91.8 48.1 46.6 38.7

81.1 85.6 81.9 89.1 81.6 86.6 77.2 65.1 80.8 63.0 91.3 45.1

83.3 85.3 84.0 70.6 70.8 60.3

85.5 88.9 86.5 65.4 63.4 45.7

96.4 94.8 96.4 94.6 96.5 96.7 96.3 69.6 97.7 60.5 99.6 47.0

95.6 95.5 96.6 80.8 74.7 63.8

94.8 94.6 96.7 70.1 61.1 47.7

Ours

Ours ReSearch

Ours ReAct

MuSiQue

R

P

Search-R1

2WikiMultihopQA

Table 3: Offline GraphRail verification performance across search-augmented reasoning frameworks. P, R, F1 , and F6 denote precision, recall, Fβ (β = 1, 6) where higher beta considers Recall with higher weight. respectively; GraphRail uses different model sizes of graph extractors: Qwen2.5-0.5B-Instruct, Qwen3-4B-Instruct-2507, and Qwen2.5-7B-Instruct, denoted as 0.5B, 4B, and 7B. We compare against generative evaluators conditioned on the evidence available before reasoning step t (Q, D<t , Tt ). repeated failed queries. Hop Decomposition Failure includes wrong multihop question decomposition errors. Decoding Failure captures degenerate outputs. Others covers trajectories that are close to correct but fail during answer extraction. Tables 1 and 2 show that process-level errors arise from multiple sources. As reasoning requires more steps, errorfree trajectories become rarer, while incorrect reasoning and query failures become more frequent. Even correct final answers can contain flawed intermediate reasoning, indicating that final-answer evaluation alone is insufficient. This motivates verifying each reasoning step with respect to three relations: question, retrieved evidence, and model’s reasoning. The question–document relation checks evidence coverage, the question–reasoning relation checks whether the reasoning follows the intended requirements, and the reasoning–document relation checks whether the reasoning is grounded in evidence. Since each relation diagnoses different failures, reliable step-level verification must consider three pairwise relations.

Method We first introduce the graph representation used to encode the question, evidence, and reasoning. We then describe the three components of the verification framework: (1) cross-graph alignment, (2) joint requirement diagnosis, and (3) auxiliary claim grounding. Finally, we explain how this framework is applied to offline and online verification.

GraphRail Graph Representation. GraphRail represents the question, retrieved evidence, and current reasoning step as triple graphs GQ , GD , and GTt . We use GD<t and GD≤t to denote the evidence available before and after retrieval at turn t. Each graph consists of triples τ = (h, r, o), where h, r, and o denote the head entity, relation, and object entity respectively, separated by [SEP] token in sentence. Unknown answer entities in the question are represented by placeholders ENTk , so alignment is performed only over the known fields of each question requirement. The question graph is constructed once, the document graph accumulates evidence across turns, and the reasoning graph is constructed at each step. Verification Framework. GraphRail performs requirement centered verification across the question, document, and reasoning graphs. For each question requirement qi ∈ GQ , the question–document (Q–D) relation checks whether relevant evidence has been retrieved, while the question– reasoning (Q–T ) relation checks whether the current reasoning addresses the requirement. When the aligned document and reasoning triples provide concrete values for the same unknown slot, the reasoning–document (D–T ) relation checks whether those values agree. GraphRail combines these signals into one of six diagnostic states: Conflict, Unsupported, Grounded, Unused, Open, and Missing, as summarized in Table 4. Cross-Graph Alignment. GraphRail uses a shared alignment operator for the Q–D and Q–T relations to robustly

State

Q–D Q–T

Conflict

Yes

Unsupported

No

Grounded

Yes

Unused

Yes

Open

No

Missing

No

D–T

Additional Condition

Interpretation

Yes Disagree Both aligned triples provide different concrete The reasoning contradicts the availvalues for the same unknown slot. able evidence. Yes – The reasoning provides a concrete value, but The reasoning introduces an unsupno supporting document value is available. ported claim. Yes Agree / – No value conflict is detected; fully specified re- The requirement is covered by both evquirements do not require unknown-slot com- idence and reasoning. parison. No – Supporting evidence is available, but the rea- Relevant evidence has been retrieved soning does not address the requirement. but remains unused. Yes – The reasoning addresses the requirement with- The requirement remains unresolved. out asserting a concrete unsupported value. No – Neither supporting evidence nor aligned rea- The requirement is not covered by the soning is available. current trajectory.

Table 4: Top-down requirement-level diagnosis based on Q–D support, Q–T coverage, and D–T value consistency. Q–D and Q–T indicate whether a question requirement is aligned with a supporting document triple and a reasoning claim, respectively, while D–T compares the concrete values recovered for the same unknown slot. “–” indicates that D–T comparison is not applicable. Because some conditions overlap, the states are evaluated from top to bottom, and the first applicable state is selected.

match evidence and reasoning. Given a question requirement qi ∈ GQ and a candidate graph GC ∈ {GD , GTt }, the operator identifies the candidate triple that best matches the known fields of qi . Unknown fields in qi are excluded from alignment. GraphRail first linearizes each triple and retrieves the topK candidates with the highest semantic similarity to the question requirement. The shortlisted candidates are then compared at the field level. Let qi = (hi , ri , oi ) and c = (hc , rc , oc ). To consider reversed subject–object orientations introduced during graph extraction, each known entity field is compared with both entity positions in c, while relations are compared directly: sh (qi , c) = max{sim(hi , hc ), sim(hi , oc )} so (qi , c) = max{sim(oi , oc ), sim(oi , hc )} sr (qi , c) = sim(ri , rc )

(1)

Entity fields are compared across both positions to handle reversed head–object order, while relation fields are compared directly to preserve predicate consistency. Let F(qi , c) denote the fields that are known in qi and available for comparison with c. GraphRail scores a candidate by its weakest evaluated field. Among the top-K candidates, it selects the highest-scoring candidate: A(qi , c) =

min

f ∈F (qi ,c)

sf (qi , c)

c∗i = arg max A(qi , c)

(2)

c∈CK (qi ;GC )

The alignment is accepted when A(qi , c∗i ) ≥ θ. Using the minimum field score requires every known field to match sufficiently well, preventing one strong field from masking a mismatch in another. When an accepted candidate fills an uninstantiated placeholder, the recovered value is propagated to other requirements sharing that placeholder and treated as

known in their alignment. Thus, only uninstantiated placeholders are excluded, and a value recovered by the current match does not affect its alignment score. This separates requirement matching from answer-value comparison. Joint Requirement Diagnosis GraphRail combines Q–D support, Q–T coverage, and D–T value consistency to diagnose each question requirement. For a requirement with an unknown slot, usable document support must provide a concrete value for that slot. The six states in Table 4 are evaluated in top-down priority order. As some conditions overlap, the first applicable state is selected. A D–T value mismatch is labeled Conflict, while a concrete value recovered through Q–T without corresponding Q–D support is labeled Unsupported. If neither condition applies, the remaining states distinguish whether the requirement is covered by the document graph, the reasoning graph, both, or neither. The D–T comparison applies only when the requirement contains an unknown answer slot and both aligned triples provide concrete values for that slot. Fully specified requirements are diagnosed using Q–D support and Q–T coverage. Auxiliary Claim Grounding In addition to requirementcentered diagnosis, GraphRail applies an auxiliary grounding check to additional concrete claims introduced during reasoning. Each eligible claim is compared with the available document graph using the same semantic retrieval and fieldlevel matching components as cross-graph alignment. For conflict detection, structural compatibility and value agreement are evaluated separately: candidate document triples are first matched using the shared entity and relation fields, after which their concrete values are compared. The claim is checked against the evidence available at the corresponding auditing stage: GD<t offline and GD≤t online. Eligible claims must be fully instantiated and explicitly asserted; triples containing unknown fields or merely restating the

question are excluded. A claim is labeled Unsupported when no compatible document evidence supports the asserted value, and Conflict when structurally compatible evidence provides a different concrete value. This auxiliary check extends grounding verification to additional intermediate assertions. Offline GraphRail Verification GraphRail audits a completed trajectory using only the evidence available at the time each reasoning step was generated. At turn t, claims in GTt are grounded against GD<t , which contains only evidence retrieved before that reasoning step. Newly retrieved document triples are added for subsequent turns, but later evidence cannot retrospectively support an earlier claim. The offline audit consists of two stages. First, a per-turn grounding audit detects Unsupported and Conflict claims as the trajectory unfolds. Second, after the final turn, a requirement-level coverage audit identifies Unused requirements, for which supporting evidence was retrieved but not used in reasoning, and Missing requirements, for which the required evidence was never retrieved. A trajectory is marked as erroneous if any turn contains an Unsupported or Conflict claim, or if the final coverage audit contains a Missing requirement. Unused is retained as a diagnostic state but is not treated as a case-level error because the relevant evidence is already available. Online GraphRail Verification In the online setting, GraphRail evaluates each reasoning step against the evidence accumulated through the current turn, GD≤t , and returns the resulting diagnosis before the agent takes its next action. Unlike offline auditing, this setting uses newly retrieved evidence immediately to guide subsequent reasoning. Each diagnostic state is mapped to a predefined feedback template: Missing and Open indicate that additional evidence is needed, Unused indicates that retrieved evidence should be incorporated into the reasoning, and Unsupported and Conflict indicate that a concrete claim should be reconsidered. Grounded requires no corrective feedback. The selected template is appended to the input containing the next retrieved document, providing verification steering guidance without directly generating or overriding the model’s subsequent search and reasoning actions.

Experiments Experimental Setup Graph Extractor. We fine-tune separate question, document, and reasoning extractors as LoRA adapters over a shared base model. We evaluate Qwen2.5-0.5B-Instruct, Qwen3-4B-Instruct-2507, and Qwen2.5-7B-Instruct. The document extractor outputs factual triples from retrieved passages, the question extractor produces requirement triples with ENTk placeholders, and the reasoning extractor extracts claims asserted in each reasoning step. To construct supervision, we first collect Search-R1 trajectories and prompt Qwen2.5-7B-Instruct separately for the question, document, and reasoning extraction tasks. The resulting task-specific graphs are used as supervision for training the corresponding extractors. For each extraction task, we

Hotpot

2Wiki

MuSiQue

EM F1 EM F1 EM F1 Vanilla – 56.6 63.0 38.8 42.3 11.2 17.4 0.5B 57.4 63.5 46.2 49.3 13.4 20.0 Search-R1 Ours 4B 57.4 63.9 45.8 48.8 14.6 20.5 7B 57.8 63.8 46.4 49.4 13.6 19.7 Vanilla – 56.4 64.0 49.4 52.0 19.4 28.0 0.5B 58.0 64.8 53.6 55.7 19.6 28.0 ReSearch Ours 4B 59.6 66.8 53.6 55.8 17.6 26.2 7B 55.6 63.9 53.0 55.4 19.4 27.7 ReAct

Vanilla – 42.0 47.9 42.8 45.2 7.6 13.0 0.5B 40.2 46.1 41.4 44.1 9.2 14.2 Ours 4B 39.0 46.0 39.8 43.1 10.0 14.3 7B 40.4 46.5 41.0 43.6 11.0 14.8

Table 5: Online GraphRail results across search-augmented reasoning frameworks. Without directly overriding in the model’s reasoning process, structural feedback can improve EM/F1.

build 4,500 instances from HotpotQA (1,000), 2WikiMultihopQA (1,500), and MuSiQue (2,000). We then fine-tune the extractors for three epochs with LoRA (r = 16, α = 32, dropout = 0.1), using a learning rate of 10−4 on a single NVIDIA RTX PRO 6000 GPU. Verification. GraphRail embeds triples with BGE-largeen-v1.5, retains the top K = 3 candidates, and accepts alignments with a field-level score of at least θ = 0.60. Evaluation Data. We audit Search-R1, ReSearch, and ReAct on HotpotQA, 2WikiMultihopQA, and MuSiQue using 500 vanilla trajectories per framework–dataset pair. All systems use BM25 retrieval over the Wikipedia-2018 dump. Since these benchmarks do not provide trajectory-level error labels, we manually annotate the evaluated trajectories to construct human reference labels for offline verification. Search-R1 trajectories are additionally categorized by failure type for the failure-mode analysis.

Results Offline GraphRail Verification Table 3 evaluates trajectory level error detection against human reference labels. Recall is particularly important for offline verification because a missed error allows an unsupported, conflicting, or incomplete trajectory to remain undetected. Following (Song and Lee 2026), we note that multi-hop QA is particularly sensitive to missing required evidence and that recall-weighted Fβ better reflects answerability than precision alone. Because missed trajectory errors can remain undetected and affect subsequent reasoning, we report F6 to place greater emphasis on recall while still penalizing false positives. GraphRail achieves the highest F6 across all framework– dataset pairs, driven by consistently strong recall. The improvement is especially pronounced on MuSiQue, where GraphRail maintains recall above 93 across all evaluated

Method

Decode Hotpot 2Wiki MuSiQue Tokens

Ours (0.5B) Ours (4B) Ours (7B) Self-RAG (7B) IBM-Granite (8B) GPT-4.1-mini

1.18s 3.11s 4.13s 0.26s 0.17s 2.28s

1.28s 3.43s 4.59s 0.35s 0.20s 2.83s

1.19s 3.17s 4.18s 0.33s 0.21s 3.14s

1,503 1,531 1,532 163 3 53

Table 6: Average sample offline latency and decode tokens. Method

Precision

Recall

F6 -Score

Temperature = 1.0 Ours (0.5B) 79.1 (± 0.3) 93.4 (± 0.8) 92.8 (± 0.8) Ours (4B) 79.1 (± 0.2) 94.0 (± 0.4) 93.4 (± 0.4) Ours (7B) 79.8 (± 0.3) 93.9 (± 0.4) 93.3 (± 0.4) Self-RAG (7B) 83.9 (± 1.4) 71.3 (± 8.1) 71.6 (± 7.9) IBM-Granite (8B) 88.4 (± 1.1) 75.7 (± 3.3) 75.4 (± 3.6) Temperature = 0.5 Ours (0.5B) 79.1 (± 0.4) 92.7 (± 0.5) 92.2 (± 0.5) Ours (4B) 79.4 (± 0.1) 94.4 (± 0.2) 93.8 (± 0.2) Ours (7B) 80.0 (± 0.2) 93.7 (± 0.4) 93.1 (± 0.4) Self-RAG (7B) 83.7 (± 0.7) 73.4 (± 3.9) 73.7 (± 3.8) IBM-Granite (8B) 87.6 (± 1.9) 76.2 (± 1.6) 76.4 (± 1.5) Table 7: Uncertainty robustness of offline GraphRail verification in Search-R1, averaged over three datasets. Each entry reports mean ± standard deviation over five seeds. By using LLMs only as graph extractors, GraphRail consistently exhibits the lowest variance, indicating robustness.

frameworks and extractor sizes. Notably, even the 0.5B extractor outperforms the larger generative verifier baselines in F6 across all settings. This result supports GraphRail’s design of restricting the learned model to structured graph extraction and performing verification through explicit alignment and diagnosis rules. Increasing the extractor size to 4B generally provides the strongest overall results, while the 7B extractor yields no consistent additional improvement. Notably, even the 0.5B extractor exceeds all generative verifier baselines in F6 across the nine evaluation settings, showing that strong verification does not require a large generative judge. Online GraphRail Feedback Table 5 shows that GraphRail feedback consistently improves Search-R1 and benefits ReSearch on HotpotQA and 2WikiMultihopQA. For Search-R1 on 2WikiMultihopQA, EM increases from 38.8 to 46.4 and F1 from 42.3 to 49.4. ReAct, in contrast, improves only on MuSiQue and declines on HotpotQA and 2WikiMultihopQA. This difference can be explained by how each framework exposes and updates its intermediate state. Search-R1 and ReSearch generate factual assertions and subsequent plans within a continuous <think> span followed by a free-form <search> query, allowing feedback to revise both within a single generation. ReAct instead sepa-

rates an undelimited Observation: from a constrained Action: search[...] slot, causing feedback to blend with retrieved evidence and requiring its translation into the action format. This interface overhead limits the benefit of feedback when there is less room for correction. Offline Latency Table 6 reports warmed-up end-to-end latency per trajectory. For all methods, latency is averaged per sample with a single active client per server. For GraphRail, question, document, and reasoning graph extraction calls are issued concurrently through the same vLLM server, and the reported latency includes the subsequent verification stage. The higher latency relative to the local verifier baselines mainly reflects the decoding workload. GraphRail generates approximately 1,500 structured output tokens per trajectory, whereas Self-RAG, IBM-Granite, and GPT-4.1-mini generate 163, 3, and 53 tokens, respectively. Thus, GraphRail constructs explicit question, document, and reasoning graphs rather than producing only a short verification output. Nevertheless, the 0.5B variant requires only about 1.2 seconds per sample and already outperforms all evaluated baselines in offline F6 , providing a performance–latency balance. Offline Uncertainty Robustness Table 7 evaluates the stability of offline verification under stochastic decoding at temperatures 0.5 and 1.0 over five random seeds. Across all extractor sizes, GraphRail exhibits consistently low variance in precision, recall, and F2 . In particular, its F2 standard deviation remains at or below 0.6, while the generative verifier baselines show larger fluctuations, especially in recall. GraphRail also maintains similar mean performance across the two temperatures. For example, the 4B extractor achieves an F2 of 89.8±0.3 at temperature 1.0 and 90.2±0.1 at temperature 0.5. This suggests that stochastic variation in the extracted triples has limited impact on the final trajectorylevel diagnosis. Since the LLM is used to produce structured graphs rather than an open-ended verification judgment, the subsequent deterministic alignment and diagnosis stages can yield stable decisions across decoding settings.

Conclusion We presented GraphRail, a graph-grounded framework that verifies search-augmented reasoning through explicit alignment among question requirements, retrieved evidence, and reasoning claims. By combining the Q–D, Q–T , and D–T relations, GraphRail distinguishes missing or unused evidence from grounded, unsupported, and conflicting reasoning without using a generative judge or gold answer. GraphRail achieves strong recall and F6 for offline trajectory auditing, remains stable under stochastic graph extraction, and provides useful online feedback for reasoning frameworks that expose explicit intermediate claims and plans. These findings suggest that confining the LLM to graph extraction and performing verification through deterministic cross-graph comparisons offers a traceable and effective alternative to open-ended generative verification.

References Asai, A.; Wu, Z.; Wang, Y.; Sil, A.; and Hajishirzi, H. 2024. Self-rag: Learning to retrieve, generate, and critique through self-reflection. In International conference on learning representations, volume 2024, 9112–9141. Cao, L. 2024. Graphreason: Enhancing reasoning capabilities of large language models through a graph-based verification approach. In Proceedings of the 2nd Workshop on Natural Language Reasoning and Structured Explanations (@ ACL 2024), 1–12. Chen, M.; Sun, L.; Li, T.; Sun, H.; Zhu, C.; Wang, H.; Pan, J.; Zhang, W.; Chen, H.; Yang, F.; et al. 2026. Learning to reason with search for llms via reinforcement learning. Advances in Neural Information Processing Systems, 38: 85287–85307. Fang, J.; Zhang, B.; Wang, C.; Wan, J.; and Xu, Z. 2026. Graph of verification: Structured verification of llm reasoning with directed acyclic graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 40, 30665– 30672. Gao, T.; Yen, H.; Yu, J.; and Chen, D. 2023. Enabling large language models to generate text with citations. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 6465–6488. Gou, Z.; Shao, Z.; Gong, Y.; Yang, Y.; Duan, N.; Chen, W.; et al. 2024. Critic: Large language models can self-correct with tool-interactive critiquing. In International Conference on Learning Representations, volume 2024, 57734–57811. Gui, R.; Li, Y.; Qu, X.; Liu, Z.; Cheng, Y.; and Cheng, Y. 2026. Faithrl: Learning to reason faithfully through step-level faithfulness maximization. ArXiv e-prints, arXiv–2602. Ho, X.; Nguyen, A.-K. D.; Sugawara, S.; and Aizawa, A. 2020. Constructing a multi-hop qa dataset for comprehensive evaluation of reasoning steps. In Proceedings of the 28th International Conference on Computational Linguistics, 6609–6625. Huang, J.; Chen, X.; Mishra, S.; Zheng, H. S.; Yu, A.; Song, X.; and Zhou, D. 2024. Large language models cannot selfcorrect reasoning yet. In International conference on learning representations, volume 2024, 32808–32824. Jeon, H.; and Lee, J.-Y. 2025. GraphCheck: Multipath FactChecking with Entity-Relationship Graphs. arXiv preprint arXiv:2502.20785. Jin, B.; Zeng, H.; Yue, Z.; Yoon, J.; Arik, S.; Wang, D.; Zamani, H.; and Han, J. 2025. Search-r1: Training llms to reason and leverage search engines with reinforcement learning. arXiv preprint arXiv:2503.09516. Li, X.; Yu, H.; Zhang, X.; Huang, Z.; He, S.; Liu, K.; Zhao, J.; Huang, F.; and Li, Y. 2025. Socratic-prmbench: Benchmarking process reward models with systematic reasoning patterns. arXiv preprint arXiv:2505.23474. Lightman, H.; Kosaraju, V.; Burda, Y.; Edwards, H.; Baker, B.; Lee, T.; Leike, J.; Schulman, J.; Sutskever, I.; and Cobbe, K. 2024. Let’s verify step by step. In International Conference on Learning Representations, volume 2024, 39578– 39601.

Madaan, A.; Tandon, N.; Gupta, P.; Hallinan, S.; Gao, L.; Wiegreffe, S.; Alon, U.; Dziri, N.; Prabhumoye, S.; Yang, Y.; et al. 2023. Self-refine: Iterative refinement with selffeedback. Advances in neural information processing systems, 36: 46534–46594. Park, J.; Cho, S.; and Lee, J.-Y. 2025. Stop-RAG: ValueBased Retrieval Control for Iterative RAG. arXiv preprint arXiv:2510.14337. Paul, D.; West, R.; Bosselut, A.; and Faltings, B. 2024. Making reasoning matter: Measuring and improving faithfulness of chain-of-thought reasoning. In Findings of the Association for Computational Linguistics: EMNLP 2024, 15012–15032. Shinn, N.; Cassano, F.; Gopinath, A.; Narasimhan, K.; and Yao, S. 2023. Reflexion: Language agents with verbal reinforcement learning. Advances in neural information processing systems, 36: 8634–8652. Song, M.; and Lee, J.-Y. 2026. Retrieving a Set, Not Independent Passages: Set-Level Compatibility Learning for Efficient Set Exploration. arXiv preprint arXiv:2607.05712. Stechly, K.; Marquez, M.; and Kambhampati, S. 2023. Gpt-4 doesn’t know it’s wrong: An analysis of iterative prompting for reasoning problems. arXiv preprint arXiv:2310.12397. Trivedi, H.; Balasubramanian, N.; Khot, T.; and Sabharwal, A. 2022. MuSiQue: Multihop Questions via Single-hop Question Composition. Transactions of the Association for Computational Linguistics, 10: 539–554. Valmeekam, K.; Marquez, M.; and Kambhampati, S. 2023. Can large language models really improve by self-critiquing their own plans? arXiv preprint arXiv:2310.08118. Wang, P.; Li, L.; Shao, Z.; Xu, R.; Dai, D.; Li, Y.; Chen, D.; Wu, Y.; and Sui, Z. 2024. Math-shepherd: Verify and reinforce llms step-by-step without human annotations. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 9426–9439. Wen, T.; Dong, G.; and Dou, Z. 2026. SmartSearch: Process Reward-Guided Query Refinement for Search Agents. arXiv preprint arXiv:2601.04888. Yang, Z.; Qi, P.; Zhang, S.; Bengio, Y.; Cohen, W.; Salakhutdinov, R.; and Manning, C. D. 2018. HotpotQA: A dataset for diverse, explainable multi-hop question answering. In Proceedings of the 2018 conference on empirical methods in natural language processing, 2369–2380. You, Q.; Yu, W.; and Zhang, W. 2026. AgenticRAGTracer: A Hop-Aware Benchmark for Diagnosing MultiStep Retrieval Reasoning in Agentic RAG. arXiv preprint arXiv:2602.19127. Zhang, D.; Zhoubian, S.; Hu, Z.; Yue, Y.; Dong, Y.; and Tang, J. 2024. Rest-mcts*: Llm self-training via process reward guided tree search. Advances in Neural Information Processing Systems, 37: 64735–64772. Zhao, W.; Wang, J.; Zhang, Y.; Li, S.; Deng, C.; Wang, J.; and Chen, L. 2026. VoG: Enhancing LLM Reasoning through Stepwise Verification on Knowledge Graphs. In The Fourteenth International Conference on Learning Representations.

Related documents

• DARE: Dialectical Agentic Reasoning for Structured Knowledge Fact Checking#1083306
• Automating Formal Verification with Agent-Guided Tree Search#241591
• ProofGap: Benchmarking Step-Level Formal Reasoning with Local Obligations Derived from Natural-Language Solutions#1077225
• GraphCert: Bootstrap Agentic Graph Reasoning with Certified Evidence Rubrics#1143399
• Harness Engineering in LLM Tool Use via Agent-Native Reusable Tool Primitives#822166