# CoEvoKG: Co-Evolving Knowledge Graphs with Self-Evolving Search Agents

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Web, search, and research agents, one of 16 directions in LLM agents and tool use.
- Builds on 24 of its 30 references that are in the map.
- First posted on arXiv 3 Aug 2026.

## Placed in

- LLM agents and tool use / [Web, search, and research agents](https://mlsanity.com/agents/web-search-and-research-agents/)
- Synthetic data and self-improvement for LLMs / [Self-evolving search agents](https://mlsanity.com/synth/self-evolving-search-agents/)

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [Self-Instruct: Aligning Language Models with Self-Generated Instructions](https://mlsanity.com/paper/2212.10560/) (2022)
- [HybridFlow: A Flexible and Efficient RLHF Framework](https://mlsanity.com/paper/2409.19256/) (2024)
- [Self-RAG: Learning to Retrieve, Generate, and Critique through Self-Reflection](https://mlsanity.com/paper/2310.11511/) (2023)
- [From Local to Global: A Graph RAG Approach to Query-Focused Summarization](https://mlsanity.com/paper/2404.16130/) (2024)
- [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)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memories](https://mlsanity.com/paper/2212.10511/) (2022)
- [Self-Play Fine-Tuning Converts Weak Language Models to Strong Language Models](https://mlsanity.com/paper/2401.01335/) (2024)
- [Absolute Zero: Reinforced Self-play Reasoning with Zero Data](https://mlsanity.com/paper/2505.03335/) (2025)
- [DeepResearcher: Scaling Deep Research via Reinforcement Learning in Real-world Environments](https://mlsanity.com/paper/2504.03160/) (2025)
- [REINFORCE++: Stabilizing Critic-Free Policy Optimization with Global Advantage Normalization](https://mlsanity.com/paper/2501.03262/) (2025)
- [Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph](https://mlsanity.com/paper/2307.07697/) (2023)
- [The Landscape of Agentic Reinforcement Learning for LLMs: A Survey](https://mlsanity.com/paper/2509.02547/) (2025)
- [Intrinsic Motivation and Automatic Curricula via Asymmetric Self-Play](https://mlsanity.com/paper/1703.05407/) (2017)
- [DeepDive: Advancing Deep Search Agents with Knowledge Graphs and Multi-Turn RL](https://mlsanity.com/paper/2509.10446/) (2025)
- [Beyond Pass@1: Self-Play with Variational Problem Synthesis Sustains RLVR](https://mlsanity.com/paper/2508.14029/) (2025)
- [Do Not Let Low-Probability Tokens Over-Dominate in RL for LLMs](https://mlsanity.com/paper/2505.12929/) (2025)
- [EPERM: An Evidence Path Enhanced Reasoning Model for Knowledge Graph Question and Answering](https://mlsanity.com/paper/2502.16171/) (2025)

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

- [Dr. Free: You Don't Need Difficulty Rewards for Self-Evolving Search Agents](https://mlsanity.com/paper/2609.33565/) (2026)
- [SIPO: Selective-Inference Policy Optimization for Tree-Structured Agentic RL](https://mlsanity.com/paper/2609.34805/) (2026)
- [UniOPSD: Unifying Outcome and Hindsight Feedback for Agentic Reinforcement Learning](https://mlsanity.com/paper/2609.34810/) (2026)

## Abstract (arXiv)

Large language models can improve with reinforcement learning for search agents, yet existing self play agents repeatedly generate tasks while discarding the knowledge gained during successful searches. We introduce CoEvoKG, a framework that turns a knowledge graph into both a source of verifiable training tasks and a persistent evidence memory for agent evolution. CoEvoKG jointly trains a task generator and a search agent: the generator creates multihop questions from entity chains sampled from the knowledge graph, while the agent learns from rewards for answer correctness and search trajectories whose entity paths are supported by graph evidence. When a search succeeds, CoEvoKG verifies and deduplicates the retrieved evidence, then writes it back to the corresponding graph nodes and edges. Future rounds reuse this enriched graph for task generation and reward computation, closing the loop between model self evolution and knowledge accumulation. Experiments on six QA benchmarks (NQ, TriviaQA, PopQA, HotpotQA, 2WikiMultiHopQA, and Bamboogle) with three backbone models show that CoEvoKG improves macro average accuracy over the corresponding base models by +11.2, +10.1, and +11.6 points on Qwen2.5-3B-Instruct, Qwen2.5-7B-Instruct, and Llama-3.1-8B-Instruct, respectively. Under matched training budgets, CoEvoKG further improves over competitive self play baselines and RL baselines for search agents by +2.6 to +3.7 macro average points across the three backbones. Code is available at https://github.com/lazzy1225/CoEvoKG.