When Connectivity Misleads: Guiding Agentic Search with Contrastive Evidence Paths

Junchen Li; Liang Xu; Rongzheng Wang; Qizhi Chen; Junhao Wen; Shuang Liang

cs.IROct 26, 2026

When Connectivity Misleads: Guiding Agentic Search with Contrastive Evidence Paths

Authors: Junchen Li, Liang Xu, Rongzheng Wang, Qizhi Chen, Junhao Wen, Shuang Liang

Organizations: University of Electronic Science and Technology of China Chengdu, China

Abstract

Search agents can use cross-document graphs to discover sources through multi-hop connections and choose subsequent actions based on candidate rankings and relationships within a limited observation window. However, documents may rank highly because their numerous connections make them easier to reach, without necessarily providing more valuable evidence. Graph diffusion methods such as Personalized PageRank (PPR) aggregate propagation contributions from multiple sources, allowing highly connected distractor nodes to crowd the observation window. Flat node scores also obscure cross-document evidence trails, limiting continued exploration. We propose Contrastive Evidence Paths (CEP), which scores candidates by their strongest individual paths on a query-conditioned document graph and calibrates these scores against the same graph's background visitation distribution to mitigate structural bias. CEP ranks candidates by the calibrated scores and retains the corresponding source paths. Building on CEP, we develop Structured Corpus Interaction (SCI), which organizes candidates and their connecting paths into a structured Map, enabling agents to verify source documents and pursue missing information through expansion from anchor documents. Experiments on BrowseComp-Plus and TREC-COVID show that SCI achieves state-of-the-art answer accuracy and nDCG@10 with the lowest generation cost. Compared with the strongest baselines by task performance, maximum reductions in tool calls and total generation costs exceed 50% and 40%, respectively. Further analysis confirms that SCI with CEP suppresses ranking inflation induced by structural connections and improves gold recall and exploration efficiency.

Figures & tables

Figure 1. Illustrative comparison of graph diffusion retrieval and contrastive evidence paths retrieval. Conceptual comparison on the same document graph. Graph diffusion prioritizes a highly connected distractor and exposes a flat node ranking. CEP combines strongest path support with a background visitation distribution to calibrate candidate priorities and retains source paths in the agent observation window.

Figure 2. Overview of SCI. (a) Shared entities connect source documents into a document graph with static transition probabilities. (b) CEP adjusts transition probabilities using the original question, computes strongest path support $M_{i}(v)$ from query-relevant starting points, and calibrates candidate scores using the background visitation distribution $b_{Q}(v)$ . It collects documents and builds a map. (c) The agent uses the map and previews to choose actions: verify collected source text with read and bash , expand from an anchor to address an information gap with graphexpand(a,q) , or initiate global retrieval with graphsearch . Shared entities connect documents into a graph. The original question adjusts transition probabilities, while the original question and current query jointly select starting points. CEP calibrates strongest path support using background visits and collects documents into a workspace with a navigation map. The agent explores through reading, command-line checks, global search, and anchor expansion.

Conventional retrieval agents
	GPT-6-Luna				DeepSeek-V4.1-Flash				Qwen3.8-Flash
Method	Acc. $\uparrow$	Turns $\downarrow$	Tools $\downarrow$	Total Cost $\downarrow$	Acc. $\uparrow$	Turns $\downarrow$	Tools $\downarrow$	Total Cost $\downarrow$	Acc. $\uparrow$	Turns $\downarrow$	Tools $\downarrow$	Total Cost $\downarrow$
Retrieval-Agent	80.00	16.43	35.97	$33.15	87.95	20.47	36.57	$26.22	82.41	24.54	52.64	$133.87
NeMo Agent	72.05	8.09	27.64	$23.06	80.12	10.47	30.69	$25.72	76.87	15.77	31.86	$56.86
Corpus interaction agents
DCI	78.07	19.94	29.85	$52.83	83.86	23.43	34.79	$40.77	84.58	33.51	37.27	$61.46

Table 1. Main results on BrowseComp-Plus with a 100K-document corpus. Turns and Tools are averaged per question. Cost is the total generation cost in USD for all 830 queries. Bold indicates the best values.

Method	nDCG@10 $\uparrow$	Turns $\downarrow$	Tools $\downarrow$	Total Cost $\downarrow$
DCI	68.85	10.18	56.00	$1.11
DR-DCI	67.17	6.20	23.20	$0.16
RISE-BM25	58.42	9.14	10.72	$0.19
RARG++	75.97	11.98	20.66	$0.29
AtlasNav	57.79	7.00	25.06	$0.26
SCI	81.77	5.24	13.72	$0.15

