PaperlayerView exact revision on arXiv

Source-linked AI summary

When Connectivity Misleads: Guiding Agentic Search with Contrastive Evidence Paths

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

arXiv:2610.36134v1cs.IRcs.AI

TL;DR

Graph-based search can reveal sources beyond direct matches, but connectivity can inflate distractor rankings and flat scores hide evidence paths. CEP ranks candidates using calibrated strongest paths, and SCI organizes those candidates and paths for verification and continued exploration. Across BrowseComp-Plus and TREC-COVID, SCI reports stronger task performance and lower costs than evaluated alternatives.

  • Problem

    Graph diffusion can let highly connected distractors gain high rankings, while flat node scores do not expose paths that could guide agents’ next searches and readings.

    Source: §1 · p. 1

  • Method

    CEP ranks candidates by query-conditioned strongest-path support calibrated against background visitation and retains source paths; SCI presents candidates and paths in a map for verification and anchor expansion.

    Source: §1 · p. 2

  • Results

    SCI achieves the highest accuracy, fewest tool calls, and lowest total generation cost across three BrowseComp-Plus backbones, and the highest nDCG@10 and lowest total generation cost on TREC-COVID.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Analysis finds that CEP reduces preference for highly connected nodes and improves gold-document rankings, while the map and anchor expansion bring gold documents into the workspace for exploration.

    Source: §1 · p. 2, §6 · p. 8

    The study focuses on evidence retrieval and continued exploration over a fixed document corpus; maintaining the graph as sources change is outside its scope.

    Source: D Limitations · p. 12

Abstract

from arXiv · show

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.

1 Introduction

Cross-document graphs can help search agents find evidence beyond direct query matches, but connectivity can inflate distractor rankings and flat scores hide paths needed for continued exploration. CEP and SCI combine calibrated path-based retrieval with a structured map and anchor expansion; experiments report stronger task performance and lower interaction costs.

1 Introduction

  • Search agents use graph connections to discover sources across multiple hops, including documents with weak direct similarity to the query.Lexical or semantic matching alone may miss connections through intermediate entities.Source: §1 · p. 1
  • PPR can rank highly connected distractors above more useful candidates because it aggregates propagation contributions across paths.In controlled experiments with content, queries, and seeds fixed, adding connections to distractors improved their PPR ranks, sometimes into the top 10.Source: §1 · p. 1
  • CEP scores candidates by their strongest query-conditioned path, retains that path, and calibrates scores against background visitation to mitigate connectivity bias.The calibration requires easily reached documents to have stronger query-specific path support to rank highly.Source: §1 · p. 2
  • SCI presents CEP candidates, source paths, shared entities, and previews in a map that supports source verification and expansion from anchors toward information gaps.Agents can also initiate global retrieval with graphsearch.Source: §1 · p. 2
  • SCI achieves the highest accuracy, fewest tool calls, and lowest total generation cost across three BrowseComp-Plus backbones, and the highest nDCG@10 and lowest total generation cost on TREC-COVID.Against each backbone’s most accurate baseline, it reduces tool calls by 14.9%–54.0% and total generation costs by 8.4%–38.6%.Source: §1 · p. 2

2 Related Work

Prior work enables agents to search and verify corpus documents and uses graphs to retrieve information through cross-document relations. SCI combines candidate ranking with query-seed-to-candidate path support to guide retrieval, reading, and anchor expansion.

2 Related Work

  • Corpus-interaction agents iteratively retrieve and read evidence, while graph structures expose relations that can retrieve sources beyond direct text matching.The paper frames its approach as connecting these two research lines.Source: §2 · p. 2

Corpus Interaction for Search Agents

  • SCI combines candidate ranking with source paths to guide retrieval, reading, and expansion from anchors.Earlier corpus-interaction systems support searching, reading, and progressive collection of relevant documents, while AtlasNav organizes document graphs into hierarchical regions [8, 14, 17, 19, 27, 34].Source: §2 · p. 2

Graph Structures for Retrieval

  • PPR-based methods propagate query signals through graph connections, but aggregated contributions allow document connectivity to influence retrieval priorities.GraphRAG [7] builds entity graphs and community summaries; HippoRAG [10] and LinearRAG [33] use PPR; PathRAG [3] selects relational paths through flow propagation and pruning.Source: §2 · p. 2

3 Problem Formulation and Preliminaries

The setting considers agents that retrieve documents into a workspace, then use limited previews to choose what to inspect or search next. Documents and their relations are represented as a weighted graph, with paths connecting retrieval starting points to candidates.

