# Knowledge-Graph Paths as Intermediate Supervision for Self-Evolving Search Agents

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

## Key facts

- Cited by 2 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 30 of its 38 references that are in the map.
- First posted on arXiv 7 May 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, 30 of 30)

- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [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)
- [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)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [MuSiQue: Multihop Questions via Single-hop Question Composition](https://mlsanity.com/paper/2108.00573/) (2021)
- [Self-Play Fine-Tuning Converts Weak Language Models to Strong Language Models](https://mlsanity.com/paper/2401.01335/) (2024)
- [The Web as a Knowledge-base for Answering Complex Questions](https://mlsanity.com/paper/1803.06643/) (2018)
- [Absolute Zero: Reinforced Self-play Reasoning with Zero Data](https://mlsanity.com/paper/2505.03335/) (2025)
- [R1-Searcher: Incentivizing the Search Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2503.05592/) (2025)
- [DeepResearcher: Scaling Deep Research via Reinforcement Learning in Real-world Environments](https://mlsanity.com/paper/2504.03160/) (2025)
- [WebSailor: Navigating Super-human Reasoning for Web Agent](https://mlsanity.com/paper/2507.02592/) (2025)
- [R-Zero: Self-Evolving Reasoning LLM from Zero Data](https://mlsanity.com/paper/2508.05004/) (2025)
- [ZeroSearch: Incentivize the Search Capability of LLMs without Searching](https://mlsanity.com/paper/2505.04588/) (2025)
- [Agentic Reinforced Policy Optimization](https://mlsanity.com/paper/2507.19849/) (2025)
- [Self-playing Adversarial Language Game Enhances LLM Reasoning](https://mlsanity.com/paper/2404.10642/) (2024)
- [Self-Questioning Language Models](https://mlsanity.com/paper/2508.03682/) (2025)
- [Dr. Zero: Self-Evolving Search Agents without Training Data](https://mlsanity.com/paper/2601.07055/) (2026)
- [EvolveSearch: An Iterative Self-Evolving Search Agent](https://mlsanity.com/paper/2505.22501/) (2025)
- [Search Self-play: Pushing the Frontier of Agent Capability without Supervision](https://mlsanity.com/paper/2510.18821/) (2025)
- [Search-P1: Path-Centric Reward Shaping for Stable and Efficient Agentic RAG Training](https://mlsanity.com/paper/2602.22576/) (2026)
- [Repurposing Synthetic Data for Fine-grained Search Agent Supervision](https://mlsanity.com/paper/2510.24694/) (2025)
- [AceSearcher: Bootstrapping Reasoning and Search for LLMs via Reinforced Self-Play](https://mlsanity.com/paper/2509.24193/) (2025)
- [Stratified GRPO: Handling Structural Heterogeneity in Reinforcement Learning of LLM Search Agents](https://mlsanity.com/paper/2510.06214/) (2025)
- [Beyond Correctness: Rewarding Faithful Reasoning in Retrieval-Augmented Generation](https://mlsanity.com/paper/2510.13272/) (2025)
- [From Superficial to Deep: Integrating External Knowledge for Follow-up Question Generation Using Knowledge Graph and LLM](https://mlsanity.com/paper/2504.05801/) (2025)

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

- [Recursive Self-Improvement in AI: From Bounded Self-Refinement to Autonomous Research Loops](https://mlsanity.com/paper/2607.07663/) (2026)
- [Dr. Free: You Don't Need Difficulty Rewards for Self-Evolving Search Agents](https://mlsanity.com/paper/2609.33565/) (2026)

## Abstract (arXiv)

Self-evolving search agents reduce reliance on human-written training questions by generating and solving their own search tasks. We build on Search Self-Play (SSP), a representative Proposer and Solver framework in which questions are generated and answered via multi-step search and reasoning. In practice, however, SSP faces two bottlenecks: the Proposer constructs questions from isolated answer entities without relational context, yielding many invalid or unverifiable questions in early self-play training, while the Solver receives only a binary outcome reward that discards useful signal from partially on-track search trajectories. We address both bottlenecks by reusing knowledge-graph paths as construction-derived intermediate supervision for both question construction and reward shaping. First, we ground question construction in LLM-guided knowledge-graph subgraphs, providing relational context for the Proposer. Second, we observe that constructing and solving a multi-hop question can involve overlapping intermediate entities: the factual bridges used to formulate the question may provide approximate waypoints for answering it. Exploiting this overlap, we introduce Waypoint Coverage Reward (WCR), which grants graded partial credit to incorrect Solver trajectories according to their coverage of entities on the construction path, while preserving full reward for correct answers. Across seven QA benchmarks and nine model configurations, our approach improves the average score over standard SSP in all configurations, including notable gains on multi-hop QA tasks. These results suggest that knowledge-graph paths can be reused as lightweight intermediate supervision, providing both relational guidance and process feedback without additional task-specific human annotations or manually labeled process steps.