Research map / Large language models / Retrieval and knowledge
Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Plan-on-Graph (PoG), a training-free self-correcting adaptive planning framework where an LLM decomposes questions into sub-objectives and iteratively explores KG reasoning paths with memory and reflection-based backtracking.
Problem
KG-augmented LLM reasoning uses predefined exploration breadth and unidirectional path extension, so it cannot adaptively explore relevant paths, self-correct wrong paths, or keep track of all question conditions.
Approach
Adds three mechanisms to LLM-driven KG exploration: Guidance (decompose the question into condition-bearing sub-objectives), Memory (subgraph, reasoning paths, sub-objective status), and Reflection (decide whether to add or backtrack to other entities), together with flexible-breadth relation and entity selection by the LLM.
Key results
- With GPT-4, PoG reaches 75.0 Hits@1 on CWQ and 87.3 on WebQSP, exceeding ToG (67.6 and 82.6) and fine-tuned baselines such as RoG (62.6 and 85.7 on CWQ/WebQSP).
- On GrailQA with GPT-3.5, PoG reaches 76.5 overall versus 68.7 for ToG, and with GPT-4 reaches 84.7 versus 81.4.
- Efficiency: PoG reduces LLM calls by at least 40.8% versus ToG and gives over 4x speedup on CWQ and GrailQA (CWQ time 23.3s vs 96.5s).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use PoG instead of ToG | GPT-3.5 KG-augmented LLM · CWQ | Hits@1: 57.1 -> 63.2 | Helped |
| use PoG instead of ToG | GPT-3.5 KG-augmented LLM · WebQSP | Hits@1: 76.2 -> 82.0 | Helped |
| use PoG instead of ToG | GPT-3.5 KG-augmented LLM · GrailQA overall | Hits@1: 68.7 -> 76.5 | Helped |
| add Guidance (question decomposition into sub-objectives) (ablation) | PoG · CWQ | Hits@1: 60.1 -> 63.2 | Helped |
| add Guidance (question decomposition into sub-objectives) (ablation) | PoG · WebQSP | Hits@1: 80.3 -> 82.0 | Helped |
| add Guidance (question decomposition into sub-objectives) (ablation) | PoG · GrailQA | Hits@1: 72.4 -> 76.5 | Helped |
| add Memory (ablation) | PoG · CWQ | Hits@1: 58.9 -> 63.2 | Helped |
| add Memory (ablation) | PoG · WebQSP | Hits@1: 77.5 -> 82.0 | Helped |
| add Memory (ablation) | PoG · GrailQA | Hits@1: 69.3 -> 76.5 | Helped |
| add Reflection (self-correction) (ablation) | PoG · CWQ | Hits@1: 59.4 -> 63.2 | Helped |
| add Reflection (self-correction) (ablation) | PoG · WebQSP | Hits@1: 78.1 -> 82.0 | Helped |
| add Reflection (self-correction) (ablation) | PoG · GrailQA | Hits@1: 70.5 -> 76.5 | Helped |
Surprising findings
- Ablation shows that removing Memory causes the largest drop, larger than removing Reflection.
- Training-free PoG with GPT-3.5 outperforms all fine-tuned KG-augmented LLM baselines on the GrailQA zero-shot subset by a large margin.
Limitations
- LLMs have low self-confidence about when information is sufficient and how many steps are needed.
- Multi-step exploration is costly; exploration depth must be manually fixed (set to 4).
- Performance depends on semantic understanding of non-standardized queries.
Experimental setup
Datasets: ComplexWebQuestions WebQSP GrailQA
Benchmarks: ComplexWebQuestions WebQSP GrailQA
Metrics: Hits@1 LLM calls input tokens output tokens time (s)
Baselines: IO prompt CoT Self-Consistency UniKGQA TIARA RE-KBQA DeCAF RoG KD-CoT KB-BINDER StructGPT Interactive KBQA
Builds on: Think-on-Graph chain-of-thought self-consistency
Closest papers by meaning
- Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning (ICLR 2024 · similarity 0.94)
- Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph (ICLR 2024 · similarity 0.91)
- Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models (ICML 2025 · similarity 0.90)
- Graph-enhanced Large Language Models in Asynchronous Plan Reasoning (ICML 2024 · similarity 0.90)
- On the self-verification limitations of large language models on reasoning and planning tasks (ICLR 2025 · similarity 0.89)
- Debate on Graph: A Flexible and Reliable Reasoning Framework for Large Language Models (AAAI 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.