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

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 41 references that are in the map.
- First posted on arXiv 20 Jul 2026.

## Builds on (most cited first, 23 of 23)

- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [HybridFlow: A Flexible and Efficient RLHF Framework](https://mlsanity.com/paper/2409.19256/) (2024)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning](https://mlsanity.com/paper/2503.09516/) (2025)
- [Unifying Large Language Models and Knowledge Graphs: A Roadmap](https://mlsanity.com/paper/2306.08302/) (2023)
- [Editing Factual Knowledge in Language Models](https://mlsanity.com/paper/2104.08164/) (2021)
- [The Web as a Knowledge-base for Answering Complex Questions](https://mlsanity.com/paper/1803.06643/) (2018)
- [Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph](https://mlsanity.com/paper/2307.07697/) (2023)
- [Beyond I.I.D.: Three Levels of Generalization for Question Answering on Knowledge Bases](https://mlsanity.com/paper/2011.07743/) (2020)
- [KG-Agent: An Efficient Autonomous Agent Framework for Complex Reasoning over Knowledge Graph](https://mlsanity.com/paper/2402.11163/) (2024)
- [DecAF: Joint Decoding of Answers and Logical Forms for Question Answering over Knowledge Bases](https://mlsanity.com/paper/2210.00063/) (2022)
- [Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs](https://mlsanity.com/paper/2410.23875/) (2024)
- [Graph-R1: Towards Agentic GraphRAG Framework via End-to-end Reinforcement Learning](https://mlsanity.com/paper/2507.21892/) (2025)
- [FiDeLiS: Faithful Reasoning in Large Language Model for Knowledge Graph Question Answering](https://mlsanity.com/paper/2405.13873/) (2024)
- [Decoding on Graphs: Faithful and Sound Reasoning on Knowledge Graphs through Generation of Well-Formed Chains](https://mlsanity.com/paper/2410.18415/) (2024)
- [Ontology-Guided Reverse Thinking Makes Large Language Models Stronger on Knowledge Graph Question Answering](https://mlsanity.com/paper/2502.11491/) (2025)
- [EffiQA: Efficient Question-Answering with Strategic Multi-Model Collaboration on Knowledge Graphs](https://mlsanity.com/paper/2406.01238/) (2024)
- [BYOKG-RAG: Multi-Strategy Graph Retrieval for Knowledge Graph Question Answering](https://mlsanity.com/paper/2507.04127/) (2025)
- [Search-on-Graph: Iterative Informed Navigation for Large Language Model Reasoning on Knowledge Graphs](https://mlsanity.com/paper/2510.08825/) (2025)
- [RJE: A Retrieval-Judgment-Exploration Framework for Efficient Knowledge Graph Question Answering with LLMs](https://mlsanity.com/paper/2510.01257/) (2025)
- [Explore-on-Graph: Incentivizing Autonomous Exploration of Large Language Models on Knowledge Graphs with Path-refined Reward Modeling](https://mlsanity.com/paper/2602.21728/) (2026)

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

- [Harness-G: A Graph-Structured Harness for Search Agents](https://mlsanity.com/paper/2607.27652/) (2026)
- [The Path Matters: Evaluating Small Language Models Beyond Answer Accuracy in KGQA](https://mlsanity.com/paper/2609.27669/) (2026)

## Abstract (arXiv)

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 textttSearch 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 textttSearch calls than its SFT initialization.