DeepDive: Teaching Open-Source AI Agents to Deep Search with Knowledge Graphs and Multi-Turn RL

Forum topic · QianXun · 2025-11-25

Summary

DeepDive is a framework from Tsinghua University researchers that trains open-source large language models to perform deep search—navigating hundreds of web pages to answer questions that even human experts find difficult. It addresses two bottlenecks: lack of hard training data and weak long-horizon search strategies. First, DeepDive automatically synthesizes difficult question-answer pairs by performing random walks on knowledge graphs and using frontier LLMs to obscure entity attributes, filtering with GPT-4o so only questions that defeat strong models survive—yielding 3,250 high-quality examples at low cost. Second, it applies end-to-end multi-turn reinforcement learning with GRPO, including a Jaccard-similarity-based redundancy penalty that discourages repetitive searches, cutting tool calls by ~14% and boosting late-stage accuracy by 20%. Applied to QwQ-32B, DeepDive raises BrowseComp accuracy from 1.5% to 15.3%, surpassing WebSailor-32B and DeepSeek-R1, with test-time scaling and parallel sampling pushing results as high as 24.8%. It also outperforms GPT-4o and Claude-3.7-Sonnet on simpler benchmarks like WebWalker (63.9%). Code, models, and data are open-sourced on GitHub. The gap to OpenAI's DeepResearch (51.5%) remains, attributed to the difficulty ceiling of synthetic data and over-search on easy questions.

Introduction

When large language models meet web search, an adventure in agent evolution begins. Imagine a detective whose clues are scattered across a city—hidden in rare library books, buried in archives, readable only with a magnifying glass. This is the 2025 digital world, where the "detective" is a web-browsing LLM and the "cases" are deep-search puzzles that even human experts need hours to crack.

DeepDive, a framework developed by Tsinghua University researchers, does not simply attach a search engine to an AI. It teaches models to dive deep like real researchers—traversing hundreds of web pages, filtering and synthesizing information—enabling open-source models to challenge OpenAI's DeepResearch and Google's Gemini Deep Research.

The Deep Search Dilemma

Easy questions like "Who won the 2024 Nobel Prize in Physics?" float on the surface. But a BrowseComp-style question—"Find a fictional character who occasionally breaks the fourth wall, whose backstory involves a selfless ascetic's help, known for humor, whose TV series aired 1960–1980 with fewer than 50 episodes"—requires navigating a maze without a map.

The gap is stark: on BrowseComp, even strong open-source DeepSeek-R1 achieves only 2–3%, while OpenAI's DeepResearch exceeds 50%. The core problem: open-source models lack not intelligence but patience and strategy—they hallucinate after one or two failed searches. And the web simply lacks enough hard, labeled training data for deep search.

Two Keys: Data Synthesis and Multi-Turn RL

Key 1: Random Walks on Knowledge Graphs

DeepDive generates hard questions by:

Starting from a knowledge-graph node and performing a random walk of 5–9 hops, forming paths like [1940s institution] → [person born mid-1980s] → … → [AFC Cup]
Entity obscuring via frontier LLMs (e.g., Gemini-2.5-Pro): "1948" becomes "late 1940s"; names become descriptive traits
Difficulty filtering: GPT-4o with basic search attempts each question four times; only questions it fails are kept

The obscuring step is formalized as:

(q, a_i^k) = \text{LLM-obscure}(P_A)

The pipeline produced 3,250 high-quality deep-search QA pairs at a fraction of manual annotation cost.

Key 2: Multi-Turn Reinforcement Learning

Deep search is a dynamic loop of reasoning chains, search actions, and observations:

\mathcal{T} = [q, (c_1, a_1, o_1), \ldots, (c_m, a_m, o_m), c_{\text{ans}}, a_{\text{eos}}]

DeepDive uses GRPO (Group Relative Policy Optimization) with normalized advantages:

A_i = \frac{r_i - \text{mean}(\{r_k\}_{k=1}^G)}{\text{std}(\{r_k\}_{k=1}^G)}

The key innovation is a redundancy penalty based on Jaccard similarity, discouraging repeated identical searches:

S(\mathcal{T}) = \frac{1}{T(T-1)}\sum_{i\neq j}\frac{|q_i \cap q_j|}{|q_i \cup q_j|}, \quad r'(\mathcal{T}) = r(\mathcal{T}) - \lambda \cdot S(\mathcal{T})

This reduced tool calls by ~14% while improving late-stage accuracy by 20%.

Results: From 6.3% to 22.2%

Applied to QwQ-32B:

BrowseComp: base model 1.3% (1.7% with browsing) → 9.5% after SFT → 15.3% after RL, beating WebSailor-32B (10.5%) and DeepSeek-R1 (2.0%)
Test-time scaling: raising max tool calls from 8 to 128 lifted BrowseComp success from 8% to 15%—the model genuinely learns to "think longer, search deeper"
Parallel sampling: running 8 times and selecting the answer with fewest tool calls boosted accuracy from 12.0% to 24.8%—confident models stop searching early; excessive searching signals uncertainty

Ablation Findings

Format rewards matter: removing strict format rewards stalled learning at ~8% on the BrowseComp-266 subset
Data difficulty determines model height: HotpotQA training brought SFT only to 4.9% and RL to 9.2%, while DeepDive's synthetic data reached 7.5% (SFT) and 12.0% (RL)

Generalization Beyond Hard Benchmarks

Though designed for "deep water," DeepDive-32B also beats GPT-4o and Claude-3.7-Sonnet on simpler tasks: 63.9% on WebWalker vs. DeepSeek-R1's 38.6%. Skills honed on hard problems provide "dimensional reduction" for easy ones.

Limitations and Outlook

A large gap remains to OpenAI's DeepResearch (51.5%), mainly due to the difficulty ceiling of synthetic data
Over-search on easy questions suggests the need for difficulty-adaptive reward mechanisms
Data-contamination analysis (n-gram detection) confirmed >97% of training samples overlap <20% with test sets, with no severe contamination

Open Source

All code, models, and data are released on GitHub. Built on GLM-4 and QwQ open models, the Slime RL framework, and Serper/Jina APIs, DeepDive is a true open-source community effort—showing how AI can evolve from a "Wikipedia-reciting parrot" into a "scholar with research strategy."

Key References

1. Lu, R., et al. (2025). DeepDive: Advancing Deep Search Agents with Knowledge Graphs and Multi-Turn RL. *arXiv preprint arXiv:2509.10446*. 2. Wei, J., et al. (2025). BrowseComp: A benchmark for deep search agents. 3. Shao, Z., et al. (2024). Deepseekmath: Pushing the limits of mathematical reasoning in open language models. 4. Yao, S., et al. (2023). ReAct: Synergizing reasoning and acting in language models. 5. DeepSeek-AI, et al. (2025). Deepseek-r1: Incentivizing reasoning capability in LLMs via reinforcement learning.

DeepDive is not an endpoint but a milestone—proof that the open-source community can tackle problems even tech giants find hard, given creative data synthesis, clever algorithms, and scientific persistence.