Knowledge-Graph Paths as Intermediate Supervision for Self-Evolving Search Agents
Introduces knowledge-graph paths as intermediate supervision, improving self-evolving search agents' QA accuracy by 7.3% on multi-hop tasks.
Key Findings
Methodology
Uses knowledge-graph paths for relational context in question generation and introduces Waypoint Coverage Reward (WCR) for partial credit to incorrect trajectories, improving training efficiency.
Key Results
- On Qwen2.5-7B-Base, average accuracy improved from 44.9% to 49.4%, with multi-hop QA accuracy rising from 34.2% to 41.5%.
- Outperformed standard SSP across seven QA benchmarks, with notable gains in multi-hop reasoning tasks.
- WCR significantly improved the distinguishability of failed trajectories, enhancing training signals.
Significance
Reduces reliance on human annotations while enhancing search agents' reasoning and generation capabilities, particularly for complex multi-hop tasks. Opens new avenues for integrating knowledge graphs with LLMs.
Technical Contribution
First to reuse knowledge-graph paths for both question generation and reward shaping, introducing WCR to unify task construction and reward signals, boosting training efficiency.
Novelty
Pioneers the dual-purpose use of knowledge-graph paths as intermediate supervision, combining LLM-guided subgraph extraction with reward design to improve self-evolving search agents.
Limitations
- WCR is limited to tasks supported by structured knowledge graphs, excluding unstructured data scenarios.
- Dependent on knowledge graph quality, which may affect robustness.
- Does not address semantic ambiguity in multi-hop reasoning.
Future Work
Future research could extend WCR to unstructured data tasks and optimize graph extraction algorithms for more complex reasoning scenarios.
AI Executive Summary
Self-evolving search agents aim to reduce reliance on human annotations by generating and solving their own training tasks. However, frameworks like Search Self-Play (SSP) face two major bottlenecks: lack of relational context in question generation, leading to low-quality early training data, and binary reward signals that ignore partial progress in reasoning.
This paper proposes using knowledge-graph paths as intermediate supervision. LLM-guided subgraph extraction provides relational context for question generation, while Waypoint Coverage Reward (WCR) assigns partial credit to incorrect trajectories based on their coverage of intermediate entities. Experiments across seven QA benchmarks show consistent improvements over SSP, with average accuracy increasing by 7.3% on multi-hop tasks.
This approach reduces dependency on human annotations and demonstrates the potential of integrating knowledge graphs with LLMs. Future work could explore extending this method to unstructured data tasks and refining graph extraction techniques for broader applications.
Deep Analysis
Background
Self-evolving search agents have gained traction for reducing human supervision in training. Frameworks like SSP leverage proposer-solver loops for multi-step reasoning but still rely on human validation for question quality.
Core Problem
SSP suffers from two bottlenecks: lack of relational context in question generation, leading to low-quality early data, and binary reward signals that fail to utilize partially correct trajectories, limiting training efficiency.
Innovation
This paper introduces two innovations: 1) LLM-guided subgraph extraction for relational context in question generation, and 2) Waypoint Coverage Reward (WCR) to assign partial credit to incorrect trajectories, improving training signals.
Methodology
- �� Extract subgraphs from knowledge graphs using LLM-guided iterative expansion.
- �� Use subgraphs to provide relational context for question generation.
- �� Introduce WCR to assign partial credit based on waypoint coverage, enhancing solver training.
- �� Optimize solver with GRPO and proposer with REINFORCE.
Experiments
Evaluated across seven QA benchmarks, including NQ, TriviaQA, and HotpotQA, focusing on multi-hop reasoning. Compared against SSP and conducted ablation studies to validate contributions.
Results
On Qwen2.5-7B-Base, average accuracy improved from 44.9% to 49.4%, with multi-hop QA accuracy rising from 34.2% to 41.5%. WCR improved training signal by distinguishing failed trajectories.
Applications
Applicable to multi-hop QA tasks, especially in scenarios requiring complex reasoning, such as knowledge graph QA and search optimization.
Limitations & Outlook
WCR depends on knowledge graph quality and cannot yet extend to unstructured data tasks. Future work should refine graph extraction for broader applications.
Plain Language Accessible to non-experts
Imagine you're navigating a maze to find the exit. The maze has signposts pointing to possible directions, but not directly to the exit. This method adds more signposts, rewarding you even for partially correct paths, helping you find the exit faster.
ELI14 Explained like you're 14
Think of playing a puzzle game where you need to find the right answer. Every time you get closer to the answer, the game gives you a small reward—even if you're not completely correct! This makes learning how to solve puzzles way easier!
Glossary
Knowledge Graph
A structured representation of data using nodes and edges to denote entities and their relationships.
Used to provide relational context for question generation.
Waypoint Coverage Reward (WCR)
A reward mechanism assigning partial credit based on the number of covered path nodes.
Improves training signals for incorrect solver trajectories.
Search Self-Play (SSP)
A closed-loop training framework where a proposer generates questions and a solver answers them.
Baseline method for comparison.
LLM-Guided Subgraph Extraction
Using language models to extract target paths and distractor branches from knowledge graphs.
Provides relational context for question generation.
Multi-Hop QA
Question-answering tasks requiring multi-step reasoning to derive answers.
Core evaluation task for this paper.
Open Questions Unanswered questions from this research
- 1 How can WCR be extended to unstructured data tasks?
- 2 What is the precise impact of knowledge graph quality on training outcomes?
Applications
Immediate Applications
Knowledge Graph QA
Enhances accuracy in complex QA tasks, useful for search engine optimization.
Educational Reasoning Training
Trains students' logical reasoning skills while reducing annotation needs.
Long-term Vision
General Reasoning Agents
Develop systems capable of handling unstructured data reasoning tasks for broader applications.
Abstract
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.