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—multi-step web research tasks exemplified by the BrowseComp benchmark, where strong open models like DeepSeek-R1 score only 2-3% versus OpenAI DeepResearch's 51.5%. The approach combines two innovations: (1) automated data synthesis by random walks over knowledge graphs, with entity obfuscation by frontier LLMs and difficulty filtering (only questions that GPT-4o fails four times are kept), yielding 3,250 hard QA pairs; and (2) end-to-end multi-turn reinforcement learning with GRPO plus a Jaccard-similarity redundancy penalty that discourages repeated queries. Applied to QwQ-32B, DeepDive lifts BrowseComp accuracy from 1.3% to 15.3%, surpassing WebSailor-32B and DeepSeek-R1. Performance scales with tool-call budget (8% to 15% as calls grow from 8 to 128), and parallel sampling with fewest-tool selection reaches 24.8%. Ablations show data difficulty and format rewards are critical. Code, models, and data are open-sourced.

DeepDive: Teaching AI to Dive Deep into the Ocean of Information

When large language models meet web search, an evolution of search agents begins. DeepDive, a framework developed by Tsinghua University researchers, trains open-source models to perform *deep search*—navigating hundreds of web pages, filtering, and synthesizing information to answer questions that would take human experts hours—challenging OpenAI's DeepResearch and Google's Gemini Deep Research.

The Deep Search Problem

Simple factual questions are easy for LLMs. But benchmarks like BrowseComp pose puzzles such as: "find a fictional character who occasionally breaks the fourth wall, has a backstory involving a selfless ascetic's help, is known for humor, and whose TV series aired in the 1960s–1980s with fewer than 50 episodes." Unlike multi-hop datasets such as HotpotQA, these questions require dozens of search steps.

The reality is harsh: DeepSeek-R1 achieves only 2–3% on BrowseComp, while OpenAI's DeepResearch exceeds 50%. Open-source models lack not intelligence but *patience and strategy*—they hallucinate after one or two failed searches. And virtually no training data exists for such deep search, since annotating such questions is extremely costly.

Two Keys: Data Synthesis + Multi-Turn RL

1. Random Walks over Knowledge Graphs

DeepDive automatically generates hard questions by:

Starting from a node in a knowledge graph and taking a random walk of 5–9 hops, forming a path of entities and relations.
Entity obfuscation: a frontier model (Gemini-2.5-Pro) replaces concrete facts with vague descriptions (e.g., "1948" → "late 1940s"), so questions can no longer be answered by a single lookup:

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

Difficulty filtering: GPT-4o with basic search attempts each question four times; only questions it always fails are kept.

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

2. Multi-Turn Reinforcement Learning

Deep search is dynamic: the model generates a reasoning chain $$c_t$$ , executes a search action $$a_t$$ , observes results $$o_t$$ , and loops:

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

Training uses GRPO with normalized advantages:

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

A key innovation is a redundancy penalty based on Jaccard similarity between queries, preventing the model from repeating the same searches:

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

This reduced tool calls by ~14% during training while boosting later-stage accuracy by 20%.

Results: From 1.3% to 15.3%

Applied to QwQ-32B on BrowseComp:

| Stage | Accuracy | |---|---| | Base model | 1.3% (1.7% with browsing) | | + SFT | 9.5% | | + RL | 15.3% |

This surpasses WebSailor-32B (10.5%) and DeepSeek-R1 (2.0%), leading the open-source field.

Test-time scaling: raising max tool calls from 8 to 128 lifts BrowseComp success from 8% to 15%—the model genuinely searches deeper.
Parallel sampling: running 8 independent attempts and selecting the answer with the fewest tool calls boosts accuracy from 12.0% to 24.8%—confident models stop searching earlier.
Ablations: without format rewards, performance stagnates at ~8%. Training on HotpotQA data yields far weaker RL results (9.2%) than DeepDive's synthetic data (12.0%)—data difficulty determines model ceiling.
Generalization: despite being trained for hard tasks, DeepDive-32B beats GPT-4o and Claude-3.7-Sonnet on easier benchmarks, scoring 63.9% on WebWalker vs. DeepSeek-R1's 38.6%.

Limitations and Transparency

The authors candidly note the gap with OpenAI DeepResearch (51.5%), attributed to the ceiling of automatically synthesized data difficulty. The model also sometimes *over-searches* on easy questions. An n-gram contamination analysis confirmed >97% of training samples have <20% overlap with test sets.

All code, models, and data are open-sourced on GitHub, built on GLM-4 and QwQ models, the Slime RL framework, and Serper/Jina APIs—a genuinely open-source collaborative effort.

Key References

1. Lu, R., et al. (2025). *DeepDive: Advancing Deep Search Agents with Knowledge Graphs and Multi-Turn RL*. 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* (GRPO) 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 the finish line but a milestone: it shows open-source communities can tackle problems even tech giants find hard—through creative data synthesis, careful algorithm design, and scientific persistence.