PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Rui Lu, Zhenyu Hou, Zihan Wang, Hanchen Zhang, Xiao Liu, Yujiang Li, Shi Feng, Jie Tang, Yuxiao Dong

arXiv:2509.10446v2cs.CL

TL;DR

Open models lag in deep search, with limited long-horizon browsing reasoning and insufficiently difficult supervised data. DeepDive synthesizes hard questions from knowledge graphs and applies end-to-end multi-turn reinforcement learning; DeepDive-32B achieves 15.3% accuracy on BrowseComp, a competitive open-source result.

  • Problem

    Open models lag in deep search, while hard-to-find training data is scarce and existing browsing agents primarily address direct search tasks.

    Source: §1 · p. 2

  • Method

    DeepDive synthesizes challenging deep-search questions from open knowledge graphs and uses end-to-end multi-turn reinforcement learning with a redundancy penalty for repeated similar queries.

    Source: §1 · pp. 2–3

  • Results

    15.3% accuracy on BrowseComp makes DeepDive-32B a competitive open-source result, surpassing WebSailor, Search-o1, and DeepSeek-R1-Browse.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Experiments report that multi-turn RL improves DeepDive performance across challenging benchmarks, while tool-call budgets and parallel sampling support test-time scaling.

    Source: §6 · p. 12

    The difficulty ceiling of the synthesized data remains below BrowseComp, and training primarily on difficult data has led to an over-search phenomenon.

    Source: §7 · p. 12

Abstract

from arXiv · show

Augmenting large language models (LLMs) with browsing tools substantially improves their potential as deep search agents to solve complex, real-world tasks. Yet, open LLMs still perform poorly in such settings due to limited long-horizon reasoning capacity with browsing tools and the lack of sufficiently difficult supervised data. To address these challenges, we present DeepDive to advance deep search agents. First, we propose a strategy to automatically synthesize complex, difficult, and hard-to-find questions from open knowledge graphs. Second, we apply end-to-end multi-turn reinforcement learning (RL) to enhance LLMs' long-horizon reasoning with deep search. To encourage diversity and reduce redundancy, we design a redundancy penalty that discourages repeated similar queries. Experiments show that DeepDive-32B achieves a new open-source competitive result on BrowseComp, outperforming WebSailor, DeepSeek-R1-Browse, and Search-o1. We demonstrate that multi-turn RL training improves deep search ability and significantly contributes to the performance improvements across multiple benchmarks. We observe that DeepDive enables test-time scaling of tool calls and parallel sampling. All datasets, models, and code are publicly available at https://github.com/THUDM/DeepDive.

1 Introduction

Open models lag in deep search amid a shortage of hard-to-find data and limited long-horizon reasoning with browsing tools. DeepDive combines knowledge-graph question synthesis with end-to-end multi-turn reinforcement learning, achieving a competitive open-source result on BrowseComp.

1 Introduction

  • Open models lag proprietary deep-search agents, while existing QA datasets often use simpler questions and browsing agents focus on direct search tasks.Deep-search questions can involve multiple blurry entities and require long-horizon reasoning; combining that reasoning with tool use remains an open question.Source: §1 · p. 2
  • 15.3% accuracy on BrowseComp makes DeepDive-32B a competitive open-source result, surpassing WebSailor, Search-o1, and DeepSeek-R1-Browse.The framework also benefits significantly from end-to-end multi-turn RL training.Source: §1 · p. 3
  • DeepDive synthesizes challenging deep-search QA pairs from open knowledge graphs and trains agents with end-to-end multi-turn reinforcement learning.A redundancy penalty discourages repeated similar queries to encourage diverse, efficient search.Source: §1 · pp. 2–3
  • The semi-automated i.i.d. QA synthesis study raises 32B-model BrowseComp accuracy to 22.2% using that data alone.Both KG-based and semi-automated data are adopted in open GLM-4.5 and GLM-4.6 models.Source: §1 · p. 3

2 The DeepDive Method

DeepDive pairs knowledge-graph-based synthesis of challenging deep-search questions with end-to-end multi-turn RL to train agents for long-horizon reasoning and browsing.

