SearchAtlas: Analyzing Agentic Search Strategies via Evidential Query Graphs

# SearchAtlas: Analyzing Agentic Search Strategies via Evidential Query Graphs
Source: [https://arxiv.org/html/2609.10901](https://arxiv.org/html/2609.10901)
###### Abstract

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 introduceSearchAtlas, 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 edgeF1F\_\{1\}of86\.0%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\.SearchAtlasexposes 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\.111Code and data are available at[https://github\.com/DukeNLP/SearchAtlas](https://github.com/DukeNLP/SearchAtlas)\.

## 1Introduction

Search agents can plan multi\-step web queries, visit pages, and synthesize answers over long horizons\([Li et al\., 2025](https://arxiv.org/html/2609.10901#bib.bib19);[Team et al\., 2025b](https://arxiv.org/html/2609.10901#bib.bib28);[Team et al\., 2025a](https://arxiv.org/html/2609.10901#bib.bib27)\)\. A growing set of benchmarks evaluates these systems mostly on final\-answer correctness\([Wei et al\., 2025](https://arxiv.org/html/2609.10901#bib.bib33);[Du et al\., 2025](https://arxiv.org/html/2609.10901#bib.bib5);[Xi et al\., 2025](https://arxiv.org/html/2609.10901#bib.bib35);[Li et al\., 2026](https://arxiv.org/html/2609.10901#bib.bib20);[Gupta et al\., 2026](https://arxiv.org/html/2609.10901#bib.bib12)\), focusing on the outcome instead of the strategies of search agents\. Two agents may differ drastically in how they approach an answer but obtain the same accuracy on a given benchmark\.

The evidence needed to understand these strategies lies in search trajectories, which contain the agent’s thoughts and actions, as well as feedback received from the environment\. They are long and flattened into a chronological order of events, which obscures the information flow\. For example, agents often adopt branched search strategies in which one piece of retrieved evidence informs several later queries\. Conversely, multiple earlier results may be combined to support a single focused query\. We therefore need a representation that makes the evidential dependencies explicit, allowing us to trace how an answer is supported and identify where the search process goes wrong\.

![Refer to caption](https://arxiv.org/html/2609.10901v1/Figure1.png)Figure 1:SearchAtlas transforms a raw search trajectory into an evidential query DAG\. \(a\) The chronological event log hides repeated clues, verbose searches unrelated to the final answer, a potentially retried failure, query terms with no visible source, and the searches that eventually support the answer\. \(b\)SearchAtlasdeterministically parses the log, attributes each part of a new query to an earlier source, prunes redundant parents, and grounds answer facts\. The resulting DAG keeps every query while exposing evidence flow to the final answer and turns each flagged problem into explicit typed edges\.We introduceSearchAtlas\([Figure 1](https://arxiv.org/html/2609.10901#S1.F1)\), a framework that converts each trajectory to an evidence\-dependency query\-to\-query DAG\. Its nodes represent each issued search query\. Edges are added when one prior query’s retrieval observably supports the formation of a later query\. We show these graphs can be automatically constructed through deterministic preprocessing that parses each query’s search results and page visits into ordered reasoning nodes, followed by LLM\-based attribution of the earlier evidence supporting subsequent queries and answer facts\. Against 100 human\-annotated graphs, this pipeline achieves stable reconstructions and a macro edgeF1F\_\{1\}ranging from0\.8140\.814to0\.8600\.860across four LLMs\.

By aggregating query nodes and evidence edges into graph\-level statistics,SearchAtlasprovides a compact structural profile of an agent’s strategy\. Across 1,350 trajectories from five agent configurations on three benchmarks, these profiles reveal systematic differences in search scale and evidence aggregation\. For example, the median number of nodes and edges ranges from 6/7 for TYDP\-Qwen3 to 103/165 for MiroThinker on BrowseComp, reflecting a significantly larger search scale of MiroThinker\. Depth, branching, and the frequency with which queries synthesize multiple earlier results also vary across settings\. MiroThinker has a median DAG depth of 26, compared with 2 for TYDP\-Qwen3; the multi\-source query rate ranges from 8% for TYDP\-Qwen3 to 39% for WebSailor and TYDP\.

Furthermore, this structured graph representation helps diagnose whether an agent is effective in forming a plausible supporting\-evidence structure relative to the question’s unique constraint structure\. For example, questions withsequentialconstraints have to resolve intermediate uncertainty needed by later constraints, whileparallel\-constraint questions can check constraints independently\. The former therefore requires evidence flowing through a focused chain, while the latter prefers more direct evidence\-to\-answer support\.

Specifically, we define three answer\-support diagnostics\.Answer\-path topologymeasures whether the evidence has the expected structure\.Constraint groundingcaptures whether the question’s requirements are addressed in queries that contribute to the final answer, rather than only in abandoned queries whose results are not used\.Prior\-knowledge reliancemarks blindly trusting LLM parametric knowledge as answer\-supporting evidence without validation from retrieval\. Together, they localize misaligned supporting structures, unused constraints, and unsupported shortcuts to specific actions\.

Across settings, trajectories with aligned answer\-path topology, stronger constraint grounding, and lower prior\-knowledge reliance are indicative of correct answers\. We compute ROC\-AUC separately within each agent by using the combined diagnostic score to rank that agent’s correct and incorrect trajectories, yielding macro ROC\-AUCs of0\.8400\.840–0\.8560\.856\. In fact, the diagnostics provide a stronger correctness signal than LLM judges given the raw trajectory or ordered query list\. While this association arises because the diagnostics capture concrete failure patterns in how evidence is gathered and used, they remain informative about process quality when diverging from outcome\. Our audit shows that high\-scoring errors expose coherent answer\-support structures that bind to the wrong target, while low\-scoring successes reveal unnecessary over\-search or reliance on unverified prior knowledge that happened to be correct\.

#### Contributions\.

\(1\) We proposeSearchAtlas, an evidence\-dependency DAG representation and an automated construction pipeline validated against human annotations\. \(2\) Across five search agents and three benchmarks, we characterize differences in search scale and evidence aggregation and define three question\-type\-conditioned diagnostics\. \(3\) We show that these diagnostics localize process failures, provide a stronger correctness signal than unstructured trajectory baselines, and capture information complementary to final\-answer accuracy\.

## 2Related Work

#### Search\-agent benchmarks and evaluation\.

Benchmarks for search agents now span realistic web environments and long\-horizon information\-seeking tasks\([Mialon et al\., 2023](https://arxiv.org/html/2609.10901#bib.bib23);[Zhou et al\., 2024](https://arxiv.org/html/2609.10901#bib.bib43);[Krishna et al\., 2024](https://arxiv.org/html/2609.10901#bib.bib16);[Wei et al\., 2025](https://arxiv.org/html/2609.10901#bib.bib33);[Xi et al\., 2025](https://arxiv.org/html/2609.10901#bib.bib35);[Chen et al\., 2025a](https://arxiv.org/html/2609.10901#bib.bib2)\)\. Most judge what the agent ultimately produces, such as task success, answer correctness, citation quality, or report quality, rather than how it arrived there\([Gou et al\., 2025](https://arxiv.org/html/2609.10901#bib.bib10);[Du et al\., 2025](https://arxiv.org/html/2609.10901#bib.bib5);[Li et al\., 2026](https://arxiv.org/html/2609.10901#bib.bib20)\)\. Several recent efforts examine the process more directly for different purposes\. In the training setting, DeSA separates search optimization from answer generation after finding that answer\-only rewards induce skipped retrieval and redundant queries, and Agent\-RRM and PPR replace sparse outcome feedback with structured trajectory\-level signals\([Wang et al\., 2025](https://arxiv.org/html/2609.10901#bib.bib32);[Fan et al\., 2026a](https://arxiv.org/html/2609.10901#bib.bib7);[Xu et al\., 2025](https://arxiv.org/html/2609.10901#bib.bib36)\)\. RE\-TRAC summarizes accumulated evidence, uncertainties, and failures to steer later exploration\([Zhu et al\., 2026](https://arxiv.org/html/2609.10901#bib.bib44)\), while other diagnostics score or localize where a trajectory becomes unreliable, exposing weaknesses invisible to output\-level metrics\([Ye et al\., 2026](https://arxiv.org/html/2609.10901#bib.bib40);[Fan et al\., 2026b](https://arxiv.org/html/2609.10901#bib.bib8);[Wang et al\., 2026](https://arxiv.org/html/2609.10901#bib.bib31);[Kim et al\., 2025](https://arxiv.org/html/2609.10901#bib.bib14)\)\. These approaches treat the process as a training signal or a step\-level quality judgment, but do not analyze how retrieved evidence flows through a run\.

#### Graph representations of agent and reasoning processes\.

One line of work uses graph or DAG structures prescriptively, as scaffolds that models expand or schedules they execute\. For reasoning, Tree\-of\-Thoughts\([Yao et al\., 2023a](https://arxiv.org/html/2609.10901#bib.bib38)\)and Graph\-of\-Thoughts\([Besta et al\., 2024](https://arxiv.org/html/2609.10901#bib.bib1)\)search over self\-generated thoughts, while DAG\-Math\([Dziri et al\., 2023](https://arxiv.org/html/2609.10901#bib.bib6);[Zhang et al\., 2025b](https://arxiv.org/html/2609.10901#bib.bib42)\)structures mathematical reasoning as a DAG for multi\-agent execution\. GPTSwarm and MacNet represent agent systems as optimizable graph or DAG topologies\([Zhuge et al\., 2024](https://arxiv.org/html/2609.10901#bib.bib45);[Qian et al\., 2024](https://arxiv.org/html/2609.10901#bib.bib24)\), while Plan\-over\-Graph, Flash\-Searcher, and S\-DAG use graph or DAG schedules to parallelize execution or route reasoning across specialized agents\([Zhang et al\., 2025a](https://arxiv.org/html/2609.10901#bib.bib41);[Qin et al\., 2025](https://arxiv.org/html/2609.10901#bib.bib26);[Dong et al\., 2026](https://arxiv.org/html/2609.10901#bib.bib4)\)\.

#### Post\-hoc graph recovery from execution traces\.

A second descriptive group recovers graph structure post hoc from executed traces\. ReasoningFlow\([Lee et al\., 2025](https://arxiv.org/html/2609.10901#bib.bib17)\)parses reasoning traces of large reasoning models into semantically typed DAGs to characterize motifs such as planning, reflection, and backtracking; Graph of Verification\([Fang et al\., 2026](https://arxiv.org/html/2609.10901#bib.bib9)\)recovers a formal DAG from a chain\-of\-thought output and verifies each node from its minimal justified premises; and WebGraphEval\([Qian et al\., 2025](https://arxiv.org/html/2609.10901#bib.bib25)\)is closer to our setting because it operates on web\-agent trajectories\. However, it aggregates actions across multiple runs into a consensus graph\.SearchAtlasoperates on one search\-agent trajectory at a time\. Its edges are gated by attributable retrieved evidence, such as reused snippets, visited pages, or explicit failure statements\. This makes the graph an attribution object over external evidence flow, rather than a representation of internal reasoning or shared navigation behavior\.

## 3SearchAtlas

In this section, we describe howSearchAtlasconverts a raw search log of the agent’s queries, reasoning and tool results, into a DAG that encodes the evidential structure of the final answer\.

### 3\.1Graph Definition

Let a trajectory containNNsearch queries in chronological order\. We represent its observable evidence flow as a typed directed graphG=\(V,E\)G=\(V,E\),

V=\{q0,PK,A\}∪𝒬,\\displaystyle V=\\\{q\_\{0\},\\mathrm\{PK\},A\\\}\\cup\\mathcal\{Q\},𝒬=\{q1,…,qN\},\\displaystyle\\mathcal\{Q\}=\\\{q\_\{1\},\\ldots,q\_\{N\}\\\},\(1\)whereq0q\_\{0\}is the original question,qiq\_\{i\}is theii\-th issued query together with its retrieved search results and visited pages,PK\\mathrm\{PK\}is a source node for unattributed prior knowledge, andAAis the agent’s final answer\.

Each edge\(u,v\)∈E\(u,v\)\\in Estates that the content available atuuobservably contributes tovv\. These edges can be grouped into four types:Constraint\-useedges \(q0→qiq\_\{0\}\\to q\_\{i\}\) indicate that queryqiq\_\{i\}directly targets a requirement in the original question\.Evidence\-useedges \(qi→vq\_\{i\}\\to v\) mark that a later query or the final answervvrelies on a fact retrieved byqiq\_\{i\}\. When queryqjq\_\{j\}responds to an explicitly failed or insufficient earlier searchqiq\_\{i\}, we addfailure\-responseedges \(qi→qjq\_\{i\}\\to q\_\{j\}\)\. This accounts for both hard failures, such as zero results and blocked pages, and soft failures, where the agent judges the retrieved results insufficient\.Prior\-knowledgeedges \(PK→v\\mathrm\{PK\}\\to v\) mark content in a query or the answervvthat emerges neither fromq0q\_\{0\}nor from evidence retrieved by an earlier query\. Herev∈\{qi\+1,…,qN,A\}v\\in\\\{q\_\{i\+1\},\\ldots,q\_\{N\},A\\\}for an edge out ofqiq\_\{i\}, andi<ji<jfor query\-to\-query edges to respect the trajectory’s causal order\.

For query\-to\-query edges, we connect an earlier query only when its retrieved content helps form the later query\. If several candidates provide overlapping support \(i\.e\., the same fact\), we keep the minimal set that together explains the parts of the later query supported by earlier retrievals, avoiding redundant edges\.

For edges to the final answer, we adopt more fine\-grained attribution\. We first splitAAinto factual units, such as names, dates, numbers, acronyms, and other key spans\. For each unit, we identify a minimal set of supporting queries using a procedure similar to the one above\. Each retained query receives aqi→Aq\_\{i\}\\to Aedge\. We denote thesedirect answer\-supportqueries by𝒬ans=\{qi∈𝒬:\(qi,A\)∈E\}\\mathcal\{Q\}\_\{\\mathrm\{ans\}\}=\\\{q\_\{i\}\\in\\mathcal\{Q\}:\(q\_\{i\},A\)\\in E\\\}\. More generally, we denote an evidence\-use edge asanswer\-reachingif it lies on a directed path toAA\. If an answer unit has no retrieved support, we connectPK→A\\mathrm\{PK\}\\to A\.

### 3\.2Automated Parsing and Validation

Manually constructing a DAG for every search trajectory is tedious labor that prevents large\-scale evaluations\. We show accurate automated graph parsing can be implemented\. Specifically, we adopt a two\-stage pipeline where deterministic preprocessing handles information that can be extracted directly from the trajectory and LLM\-based attribution resolves evidence dependencies that require semantic interpretation\.

First, a deterministic program extracts each search query as a node and collects its search results\. It also detects search failures and addsq0→qiq\_\{0\}\\to q\_\{i\}constraint\-use edges when a query explicitly mentions a requirement from the original question\.

We then adopt an LLM to attribute the evidential linkages between queries\. Targeting one query at a time, the LLM is given the original question, the current reasoning block, and all earlier queries with their retrieved evidence to identify incoming evidence\-use edges\. The detailed attribution and parent\-pruning process can be found in Appendix[A](https://arxiv.org/html/2609.10901#A1)\.

The automated pipeline is evaluated against 100 human\-annotated trajectory DAGs\. Comparing the predicted and human\-labeled edges, the parser achieves a macro edgeF1F\_\{1\}of0\.8600\.860, with similar performance across the three benchmarks\. Reconstruction fidelity and downstream results remain stable across four different LLMs used for the second\-stage edge attribution \(Appendix[A\.6](https://arxiv.org/html/2609.10901#A1.SS6)\)\.

## 4Process Diagnostics

The constructed DAG captures fine\-grained evidence dependencies, which we use to derive high\-level diagnostics of how search agents model question constraints and organize evidence\. Although these dependencies merely describe how evidence flows, they become diagnostically meaningful when interpreted relative to the question’s constraint structure\. We therefore distinguish two question constraint types and define three type\-conditioned diagnostics of answer\-path topology, constraint grounding, and prior\-knowledge reliance\.

### 4\.1Question Constraint Types

A question hassequentialconstraints if they form a dependency chain in which at least one constraint refers to a latent intermediate variable\. The value of this variable must be resolved before the dependent constraint can be instantiated or evaluated\. In the sequential example of[Figure 3](https://arxiv.org/html/2609.10901#S4.F3), the agent needs to identify a physical therapist by tracing a 2023 article through a Gracie Award recipient to a coauthored study presented at APTA CSM\. Each discovery determines the target of the next search\.

Conversely, a question comes withparallelconstraints if it is specified either by one constraint or by multiple independently verifiable constraints that jointly restrict a common target variable\. In this case, constraints may be resolved in any order\.

Figure 2:Ideal structures for the two question constraint types from successful TYDP runs \(WebWalker\-004 and BrowseComp\-77\)\. In the parallel run, every supporting query connects directly to the answer; in the sequential run, evidence concentrates in a focused chain\.
### 4\.2Answer\-Path Topology

Motivated by prior work on supporting facts and connected reasoning paths in evidence\-grounded QA evaluations\([Yang et al\., 2018](https://arxiv.org/html/2609.10901#bib.bib37);[Trivedi et al\., 2022](https://arxiv.org/html/2609.10901#bib.bib29);[Trivedi et al\., 2023](https://arxiv.org/html/2609.10901#bib.bib30)\), we define an answer\-path topology diagnostic to describe how evidence is organized to construct the final answer\. We instantiate this diagnostic separately for the two question types to meet different expectations \([Figure 2](https://arxiv.org/html/2609.10901#S4.F2)\)\.

Since the constraints inparallel\-constraint questions can usually be checked independently, evidence for each constraint connects relatively directly to the final answer\. We measure this pattern throughanswer\-path directness\(GdirectG\_\{\\mathrm\{direct\}\}\), the fraction of answer\-reaching evidence\-use edges that link directly toAA\. A higher value indicates that retrieved evidence is used directly for answer construction, rather than being routed through intermediate queries\.

Forsequential\-constraint questions, effective strategies address one constraint at a time rather than wasting effort in unused evidence dispersed across side branches or abandoned paths\. We measure this withanswer\-backbone concentration\(BansB\_\{\\mathrm\{ans\}\}\), the fraction of answer\-reaching edges on the longest path toAA\. High concentration indicates that most of the search effort focuses on a single chain of evidence, whereas low concentration suggests shallow exploration of constraints\.

Figure 3:Illustration of constraint grounding\. Constraint units are highlighted in the question examples\. Four DAGs illustrate how the units are grounded on query nodes under high versus low direct constraint coverage \(parallel\) and high versus low backbone constraint share \(sequential\)\.
### 4\.3Constraint Grounding

We examine whether the constraints stated in the question are incorporated into the evidence paths leading to the final answer\. Search agents may commit to an answer while leaving some constraints unchecked\([Wang et al\., 2026](https://arxiv.org/html/2609.10901#bib.bib31);[Ko et al\., 2026](https://arxiv.org/html/2609.10901#bib.bib15);[Lee et al\., 2026](https://arxiv.org/html/2609.10901#bib.bib18)\)\.

For*sequential*\-constraint questions,backbone constraint share\(BCG\) measures the fraction of constraints addressed along the longest answer\-reaching path rather than dispersed across side branches\. For*parallel*\-constraint questions,direct constraint coverage\(DCC\) measures the fraction of question constraints deployed by answer support queries𝒬ans\\mathcal\{Q\}\_\{\\mathrm\{ans\}\}\. High coverage indicates that the answer\-path structure accounts for most of the question’s identifying requirements, whereas low coverage indicates that the model may produce an answer without grounding one or more of those requirements\.

### 4\.4Prior\-Knowledge Reliance

Recalling facts directly from LLM parametric knowledge to construct the final answer without retrieval verification is risky due to outdated training and hallucination\([Chen et al\., 2025b](https://arxiv.org/html/2609.10901#bib.bib3);[Huang et al\., 2025](https://arxiv.org/html/2609.10901#bib.bib13);[Lin et al\., 2025](https://arxiv.org/html/2609.10901#bib.bib21)\)\.

For*sequential*\-constraint questions,PKAans\\mathrm\{PKA\}\_\{\\mathrm\{ans\}\}is a binary indicator that monitors if prior knowledge is used directly in the final answer construction\. For*parallel*constraints that require independent verification, unsupported prior knowledge in any of these queries could be consequential\. So we count direct answer\-support queries formulated using unsupported information and normalize by the number of direct answer\-support queries\|𝒬ans\|\|\\mathcal\{Q\}\_\{\\mathrm\{ans\}\}\|\. We name itPKDans\\mathrm\{PKD\}\_\{\\mathrm\{ans\}\}\. Higher values indicate greater reliance on unsupported information during answer construction\.

## 5Experimental Results

### 5\.1Experimental Setup

#### Agents\.

To ensure evaluation generalizability, we select search agents with different base models and agentic scaffolding\. We evaluate \(1\)WebSailor\([Li et al\., 2025](https://arxiv.org/html/2609.10901#bib.bib19)\)\(v1, 32B\), a model post\-trained with agentic reinforcement learning \(DUPO\) and deployed within a ReAct\([Yao et al\., 2023b](https://arxiv.org/html/2609.10901#bib.bib39)\)loop, representing smaller open\-source agents trained with reinforcement learning; \(2\)MiroThinker\([Team et al\., 2025a](https://arxiv.org/html/2609.10901#bib.bib27)\)\(v1, 30B\), designed for interaction scaling and trained to sustain hundreds of tool calls within a 256K\-token context window; \(3\)Tongyi DeepResearch\(TYDP\)\([Team et al\., 2025b](https://arxiv.org/html/2609.10901#bib.bib28)\), a 30B\-parameter mixture\-of\-experts agent trained via agentic mid\-training and GRPO\-based post\-training for long\-horizon information seeking\. To separate the effect of the underlying model from that of the harness, we additionally run the Tongyi scaffold with two alternative backbones, GPT\-5 and Qwen3\-32B, under the same search policy; we denote these two variants as \(4\)TYDP\-GPT5and \(5\)TYDP\-Qwen3\. This setup yields five agents in total\.

#### Datasets\.

We evaluate both question types across three benchmarks: BrowseComp\([Wei et al\., 2025](https://arxiv.org/html/2609.10901#bib.bib33)\)provides sequential\-constraint questions \(150\), WebWalker\-Hard\-English\([Wu et al\., 2025](https://arxiv.org/html/2609.10901#bib.bib34)\)provides parallel\-constraint questions \(70\), and DeepSearchQA\([Gupta et al\., 2026](https://arxiv.org/html/2609.10901#bib.bib12)\)provides a stress test with 25 questions per regime\. Full curation details and question IDs are in Appendix[A\.9](https://arxiv.org/html/2609.10901#A1.SS9)\.

### 5\.2SearchAtlasReveals Diverse Search Behaviors

The recovered DAGs reveal substantial differences in how extensively agents search and in how information is carried across their search steps\. In Table[1](https://arxiv.org/html/2609.10901#S5.T1), a higher number of nodes indicates that the agent takes more search steps before reaching the answer and a higher number of edges means that more search queries are interconnected through reused evidence or question constraints\. MiroThinker conducts the most extensive searches on BrowseComp and DeepSearchQA, producing the most nodes and edges, whereas TYDP produces the largest DAGs on WebWalker\-Hard\. TYDP\-Qwen3, which receives the least search training, consistently produces the shortest trajectories across all three benchmarks\.

Multi\-source query rate and depth show how agents integrate information differently\. TYDP has the largest synthesis rate, followed by MiroThinker, on all datasets, which indicates that they tend to formulate complex search queries based on multiple evidence sources\. Depth is measured by averaging the lengths of the two longest structural paths in each DAG\. MiroThinker and TYDP produce the deepest DAGs, indicating the ability of both agents to build upon long chains of evidence\.

Search AgentNodesEdgesDep\.BranchMulti\-SourceQuery RateBrowseComp \(150 questions\)WebSailor27496539%MiroThinker103165261129%TYDP67133161139%TYDP\-GPT521413832%TYDP\-Qwen367228%WebWalker\-Hard \(70 questions\)WebSailor810215%MiroThinker812326%TYDP16233411%TYDP\-GPT5813238%TYDP\-Qwen355220%DeepSearchQA \(50 questions\)WebSailor13193315%MiroThinker76150241238%TYDP62144181241%TYDP\-GPT515273619%TYDP\-Qwen378228%Table 1:Graph statistics of search agents across datasets\. Nodes, edges, depth, and branching are trajectory\-level medians\. Branching is the average unique\-child count of the two widest non\-Q0nodes in each trajectory, excluding failure\-derived edges\. Multi\-source query rate is the mean percentage of query nodes per trajectory that rely on multiple earlier queries\. Nodes, edges, and depth are rounded to integers; branching is reported to at most two decimal places\.
### 5\.3Failure Modes and Strengths of Search Strategies

Our proposed diagnostics reveal the strengths and failures in how search agents construct answers\.

Figure 4:SearchAtlasvisualizes trajectories of five agents on a parallel question \(WebWalker\-017, a–e\) and a sequential question \(BrowseComp\-77, f–j\)\. Query nodes shown in darker shades contribute to the final answer\. The values of the three diagnostics defined in[section 4](https://arxiv.org/html/2609.10901#S4)are shown below each panel; green indicates favorable values, whereas red color flags values indicating a potential process failure\. The correct runs \(c\), \(f\), \(g\), \(i\) match the expected shape per question constraint type\. The failed ones scatter evidence, leave constraints uncovered, or draw the answer from prior knowledge \(illustrated as purple edges pointing to A\)\.Answer\-path topology shows whether the evidence is organized the way the question requires: flat for parallel questions, a focused chain for sequential ones\. Question type induces systematic differences in DAG structure\. Sequential\-constraint questions tend to produce DAGs with greater depth and more branches, which lower query efficiency \(the proportion of issued queries ultimately contributing to the final answer\) and increase the number of queries that synthesize evidence from multiple prior steps\. Parallel\-constraint questions, by contrast, produce search structures in which retrieved evidence remains useful across a larger fraction of the trajectory\. At the agent level, depth serves as a relatively stable signature of an agent’s search behavior, while width is more sensitive to question type\. These statistics reflect a fundamental difference in how evidence must be assembled to resolve each question type \(Appendix[A\.11](https://arxiv.org/html/2609.10901#A1.SS11)\), which motivates the question\-type\-conditioned metrics\.

Parallel\-constraint questions decompose into independent checks against a single candidate, so their correct evidence graphs are flat: most edges land directly on the answer node\. In sequential\-constraint questions, some constraints become interpretable only after earlier constraints resolve an intermediate entity\. A focused dependency chain matches this resolution structure, while evidence spread over side branches, failed candidates, or abandoned directions signals fragmented support;[subsection 5\.4](https://arxiv.org/html/2609.10901#S5.SS4)tests this in aggregate\. The two question types therefore reward high answer\-path directness for parallel questions and high answer\-backbone concentration for sequential questions\.

This contrast appears directly in the reference runs of[Figure 2](https://arxiv.org/html/2609.10901#S4.F2)\. Being flat is a matter of how evidence reaches the answer, not of how many queries supply it: the correct parallel run in panel \(c\) of[Figure 4](https://arxiv.org/html/2609.10901#S5.F4)supports the answer through a single query that carries most of the question’s constraints, with no intermediate chain\. Panels \(g\) and \(i\) share the sequential backbone shape, while the failures in panels \(e\) and \(j\) do not form the structure expected for their question type\.

Constraint grounding shows which of the question’s requirements reach the answer’s support, and which are stranded in side searches or never used at all\. Topology alone is insufficient\. In[Figure 4](https://arxiv.org/html/2609.10901#S5.F4), panels \(c\) and \(d\) are both flat, but panel \(d\) covers only half of the constraints and fails\. Panels \(h\) and \(j\) show the converse: constraint placement can look reasonable even when the main evidence path is missing or the answer uses unsupported information\.

Prior\-knowledge reliance pinpoints where unsupported content from LLM parametric knowledge enters the answer’s support\. In[Figure 4](https://arxiv.org/html/2609.10901#S5.F4), panels \(a\), \(d\), \(h\), and \(j\) use unsupported information for the answer when other indicators of the graph look healthy, which potentially leads to their failures\. The correct cases in the same rows do not\.

Macro AUC after each diagnostic is added

Full\-score AUC by agent

Table 2:Macro AUC after adding each diagnostic and full\-score AUC for each agent\. Every AUC is computed within one agent; the Macro column averages the five agent\-level results\. Complete agent\-level AUCs for all three stages are reported in Appendix[A\.12](https://arxiv.org/html/2609.10901#A1.SS12)\.
### 5\.4Process Signals Reflect Answer Correctness

Diagnostic scores are associated with answer correctness, and the behaviors they capture are consequential for search outcomes\.

#### Three diagnostics together are associated with answer correctness within each agent\.

The three diagnostics are on different scales: the topology and grounding metrics are in\[0,1\]\[0,1\], the sequential PK indicator is binary, and the parallel PK score can exceed11\. We therefore normalize each metric into standard distributions and sum them \(the PK reliance metric was negated\) so that a higher score always means a better\-supported answer\. For each agent on each benchmark and regime, we compute the AUC of this score for separating the agent’s correct trajectories from its incorrect ones under question\-held\-out evaluation; macro values average the five agent\-level AUCs\. TYDP\-Qwen3 on BrowseComp has an answer accuracy of only0\.0400\.040, yet its correct runs rank above its incorrect ones with an AUC of0\.8800\.880\. Topology alone already provides a strong ranking signal, and adding grounding and then PK reliance improves macro AUC on every benchmark, reaching0\.8400\.840–0\.8560\.856for the full score \([Table 2](https://arxiv.org/html/2609.10901#S5.T2)\)\.

Furthermore, we find that a simple held\-out threshold on the score predicts correctness with anF1F\_\{1\}of0\.7050\.705on the sequential regime and0\.7800\.780on the parallel regime\. Calibration details and module ablations are in Appendices[A\.13](https://arxiv.org/html/2609.10901#A1.SS13)and[A\.12](https://arxiv.org/html/2609.10901#A1.SS12)\.

#### Comparison with non\-DAG baselines\.

To confirm thatSearchAtlasenables nontrivial, targeted diagnostics of search agent failures, we compare the DAG\-derived scorer with LLM judges with access to the complete raw log or the ordered query list in context\. WhileSearchAtlassimply adopts a thresholded sum of three interpretable scores, it remains the most accurate of the three \(Table[3](https://arxiv.org/html/2609.10901#S5.T3)\)\. The full\-trajectory judge predicts failures at a much higher rate and recovers fewer than half of the correct trajectories \(pos\. recall0\.4750\.475vs\.0\.7500\.750, Appendix[A\.14](https://arxiv.org/html/2609.10901#A1.SS14)\)\. This result demonstrates that evidence dependencies provide outcome\-associated information beyond unstructured trajectory content and queries alone\.

Table 3:Association with answer correctness, pooled over 1,350 trajectories\. The two non\-DAG baselines are GPT\-5\.2 judges\.To further test whether this signal can be explained by how much search activity a trajectory contains, we compare the DAG\-derived score with a classifier using only raw\-log statistics, including query count, page visits, trace length, and query redundancy \(Appendix[A\.15](https://arxiv.org/html/2609.10901#A1.SS15)\)\.SearchAtlasoutperforms this baseline by a wide margin, showing that search statistics cannot substitute for modeling how evidence is organized and used\.

#### Ablation of constraint\-grounding region\.

To show that constraint\-grounding is most important when it occurs on the answer\-supporting backbone, we compare the constraint\-grounding metric with a trajectory\-wide baseline\. This baseline marks a constraint as covered whenever any query uses it, even if that query lies in branches that do not contribute to the final answer\. The constraint\-grounding metric outperforms the baseline on both question types \(Table[4](https://arxiv.org/html/2609.10901#S5.T4)\); on BrowseComp, the trajectory\-wide baseline is no better than chance\. Whether a constraint is mentioned somewhere carries little signal; what matters is whether it contributes to the answer\. Appendix[A\.14](https://arxiv.org/html/2609.10901#A1.SS14.SSS0.Px1)provides the complete experimental setup\.

Table 4:Constraint\-grounding localization\. Each cell reports macro\-AUC/AP of the grounding signal alone; both columns use the same constraint units and differ only in where a deployment counts\.
#### Ablation of location of prior\-knowledge use\.

We test whether the location of prior\-knowledge use matters while holding all other metrics fixed\. The baseline uses the same DAG, answer\-path topology and constraint\-grounding metrics asSearchAtlas\. The only difference is that the baseline counts PK use anywhere in the trajectory, whereasSearchAtlasrestricts it to the parts that contribute to the final answer\. Replacing the PK score with this baseline reduces macro AUC from0\.8400\.840to0\.7770\.777on WebWalker\-Hard and from0\.8560\.856to0\.7690\.769on parallel DeepSearchQA\. This shows that PK is most informative when its location relative to answer support is retained \(Appendix[A\.14](https://arxiv.org/html/2609.10901#A1.SS14.SSS0.Px2)\)\.

### 5\.5Where Process Signals and Accuracy Diverge

Behavioral evidence structure and answer correctness can diverge in meaningful ways\. A well\-organized support path can be fruitless if it binds to the wrong target, while a correct answer can emerge from diffuse search or an unsupported shortcut\. We audit 100 such disagreements—high\-scoring incorrect and low\-scoring correct trajectories—selected separately within each benchmark\-regime and model \([Table 5](https://arxiv.org/html/2609.10901#S5.T5)and[Figure 5](https://arxiv.org/html/2609.10901#S5.F5)\)\.

Table 5:Behavior–outcome divergence cases by agent\. Rate is the percentage of all trajectories for that model\.High\-scoring errors illustrate that well\-organized reasoning is necessary but not sufficient for trajectory success\. Our diagnostics measure whether evidence and question constraints are concentrated along the answer\-reaching path, capturing the structural coherence of the trajectory\. In BrowseComp\-111 / TYDP\-Qwen3 \([Figure 5](https://arxiv.org/html/2609.10901#S5.F5)\-a\), the agent links the clues to Bruno Mars and Silk Sonic without supporting evidence, then continues to gather candidate\-specific evidence despite retrieving facts that contradict the question’s constraints\. The trajectory nevertheless scores highly because these constraints are deployed coherently along the answer backbone\. This case shows that structural organization is an important component of successful reasoning but must be paired with candidate\-level constraint satisfaction\.

Conversely, over\-search can lower the DAG\-derived score despite a correct answer\. WebWalker\-010 / TYDP \([Figure 5](https://arxiv.org/html/2609.10901#S5.F5)\-c\), for example, reaches the answer through near\-duplicate queries that produce diffuse support\. A smaller group succeeds through prior\-knowledge shortcuts rather than retrieval\-backed evidence\.

Figure 5:The top block gives the cleaned outlier distribution by score–accuracy disagreement type \(N=100N=100\)\. Panels \(a\)–\(d\) show premature target binding with unresolved contradictions, missed correct evidence, over\-search success, and shortcut success\.

## 6Conclusion

Evaluating search agents requires more than checking whether they end with the correct answer\. We introducedSearchAtlas, a query\-to\-query DAG framework for post\-hoc behavioral auditing of how retrieved evidence, failures, and prior knowledge appear in search trajectories\. Across five search agents and three benchmarks, the recovered DAGs localize recurring process failures—fragmented answer support, question constraints that never reach the answer, and unsupported prior\-knowledge shortcuts—to specific queries and edges\. That these signals track answer correctness is external evidence that the failures they surface matter, and the behavior–outcome divergences show that process quality and answer correctness carry complementary information\. Looking forward, the representation can be extended to analyze more general\-purpose agents with richer tool settings beyond search\.

## Limitations

SearchAtlasuses an LLM to make its local attribution decisions\. Reconstruction fidelity and the downstream conclusions remain stable across four attribution models, but the recovered DAGs can still inherit systematic errors shared across models, and constructing each DAG carries a nontrivial inference cost\. Scaling the framework will therefore call for cheaper attribution models, uncertainty estimates, or human\-in\-the\-loop validation\. The pipeline recovers only what the trajectory reveals\. It works well when a trajectory exposes its reasoning text, tool calls, retrieved results, page visits, and final answer, but any dependency that shapes the model internally without surfacing in the log stays invisible to it\. Additionally, scoring assumes the question has been routed to the right regime\. Since sequential and parallel questions are judged against different expected evidence structures, a misclassification sends a question to the wrong metric family and adds evaluation noise\.

Finally, our study stays within closed\-answer, English\-language deep\-search tasks, whose questions have identifiable answers that map cleanly to sequential\- or parallel\-constraint regimes\. This leaves open\-ended, non\-English and multimodal settings untested, as trajectories in these settings may have no single gold answer or fixed support structure to score against\.

## Acknowledgments

We thank members of the NLP group at Duke University for fruitful discussions\. This work was supported by NSF award IIS\-2211526\.

## References

- Besta et al\. \(2024\)Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoefler\. 2024\.[Graph of thoughts: Solving elaborate problems with large language models](https://doi.org/10.1609/AAAI.V38I16.29720)\.In*Thirty\-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024, Thirty\-Sixth Conference on Innovative Applications of Artificial Intelligence, IAAI 2024, Fourteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2024, February 20\-27, 2024, Vancouver, Canada*, pages 17682–17690\. AAAI Press\.
- Chen et al\. \(2025a\)Kaiyuan Chen, Yixin Ren, Yang Liu, Xiaobo Hu, Haotong Tian, Tianbao Xie, Fangfu Liu, Haoye Zhang, Hongzhang Liu, Yuan Gong, Chen Sun, Han Hou, Hui Yang, James Pan, Jianan Lou, Jiayi Mao, Jizheng Liu, Jinpeng Li, Kangyi Liu, and 14 others\. 2025a\.[xbench: Tracking agents productivity scaling with profession\-aligned real\-world evaluations](https://arxiv.org/abs/2506.13651)\.*Preprint*, arXiv:2506\.13651\.
- Chen et al\. \(2025b\)Sanxing Chen, Yukun Huang, and Bhuwan Dhingra\. 2025b\.[Real\-time factuality assessment from adversarial feedback](https://doi.org/10.18653/v1/2025.acl-long.81)\.In*Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\)*, pages 1610–1630, Vienna, Austria\. Association for Computational Linguistics\.
- Dong et al\. \(2026\)Jiangwen Dong, Zehui Lin, Wanyu Lin, and Mingjin Zhang\. 2026\.[S\-DAG: A subject\-based directed acyclic graph for multi\-agent heterogeneous reasoning](https://doi.org/10.1609/aaai.v40i35.40180)\.*Proceedings of the AAAI Conference on Artificial Intelligence*, 40\(35\):29394–29402\.
- Du et al\. \(2025\)Mingxuan Du, Benfeng Xu, Chiwei Zhu, Xiaorui Wang, and Zhendong Mao\. 2025\.[Deepresearch bench: A comprehensive benchmark for deep research agents](https://arxiv.org/abs/2506.11763)\.*Preprint*, arXiv:2506\.11763\.
- Dziri et al\. \(2023\)Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D\. Hwang, Soumya Sanyal, Sean Welleck, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi\. 2023\.[Faith and fate: Limits of transformers on compositionality](https://arxiv.org/abs/2305.18654)\.In*Advances in Neural Information Processing Systems \(NeurIPS\)*\.
- Fan et al\. \(2026a\)Kaixuan Fan, Kaituo Feng, Manyuan Zhang, Tianshuo Peng, Zhixun Li, Yilei Jiang, Shuang Chen, Peng Pei, Xunliang Cai, and Xiangyu Yue\. 2026a\.[Exploring reasoning reward model for agents](https://arxiv.org/abs/2601.22154)\.*Preprint*, arXiv:2601\.22154\.
- Fan et al\. \(2026b\)Shengda Fan, Xuyan Ye, Yupeng Huo, Zhi\-Yuan Chen, Yiju Guo, Shenzhi Yang, Wenkai Yang, Shuqi Ye, Jingwen Chen, Haotian Chen, Xin Cong, and Yankai Lin\. 2026b\.AgentProcessBench: Diagnosing step\-level process quality in tool\-using agents\.*arXiv preprint arXiv:2603\.14465*\.
- Fang et al\. \(2026\)Jiwei Fang, Bin Zhang, Changwei Wang, Jin Wan, and Zhiwei Xu\. 2026\.[Graph of verification: Structured verification of llm reasoning with directed acyclic graphs](https://doi.org/10.1609/aaai.v40i36.40322)\.In*Proceedings of the AAAI Conference on Artificial Intelligence*, volume 40, pages 30665–30672\.
- Gou et al\. \(2025\)Boyu Gou, Zanming Huang, Yuting Ning, Yu Gu, Michael Lin, Weijian Qi, Andrei Kopanev, Botao Yu, Bernal Jiménez Gutiérrez, Yiheng Shu, Chan Hee Song, Jiaman Wu, Shijie Chen, Hanane Nour Moussa, Tianshu Zhang, Jian Xie, Yifei Li, Tianci Xue, Zeyi Liao, and 7 others\. 2025\.[Mind2web 2: Evaluating agentic search with agent\-as\-a\-judge](https://arxiv.org/abs/2506.21506)\.
- Guo and Vosoughi \(2025\)Xiaobo Guo and Soroush Vosoughi\. 2025\.Serial position effects of large language models\.In*Findings of the Association for Computational Linguistics: ACL 2025*, pages 927–953, Vienna, Austria\.
- Gupta et al\. \(2026\)Nikita Gupta, Riju Chatterjee, Lukas Haas, Connie Tao, Andrew Wang, Chang Liu, Hidekazu Oiwa, Elena Gribovskaya, Jan Ackermann, John Blitzer, Sasha Goldshtein, and Dipanjan Das\. 2026\.[Deepsearchqa: Bridging the comprehensiveness gap for deep research agents](https://arxiv.org/abs/2601.20975)\.
- Huang et al\. \(2025\)Ziyang Huang, Xiaowei Yuan, Yiming Ju, Jun Zhao, and Kang Liu\. 2025\.[Reinforced internal\-external knowledge synergistic reasoning for efficient adaptive search agent](https://doi.org/10.48550/arXiv.2505.07596)\.*Preprint*, arXiv:2505\.07596\.
- Kim et al\. \(2025\)Wonjoong Kim, Sang Yoon Park, Yeonjun In, Sein Kim, Dongha Lee, and Chanyoung Park\. 2025\.Beyond the final answer: Evaluating the reasoning trajectories of tool\-augmented agents\.*arXiv preprint arXiv:2510\.02837*\.
- Ko et al\. \(2026\)Dayoon Ko, Jihyuk Kim, Sohyeon Kim, Haeju Park, Dahyun Lee, Gunhee Kim, Moontae Lee, and Kyungjae Lee\. 2026\.[When is enough not enough? illusory completion in search agents](https://doi.org/10.48550/arXiv.2602.07549)\.*Preprint*, arXiv:2602\.07549\.
- Krishna et al\. \(2024\)Satyapriya Krishna, Kalpesh Krishna, Anhad Mohananey, Steven Schwarcz, Adam Stambler, Shyam Upadhyay, and Manaal Faruqui\. 2024\.Fact, fetch, and reason: A unified evaluation of retrieval\-augmented generation\.*arXiv preprint arXiv:2409\.12941*\.
- Lee et al\. \(2025\)Jinu Lee, Sagnik Mukherjee, Dilek Hakkani\-Tur, and Julia Hockenmaier\. 2025\.[Reasoningflow: Semantic structure of complex reasoning traces](https://arxiv.org/abs/2506.02532)\.*Preprint*, arXiv:2506\.02532\.
- Lee et al\. \(2026\)Nahyun Lee, Dongkeun Yoon, Guijin Son, Geewook Kim, Dayoon Ko, Jeonghun Park, Haneul Yoo, Jaewon Cho, Junghun Park, Changyoon Lee, Kyochul Jang, Jaeyeon Kim, Eunsu Kim, Woojin Cho, and Seungone Kim\. 2026\.[K\-BrowseComp: A web browsing agent benchmark grounded in korean contexts](https://doi.org/10.48550/arXiv.2606.02404)\.*Preprint*, arXiv:2606\.02404\.
- Li et al\. \(2025\)Kuan Li, Zhongwang Zhang, Huifeng Yin, Liwen Zhang, Litu Ou, Jialong Wu, Wenbiao Yin, Baixuan Li, Zhengwei Tao, Xinyu Wang, Weizhou Shen, Junkai Zhang, Dingchu Zhang, Xixi Wu, Yong Jiang, Ming Yan, Pengjun Xie, Fei Huang, and Jingren Zhou\. 2025\.[Websailor: Navigating super\-human reasoning for web agent](https://arxiv.org/abs/2507.02592)\.*Preprint*, arXiv:2507\.02592\.
- Li et al\. \(2026\)Ruizhe Li, Mingxuan Du, Benfeng Xu, Chiwei Zhu, Xiaorui Wang, and Zhendong Mao\. 2026\.[Deepresearch bench ii: Diagnosing deep research agents via rubrics from expert report](https://arxiv.org/abs/2601.08536)\.
- Lin et al\. \(2025\)Tzu\-Han Lin, Wei\-Lin Chen, Chen\-An Li, Hung\-yi Lee, Yun\-Nung Chen, and Yu Meng\. 2025\.[Adasearch: Balancing parametric knowledge and search in large language models via reinforcement learning](https://doi.org/10.48550/arXiv.2512.16883)\.*Preprint*, arXiv:2512\.16883\.
- Liu et al\. \(2024\)Nelson F\. Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang\. 2024\.Lost in the middle: How language models use long contexts\.*Transactions of the Association for Computational Linguistics*, 12:157–173\.
- Mialon et al\. \(2023\)Grégoire Mialon, Clémentine Fourrier, Craig Swift, Thomas Wolf, Yann LeCun, and Thomas Scialom\. 2023\.GAIA: A benchmark for general AI assistants\.*arXiv preprint arXiv:2311\.12983*\.
- Qian et al\. \(2024\)Chen Qian, Zihao Xie, Yifei Wang, Wei Liu, Yufan Dang, Zhuoyun Du, Weize Chen, Cheng Yang, Zhiyuan Liu, and Maosong Sun\. 2024\.[Scaling large\-language\-model\-based multi\-agent collaboration](https://arxiv.org/abs/2406.07155)\.*Preprint*, arXiv:2406\.07155\.
- Qian et al\. \(2025\)Yaoyao Qian, Yuanli Wang, Jinda Zhang, Yun Zong, Meixu Chen, Hanhan Zhou, Jindan Huang, Yifan Zeng, Xinyu Hu, Chan Hee Song, and Danqing Zhang\. 2025\.[Webgrapheval: Multi\-turn trajectory evaluation for web agents using graph representation](https://arxiv.org/abs/2510.19205)\.
- Qin et al\. \(2025\)Tianrui Qin, Qianben Chen, Sinuo Wang, He Xing, King Zhu, He Zhu, Dingfeng Shi, Xinxin Liu, Ge Zhang, Jiaheng Liu, Yuchen Eleanor Jiang, Xitong Gao, and Wangchunshu Zhou\. 2025\.[Flash\-searcher: Fast and effective web agents via dag\-based parallel execution](https://arxiv.org/abs/2509.25301)\.*Preprint*, arXiv:2509\.25301\.
- Team et al\. \(2025a\)MiroMind Team, Song Bai, Lidong Bing, Carson Chen, Guanzheng Chen, Yuntao Chen, Zhe Chen, Ziyi Chen, Jifeng Dai, Xuan Dong, Wenhan Dou, Yue Deng, Yunjie Fu, Junqi Ge, Chenxia Han, Tammy Huang, Zhenhang Huang, Jerry Jiao, Shilei Jiang, and 36 others\. 2025a\.[Mirothinker: Pushing the performance boundaries of open\-source research agents via model, context, and interactive scaling](https://arxiv.org/abs/2511.11793)\.*Preprint*, arXiv:2511\.11793\.
- Team et al\. \(2025b\)Tongyi DeepResearch Team, Baixuan Li, Bo Zhang, Dingchu Zhang, Fei Huang, Guangyu Li, Guoxin Chen, Huifeng Yin, Jialong Wu, Jingren Zhou, Kuan Li, Liangcai Su, Litu Ou, Liwen Zhang, Pengjun Xie, Rui Ye, Wenbiao Yin, Xinmiao Yu, Xinyu Wang, and 38 others\. 2025b\.[Tongyi deepresearch technical report](https://arxiv.org/abs/2510.24701)\.*Preprint*, arXiv:2510\.24701\.
- Trivedi et al\. \(2022\)Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal\. 2022\.[MuSiQue: Multihop questions via single\-hop question composition](https://doi.org/10.1162/tacl_a_00475)\.*Transactions of the Association for Computational Linguistics*, 10:539–554\.
- Trivedi et al\. \(2023\)Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal\. 2023\.[Interleaving retrieval with chain\-of\-thought reasoning for knowledge\-intensive multi\-step questions](https://doi.org/10.18653/v1/2023.acl-long.557)\.In*Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\)*, pages 10014–10037, Toronto, Canada\. Association for Computational Linguistics\.
- Wang et al\. \(2026\)Jiaming Wang, Ziteng Feng, Jiangtao Wu, Ruihao Li, Qianqian Xie, Yuxiang Ren, He Zhu, Xueming Han, Fanyu Meng, Junlan Feng, and Jiaheng Liu\. 2026\.[Where do deep\-research agents go wrong? span\-level error localization in agent trajectories](https://doi.org/10.48550/arXiv.2606.02060)\.*Preprint*, arXiv:2606\.02060\.
- Wang et al\. \(2025\)Yiding Wang, Zhepei Wei, Xinyu Zhu, and Yu Meng\. 2025\.[Beyond outcome reward: Decoupling search and answering improves llm agents](https://arxiv.org/abs/2510.04695)\.*Preprint*, arXiv:2510\.04695\.
- Wei et al\. \(2025\)Jason Wei, Zhiqing Sun, Spencer Papay, Scott McKinney, Jeffrey Han, Isa Fulford, Hyung Won Chung, Alex Tachard Passos, William Fedus, and Amelia Glaese\. 2025\.[Browsecomp: A simple yet challenging benchmark for browsing agents](https://doi.org/10.48550/arXiv.2504.12516)\.*arXiv preprint arXiv:2504\.12516*\.
- Wu et al\. \(2025\)Jialong Wu, Wenbiao Yin, Yong Jiang, Zhenglin Wang, Zekun Xi, Runnan Fang, Linhai Zhang, Yulan He, Deyu Zhou, Pengjun Xie, and Fei Huang\. 2025\.[WebWalker: Benchmarking LLMs in web traversal](https://doi.org/10.18653/v1/2025.acl-long.508)\.In*Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\)*, pages 10290–10305, Vienna, Austria\. Association for Computational Linguistics\.
- Xi et al\. \(2025\)Yunjia Xi, Jianghao Lin, Menghui Zhu, Yongzhao Xiao, Zhuoying Ou, Jiaqi Liu, Tong Wan, Bo Chen, Weiwen Liu, Yasheng Wang, Ruiming Tang, Weinan Zhang, and Yong Yu\. 2025\.[Infodeepseek: Benchmarking agentic information seeking for retrieval\-augmented generation](https://arxiv.org/abs/2505.15872)\.*Preprint*, arXiv:2505\.15872\.
- Xu et al\. \(2025\)Peiran Xu, Zhuohao Li, Xiaoying Xing, Guannan Zhang, Debiao Li, and Kunyu Shi\. 2025\.[Hybrid reward normalization for process\-supervised non\-verifiable agentic tasks](https://arxiv.org/abs/2509.25598)\.*Preprint*, arXiv:2509\.25598\.
- Yang et al\. \(2018\)Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D\. Manning\. 2018\.[HotpotQA: A dataset for diverse, explainable multi\-hop question answering](https://doi.org/10.18653/v1/D18-1259)\.In*Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing*, pages 2369–2380, Brussels, Belgium\. Association for Computational Linguistics\.
- Yao et al\. \(2023a\)Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L\. Griffiths, Yuan Cao, and Karthik Narasimhan\. 2023a\.[Tree of thoughts: Deliberate problem solving with large language models](http://papers.nips.cc/paper_files/paper/2023/hash/271db9922b8d1f4dd7aaef84ed5ac703-Abstract-Conference.html)\.In*Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 \- 16, 2023*\.
- Yao et al\. \(2023b\)Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R\. Narasimhan, and Yuan Cao\. 2023b\.[React: Synergizing reasoning and acting in language models](https://openreview.net/pdf?id=WE_vluYUL-X)\.In*The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1\-5, 2023*\. OpenReview\.net\.
- Ye et al\. \(2026\)Fangda Ye, Yuxin Hu, Pengxiang Zhu, Yibo Li, Ziqi Jin, Yao Xiao, Yibo Wang, Lei Wang, Zhen Zhang, Lu Wang, Yue Deng, Bin Wang, Yifan Zhang, Liangcai Su, Xinyu Wang, He Zhao, Chen Wei, Qiang Ren, Bryan Hooi, and 3 others\. 2026\.[Miroeval: Benchmarking multimodal deep research agents in process and outcome](https://arxiv.org/abs/2603.28407)\.*Preprint*, arXiv:2603\.28407\.
- Zhang et al\. \(2025a\)Shiqi Zhang, Xinbei Ma, Zouying Cao, Zhuosheng Zhang, and Hai Zhao\. 2025a\.[Plan\-over\-graph: Towards parallelable llm agent schedule](https://arxiv.org/abs/2502.14563)\.*Preprint*, arXiv:2502\.14563\.
- Zhang et al\. \(2025b\)Yuanhe Zhang, Ilja Kuzborskij, Jason D\. Lee, Chenlei Leng, and Fanghui Liu\. 2025b\.[Dag\-math: Graph\-of\-thought guided mathematical reasoning in llms](https://arxiv.org/abs/2510.19842)\.*Preprint*, arXiv:2510\.19842\.
- Zhou et al\. \(2024\)Shuyan Zhou, Frank F\. Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, Uri Alon, and Graham Neubig\. 2024\.[Webarena: A realistic web environment for building autonomous agents](https://arxiv.org/abs/2307.13854)\.*Preprint*, arXiv:2307\.13854\.
- Zhu et al\. \(2026\)Jialiang Zhu, Gongrui Zhang, Xiaolong Ma, Lin Xu, Miaosen Zhang, Ruiqi Yang, Song Wang, Kai Qiu, Zhirong Wu, Qi Dai, Ruichun Ma, Bei Liu, Yifan Yang, Chong Luo, Zhengyuan Yang, Linjie Li, Lijuan Wang, Weizhu Chen, Xin Geng, and Baining Guo\. 2026\.[Re\-trac: Recursive trajectory compression for deep search agents](https://arxiv.org/abs/2602.02486)\.*Preprint*, arXiv:2602\.02486\.
- Zhuge et al\. \(2024\)Mingchen Zhuge, Wenyi Wang, Louis Kirsch, Francesco Faccio, Dmitrii Khizbullin, and Jürgen Schmidhuber\. 2024\.GPTSwarm: Language agents as optimizable graphs\.In*Proceedings of the 41st International Conference on Machine Learning*\.

## Appendix AAdditional Construction Details

### A\.1Evidence Sources and Visit Attribution

The construction pipeline uses two evidence channels\. First, each think block is sentence\-split into stable sentence identifiers so that query\-side justifications can cite exact reasoning sentences\. Second, earlier tool outputs are segmented into attributable provenance windows from search snippets and visited\-page summaries\. In the implementation, visited\-page evidence is treated as stronger than snippet evidence, and snippet evidence is treated as stronger than think\-only evidence\.

Visited\-page attribution is resolved by a deterministic priority order: exact URL match against same\-turn search results, exact match in earlier turns, URL\-topic fallback based on salient path segments, and finallyP​r​i​o​r​\_​k​n​o​w​l​e​d​g​ePrior\\\_knowledgefallback when no owner can be recovered\. When ownership is recovered only through URL\-topic fallback, the system also records an auxiliaryP​r​i​o​r​\_​k​n​o​w​l​e​d​g​ePrior\\\_knowledgesource because the agent likely constructed the authoritative URL instead of directly retrieving it\.

### A\.2Signal Statuses, Candidate Parents, and MPSC

For each target queryqq, the implementation tokenizes the query into normalized signals and assigns each signal one of four statuses using only earlier turns as context:Q0\_ONLY,Q0\_SEEN,SEEN, andNEW\. Signals markedQ0\_ONLYare treated as direct carry\-over from the original question and do not require query\-to\-query parents\. The remaining supported signals define the used\-signal setU⁡\(q\)U\(q\)\.

Candidate parents may come only from prior queries that appear in provenance for signals inU⁡\(q\)U\(q\), fromP​r​i​o​r​\_​k​n​o​w​l​e​d​g​ePrior\\\_knowledgewhen an explicitly introduced signal lacks retrievable provenance, or from deterministic failure logic\. Each candidate parentppcovers a subset of the target’s used signals\. Minimal parent\-set cover \(MPSC\) retains a minimal covering parent set, implemented as a deterministic greedy set\-cover approximation with recency\-first tie\-breaking and lowest priority forP​r​i​o​r​\_​k​n​o​w​l​e​d​g​ePrior\\\_knowledgeunder equal gain\. This keeps the query\-side graph sparse and stable across runs\. Recency\-first tie\-breaking reflects the serial\-position behavior of LLMs in long contexts: when the same information appears at multiple positions, models rely most on its most recent occurrence\([Liu et al\., 2024](https://arxiv.org/html/2609.10901#bib.bib22);[Guo and Vosoughi, 2025](https://arxiv.org/html/2609.10901#bib.bib11)\), so among earlier queries supplying the same clue, the latest copy is the one most plausibly conditioning the next query\.

### A\.3Failure\-Response Edges and Orphan Queries

Failure transitions are encoded explicitly rather than being folded into topical similarity\. Hard failures correspond to unusable retrieval such as zero\-result pages, access denial, login walls, or HTTP failures\. Soft failures correspond to explicit insufficiency statements in the current think block\. The implementation always preserves deterministic soft anchor\-to\-anchor edges once a soft\-failure pattern is detected, even if the next turn also receives evidence\-use parents\.

Two conservative exclusions prevent over\-attribution\. First, same\-turn queries are never connected because they are parallel actions\. Second, a query may remain orphaned when no admissible parent can be justified\. The graph is therefore allowed to be disconnected at the query level when the trajectory itself does not expose a recoverable source\.

### A\.4Answer\-Support Frontier Details

The answer node preserves the original final answer text but is grounded through a smaller set of stable answer signals, including whole\-answer spans, text\-anchored answer units, and high\-value names, numbers, years, and acronyms\. A query receives aq→Answerq\\rightarrow\\mathrm\{Answer\}edge only when its attributable tool outputs support at least one answer signal\. When no supporting query provenance exists for an answer signal, aP​r​i​o​r​\_​k​n​o​w​l​e​d​g​e→AnswerPrior\\\_knowledge\\rightarrow\\mathrm\{Answer\}edge is added instead, indicating that the answer is unsupported by retrieval and treated as drawn from the model’s prior knowledge\.

Answer\-side parent selection follows a frontier policy instead of strict minimality\. The system retains strong support candidates first, then adds extra parents only when necessary to cover still\-unsupported answer signals\. It prunes only locally dominated ancestors from the same provenance cluster and performs light deduplication afterward\. This yields a sparse frontier while preserving multiple supporting branches when they genuinely contribute distinct answer evidence\.

### A\.5Representative DAG Overview

The BrowseComp portion of the 100\-DAG canonical validation package contains 50 DAGs: ten tasks \(BC7, BC9, BC10, BC11, BC12, BC15, BC22, BC33, BC40, BC44\) crossed with five systems\. This subset provides the detailed worked examples used for illustration, while Appendix[A\.6](https://arxiv.org/html/2609.10901#A1.SS6)reports the full validation package across BrowseComp, WebWalker\-Hard, and DeepSearchQA\.

![Refer to caption](https://arxiv.org/html/2609.10901v1/Detailed_Example.png)Figure 6:Worked example of aSearchAtlasDAG for one trajectory\. The figure shows how query nodes, evidence\-use query\-to\-query edges, prior\-knowledge attribution, and answer\-support edges are represented in a concrete case\.
### A\.6DAG Parsing Validation

Human\-labeled DAGs serve as canonical references for evaluating the generated DAG pipeline\. Two annotators independently labeled each trajectory using the same raw trajectory evidence and the guidelines summarized below\. Edges on which the annotators agreed formed an initial consensus graph; remaining ambiguous or disputed edges were reviewed against the raw trajectory and adjudicated through a five\-author audit to produce the final canonical DAG\. The annotation target is the model’s actual trajectory and final answer, not the dataset’s gold answer\.

#### Annotation inputs and workflow\.

Annotators used an interactive HTML labeling tool organized query by query \(Figure[7](https://arxiv.org/html/2609.10901#A1.F7)\)\. The interface presented the original question, the model’s final answer, automatically generated deterministicq0q\_\{0\}edges, and the sequence of extracted search queries\. For each query, annotators first reviewed the query content, the reasoning block that issued it, the retrieved tool results, visited webpages, and a word\-status table labeling each query word as copied from the original question, previously seen, introduced from earlier retrieved evidence, or unsupported; for any word whose provenance was not established by exact carryover, they used this evidence to classify it as aq0q\_\{0\}paraphrase, an unsupported prior\-knowledge contribution, or unresolved\.

Second, for each query, the interface displayed candidate parent queries, edge type, confidence, notes, and the words of that query covered by that candidate parent\. For each covered signal, the tool exposed supporting evidence such as first and latest query occurrence, matching reasoning sentences, and provenance windows from source queries\. Finally, annotators reviewed answer\-support candidates from query nodes to the final answer and exported the resulting graph JSON\.

Table[6](https://arxiv.org/html/2609.10901#A1.T6)summarizes the edge\-specific annotation rules\. Annotators add an edge only when they can identify visible evidence, a visible failure, an original\-question constraint, or an unsupported model assumption that explains the target query or answer\.

Table 6:Condensed human annotation rules for canonical DAG construction\. The full internal guideline uses the same principle throughout: visible contribution, not possible relevance\.![Refer to caption](https://arxiv.org/html/2609.10901v1/figures/human_anno.png)Figure 7:Human DAG annotation interface used to construct canonical DAGs\. The interface lets annotators review each candidate parent query and inspect the evidence provenance of individual query tokens\.
#### Human disagreement and adjudication\.

Table[7](https://arxiv.org/html/2609.10901#A1.T7)summarizes the recurring disagreement categories, and Table[8](https://arxiv.org/html/2609.10901#A1.T8)provides representative adjudication decisions from 39 trajectories\. These tables document the annotation protocol and are not treated as additional independent labels\.

Table 7:Disagreement taxonomy used during adjudication of the canonical DAG annotations\.Table 8:Examples of adjudication decisions drawn from the audited annotation reports\. These examples instantiate the disagreement taxonomy in[Table 7](https://arxiv.org/html/2609.10901#A1.T7)\.
#### Canonical annotation package scale\.

The 100 canonical DAGs are compact in number but not in annotation volume\. As summarized in Table[9](https://arxiv.org/html/2609.10901#A1.T9), they cover three benchmarks and all five systems, requiring thousands of node and edge decisions\.

Table 9:Scale of the human canonical DAG validation package\. The parent\-pair count is the full temporal search space implied by query order\. For each query,q0q\_\{0\}and all previous queries are possible parents before provenance filtering\. It is not the number of manually clicked include/exclude decisions\.These tables are the appendix counterpart of the reliability claim in Section 3\. They summarize the stability and ground\-truth\-aligned \(GT\-aligned\) graph\-accuracy results for the 100 canonical DAG package: ten BrowseComp tasks and five tasks each from WebWalker\-Hard and DeepSearchQA, all crossed with five systems\. Graph precision, recall, andF1F\_\{1\}compare each majority\-vote graph against its human\-adjudicated canonical DAG using exact\(source,target\)\(\\mathrm\{source\},\\mathrm\{target\}\)edge matches\. Each metric is computed independently per DAG and then macro\-averaged separately; consequently, the reported meanF1F\_\{1\}is not obtained by taking the harmonic mean of the reported mean precision and recall\. Stability is the mean pairwise Jaccard over repeated generated DAGs\. Seventy\-one of the 100 canonical DAGs contain at least one failure\-response relation, illustrating that recovery and failed branches are common in the validation set\.

Table 10:GT\-aligned graph reconstruction and run stability for the 100 human\-adjudicated canonical DAGs\. Precision, recall, and GraphF1F\_\{1\}are computed per DAG and macro\-averaged separately within each dataset–model group\.Table 11:Dataset\-level reliability summary for the human\-adjudicated canonical package\. Precision, recall, and GraphF1F\_\{1\}are computed per DAG and macro\-averaged separately\.Table 12:Edge\-type\-level GT alignment and repeat stability for the 100 canonical DAG package\. For each type, precision, recall, andF1F\_\{1\}use exact source–target matches within each DAG and are macro\-averaged separately; a type absent from both graphs is treated as an exact match\. Stability is pairwise Jaccard computed within each edge type before averaging across DAGs\.Table 13:Scale of the human\-adjudicated canonical DAG package\. Gold edges are unique\(source,target\)\(\\mathrm\{source\},\\mathrm\{target\}\)pairs, matching the evaluation unit\. Candidate parent pairs count possible earlier\-query parent choices for each query node\.We test whether reconstruction and downstream conclusions depend on the LLM used for local attribution\. We hold the trajectory inputs, graph ontology, deterministic preprocessing, and evaluation protocol fixed, and replace only the attribution model\. Table[14](https://arxiv.org/html/2609.10901#A1.T14)evaluates four constructors against the same 100 human\-adjudicated DAGs\. Precision, recall, and GraphF1F\_\{1\}are computed per DAG and macro\-averaged separately\. All four constructors retain substantial agreement with human annotations, with GraphF1F\_\{1\}between0\.8140\.814and0\.8600\.860\.

Table 14:Sensitivity of canonical\-DAG reconstruction to the local attribution model\. All non\-constructor components are held fixed\.At full\-set scale, we reconstruct the 1,350\-trajectory evaluation with GLM\-5\.2 and Gemini\-3\.5\-Flash\. Relative to the GPT\-5\.2 graphs, their per\-trajectory macro edgeF1F\_\{1\}scores are0\.8660\.866and0\.8700\.870, respectively\. We then recompute the complete question\-held\-out diagnostic evaluation\. Table[15](https://arxiv.org/html/2609.10901#A1.T15)shows that all constructor–regime comparisons preserve the same stage\-wise result: constraint grounding improves on topology alone, and PK reliance provides a further improvement\. Final AUCs remain between0\.7600\.760and0\.8610\.861\.

Table 15:Stage\-wise held\-out AUC under different DAG constructors\. Each entry reports Topology / \+ Grounding / \+ PK\-risk penalty\.We also report the inference cost of graph construction\.

Table 16:Graph\-construction cost for the 1,350\-trajectory evaluation\.The contrast with direct one\-shot construction, which reaches only0\.0720\.072edgeF1F\_\{1\}and0\.4550\.455repeat Jaccard, indicates that the structured harness—deterministic preprocessing, local evidence attribution, and parent\-set pruning—is central to this robustness\.

We also test whether the graph can be recovered by prompting GPT\-5\.2 to directly produce a DAG from the trajectory, without the structured construction pipeline\. The pilot covers the 50\-DAG BrowseComp subset of the canonical package: ten BrowseComp questions, five agents, and three repeated direct\-generation runs per case\. We compare each generated graph against the human\-adjudicated canonical graph using exact source–target edge\-pair precision, recall, andF1F\_\{1\}; edge kinds are ignored in this comparison\. Repeat stability is measured by repeat\-to\-repeat edge Jaccard\.

Direct GPT\-5\.2 DAG Baseline PromptRole\.Convert a raw web\-search / deep\-research trajectory directly into a DAG using the same ontology as the staged Query\-DAG pipeline\.Input\.The model receives raw trajectory text, including the original question, issued queries/actions, tool results when present, reasoning text, and final answer\.Nodes\.Include exactly one Q0 node, one chronological query node for each distinct search/query/action request, exactly one Answer node, and a Prior\_knowledge node only if an edge uses it\.Answer units\.Decompose the provided final answer into short answer units\. Each answer unit must be a literal or normalized span from the final answer\.Edge kinds\.Use Q0→\\rightarrowq constraint\-use edges when a query deploys a question constraint; q→\\rightarrowq or q→\\rightarrowAnswer evidence\-use edges only when the trajectory shows that retrieved evidence was materially used; Prior\_knowledge→\\rightarrowq/Answer prior\-knowledge edges only when a necessary signal is introduced without trajectory evidence; and failure\-response edges only when the trajectory explicitly states a failed or insufficient earlier query and the later query repairs that gap\.Hard rules\.Do not use outside knowledge, correct the agent, infer hidden tool results, hallucinate evidence, create Answer support from topical overlap, or add redundant edges\. If support is uncertain, omit the edge or mark confidence as uncertain\.Output\.Return JSON only withq0\_units,answer\_units, graph nodes, graph edges,no\_source\_found, and brief notes\.

Table 17:Overall direct GPT\-5\.2 DAG\-construction baseline\. Direct generation obtains moderate precision but extremely low recall andF1F\_\{1\}, indicating that it misses most GT edges\.By agent

By question

Table 18:Direct GPT\-5\.2 DAG baseline by agent and by question\. P, R,F1F\_\{1\}, and Jac\. denote micro precision, micro recall, microF1F\_\{1\}, and repeat\-to\-repeat edge Jaccard\. Recall remains low across both agents and validation questions, showing that direct prompting is not a substitute for the structured attribution pipeline\.The direct baseline usually emits sparse graphs that contain a small number of plausible edges, which explains the moderate precision, but it fails to recover the dense attribution structure needed for query\-to\-query analysis\. The result motivates the design choice in Section 3: the LLM is used for narrow attribution decisions inside a constrained pipeline, rather than being asked to synthesize the entire DAG in one step\.

### A\.7Human Audit of Question Type and Constraint Decomposition

We separately audit the two annotations used by the downstream diagnostics\. Constraint units are proposed by an LLM, checked by a deterministic parser, and independently reviewed by two annotators; question types are reviewed under the operational dependency definition in Appendix[A\.8](https://arxiv.org/html/2609.10901#A1.SS8)\. For each annotation target, agreed labels form the initial consensus and disagreements are resolved through five\-annotator adjudication\. Table[19](https://arxiv.org/html/2609.10901#A1.T19)reports exact agreement before adjudication\.

Table 19:Independent human audit of question\-type and constraint annotations before adjudication\.
### A\.8Question\-Type Classification Prompt

The following prompt follows the definitions in Section[4](https://arxiv.org/html/2609.10901#S4)\. It treats dependency\-carrying search, ranked or survivor\-set maintenance, and derived\-owner mappings as sequential constraints, and direct\-field evaluation over a shared target or bounded candidate space as parallel constraints\.

Question\-Type Classification PromptClassify each question as exactly one of:SEQUENTIAL\_CONSTRAINT:The question requires dependency\-carrying search\. The solver must first construct or bind an intermediate candidate set, entity, source, owner, ranking, or eligibility state, and later constraints depend on that intermediate state before the final answer can be selected\.PARALLEL\_CONSTRAINT:The question requires direct candidate evaluation\. The constraints are direct predicates on the same target variable, such as attributes, dates, counts, rankings, memberships, thresholds, comparisons, semantic matches, or simple aggregations over a shared candidate space\.Core distinction\.Do not classify by the number of lookups, sources, or constraints\. If all conditions can be checked as direct predicates on the same candidatexx, choosePARALLEL\_CONSTRAINT\. ChooseSEQUENTIAL\_CONSTRAINTwhen earlier retrieval changes what later constraints are evaluated against, or when a constructed candidate state must be preserved through downstream checks\.Decision rules\.1\.Direct\-field rule:UsePARALLEL\_CONSTRAINTwhen the question asks for an entity or direct attribute and all constraints describe direct fields of that same target\.2\.Compact\-anchor rule:UsePARALLEL\_CONSTRAINTwhen the question is anchored to a named table, report, website, organization, event corpus, legal context, roster, or bounded candidate set, and the remaining work only reads, filters, compares, intersects, or aggregates direct attributes of those candidates\.3\.Dependency\-chain rule:UseSEQUENTIAL\_CONSTRAINTwhen the solver must first resolve an intermediate entity, value, source, owner, or candidate set before later constraints become meaningful\.4\.Ranked/survivor\-state rule:UseSEQUENTIAL\_CONSTRAINTwhen a top\-kk, bottom\-kk, highest/lowest group, shortlist, or survivor set is constructed and then carried through multiple downstream checks before the final answer is selected\.5\.Derived\-owner rule:UseSEQUENTIAL\_CONSTRAINTwhen a candidate must be mapped to another evidence target before the decisive check, such as entity→\\rightarrowsource, university→\\rightarrowcity, event→\\rightarrowdate/month, person→\\rightarrowwork, item→\\rightarrowlinked document, or legal/textual item→\\rightarrowcited item\.6\.Broad\-survivor rule:UseSEQUENTIAL\_CONSTRAINTfor broad research\-style questions where the answer is an obscure survivor of many heterogeneous public\-data, institutional, technical, or source\-specific constraints\.Conflict resolution\.PreferPARALLEL\_CONSTRAINTfor direct target\-field evaluation over a shared candidate space\. PreferSEQUENTIAL\_CONSTRAINTwhen the question requires maintaining an intermediate state, transferring a ranked or survivor set, mapping to a derived owner/source, or resolving a dependency path before the final answer can be selected\.Few\-shot boundaries\.Example 1\.Question pattern: A top\-five candidate set is first obtained from one source, then carried into later checks or mapped to another owner/source before choosing the final answer\. Label:SEQUENTIAL\_CONSTRAINT\. Reason: the top\-five set is an intermediate search state that must be preserved through downstream evidence\.Example 2\.Question pattern: A named source, table, report, or compact candidate set is given, and each candidate is checked against direct fields; or two small lists are intersected and one direct field is read\. Label:PARALLEL\_CONSTRAINT\. Reason: each condition is a direct predicate on the same candidate variable\.Return format\.Return exactly one JSON object with two fields:"category", whose value is either"SEQUENTIAL\_CONSTRAINT"or"PARALLEL\_CONSTRAINT", and"reason", a 1–3 sentence explanation\.

### A\.9Benchmark Subset Question IDs

We report the exact question subsets used in the main experiments in[Table 20](https://arxiv.org/html/2609.10901#A1.T20)\. The subsets are selected after applying the question\-type classifier in Appendix[A\.8](https://arxiv.org/html/2609.10901#A1.SS8): BrowseComp is used as the sequential source because almost all questions in the full pool are classified as sequential, while WebWalker\-Hard\-English is used as the parallel source because almost all questions in the hard\-English split are classified as parallel\. For BrowseComp, we remove geography\-only direct\-field items and take the first 150 remaining questions by official ID\. For DeepSearchQA, which contains both regimes, we sample 25 classified sequential questions and 25 classified parallel questions\.

Benchmark subsetRegimeQuestion IDsBrowseCompSequentialBrowseComp\-1, BrowseComp\-3, BrowseComp\-6, BrowseComp\-7, BrowseComp\-8, BrowseComp\-9, BrowseComp\-10, BrowseComp\-11, BrowseComp\-12, BrowseComp\-13, BrowseComp\-15, BrowseComp\-17, BrowseComp\-18, BrowseComp\-19, BrowseComp\-20
BrowseComp\-21, BrowseComp\-22, BrowseComp\-23, BrowseComp\-24, BrowseComp\-25, BrowseComp\-26, BrowseComp\-27, BrowseComp\-28, BrowseComp\-29, BrowseComp\-30, BrowseComp\-31, BrowseComp\-32, BrowseComp\-33, BrowseComp\-36, BrowseComp\-37
BrowseComp\-38, BrowseComp\-39, BrowseComp\-40, BrowseComp\-41, BrowseComp\-42, BrowseComp\-43, BrowseComp\-44, BrowseComp\-46, BrowseComp\-47, BrowseComp\-48, BrowseComp\-49, BrowseComp\-50, BrowseComp\-51, BrowseComp\-52, BrowseComp\-54
BrowseComp\-55, BrowseComp\-56, BrowseComp\-57, BrowseComp\-58, BrowseComp\-59, BrowseComp\-60, BrowseComp\-61, BrowseComp\-62, BrowseComp\-63, BrowseComp\-64, BrowseComp\-65, BrowseComp\-66, BrowseComp\-67, BrowseComp\-68, BrowseComp\-69
BrowseComp\-70, BrowseComp\-73, BrowseComp\-75, BrowseComp\-76, BrowseComp\-77, BrowseComp\-78, BrowseComp\-79, BrowseComp\-80, BrowseComp\-81, BrowseComp\-83, BrowseComp\-85, BrowseComp\-86, BrowseComp\-89, BrowseComp\-90, BrowseComp\-91
BrowseComp\-92, BrowseComp\-93, BrowseComp\-94, BrowseComp\-95, BrowseComp\-97, BrowseComp\-99, BrowseComp\-100, BrowseComp\-101, BrowseComp\-102, BrowseComp\-103, BrowseComp\-104, BrowseComp\-105, BrowseComp\-106, BrowseComp\-107, BrowseComp\-108
BrowseComp\-109, BrowseComp\-110, BrowseComp\-111, BrowseComp\-112, BrowseComp\-113, BrowseComp\-114, BrowseComp\-115, BrowseComp\-116, BrowseComp\-117, BrowseComp\-118, BrowseComp\-119, BrowseComp\-120, BrowseComp\-121, BrowseComp\-123, BrowseComp\-124
BrowseComp\-125, BrowseComp\-126, BrowseComp\-127, BrowseComp\-128, BrowseComp\-129, BrowseComp\-130, BrowseComp\-131, BrowseComp\-132, BrowseComp\-134, BrowseComp\-136, BrowseComp\-139, BrowseComp\-141, BrowseComp\-142, BrowseComp\-143, BrowseComp\-145
BrowseComp\-146, BrowseComp\-147, BrowseComp\-149, BrowseComp\-150, BrowseComp\-151, BrowseComp\-152, BrowseComp\-153, BrowseComp\-154, BrowseComp\-155, BrowseComp\-156, BrowseComp\-157, BrowseComp\-158, BrowseComp\-159, BrowseComp\-160, BrowseComp\-161
BrowseComp\-162, BrowseComp\-164, BrowseComp\-165, BrowseComp\-166, BrowseComp\-167, BrowseComp\-168, BrowseComp\-169, BrowseComp\-170, BrowseComp\-171, BrowseComp\-173, BrowseComp\-174, BrowseComp\-175, BrowseComp\-176, BrowseComp\-178, BrowseComp\-180WebWalker\-Hard\-EnglishParallelWebWalkerQA\-Hard\-002, WebWalkerQA\-Hard\-003, WebWalkerQA\-Hard\-004, WebWalkerQA\-Hard\-005, WebWalkerQA\-Hard\-007, WebWalkerQA\-Hard\-009, WebWalkerQA\-Hard\-010, WebWalkerQA\-Hard\-011, WebWalkerQA\-Hard\-012, WebWalkerQA\-Hard\-014, WebWalkerQA\-Hard\-015, WebWalkerQA\-Hard\-016, WebWalkerQA\-Hard\-017, WebWalkerQA\-Hard\-018, WebWalkerQA\-Hard\-019
WebWalkerQA\-Hard\-021, WebWalkerQA\-Hard\-022, WebWalkerQA\-Hard\-023, WebWalkerQA\-Hard\-024, WebWalkerQA\-Hard\-025, WebWalkerQA\-Hard\-026, WebWalkerQA\-Hard\-027, WebWalkerQA\-Hard\-028, WebWalkerQA\-Hard\-029, WebWalkerQA\-Hard\-030, WebWalkerQA\-Hard\-031, WebWalkerQA\-Hard\-032, WebWalkerQA\-Hard\-033, WebWalkerQA\-Hard\-034, WebWalkerQA\-Hard\-035
WebWalkerQA\-Hard\-036, WebWalkerQA\-Hard\-037, WebWalkerQA\-Hard\-038, WebWalkerQA\-Hard\-039, WebWalkerQA\-Hard\-040, WebWalkerQA\-Hard\-041, WebWalkerQA\-Hard\-042, WebWalkerQA\-Hard\-043, WebWalkerQA\-Hard\-044, WebWalkerQA\-Hard\-045, WebWalkerQA\-Hard\-046, WebWalkerQA\-Hard\-047, WebWalkerQA\-Hard\-048, WebWalkerQA\-Hard\-049, WebWalkerQA\-Hard\-050
WebWalkerQA\-Hard\-051, WebWalkerQA\-Hard\-052, WebWalkerQA\-Hard\-053, WebWalkerQA\-Hard\-054, WebWalkerQA\-Hard\-055, WebWalkerQA\-Hard\-056, WebWalkerQA\-Hard\-057, WebWalkerQA\-Hard\-058, WebWalkerQA\-Hard\-059, WebWalkerQA\-Hard\-060, WebWalkerQA\-Hard\-061, WebWalkerQA\-Hard\-062, WebWalkerQA\-Hard\-063, WebWalkerQA\-Hard\-064, WebWalkerQA\-Hard\-065
WebWalkerQA\-Hard\-066, WebWalkerQA\-Hard\-067, WebWalkerQA\-Hard\-068, WebWalkerQA\-Hard\-069, WebWalkerQA\-Hard\-070, WebWalkerQA\-Hard\-071, WebWalkerQA\-Hard\-073, WebWalkerQA\-Hard\-074, WebWalkerQA\-Hard\-075, WebWalkerQA\-Hard\-076DeepSearchQASequentialDeepSearchQA\-004, DeepSearchQA\-083, DeepSearchQA\-095, DeepSearchQA\-131, DeepSearchQA\-257, DeepSearchQA\-268, DeepSearchQA\-300, DeepSearchQA\-316, DeepSearchQA\-349, DeepSearchQA\-370, DeepSearchQA\-403, DeepSearchQA\-450, DeepSearchQA\-517, DeepSearchQA\-521, DeepSearchQA\-568
DeepSearchQA\-605, DeepSearchQA\-609, DeepSearchQA\-680, DeepSearchQA\-719, DeepSearchQA\-759, DeepSearchQA\-763, DeepSearchQA\-828, DeepSearchQA\-848, DeepSearchQA\-875, DeepSearchQA\-885DeepSearchQAParallelDeepSearchQA\-012, DeepSearchQA\-053, DeepSearchQA\-070, DeepSearchQA\-106, DeepSearchQA\-110, DeepSearchQA\-193, DeepSearchQA\-203, DeepSearchQA\-379, DeepSearchQA\-408, DeepSearchQA\-460, DeepSearchQA\-482, DeepSearchQA\-487, DeepSearchQA\-534, DeepSearchQA\-561, DeepSearchQA\-577
DeepSearchQA\-589, DeepSearchQA\-614, DeepSearchQA\-652, DeepSearchQA\-666, DeepSearchQA\-682, DeepSearchQA\-703, DeepSearchQA\-728, DeepSearchQA\-876, DeepSearchQA\-880, DeepSearchQA\-888Table 20:Question IDs used in the main experiments\. BrowseComp IDs follow the official order after filtering geography\-only direct\-field questions; WebWalker\-Hard\-English IDs are the direct\-anchor subset; DeepSearchQA IDs are sampled from the classifier\-assigned sequential and parallel pools\.
### A\.10DAG Construction and Audit Prompts

This appendix summarizes the LLM prompts used by the structured DAG construction pipeline\. The production runner isrun\_query\_subgraph\_v4\.20260314\_032109\.py\. We show the module\-level prompts rather than raw trajectory payloads, which vary by instance\.

Runner Prompt: Q0 Unit DecompositionRole\.Decompose a user question into atomic Q0 units for a search\-trajectory DAG\.Task\.Each unit is one testable constraint or requested field from the question\. Unit types include target type, location, attribute, numeric constraint, answer field, and temporal constraint\.Output\.Return JSON with a list of units, each containingunit\_id,unit\_type, andq0\_span\.Rules\.Be exhaustive; capture all constraints and requested fields; keep units atomic; makeq0\_spana verbatim or near\-verbatim substring of the question; output valid JSON only\.

Runner Prompt: Q0\-to\-Query Match ArbiterRole\.Judge whether a search query operationalizes, addresses, or investigates a specific constraint unit from Q0\.Definition\.Operationalizes means the query is purposefully trying to find information related to that constraint, including through paraphrase, synonym, or a narrower/broader formulation\.Reject\.Surface word overlap alone is not sufficient; queries that share common words without targeting the constraint are rejected\.Output\.For each pair, return JSON withpair\_id,matchas true/false, and a one\-sentence reason\. Output valid JSON only\.

Runner Prompt: Q0 Paraphrase / PK Attribution RuleRole\.Judge whether a token or short phrase in a query is only a paraphrase of information already present in Q0\.Labels\.Return eitherq0\_paraphraseortruly\_new\.Rules\.Judge meaning rather than exact wording\. Small wording changes, tense changes, inflections, and near\-synonyms can still be Q0 paraphrases\. Returntruly\_newif the token adds a more specific fact, a different fact, or a new entity\.

Runner Prompt: Answer Unit DecompositionRole\.Decompose the final answer into atomic answer units for a search\-trajectory DAG\.Task\.Each unit is one independently verifiable factual claim, such as an entity name, date, number, descriptive attribute, or short description\. The original question is provided to identify which claims are relevant\.Output\.Return JSON withanswer\_units; each unit containsunit\_id,claim, andunit\_type\.Rules\.Capture all distinct factual claims; keep each claim short and verifiable; output valid JSON only\.

Runner Prompt: Answer Support MatchRole\.Judge whether a query’s retrieved evidence supports a normalized answer unit\.Input\.The prompt receives the original question, the final answer’s supporting analysis, and candidate pairs of answer unit and query evidence\.Accept\.Marksupport=trueonly when the evidence excerpt materially supports the answer unit, including via alias, paraphrase, or short cross\-sentence inference\.Reject\.Reject topical overlap, overlapping words without claim support, and claims asserted only in the answer reasoning rather than in query evidence\.Output\.Return JSON verdicts withpair\_id,supports,confidence,reason, and the best short supporting evidence sentence\.

Runner Prompt: Query\-to\-Query / PK / Failure\-Response Edge AttributionRole\.Act as a Query\-DAG edge classifier for one search turn\. Output only edges whose target is a query issued in the current turn\.Input\.The prompt receives Q0 as background, prior query index, turn\-level status, current reasoning block split into sentence IDs, current\-turn queries, and a hint chart containing token statuses \(Q0\_ONLY,Q0\_SEEN,SEEN,NEW\), used signals, reasoning sentence hits, and provenance windows from earlier snippets or visits\.Allowed edges\.Evidence\-use edges from prior query to current query are allowed only when a used signal has provenance attributed to that prior query or an explicit reasoning sentence ties the signal to it\. Prior\-knowledge edges are allowed only when a signal is new, appears in reasoning support, and has no provenance\. Soft failure\-response edges are allowed only when the reasoning explicitly states that a prior query was insufficient and the current query fills that gap\.Hard gates\.Every emitted edge must cite a reasoning sentence ID or provenance window\. Do not output Q0 edges, same\-turn edges, deterministic hard failure\-response edges, hallucinated sources, or PK fallback when provenance exists\.Parent selection\.Use informative tokens only, ignore generic search\-template tokens, prefer visits over snippets, and keep the minimal parent set whose union covers the informative used signals\. Each retained parent must explain at least one signal not already covered by another parent\.Output\.Return JSON withedgesandno\_source\_found\. Each edge includes source, target, edge kind, optional failure subtype, covered signals, evidence, and confidence\.

Constraint\-Unit Annotation Rules for BCG and DCCGoal\.Produce semantic constraint units used by the constraint\-grounding metrics, then determine which query nodes deploy each unit\.Unit creation\.We first decompose the question into semantic units such as entity, attribute, time, role, location, source, ranking, threshold, or requested answer field\. The decomposition is LLM\-assisted and manually reviewed\.Query deployment\.A query is marked as deploying a unit by a rule\-based lexical overlap test after basic normalization \(lowercasing, singularization, stopword/generic\-term removal\)\. Generic\-word overlaps are ignored, and for multi\-token units numeric\-only or weak single\-token overlaps do not count without distinctive non\-numeric support\.Metric use\.For sequential questions, BCG \(backbone constraint share\) counts whether these unit deployments fall on the answer backbone rather than side branches\. For parallel questions, DCC \(direct constraint coverage\) counts how many distinct question units are covered by direct answer\-supporting queries\.

Outlier Mechanism Judge Prompt \(§[5\.5](https://arxiv.org/html/2609.10901#S5.SS5)\)Role\.Label mechanisms for structural metric outliers in search\-agent DAG analysis\.Input\.The judge receives the outlier type, benchmark, regime, model, case ID, correctness, metric values, question, gold answer, model prediction, final answer from messages, DAG summary, transcript excerpt, and, when available, the full or pruned raw trajectory and raw DAG item\.Labels\.Use exactly one main label:WRONG\_TARGET\_BINDING,SEMANTIC\_SPECIFICITY\_FAILURE,SHORTCUT\_SUCCESS,OVER\_SEARCH\_SUCCESS, orUNCERTAIN\.Outlier constraints\.High\-score wrong cases can only be wrong\-target binding, semantic\-specificity failure, or uncertain\. Low\-score correct cases can only be shortcut success, over\-search success, or uncertain\.Rules\.Base the label on the trajectory/messages and DAG first\. Use metric values only for orientation\. For shortcut success, also markinternal\_knowledge,open\_web\_shortcut,mixed, orunclear\.Output\.Return one JSON object withmechanism\_main,shortcut\_subtype,confidence,needs\_human\_check,rationale,evidence\_basis, andambiguity\_notes\. Setneeds\_human\_check=trueif confidence is below 0\.70, if transcript/DAG context is missing, or if two mechanisms are similarly plausible\.

### A\.11Structural Profiles Across Question Types and Agents

Figure 8:Boxplots of depth and width metrics for sequential and parallel constraint questions\.Figure 9:Boxplots of three trajectory\-level metrics for sequential and parallel constraint questions: multi\-incoming node count, efficiency ratio, and evidence\-reuse span\.#### Sequential constraints deepen the DAG and increase branching\.

Sequential\-constraint questions require resolving intermediate entities before later constraints become interpretable\. This tends to produce longer evidence chains and more branching than parallel\-constraint questions, where several constraints can often be checked against a common candidate or source\. The following profile metrics show where this additional structure appears\.

#### Sequential questions reduce query efficiency\.

*Query efficiency*measures what fraction of the agent’s search queries ultimately contribute to the answer, as opposed to being spent on searching candidates that are later discarded, measured by the ratio of queries that lie on a path leading to the final answer to the total number of queries issued\. Across all models, efficiency drops noticeably when questions involve sequential constraints that require resolving more latent entities and verifying more constraints\. The remaining queries are not wasted at random: they concentrate on two recognizable activities, generating candidate entities by trial and error, and subsequent verification of candidates that turn out not to satisfy every constraint\.

#### Sequential questions require more multi\-source synthesis\.

The set of incoming edges to a query node tells us how that query was formulated: a node with a single parent inherits its content from a single prior query’s retrieval result, while a node with multiple parents synthesizes information gathered across several earlier queries\. We therefore count, for each trajectory, the number of query nodes with two or more incoming edges—queries that aggregate evidence rather than extend a single line of inquiry\. On sequential\-constraint questions, the agent increasingly issues queries that fuse multiple constraints or cross\-check candidate entities against several pieces of prior evidence at once, rather than pursuing one constraint at a time\.

#### Evidence is reused farther in parallel\-constraint questions\.

In parallel\-constraint trajectories, evidence retrieved by a query is attributed to later queries throughout a much larger fraction of the remaining search; in sequential\-constraint trajectories, retrieved evidence is usually attributed only to the next few turns before the agent moves on to the next sub\-problem\. We quantify this with the*normalized evidence\-reuse span*of each parent–child edgeu→vu\\rightarrow v:

turn​\(v\)−turn​\(u\)total\_turns−turn​\(u\),\\frac\{\\text\{turn\}\(v\)\-\\text\{turn\}\(u\)\}\{\\text\{total\\\_turns\}\-\\text\{turn\}\(u\)\},the gap in search turns expressed as a fraction of the trajectory still available afteruuwas issued\. The parallel group has a much higher mean and median than the sequential group\.

### A\.12Accuracy\-Metric Ablations

This appendix reports the quantitative checks behind the three\-module process analysis in Section[5\.4](https://arxiv.org/html/2609.10901#S5.SS4)\. All metrics are oriented so that larger values should rank correct trajectories above incorrect trajectories: topology and grounding enter positively, while prior\-knowledge risk enters with the negative sign used by the fixed additive score\. BrowseComp is evaluated as the sequential regime, WebWalker\-Hard as the parallel regime, and DeepSearchQA is split into sequential and parallel subsets\.

Table 21:Single\-module diagnostic results, macro\-averaged across models\. The PK column reports the signed PK\-risk signal used by the additive score, not the raw amount of PK\. The table shows that individual modules are associated with answer outcomes, but also that no single module is uniformly sufficient across regimes\.Table 22:Stage\-wise additive\-score ablation\. Each cell reports AUC / AP, macro\-averaged across models\. The main\-text table reports AUC and incremental gains; this table adds the AP values\.Table 23:Per\-model numerical values underlying[Table 2](https://arxiv.org/html/2609.10901#S5.T2)\. Every AUC is computed within one fixed model and benchmark\-regime, comparing only that model’s correct and incorrect trajectories; no cross\-model trajectory pair enters an individual AUC\. The columns report cumulative held\-out AUC after adding the three modules\. For sequential regimes, the modules are answer\-backbone concentration, backbone constraint share, and sequential PK penalty; for parallel regimes, they are answer\-path directness, direct constraint coverage, and parallel PK score\. Acc\. is the empirical answer accuracy for that benchmark\-regime and model\.
### A\.13Score Calibration and Auxiliary Outcome Prediction

AUC evaluates the association between the behavioral diagnostics and answer outcomes at the ranking level\. As an auxiliary outcome\-risk check, we also ask whether the fixed DAG\-derived score produces interpretable score bands and whether a held\-out threshold preserves this association at the trajectory level\. We compute composite DAG\-derived scores out\-of\-fold under the same question\-held\-out protocol as the main result\. For score bands, we sort trajectories by the composite score within each benchmark\-regime and report empirical accuracy in score tertiles\. For threshold prediction, each benchmark\-regime/model learns a threshold on training questions that maximizes balanced accuracy, then applies it to held\-out questions\.

Table 24:Answer accuracy by composite DAG\-derived score tertile within each benchmark\-regime\. Values are percentages\.Table 25:Top\- and bottom\-quintile accuracy by model and regime\. Values are percentages\. The score separates high\-risk and low\-risk trajectories for every model, but the absolute accuracy of high\-score sequential trajectories remains model\-dependent\.Table 26:Auxiliary held\-out outcome\-risk prediction from the fixed DAG\-derived score within each benchmark\-regime\. Values are percentages\. Thresholds are selected only on training questions within each benchmark\-regime/model and then evaluated on held\-out questions\. AggregateF1F\_\{1\}is70\.570\.5for sequential and78\.078\.0for parallel questions\.These auxiliary results clarify how the behavioral score relates to outcomes\. High\-score bands are much more accurate than low\-score bands, so the score can support trajectory\-level risk assessment and selective review without serving as a standalone correctness judgment\. At the same time, sequential precision is lower because a coherent answer\-support path can still bind to the wrong target; this behavior–outcome divergence is analyzed in Section[5\.5](https://arxiv.org/html/2609.10901#S5.SS5)\.

### A\.14Non\-DAG LLM Judge Baselines

As an auxiliary outcome\-risk comparison, we compare the thresholded DAG\-derived score with two non\-DAG LLM judges\. The first is an outcome\-oriented baseline that asks GPT\-5\.2 to judge whether the trajectory’s final answer is correct from the full trajectory\. This tests whether the DAG adds value beyond having a strong model summarize the entire log\. The second is an ordered\-query\-list baseline that gives the judge only the original question, final answer, and chronological query list, with retrieved evidence, page visits, reasoning, and DAG edges removed\. This tests whether query order alone is enough without explicit dependency structure\. Table[27](https://arxiv.org/html/2609.10901#A1.T27)gives the pooled comparison\. Macro\-F1F\_\{1\}weights correct and incorrect trajectories equally, while positiveF1F\_\{1\}treats correct trajectories as the positive class\.SearchAtlasimproves over the full\-trajectory judge by3\.83\.8accuracy and6\.76\.7macro\-F1F\_\{1\}points, and over the ordered\-query\-list judge by9\.99\.9and16\.416\.4points\. To make the more detailed comparison with thresholded DAG\-derived predictions direct, AUC and AP in Table[28](https://arxiv.org/html/2609.10901#A1.T28)are computed from the binary predictions only\.

Table 27:Pooled trajectory\-level comparison on all 1,350 trajectories\. Values are percentages\.Full\-Trajectory GPT\-5\.2 Correctness Judge PromptRole\.You are a trajectory\-structure correctness judge for a web\-search research agent\.Task\.Predict whether the agent’s final answer is correct using only the information inside the provided trajectory and the structure of the agent’s search/reasoning process\.Hard restrictions\.Do not use your own world knowledge, memory, or web knowledge\. Do not solve the original question yourself\. Treat all facts as unknown unless supported by the trajectory text\. The gold answer is not provided\.Allowed signals\.Use structural evidence such as whether constraints were searched, whether evidence was found, whether the final answer is grounded in cited/tool evidence, unresolved contradictions, hallucinated leaps, failed searches, or unsupported candidate switches\. Do not reward verbosity\.Binary decision\.Choose exactly one final label:correctorincorrect\. Do not outputuncertain\. If evidence is incomplete or ambiguous, still make the best binary prediction from trajectory structure alone and use confidence to express uncertainty\.Output\.Return JSON only with fields:prediction,confidence,final\_answer\_supported,all\_question\_constraints\_checked,uses\_only\_trajectory\_evidence,gold\_answer\_present\_in\_prompt,structural\_signals, andrationale\.User payload\.Task ID; input file; agent; original question; agent final answer to judge; search transcript, introduced as “the only evidence you may use”; return JSON only\.

Table 28:Trajectory\-level comparison between the thresholded DAG\-derived score and non\-DAG LLM\-judge baselines on all three benchmarks \(BrowseComp 150 questions sequential, WebWalker\-Hard 70 questions parallel, DeepSearchQA 25 sequential and 25 parallel questions; all crossed with five agents\)\. Values are percentages exceptNN\. Precision, recall, andF1F\_\{1\}treat correct trajectories as the positive class\. AUC and AP in this table use binary predictions so that all rows share the same thresholded\-decision protocol\.Ordered\-Query\-List GPT\-5\.2 Judge PromptRole\.You are a trajectory\-structure correctness judge for a web\-search research agent, but you may only inspect the ordered query list\.Task\.Predict whether the agent’s final answer is correct using the original question, the agent’s final answer, and the chronological list of issued search queries\.Unavailable information\.Retrieved search results, visited pages, reasoning text, citations, and DAG edges are deliberately removed\. Do not infer hidden evidence from query wording alone\.Allowed signals\.Use only coarse query\-list signals such as whether the agent searched for the stated constraints, whether the query sequence appears to refine or drift from the task, whether key entities in the final answer appear in the query list, and whether the query list looks sufficient or under\-specified\.Binary decision\.Choose exactly one final label:correctorincorrect\. If the query list is insufficient to tell, still make the best binary prediction and use confidence to express uncertainty\.Output\.Return JSON only withprediction,confidence,query\_coverage,final\_answer\_appears\_searched,query\_sequence\_sufficiency,structural\_signals, andrationale\.

Table[29](https://arxiv.org/html/2609.10901#A1.T29)reports the full ordered\-query\-list results from the confidence\-ranked judge score\. The baseline is conservative: it attains high precision because it predicts relatively few trajectories as correct, but its recall is low across both sequential and parallel regimes\. Thus, chronological query text can identify a small set of obvious successes, but without dependency edges it misses many trajectories whose final answers are supported by retrieved evidence\.

Table 29:Ordered\-query\-list judge results\. The benchmark\-regime rows are per\-model macro averages within each benchmark\-regime\. The All row is pooled over all 1,350 trajectories\. AUC and AP in this table use the judge’s confidence\-oriented score, unlike the binary\-prediction AUC/AP in Table[28](https://arxiv.org/html/2609.10901#A1.T28)\. Values are percentages exceptNN\.Table 30:Per\-model ordered\-query\-list judge results\. AUC and AP use the judge’s confidence\-oriented score\. Values are percentages exceptNN\.#### Trajectory\-wide versus DAG\-localized constraint grounding\.

A trajectory\-wide coverage baseline records the fraction of semantic question constraints deployed by at least one query anywhere in the run\. It does not use dependency edges or distinguish answer\-supporting queries from side branches\. We compare it with the regime\-specific DAG\-derived grounding diagnostic computed from the same constraint units: backbone constraint share for sequential questions and direct constraint coverage at the answer\-support frontier for parallel questions\.

Table 31:Constraint\-grounding localization ablation\. Each score is AUC / AP, macro\-averaged across agents under question\-held\-out evaluation\. The trajectory\-wide baseline counts constraint coverage anywhere in the query sequence; DAG\-localized grounding restricts the signal to the answer backbone \(sequential\) or answer\-support frontier \(parallel\)\.Localizing constraint deployment improves both AUC and AP in both regimes\. The larger BrowseComp difference also shows why repeated or scattered mentions of question constraints should not receive the same credit as constraints integrated into the answer\-reaching evidence path\.

#### Trajectory\-wide versus answer\-localized prior\-knowledge reliance\.

We construct a matched trajectory\-wide PK baseline from the same generated DAGs and PK attribution decisions\. It counts allPK→q\\mathrm\{PK\}\\to qedges in the trajectory, adds an indicator for an eligiblePK→A\\mathrm\{PK\}\\to Aedge, and divides by the total number of queries\. Unlike the current parallel PK score, it does not use answer reachability\. We then replace only the PK term in the full additive score: topology, grounding, trajectories, agent\-wise evaluation, semantic signs, and question\-held\-out folds remain fixed\.

Table 32:Matched PK\-localization ablation\. Each score is AUC / AP, macro\-averaged across agents\. Both columns retain identical topology and grounding terms; only the PK term is replaced\. PositiveΔ\\DeltaAUC favors the current answer\-specific/localized PK term; deltas are computed from unrounded values\.The complete score is stronger with the answer\-specific/localized PK term in all four benchmark\-regimes\. The parallel rows provide the direct DAG\-localization test because the current parallel score restricts PK to the answer\-supporting subgraph\. In the sequential rows, the current term is an answer\-specific pre\-answer\-context fallback check, so those rows establish the value of answer specificity but should not be interpreted as a graph\-traversal ablation\. PK\-only performance is not uniformly stronger under localization; the result therefore supports localized PK as a complementary term alongside topology and grounding, rather than as a standalone correctness score\.

Table 33:Drop\-one module ablations\. Each cell reports AUC / AP\. Removing any module usually reduces the complete three\-module score, supporting the complementary role of topology, constraint grounding, and prior\-knowledge reliance\.The ablations support two conclusions\. First, topology is a useful first\-order signal, but it is not a complete account of answer\-support behavior\. Constraint grounding and PK reliance surface outcome\-associated distinctions that topology alone cannot see\. Second, the contribution of each auxiliary module is regime\-dependent: grounding is especially strong on sequential DeepSearchQA, while PK risk provides a large gain for the parallel WebWalker and DeepSearchQA subsets\. Within the DeepSearchQA parallel split, TYDP\-Qwen3 is the one model for which adding grounding slightly hurts AUC before the PK module is added; this is consistent with the role of grounding as a complementary rather than standalone signal\.

### A\.15Raw\-Log Process Baselines

This appendix tests whether the DAG\-derived diagnostics are merely proxies for coarse trajectory effort, such as how many queries an agent issued, how many pages it visited, how long the trajectory was, or how often it repeated searches\. These raw\-log features carry modest accuracy\-associated signal, confirming that search effort is not irrelevant\. However, they conflate productive search with unproductive drift: the same increase in length or breadth can reflect either necessary evidence gathering or failed exploration\. The DAG\-derived diagnostics consistently improve over them because they evaluate the organization of evidence rather than the amount of search\.

Table 34:Raw\-log baseline features\. These features are computed directly from the trajectory log and do not use the recovered DAG\.We evaluate the log\-only baselines with the same grouped 5\-fold cross\-validation protocol by question ID\. The compact log\-only baseline is a ridge logistic regression over the four features in[Table 34](https://arxiv.org/html/2609.10901#A1.T34)\. The DAG\-derived baseline uses the fixed additive score from Section[5\.4](https://arxiv.org/html/2609.10901#S5.SS4)\.

Table 35:Raw\-log process baselines versus the fixed DAG\-derived score\. Each score is AUC / AP under question\-held\-out evaluation\. “Best single log\-only” reports the strongest individual raw\-log feature in each split, while “Compact log\-only” combines all four raw\-log features\. The all\-regime rows are benchmark\-macro summaries\.