DeepSearchQA: Bridging the Comprehensiveness Gap for Deep Research Agents

AI summary

Overview

Research area: Evaluation of autonomous web agents for deep research / multi-step information-seeking tasks (Natural Language Processing).

Technical level: Advanced. The paper assumes familiarity with information retrieval metrics (precision, recall, F1), agent architectures, and LLM-as-a-judge evaluation pipelines, though the core argument is accessible.

Scope: The paper introduces DeepSearchQA, a 900-prompt benchmark across 17 fields that evaluates agents on producing exhaustive, verified answer sets rather than single answers, and reports results for ten state-of-the-art models.

What This Paper Is About

Most agent benchmarks ask a single question with a single correct answer, which rewards finding one needle in a haystack and ignores the kind of research where a user needs a complete list ("all countries satisfying X, Y and Z"). The authors call this blind spot the Comprehensiveness Gap and argue that existing benchmarks therefore fail to measure systematic collation of fragmented sources, de-duplication/entity resolution, and reasoning about when a search is finished. Their goal is a benchmark whose scoring forces agents to balance recall (finding everything) against precision (including nothing that does not belong).

Key Contributions

1. A new benchmark, DeepSearchQA, consisting of 900 hand-crafted prompts paired with ground-truth answer sets, spanning 17 fields and anchored to time-stamped or static sources (e.g., "According to the 2020 Census…") to limit ground-truth drift.
2. A task taxonomy that separates three cognitive demands — Structured Retrieval ("The Search"), Context Management ("The Assembly"), and Logical Reasoning ("The Thinker") — each illustrated with easy examples from prior benchmarks versus hard DeepSearchQA examples.
3. A set-based evaluation methodology combining continuous information-retrieval metrics (Precision, Recall, F1-Score) with four disjoint categorical outcomes: Fully Correct, Fully Incorrect, Partially Correct, and Correct with Extraneous Answers (the "hedging" failure mode).
4. A public leaderboard on Kaggle with independently run evaluations, plus an empirical study of ten state-of-the-art agent and reasoning models that identifies distinct failure modes such as premature stopping, hedging, quantitative estimation error, and tool-call limitations.

Main Findings

• Even the best systems leave substantial headroom. The Gemini Deep Research Agent scores an F1 of 81.90 and 66.09% Fully Correct; GPT-5 Pro High Reasoning scores 78.98 F1 and 65.18% Fully Correct. No model solves the benchmark.
• Agents beat standalone reasoning models. Deep Research agents outperform their standalone model counterparts, which the authors attribute to the iterative loop being necessary to close the Comprehensiveness Gap.
• Catastrophic-failure rates differ even when accuracy is comparable. Although their Fully Correct rates are statistically comparable (66.09% vs. 65.18%), Gemini Deep Research Agent reports the lowest Fully Incorrect rate at 9.95% versus 14.13% for GPT-5 Pro High Reasoning.
• There is a sharp reasoning threshold, not a smooth curve. Gemini 2.5 Flash reaches an F1 of 42.99 — roughly half the leader — and its Fully Incorrect rate spikes to 45.27%, nearly five times the SOTA agent's rate. Claude 4.5 Haiku has the highest Fully Incorrect rate in the table at 71.00% with an F1 of 22.24.
• Mid-tier agents degrade quickly. o3 Deep Research reaches 44.24% Fully Correct and o4 Mini Deep Research 40.36%, with Fully Incorrect rates rising to 20.09% and 24.19% respectively.
• More test-time compute helps substantially. Increasing the number of samples raises the Fully Correct rate from 67.18% at n=1 to 74.51% at n=2, 81.72% at n=4, and 85.71% at n=8.
• A persistent "Last Mile Problem." The gap between F1 and strict Fully Correct is roughly 15 points for Gemini Deep Research Agent (81.90 F1 vs. 66.09% Fully Correct) and around 13 points for GPT-5 Pro High Reasoning, driven by under-retrieval (missing long-tail entities) and over-retrieval (perfect recall but hallucinated extras).
• Distinct failure modes appear at different pipeline stages. Worked examples show Gemini failing to synthesize an estimate ("Even a conservative estimate places this in the tens of millions… Total Estimated Tonnage"), GPT-5 Pro halting after finding an Excel file it says it cannot open, and GPT-5 Pro failing to filter a correctly-retrieved author list according to the prompt's constraints.
• All answers are graded by an LLM judge — Gemini 2.5 Flash used zero-shot with the prompt template in Appendix A — and results were independently evaluated by Kaggle.

Methodology in Plain English

