PaperlayerView exact revision on arXiv

Source-linked AI summary

SearchAtlas: Analyzing Agentic Search Strategies via Evidential Query Graphs

Jiacheng Sang, Mengyuan Li, Sanxing Chen, Yukun Huang, Yu Feng, Bhuwan Dhingra

arXiv:2609.10901v1cs.CL

TL;DR

SearchAtlas addresses the gap between evaluating search agents by final-answer correctness and understanding how they retrieve evidence for question constraints. It converts trajectories into evidential query DAGs, achieving strong agreement with human annotations, and shows that process diagnostics reveal failures associated with correctness while capturing information complementary to answer accuracy.

  • Problem

    Search-agent evaluation mostly emphasizes final-answer correctness, while the long chronological trajectories needed to understand evidence dependencies and search strategies are difficult to interpret.

  • Method

    SearchAtlas converts search trajectories into evidence-dependency query DAGs and derives diagnostics for answer-path topology, constraint grounding, and prior-knowledge reliance.

  • Results

    Across five agents and three benchmarks, the graphs expose systematic differences and process failures associated with incorrect answers; diagnostics achieve macro ROC-AUCs of 0.840–0.856 and outperform LLM-judge baselines.

  • Takeaways & Limitations

    Process quality and final-answer correctness provide complementary information, with graph diagnostics localizing fragmented support, unused constraints, and unsupported prior-knowledge shortcuts.

  • Takeaways & Limitations

    The framework is tested on closed-answer, English-language deep-search tasks and cannot recover dependencies that remain hidden from the trajectory.

Abstract

from arXiv · show

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.

1 Introduction

SearchAtlas addresses the limits of final-answer evaluation by representing search trajectories as evidence-dependent query graphs. Across agents and benchmarks, these graphs expose strategy differences and process failures that are associated with correctness and complement answer accuracy.

  • Framework: SearchAtlas converts each search trajectory into a query-to-query evidence-dependency DAG that makes support flow to the final answer explicit.The representation retains issued queries while linking later queries and answer facts to earlier retrieved evidence.
  • Framework: The automated pipeline parses trajectories, attributes earlier evidence to later queries and answer facts, and achieves macro edge F1 from 0.814 to 0.860 across four LLMs.Evaluation against 100 human-annotated graphs showed stable reconstructions across attribution models.
  • Empirical analysis: Across five agents and three benchmarks, graph profiles reveal systematic differences in search scale and evidence aggregation, including median DAG depths of 26 versus 2.The cited comparison contrasts MiroThinker with TYDP-Qwen3, while multi-source query rates also vary across settings.
  • Process diagnostics: The framework defines diagnostics for answer-path topology, constraint grounding, and reliance on unsupported prior knowledge.Together they identify misaligned support structures, unused question constraints, and unsupported shortcuts at specific actions.
  • Process diagnostics: Combined diagnostics achieve macro ROC-AUCs of 0.840–0.856 and provide a stronger correctness signal than LLM judges using raw trajectories or ordered query lists.An audit further shows that high-scoring errors and low-scoring successes reveal process information not reducible to final-answer correctness.

2 Related Work

Prior work uses graphs both to prescribe agent or reasoning behavior and to recover structure from completed execution traces. SearchAtlas belongs to the latter descriptive line while focusing on evidential dependencies in web-search trajectories.

  • Search-agent evaluation: Search-agent benchmarks predominantly evaluate final outputs such as task success, answer correctness, citation quality, or report quality rather than how agents arrived there.This motivates process-oriented analysis of search trajectories.
  • Graph representations: Prescriptive graph methods use trees or DAGs to scaffold reasoning, execute schedules, or optimize agent-system topologies.Examples include Tree-of-Thoughts, Graph-of-Thoughts, DAG-Math, GPTSwarm, and MacNet.
  • Post-hoc graph recovery: Post-hoc graph-recovery methods reconstruct structured reasoning or execution processes from completed traces.Examples recover semantic reasoning motifs, formal verification dependencies, or web-agent execution graphs.

