Search-augmented reasoning systems can reach correct answers while making errors in intermediate steps. Reliable auditing must check whether evidence D covers the question Q, reasoning T addresses Q, and T is grounded in D. We introduce GraphRail, which represents requirements, evidence, and reasoning as structured claims and compares them without a generative judge or gold answer. Across three multi-hop QA benchmarks and three reasoning frameworks, GraphRail improves error recall over generative verifiers while remaining stable under stochastic extraction. Its diagnoses can also guide online reasoning, providing a traceable way to detect and correct intermediate errors.
Figures & tables
Figure 1: An unsupported intermediate claim can influence subsequent retrieval and reasoning. Final-answer evaluation alone does not reveal when the trajectory loses evidence.
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.
Hotpot
2Wiki
Musique
No Error
45.2
17.4
6.2
Error Cases
Incorrect Reasoning
Given gold document
6.8
7.0
9.4
Given irrelevant document
14.8
38.4
33.8
Given no evidence
13.0
14.8
21.6
Table 1: Reasoning analysis for all samples. Most step-level errors arise from document hallucinations and become more frequent as average model steps increase.
HotpotQA
2WikiMultihopQA
MuSiQue
P
R
F1
F6
P
R
F1
F6
P
R
F1
F6
Search-R1
0.5B
56.0
90.1
69.1
88.6
86.3
90.1
88.2
90.0
94.4
97.2
95.8
97.1
Ours
4B
58.1
96.0
72.4
94.3
87.4
90.8
89.1
90.7
94.3
98.5
96.4
98.4
7B
57.7
95.3
71.9
93.7
87.1
90.1
88.6
90.0
94.6
96.8
95.7
96.7
Self-RAG
7B
66.5
60.9
63.6
61.0
87.4
78.9
82.9
79.1
95.6
87
91.1
87.2
IBM-Granite
8B
73.9
63.1
68.1
63.4
92.3
86.7
89.4
86.8
97.1
79.7
87.5
80.1
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 ).
State
Q – D
Q – T
D – T
Additional Condition
Interpretation
Conflict
Yes
Yes
Disagree
Both aligned triples provide different concrete values for the same unknown slot.
The reasoning contradicts the available evidence.
Unsupported
No
Yes
–
The reasoning provides a concrete value, but no supporting document value is available.
The reasoning introduces an unsupported claim.
Grounded
Yes
Yes
Agree / –
No value conflict is detected; fully specified requirements do not require unknown-slot comparison.
The requirement is covered by both evidence and reasoning.
Unused
Yes
No
–
Supporting evidence is available, but the reasoning does not address the requirement.
Relevant evidence has been retrieved but remains unused.
Open
No
Yes
–
The reasoning addresses the requirement without asserting a concrete unsupported value.
The requirement remains unresolved.
Missing
No
No
–
Neither supporting evidence nor aligned reasoning is available.
The requirement is not covered by the 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.
Hotpot
2Wiki
MuSiQue
EM
F1
EM
F1
EM
F1
Search-R1
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
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
ReSearch
Vanilla
–
56.4
64.0
49.4
52.0
19.4
28.0
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.
Method
Hotpot
2Wiki
MuSiQue
Decode Tokens
Ours (0.5B)
1.18s
1.28s
1.19s
1,503
Ours (4B)
3.11s
3.43s
3.17s
1,531
Ours (7B)
4.13s
4.59s
4.18s
1,532
Self-RAG (7B)
0.26s
0.35s
0.33s
163
IBM-Granite (8B)
0.17s
0.20s
0.21s
3
GPT-4.1-mini
2.28s
2.83s
3.14s
53
Table 6: Average sample offline latency and decode tokens.
Multi-hop QA benchmarks often reward Large Language Models (LLMs) for spurious correctness, where models reach correct answers through invalid intermediate reasoning. We propose SAFE, an LLM-as-verifier framework for evidence-grounded multi-hop QA. Rather than judging only the final answer after generation, SAFE verifies reasoning during generation by checking intermediate steps against the provided passages and previous reasoning trajectory. To make this process checkable, SAFE decomposes reasoning into atomic, evidence-grounded units represented with Knowledge Graph (KG) triples. At train-time, SAFE verifies benchmark supervision under KG-grounded constraints and constructs reliable verifier training data. At inference-time, an external verifier checks each generated step, identifies invalid reasoning, and provides correction feedback before errors propagate. Across three multi-hop QA benchmarks, SAFE improves accuracy by 8.8 pp on average. These results show that evidence-grounded multi-hop QA benefits from shifting LLM-based evaluation from post-hoc answer judgment to stepwise reasoning verification.
Reasoning structures (e.g., chains and graphs) are increasingly used for probabilistic inference, factuality verification, and uncertainty estimation, but their structural reliability is rarely evaluated directly. We test whether this reliability holds through a proposed two-stage diagnostic evaluation in open-ended multi-hop QA. Stage 1 tests different capabilities required to construct reasoning graphs, showing that graph reliability varies with topology, prompt design, and model family. Stage 2 uses uncertainty estimation as a downstream test case. Generated-edge experiments show that graph-based computation is sensitive to upstream graph errors, with performance dropping relative to the gold-graph setting. Gold-graph experiments further show that graph structure provides little benefit when used only as prompt context, but improves the separation of correct from incorrect answers by confidence score and enables node-level diagnostics.
LLM search agents are often evaluated on final-answer accuracy, overlooking the process. Analyzing a search strategy requires understanding how credible evidence is retrieved to address question constraints. This valuable information is buried in raw search trajectories that are long and difficult to parse. We introduce SearchAtlas, a framework that converts search trajectories into structured graphs whose edges represent how evidence is propagated across the reasoning trace, from the query that retrieves it to the final answer. Our automated parsing pipeline achieves a mean edge F1 of 86.0% against human-annotated graphs and remains consistent across repeated runs. We analyze five search agents on three benchmarks, revealing systematic differences in search scale and evidence aggregation. SearchAtlas exposes fragmented answer support, question constraints that do not reach the answer, and unverified parametric knowledge entering the response. These process failures are strongly associated with incorrect answers, even more so than an LLM judge given either the raw trajectory or the ordered query list, suggesting that the constructed graphs provide useful interpretability. Moreover, an audit of cases in which process-diagnostic scores disagree with final-answer correctness shows that they capture information not reducible to answer accuracy.