3.1 Corpus Interaction Setting

  • The agent searches and verifies evidence with bash and read, while retrieval tools collect relevant documents’ full text in a local workspace.Tool outputs inform subsequent actions and evidence accumulation.Source: §3.1 · p. 2
  • Because the workspace is not shown all at once, each tool call exposes only limited candidate information or previews.The setting focuses on selecting and presenting candidates for continued exploration within this observation window.Source: §3.1 · p. 2
  • SCI’s overview links shared-entity document connections and static transitions to CEP scoring, map construction, and agent actions.The actions include verification with read and bash, anchor expansion with graphexpand(a,q), and global retrieval with graphsearch.Source: Figure 2 · p. 3

3.2 Document Graph and Path Notation

  • The corpus is represented as a weighted graph G = (V, L), where V contains document nodes and L contains edges representing document relations.Source: §3.2 · p. 3
  • A retrieval path is a sequence of connections from a starting document to a candidate document, with p(v) denoting starting weight and K(u, v) denoting transition probability.Source: §3.2 · p. 3
  • For a path of length zero, the path weight is the starting document’s weight p(v0).This notation describes paths from retrieval starting points to candidate documents.Source: §3.2 · p. 3

4 Method

SCI’s method constructs a shared-entity document graph, uses CEP to rank candidates and retain their strongest paths, then organizes retrieval results for agent-guided verification and expansion.

4.1 Document Graph Construction

  • Documents sharing entities form a weighted graph whose normalized transitions provide the offline basis for question-conditioned retrieval.Entity mentions are extracted with types and confidence scores; entities appearing in 2 to τ documents are retained to control connections from frequent entities.Source: §4.1 · pp. 3–4

4.2 Contrastive Evidence Paths Retrieval

  • Starting points combine semantic relevance to the original question with lexical matching to the current query, and semantic ranks adjust outgoing transition probabilities.Semantic relevance uses the maximum match across a document’s text segments; lexical and semantic ranks are fused to select starting points.Source: §4.2 · p. 4
  • CEP scores each candidate by its strongest path of at most H hops, then calibrates that support against a PageRank background visitation distribution.The square-root calibration moderates background-probability differences; higher-background candidates require stronger path support to outrank others.Source: §4.2 · p. 4
  • Max-product dynamic programming computes strongest-path support and records predecessor choices so CEP can recover each candidate’s source path.Each iteration compares zero-hop support with paths extended from predecessors; the computation takes O((T_b + mH)(N + J)) time per retrieval call.Source: §4.2 · p. 4
  • For each query, CEP places the top B candidates and documents on their strongest paths into the workspace for reading and verification.Workspace documents are deduplicated by document identifier.Source: §4.2 · p. 5

4.3 Map and Agent Evidence Exploration

  • SCI’s map presents top candidates, source paths, shared entities, and text previews; agents can inspect sources and expand from an anchor using a query for missing information.Anchor-guided local expansion uses CEP-based beam search for at most two hops, then ranks reached documents by their highest path score.Source: §4.3 · p. 5

5 Experiments

On BrowseComp-Plus and TREC-COVID, SCI combines strong answer and ranking results with reduced interaction costs. Ablations and analyses examine its retrieval, map, exploration, and ranking mechanisms.

5.1 Experimental Setup

  • Evaluation covers BrowseComp-Plus and TREC-COVID, with BrowseComp-Plus tested using three model backbones and a corpus expanded to 1 million documents for scaling experiments.SCI uses a 1,000-document candidate budget and displays the top 10 candidates in its map; agent methods were limited to 100 turns and 3,600 seconds per question.Source: §5.1 · p. 5

5.2 Main Results

  • Across three BrowseComp-Plus backbones, SCI has the highest accuracy, fewest tool calls, and lowest cost; on TREC-COVID it reaches 81.77% nDCG@10, 5.80 points above RARG++.Against the most accurate BrowseComp-Plus baseline for each backbone, tool calls fall 14.9%–54.0% and generation costs 8.4%–38.6%; on TREC-COVID, SCI also reduces turns, calls, and costs versus RARG++ by 56.3%, 33.6%, and 48.3%.Source: §5.2 · pp. 5–6, Table 1 · p. 6, Table 2 · p. 6
  • At 1 million documents, SCI reaches 85% BrowseComp-Plus accuracy while remaining more accurate than RARG++; after roughly tenfold corpus expansion, graphsearch and graphexpand average 0.877 and 0.264 seconds.Accuracy declines for both SCI and RARG++ as the corpus grows; the reported tool times remain acceptable for interactive retrieval.Source: §5.2 · p. 6, Figure 3 · p. 6

