acceptodds
Under review as a conference paper at ICLR 2027

DEEPSEARCHDAG: A DAG-STRUCTURED BENCHMARK FOR NODE-LEVEL EVALUATION OF DEEP SEARCH AGENTS

Abstract

Existing benchmarks for evaluating search agents predominantly verify only the final answer while treating intermediate sub-problems as a black box, providing no structural signal for distinguishing well-supported coverage from a potential lucky hit. Moreover, they typically involve a single target entity or a homogeneous set, lacking the multi-entity heterogeneity of real-world search tasks; benchmarks that jointly stress both search depth and width remain scarce. We present DeepSearchDAG (DSD), a DAG-structured benchmark built on a real-world online business dataset, decomposing queries involving multiple heterogeneous entities into atomic sub-problems connected by dependency edges, enabling node-level evaluation of both depth and width. DSD places representative search-agent benchmarks in a common node-level view and extends it to checked DAG dependencies. We propose NodeF1 for final-answer coverage and a trajectory-aware DSD-Score for tool-augmented search agents. Its Prerequisite Edge Score (PES) measures whether recorded tool trajectories follow annotated prerequisite edges. The dataset comprises instances spanning business domains, atomic claims spanning enumerations, numerical values, and factual descriptions (average per instance), and dependency edges (average per instance), with mean Width , Depth , and Members . Experiments show that state-of-the-art agent frameworks powered by frontier LLMs achieve low success rates on DSD, while trajectory-aware PES complements final-answer coverage with a prerequisite-edge execution signal.

Primary area:
datasets and benchmarks
Keywords:
Deep Search, Agent Evaluation, Benchmark, DAG-Structured Query Decomposition, Node-Level Evaluation

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_tAv5OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper introduces DeepSearchDAG, a benchmark for evaluating complex search tasks through claim-level annotations and dependency DAGs. It contains 348 real-world business queries, 10,617 atomic claims, and 2,411 dependency edges. The authors propose NodeF1 to measure final-answer coverage and a trajectory-aware Prerequisite Edge Score (PES) to evaluate whether search agents follow annotated information dependencies. Experiments across eight backbone models and three agent frameworks reveal substantial limitations in both answer coverage and prerequisite-linked search behavior.

Critical strengths
  1. Fine-grained benchmark design. DSD evaluates complex search tasks at the claim level, providing more informative feedback than final-answer-only benchmarks.
  2. Extensive benchmark evaluation. The paper evaluates 32 model-framework configurations and includes human annotation procedures, judge consistency analysis, and detailed error diagnostics.
Critical weaknesses
  1. Unclear validity of prerequisite-edge scoring. PES rewards adherence to annotated dependencies, but valid search strategies may retrieve information through alternative paths. The paper lacks direct validation that higher PES reflects better search reasoning rather than conformity to a predefined structure.
  2. Limited independence from answer accuracy. NodeF1 and PES are highly correlated across configurations (Pearson r = 0.988). The additional diagnostic value of PES remains insufficiently established.
  3. Inconsistent fan-in evaluation. Verify nodes are defined as requiring multiple evidence branches, yet the Complete Success Rate requires only one incoming fan-in edge to be satisfied. This appears inconsistent with the intended evaluation of multi-source verification.
  4. Potential overestimation of answer coverage. Enumeration claims are considered fully covered when their set-level F1 reaches only 0.60. This binary threshold may reward incomplete lists and obscure meaningful differences in information coverage.
  5. Limited validation of evaluation reliability. Although the paper reports high LLM-judge agreement, cross-judge DSD-Score varies by 0.066 on the tested subset. Independent human validation of PES decisions is not provided.
  6. Questionable interpretation of structural depth. The reported Depth metric includes artificial ordering edges between claims within the same milestone. Consequently, it may reflect claim serialization rather than genuine search dependency depth.
  7. The pictures in this paper need to be polished.
Questions for authors
  1. PES validity. How do the authors verify that annotated prerequisite edges represent necessary information dependencies rather than one possible search strategy? Could they evaluate PES against human judgments of search-process quality?
  2. Incremental value of PES. Given the strong correlation between NodeF1 and PES (r = 0.988), what additional information does PES provide beyond answer accuracy? Could the authors analyze cases where the two metrics disagree substantially?
  3. Fan-in consistency. Why does the Complete Success Rate require only one incoming edge for a fan-in verification node, while the DAG formulation emphasizes multi-source verification and PES scores each incoming edge separately?
  4. Metric sensitivity. How sensitive are model rankings to the enumeration threshold of 0.60 and the DSD-Score weights of 0.7/0.3? Could the authors report results using stricter coverage criteria?
  5. Judge reliability. How well do LLM-generated PES judgments agree with independent human assessments? Does the observed cross-judge variation affect model rankings?
  6. Structural depth. How much of the reported Depth comes from actual dependency edges versus artificial within-milestone ordering? Would the benchmark retain its claimed depth advantage under a dependency-only definition?
