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

Summary

This paper aims to improve KG-augmented LLMs by introducing a self-correcting adaptive planning paradigm. PoG uses three important mechanisms: Guidance, Memory, and Reflection. Guidance leverages LLM to decompose the query into subqueries; Memory stores historical retrieval and reasoning information for reflection; and Reflection uses LLM to decide whether to continue exploration or generate the final output. Experiments show the effectiveness of PoG compared to other SOTA methods and also demonstrate improved efficiency.

Strengths

1. The design of the memory is effective, especially the Sub-Objective Status part. The status of sub-objectives contains the current known information related to the sub-objectives and can effectively remind the LLM of the known knowledge so far and the progress of exploration. 2. The experimental results are also good, showing strong improvement over existing methods. 3. PoG is training-free, which makes it suitable to serve as a plug-and-play for evolving LLMs.

Weaknesses

1. The self-correction is restricted to the retrieval process. However, whether the final answer can be correctedly answer also depend on how the query was decomposed. If the decomposed sub-queries are not suitable for retrieval, the self-correction cannot handle this case. 2. Even though PoG improves efficiency compared with previous methods, it still requires multiple interactions with the LLM (more than 6) and incurs latency, especially for real-time QA (more than 10 seconds on all datasets as reported).

Questions

1. In Table 4, is the number of input/output tokens the average of every single LLM call or for the whole QA?

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

2

Limitations

See weakness above

Summary

This paper proposes a new self-correcting adaptive planning paradigm for KG-augmented LLM named Plan-on-Graph (PoG). It has three important mechanism: Guidance, Memory and Reflection. Experiments on three knowledge graph question answering datasets show good results.

Strengths

1, The paper is presented well. The four steps of the algorithm are well explained with Figure 1 and Figure 2, which makes the paper easy to understand. The authors also provide a case study to explain the new method. 2, The experiment results are good compared with other Prompting KG-Augmented LLM methods.

Weaknesses