5.3 Ablation Study

  • CEP achieves the highest initial-workspace gold recall across retrieval budgets and Top10 previews, reaching 78.15% at budget 1,000 and beating the strongest baselines by 4.76 and 3.92 points at budgets 100 and 500.PCST returns a selected subtree rather than a ranked list, so its Top10 preview recall is not reported.Source: §5.3 · p. 6, Table 3 · p. 7
  • Removing either path support or background calibration reduces workspace and Top10 preview gold recall; both improve preview recall, with calibration having the larger effect.Full CEP has the highest workspace recall across retrieval budgets.Source: §5.3 · p. 7, Figure 4 · p. 7
  • Removing map structure or anchor-based local expansion lowers accuracy from 93% to 83%, and removing both lowers it to 80%; each variant also makes more total tool calls.Without map structure, global search and document-reading calls increase; without local expansion, read and bash calls increase.Source: §5.3 · p. 7, Table 4 · p. 7

5.4 Agent Behavior Analysis

  • Across exploration, workspace gold recall rises from 78.15% to 94.65%, map coverage from 30.55% to 76.48%, and preview coverage from 26.50% to 73.87%.On 511 queries where local expansion is used, it adds 67 gold documents to the workspace and first exposes 372 already-collected gold documents in the map; 37 new and 212 existing documents are later read.Source: §5.4 · p. 7, Table 5 · p. 8

5.5 Mechanism Analysis

  • CEP retrieves lower-degree documents than PPR, improves median gold rank from 245 to 147, and ranks gold documents higher in 73.1% of 2,407 rank pairs.With controlled distractor edge additions, PPR's Top10 entry rate rises from 0 to 15.22%; full CEP keeps it at 0, while its mean rank shifts from 45.79 to 75.87.Source: §5.5 · p. 8, Figure 6 · p. 8, Table 6 · p. 8

6 Conclusion

The conclusion presents CEP and SCI as responses to connectivity-induced ranking bias and missing source paths, reporting improved retrieval quality and interaction efficiency. The appendix establishes that edgewise and endpoint calibration produce equivalent candidate scores and optimal paths under the same path set and hop limit.

6 Conclusion

  • SCI improves answer accuracy, document ranking quality, and interaction efficiency while reducing generation costs on BrowseComp-Plus and TREC-COVID.The conclusion also reports that CEP mitigates connectivity-induced ranking bias, improves gold rankings and evidence coverage, and that anchor expansion brings undisplayed gold documents into the agent’s observation window.Source: §6 · p. 8

A Equivalence of Edgewise and Endpoint Calibration

  • The implementation incorporates background-visitation calibration into initialization and edgewise propagation while matching main-text endpoint calibration under the same path set and hop limit.The appendix states that the two formulations yield identical candidate scores and sets of optimal paths.Source: A Equivalence of Edgewise and Endpoint… · p. 9
  • Edgewise calibration yields the same candidate scores as endpoint calibration and preserves the optimal paths for each endpoint.Different endpoint calibration factors can change rankings across candidates.Source: A Equivalence of Edgewise and Endpoint… · p. 10
  • Although individual edgewise scoring factors may exceed 1, traversing a cycle cannot increase path score, and removing it cannot reduce calibrated score for the same endpoint.For a cycle, the background factors cancel; the remaining conditions are 0 < λ < 1 and 0 ≤ K_Q(u, v) ≤ 1.Source: A Equivalence of Edgewise and Endpoint… · p. 10

B.1 Experimental Details

The experimental details specify model and retrieval configurations, execution limits, evaluation procedures, and cost accounting. SCI uses entity- and semantic-retrieval settings, while the two benchmarks are evaluated with task-specific outcome measures.

Experimental Details

  • SCI uses GPT-6-Luna and DeepSeek-V4.1-Flash with high reasoning effort, and Qwen3.8-Flash and Qwen3.8-27B with xhigh reasoning effort.The local GPU environment has eight NVIDIA A100 80GB GPUs; entity extraction uses GLiNER2.5-small at a 0.5 confidence threshold across eight entity types.Source: §B.1 · p. 10
  • Semantic retrieval segments are limited to 1,024 tokens with 128-token overlap, and Qwen3-Embedding-0.6B vectors are reduced to 256 dimensions and L2-normalized.Entity recognition covers person, organization, location, creative work, event, award, profession or role, and disease or medical condition.Source: §B.1 · p. 10, Table 8 · p. 10
  • All agent methods have a limit of 100 turns and 3,600 seconds per query, with runtime including successful model requests and tool execution.BrowseComp-Plus accuracy is judged for semantic equivalence to reference answers; TREC-COVID nDCG@10 averages relevance-based scores over 50 queries.Source: §B.1 · p. 10
  • Generation costs are calculated using the token-generation rates summarized in Table 9.GPT-6-Luna rates vary by input tokens per request, while DeepSeek-V4.1-Flash uses off-peak rates.Source: §B.1 · p. 10, Table 9 · p. 10