3 SEARCHATLAS

SEARCHATLAS converts observable search logs into typed evidence-flow DAGs and uses deterministic extraction plus LLM attribution to recover their dependencies. The resulting graphs achieve high agreement with human annotations while supporting fine-grained answer attribution.

  • Graph definition: Each trajectory is represented as a typed directed graph containing the original question, issued queries with retrieved evidence, prior knowledge, and the final answer.Edges encode observable contributions while respecting the chronological order of query formation.
  • Graph definition: The graph distinguishes constraint-use, evidence-use, failure-response, and prior-knowledge edges to represent how information enters later queries or the answer.Failure-response edges cover hard and soft retrieval failures, while prior-knowledge edges mark unsupported content.
  • Graph construction: Redundant query parents are pruned by retaining the minimal earlier evidence set that explains supported parts of a later query.This preserves explanatory dependencies without duplicating overlapping support.
  • Graph construction: Answer attribution splits the final response into factual units and links each unit to a minimal set of supporting queries, or to prior knowledge when retrieval support is absent.Queries directly linked to the answer form Qans, while any evidence-use edge on a path to the answer is answer-reaching.
  • Automated parsing: The two-stage pipeline combines deterministic extraction of queries, results, failures, and explicit constraint links with LLM attribution of semantic evidence dependencies.The LLM processes one query at a time using the question, current reasoning block, and earlier retrieved evidence.
  • Automated parsing: Against 100 human-annotated trajectory DAGs, the parser achieves a macro edge F1 of 0.860 with similar performance across three benchmarks and stable results across four LLMs.The reported evaluation measures predicted versus human-labeled edges.

4 Process Diagnostics

SearchAtlas evaluates search behavior against the structure implied by question constraints. Parallel questions favor direct evidence-to-answer links, whereas sequential questions favor concentrated chains, with grounding and prior-knowledge reliance providing additional diagnostics.

  • Question Constraint Types: Sequential questions contain dependency chains requiring latent intermediate variables to be resolved before later constraints can be evaluated.Each discovery determines the target of the next search in the cited example.
  • Question Constraint Types: Parallel questions contain independently verifiable constraints that jointly restrict a target and can be resolved in any order.Their expected evidence structure differs from the focused chain required by sequential questions.
  • Answer-Path Topology: Parallel questions are expected to have flat answer paths with direct evidence-to-answer links, while sequential questions are expected to concentrate evidence in a chain.The topology diagnostic is instantiated separately for these two constraint types.
  • Answer-Path Topology: Answer-path directness measures the fraction of answer-reaching evidence edges that link directly to the final answer for parallel-constraint questions.Higher values indicate that retrieved evidence is used directly rather than routed through intermediate queries.
  • Answer-Path Topology: Answer-backbone concentration measures the fraction of answer-reaching edges on the longest path for sequential questions, with higher values indicating focus on one evidence chain.Lower concentration indicates shallow exploration dispersed across side branches.
  • Constraint Grounding: Constraint grounding measures whether question requirements enter answer-support paths through direct constraint coverage or backbone constraint share.High coverage means the answer structure accounts for more identifying requirements, while unsupported prior knowledge is separately tracked as a risk.

5 Experimental Results