The weakness of this paper is from the novelty side. The proposed method PoG is like a trivial improvement on the knowledge graph reasoning task based on [Graph of Thoughs (GoT)](https://ojs.aaai.org/index.php/AAAI/article/view/29720). The path explored in this paper also forms a graph like the graph in GoT paper. And the self-reflection and evaluation are like the backtracing and refining steps in GoT paper. The proposed method just adapts these GoT steps in knowledge graph reasoning task.

Questions

Can the authors explain more about the difference of the proposed PoG method and GoT method? My suggestion is to clarify more on why PoG is not a trivial adaption of GoT on knowledge graph tasks.

Rating

5

Confidence

4

Soundness

3

Presentation

4

Contribution

2

Limitations

Yes the authors adequately addressed the limitations.

Summary

This paper proposes a self-correcting adaptive planning paradigm for KG-augmented LLM called PoG. It consists of four components: task decomposition, path exploration, memory updating, and evaluation. Experiments on three datasets demonstrate the effectiveness of PoG, outperforming previous methods.

Strengths

1. The introduction of the self-correcting and adaptive planning mechanism enhances the reasoning capabilities of KG-augmented LLMs. 2. The experimental results support the effectiveness and efficiency of PoG. The comparison with state-of-the-art baselines demonstrates its superior performance.

Weaknesses

1. Although the paper has achieved certain results in the experiments, it lacks sufficient analysis on why PoG can achieve better results compared to the baseline models. Additionally, for other KG-augmented LLMs such as ToG[1], ARI[2], and RoG[3], the paper does not sufficiently highlight the advantages and differences of the proposed method. 2. There is a concern about the efficiency of the proposed method. In a KG, there may be thousands or even millions of entities. Taking Figure 2 as an example, a singer may have hundreds of songs. When the LLM completes the first step of reasoning (finding the singer's songs) and proceeds to the second step of finding the songs that have won awards, the LLM may need to be called hundreds of times? This could potentially lead to inefficiency and increased computational costs. 3. The paper could provide more details on the potential limitations and challenges of PoG, as well as possible strategies to overcome them. [1] Think-on-graph: Deep and responsible reasoning of large language model with knowledge graph [2] Temporal knowledge question answering via abstract reasoning induction [3] Reasoning on graphs: Faithful and interpretable large language model reasoning

Questions

1.How are the topic entities in the question obtained? 2. When there are too many candidate entities, how does the model ensure the efficiency of reasoning? 3. After selecting the wrong relation or entity, how does the model perform backtracking and reflection?

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

The paper could provide more details on the potential limitations and challenges of PoG.

Summary

The paper introduces Plan-on-Graph (PoG), a new paradigm for integrating LLMs with KGs to enhance their reasoning capabilities. The main innovation lies in PoG’s self-correcting adaptive planning mechanism, which addresses the limitations of existing KG-augmented LLMs that rely on predefined exploration spaces and unidirectional navigation. PoG breaks down complex questions into sub-objectives, then iteratively explores and corrects reasoning paths using a combination of Guidance, Memory, and Reflection mechanisms. The Guidance mechanism helps in decomposing the question, Memory stores historical data to support reasoning, and Reflection allows the model to self-correct erroneous paths. The authors validate PoG’s effectiveness through extensive experiments on three KGQA datasets, showing that it outperforms state-of-the-art methods in terms of both accuracy and efficiency.

Strengths

- novel reasoning framework with adaptive searching and reflective thinking. - great performance on 3 real-world KGQA datasets validate the effectiveness and efficiency of PoG. PoG achieves the best performance across all three datasets, outperforming both LLM-only and KG-augmented LLM baselines.

Weaknesses

- The PoG framework’s complexity, with its multiple components and iterative processes, might make it challenging to implement and optimize. - The necessity for extensive prompt engineering and management of memory and reflection mechanisms could be resource-intensive. - While PoG performs well on the evaluated datasets, its generalization to other domains or types of KGs is not thoroughly explored. - Not compared with other RAG methods such as REPLUG[1]. - The efficiency and cost can be an important limitation. Efficiency in terms of computational resources and time is a concern, as PoG, while efficient, is still resource-intensive. The reliance on KGs means that the model’s knowledge can become outdated if the KG is not regularly updated. [1] REPLUG: Retrieval-Augmented Black-Box Language Models

Questions

- How does the choice of the exploration depth (set to 4) impact the performance across different datasets? Have you experimented with varying this parameter? - How does PoG perform with larger and more complex KGs that were not part of the evaluation datasets? - How does PoG compare with other recent advancements in RAG methods? - How do you decide when to use the PoG and when to use regular LLM call? Given the expensive cost of PoG, I think it is very unrealistic to run all user queries with PoG. I'd suggest the authors discuss how PoG can be applied in real-world application scenarios.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

discussed

Summary

This paper introduces Plan-on-Graph (PoG), a novel self-correcting adaptive planning paradigm for Knowledge Graph-augmented Large Language Models (KG-LLM). PoG aims to address limitations in existing KG-augmented LLM approaches by decomposing questions into sub-objectives and iteratively exploring reasoning paths, updating memory, and reflecting on the need for self-correction. The method incorporates three key mechanisms: Guidance, Memory, and Reflection, designed to ensure adaptive breadth in self-correcting planning for graph reasoning. Experiments on three real-world datasets demonstrate the effectiveness and efficiency of the proposed approach.

Strengths

- Novel approach: The paper introduces reflection and self-correction in KG path exploration for KGQA, addressing limitations of fixed path breadth and irreversible exploration in previous methods. - Comprehensive context: The paper provides a clear and organized discussion of related work in KG-augmented LLMs, offering a good overview of the research area. - Experimental comparison: The study includes different types of baselines in the experiments, demonstrating the improvements achieved by the proposed model in a broader context.

Weaknesses

- Missing important implementation details: While the paper provides visualized knowledge subgraphs to represent path exploration and memory updates, there is no explicit template or example showing how this graph or tree structure is exactly flattened in the prompts of the LLM agent. The use of arrows for paths in both Figure 3 and 5 creates ambiguity about the real implementation. This makes reader unclear and concerns about the real implementation. - Concerns about model dependency: The proposed PoG method is a pure prompting approach, which raises questions about its applicability and performance on smaller open-source models. There are concerns about whether the performance improvements achieved by PoG are largely due to the capabilities of the advanced base models used, rather than the method itself. - Lack of critical evaluations: The paper is missing several important analyses, such as: - The proportion of cases where the LLM needs to trigger reverse direction path visiting - The frequency with which this revisiting leads to correct or incorrect answers - How the number of breadth in each step affects the effectiveness of the proposed method - Whether the length of hops from the query entity to the answer entity affects the number of revisiting and the method's effectiveness - How consistent or diverse is the exploration path under the proposed method if experiment with multiple trails? - Minor thoughts: Additionally, it would be interesting if the authors could discuss or explore whether this method of constructing paths and memories could support effective post-training of open-source models, though this is not a critical weakness.

Questions

Please refer to the questions raised in Weakness section.

Rating

5

Confidence

4

Soundness

2

Presentation

2

Contribution

3

Limitations

Yes, the author has discussed the limitations in Appendix G, and leave them as future work.

Response

The author's response partially addressed my concerns. I have raised my score. I hope the author further revises the manuscript to make it more complete.

Response

Thank you to the authors for addressing my questions. I will maintain my positive score.

Official Comment by Reviewer vd15

Dear authors, Thanks for your answer. Now I understand more about the innovation part of this paper. I will keep the current score. Thanks, Reviewer vd15