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

Liyi Chen; Panrong Tong; Zhongming Jin; Ying Sun; Jieping Ye; Hui Xiong

Source-linked AI summary

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

Liyi Chen, Panrong Tong, Zhongming Jin, Ying Sun, Jieping Ye, Hui Xiong

arXiv:2410.23875v1Oct 31, 2024cs.AI

TL;DR

LLM-based KG reasoning remains limited by stale knowledge, hallucinations, opaque decisions, and rigid or error-prone graph exploration. PoG decomposes questions and iteratively combines adaptive path exploration, memory, and reflection, with experiments on three KGQA datasets demonstrating effectiveness and efficiency.

Problem
Existing KG-augmented LLMs cannot adaptively explore reasoning paths from question semantics or self-correct erroneous paths.
Method
PoG decomposes questions into sub-objectives and iteratively explores paths, updates memory, and reflects on self-correction.
Results
Experiments on CWQ, WebQSP, and GrailQA demonstrate PoG’s effectiveness and efficiency.
Takeaways & Limitations
Guidance, Memory, and Reflection work together to support adaptive breadth and self-correcting graph reasoning.
Takeaways & Limitations
The paper describes broader impact and application scope but does not provide a concrete method limitation in the supplied passages.

Abstract

from arXiv · show

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.

1 Introduction

LLMs offer strong language reasoning but remain vulnerable to stale knowledge, hallucinations, and opaque decisions. PoG addresses limitations in KG-augmented reasoning by adaptively exploring paths and self-correcting errors through Guidance, Memory, and Reflection.

Motivation: Knowledge Graphs provide explicit and editable knowledge that can complement LLM limitations, but prior integration methods may remain black-box or retrieval-dependent.Earlier approaches either compress KG knowledge into model parameters or rely heavily on KG completeness.
Limitations of Existing Paradigms: Existing KG-augmented LLMs manually fix exploration breadth and may select incorrect paths for complex questions.The Taylor Swift example shows a fixed maximum breadth can miss the correct song entity.
Plan-on-Graph: PoG decomposes questions into sub-objectives, adaptively explores reasoning paths, updates memory, and reflects to correct erroneous paths.Its Guidance, Memory, and Reflection mechanisms jointly support adaptive self-correcting planning.
Experiments: PoG is evaluated on CWQ, WebQSP, and GrailQA, with experiments demonstrating effectiveness and efficiency.The supplied passage reports results across three real-world KGQA datasets without providing numerical values.

2 Preliminary

The paper formulates KGQA over a graph of entities and relations, where reasoning follows relation paths instantiated by entity sequences. Given a question and linked topic entities, the goal is to generate linked answer entities.

Knowledge Graph: A Knowledge Graph stores factual knowledge as triples of entities connected by relations.The graph is represented as G = {(e, r, e′) | e, e′ ∈E, r ∈R}.
Paths: A relation path is an ordered sequence of relations, while a reasoning path instantiates it with linked entities.Reasoning paths preserve the entity-relation sequence traversed in the KG.
KGQA: KGQA answers a natural-language question using KG facts, with topic entities and answers assumed to be linked to graph entities.The target is to generate answer entities Aq from question q, graph G, and topic entities Tq.

3 Methodology

PoG combines task decomposition, adaptive path exploration, memory updating, and evaluation to guide KG reasoning. It repeatedly selects relevant paths, records intermediate state, and reflects on whether to continue or backtrack for self-correction.

Task Decomposition: PoG decomposes each question into interdependent sub-objectives that guide retrieval and reasoning under the question’s conditions.Sub-objectives can depend on results from other sub-objectives.
Path Exploration: Path exploration begins from topic entities and continues only along paths judged most relevant to the question and sub-objectives.The method uses relation exploration followed by entity exploration, with a flexible number of selected paths rather than a fixed breadth.
Path Exploration: Relation exploration retrieves candidate relations, and entity exploration retrieves neighboring candidate entities before the LLM selects relevant reasoning paths.Candidate entities may be recalled using similarity scoring when their number is large.
Memory Updating: Memory dynamically stores the searched subgraph, reasoning paths, and sub-objective status as historical retrieval and reasoning information.These records preserve graph structure and help the model track conditions during later reflection.
Evaluation: When information is insufficient, reflection decides whether current paths can be extended or whether to backtrack and explore additional entities.The decision uses the question, memory state, current paths, and planned next-step entities.

