# Search-on-Graph: Iterative Informed Navigation for Large Language Model Reasoning on Knowledge Graphs

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 48 of its 71 references that are in the map.
- First posted on arXiv 9 Oct 2025.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 30 of 48)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Large Language Models Encode Clinical Knowledge](https://mlsanity.com/paper/2212.13138/) (2022)
- [A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions](https://mlsanity.com/paper/2311.05232/) (2023)
- [Large Language Models Struggle to Learn Long-Tail Knowledge](https://mlsanity.com/paper/2211.08411/) (2022)
- [The Web as a Knowledge-base for Answering Complex Questions](https://mlsanity.com/paper/1803.06643/) (2018)
- [Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning](https://mlsanity.com/paper/2310.01061/) (2023)
- [A Comprehensive Survey of Hallucination Mitigation Techniques in Large Language Models](https://mlsanity.com/paper/2401.01313/) (2024)
- [RealTime QA: What's the Answer Right Now?](https://mlsanity.com/paper/2207.13332/) (2022)
- [G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering](https://mlsanity.com/paper/2402.07630/) (2024)
- [PullNet: Open Domain Question Answering with Iterative Retrieval on Knowledge Bases and Text](https://mlsanity.com/paper/1904.09537/) (2019)
- [Beyond I.I.D.: Three Levels of Generalization for Question Answering on Knowledge Bases](https://mlsanity.com/paper/2011.07743/) (2020)
- [Open Domain Question Answering Using Early Fusion of Knowledge Bases and Text](https://mlsanity.com/paper/1809.00782/) (2018)
- [Large-scale Simple Question Answering with Memory Networks](https://mlsanity.com/paper/1506.02075/) (2015)
- [StreamingQA: A Benchmark for Adaptation to New Knowledge over Time in Question Answering Models](https://mlsanity.com/paper/2205.11388/) (2022)
- [Deductive Verification of Chain-of-Thought Reasoning](https://mlsanity.com/paper/2306.03872/) (2023)
- [UniKGQA: Unified Retrieval and Reasoning for Solving Multi-hop Question Answering Over Knowledge Graph](https://mlsanity.com/paper/2212.00959/) (2022)
- [KG-Agent: An Efficient Autonomous Agent Framework for Complex Reasoning over Knowledge Graph](https://mlsanity.com/paper/2402.11163/) (2024)
- [RnG-KBQA: Generation Augmented Iterative Ranking for Knowledge Base Question Answering](https://mlsanity.com/paper/2109.08678/) (2021)
- [DecAF: Joint Decoding of Answers and Logical Forms for Question Answering over Knowledge Bases](https://mlsanity.com/paper/2210.00063/) (2022)
- [Simple Is Effective: The Roles of Graphs and Large Language Models in Knowledge-Graph-Based Retrieval-Augmented Generation](https://mlsanity.com/paper/2410.20724/) (2024)
- [Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs](https://mlsanity.com/paper/2410.23875/) (2024)
- [Few-shot In-context Learning for Knowledge Base Question Answering](https://mlsanity.com/paper/2305.01750/) (2023)
- [TransferNet: An Effective and Transparent Framework for Multi-hop Question Answering over Relation Graph](https://mlsanity.com/paper/2104.07302/) (2021)
- [Generate-on-Graph: Treat LLM as both Agent and KG in Incomplete Knowledge Graph Question Answering](https://mlsanity.com/paper/2404.14741/) (2024)
- [Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models](https://mlsanity.com/paper/2410.13080/) (2024)

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

- [Autonomous Knowledge Graph Exploration with Adaptive Breadth-Depth Retrieval](https://mlsanity.com/paper/2601.13969/) (2026)
- [Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning](https://mlsanity.com/paper/2607.18481/) (2026)
- [DeSQ: Decomposition-based SPARQL Query Generation](https://mlsanity.com/paper/2606.00203/) (2026)
- [KGCache: Amortized Subgraph Retrieval for KG Reasoning with LLMs](https://mlsanity.com/paper/2608.07954/) (2026)
- [The Path Matters: Evaluating Small Language Models Beyond Answer Accuracy in KGQA](https://mlsanity.com/paper/2609.27669/) (2026)

## Abstract (arXiv)

Large language models (LLMs) augmented with knowledge graphs (KGs) offer a promising approach for knowledge-intensive reasoning. Central to this approach is the selection of appropriate reasoning paths in the KG. Yet, existing methods face a common limitation: reasoning path selection is often performed by separate modules using criteria that are only weakly connected to the reasoning requirements. This often results in selecting incorrect relations or premature pruning of relevant paths. We propose Search-on-Graph (SoG), a method that strengthens the connection between path selection and reasoning by having the LLM itself select which relations to follow, informed by both the available KG structure and the complete reasoning history. SoG follows an textitobserve-think-navigate paradigm: at each step, the LLM observes the relational connections available at the current entity, reasons about which path best advances toward answering the question, and navigates accordingly. This context-aware navigation fully exploits the LLM's reasoning capabilities rather than relying on independent selection modules with surrogate criteria. Experiments on six knowledge graph question answering (KGQA) benchmarks demonstrate that SoG outperforms state-of-the-art methods while requiring no task-specific fine-tuning and generalizing across different KG schemas.