Table 2. Main results on TREC-COVID with GPT-6-Luna. Turns and Tools are averaged per query. Cost is the total generation cost for 50 queries. Best values are bold.

Figure 3. Corpus scaling results. (a) Accuracy of SCI and RARG++. (b) Mean tool time of graphsearch and graphexpand . Accuracy of SCI and RARG++ and mean execution times of graphsearch and graphexpand as the corpus grows from 100K to 1M documents. SCI maintains higher accuracy across all tested sizes. At 1M documents, graphsearch and graphexpand take 0.877 and 0.264 seconds on average, respectively.

Type	Method	100	500	1,000	preview
		Retrieval budget per query			Top10
Conventional retrieval	BM25	34.74	50.80	58.31	19.85
	Dense	45.14	67.76	77.16	20.83
	Hybrid	41.92	62.02	71.28	20.33
Graph retrieval	PPR	45.83	65.05	74.12	21.88
	PCST	40.71	60.35	68.42	–

Table 3. Retrieval algorithm ablation on BrowseComp-Plus. Gold recall (%) is measured after initial retrieval. PCST returns a selected subtree rather than a ranked list, so Top10 preview recall is not reported.

Figure 4. CEP component ablation. (a) Initial workspace gold recall across retrieval budgets. (b) Top10 preview gold recall. Workspace recall curves and preview recall bars for full CEP, without path support, without background calibration, and without both.

Configuration	Acc. $\uparrow$	Turns $\downarrow$	Tools $\downarrow$	graphsearch	graphexpand	read	bash
SCI	93	14.15	18.61	5.15	0.88	6.68	5.90
w/o map	83	12.52	19.35	5.47	0.70	7.57	5.61
w/o expansion	83	13.08	21.40	4.46	–	7.93	9.01
w/o both	80	12.66	21.95	4.74	–	8.39	8.82

Table 4. Structured map ablation on BrowseComp-Plus with GPT-6-Luna. Turns and tool calls are averaged per question. Bold indicates the best values.

Figure 5. Evolution of evidence coverage. Coverage after the initial search versus cumulative coverage over the full agent trajectory. First-search and cumulative gold recall for workspace documents, map sources, and preview sources.

Expansion outcome	Documents	Read	Read or Bash
Newly acquired	67	32	37
Newly shown in map	372	180	212

Table 5. Gold documents newly added to the workspace or first shown in the map from the existing workspace by local expansion. The last two columns count documents later accessed via read and via read or bash , respectively.

	Mean degree		Highly connected (%)
Top- $k$	PPR	CEP	PPR	CEP
10	182.29	66.56	56.76	33.55
100	220.63	57.29	56.13	29.36
1,000	171.00	61.30	50.26	30.68

Table 6. Mean degree and proportion of highly connected nodes among documents retrieved by PPR and CEP.

Figure 6. Gold document rankings under PPR and CEP. (a) Rank pairs within the top 1,000 under both methods, with medians computed over all 2,407 rank pairs. (b) Proportions of rank wins and ties across all rank pairs.

Method	Mean distractor rank Before $\rightarrow$ After	Top10 entry (%) Before $\rightarrow$ After
PPR	$50.67\rightarrow 24.96$	$0.00\rightarrow 15.22$
CEP w/o calibration	$42.21\rightarrow 42.21$	$0.84\rightarrow 0.84$
Full CEP	$45.79\rightarrow 75.87$	$0.00\rightarrow 0.00$

Table 7. Mean rank and Top10 entry rate of distractor documents before and after controlled edge addition. Higher mean ranks and lower Top10 entry rates indicate stronger suppression of distractors.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Parameter	Setting
Entity document frequency limit $\tau$	4
Rank offset $k$	60
Retrieval starting points per query $R$	1000
Background restart probability $\alpha$	0.5
Background estimation iterations $T_{b}$	24
Hop discount $\lambda$	0.5

Appendix

Table 8. SCI retrieval parameters.

Model	Input	Cache hit	Cache write	Output
GPT-6-Luna ( $\leq$ 272K)	0.10	0.01	0.125	0.50
GPT-6-Luna ( $>$ 272K)	0.20	0.02	0.25	0.75
DeepSeek-V4.1-Flash	0.15	0.003	–	0.60
Qwen3.8-Flash	0.15	0.016	0.20	0.47

Appendix

Table 9. Generation pricing in USD per million tokens. GPT-6-Luna tiers refer to input tokens per request. DeepSeek-V4.1-Flash uses off-peak rates.

Specially trained deep research agents
Method	Acc. $\uparrow$	Turns $\downarrow$	Tools $\downarrow$
OpenResearcher-30B-A3B	46.00	67.64	66.44
QUEST-35B-RL	48.00	56.14	53.79
Corpus interaction agents (Qwen3.8-27B)
DCI	77.00	27.53	74.94
DR-DCI	71.00	27.60	70.26

