# Deep Search in Real-World Web Environments

> OpenDS-World shows current AI search agents achieve under 25 percent accuracy versus 94 percent human upper bound, revealing deep search remains unsolved.

- **Source:** [arXiv](https://arxiv.org/abs/2610.30181)
- **Published:** 2026-10-24
- **Permalink:** https://picx.dev/p/xe036C
- **Whiteboard:** https://picx.dev/p/xe036C/image

## Summary

## 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**

| Model | Accuracy (%) | Avg Cost ($) |
|-------|---------------|---------------|
| OpenAI Deep Research | 20.0 | — |
| Gemini 1.5 Deep Research | 22.3 | — |
| Kimi K1.5 (w/ search) | 10.0 | — |
| GPT-4o (w/ search) | 15.4 | — |
| **Human (Best)** | **77.7** | — |
| **Human (Average)** | 34.6 | — |
| **Human (Upper Bound)** | 93.8 | — |

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:

| Error Type | Description | Frequency |
|------------|-------------|-----------|
| **Insufficient coverage** | Agent stops searching too early; misses critical evidence | High |
| **Incorrect synthesis** | Correctly retrieves evidence but reasons incorrectly | Medium |
| **Premature termination** | Agent outputs an answer despite incomplete information | Medium |
| **Misleading context** | Stale or unrelated web content distracts the agent | Low |

## 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.

---

_Markdown view of https://picx.dev/p/xe036C, served by PicX — AI-generated visual whiteboard summaries of research papers._