# DynaSearcher: Dynamic Knowledge Graph Augmented Search Agent via Multi-Reward Reinforcement Learning

arXiv: https://arxiv.org/abs/2507.17365 · HTML: https://mlsanity.com/paper/2507.17365/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 16 of its 25 references that are in the map.
- First posted on arXiv 23 Jul 2025.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)
- LLM agents and tool use / [Web, search, and research agents](https://mlsanity.com/agents/web-search-and-research-agents/)

## Builds on (most cited first, 16 of 16)

- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Self-RAG: Learning to Retrieve, Generate, and Critique through Self-Reflection](https://mlsanity.com/paper/2310.11511/) (2023)
- [Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning](https://mlsanity.com/paper/2503.09516/) (2025)
- [Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps](https://mlsanity.com/paper/2011.01060/) (2020)
- [Text Embeddings by Weakly-Supervised Contrastive Pre-training](https://mlsanity.com/paper/2212.03533/) (2022)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [Interleaving Retrieval with Chain-of-Thought Reasoning for Knowledge-Intensive Multi-Step Questions](https://mlsanity.com/paper/2212.10509/) (2022)
- [PyTorch FSDP: Experiences on Scaling Fully Sharded Data Parallel](https://mlsanity.com/paper/2304.11277/) (2023)
- [Search-o1: Agentic Search-Enhanced Large Reasoning Models](https://mlsanity.com/paper/2501.05366/) (2025)
- [ReTool: Reinforcement Learning for Strategic Tool Use in LLMs](https://mlsanity.com/paper/2504.11536/) (2025)
- [KEPLER: A Unified Model for Knowledge Embedding and Pre-trained Language Representation](https://mlsanity.com/paper/1911.06136/) (2019)
- [Enhancing Retrieval-Augmented Large Language Models with Iterative Retrieval-Generation Synergy](https://mlsanity.com/paper/2305.15294/) (2023)
- [Fact, Fetch, and Reason: A Unified Evaluation of Retrieval-Augmented Generation](https://mlsanity.com/paper/2409.12941/) (2024)
- [From Web Search towards Agentic Deep Research: Incentivizing Search with Reasoning Agents](https://mlsanity.com/paper/2506.18959/) (2025)
- [s3: You Don't Need That Much Data to Train a Search Agent via RL](https://mlsanity.com/paper/2505.14146/) (2025)
- [MoreHopQA: More Than Multi-hop Reasoning](https://mlsanity.com/paper/2406.13397/) (2024)

## Built on by (most cited first, 14 of 14)

- [VCRL: Variance-based Curriculum Reinforcement Learning for Large Language Models](https://mlsanity.com/paper/2509.19803/) (2025)
- [A Comprehensive Survey on Reinforcement Learning-based Agentic Search: Foundations, Roles, Optimizations, Evaluations, and Applications](https://mlsanity.com/paper/2510.16724/) (2025)
- [Adaptation of Agentic AI: A Survey of Post-Training, Memory, and Skills](https://mlsanity.com/paper/2512.16301/) (2025)
- [AgentMath: Empowering Mathematical Reasoning for Large Language Models via Tool-Augmented Agent](https://mlsanity.com/paper/2512.20745/) (2025)
- [Search-E1: Self-Distillation Drives Self-Evolution in Search-Augmented Reasoning](https://mlsanity.com/paper/2605.22511/) (2026)
- [Erase to Improve: Erasable Reinforcement Learning for Search-Augmented LLMs](https://mlsanity.com/paper/2510.00861/) (2025)
- [RE-Searcher: Robust Agentic Search with Goal-oriented Planning and Self-reflection](https://mlsanity.com/paper/2509.26048/) (2025)
- [MemSearch-o1: Empowering Large Language Models with Reasoning-Aligned Memory Growth in Agentic Search](https://mlsanity.com/paper/2604.17265/) (2026)
- [PVPO: Pre-Estimated Value-Based Policy Optimization for Agentic Reasoning](https://mlsanity.com/paper/2508.21104/) (2025)
- [From Evidence to Trajectory: Abductive Reasoning Path Synthesis for Retrieval-Augmented Generation Agents Development](https://mlsanity.com/paper/2509.23071/) (2025)
- [ADRA-Bank: A Modular Benchmark for Academic Deep Research Agents](https://mlsanity.com/paper/2512.00986/) (2025)
- [Beyond Trajectory Rewards: Step-level Credit Assignment for Agentic Search via Graph Modeling](https://mlsanity.com/paper/2605.29697/) (2026)
- [Plan Then Retrieve: Reinforcement Learning-Guided Complex Reasoning over Knowledge Graphs](https://mlsanity.com/paper/2510.20691/) (2025)
- [HERALD: Counterfactual Audits and Minimal Repairs for Proof-of-Retrieval Rewards](https://mlsanity.com/paper/2608.06012/) (2026)

## Abstract (arXiv)

Multi-step agentic retrieval systems based on large language models (LLMs) have demonstrated remarkable performance in complex information search tasks. However, these systems still face significant challenges in practical applications, particularly in generating factually inconsistent intermediate queries and inefficient search trajectories, which can lead to reasoning deviations or redundant computations. To address these issues, we propose DynaSearcher, an innovative search agent enhanced by dynamic knowledge graphs and multi-reward reinforcement learning (RL). Specifically, our system leverages knowledge graphs as external structured knowledge to guide the search process by explicitly modeling entity relationships, thereby ensuring factual consistency in intermediate queries and mitigating biases from irrelevant information. Furthermore, we employ a multi-reward RL framework for fine-grained control over training objectives such as retrieval accuracy, efficiency, and response quality. This framework promotes the generation of high-quality intermediate queries and comprehensive final answers, while discouraging unnecessary exploration and minimizing information omissions or redundancy. Experimental results demonstrate that our approach achieves state-of-the-art answer accuracy on six multi-hop question answering datasets, matching frontier LLMs while using only small-scale models and limited computational resources. Furthermore, our approach demonstrates strong generalization and robustness across diverse retrieval environments and larger-scale models, highlighting its broad applicability.