Research map / Large language models / Retrieval and knowledge

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

NeurIPS 2026 · Large language models › Retrieval and knowledge · approach: Explanatory and multiple-choice QA benchmarks · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Reuses knowledge-graph construction paths both to ground Proposer question generation and to give Solver partial credit (Waypoint Coverage Reward) for incorrect search trajectories in Search Self-Play.

Problem

Search Self-Play (SSP) suffers from invalid questions generated from isolated answer entities early in training, and from sparse binary Solver rewards that discard partial progress in multi-step search.

Approach

Uses the same LLM-guided Wikidata KG path as both relational context for the Proposer and as waypoints; incorrect Solver trajectories get graded partial credit proportional to coverage of intermediate path entities, while correct answers keep full reward.

Key results

• On Qwen2.5-7B-Base, average score rises from 44.9 (SSP) to 49.4 across seven benchmarks; Multi-HopQA average from 34.2 to 41.5.
• On Qwen3-8B, the ablation shows average going from 54.9 (SSP) to 56.1 with the full method; Bamboogle 60.8 to 65.2.
• Valid early-stage question rate of SSP is only 8.3% under the RAG-based verifier, the motivation for KG-grounded construction.

Surprising findings

• A control that uses the same KG terminal answer entities but vanilla SSP training slightly decreases the average (-0.8 and -0.7), so answer distribution alone does not explain the gains.
• ZeroSearch-7B is an exception where gains on multi-hop benchmarks do not follow the general pattern.

Limitations

• Evaluated only on factoid multi-hop QA grounded in Wikidata; transfer to other structured resources or tasks is untested.
• Subgraph quality depends on the external LLM selector (DeepSeek-V3.2).
• WCR coverage correlates only modestly with correctness (Spearman 0.16) and may reflect trajectory length or search intensity.

Experimental setup

Datasets: Wikidata NQ TriviaQA PopQA HotpotQA 2WikiMultiHopQA MuSiQue Bamboogle

Benchmarks: NQ TriviaQA PopQA HotpotQA 2WikiMultiHopQA MuSiQue Bamboogle

Metrics: LLM-as-a-Judge accuracy exact match F1

Baselines: Search Self-Play (SSP) Dr.Zero ZeroSearch Search-R1

Builds on: Search Self-Play GRPO Search-R1 REINFORCE

Closest papers by meaning

• MAGE: Multi-Agent Self-Evolution with Co-Evolutionary Knowledge Graphs (NeurIPS 2026 · similarity 0.89)
• Explore-on-Graph: Incentivizing Autonomous Exploration of Large Language Models on Knowledge Graphs with Path-refined Reward Modeling (ICLR 2026 · similarity 0.88)
• Search-R2: Enhancing Search-Integrated Reasoning via Actor-Refiner Collaboration (ICML 2026 · similarity 0.87)
• AgentHop: A Diagnostic Benchmark for Agentic Multi-Hop Scientific Question Answering (NeurIPS 2026 · similarity 0.87)
• SD-Search: Hindsight Self-Distillation for Search-Augmented Reasoning (NeurIPS 2026 · similarity 0.87)
• ReSeek: A Self-Correcting Framework for Search Agents with Instructive Rewards (ICML 2026 · similarity 0.86)