Appendix

Table 10. Supplementary agent comparison on 100 BrowseComp-Plus queries.

Native graph RAG pipelines
Method	Corpus size	Acc. $\uparrow$	Turns $\downarrow$	Tools $\downarrow$	Total Cost $\downarrow$
HippoRAG2	1,545	42.00	—	—	—
PathRAG	1,545	28.00	—	—	—
LinearRAG	1,545	28.00	—	—	—
Graph retrieval tools within Pi Agent
HippoRAG2 + Pi Agent	1,545	89.00	12.49	26.74	$2.43

Appendix

Table 11. Reference comparison of graph-based RAG methods and SCI. Cost is the total generation cost in USD for 100 queries. For a fair cost comparison among agents, we only report costs for agent methods.

Figure 7. Two local expansion cases on BrowseComp-Plus, with full questions, abbreviated tool calls, and returned map excerpts. Quotes reproduce source text. R denotes the interaction turn. Bracketed numbers are corpus document IDs. Two recorded local expansion trajectories. Case A retrieves a previously uncollected paper through Yuval Peres, then reads and cites it to verify a coauthorship clue supporting the answer Russell David Lyons. Case B first shows an already collected Hirata Family archive in the map, then reads and cites it to corroborate the answer Jun, whose name was already present in the anchor.

Method	GPT-6- Luna	DeepSeek- V4.1-Flash	Qwen3.8- Flash
Retrieval-Agent	67.21 s	98.30 s	561.95 s
NeMo Agent	49.44 s	113.57 s	534.30 s
DCI	133.45 s	146.19 s	493.76 s
DR-DCI	62.04 s	164.89 s	652.18 s
RISE	59.57 s	111.83 s	419.95 s
RARG++	172.86 s	232.50 s	960.02 s

Appendix

Table 12. Mean end-to-end execution time (s) per query on BrowseComp-Plus. Bold indicates the lowest values.

Web Search Agents

Web search agents use language models to find, verify, and synthesize information from the web for multi-step tasks.

See all 41 papers

PathAnchor: Path-Structured Evidence for Scientific Agents
Sep 30, 2026Qiuhui Chen, Jiafan Lu, Shuaimin Tang +5Evidence-Grounded Reasoning Scientific QA
School of Information Science and Engineering, East China University of Science and Technology · College of Intelligent Robotics and Advanced Manufacturing, Fudan University · Tencent
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
DocNavRAG: Document-Structured Graph RAG with Stateful Evidence Construction for Complex Document Question Answering
Aug 3, 2026Dongyang Xie, Yao Tian, Hao Zhang +5Graph Retrieval-Augmented Generation Agentic RAG
School of Computer Science, Wuhan University · The Hong Kong University of Science and Technology · The Chinese University of Hong Kong +1

Sep 30, 2026J/K move · Enter open · S save

PathAnchor: Path-Structured Evidence for Scientific Agents

Qiuhui Chen, Jiafan Lu, Shuaimin Tang, Tao Dai+4

School of Information Science and Engineering, East China University of Science and Technology · College of Intelligent Robotics and Advanced Manufacturing, Fudan University · Tencent

Evidence-Grounded Reasoning Scientific QA Structured Reasoning Evidence Retrieval Evidence-Grounded QA Scientific Document Retrieval

Open paper AskPDF arXiv

Scientific agents can retrieve relevant passages yet still lose functional order, mix evidence across sources, or state conclusions that exceed the retrieved record. We introduce PathAnchor, a bounded scientific reasoning system built on path-structured evidence workspaces. Instead of treating passages or extracted concepts as independent units, the system retrieves source-linked Material-Sensor-Signal-System trajectories that preserve role, direction, and the evidence supporting each transition. A controller uses three read-only tools to search paper-specific trajectories, trace paths across candidate sources, and open exact evidence before producing a claim-cited answer and an explicit evidence boundary. On 120 single- and cross-paper flexible-sensor questions, PathAnchor scores 82.6% and leads six evaluated systems. Under a matched controller, corpus, and six-call budget, replacing unordered concept graphs with path-structured records raises source recall from 61.3% to 82.9%, increases answers whose claims all cite opened evidence from 69.2% to 90.0%, and reduces tool calls. These results show that evidence organization affects retrieval and citation completeness under fixed agent resources.

Abstract

Web Search Agents

Explore similar work

PathAnchor: Path-Structured Evidence for Scientific Agents

SearchAtlas: Analyzing Agentic Search Strategies via Evidential Query Graphs

DocNavRAG: Document-Structured Graph RAG with Stateful Evidence Construction for Complex Document Question Answering