Reviewer_toXEOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

DeepSearchDAG introduces 348 real-world Chinese business queries across 19 domains, annotated with 10,617 typed claims and 2,411 milestone-level dependency edges. It evaluates answer coverage using NodeF1 and combines this with a trajectory-based Prerequisite Edge Score (PES) to assess dependency execution. Experiments cover eight backbone models in direct-answer and three agent-framework settings, supplemented by judge-repeatability and cross-judge sensitivity analyses. The reported results show substantial remaining difficulty, with complete success reaching at most 4.2% on the multi-claim subset.

Critical strengths

The dataset captures complex information needs involving multiple entities and heterogeneous answer types. Its detailed claim annotations and dependency structures could help identify where search agents fail, providing more actionable feedback than final-answer correctness alone. The staged annotation and review process represents substantial effort.

The answer-evaluation pipeline makes several sensible design choices, including type-specific checking and blind extraction with anaphora resolved from the agent’s own response. The experiments span multiple frameworks and backbones, and the repeated evaluations with different judges provide useful evidence about evaluator stability and sensitivity.

Critical weaknesses

The central dependency metric lacks a consistent, validated interpretation. Section 1.2 describes response-level coverage, while Section 4.3 requires ordered tool events and observable reuse of upstream results. The paper does not adequately specify or validate how this reuse is detected. Edge semantics are also inconsistent: Appendix H excludes aggregation and defines fan-in as independent corroboration, whereas Appendices I.1–I.2 use fan-in for comparisons requiring multiple inputs. SR nevertheless accepts just one incoming edge. These distinctions determine which executions receive credit and need to be resolved before PES can support reliable conclusions about search quality.

The reported difficulty is confounded by evaluation restrictions. Appendix G.2 truncates responses to 10,000 characters, potentially removing correct content from comprehensive reports, but provides no analysis of the resulting score changes. Appendix I.4 also includes information obtained through QR-code scanning and access within WeChat, while the evaluated agents receive Google Search and an HTML-based webpage tool. The experiments do not quantify how much failure comes from discarded output or unavailable access. This matters especially for complete success, where a single affected claim can make an otherwise successful instance fail.

Questions for authors

Which dependency-scoring procedure produced the reported results? Please provide a worked trajectory showing how upstream-result reuse is identified, together with agreement against human judgments of those decisions.

How are alternative corroborating sources distinguished from jointly necessary inputs? Why is one satisfied incoming edge sufficient for SR in the multi-input comparison examples, and would resolving this inconsistency change the results?

What fraction of responses loses relevant content under the 10,000-character limit, and what fraction of claims requires access unavailable through the supplied tools? Do the main conclusions and framework rankings hold with full-response evaluation on a tool-accessible subset?

Reviewer_ZM4POpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper introduces DeepSearchDAG, a benchmark for evaluating search completeness and the search process in real-world business tasks. It decomposes queries into atomic claims and forms a dependency DAG. The benchmark measures final-answer coverage, and evaluates whether the search trajectory follows the annotated dependencies.

Critical strengths

•⁠ ⁠Checking intermediate claims and their dependencies in a search process provides a way to analyse search behavior beyond final-answer accuracy.

•⁠ ⁠The benchmark contains real-world queries across 19 business domains. The paper also evaluates three agent frameworks with eight backbone models providing a broad comparison of current systems.

Critical weaknesses

•⁠ ⁠The evaluation uses LLMs for claim extraction, context matching and trajectory-edge satisfaction. While there is a multi-judge study, there is no comparison with human judgements to establish the accuracy of LLM extractions and evaluation.

•⁠ ⁠An agent can take an alternative reasoning and search route to reach the correct answer. In this case, it may explore claims outside the reference DAG or skip some paths in the DAG. PES may therefore penalize valid search paths that do not follow the reference DAG.

•⁠ ⁠There is very limited analysis of the main results in section 5. The results also show that NodeF1 and PES seems to be strongly correlated so it doesnt show the need for having both metrics. A qualitative analysis of cases with similar answer coverage but varying PES would demonstrate the value of measuring dependency coverage.

Questions for authors

See weaknesses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.