Across five agents and three benchmarks, SEARCHATLAS reveals systematic differences in search scale, evidence aggregation, and question-conditioned support structures. Its diagnostics associate coherent evidence paths and grounded constraints with correctness, outperforming unstructured baselines while exposing cases where organized reasoning or final accuracy alone is insufficient.

  • 5.2 SEARCHATLAS Reveals Diverse Search Behaviors: MiroThinker searches most extensively on BrowseComp and DeepSearchQA, while TYDP produces the largest WebWalker-Hard DAGs and the highest synthesis rate across datasets.MiroThinker and TYDP also produce the deepest DAGs, indicating longer evidence chains.
  • 5.2 SEARCHATLAS Reveals Diverse Search Behaviors: Sequential questions produce deeper, more branched DAGs than parallel questions, which favor flatter graphs with direct evidence-to-answer support.Sequential structure reflects intermediate uncertainty, whereas parallel constraints can be checked independently.
  • 5.3 Failure Modes and Strengths of Search Strategies: Constraint grounding distinguishes successful flat structures from failures: identical topology can still leave requirements uncovered, while plausible constraint placement can coexist with a missing evidence path.Panels (c) and (d) are both flat, but only one covers the constraints; panels (h) and (j) show the converse failure.
  • 5.4 Process Signals Reflect Answer Correctness: Macro AUC reaches 0.840–0.856 when topology, constraint grounding, and prior-knowledge reliance are combined to rank correct versus incorrect trajectories.A held-out threshold also predicts correctness with F1 of 0.705 for sequential questions and 0.780 for parallel questions.
  • 5.4 Process Signals Reflect Answer Correctness: SEARCHATLAS outperforms LLM judges and raw-log statistics because it models how evidence is organized and used, not merely how much search activity occurred.The full-trajectory judge recovers fewer than half of correct trajectories, with positive recall 0.475 versus 0.750 for SEARCHATLAS.
  • 5.5 Where Process Signals and Accuracy Diverge: Process diagnostics capture complementary information rather than replacing answer accuracy: coherent reasoning can still support an incorrect candidate, while over-search can depress scores despite a correct answer.High-scoring errors may violate candidate-level constraints, whereas near-duplicate queries can diffuse support for a correct answer.

6 Conclusion

SEARCHATLAS audits search-agent behavior by recovering evidence dependencies and locating process failures in trajectories. Across agents and benchmarks, these process signals complement final-answer correctness.

  • SEARCHATLAS recovers query-to-query evidence dependencies to localize fragmented support, unreachable question constraints, and unsupported prior-knowledge shortcuts.These failures are localized to specific queries and edges in recovered DAGs.
  • Process quality and answer correctness carry complementary information, as shown by behavior–outcome divergences.

Limitations

SEARCHATLAS’s conclusions remain stable across attribution models, but graph recovery can inherit shared model errors and requires nontrivial inference cost. Its evaluation also depends on observable traces, correct question-regime routing, and closed-answer English-language tasks.

  • Recovered DAGs can inherit systematic errors shared across attribution models, while constructing each graph carries nontrivial inference cost.The paper identifies cheaper models, uncertainty estimates, or human validation as scaling needs.
  • The pipeline cannot capture dependencies that shape model behavior internally without appearing in the trajectory log.It works when reasoning text, tool calls, retrieved results, page visits, and final answers are exposed.
  • Misclassifying sequential versus parallel questions sends them to the wrong metric family and adds evaluation noise.
  • The study covers closed-answer, English-language deep-search tasks and leaves open-ended, non-English, and multimodal settings untested.Those settings may lack a single gold answer or fixed support structure for scoring.

A.1 Evidence Sources and Visit Attribution

The construction pipeline uses sentence-level reasoning identifiers and provenance windows from search snippets and visited-page summaries. It prioritizes visited-page evidence over snippets and think-only evidence, then resolves page ownership through a deterministic fallback order.

  • Evidence comes from sentence-split think blocks and attributable provenance windows built from search snippets and visited-page summaries.
  • Visited-page evidence is stronger than snippet evidence, which is stronger than think-only evidence.
  • Page ownership is resolved by exact URL matches, earlier-turn matches, URL-topic fallback, and finally Prior_knowledge fallback.URL-topic fallback also records an auxiliary Prior_knowledge source.

A.2 Signal Statuses, Candidate Parents, and MPSC

