Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning
Linhao Luo, Yuan-Fang Li, Gholamreza Haffari, Shirui Pan
Abstract
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 planningretrieval-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 1 .
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
139 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Tree of Thoughts: Deliberate Problem Solving with Large Language Models cites Language Models are Few-Shot Learners
- Tree of Thoughts: Deliberate Problem Solving with Large Language Models cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph cites Tree of Thoughts: Deliberate Problem Solving with Large Language Models
- Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph cites Language Models are Few-Shot Learners
- Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph cites Graph of Thoughts: Solving Elaborate Problems with Large Language Models
- Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- MedRAG: Enhancing Retrieval-augmented Generation with Knowledge Graph-Elicited Reasoning for Healthcare Copilot cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering cites Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph
- G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- HippoRAG: Neurobiologically Inspired Long-Term Memory for Large Language Models cites Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph
- HippoRAG: Neurobiologically Inspired Long-Term Memory for Large Language Models cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs cites Tree of Thoughts: Deliberate Problem Solving with Large Language Models
- Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs cites Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph
- Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs cites Language Models are Few-Shot Learners
- Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs cites Graph of Thoughts: Solving Elaborate Problems with Large Language Models
- Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- Graph of Thoughts: Solving Elaborate Problems with Large Language Models cites Tree of Thoughts: Deliberate Problem Solving with Large Language Models
- Graph of Thoughts: Solving Elaborate Problems with Large Language Models cites Language Models are Few-Shot Learners
- Graph of Thoughts: Solving Elaborate Problems with Large Language Models cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- Finetuned Language Models are Zero-Shot Learners cites Language Models are Few-Shot Learners
- Finetuned Language Models are Zero-Shot Learners cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
Cited by top-tier papers139
- HippoRAG: Neurobiologically Inspired Long-Term Memory for Large Language ModelsBernal Jimenez Gutierrez, Yiheng Shu, Yu Gu, Michihiro Yasunaga et al.NeurIPS 2024 · 395 citations
- G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question AnsweringXiaoxin He, Yijun Tian, Yifei Sun, Nitesh V. Chawla et al.NeurIPS 2024 · 384 citations
- Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge GraphJiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang et al.ICLR 2024 · 247 citations
- Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge GraphsLiyi Chen, Panrong Tong, Zhongming Jin, Ying Sun et al.NeurIPS 2024 · 160 citations
- MedRAG: Enhancing Retrieval-augmented Generation with Knowledge Graph-Elicited Reasoning for Healthcare CopilotXuejiao Zhao, Siyan Liu, Su-Yin Yang, Chunyan MiaoWWW 2025 · 134 citations
Builds on34
- Language Models are Few-Shot LearnersTom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah et al.NeurIPS 2020 · 64,255 citations
- Chain-of-Thought Prompting Elicits Reasoning in Large Language ModelsJason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma et al.NeurIPS 2022 · 22,562 citations
- Tree of Thoughts: Deliberate Problem Solving with Large Language ModelsShunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran et al.NeurIPS 2023 · 5,068 citations
- Finetuned Language Models are Zero-Shot LearnersJason Wei, Maarten Bosma, Vincent Y. Zhao, Kelvin Guu et al.ICLR 2022 · 4,966 citations
- Graph of Thoughts: Solving Elaborate Problems with Large Language ModelsMaciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger et al.AAAI 2024 · 1,292 citations
Related papers
- Paths-over-Graph: Knowledge Graph Empowered Large Language Model ReasoningXingyu Tan, Xiaoyang Wang, Qing Liu, Xiwei Xu et al.WWW 2025 · 86 citations
- Plan-Answer-Refine-on-Graph: Structured Planning and Self-Refinement for Large Language Model Reasoning on Knowledge GraphsYuxin Shi, Han Fu, Zhuo Li, Chenghao Liu et al.ICLR 2026
- Explore-on-Graph: Incentivizing Autonomous Exploration of Large Language Models on Knowledge Graphs with Path-refined Reward ModelingShiqi Yan, Yubo Chen, Ruiqi Zhou, Zhengxi Yao et al.ICLR 2026 · 3 citations
- VoG: Enhancing LLM Reasoning through Stepwise Verification on Knowledge GraphsWenxin Zhao, Jiachuan Wang, Yongqi Zhang, Shuangyin Li et al.ICLR 2026
- Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language ModelsLinhao Luo, Zicheng Zhao, Gholamreza Haffari, Yuan-Fang Li et al.ICML 2025
