# Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs

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

## Key facts

- Cited by 78 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 39 of its 64 references that are in the map.
- First posted on arXiv 31 Oct 2024.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [ERNIE: Enhanced Language Representation with Informative Entities](https://mlsanity.com/paper/1905.07129/) (2019)
- [The Web as a Knowledge-base for Answering Complex Questions](https://mlsanity.com/paper/1803.06643/) (2018)
- [KEPLER: A Unified Model for Knowledge Embedding and Pre-trained Language Representation](https://mlsanity.com/paper/1911.06136/) (2019)
- [StructGPT: A General Framework for Large Language Model to Reason over Structured Data](https://mlsanity.com/paper/2305.09645/) (2023)
- [Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning](https://mlsanity.com/paper/2310.01061/) (2023)
- [KG-BERT: BERT for Knowledge Graph Completion](https://mlsanity.com/paper/1909.03193/) (2019)
- [GraphGPT: Graph Instruction Tuning for Large Language Models](https://mlsanity.com/paper/2310.13023/) (2023)
- [Beyond I.I.D.: Three Levels of Generalization for Question Answering on Knowledge Bases](https://mlsanity.com/paper/2011.07743/) (2020)
- [SelfCheck: Using LLMs to Zero-Shot Check Their Own Step-by-Step Reasoning](https://mlsanity.com/paper/2308.00436/) (2023)
- [UniKGQA: Unified Retrieval and Reasoning for Solving Multi-hop Question Answering Over Knowledge Graph](https://mlsanity.com/paper/2212.00959/) (2022)
- [Knowledge-Driven CoT: Exploring Faithful Reasoning in LLMs for Knowledge-intensive Question Answering](https://mlsanity.com/paper/2308.13259/) (2023)
- [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)
- [Boosting Language Models Reasoning with Chain-of-Knowledge Prompting](https://mlsanity.com/paper/2306.06427/) (2023)
- [Few-shot In-context Learning for Knowledge Base Question Answering](https://mlsanity.com/paper/2305.01750/) (2023)
- [T-SciQ: Teaching Multimodal Chain-of-Thought Reasoning via Mixed Large Language Model Signals for Science Question Answering](https://mlsanity.com/paper/2305.03453/) (2023)
- [TIARA: Multi-grained Retrieval for Robust Question Answering over Large Knowledge Bases](https://mlsanity.com/paper/2210.12925/) (2022)
- [Don't Generate, Discriminate: A Proposal for Grounding Language Models to Real-World Environments](https://mlsanity.com/paper/2212.09736/) (2022)
- [FlexKBQA: A Flexible LLM-Powered Framework for Few-Shot Knowledge Base Question Answering](https://mlsanity.com/paper/2308.12060/) (2023)
- [MoT: Memory-of-Thought Enables ChatGPT to Self-Improve](https://mlsanity.com/paper/2305.05181/) (2023)

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

- [A Survey of Graph Retrieval-Augmented Generation for Customized Large Language Models](https://mlsanity.com/paper/2501.13958/) (2025)
- [PathRAG: Pruning Graph-based Retrieval Augmented Generation with Relational Paths](https://mlsanity.com/paper/2502.14902/) (2025)
- [TokenSelect: Efficient Long-Context Inference and Length Extrapolation for LLMs via Dynamic Token-Level KV Cache Selection](https://mlsanity.com/paper/2411.02886/) (2024)
- [Large Language Models Meet Knowledge Graphs for Question Answering: Synthesis and Opportunities](https://mlsanity.com/paper/2505.20099/) (2025)
- [Harnessing Large Language Models for Knowledge Graph Question Answering via Adaptive Multi-Aspect Retrieval-Augmentation](https://mlsanity.com/paper/2412.18537/) (2024)
- [LLM-powered Multi-agent Framework for Goal-oriented Learning in Intelligent Tutoring System](https://mlsanity.com/paper/2501.15749/) (2025)
- [Hierarchical Time-Aware Mixture of Experts for Multi-Modal Sequential Recommendation](https://mlsanity.com/paper/2501.14269/) (2025)
- [Diagnosing and Addressing Pitfalls in KG-RAG Datasets: Toward More Reliable Benchmarking](https://mlsanity.com/paper/2505.23495/) (2025)
- [Align-GRAG: Anchor and Rationale Guided Dual Alignment for Graph Retrieval-Augmented Generation](https://mlsanity.com/paper/2505.16237/) (2025)
- [Reliable Reasoning Path: Distilling Effective Guidance for LLM Reasoning with Knowledge Graphs](https://mlsanity.com/paper/2506.10508/) (2025)
- [ReMindRAG: Low-Cost LLM-Guided Knowledge Graph Traversal for Efficient RAG](https://mlsanity.com/paper/2510.13193/) (2025)
- [Reason-Align-Respond: Aligning LLM Reasoning with Knowledge Graphs for KGQA](https://mlsanity.com/paper/2505.20971/) (2025)
- [TeaRAG: A Token-Efficient Agentic Retrieval-Augmented Generation Framework](https://mlsanity.com/paper/2511.05385/) (2025)
- [Membox: Weaving Topic Continuity into Long-Range Memory for LLM Agents](https://mlsanity.com/paper/2601.03785/) (2026)
- [Dynamic-KGQA: A Scalable Framework for Generating Adaptive Question Answering Datasets](https://mlsanity.com/paper/2503.05049/) (2025)
- [Learning Efficient and Generalizable Graph Retriever for Knowledge-Graph Question Answering](https://mlsanity.com/paper/2506.09645/) (2025)
- [Efficient and Transferable Agentic Knowledge Graph RAG via Reinforcement Learning](https://mlsanity.com/paper/2509.26383/) (2025)
- [Search-on-Graph: Iterative Informed Navigation for Large Language Model Reasoning on Knowledge Graphs](https://mlsanity.com/paper/2510.08825/) (2025)
- [Self-Reflective Planning with Knowledge Graphs: Enhancing LLM Reasoning Reliability for Question Answering](https://mlsanity.com/paper/2505.19410/) (2025)
- [RJE: A Retrieval-Judgment-Exploration Framework for Efficient Knowledge Graph Question Answering with LLMs](https://mlsanity.com/paper/2510.01257/) (2025)
- [KnowPath: Knowledge-enhanced Reasoning via LLM-generated Inference Paths over Knowledge Graphs](https://mlsanity.com/paper/2502.12029/) (2025)
- [Enhancing Large Language Models with Reward-guided Tree Search for Knowledge Graph Question and Answering](https://mlsanity.com/paper/2505.12476/) (2025)
- [Beyond Chains: Bridging Large Language Models and Knowledge Bases in Complex Question Answering](https://mlsanity.com/paper/2505.14099/) (2025)
- [Advancing Multi-Agent RAG Systems with Minimalist Reinforcement Learning](https://mlsanity.com/paper/2505.17086/) (2025)
- [LLM Inference Enhanced by External Knowledge: A Survey](https://mlsanity.com/paper/2505.24377/) (2025)
- [Ground-Truth Subgraphs for Better Training and Evaluation of Knowledge Graph Augmented LLMs](https://mlsanity.com/paper/2511.04473/) (2025)
- [Debate over Mixed-knowledge: A Robust Multi-Agent Reasoning Framework for Incomplete Knowledge Graph Question Answering](https://mlsanity.com/paper/2511.12208/) (2025)
- [KBQA-R1: Reinforcing Large Language Models for Knowledge Base Question Answering](https://mlsanity.com/paper/2512.10999/) (2025)
- [CoG: Controllable Graph Reasoning via Relational Blueprints and Failure-Aware Refinement over Knowledge Graphs](https://mlsanity.com/paper/2601.11047/) (2026)
- [Agentic SPARQL: Evaluating SPARQL-MCP-powered Intelligent Agents on the Federated KGQA Benchmark](https://mlsanity.com/paper/2603.06582/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) have shown remarkable reasoning capabilities on complex tasks, but they still suffer from out-of-date knowledge, hallucinations, and opaque decision-making. In contrast, Knowledge Graphs (KGs) can provide explicit and editable knowledge for LLMs to alleviate these issues. Existing paradigm of KG-augmented LLM manually predefines the breadth of exploration space and requires flawless navigation in KGs. However, this paradigm cannot adaptively explore reasoning paths in KGs based on the question semantics and self-correct erroneous reasoning paths, resulting in a bottleneck in efficiency and effect. To address these limitations, we propose a novel self-correcting adaptive planning paradigm for KG-augmented LLM named Plan-on-Graph (PoG), which first decomposes the question into several sub-objectives and then repeats the process of adaptively exploring reasoning paths, updating memory, and reflecting on the need to self-correct erroneous reasoning paths until arriving at the answer. Specifically, three important mechanisms of Guidance, Memory, and Reflection are designed to work together, to guarantee the adaptive breadth of self-correcting planning for graph reasoning. Finally, extensive experiments on three real-world datasets demonstrate the effectiveness and efficiency of PoG.