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

• URL: http://arxiv.org/abs/2605.05702v1
• Date: Thu, 07 May 2026 05:46:53 GMT
• Title: Knowledge-Graph Paths as Intermediate Supervision for Self-Evolving Search Agents
• Abstract summary: Self-evolving search agents generate and solve their own search tasks.<n>We build on the Search Self-Play (SSP) framework in which questions are generated and answered via multi-step search and reasoning.<n>We address two bottlenecks by reusing knowledge-graph paths as construction-derived intermediate supervision for both question construction and reward shaping.
• Score: 21.366388027090736
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• BiCAA: Bidirectional Credit Assignment for Search-Augmented Agent [7.0011576165695]
  BiCAA builds bidirectional process rewards by fusing two complementary signals: forward solvability gain and hindsight success criticality.<n> Experiments on search-augmented QA benchmarks show that BiCAA stabilizes policy optimization, reduces redundant search behavior, and achieves competitive performance.
  arXiv  Detail & Related papers  (2026-08-02T15:41:57Z)
• OpenSearch-VL: An Open Recipe for Frontier Multimodal Search Agents [50.79529228477821]
  We introduce OpenSearch-VL, a fully open-source recipe for training frontier multimodal deep search agents with agentic reinforcement learning.<n>First, we curated a dedicated pipeline to construct high-quality training data through Wikipedia path sampling, fuzzy entity rewriting, and source-anchor visual grounding.<n>Besides, we design a diverse tool environment that unifies text search, image search, OCR, cropping, sharpening, super-resolution, and perspective correction.
  arXiv  Detail & Related papers  (2026-05-06T17:50:38Z)
• PRAISE: Prefix-Based Rollout Reuse in Agentic Search Training [28.912613644535668]
  We present PRAISE, a framework for improving data efficiency and credit assignment in agentic search training.<n>Our method uses a single shared model for both search policy learning and prefix answer evaluation.<n>Experiments on multi-hop QA benchmarks show that PRAISE consistently improves performance over strong baselines.
  arXiv  Detail & Related papers  (2026-04-04T10:23:46Z)
• Search-R2: Enhancing Search-Integrated Reasoning via Actor-Refiner Collaboration [49.9937230730202]
  We propose Search-R2, a novel Actor-Refiner collaboration framework that enhances reasoning through targeted intervention.<n>Our approach decomposes the generation process into an Actor, which produces initial reasoning trajectories.<n>We show that Search-R2 consistently outperforms strong RAG and RL-based baselines across model scales.
  arXiv  Detail & Related papers  (2026-02-03T15:32:09Z)
• SAGE: Steerable Agentic Data Generation for Deep Search with Execution Feedback [68.60326181052658]
  We propose an agentic pipeline that automatically generates high quality, difficulty-controlled deep search question-answer pairs.<n>Our pipeline, SAGE, consists of a data generator which proposes QA pairs and a search agent which attempts to solve the generated question.<n>Our intrinsic evaluation shows SAGE generates questions that require diverse reasoning strategies, while significantly increases the correctness and difficulty of the generated data.
  arXiv  Detail & Related papers  (2026-01-26T06:37:56Z)
• PRISMA: Reinforcement Learning Guided Two-Stage Policy Optimization in Multi-Agent Architecture for Open-Domain Multi-Hop Question Answering [26.994531058178982]
  Answering real-world open-domain questions over massive corpora is a critical challenge in Retrieval-Augmented Generation (RAG) systems.<n>Recent research employs reinforcement learning (RL) to end-to-end optimize the retrieval-augmented reasoning process.<n>We propose PRISMA, a decoupled-guided framework featuring a Plan-Retrieve-Inspect-Memoize architecture.
  arXiv  Detail & Related papers  (2026-01-09T01:38:38Z)
• Modeling Contextual Passage Utility for Multihop Question Answering [3.8786514101828167]
  Multihop Question Answering (QA) requires systems to identify and synthesize information from multiple text passages.<n>We propose a lightweight approach to model contextual passage utility, accounting for inter-passage dependencies.<n>We leverage the reasoning traces from an advanced reasoning model to capture the order in which passages are used to answer a question.
  arXiv  Detail & Related papers  (2025-12-06T14:54:47Z)
• Thinking Forward and Backward: Multi-Objective Reinforcement Learning for Retrieval-Augmented Reasoning [137.33138614095435]
  Retrieval-augmented generation (RAG) has proven to be effective in mitigating hallucinations in large language models.<n>Recent efforts have incorporated search-based interactions into RAG, enabling iterative reasoning with real-time retrieval.<n>We propose Bi-RAR, a novel retrieval-augmented reasoning framework that evaluates each intermediate step jointly in both forward and backward directions.
  arXiv  Detail & Related papers  (2025-11-12T08:29:39Z)
• Decomposition-Enhanced Training for Post-Hoc Attributions In Language Models [64.49342399229529]
  We argue that post-hoc attribution can be reframed as a reasoning problem, where answers are decomposed into constituent units, each tied to specific context.<n>We introduce DecompTune, a post-training method that teaches models to produce answer decompositions as intermediate reasoning steps.<n>Across extensive experiments and ablations, DecompTune substantially improves attribution quality, outperforming prior methods and matching or exceeding state-of-the-art frontier models.
  arXiv  Detail & Related papers  (2025-10-29T17:58:59Z)
• BMGQ: A Bottom-up Method for Generating Complex Multi-hop Reasoning Questions from Semi-structured Data [8.52473384574856]
  We present an automated framework for generating high-difficulty, training-ready multi-hop questions from semi-structured knowledge sources.<n>The system grows diverse, logically labeled evidence clusters through Natural Language Inference (NLI)-based relation typing and diversity-aware expansion.
  arXiv  Detail & Related papers  (2025-10-28T07:43:15Z)
• Reinforcing Compositional Retrieval: Retrieving Step-by-Step for Composing Informative Contexts [67.67746334493302]
  Large Language Models (LLMs) have demonstrated remarkable capabilities across numerous tasks, yet they often rely on external context to handle complex tasks.<n>We propose a tri-encoder sequential retriever that models this process as a Markov Decision Process (MDP)<n>We show that our method consistently and significantly outperforms baselines, underscoring the importance of explicitly modeling inter-example dependencies.
  arXiv  Detail & Related papers  (2025-04-15T17:35:56Z)
• Divide-and-Conquer: Tree-structured Strategy with Answer Distribution Estimator for Goal-Oriented Visual Dialogue [30.126882554391837]
  Tree-Structured Strategy with Answer Distribution Estimator (TSADE)<n>We propose a Tree-Structured Strategy with Answer Distribution Estimator (TSADE) which guides the question generation by excluding half of the current candidate objects in each round.<n>We experimentally demonstrate that our method can enable the agents to achieve high task-oriented accuracy with fewer repeating questions and rounds compared to traditional ergodic question generation approaches.
  arXiv  Detail & Related papers  (2025-02-09T08:16:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.