Summary (Overview)

• OpenDS-World is a novel benchmark for evaluating "deep search" capabilities of AI systems in real-world web environments, consisting of 130 carefully designed tasks that require multi-step information gathering, integration, and reasoning.
• The benchmark addresses a critical gap in existing evaluation frameworks by focusing on open-ended, complex queries that cannot be solved by simple retrieval or single-round search.
• The paper introduces a comprehensive evaluation protocol including independent human solving baselines and cost analysis to capture the economic feasibility of different AI approaches.
• Results show that current state-of-the-art large language models (LLMs) with search capabilities still underperform human experts by a significant margin, highlighting substantial room for improvement.
• The paper provides detailed error and budget analyses that reveal specific failure modes of existing models and the cost-effectiveness trade-offs between different agentic search strategies.

Introduction and Theoretical Foundation

The paper addresses the evolving landscape of information retrieval, where traditional search engines and single-turn question-answering systems are inadequate for complex real-world queries. The authors introduce the concept of "deep search" — a paradigm that extends beyond surface-level retrieval to involve:

1. Multi-step information gathering across various web sources
2. Information integration and synthesis from heterogeneous sources
3. Deductive reasoning to draw conclusions that are not explicitly stated
4. Iterative refinement of search strategies based on intermediate findings

The theoretical foundation draws from prior work in:

• Web search and information retrieval: Moving from single-query to multi-query, interactive search paradigms
• Tool-augmented LLMs: Models that can use external tools (e.g., web search APIs, calculators, code interpreters)
• Agentic systems: Autonomous agents that plan and execute complex sequences of actions
• Real-world reasoning: Evaluating AI systems in ecologically valid environments rather than static benchmarks

The authors argue that existing benchmarks like WebArena, Mind2Web, and GAIA fail to capture the full complexity of real-world deep search tasks, which often require dynamic interaction with live web content and the ability to handle unanticipated information.

Methodology

2.1 OpenDS-World Benchmark Construction

Task Definition: A deep search task is formally defined as a tuple $\mathcal{T} = (q, A, y, w)$ where:

• $q$ is a natural language query requiring deep, multi-step research
• $A$ is the set of acceptable answers
• $y$ is the final answer
• $w$ is a set of supporting web evidence sources

Main Attributes of tasks include:

• Comprehensiveness: Queries that require retrieving diverse, complementary information
• Depth: Questions that necessitate multi-hop reasoning across sources
• Real-world relevance: Based on actual events, products, or entities

2.2 Task Construction Process

Tasks were constructed through a three-phase pipeline:

1. Task drafting: Task creators generated candidate queries, emphasizing open-endedness and complexity requirements
2. Verification: Each candidate task underwent rigorous multi-round verification to ensure:
   • The task is solvable (ground truth exists and is verifiable)
   • The task is non-trivial (cannot be answered by simple lookup)
   • The answer is unambiguous and well-defined
3. Quality control: A separate team reviewed tasks for language quality, answer clarity, and evidence completeness

Evidence was gathered with timestamps to ensure temporal verifiability, with all evidence archived to maintain benchmark integrity against web content drift.

2.3 Human Testing Protocol

To establish a robust baseline, the authors recruited human participants who:

• Were allowed unlimited time and full web access
• Received instructions to prioritize accuracy over speed
• Provided evidence for their answers to verify genuine reasoning

Human performance was measured using accuracy tracks:

• Binary accuracy: Correct vs. incorrect final answer
• Partial credit: Degree of correctness for multi-component answers

The HumanSolvedRate metric was defined as the percentage of tasks where at least one human participant provided a correct answer with valid evidence.

2.4 Evaluation Setup for AI Systems

The authors evaluated several state-of-the-art LLMs (including GPT-4o, Claude, and proprietary search-agent models like OpenAI Deep Research and Gemini Deep Research) on the benchmark, measuring:

• Accuracy: Overall correctness on the 130 tasks
• Cost: Average cost ($USD) per task
• Token usage: Efficiency of information processing
• Tool use patterns: Frequency and types of search tool invocations

Empirical Validation / Results

3.1 Main Results

Table 1: Performance on OpenDS-World

The paper's Figure 1 (referenced above) visualizes these results, clearly showing that all AI models achieve less than ~25% accuracy, while human experts reach ~78% (best individual) with an upper bound approaching ~94%.

Key findings:

• The gap between AI and human performance is statistically and practically significant
• Even the best-performing AI systems fail to reach even a quarter of the tasks
• The human upper bound (~93.8%) suggests that nearly all tasks are solvable with sufficient effort, further emphasizing AI's limitations

3.2 Cost Analysis

The paper highlights a critical cost-performance trade-off:

• Deep search agents incur substantial monetary costs per query due to:
  • Multiple LLM API calls for planning, reasoning, and tool orchestration
  • Long context windows requiring extensive processing of retrieved documents
  • Iterative search-and-refine loops
• The cost analysis demonstrates that for real-world deployment, the economic efficiency of current agents is a significant barrier, not just accuracy

3.3 Tool-Use and Budget Analysis

• Tool-use analysis revealed that successful agents engage in:

  • More diverse search queries (varying phrasing and specific technical terms)
  • Strategic query reformulation based on intermediate results
  • Aggregation from multiple sources before synthesizing answers

• Budget analysis showed that increasing the search budget (number of allowed retrieval operations) does not linearly translate to improved performance for current models — a saturation effect and, in some cases, degradation occur beyond a certain budget, suggesting that models struggle to effectively utilize large amounts of retrieved information.

3.4 Error Analysis

Common failure modes identified:

Theoretical and Practical Implications

Theoretical Implications

• Scaling limits of retrieval: The results challenge the assumption that simply scaling up LLMs or search budgets leads to proportional gains in deep search performance. The gap suggests a need for fundamentally new reasoning architectures, not just larger models.
• Human-in-the-loop value: Human participants' ability to beat AI by ~3-4x demonstrates the importance of strategic exploration and evaluation — cognitive processes not yet well-captured by current agent frameworks.
• Task complexity taxonomy: The benchmark provides a foundation for categorizing deep search tasks along dimensions of complexity, abstraction, and evidence integration, enabling future theory development.

Practical Implications

• Deployment feasibility: Current AI deep search agents are not yet production-ready for tasks requiring high accuracy (e.g., academic research, legal work, financial analysis), and their cost ($0.50–$3+ per task) may be prohibitive at scale.
• Agent design guidance: The error analysis pinpoints specific components (e.g., early-stopping heuristics, contradiction detection, evidence weighting) as targets for immediate improvement.
• Benchmarking methodology: OpenDS-World's living nature (with archived evidence) provides a template for building temporally-stable yet real-world-representative benchmarks, addressing a major limitation of static QA datasets.

Conclusion

The paper introduces OpenDS-World, the first benchmark specifically targeting deep search in real-world web environments. Through rigorous construction, human verification, and comprehensive evaluation, the authors demonstrate that:

1. Current state-of-the-art AI systems achieve only ~20-25% accuracy, dramatically underperforming human experts (up to ~94% upper bound)
2. The benchmark effectively captures tasks where relevance assessment, evidence synthesis, and iterative search are critical — abilities that current systems lack
3. There is a clear and urgent need for advancing retrieval, reasoning, and cost-efficient agent design

Future directions identified by the authors include:

• Designing agents with adaptive search termination mechanisms
• Developing multi-source evidence integration modules
• Investigating cost-aware agent training to optimize the accuracy-efficiency frontier
• Expanding the benchmark to include multimedia evidence and non-English web sources

The code, dataset, and contact information are publicly released to facilitate further research in this critical area.