SEARCHATLAS classifies query signals using only earlier turns, separates original-question carry-over from supported signals, and selects sparse parent sets through deterministic minimal covering logic. Recency-first tie-breaking favors the latest source when clues recur.

  • Signals receive Q0_ONLY, Q0_SEEN, SEEN, or NEW statuses using only earlier turns as context.Q0_ONLY signals carry over directly from the original question and require no query-to-query parents.
  • The used-signal set U(q) consists of the target query’s remaining supported signals after direct original-question carry-over is excluded.
  • Minimal parent-set cover retains a sparse covering parent set through deterministic greedy set cover, recency-first tie-breaking, and lowest Prior_knowledge priority under equal gain.Candidate parents must be supported by provenance, explicit Prior_knowledge, or deterministic failure logic.

A.3 Failure-Response Edges and Orphan Queries

Failure transitions are represented explicitly, while conservative exclusions prevent unsupported or ambiguous query dependencies from entering the graph.

  • A.3 Failure-Response Edges and Orphan Queries: Hard failures encode unusable retrieval, whereas soft failures encode explicit insufficiency statements in the current reasoning block.Soft failure-response edges are preserved even when the next turn also receives evidence-use parents.
  • A.3 Failure-Response Edges and Orphan Queries: Same-turn queries remain disconnected because they are parallel actions, and queries may remain orphaned when no admissible parent is justified.The graph therefore permits query-level disconnection when the trajectory exposes no recoverable source.

A.4 Answer-Support Frontier Details

Answer support is assembled as a sparse frontier that preserves strong and genuinely distinct evidence branches while avoiding redundant ancestors.

  • A.4 Answer-Support Frontier Details: The answer node is grounded through stable answer signals, with query-to-answer edges added only when attributable tool outputs support at least one signal.Unsupported answer signals instead receive a Prior_knowledge →Answer edge.
  • A.4 Answer-Support Frontier Details: Answer-side parent selection retains strong support candidates before adding parents needed to cover unsupported answer signals.The frontier policy prunes only locally dominated ancestors from the same provenance cluster.
  • A.4 Answer-Support Frontier Details: Light deduplication yields a sparse frontier while preserving multiple supporting branches when they contribute distinct answer evidence.This balances compactness with coverage of genuinely independent support.

A.5 Representative DAG Overview

SearchAtlas constructs and validates evidence-dependency DAGs, then uses them to diagnose how search behavior relates to answer correctness across question types and evaluation baselines.

  • A.6 DAG Parsing Validation: SEARCHATLAS retains substantial agreement with human annotations, with Graph F1 between 0.814 and 0.860 across four attribution constructors.The evaluation holds trajectory inputs, ontology, preprocessing, and protocol fixed while replacing only the attribution model.
  • A.6 DAG Parsing Validation: The structured harness outperforms direct one-shot construction, which reaches only 0.072 edge F1 and 0.455 repeat Jaccard.Deterministic preprocessing, local attribution, and parent-set pruning are identified as central to robustness.
  • A.5 Representative DAG Overview: Sequential-constraint questions produce longer, more branching evidence structures and lower query efficiency because intermediate entities and later constraints require additional search.Discarded queries concentrate on candidate generation and verification rather than random exploration.
  • A.5 Representative DAG Overview: Parallel-constraint trajectories reuse retrieved evidence across a larger fraction of later search, whereas sequential trajectories usually reuse it only for the next few turns.The parallel group has a higher mean and median normalized evidence-reuse span.
  • A.13 Score Calibration and Auxiliary Outcome Prediction: High diagnostic-score bands are more accurate than low-score bands, but sequential precision is lower because coherent support paths can still bind to the wrong target.The score supports trajectory-level risk assessment and selective review rather than standalone correctness judgment.
  • A.14 Non-DAG LLM Judge Baselines: SEARCHATLAS improves over full-trajectory and ordered-query-list judges by 3.8 and 9.9 accuracy points, respectively.The corresponding macro-F1 improvements are 6.7 and 16.4 points.
Loading 2609.10901v1…