Deep Search in Real-World Web Environments

AI summary

Overview

Research area: Information retrieval / agent evaluation — specifically "Deep Search" agents that autonomously research questions on the live, open Web (cs.IR).

Technical level: Advanced. The paper assumes familiarity with LLM agents, tool-use harnesses, and benchmark design, though the core argument is accessible.

Scope: The paper introduces the OpenDS task and the OpenDS-World benchmark (200 human-verified tasks) to measure how well 12 frontier models perform multi-step evidence gathering across the real open Web, and reports accuracy, cost, tool-use, and failure behavior.

What This Paper Is About

AI "Deep Search" agents are improving quickly, but existing tests do not capture how hard real Web research actually is: evidence is scattered across text, images, audio and video, stored in many file formats (HTML, PDF, XML, Parquet), and often locked behind interactions such as navigating a virtual tour, applying filters, or downloading an artifact. The authors build a benchmark where an agent must start from a video, work outward through multiple independent Web sources, and arrive at one unique factual answer — then measure how frontier models compare to humans doing the same work in a normal browser.

Key Contributions

1. The OpenDS task formulation. A definition of open-Web deep search as a factual question-answering problem in which the agent must autonomously discover, access, process, and connect evidence across sources with diverse modalities, heterogeneous formats, and interactive access requirements — with no pre-given locations or access methods.

2. The OpenDS-World benchmark. 200 tasks across eight domains (culture, daily life, science, economy, history, nature, society, technology), built from 500 candidate videos, containing 787 annotated evidence-chain entries (3.94 per task on average) covering four modalities, 42 formats, and seven access types, with independent human verification by ten reviewers.

3. A human difficulty calibration. 50 independent solvers, none involved in construction, attempted 1,000 total attempts under browser-only conditions (no LLM tools), yielding accuracy, solving-time, and subjective-difficulty data used to define Low/Medium/High task tiers.

4. A unified 12-model evaluation. All models run under the same tool harness, prompts, and budgets (3,600-second search phase, 100 tool calls), with analysis of accuracy, token and wall-clock cost, tool-category usage, termination outcomes, tool-failure recovery, and budget exhaustion.

Main Findings

• Best model reaches 39.0%, and humans reach 21.1%. GPT-6 Astra leads at 39.0% (78 of 200), followed by Claude Opus 5.5 at 38.0% (76), Gemini 3.8 Flash at 36.5% (73), and Claude Fable 5.1 at 33.5% (67). Human solvers achieved 21.10% (211 of 1,000 independent attempts). Even the top model fails 122 of 200 tasks, a 61.00% failure rate.

• The benchmark is genuinely hard for people too. Only 115 of 200 tasks (57.50%) were solved by at least one of five solvers; 85 tasks (42.50%) were solved by none. Just 1 task (0.50%) was solved by all five, and only 29 tasks (14.50%) were solved by three or more.

• Human effort was substantial. The 50 participants averaged 12.92 hours for their 20-task sets (median 9.44 hours; about 646 hours total), roughly 38.8 minutes per attempt. Mean subjective difficulty was 3.884/5 (median 4/5), with 43.00% of attempts rated 5 and 65.50% rated 4 or 5.

• Accuracy drops sharply with difficulty. Averaged over the 12 models, accuracy falls from 39.66% (Low, 54 tasks) to 23.50% (Medium, 61 tasks) to 16.76% (High, 85 tasks). GPT-6 Astra goes 59.26% → 40.98% → 24.71%. Gemini 3.8 Flash is the strongest on High at 28.24%, while Qwen3.8-Flash and DeepSeek-V4-Pro reach only 4.71% and 3.53% there.

• More spending does not buy accuracy. GPT-6 Astra and GPT-5.6 Sol consume nearly identical total tokens (187M vs 186M) yet differ by 11.00 percentage points in accuracy. Gemini 3.8 Flash uses about 5.22× GPT-6 Astra's tokens (976M) for lower accuracy (36.5%). DeepSeek-V4-Pro spends about 2.39× GPT-6 Astra's wall-clock time (148 h vs 62 h) for 12.5% accuracy.

• Per-task cost varies widely. GPT-6 Astra averages 51.05 tool calls and 18.66 minutes per task; GPT-5.6 Sol averages 52.42 calls but only 8.99 minutes (median 7.22 minutes vs 14.35 for GPT-6 Astra). Qwen3.8-Flash averages 89.94 calls, while DeepSeek-V4-Pro and GLM 5.3 average 44.47 and 43.36 minutes, with long tails.

