DeepDive: Teaching Open-Source LLMs to Deep Search via 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 on questions like those in the BrowseComp benchmark, where models must synthesize information across dozens of web pages. The approach has two pillars: (1) automatic data synthesis by performing random walks on knowledge graphs, then using a frontier LLM to obscure entities and filter questions via a difficulty check (keeping only questions GPT-4o with basic search fails repeatedly), yielding 3,250 high-quality QA pairs; and (2) end-to-end multi-turn reinforcement learning with GRPO, plus a Jaccard-similarity-based redundancy penalty that discourages repeated queries. Applied to QwQ-32B, DeepDive raises BrowseComp accuracy from 1.3% to 15.3%, outperforming WebSailor-32B and DeepSeek-R1, with test-time scaling improving results further (up to ~24.8% via parallel sampling). It also surpasses GPT-4o on simpler benchmarks like WebWalker (63.9%). Code, models, and data are open-sourced. The paper (arXiv:2509.10446) acknowledges a remaining gap versus OpenAI's DeepResearch (51.5%) and issues like over-searching on easy questions.

Introduction

When large language models are equipped with web browsers, a new class of task emerges: deep search — questions that require browsing, filtering, and synthesizing information across potentially hundreds of web pages. On benchmarks like BrowseComp, even strong open-source models fail badly: DeepSeek-R1 achieves only 2–3% accuracy, while OpenAI's DeepResearch exceeds 50%.

DeepDive, a framework developed by researchers at Tsinghua University, addresses this gap not by simply attaching a search engine to an LLM, but by teaching models to search with patience and strategy — like a real researcher.

The Problem

Simple factual questions ("Who won the 2024 Nobel Prize in Physics?") are easy for LLMs. But BrowseComp-style questions are different: they describe targets only through obscure, obfuscated attributes, requiring many rounds of search and reasoning. The failure mode of open models is premature hallucination — after one or two unsuccessful searches, they fabricate an answer. And crucially, the internet lacks sufficiently difficult, human-annotated training data for this skill.

Key Points

DeepDive's solution combines two innovations:

1. Automatic Data Synthesis via Knowledge Graphs

Starting from a knowledge graph, the system performs random walks of 5–9 hops, producing attribute-enhanced paths such as [organization founded in late 1940s] → [person born mid-1980s] → … → [AFC Cup].
A frontier model (Gemini-2.5-Pro) then obscures entities: exact years become decades, names become descriptive traits, making questions un-searchable directly.

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

A difficulty filter keeps only questions that GPT-4o (with basic search) fails to answer across four attempts.
The pipeline yields 3,250 high-quality deep-search QA pairs at a fraction of human annotation cost.

2. Multi-Turn Reinforcement Learning

Trajectories interleave 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}}]

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 novel redundancy penalty based on Jaccard similarity discourages repeated identical queries:

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 redundant tool calls by ~14% and improved late-stage accuracy by ~20%.

Results

Applied to QwQ-32B, BrowseComp accuracy rose from 1.3% (base) → 9.5% (SFT) → 15.3% (RL), beating WebSailor-32B (10.5%) and DeepSeek-R1 (2.0%) among open models.
Test-time scaling: raising max tool calls from 8 to 128 lifted BrowseComp success from 8% to 15%, showing genuine deeper exploration rather than random retrying.
Parallel sampling: running 8 independent attempts and choosing the answer with the fewest tool calls boosted accuracy from 12.0% to 24.8% — less searching correlates with higher model confidence.
Ablations: strict format rewards were essential for learning; HotpotQA-based training data plateaued far below DeepDive's synthetic data (9.2% vs 12.0% at RL stage), confirming that data difficulty determines capability ceiling.
Generalization: on simpler benchmarks (HotpotQA, Frames, WebWalker), DeepDive-32B outperformed GPT-4o and Claude-3.7-Sonnet, e.g., 63.9% on WebWalker vs DeepSeek-R1's 38.6%.
Data contamination check: n-gram analysis found >97% of training samples had <20% overlap with the test set; no sample reached serious contamination levels.

Limitations

A large gap remains versus OpenAI's DeepResearch (51.5%), attributed to the difficulty ceiling of automatically synthesized data.
Models sometimes over-search easy questions; future work needs rewards that adapt search depth to question difficulty.

Open Source

All code, models, and data are released on GitHub. The project builds on open models (GLM-4, QwQ), the Slime RL framework, and Serper/Jina APIs.

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. 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 marks a milestone: it shows the open-source community can tackle problems once thought to require frontier labs, evolving AI from a "Wikipedia-reciting parrot" into a strategic researcher capable of sustained, deliberate information foraging.