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

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 $348$ instances spanning $19$ business domains, $10,617$ atomic claims spanning enumerations, numerical values, and factual descriptions (average $30.5$ per instance), and $2,411$ dependency edges (average $6.9$ per instance), with mean Width $45.9$, Depth $16.3$, and Members $49.7$. 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.