Demystifying Deep Search: A Holistic Evaluation with Hint-free Multi-Hop Questions and Factorised Metrics

🕒 Published (v1): 2026-01-01 · Source: ICLR · Venue: ICLR 2026 · link

Why this paper was selected

Hint-free multi-hop questions and factored metrics for deep search evaluation

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

WebDetective is a 200-question benchmark of hint-free multi-hop questions paired with a controlled, masked Wikipedia sandbox, designed to force agents to discover reasoning chains rather than execute prescribed ones. It introduces factorised metrics separating search sufficiency, knowledge utilisation, and refusal behaviour. Evaluating 25 frontier models reveals that even the strongest systems reach only ~56% Pass@1, with synthesis and calibrated refusal—not retrieval—as the primary bottlenecks.

Problem

Existing multi-hop QA benchmarks embed two forms of scaffolding that inflate apparent agent capability: Path-Hinting (PH), where the question narrates the full reasoning chain (e.g., HotpotQA's "Who is the husband of the stepmother of the brother of X?"), and Specification-Hinting (SH), where distinctive attribute clusters fingerprint the target entity (e.g., BrowseComp). Both reduce the task to path execution or constraint filtering rather than autonomous path discovery. Additionally, single pass-rate metrics collapse distinct failure modes—poor synthesis, premature refusal, hallucination under noise—making targeted improvement difficult.

Method

WebDetective co-designs hint-free questions with a controlled evaluation environment through three components:

1. Hint-Free (HF) question construction. Starting from Wikipedia single-hop QA pairs \((q, v_0, v_n)\), the direct link \(v_0 \to v_n\) is removed and BFS over the hyperlink graph finds the shortest alternative multi-hop path \(v_0 \to v_1 \to \cdots \to v_n\). Questions contain only the minimal information need with no path or attribute hints.

2. Masked Wikipedia sandbox. Each intermediate node \(v_i\) is masked so it is only discoverable by visiting \(\text{page}(v_{i-1})\), enforcing: $\(v_i \text{ is discoverable} \iff \text{agent visits } \text{page}(v_{i-1})\)$ This eliminates shortcutting via spurious co-occurrences while allowing any valid reasoning strategy, not just the reference path.

3. Factorised metrics. Knowledge Sufficiency checks whether the agent gathered all required evidence \(E = \{e_1,\ldots,e_n\}\) (via search or confirmed parametric knowledge). Search Score additionally credits efficient combination of partial search with parametric memory. Generation quality is split into Good Refusal F1 (\(F1_{GR}\), penalises hallucination when evidence is absent) and Knowledge Utilisation F1 (\(F1_{KU}\), penalises failure to synthesise available evidence), combined as: $\(\text{GenScore} = \frac{F1_{GR} + F1_{KU}}{2} \cdot \text{KnowledgeScore}\)$

EvidenceLoop, a diagnostically-derived agentic baseline, runs \(N\) parallel solver agents per iteration for \(R_{\max}\) rounds with \(B\) actions each. An extraction agent distils findings and an aggregation agent builds a structured context \(C^{r+1}\) per round. A persistent evidence memory assigns each retrieved fact an Evidence ID (EID); agents reason over summaries but can retrieve full documents via EID. Any proposed answer is decomposed into atomic claims \(\{c_1,\ldots,c_m\}\), each traced to an EID, and a verification agent checks entailment before accepting.

Key Contributions

• WebDetective: the first benchmark to systematically eliminate both path-hinting and specification-hinting from multi-hop QA, using a masked Wikipedia sandbox enabling full action traceability.
• Factorised diagnostic framework: separates Knowledge Sufficiency, Search Score, Good Refusal F1, and Knowledge Utilisation F1 from a single pass rate, enabling per-failure-mode analysis.
• Knowledge Degradation probes: Forget test (parametric knowledge succeeds in isolation but fails in full search context) and Lead-astray test (noisy search context degrades synthesis of otherwise accessible evidence).
• EvidenceLoop: a structured agentic workflow with EID-based evidence memory, parallel exploration, and claim-level verification, demonstrating that the benchmark's diagnostic framework can guide concrete architectural improvements.
• Comprehensive evaluation of 25 frontier models across 6 providers, revealing systematic gaps.

Results

• Best Pass@1: o3-Pro 56.0%, GPT-5 and Grok-4 both 50.5%, Claude-Opus-4.1 44.5%; most models fall well below 40%.
• Search and synthesis are decoupled: GPT-5 achieves 80.0% Search Score but only 23.21% Generation Score; Qwen3-235B-Think posts 72.0% Search Score but only 11.15% Generation Score and 21.5% Pass@1.
• Grok-4 achieves the highest Generation Score (34.71%) with 50.5% Pass@1; no model saturates any metric.
• Good Refusal F1 is near-absent: best is Doubao-1.6-Flash at 53.95%; GPT-5 scores 8.89%, o3-Pro 9.37%, o4-Mini 19.75%.
• EvidenceLoop (DeepSeek-R1 backbone): Knowledge Sufficiency 61.5%, Pass@1 25.0%—comparable to the base model's 20.0% Pass@1 but with 5pp gain, validating the framework's diagnostic utility without dramatic gains.
• Knowledge Degradation: Forget rates up to 100% (GPT-OSS-120B); Lead-astray up to 59.56% (o4-Mini).

Limitations

• Benchmark size is small (200 questions), limiting statistical power for fine-grained model comparisons.
• Instantiated solely on Wikipedia; generalisability to live web environments or other corpora is asserted but not empirically demonstrated.
• EvidenceLoop does not substantially outperform strong baselines at Pass@1, leaving the open question of how to close the diagnostic gap with architectural improvements.
• Questions are 2–4 hops; longer chains or more complex compositional reasoning are not covered.
• Automated LLM-based validation (Qwen-3-235B) for chain necessity may introduce model-specific biases in dataset construction.

Relevance to Agentic AI / LLM Agents

WebDetective directly targets a core capability gap in agentic systems: the difference between path execution (following explicitly scaffolded reasoning) and path discovery (autonomously identifying which connections matter). The benchmark's factorised metrics expose that current frontier agents fail not primarily at retrieval but at evidence synthesis and calibrated uncertainty—failure modes invisible to pass-rate-only evaluation. The EvidenceLoop framework, with its EID-based evidence memory and claim-level verification loop, is a concrete architectural template for multi-hop reasoning agents. For researchers building or evaluating web agents, RAG systems, or tool-using LLMs, WebDetective establishes that genuine autonomy requires better synthesis and refusal mechanisms, not just better search.