For each prompt the agent submits a set of answers, and the benchmark compares that set to a ground-truth set regardless of ordering or wording, using a judge to decide semantic equivalence item by item. A perfect response contains every ground-truth item and nothing else, which turns the task into a precision/recall trade-off: cast too wide a net and precision drops, stop too early and recall drops. Tasks are designed as causal chains, where each step depends on the previous one, so an agent must plan multiple searches, hold context across them, merge fragmented findings, and decide when further searching is pointless. Ground truth was validated with a three-phase protocol: three reviewers independently researched each answer, cross-referenced it against the curator's ground truth, and any discrepancy triggered a conflict-resolution phase; ambiguous prompts were filtered out. The authors deliberately evaluate only the final answer set, treating the agent as a black box, and compute F1 per prompt before averaging across the evaluation set.

Why This Matters

The paper shifts agent evaluation from "can it find an answer" to "can it exhaustively map an information landscape," which is the actual shape of many professional research requests. It also gives a diagnostic vocabulary — under-retrieval versus hedging versus stopping-criterion failure — that points architecture research at specific bottlenecks rather than a single aggregate score.

Real-world applications reflected in the benchmark's example prompts:

• Public health research, such as identifying countries meeting combined population, life-expectancy and immunization thresholds using World Bank data.
• Regulatory and safety analysis, such as finding US states meeting consecutive-year fatality-rate criteria according to NHTSA data.
• Market and financial analysis, such as intersecting annual stock-price growth thresholds with national GDP growth across multiple data sites.
• Personal decision support and historical/biographical research, such as filtering cities by house price, green space, employment and clean-air-zone status, or enumerating botanists in a library archive who never held a named professorship.

Industry relevance: Because evaluation is outcome-based and does not constrain architecture, the benchmark can be used to compare proprietary agent stacks; the authors note the leaderboard remains open to new model submissions and that Kaggle performs evaluation. The scaling results also carry a direct commercial message: cheaper models are not a linear cost trade-off but a step-function drop in reliability for research tasks.

Future Directions

• Add process-based metrics. Categorizing agent trajectories (pages visited, query sequences) while keeping scoring outcome-based would help distinguish retrieval failures from reasoning and synthesis errors, and would offset the fact that black-box scoring cannot tell a correct method from a lucky one.
• Introduce dynamic, time-sensitive questions whose ground truth is volatile, such as listing current members of a parliamentary committee, to test real-time retrieval that the paper's static-web assumption currently excludes.
• Move to weighted relevance scoring. Distinguishing "core" from "peripheral" answers would allow rank-aware metrics such as normalized Discounted Cumulative Gain (nDCG).
• Drive new agent capabilities. The authors argue that high performance will require methodical tree- or graph-based exploration instead of opportunistic keyword search, robust entity resolution and de-duplication across heterogeneous sources, and dynamic stopping criteria that reason about when a retrieved set is likely exhaustive.

The paper also flags dataset maintenance as an open issue: source websites can be removed or altered, so periodic manual review and updates are needed.

Target Audience

Researchers and engineers building or evaluating autonomous web agents and deep-research systems; benchmark designers interested in set-based rather than single-answer evaluation; and practitioners who need to know how much to trust current agentic research tools, including teams deciding whether cheaper models are adequate for multi-step retrieval workflows. Readers focused on long-form generation, trajectory-level agent diagnostics, or non-verifiable subjective tasks will find the benchmark's scope narrower than their interests.

Authors’ abstract

We introduce DeepSearchQA, a 900-prompt benchmark for evaluating agents on difficult multi-step information-seeking tasks across 17 different fields. Unlike traditional benchmarks that target single answer retrieval or broad-spectrum factuality, DeepSearchQA features a dataset of challenging, handcrafted tasks designed to evaluate an agent's ability to execute complex search plans to generate exhaustive answer lists. This shift in design explicitly tests three critical, yet under-evaluated capabilities: 1) systematic collation of fragmented information from disparate sources, 2) de-duplication and entity resolution to ensure precision, and 3) the ability to reason about stopping criteria within an open-ended search space. Each task is structured as a causal chain, where discovering information for one step is dependent on the successful completion of the previous one, stressing long-horizon planning and context retention. All tasks are grounded in the open web with objectively verifiable answer sets. Our comprehensive evaluation of state-of-the-art agent architectures reveals significant performance limitations: even the most advanced models struggle to balance high recall with precision. We observe distinct failure modes ranging from premature stopping (under-retrieval) to hedging behaviors, where agents cast an overly wide net of low-confidence answers to artificially boost recall. These findings highlight critical headroom in current agent designs and position DeepSearchQA as an essential diagnostic tool for driving future research toward more robust, deep-research capabilities.