2 The DeepDive Method

  • Deep-search training data must pose difficult questions because relevant information can be scattered, conflicting, and hard to locate, while manual annotation is costly to scale.Source: §2.1 · p. 3

2.1 Automated Data Synthesis from Knowledge Graphs

  • Random walks create long, multi-hop knowledge-graph paths, and LLM obfuscation of attribute-rich paths turns terminal-node attributes into answers to harder questions.The method uses longer paths (for example, k > 5) to increase potential reasoning complexity and can generalize specific dates into ranges.Source: §2.1 · p. 4
  • Degree filtering avoids overly popular or poorly expandable nodes, while an LLM selects the next candidate that best fits the existing path.A frontier model tests each question four times, retaining it only if the model fails all four attempts.Source: §2.1 · pp. 4–5

2.2 End-to-End Multi-Turn Reinforcement Learning

  • Multi-turn GRPO trains agents on sampled tool-use trajectories, rewarding correctly formatted reasoning and actions only when the final answer matches ground truth.An LLM judge verifies answers because entities may have multiple valid representations.Source: §2.2 · pp. 5–6
  • A Jaccard-similarity penalty discourages repeated queries, with lower within-trajectory query similarity indicating more diverse exploration.The reward combines correctness with a redundancy penalty to encourage search diversity.Source: §2.2 · pp. 5–6

3 Experiments

DeepDive combines challenging synthetic supervision with end-to-end multi-turn RL for deep search. Its 32B model is competitive among open agents, and further results examine tool-call scaling and reward components.

3.1 Setup

  • The setup evaluates four deep-search benchmarks and constructs KG-based QA data from long-chain paths, splitting 3,250 pairs into 1,016 SFT and 2,234 RL samples.BrowseComp evaluation uses a fixed 266-sample subset during RL training and the full 1,266-instance benchmark after training saturates.Source: §3.1 · pp. 6–7

3.2 Overall Performance

  • On BrowseComp-266, accuracy and tool-call counts rise during RL training, indicating deeper search alongside improving performance.The reported gains generalize to unseen samples.Source: Figure 5 · p. 7, §3.2 · p. 7
  • 15.3% BrowseComp accuracy places DeepDive-32B behind OpenAI’s DeepResearch but ahead of other open-source models and agents.The 32B SFT model scores 9.5% on BrowseComp, and RL improves the SFT version across each benchmark; gains are less pronounced for the 9B model.Source: §3.2 · p. 7, Table 1 · p. 8

3.3 Test-Time Scaling for DeepDive

  • Increasing the tool-call budget improves BrowseComp and BrowseComp-ZH performance; at 16 or more calls, RL-trained DeepDive-32B outperforms its SFT-only counterpart.On BrowseComp-266, selecting the parallel-sample answer with the fewest tool calls reaches 24.8%, versus 18.8% for majority voting and 12.0% without selection.Source: §3.3 · pp. 8–9, Figure 6 · p. 9

3.4 Ablation Study

  • On BrowseComp-266, the strict format reward keeps accuracy about 2 points higher during training, while the redundancy penalty raises later accuracy to about 20% and cuts tool calls by roughly 14%.The authors report that the redundancy penalty improves search efficiency without sacrificing performance.Source: §3.4 · p. 9, Figure 7 · p. 9
  • Synthetic deep-search QA data improves accuracy and tool use across benchmarks in SFT, while synthetic-data RL yields larger gains than HotpotQA-based RL, especially on BrowseComp-266.The authors conclude that synthetic data supports both training stages and long-horizon deep search.Source: §3.4 · pp. 9–10

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

The additional study develops a semi-automated workflow for creating difficult, verifiable deep-search questions with annotator and model collaboration. RL with i.i.d. data improves BrowseComp and Chinese benchmarks, while SEAL-0 remains largely unchanged.

i.i.d. Data Synthesis

  • The semi-automated workflow has annotators and a search-enabled model find entities, construct obscured multi-hop questions, and verify answers, discarding incorrect or ambiguous samples.The annotator also records the model’s answer time to identify harder, higher-quality questions.Source: §4 · p. 10
  • The workflow produces 2,997 English and 275 Chinese challenging deep-search QA pairs.The same procedure is applied to Chinese websites to enhance multilingual performance.Source: §4 · p. 10