B.2 Agent Implementation

SCI is implemented as an interactive agent with graph tools for collecting documents and updating a structured map, alongside tools for working with acquired documents. The section also describes context and preview handling and introduces supplementary comparisons on a 100-query subset.

B.2 Agent Implementation

  • Pi Agent manages model requests, tool execution, and conversation history, with a separate workspace and interaction history for each query.The four corpus-interaction tools are read, bash, graphsearch, and graphexpand; graph tools collect source documents and update the map.Source: §B.2 · p. 10
  • When input reaches 200,000 tokens, older tool-result bodies are replaced with [cleared], while at least the latest 12 tool results are retained.System instructions, the query, agent messages, and tool-call records remain unchanged.Source: §B.2 · pp. 10–11
  • Graph-search previews are limited to 240 characters and graph-expansion previews to 600, with source paths and character offsets preserved for later reading.Previews draw on the two indexed segments most relevant to the query; read and bash outputs are limited to 10 KiB.Source: §B.2 · p. 11

C Supplementary Comparisons

  • The supplementary comparisons examine smaller-model performance and conventional graph-based RAG methods on a subset of 100 BrowseComp-Plus queries.The experiments compare agent performance under different execution modes.Source: C Supplementary Comparisons · p. 11

C.1 Smaller Models and Specially Trained Agents

On a 100-query BrowseComp-Plus subset using Qwen3.8-27B, SCI outperforms RARG++ in accuracy while reducing turns and tool calls. The authors report that the main experiments’ accuracy and interaction-efficiency advantages extend to this smaller backbone.

C.1 Smaller Models and Specially Trained Agents

  • The comparison uses Qwen3.8-27B as a common backbone for SCI and five corpus-interaction baselines, alongside two specially trained deep research agents with similar total parameter counts.The subset contains 100 BrowseComp-Plus queries.Source: §C.1 · p. 11
  • SCI achieves 84% accuracy with Qwen3.8-27B and reduces turns and tool calls by 50.1% and 54.0%, respectively, versus RARG++, the highest-accuracy baseline.SCI also uses the fewest average turns and tool calls among the compared methods; corpus-interaction methods generally outperform specially trained deep research agents in accuracy and interaction efficiency.Source: §C.1 · p. 11, Table 11 · p. 11

C.2 Reference Comparison with Graph-Based RAG Methods

On a shared reduced corpus, SCI outperformed the graph-based RAG methods with 97% accuracy, the fewest turns and tool calls, and the lowest cost; on the full corpus, it reached 93% accuracy at $1.96 total generation cost.

C.2 Reference Comparison with Graph-Based RAG Methods

  • The comparison used 100 BrowseComp-Plus queries and a shared 1,545-document corpus; SCI was also evaluated on the full corpus.The shared corpus combined 562 annotated gold documents with 983 sampled negatives; the graph RAG methods built separate indexes.Source: §C.2 · p. 11
  • 97% accuracy, with the fewest turns and tool calls and the lowest cost, was achieved by SCI on the reduced corpus.The comparison used the same corpus and interaction budget.Source: §C.2 · p. 11
  • Integrated into Pi Agent, HippoRAG2 rose from 42% to 89% accuracy, PathRAG from 28% to 83%, and LinearRAG from 28% to 85%.SCI achieved 97% accuracy on the same reduced corpus.Source: §C.2 · p. 11
  • 93% accuracy at $1.96 total generation cost was achieved by SCI on the full corpus, below the costs of all three graph retrieval agents on the reduced corpus.Source: §C.2 · p. 11

D Limitations

The study addresses evidence retrieval and continued exploration on a fixed document corpus, leaving graph maintenance for changing sources outside scope. Local expansion supports clue verification, and SCI has the lowest mean execution time across three backbones.

D Limitations

  • Maintaining the document graph as sources are added or revised is outside the study’s fixed-corpus scope.Source: D Limitations · p. 12

E Case Studies of Local Expansion

  • Local expansion can retrieve an uncollected source for clue verification or surface a workspace document not previously displayed.The cases illustrate coauthorship verification and verification of immigration and marriage clues supporting the answer Jun.Source: E Case Studies of Local Expansion · p. 12

F End-to-End Execution Time

  • SCI achieves the lowest mean execution time across all three backbones.The results complement tool-usage and cost comparisons with shorter execution times.Source: F End-to-End Execution Time · p. 12

Related papers

Loading 2610.36134v1…