4 Experiments

Experiments on CWQ, WebQSP, and GrailQA show that PoG achieves strong effectiveness while reducing reasoning cost through adaptive exploration and self-correction.

4.2 Performance Comparison: PoG achieves the best performance across CWQ, WebQSP, and GrailQA, substantially outperforming the prompting baseline ToG with either GPT-3.5 or GPT-4.PoG also remains competitive with fine-tuned KG-augmented LLM baselines.
4.3 Ablation Study: Removing Guidance, Memory, Reflection, or adaptive breadth weakens performance, with minimum reductions of 3.0% on CWQ, 2.1% on WebQSP, and 3.5% on GrailQA.The largest degradation occurs without Memory, followed by removing Reflection.
4.4 Efficiency Study: PoG reduces average LLM calls by at least 40.8% versus ToG and achieves over 4× speedups on CWQ and GrailQA.On CWQ, PoG uses 353.159 output tokens, roughly 76.2% fewer than ToG.
4.5 Case Study: In a CWQ case, PoG detects insufficient information, uses memory to identify the unresolved sub-objective, and revises the exploration path to reach the correct answer.The case compares PoG with ToG and CoT using GPT-3.5.

CoT

The case comparison illustrates how PoG uses stored sub-objective status to revise an exploration path and ultimately provide the correct answer.

CoT: Figure 3 compares methods using partial reasoning paths and sub-objective status, with topic entities, wrong answers, correct answers, and revised paths color-coded.The displayed colors distinguish blue topic entities, red wrong answers, green correct answers, and yellow revised paths.
CoT: PoG uses sub-objective status in memory to self-correct its exploration path and finally provide the correct answer.The figure compares methods on a complex question and marks revised paths distinctly.

5 Related Work

Related work covers LLM reasoning and KG-augmented LLMs, while identifying adaptive KG exploration and self-correction as unresolved challenges addressed by PoG.

CoT: LLM reasoning research includes Chain-of-Thought and variants such as Tree-of-Thought, Graph-of-Thought, and Memory of Thought.
KG-Augmented LLM: KG-augmented LLM methods use knowledge graphs to provide explicit knowledge and may treat the LLM as an agent that interactively explores entities and relations.Earlier approaches also integrated KG knowledge during pre-training or fine-tuning.
KG-Augmented LLM: Existing KG-augmented LLM paradigms still face challenges in adapting exploration to question semantics and self-correcting erroneous reasoning paths.PoG is presented as a pioneering effort to integrate reflection for these challenges.

6 Conclusion

PoG combines Guidance, Memory, and Reflection to adaptively explore knowledge graphs and self-correct reasoning paths until answering a question. Its implementation uses structured prompts and predefined Freebase queries to support iterative retrieval and reasoning.

6 Conclusion: PoG decomposes questions into sub-objectives, explores reasoning paths adaptively, updates memory, and reflects on whether to self-correct until reaching an answer.The three mechanisms are Guidance, Memory, and Reflection.
6 Conclusion: Guidance prompts the model to produce as few sub-objectives and highly relevant relations as possible, then select the minimum necessary entities for retrieval.These prompts operationalize semantic decomposition and selective graph exploration.
6 Conclusion: Memory records currently known information from retrieved triplets and supports answer generation, while explicit triplets take priority when they contain the answer.The answer stage uses the question, memory, related knowledge triplets, and the model’s knowledge.
6 Conclusion: Reflection evaluates whether additional entities are needed based on the current entity set, memory, and knowledge triplets before further retrieval.The resulting decision includes whether to add entities and the reason for doing so.
6 Conclusion: PoG automates Freebase access with predefined SPARQL templates filled using an entity mid and relation.The templates retrieve relations, connected entities, and entity names or aliases.

C Datasets

The evaluation uses three multi-hop KGQA datasets built on Freebase, covering standard, complex, and multiple generalization settings. Comparisons include both LLM-only and KG-augmented LLM baselines.

