# Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning

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

## Key facts

- Cited by 328 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 54 of its 76 references that are in the map.
- First posted on arXiv 2 Oct 2023.

## 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 54)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Finetuned Language Models Are Zero-Shot Learners](https://mlsanity.com/paper/2109.01652/) (2021)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Scaling Instruction-Finetuned Language Models](https://mlsanity.com/paper/2210.11416/) (2022)
- [Survey of Hallucination in Natural Language Generation](https://mlsanity.com/paper/2202.03629/) (2022)
- [Leveraging Passage Retrieval with Generative Models for Open Domain Question Answering](https://mlsanity.com/paper/2007.01282/) (2020)
- [A Multitask, Multilingual, Multimodal Evaluation of ChatGPT on Reasoning, Hallucination, and Interactivity](https://mlsanity.com/paper/2302.04023/) (2023)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Unifying Large Language Models and Knowledge Graphs: A Roadmap](https://mlsanity.com/paper/2306.08302/) (2023)
- [Towards Reasoning in Large Language Models: A Survey](https://mlsanity.com/paper/2212.10403/) (2022)
- [Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Models](https://mlsanity.com/paper/2305.04091/) (2023)
- [Decomposed Prompting: A Modular Approach for Solving Complex Tasks](https://mlsanity.com/paper/2210.02406/) (2022)
- [The Web as a Knowledge-base for Answering Complex Questions](https://mlsanity.com/paper/1803.06643/) (2018)
- [QA-GNN: Reasoning with Language Models and Knowledge Graphs for Question Answering](https://mlsanity.com/paper/2104.06378/) (2021)
- [Key-Value Memory Networks for Directly Reading Documents](https://mlsanity.com/paper/1606.03126/) (2016)
- [PullNet: Open Domain Question Answering with Iterative Retrieval on Knowledge Bases and Text](https://mlsanity.com/paper/1904.09537/) (2019)
- [GreaseLM: Graph REASoning Enhanced Language Models for Question Answering](https://mlsanity.com/paper/2201.08860/) (2022)
- [Variational Reasoning for Question Answering with Knowledge Graph](https://mlsanity.com/paper/1709.04071/) (2017)
- [Open Domain Question Answering Using Early Fusion of Knowledge Bases and Text](https://mlsanity.com/paper/1809.00782/) (2018)
- [Rethinking with Retrieval: Faithful Large Language Model Inference](https://mlsanity.com/paper/2301.00303/) (2022)
- [End-to-End Training of Multi-Document Reader and Retriever for Open-Domain Question Answering](https://mlsanity.com/paper/2106.05346/) (2021)
- [Faithful Reasoning Using Large Language Models](https://mlsanity.com/paper/2208.14271/) (2022)
- [UniKGQA: Unified Retrieval and Reasoning for Solving Multi-hop Question Answering Over Knowledge Graph](https://mlsanity.com/paper/2212.00959/) (2022)
- [Improving Multi-hop Knowledge Base Question Answering by Learning Intermediate Supervision Signals](https://mlsanity.com/paper/2101.03737/) (2021)
- [Knowledge-Driven CoT: Exploring Faithful Reasoning in LLMs for Knowledge-intensive Question Answering](https://mlsanity.com/paper/2308.13259/) (2023)

## Built on by (most cited first, 30 of 328)

- [Retrieval-Augmented Generation for Large Language Models: A Survey](https://mlsanity.com/paper/2312.10997/) (2023)
- [Time-LLM: Time Series Forecasting by Reprogramming Large Language Models](https://mlsanity.com/paper/2310.01728/) (2023)
- [A Survey on the Memory Mechanism of Large Language Model based Agents](https://mlsanity.com/paper/2404.13501/) (2024)
- [Graph Retrieval-Augmented Generation: A Survey](https://mlsanity.com/paper/2408.08921/) (2024)
- [HippoRAG: Neurobiologically Inspired Long-Term Memory for Large Language Models](https://mlsanity.com/paper/2405.14831/) (2024)
- [G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering](https://mlsanity.com/paper/2402.07630/) (2024)
- [Large Language Models on Graphs: A Comprehensive Survey](https://mlsanity.com/paper/2312.02783/) (2023)
- [Retrieval-Augmented Generation with Graphs (GraphRAG)](https://mlsanity.com/paper/2501.00309/) (2024)
- [Multi-Step Reasoning with Large Language Models, a Survey](https://mlsanity.com/paper/2407.11511/) (2024)
- [GNN-RAG: Graph Neural Retrieval for Large Language Model Reasoning](https://mlsanity.com/paper/2405.20139/) (2024)
- [Retrieval-Augmented Generation with Knowledge Graphs for Customer Service Question Answering](https://mlsanity.com/paper/2404.17723/) (2024)
- [KG-Agent: An Efficient Autonomous Agent Framework for Complex Reasoning over Knowledge Graph](https://mlsanity.com/paper/2402.11163/) (2024)
- [Can Knowledge Graphs Reduce Hallucinations in LLMs? : A Survey](https://mlsanity.com/paper/2311.07914/) (2023)
- [What Did I Do Wrong? Quantifying LLMs' Sensitivity and Consistency to Prompt Engineering](https://mlsanity.com/paper/2406.12334/) (2024)
- [From Matching to Generation: A Survey on Generative Information Retrieval](https://mlsanity.com/paper/2404.14851/) (2024)
- [A Survey of Graph Retrieval-Augmented Generation for Customized Large Language Models](https://mlsanity.com/paper/2501.13958/) (2025)
- [MedRAG: Enhancing Retrieval-augmented Generation with Knowledge Graph-Elicited Reasoning for Healthcare Copilot](https://mlsanity.com/paper/2502.04413/) (2025)
- [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)
- [GRAG: Graph Retrieval-Augmented Generation](https://mlsanity.com/paper/2405.16506/) (2024)
- [Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs](https://mlsanity.com/paper/2410.23875/) (2024)
- [A Survey of Large Language Models for Graphs](https://mlsanity.com/paper/2405.08011/) (2024)
- [KAG: Boosting LLMs in Professional Domains via Knowledge Augmented Generation](https://mlsanity.com/paper/2409.13731/) (2024)
- [Demystifying Chains, Trees, and Graphs of Thoughts](https://mlsanity.com/paper/2401.14295/) (2024)
- [Generate-on-Graph: Treat LLM as both Agent and KG in Incomplete Knowledge Graph Question Answering](https://mlsanity.com/paper/2404.14741/) (2024)
- [Knowledge Graph Retrieval-Augmented Generation for LLM-based Recommendation](https://mlsanity.com/paper/2501.02226/) (2025)
- [InstructGraph: Boosting Large Language Models via Graph-centric Instruction Tuning and Preference Alignment](https://mlsanity.com/paper/2402.08785/) (2024)
- [KG-RAG: Bridging the Gap Between Knowledge and Creativity](https://mlsanity.com/paper/2405.12035/) (2024)
- [Knowledge Mechanisms in Large Language Models: A Survey and Perspective](https://mlsanity.com/paper/2407.15017/) (2024)
- [LLM-based Agents Suffer from Hallucinations: A Survey of Taxonomy, Methods, and Directions](https://mlsanity.com/paper/2509.18970/) (2025)
- [Large Language Models Hallucination: A Comprehensive Survey](https://mlsanity.com/paper/2510.06265/) (2025)

## Abstract (arXiv)

Large language models (LLMs) have demonstrated impressive reasoning abilities in complex tasks. However, they lack up-to-date knowledge and experience hallucinations during reasoning, which can lead to incorrect reasoning processes and diminish their performance and trustworthiness. Knowledge graphs (KGs), which capture vast amounts of facts in a structured format, offer a reliable source of knowledge for reasoning. Nevertheless, existing KG-based LLM reasoning methods only treat KGs as factual knowledge bases and overlook the importance of their structural information for reasoning. In this paper, we propose a novel method called reasoning on graphs (RoG) that synergizes LLMs with KGs to enable faithful and interpretable reasoning. Specifically, we present a planning-retrieval-reasoning framework, where RoG first generates relation paths grounded by KGs as faithful plans. These plans are then used to retrieve valid reasoning paths from the KGs for LLMs to conduct faithful reasoning. Furthermore, RoG not only distills knowledge from KGs to improve the reasoning ability of LLMs through training but also allows seamless integration with any arbitrary LLMs during inference. Extensive experiments on two benchmark KGQA datasets demonstrate that RoG achieves state-of-the-art performance on KG reasoning tasks and generates faithful and interpretable reasoning results.