Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning

• URL: http://arxiv.org/abs/2607.18481v1
• Date: Mon, 20 Jul 2026 19:58:32 GMT
• Title: Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning
• Abstract summary: Search-on-Graph-R1 internalizes navigation into a compact 8B model.<n>sogrone at 8B surpasses every frozen frontier-LLM system in our comparison.
• Score: 44.1709905429432
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Knowledge graph question answering (KGQA) requires navigating from topic entities to an answer several relations away. Recent methods prompt a frontier LLM to explore the graph through a retrieval tool, but their reliance on frontier-scale inference makes them costly to deploy. We present Search-on-Graph-R1 (\sogrone{}), which internalizes this navigation into a compact 8B model through supervised fine-tuning (SFT) followed by reinforcement learning (RL). Our central idea is to scaffold a frontier teacher with each question's gold SPARQL query, so the teacher traverses a known answer-bearing path with a live \texttt{Search} tool rather than having to discover the path itself. Since every call executes against a live Freebase server, the resulting trajectories are grounded in the knowledge graph by construction. On WebQSP, CWQ, and GrailQA, \sogrone{} at 8B surpasses every frozen frontier-LLM system in our comparison and posts the strongest results on CWQ of any system we compare against. It does so using no auxiliary module at inference and no LLM judge during training. Isolating each training stage shows that SFT and RL contribute complementary gains, our approach transfers across model families, and RL learns to reach answers in fewer \texttt{Search} calls than its SFT initialization.

Related papers

• Iris: Climbing to the Search Frontier [21.066541702697112]
  We present Iris-mini and Iris-pro, two search agents trained at the 35B-A3B and 397B-A17B scales, together with the data pipeline and training recipe behind them.
  arXiv  Detail & Related papers  (2026-09-03T17:51:01Z)
• GTA-RAG: Graph-Trajectory-Augmented Reinforcement Learning for Multi-Turn Retrieval-Augmented Reasoning [27.83191719981676]
  We present textscGTA-RAG, a graph-trajectory-augmented RL framework for retrieval-augmented reasoning.<n>Method consistently outperforms RL-based RAG baselines with both Qwen2.5-3B and Qwen2.5-7B backbones.
  arXiv  Detail & Related papers  (2026-08-23T16:05:20Z)
• LongTraceRL: Learning Long-Context Reasoning from Search Agent Trajectories with Rubric Rewards [53.339700196282905]
  Reinforcement learning with verifiable rewards (RLVR) has shown promise for this task.<n>Existing methods are limited by low-confusability distractors and sparse, outcome-only reward signals.<n>textscLongTraceRL produces training contexts that are far more challenging than those built by random sampling or one-shot search.
  arXiv  Detail & Related papers  (2026-05-29T17:51:40Z)
• GraphWalker: Agentic Knowledge Graph Question Answering via Synthetic Trajectory Curriculum [22.56991897386462]
  Agentic knowledge graph question answering (KGQA) requires an agent to iteratively interact with knowledge graphs (KGs)<n>Existing approaches often restrict agent exploration, while current training pipelines usually confine reasoning to predefined trajectories.<n>This paper proposes textitGraphWalker,' a novel agentic KGQA framework that addresses these challenges through textitAutomated Trajectory Synthesis and textitStage-wise Fine-tuning
  arXiv  Detail & Related papers  (2026-03-30T14:56:59Z)
• GraphDancer: Training LLMs to Explore and Reason over Graphs via Curriculum Reinforcement Learning [19.78190825157365]
  Large language models increasingly rely on external knowledge to improve factuality.<n>Many real-world knowledge sources are organized as heterogeneous graphs rather than plain text.<n>We propose GraphDancer, a framework that teaches LLMs to navigate graphs by interleaving reasoning and function execution.
  arXiv  Detail & Related papers  (2026-01-24T02:44:49Z)
• MARAG-R1: Beyond Single Retriever via Reinforcement-Learned Multi-Tool Agentic Retrieval [50.30107119622642]
  Large Language Models (LLMs) excel at reasoning and generation but are inherently limited by static pretraining data.<n>Retrieval-Augmented Generation (RAG) addresses this issue by grounding LLMs in external knowledge.<n>MarAG-R1 is a reinforcement-learned multi-tool RAG framework that enables LLMs to dynamically coordinate multiple retrieval mechanisms.
  arXiv  Detail & Related papers  (2025-10-31T15:51:39Z)
• Search-on-Graph: Iterative Informed Navigation for Large Language Model Reasoning on Knowledge Graphs [26.0585592684229]
  Large language models (LLMs) have demonstrated impressive reasoning abilities yet remain unreliable on knowledge-intensive, multi-hop questions.<n>We propose Search-on-Graph (SoG), a simple yet effective framework that enables LLMs to perform iterative informed graph navigation.<n>We demonstrate particularly strong gains on Wikidata benchmarks (+16% improvement over previous best methods) alongside consistent improvements on Freebase benchmarks.
  arXiv  Detail & Related papers  (2025-10-09T21:20:16Z)
• GRIL: Knowledge Graph Retrieval-Integrated Learning with Large Language Models [59.72897499248909]
  We propose a novel graph retriever trained end-to-end with Large Language Models (LLMs)<n>Within the extracted subgraph, structural knowledge and semantic features are encoded via soft tokens and the verbalized graph, respectively, which are infused into the LLM together.<n>Our approach consistently achieves state-of-the-art performance, validating the strength of joint graph-LLM optimization for complex reasoning tasks.
  arXiv  Detail & Related papers  (2025-09-20T02:38:00Z)
• LTRR: Learning To Rank Retrievers for LLMs [53.285436927963865]
  We show that routing-based RAG systems can outperform the best single-retriever-based systems.<n>Performance gains are especially pronounced in models trained with the Answer Correctness (AC) metric.<n>As part of the SIGIR 2025 LiveRAG challenge, our submitted system demonstrated the practical viability of our approach.
  arXiv  Detail & Related papers  (2025-06-16T17:53:18Z)
• Enhancing Large Language Models with Reward-guided Tree Search for Knowledge Graph Question and Answering [8.449873147110516]
  Large language models (LLMs) have demonstrated impressive performance in Knowledge Graph Question Answering (KGQA) tasks.<n>This paper proposes a novel and training-free framework for KGQA tasks called Reward-guided Tree Search on Graph (RTSoG)
  arXiv  Detail & Related papers  (2025-05-18T15:52:57Z)
• UniKGQA: Unified Retrieval and Reasoning for Solving Multi-hop Question Answering Over Knowledge Graph [89.98762327725112]
  Multi-hop Question Answering over Knowledge Graph(KGQA) aims to find the answer entities that are multiple hops away from the topic entities mentioned in a natural language question. We propose UniKGQA, a novel approach for multi-hop KGQA task, by unifying retrieval and reasoning in both model architecture and parameter learning.
  arXiv  Detail & Related papers  (2022-12-02T04:08:09Z)
• Question-Answer Sentence Graph for Joint Modeling Answer Selection [122.29142965960138]
  We train and integrate state-of-the-art (SOTA) models for computing scores between question-question, question-answer, and answer-answer pairs. Online inference is then performed to solve the AS2 task on unseen queries.
  arXiv  Detail & Related papers  (2022-02-16T05:59:53Z)

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.