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

Hyeseo Jeon; Seonho Yoo; Jay-Yoon Lee

cs.AINov 4, 2026

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

Authors: Hyeseo Jeon, Seonho Yoo, Jay-Yoon Lee

Organizations: Seoul National University · Korea University

Abstract

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.

Error Cases
	Hotpot	2Wiki	Musique
No Error	45.2	17.4	6.2
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	$F_{1}$	$F_{6}$	P	R	$F_{1}$	$F_{6}$	P	R	$F_{1}$	$F_{6}$
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,

F_{1}

, and

F_{6}

denote precision, recall,

F_{\beta}

(

\beta=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},T_{t}

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.

Reasoning Verification

Reasoning verification checks whether intermediate steps and final answers are logically valid and supported by evidence.

See all 59 papers

SAFE: An LLM-as-Verifier Framework for Evidence-Grounded Multi-Hop Reasoning
Apr 2, 2026Daeyong Kwon, Soyoung Yoon, Seung-won HwangMulti-Hop QA LLM Answer Verification
Seoul National University, South Korea
Diagnostic Analysis for Large Language Model Reasoning
Oct 19, 2026Xinyu Liu, Dongqi Fu, Jun WuLanguage Model Reasoning Evaluation LLM Reasoning with Graphs
Michigan State University · Meta AI
SearchAtlas: Analyzing Agentic Search Strategies via Evidential Query Graphs
Sep 9, 2026Jiacheng Sang, Mengyuan Li, Sanxing Chen +3Agentic Search LLM Interpretability
Duke University · University of Pennsylvania

Apr 2, 2026J/K move · Enter open · S save

SAFE: An LLM-as-Verifier Framework for Evidence-Grounded Multi-Hop Reasoning

Daeyong Kwon, Soyoung Yoon, Seung-won Hwang

Seoul National University, South Korea

Multi-Hop QA LLM Answer Verification LLM Grounding

Open paper AskPDF arXiv

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.

Abstract

Reasoning Verification

Explore similar work

SAFE: An LLM-as-Verifier Framework for Evidence-Grounded Multi-Hop Reasoning

Diagnostic Analysis for Large Language Model Reasoning

SearchAtlas: Analyzing Agentic Search Strategies via Evidential Query Graphs