DeepDive: Advancing Deep Search Agents with Knowledge Graphs and Multi-Turn RL

🔥 News

• [2026/06/17] Released the training code with the DeepDive slime rollout setup.
• [2025/10/02] Released the complete data construction pipeline — now fully available in the repository.
• [2025/09/17] QA pairs and SFT trajectories have been fully open-sourced, totaling 4,108 entries. Check them out on Hugging Face Dataset DeepDive.
• Model checkpoints are currently under development – coming soon!

Overview

DeepDive presents an automated approach for training deep search agents that can navigate complex, multi-step information-seeking tasks. Our method combines automated data synthesis from knowledge graphs with end-to-end multi-turn reinforcement learning to create agents capable of sophisticated long-horizon reasoning and web browsing.

Key Features

• Automated Deep Search Data Synthesis: Generate challenging QA pairs from knowledge graphs through controlled random walks
• Multi-Turn RL Training for Browsing: End-to-end reinforcement learning for deep search capabilities
• Test-Time Scaling: Supports scaling via tool calls and parallel sampling

Method Overview

Stage 1: Automated Data Synthesis from Knowledge Graphs

We propose an automated method to synthesize complex, difficult, and hard-to-find questions from open knowledge graphs. The process involves three key steps:

Knowledge Graph Random Walks: Starting from an initial node $v_0$, we navigate through the graph for $k$ steps to form a path $P=[v_0, v_1, \ldots, v_k]$, where each step $(v_i, v_{i+1})$ is a valid edge in the graph. We choose longer path lengths ($k > 5$) to increase reasoning complexity.

Entity Obfuscation: We combine each node $v_i$ in the path with its corresponding attributes to form an attribute-rich path:

$$P_A = [(v_0, [a_0^0, a_0^1, \ldots]), (v_1, [a_1^0, a_1^1, \ldots]), \ldots, (v_k, [a_k^0, a_k^1, \ldots])]$$

An LLM then obfuscates information along the entire path, generalizing specific details and creating "blurry entities" that require deep search to resolve.

Difficulty Filtering: We use a frontier model (GPT-4o) with basic search to attempt each question four times. Only questions that the frontier model fails in all attempts are retained, ensuring high difficulty.

Stage 2: End-to-End Multi-Turn Reinforcement Learning

We apply end-to-end multi-turn RL to enhance the agent's long-horizon reasoning and browsing capabilities. The training process follows an iterative cycle where at step $t$, the agent generates chain-of-thought $c_t$, executes browsing action $a_t$, and observes web content $o_t$.

Multi-Turn GRPO Training: We employ 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)} $$

Strict Binary Rewards: A trajectory receives reward +1 if and only if both format correctness and answer accuracy are satisfied:

$$ r(\mathcal{T}) = \begin{cases} 1, & (\forall i, \text{Format}(c_i, a_i)) \wedge \text{Judge}(a_{\text{eos}}, a^*) \ 0, & \text{otherwise} \end{cases} $$

This strict reward mechanism ensures high-quality trajectories and prevents reward hacking.

For the recommended DeepDive training interface and slime rollout setup, see training/README.md.

Models

Data

Synthetic Dataset Construction

Our automated data synthesis pipeline creates challenging QA pairs through knowledge graph random walks, entity obfuscation, and difficulty filtering. The process uses multi-hop paths (k=5-9) through KILT and AMiner knowledge graphs.

Data Example

Results

Main Results

We evaluate DeepDive on four challenging deep search benchmarks: BrowseComp, BrowseComp-ZH, Xbench-DeepSearch, and SEAL-0. The results demonstrate consistent improvements over existing open-source models.

[!NOTE] * represents reported performance from existing studies. † represents equipping browsing via function call.

Generalization on Simple Search Tasks

We evaluate DeepDive not only on challenging search tasks (e.g., BrowseComp, BrowseComp-ZH) but also on simpler benchmarks such as HotpotQA, Frames, and WebWalker. DeepDive-32B (SFT and RL) consistently outperforms strong baselines, achieving >60 points on WebWalker, surpassing WebShaper-72B (52.2). These results demonstrate DeepDive’s strong and generalizable search capabilities.

Test-Time Scaling

DeepDive demonstrates remarkable test-time scaling capabilities through two mechanisms:

Tool Call Scaling: Allowing DeepDive more tool calls during inference leads to higher accuracy on complex, multi-step tasks. As shown in the BrowseComp and BrowseComp-ZH benchmark results:

• When the maximum number of tool calls is increased, accuracy rises steadily. On BrowseComp, performance improves from 8% accuracy at 8 tool calls to 15% at 128 tool calls, showing that the model benefits from additional search and reasoning opportunities.
• DeepDive-32B consistently outperforms its SFT-only variant, especially when the allowed tool calls exceed 32. This indicates that the reinforcement learning stage better equips the model to utilize long tool call horizons.

Parallel Sampling: Beyond a larger tool call budget, DeepDive leverages parallel sampling to further boost performance. For each question, DeepDive generates 8 independent reasoning trajectories in parallel.

• Three answer selection strategies are considered: single-shot inference, majority voting among samples, and choosing the answer that required the fewest tool calls before submission.
• Empirical analysis reveals a clear trend: answers submitted earlier with fewer tool calls are usually more accurate. In practice, selecting the answer with minimal tool calls among 8 samples raises accuracy from 12.0% (single-shot) to 24.8%, more than doubling performance. Majority voting also helps (18.8% accuracy), but is outperformed by minimal tool-call selection.

Additional Study: Semi-Automated i.i.d. Deep Search QA for RL

To further boost performance on deep search tasks, we create a semi-automated framework for generating i.i.d. QA pairs.

Training with i.i.d. data brings larger improvements. The 32B-RL model reaches 22.2% accuracy on BrowseComp, up from 14.8%, and also performs better on Chinese benchmarks.

[!NOTE] Given the contamination analysis, both the KG data and i.i.d. data are adopted by the open  GLM-4.5 / GLM-4.6 models, which show strong performance on BrowseComp.

Acknowledgments

• Built on top of GLM-4 and QwQ base models
• Uses Slime framework for RL training
• Powered by Serper and Jina APIs for web access

Citation

If you find DeepDive useful for your research, please cite our paper:

@misc{lu2025deepdiveadvancingdeepsearch,
      title={DeepDive: Advancing Deep Search Agents with Knowledge Graphs and Multi-Turn RL},
      author={Rui Lu and Zhenyu Hou and Zihan Wang and Hanchen Zhang and Xiao Liu and Yujiang Li and Shi Feng and Jie Tang and Yuxiao Dong},
      year={2025},
      eprint={2509.10446},
      archivePrefix={arXiv},
      primaryClass={cs.CL},
      url={https://arxiv.org/abs/2509.10446},
}