RL with i.i.d. Deep Search Data

  • DeepDive-32B-RL reaches 20.8% accuracy on full BrowseComp, a 40% improvement over the previous best score of 15.3%.The model also gains considerably on BrowseComp-ZH and Xbench-DeepSearch; SEAL-0 remains largely unchanged.Source: §4 · pp. 10–11
  • SEAL-0 performance remains largely unchanged; the authors identify recognizing and selecting among search results as a future enhancement target.They attribute the unchanged result to the dataset’s focus on that capability.Source: §4 · p. 11

Data Contamination Analysis

  • More than 97% of training samples are classified as Clean, and none are Dirty under the paper’s n-gram-overlap analysis.The authors interpret this as indicating almost no test-data leakage in the constructed training dataset.Source: §4 · p. 11, Table 4 · p. 11

5 Related Work

Related work spans verifiable-reward reinforcement learning and deep-search agents. The paper describes a persistent performance gap between open-source and proprietary systems.

Reinforcement Learning for LLMs

Deep Search Agents

  • ReAct [Yao et al., 2023] interleaves reasoning and actions; proprietary DeepResearch [OpenAI, 2025] and Gemini Deep Research are described as near-expert information-seeking systems.Open-source approaches include RL-based agents and framework-based systems targeting long-form generation.Source: §5 · pp. 11–12
  • The paper identifies a significant gap between open-source and proprietary deep-search models.The passage presents this as an ongoing gap despite recent open-source agent work.Source: §5 · p. 12

6 Conclusion

DeepDive combines automated deep-search QA synthesis and end-to-end multi-turn RL. The conclusion reports competitive BrowseComp accuracy and test-time scaling with tool-call budgets and parallel sampling.

6 Conclusion

  • DeepDive-32B reaches 15.3% accuracy on BrowseComp, surpassing larger agents and multiple strong proprietary baselines while setting a competitive open-source result.Complex supervision and multi-turn RL jointly ground tool use; performance scales with tool-call budgets and parallel sampling, and hard-problem skills transfer to simpler settings.Source: §6 · p. 12
  • DeepDive generates ambiguity-rich, multi-hop questions with hidden cues and trains with multi-turn RL that uses a redundancy penalty to encourage diverse, efficient search.The conclusion frames these as the data and training components of the approach.Source: §6 · p. 12
  • The conclusion reports that skills learned on hard problems transfer to simpler settings.Source: §6 · p. 12

7 Limitation

DeepDive’s training data has a difficulty ceiling below BrowseComp, and its difficult-data training is associated with over-search.

7 Limitation

  • The synthesized data’s difficulty ceiling remains below BrowseComp, indirectly contributing to DeepDive-32B’s substantially lower performance than o3 with browsing.The paper says the methods support competitive results among open-source models, but their difficulty ceiling remains lower than datasets like BrowseComp.Source: §7 · p. 12
  • Training primarily on difficult data has led to an “over-search” phenomenon in DeepDive-32B.Source: §7 · p. 12
  • The authors identify optimal RL training steps and more appropriate reward mechanisms as future research directions.Source: §7 · p. 12
  • The data synthesis methods are described as producing high-quality data with guaranteed difficulty and accuracy, supporting competitive open-source results.Source: §7 · p. 12

A Generalization on Simple Search Tasks

On simpler search benchmarks, DeepDive-32B outperforms the reported baselines, with RL providing additional improvements across all three benchmarks.

A Generalization on Simple Search Tasks

B Case Study

The case study tracks how query-operator use changes during RL training, with quoting and minus usage showing different trends and OR usage reported inconsistently.

B Case Study

  • The study measures the fractions of generated BrowseComp-266 queries using quoted phrases, leading-minus exclusions, and OR alternatives.Source: B Case Study · p. 16
  • Quote Usage rises from around 30% to 40% early, then falls below 25%, while Minus Usage climbs from 14% to 18% throughout training.Source: Figure 9 · p. 16, B Case Study · p. 16
  • From Figure 9, OR Usage steadily grows from approximately 2% to 8%, while Quote Usage rises from around 30% to 40% early in training before gradually declining below 25%.Source: B Case Study · p. 16

Related papers

Loading 2509.10446v2…