• Tool mix does not predict success. GPT-5.6 Sol is the most search-heavy (74.50% Search, 17.77% GUI). Claude Opus 5.5 and Qwen3.8-Flash put 51.52% and 49.42% of calls into GUI operations, yet score 38.00% and 12.00%. DeepSeek-V4.1-Flash makes 11.78 video/subtitle calls per task versus 4.67 for Claude Opus 5.5, and scores lower (20.50% vs 38.00%).

• Models mostly repeat their own tool category. Within-category transitions dominate: Search → Search reaches 84.63% for Gemini 3.8 Flash and GUI → GUI reaches 84.97% for Qwen3.8-Flash.

• Budget exhaustion is common and splits into two failure modes. At least one limit is hit on 81.5% of tasks for Qwen3.8-Flash, 78.0% for DeepSeek-V4.1-Flash, 73.0% for GLM 5.3, and 72.5% for DeepSeek-V4-Pro, versus 25.5% for GPT-6 Astra, 22.0% for GPT-5.6 Sol, and 16.5% for Claude Opus 5.5. Some models are call-limited (Qwen3.8-Flash 80.0% call-only; DeepSeek-V4.1-Flash 60.5%) and others time-limited (GLM 5.3 41.0%; Kimi K3 29.5%; Claude Fable 5.1 28.0%); both limits coincide on at most 1.0% of tasks per model.

• Stopping is not the same as succeeding. GPT-6 Astra terminates naturally on 69.0% of tasks, GPT-5.6 Sol on 65.0%, and Claude Opus 5.5 on 60.5%, but accuracies stay below 40%. Qwen3.8-Flash terminates naturally on only 6.5% and hits the call limit on 80.0%.

• Tool failures are cheap in count but expensive in time. Failed calls are 2.83%–9.42% of calls but consume 19.27%–61.90% of tool execution time (for GPT-6 Astra, 6.34% and 42.57%). After a failure, switching tools is the dominant response (~83% for Claude Opus 5.5, ~81% Gemini 3.8 Flash, ~79% GPT-5.6 Sol), while Kimi K3 and GLM 5.3 retry with modified arguments more often (~38% and ~37%).

• Evidence chains are multimodal and interactive. Text appears in 99.5% of tasks, images in 44.5%, video in 35.5%, audio in 16.0%, and 82.5% of tasks involve at least two modalities. HTML covers 98% of tasks, MP4 35%, PDF 31%, with 96.0% using at least two formats. Access requirements include navigation (67.0%), artifact transfer (60.0%), temporal indexing (47.5%), parameterized state updates (42.0%), and 95.5% of tasks combine multiple access types.

Methodology in Plain English

Building the tasks (three stages). Annotators first picked a publicly accessible video and identified an entity that can only be recognized from the video's visual and audio content — not from text on the page — and that maps to a unique Wikidata entry. From that anchor, they used Google Search to hop outward: each hop selects a real Web source, extracts a new entity from it, and requires that entity to be corroborated by multiple independent sources before it becomes the next link. The chain stops at a unique terminal answer. Finally, the whole chain is inverted into a question: intermediate nodes are never named, only obliquely described, so the clues together pin down exactly one answer but no single clue gives it away. The videos ship with the benchmark, matched to tasks by ID.

Verification. Ten independent reviewers re-walked every candidate path using the preserved source links, checking both that the evidence is real, accessible, and independently corroborable (not just asserted by the original source) and that the question has one unambiguous answer. Any task with factual errors, weak evidence, inconsistent relations, ambiguity, or a non-unique answer was dropped, leaving 200 tasks.

Human baseline. Tasks were split into 10 sets of 20; each set went to five solvers, 50 people total, each doing only one set. Solvers saw only the video, audio, and question — no reference answer, no evidence path — and could use an ordinary browser such as Google Chrome but no LLM tools. No per-question time limit. They submitted an answer, their time, and a 0–5 difficulty rating.

Model evaluation. All 12 models ran in one shared harness with three tool families: a Search Tool (text, image, and video search), a GUI Tool (navigation, reading, clicking, typing, scrolling, screenshots), and Other Tools (video-frame inspection and subtitle extraction for input and external videos). Each sample was capped at 3,600 seconds and 100 tool calls; if search ended by timeout, budget, or no valid answer, a tool-disabled finalization stage produced an answer from whatever evidence had been gathered. Answers were graded for semantic equivalence against the reference by an LLM judge, Qwen3.8-27B, with accuracy as the primary metric and tokens and elapsed time as cost metrics.