C Datasets: The datasets are WebQSP, ComplexWebQuestions, and GrailQA, all relying on Freebase as the external knowledge graph.They are used to evaluate complex multi-hop question answering.
C Datasets: WebQSP tests I.I.D. generalization, CWQ covers conjunction, composition, comparative, and superlative questions, and GrailQA tests I.I.D., compositional, and zero-shot generalization.These datasets provide varied question complexity and generalization regimes.
C Datasets: The baseline pool contains LLM-only methods and KG-augmented LLM methods, including fine-tuned and prompting approaches.Standard prompting, Chain-of-Thought, and Self-Consistency represent the LLM-only group.

Finetuned KG-Augmented LLM Methods

The compared fine-tuned KG-augmented methods use diverse strategies for schema retrieval, semantic parsing, program composition, candidate ranking, and structured reasoning. These approaches target stronger retrieval, generalization, or interpretability in KGQA.

Finetuned KG-Augmented LLM Methods: RE-KBQA enhances entity representations with KG relations and extra supervision, while DeCAF jointly combines semantic parsing with LLM reasoning to generate answers.Both methods use structured KG information to support reasoning.
Finetuned KG-Augmented LLM Methods: RoG collaborates LLMs with KGs for trustworthy reasoning, whereas RnG-KBQA ranks enumerated candidate programs and edits top programs into more complex ones.RnG-KBQA limits initial candidate-program complexity before editing.
Finetuned KG-Augmented LLM Methods: FC-KBQA uses fine-to-coarse composition to avoid knowledge entanglement and support generalization and logical interpretability, while Pangu uses an LLM-assisted symbolic agent.These methods emphasize compositional structure and discriminative ability.

E Implementation Details

Experiments use GPT-3.5 and GPT-4 with fixed generation settings and exploration depth. Increasing depth improves CWQ performance, but gains beyond depth 4 become less noticeable while resource and time costs grow exponentially.

E Implementation Details: The experiments use GPT-3.5 and GPT-4 with temperature 0.3, zero frequency and presence penalties, and a maximum generation length of 1024 tokens.The default exploration depth is 4.
E Implementation Details: On CWQ, increasing exploration depth from 1 to 5 improves PoG performance, with less noticeable improvement beyond depth 4.Depth 4 is selected to avoid endless exploration.
E Implementation Details: Greater exploration depth causes exponential growth in resource and time consumption, motivating a finite depth setting.The paper balances performance gains against computational cost.

G Case Analysis

PoG’s self-correction reverses erroneous exploration in a substantial share of cases and supports correct answers across datasets. A case comparison shows that adaptive breadth and sub-objective memory avoid hallucinated or condition-incomplete answers.

24% of CWQ cases involve reversing during exploration, indicating that self-correction is necessary for KG-augmented LLMs.The reversal rate measures cases where exploration backtracks to achieve self-correction.
After self-correction, correct answers reached 64% on WebQSP and 48% on CWQ.Figure 6 reports the proportion of correct answers obtained after PoG’s self-correction process.
PoG answers the Claude Debussy question with Incidental music, whereas the comparison outputs hallucinated Impressionism-based answers.The case contrasts PoG’s answer with answers that infer the genre from one or both conditions without sufficient support.
PoG adaptively selects the relevant relation and later only Ballet after recording the first sub-objective’s known information in memory.This case illustrates how adaptive breadth and memorized sub-objective status guide successive exploration.

H Broader Impact & Limitation

PoG is presented as improving complex KG-augmented LLM reasoning through dynamic exploration and self-correction. Its scope remains limited by uncertainty, multi-step efficiency costs, and weaker semantic understanding for non-standardized queries.

Broader Impact: PoG’s guidance, memory, and reflection mechanisms are presented as improving flexibility, accuracy, and self-correction for complex KG queries.The broader-impact discussion connects dynamic exploration and backtracking with more efficient and accurate problem solving.
Broader Impact: PoG may expand applications requiring complex queries and large volumes of data through more accurate and quicker responses.This is stated as a broader-impact implication of the paradigm’s reasoning capabilities.
Limitation: For more complex problems, PoG remains limited by low self-confidence, multi-step efficiency costs, and insufficient semantic understanding of non-standardized queries.The paper proposes confidence evaluation, step reduction, query rewriting, or user interaction as future directions.