Analysis. Beyond accuracy, the authors broke results into three difficulty tiers defined by how many of the five human solvers got the task right (Low ≥ 2, Medium = 1, High = 0), and examined trajectories for tool-category transitions, termination types, failure recovery choices, and which budget limit was hit.

Why This Matters

Impact on research. The paper shifts deep-search evaluation away from static retrieval snapshots toward the messy, live Web — multiple modalities, awkward formats, and evidence that only appears after you interact with a page. It also supplies a calibrated difficulty scale grounded in human performance rather than guesswork, and shows that scaling tool calls or wall-clock time is not a path to better research; coordination, source selection, and knowing when to stop are.

Real-world applications:

• Enterprise and competitive intelligence: pulling a fact out of an earnings PDF, a dataset, and a product video, where the answer requires joining all three.
• Scientific and regulatory literature work: reconciling figures across papers, supplementary PDFs, and structured data repositories.
• Investigative and fact-checking workflows: tracing a claim back through several independent sources and confirming it is corroborated rather than repeated.
• Accessibility and media-driven research: starting from audiovisual material and locating the underlying authoritative record.

Industry relevance. The failure analysis is directly actionable for anyone shipping an agent product: budget exhaustion affects a majority of tasks for several models, failed tool calls eat 19.27%–61.90% of execution time, and natural termination does not imply a correct answer. Those are concrete targets for harness design, retry policy, and stopping criteria, and the open benchmark plus code and dataset links make it usable as a leaderboard-style evaluation.

Future Directions

• Better stopping and self-assessment. Models terminate naturally on 60.5%–69.0% of tasks while scoring under 40%, so teaching agents to judge whether their evidence actually supports an answer is a clear next step.
• Long-horizon execution and self-improvement. The authors point to a discussion of long-horizon execution and potential self-improvement directions, and the wide spread in budget exhaustion (16.5% to 81.5% of tasks) suggests room for learned budget management.
• Smarter tool coordination and failure handling. The dominance of within-category transitions (up to 84.97% GUI → GUI) and the heavy time cost of failing calls point to policies that switch modalities and tools more deliberately.
• Extending the evidence-attribute space. With 42 formats already represented (including a 108-entry long tail spanning 35 types) and seven access types, the natural question is whether performance holds as formats, interfaces, and interaction mechanisms continue to diversify.

Target Audience

Agent and RAG researchers building search or browsing systems; benchmark and evaluation researchers who need a realistic, human-calibrated alternative to static retrieval tests; and engineering teams shipping Web-research agents who want to know which failure modes — budget exhaustion, tool-failure cost, or premature stopping — are actually limiting their system. Readers new to the area can follow the task motivation and headline results, but the analysis sections assume comfort with agent tool-trajectory metrics.

Authors’ abstract

Despite substantial progress in Deep Search agents, their ability to conduct end-to-end research in real-world open Web environments remains insufficiently evaluated. Unlike static retrieval settings, information on the real-world Web is distributed across diverse sources, modalities, and heterogeneous formats, often involving complex interaction mechanisms that require agents to autonomously search for, access, and integrate relevant evidence during execution. To address this gap, we introduce the OpenDS task, designed to evaluate agents' ability to perform multi-step deep search in the live, open Web. This task requires agents to autonomously explore the real Web, discover and connect relevant evidence from multiple independent sources through Web search, browser interaction, and evidence processing, and ultimately determine a unique factual answer. Building on this task formulation, we construct OpenDS-World, a benchmark comprising 200 challenging tasks spanning diverse information modalities, heterogeneous file formats, and interactive access requirements, with independent human verification to ensure evidence validity and answer uniqueness. We evaluate 12 frontier models under a unified tool environment and execution protocol. The best-performing model achieves 39.0% accuracy, while human evaluation across 1,000 independent attempts yields 21.1% accuracy. Further analyses of tool usage, search cost, termination behavior, and failure recovery reveal substantial differences in research strategies across models, as well as persistent challenges in tool coordination and long-horizon search management. OpenDS-World provides a unified evaluation platform for systematically assessing and advancing agents' autonomous deep search capabilities in real-world open Web environments.