Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs
Authors: Liyi Chen
Panrong Tong
Zhongming Jin
Ying Sun
Jieping Ye
Hui Xiong
Venue: NeurIPS 2024 poster (2024)
Keywords: Large Language Model
KG-Augmented LLM
LLM Explainability
Primary area: interpretability_and_explainability

Abstract: 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.

Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs
Liyi Chen 1,2 Panrong Tong", Zhongming Jin', Ying Sun", Jieping Ye²+, Hui Xiong 3.4+
1 University of Science and Technology of China, 2 Alibaba Cloud Computing, Thrust of Artificial Intelligence, The Hong Kong University of Science and Technology (Guangzhou), DDepartment of Computer Science and Engineering. The Hong Kong University of Science and Technology
liyichencly@gmail. com, yings@hkust-ga edu. en, xionghui@us @ust. hk, {panrong tpr, zhongming. jinzm, yejieping yeleallbbbaainc.commmm com
Abstract
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 efficiency and effect. To address these limitations, propose 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
Large Language Models (LLMs) have manifested outstanding performance in various natural language processing and data science tasks, such question answering 142 25 62]. gen- eration Ig
51 44). and domain Jomain-specific applica- They leverage advanced deep learning techniques and immense amounts of pre-existing text data to understand and generate human language with impressive fluency and coher- ence. Despite their success in numerous applications, LLMs still suffer from out-of-date knowledge, hallucinations, and opaque decision-making highlighting the ongoing need for further investigation this rapidly evolving field.
B
g
15
recommender systems [60] 59
tions 46 45
36).
Intuitively, as large-scale structural knowledge bases, Knowledge Graphs (KGs) 1 43 provide explicit and editable depictions of massive real-world knowledge, which have the potential to be promising complement to the drawbacks of LLMs. Previous studies manage to integrate KGs into
LLM pre-training [6 47 fine-tuning (53] 27 stage. However, these methods mainly compress
structured knowledge in KGs into LLMs parameters in black-box fashion and still cannot fully
thiis work was accomplished when Liyi Chen was an intern at Alibaba Cloud Computing. *Corresponding authors.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Question: Which of Taylor Swift's songs has won American Music Awards (AMAJ? Answer: Blank Space.
Retrieving
KG Retrieving
Compoier
Ed Sheeron
Reading
Speak New
The Joker
Born in
Album
Song
The Joker And The Quaen
The Queen
Release Date
2022-02-11
Taylor Swift
Award
MTV
Song
Shake 11 OFF
Shake 1f Off
Nationalityy
Song
Award
SRIT Award
Crual Summer
America
Blank Space
Cruel Summer
Album
Lover
Reasoning
Relevant Irrelevant
LLM Reasoning
Relevant
Irrelevant
Reading
Speak Now
Composer
Ed Sheeron
Born
Albumm
Song
The Joker And
The Queen
The Joker And
The Queen
Releaze Date
2028-02-11
Taylor Swift
Song
Nationality
Sonig
Song
Song
Shake
Shake It Off
Award
MTV
Gruel Summer
Award
BRIT Award
America
Blonk Space
Cruel Summer
in Album
X
Relevant Triplets: Select most relevant triglets (Breadth 5 3), bacouse
Relevant Triplets: No information related to the "American Music Awards". Therefore, there relevant triplets.
"The And Queen", "Shoke off", "Cruel Summer"
songs Taylor.
Enough Information: Ne.
Enough Information: No.
/Next Action: End refrieval and directly answer "Lve Story without using information from knowledge graphs.
Next Action: Continus netrieving connected entities for relevant tripletzi
Figure I: A toy example of existing KG-augmented LLM paradigm.
enhance the flexibility, reliability, and transparency of LLMs. Therefore, several attempts 3 2 first retrieve information from KGs and then deliver explicit knowledge into LLMs. Under these circumstances, LLMs do not directly participate in the graph reasoning process, making these methods excessively dependent on the KG completeness. Recently, a KG-augmented LLM paradigm has been proposed to conduct graph reasoning, which treats the LLM as an agent to interactively explore related entities and relations on KGs and perform reasoning based on the retrieved knowledge. For instance, StructGPT [99 and ToG (35) predefine the breadth of reasoning paths explored on the KG, and leverage the LLM to iterate the process of unidirectionally extending along the reasoning paths relevant to the question and reasoning the answer using these reasoning paths. This KG- augmenedd LLM paradigm offers an opportunity for more comprehensively amalgamating the knowledge from both the KG and LLM by facilitating the step-by- derivation of further insights.
However, existing paradigm may fail to plan the exploration of correct reasoning paths for many complex questions. Figure Tillustrates an example of existing paradigm's 's limitations when answering the question "Which of Taylor Swift's songs has won American Music Awards? (AMA)". These limitations lie in: (I) Predefined path breadth: Existing paradigm requires manually setting the breadth of reasoning paths in KGs, and fixed breadth may result in all the selected relations or entities being incorrect. When determining the relevance between paths and questions in step 2. due to the limited maximum breadth of three and the uncertainty surrounding the respective awards of songs, the LLM selected maximum numbers of songs, ignoring the correct entity "Blank Space". (2) Irreversible exploration direction: The path exploration in existing paradigm unidirectional without the ability to self- self-correct. Even if the paths are incorrect, the LLM still continues to extend current incorrect paths and lead to the failure of reasoning on the KG. In step 3 and ④ since "The Joker And The Queen", "Shake It Off",, and "Cruel Summer" were already chosen, the reasoning process continued on incorrect paths and the right answer was not found. (3) Forgetting partial conditions: During reasoning. the LLM may forget partial conditions in the question and cannot provide the answer that satisfies multiple conditions simultaneously. In step ④ the LLM only remembered the condition that the song was by Taylor Swift but forgot the condition about the song winning an AMA award, leading to an incorrect answer, "Love Story". Therefore, the reasoning of complex questions may heavily rely adaptive exploration and self-correctinn of erroneous reasoning paths.
To address these limitations, we propose a novel self-correcting adaptive planning paradigm for KG- augmented LLM named Plan-on-Graph (PoG). To the best of our knowledge, we are the first to design a reflection mechanism for self-correction and adaptive KG exploration into KG-augmented I.L.ss effectively improving the ability and efficiency of LLM reasoning. Specifically, PoG first decomposes

---

the question into several sub suboobjectives as guidance for planning exploration, and then repeats the process of adaptively exploring reasoning paths to access relevant KG data, updating memory to provide dynamic evidence for reflection, and reflecting on the need to self-correct reasoning paths until arriving at the answer. In PoG, three mechanisms are designed for adaptive self-correcting planning: (1) Guidance: To better guide adaptive exploration by harnessing conditions in the question, we employ the LLM to decompose the question into sub-objectives containing conditions, thereby benefiting the identification of relevant paths to each condition with flexible exploration breadth. (2) Memory: The information stored in memory offers historical retrieval and reasoning information for reflection. We record and update the subgraph to provide the LLM with all retrieved entities for initializing new exploration and self-correcting paths, reasoning paths to preserve the relationships between entities for LLM reasoning and allow for path correction, and sub-objective status to make the L.M recognize the known information of each condition and mitigate its forgetting in reflection stage. (3) Reflection: To determine whether to continue or self-correct current reasoning paths, we design a reflection mechanism to employ the LLM to reason whether to consider other entities into new exploration and decide which entities to backtrack to for self-correction based on information in memory. Finally, extensive experiments on three real-world KGQA datasets validate the effectiveness and efficiency of PoG [1 The main contributions of this paper are listed as follows:
We propose a novel self-correcting adaptive planning paradigm for KG- (GGaugeeeted LLM named PoG, which exploits the LLM plan the adaptive breadth of reasoning paths and reflect to self-correct erroneous paths. To the best of our knowledge, we are the first to incorporate reflection mechanism for self-correction and adaptive KG exploration into KG-augmented LLMs, effectively augmenting the LLM's reasoning ability.
We specially design Guidance, Memory, and Reflection mechanisms for PoG. Guidance harnesses question conditions to better plan adaptive exploration by decomposing task into sub-objectives including conditions. Memory records the subgraph, reasoning paths, and sub-objective status to provide historical retrieval and reasoning information for Reflection. Based on Memory, Reflection reasons whether to self-correct reasoning paths and which entity to backtrack to for initiating new exploration.
We conduct extensive experiments on three real-world KGQA datasets, namely CWQ, We- bQSP, and GrailQA. The results demonstrate not only the effectiveness but also the efficiency of our proposed novel PoG paradigm for KG-augmented LLM.
2 Preliminary
Knowledge Graph (KG) stores massive factual knowledge in the form of a set of triplets: G (lc,r,e))eee E E.r R}. where E and R denote the set of entities and relations, respectively.
Relation Paths are a sequence of relations: 2 (ri, r?..., TT}, where rÚ R denotes the i-th relation in the path and l denotes the length of the path.
Reasoning Paths are the instances of relation path in the KG: p= = eg r161 - T262 rrez, where e, E E denotes the i-th entity and r; denotes the i-th relation in the relation path z.
Knowledge Graph Question Answering (KGQA) is the task of answering natural language ques- tions based on a set of facts over the KG. Given a question q, a knowledge graph G. and topic entities T3 mentioned in q, the target of KGQA is to generate answers Ag to the question q. Following previous studies [35], we assume any entity eg E T, mentioned in q and answers ag E Ag are labeled and linked to the corresponding entities in G, ie.. Tq. Ag C E.
3 Methodology
In this section, we introduce the technical details of the novel self-correcting adaptive planning paradigm for KG-augmented LLM named Plan-on-Gran (PoG). As illustrated in Figure 2 PoG consists of four key components: Task Decomposition, Path Exploration, Memory Updating, and Evaluation. PoG first decomposes the question into several sub-objectives as guidance of planning exploration and then repeats the process of adaptively exploring reasoning paths to access relevant KG data, updating memory to provide historical retrieval and reasoning information for reflection, and reflecting on the need to self-correct reasoning paths until arriving at the answer.
https://gittuu/ http://hhhha..ol/lyicceeeeeeeeee cly/PoG
3

---

Task Decomposition
Task: Aeswer the question "Which of Taylor Switts sangs has won Americon Music Award:s (NWA) Sub-Ob Sub-Objactives: Find the songe of Taylor Swift. 2. Find the awords these songs have Identify the with American Music Awardss (AMA).
Path Exploration
Path Exploration
Relevont
Irrelesant
Reading
Alburm
Speak Now
Joker And
"Cmppsse
Sheeron
Path Exploration
Nationality
Tayfor
Swift
Born
Song
Song
Song
Song
Spnig
Shake
Joker
Queen
Shake
Release
Aword
Awarrd
2022-02-11
BRIT Award
MTV VMA
Blank Space
Love Story
Award
Award
AMA
BME
America
Blank Space
Cruel Summer
In Album
Lover
CMIT Music
Nwwrrds
30
Memory Updating
Mamory Updating
Memory Updating
Memory
Memory
Memory
Subgraph
Ressoning Patha
Sub- Objectives
Subgraph
Recsoning Paths
Sub- Objectives
Subgraph
Reasoning
Patha
Objectives
1. "The Toker And The Queen?, "Shake 1I OFF". and "Onuel Summer" are the tonge of Taylor 2. No relevont information.
Joker And Queen", "Shake OFF".
The Soker "Bannk Space", "Love Story"...
and "Cruel Summer" are the songs of Taylor. "Shake OFF has wan MTV Vith and No relevent information.
one the songs of Taylor.
2. "Shake and "Blank Spacel has won AMA,
3. No relevent information.
and "Love Slory" has BMI and AMA.
"Blank Spoce"
Evoluation
Evaluation
.00
Evaluatioo
Insufficient
Knowledge
Reflect
Continue
Correct
Knowledge
Insufficient
Reffect
Continum
Correct
Insufticint Knowweegge
Reffect
Continue
awards information "The Jaker Queen", "Shake 11 off". and "Cruel Summer", so I meed to conlinue.
Knowledge
Sufficient
Output
"The Jöker And The Queeen", "Shake 11 off", and "Gruel Summer" have not wan AMA I need to Find other add the "Blank Spate", "Love Story". into the fullowing seploration.
Inowledie
Sufficient
Output
Knowelddee
Sufficient
Output
Correct
"Blonk Space" the song of Tayler Swift, and If has won AMA. The answer is Blank Space.
Figure 2: The framework overview of PoG, which includes four key components: Task Decomposi- tion, Path Exploration, Memory Updating, and Evaluation.
3.1 Task Decomposition
To harness conditions in the question to better guide the adaptive exploration process. PoG decom- poses the task of answering the question into multiple sub- uub-objectives containing conditions through semantic analysis of the I.L.M Sub-objectives serve as guidance for path exploration, benefiting the identification of relevant paths to each condition outlined in the question with flexible explo- ration breadth. Specifically, we prompt the LLM to decompose the original question q into list of sub-objectives for KG retrieval and reasoning. The prompt is shown in Appendix [A.] The list of sub-objectives can be denoted as = {0r, 02, 03, J. It is important to note that sub-objectives in O may refer to the results obtained from other sub-objectives in O, allowing for interdependencies in the reasoning process.
3.2 Path Exploration
We access relevant information from the KG by exploring reasoning paths in the KG. On the initiation of path exploration, we localize the initial entities of reasoning paths, which correspond to the topic entities mentioned in the given question. Similar prior research 35) topic entities have been pre-identified and are part of the annotated datasets. Specifically, when presented with a question q, we use topic entities to serve as the initial elements of the reasoning paths, E Tq = (el, eg. No. ).
where No is the number of topic entities.
In the subsequent iterations, we continue exploring reasoning paths most relevant the question and suspend other reasoning paths. Taking the D-th iteration as an example, before the iteration starts, each reasoning path Pn E P consists of Dp. (Dp.. < D- 1) triplets, i.c., Pv: {(ed r ed. ed,,) where ei, and ed,, denote subject and object entities, rs.n is a specific relation between them, (eg j.n. ed,n) and (ed+1 - d+1 .edt.)) ) are linked to each other. It is noted that the length of each reasoning path may vary, because in the D-th iteration, we only continue exploring the reasoning paths most semantically relevant the question, which are identified in the D 1-th iteration. The sets of tail entities and relations to be explored are denoted as DDD1 {cf D- ez
) Dpn d= I
D-1
e D k
and DD {rP D-1 DD11 D-1
.12 ..... No-, }. respectively, where ND-1 is the length of DD and

---

RD-1. We leverage the LLM to identify the most relevant entities E from the neighboring entities of the current entity set E based on the question q and extend the reasoning paths P with E In order to manage the complexity of dealing with a large number of neighboring entities using the ILM,, we propose an adaptive exploration strategy that not limited by the fixed number of relations and entities. This strategy involves a two-step process of finding relevant relations and utilizing these selected relations to explore entities.
Relation Exploration. Relation exploration is a process to retrieve the relations of all tail entities in ED-1 and identify the most relevant relations the question q and the sub- sub-objectives O. To be specific, we first conduct the search to obtain all relations linked to the tail entities in E as the candidate relation set R Rannd = {r cand. T cond,2: .... T cand.NN }. We utilize R to extend the reasoning paths into candidate reasoning paths Peand- Then, we employ the LLM to select a flexible number of relevant reasoning paths P ending with the tail relations in RD from Poonds based on the semantic information of the question q, tail entities ED-1, candidate relations Reand- and sub-objectives O. The prompt is shown in Appendix A.2.1 and the pre-defined query for relation search is shown in Appendix B.1
Entity Exploration. Analogously, entity exploration is process to retrieve neighboring entities based on RD and D' and detect the most relevant entities to the question q. From the previous relation exploration, we obtain extended reasoning paths P and new tail relations RD. For each reasoning path Pn, P. we can execute the queries of ( . ?) or (?, r e 2-11 to retrieve a candidate entity set F where < and r are the tail entity and relation in Pn- When confronted with large number of candidate entities, we to calculate the similarity between candidate entities and the question for recall. Then, we summarize all candidate entity sets into E and use Eognn as the tail entities to expand P into Peand. With the candidate reasoning paths P Peand. we exploit the LLM to choose a flexible number of relevant reasoning paths P' ending with the tail entities E. from Peand- based on the semantic information of the question q and knowledge triplets composed of tail entities ED-1, tail relations RD and candidate entities ED E The prompt shown Appendix A.2.2 and the pre-defined query for entity search is shown in Appendix B.2
small pre-trained DistilBERT 31
3.3 Memory Updating
The information stored in memory provides historical retrieval and reasoning information for reflec- tion. After a two-step exploration, we dynamically update the searched subgraph Gsus, reasoning paths P. and sub-objective status S in memory based on the ongoing reasoning process.
Subgraph. The subgraph includes all retrieved relations and entities from the KG. We update the subgraph in memory. which can be utilized during later reflection determine which entity to backtrack to for self-correction. In the D-th iteration, the searched subgraph Gsub is updated by adding the retrieved candidate relation set Roand and candidate entity set ED Eoend-
Reasoning Paths. In order to ensure that the LLM can understand relationships between entities for better reasoning and allow for path correction in reflection stage, update reasoning paths P to preserve the semantic structure within the KG.
Sub- Cuj-Ohjectivve Status. The LLM may forget partial conditions in the reasoning process. Sub- objectives obtained by decomposing the question can help the LLM remember multiple conditions in the question. The status of sub-objective. contains the current known information related to the sub-objectives, which can aid the LLM in remembering the known information of cach condition and determining whether to correct the exploration direction in reflection stage. Hence, we leverage the LLM to update the currently known information relevant to sub-objectives into sub-objective status S == {s1, $2, $3.... |S| |O], based on the semantic information of the question q, sub-objectives O, historical sub-objective status, and reasoning paths P, along with the LLM'ss own knowledge. The prompt is shown in Appendix A.3
3.4 Evaluation
After the path exploration and memory updating, PoG prompts the LLM to reason whether the current acquired information, including sub-objective states and reasoning paths recorded in memory, is sufficient to infer an answer. The prompt is shown in Appendix A.4.I If the LLM determines that the
base-tas-B
5

---

information is sufficient, it will integrate reasoning paths, sub-objective states, and its own knowledge to provide an answer. When information is considered insufficient, there may be two situations. One is that PoG will acquire sufficient information after further extension of current paths, and the other is that current paths are incorrect. Since the reasoning capability of the L..M does not always guarantee the correctness of path exploration, there is need to self-correct erroneous reasoning paths. Therefore, we design a reflection mechanism to determine whether and how to self-correct reasoning paths. When the LLM believes that the information is insufficient, PoG enters the stage of reflection. Specifically, PoG utilizes the LLM to reflect on whether to correct the current exploration direction based on the question q. sub-objective status S, reasoning paths P, and entities planned for the next iteration of retrieval E from memory. Besides, the LLM will provide the reason for the reflection result. If the LLM judges that it is necessary incorporate additional entities beyond those in FD for exploration. then a self-correction of reasoning paths is needed, Otherwise, PoG will continue exploring along the current reasoning paths with tail entities in F.D. For self-correction, PoG employs the L.L to decide which entities in Feand = F U F U... U F to backtrack to based on sub-objective states in S and the reason for additional retrieval obtained from the reflection, and adds new exploration of backtracked entities Eud into EDD for the self-correction, denoted as E
E ED The prompts for reflection are shown Appendix A.4.2
add-
4
Experiments
4.1
Experimental Setups
4.1.1 Datasets & Evaluation Metries
To demonstrate the effectiveness of PoG on complex reasoning over knowledge graphs, we adopt three representative hop KGQA datasets: CWQ [37]. WebQSP [56], and GrailQA [17]. All three datasets rely on the external knowledge graph from Freebase [5]. For the large dataset GrailQA, we
utilize the same testing samples as those in ToG 35 to improve computational efficiency. Following prior research
23 19 35,,
we use exact match accuracy (Hits@) as the evaluation metric.
4.1.2 Comparison Methods
Due to variations in the performance of the method across different datasets, we select prior state-of- the-art (SOTA) approaches as baselines for each dataset. They can be categorized into two groups:
(1) LLM-only methods, including standard prompting (IO prompt) [6]. Chain-of- ThoThht prompting
(CoT) 49,, and Celf-Consistency (SC) 48
(2) KG-augmented I.IM methods, including fine-tuned and prompting methods. For CWQ
Table 1:
Performance comparison of different methods on CWQ and WebQSP.
and WebQSP, we utilize UniKGQA
20
Method
CWQ
WebQSP
TIARA [34], RE-KBQA 771 DeCAF [57].
LLM-Only
and RoG [27 as fine-tuned baselines and KD-
COT 40, KB-BINDER (23), StructGPT 19),
TO Prompt 6
37.6
63.3
Interactive KBQA (52), and ToG (35) prompt- ing baselines. For GrailQA, we utilize RnG-
CoT 49
38.8
62.2
SC 48
45.4
61.1
KBQA [55]. TIARA (34, FC-KBQA (58).
Fine-Tuned KG-Augmented LLM
Pangu [6]. FlcxKBQA 26), and GAIN [33] as
UniKGQA 20
$1.2
79.1
fine-tuned baselines and KB-BINDER [24] and
TIARA D4
75.2
ToG (35] as prompting baselines. The descrip- tions of baselines are presented in Appendix D
RE-KBQA
50.3
74.6
DcCAF 57
70.4
82.1
RoG 27
62.6
85.7
4.2 Performance Comparison
Prompting KG-Augmented LLM w/GPT-3.5 or others
We compare PoG with the SOTA baselines to demonstrate its effectiveness for KG-augmented LLM. Table I and Table 2 present the experi- mental results on CWQ, WebQSP, and GrailQA datasets. Overall, PoG achieves the best per- formance across all three datasets. Specifically, we can make the following observations. First, compared to all prompting KG-aaumented L.LM baselines, PoG shows superior performance vantages. Regardless of whether GPT-3.5 or
KD-CoT 41
50.5
73.7
KB- BE-BINDER 25
74.4
StrucIGPT 19
54.3
72.6
ToG 35
57.1
76.2
PoG
63.2
82.0
Prompting KG-Augmented LLM w/GPT-4
InteractiveKBOA 52
59.2
72.5
ToG (35
67.6
82.6
PoG
75.0
87.3

---

Table 2: Performance comparison of different methods on GrailQA.
GrailQA
Method
Overall
L.I.D
Compositional
Zero-shot
LLM-Only
10 Prompt
29.4
CoT 49
28.1
SC 48
29.6
Fine-Tinne KG-Augmented L.M
RnG-KBQA
55
68.8
86.2
63.8
63.0
TIARA [34
73.0
87.8
69.2
68.0
PC-KBQA [58]
73.2
88.5
70.0
67.6
Pangu 16
75.4
84.4
74.6
71.6
FlexKBQA 26
62.8
71.3
59.1
60.6
GAIN 3
76.3
88.5
73.7
71.8
Prompting KG-Augmented LLM w/GPT-3.5 others
KB-BINDER
23
50.6
ToG R5
68.7
70.1
56.1
72.7
PoG
76.5
76.3
62.1
81.7
Prompting KG XG-ummeeted LLM w/GPT-4
ToG 35
81.4
79.4
67.3
86.5
PoG
84.7
87.9
69.7
88.6
GPT-4 is used the underlying LLM, PoG substantially outperforms the SOTA baseline, ToG, ToG explores reasoning paths with fixed exploration breadth and cannot detect or correct the errors, showing limitations in effect and efficiency. Meantime, we specially design self-correction and adaptive planning mechanisms, which can effectively improve both performance and efficiency. Second, although PoG is training free prompting method, its performance is highly competitive with tnnettuned KG-augman auggenedd LLM baselines. When using GPT-4, the performance of PoG exceeds all fine-tuned KG-augmented L.M baselines across the board. Even with GPT-3.5, the result of PoG on GrailQA surpasses all fine-tuned KG-augmented L.M methods. This suggests that our designed guidance, memory, and reflection mechanisms allow PoGi's effect surpass most of the fine-tuned methods. Third, the improvement of PoG is obvious when compared to LLM-only baselines, which do not leverage external KGs. Besides, all KG-augmented LLM methods consistently outperform LLM-only methods, indicating the value of incorporating KGs to enhance LLM performance. More- over, PoG further improves the effectiveness of KG-augmented LLMs through its self-correctable adaptive planning. Additionally, it is worth noting that PoG with GPT-3.5 outperforms other methods on the zero-shot subset of the GrailQA dataset by a large margin, apparently outperforming all fine-tuned KG-augmented LLMs this category. The self-correction mechanism in PoG allows it to dynamically correct errors during the reasoning process, which crucial for zero-shot problems.
4.3 Ablation Study
Table 3: Performance of removing each mecha-
In order to assess the effectiveness each mech- anism and adaptive exploration in PoG, con- duct the ablation study to remove them on three datasets, respectively. Specifically, w/o Guid- ance refers to the variant where entire task de- composition as guidance removed. w/o Mem- ory indicates the variant without the memory mechanism. w/o Reflection refers the variant where, in the case of insufficient information, it only continues exploring along the original reasoning paths. w/o Adaptive Breadth means that the variant uses fixed exploration space breadth instead of adapting it based on the situation. Table the performance of all variants and the results suggest that each mechanism and adaptive breadth appears to contribute positively to overall performance, with their removal leading to weaker results on complex question answering tasks across the evaluated datasets. These variations achieve minimum reduction of 3.0%, 2.1 %, and 3.5% on CWQ, WebQSP, and GrailQA, respectively. The performance of w/o Memory drops the
nism and adaptive exploration, respectively.
Method
CWQ WebQSP GrailQA
PoG
63.2
82.0
76.5
w/o Guidance
60.1
80.3
72.4
w/o Memory
58.9
77.5
69.3
Reflection
59.4
78.1
70.5
w/o Adaptive Breadth
61.3
80.2
73.8
7

---

Table 4: Efficiency comparison between our proposed PoG and the baseline ToG.
Dataset
Method
LLM Call
Input Token
Output Token
Total Token
Time (s)
ToG PoG
22.6
8,182.9
1,486.4
9,669.4
96.5
CWQ
13.3
7,803.0
353.2
8,156.2
23.3
ToG
15.9
6,031.2
987.7
7,018.9
63.1
WebQSP
PoG
9.0
5,234.8
282.9
5,517.7
16.8
ToG
11.1
4,066.0
774.6
4,840.6
50.2
GrailQA
PoG
6.5
3,372.8
202.8
3,575.6
11.5
most, followed by w/o Reflection, because without the memory there is no information to support PoG navigating the exploration and achieving self-correction, and PoG cannot self-correct the wrong reasoning paths without the reflection mechanism. Moreover, after setting fixed maximum breadth for exploration, the performance deteriorates. This indicates that a fixed breadth makes the method lack flexibility and less adaptable to different questions. However, because the mechanisms of memory and reflection ensure that PoG is able to self-correct, the performance of w/o Adaptive Breadth does not decrease lot.
4.4 Efficiency Study
We study the efficiency of PoG and the SOTA prompting KG-augmented LLM baseline, ToG. Table presents the average LLM call, token consumption, and time required by both methods to answer a question across three datasets. In all datasets, PoG demonstrates clear advantages over ToG in terms of all metrics. For average number of LLM calls, PoG consistently requires fewer calls to the LLM, and reduces it by at least 40.8%. This highlights PoG's ability to reason more efficiently with fewer LLM interactions. Regarding token consumption, PoG exhibits notable advantage in both input and output token usage. On CWQ, compared to ToG's input tokens, PoG shows a reduction of approximately 4.6% input token consumption. As for output tokens, PoG produces just 353.159 output tokens, representngg substantial decrease of roughly 76.2%. This indicates the effectiveness of PoG in reducing the overall token consumption during the reasoning process. Most importantly, PoG achieves superior time efficiency compared to ToG. On CWQ and GrailQA, PoG presents speedup of over times. ToG predefines the breadth of exploration, leading to the exploration of many irrelevant paths. Additionally, ToG lacks self self-correction mechanism, and when there is insufficient information to answer a question, can only extend the current reasoning paths, sacrificing a lot of efficiency on irrelevant explorations. By contrast, the efficiency advantages of PoG can be attributed to its adaptive exploration and self-correction of reasoning paths based on the semantics of the question. The adaptive breadth reduces unnecessary exploration, and effective correction avoids the extending of wrong current paths.
4.5 Case Study
FigureBishowe typical case from the testing results CWQ dataset. We compare the results of PoG, ToG, and CoT in answering the question "Who is in control of the place where the movie 'The Naked and the Dead' takes place?". The underlying LLMs they used are all based GPT-3.5. PoG initially identifies a flexible number of relations related to the topic entities. Specifically, for "The Naked and the Dead", PoG successfully discovers that the movie takes place in Panama, while for "President of Panama", the LLM thinks that only the relation "government, government officee_oor..eee oor jr_iitle.jjue itteejurisdiction" relevant. Upon retrieval, no information is found regarding the person in control of Panama. This triggers reflection as PoG realizes that it lacks sufficient information. With the memory, PoG refers the sub-objective status and recognizes that it already knows the movie location (Panama) for sub-objective #1 but is unaware of the person in control of Panama for sub-objective #2. Based on the current reasoning paths, PoG makes a decision to execute self-correction and returns to exploring the relation not previously explored for "President of Panama". Due to the task decomposition, during the self-correction process, becomes easier to identify the correct relation government offfce_ or "wwpccccchchheerrr"" according to the sub-objectives. Through the guidance, memory, and reflection mechanisms, PoG successfully finds the correct answer, "Juan Carlos Varela". In contrast, ToG fails to identify the most relevant relation concerning "President of Panama" and continues exploring incorrect paths. This consumes a significant amount of time and ultimately leads to an erroneous answer due to the hallucination. CoT refuses to answer directly since the I.L. realizes its lack of knowledge regarding the answer and requires additional information to be provided. From this analysis, it is evident that PoG outperforms ToG and COT. PoG successfully
"govermmen.govvemmeet
8

---

Question: Who is in control of the place where the movie "The Naked and the Dead" takes place?
Answer: [Refused to answer.] I'm sorry, but need to clarify the question bit further in order to provide an accurate answer. Could you please specify whether you are referring to the character or the entity in control of the place where the movie "The Naked and the Dead" takes place? Thank you for your understanding.
CoT
question according to its own knowledge. First, the movie "The Naked and the Dead" takes place during World War II. Second, the United States Army is in control of the place where the movie takes place.
Answer: [KG exploration failed, and the LLM answered
ToG
Paths: The Naked the Dead film. fil..ccuttry United States America film. film. featured film locations + Panama
President of Panama government.goverrmentt cacprtt_fffc_eeeeeeeeeeeee htrffiic__o_iitleejrriieeeee ttt.e..jriiiicitiinn
gpoeerrennttl_iiiisscctttooooo www.rrmmnttteeeeeee.o...ommmm.. government_positionn government, wwwp:etnowweeeeeeooaaaaa www.ijjitiiiiiooooo htt.://rre.ooeeeeeeoooooottooooo
[Through reflection to self-correct paths, the answer was found on the revised paths.] The movie "The Naked and the Dead" takes place in Panama. The President of Panama, Juan Carlos Varela, is in control of Panama based the knowledge triplets.
Answer:
Sub-Objectives: 1. Identify the place where the movie "The Naked and the Dead" takes place; 2. Determine the authority or governing body in control of that place.
PoG
Sub-Obiective Status: 1. The movie "The Naked and the Dead" takes place in Panamaj
2. The President of Panama, Juan Carlos Varela is in control of Panama.
ClL.utty Paths: The Naked and the Dead + film. country + United States of America
film featured filttueel film Locations Panama President of Panama government. government office or_ or_rrrr_ttt__ government. www.ort..goreemmmeeeee.mm
ritle.jjrisdicte Carlos Varela Satpmmeent_fffcceeeeeee office_ title.office holders m. 010gg022
cettrmmmentt.ovvereeentntn cerrritttooneeeddd.e held. htt.iiooonneddoo.fifeeeeee holder
Figure A typical case to compare different methods answer the complex question. For the convenience of display, we only provide the sub-objective status and partial reasoning paths stored in memory. Topic entities, wrong answers, and correct answers are highlighted in blue, red, and green. The revised path is highlighted with yellow background.
leverages sub-objective status self-correct the exploration path in the reflection stage and finally provides the correct answer.
5 Related Work
LLM Reasoning. To encourage LLMs engage reasoning rather than simply providing answers
directly, many researchers instruct LLMs to generate the process of thinking in their outputs [49
22
(63. In the early stages, Chain of Thought (CoT) [49] was designed provide a few examples
of intermediate natural language reasoning steps as the prompt. After that, several variants of
CoT reasoning with different forms like Tree-of Tree-of-Thought (54). Traph-of-Thought [4] Memory of
Thought 24], and Skeleton-of- Thought [30 were proposed to enhance the thinking process. However,
LLMs may make mistakes during the reasoning process. Hence, many works [32 21
29]
designed self-correction mechanisms based on feedback to rectify flawed reasoning and ensure accuracy. Additionally, large efforts were dedicated to guiding LLMS understanding complex graph structures [39] (88 and improving their graph reasoning across different graph tasks [11 10 9
However, it is still an open issue to address the outdated knowledge, hallucinations, and opaque makingg for LLM reasoning.
KG-Augmented LLM. Despite the pre-training of LLMS on massive corpora, they still suffer from limitations such as outdated knowledge, hallucinations, and opaque decision-mann -akinn.. An effective approach to address these limitations to leverage KGs for explicit and editable knowledge provision to LLMs. Previous studies integrated KGs into LLM pre-training [61, 47 or fine-tuning [53] 27 stage, but they merely inject structured knowledge into LLMs' parameters and still leave these limitations unexplored. Therefore, several works 3 2 40 first retrieved information from KGs and then directly fed explicit knowledge into L.Mss. In this way, L.MSs do not involve the graph reasoning process and cannot provide potential insights. Then, novel KG-augmented LLM paradigm [19 35

---

was proposed to treat the LLM as agent to interactively explore related entities and relations on KGs and perform reasoning based on the retrieved knowledge. Although this KG-augmented LLM paradigm has achieved impressive performance, it still faces the challenges of adaptively exploring the KG based on question semantics and self-correcting erroneous reasoning paths. To the best of our knowledge, our work stands out as pioneering effort in successfully integrating reflection mechanism for self-correction and adaptive KG exploration into KG-augmented LLMs, effectively enhancing the LLM's reasoning ability.
6 Conclusion
In this paper, we proposed a novel self-correcting adaptive planning paradigm for KG-augmented LLM named Plan-on-Graph (PoG). To the best of our knowledge, we were the first incorporate reflection mechanism for self-correction and adaptive KG exploration into KG-augmenned LLMs, effectively augmenting LLM's reasoning ability and efficiency. PoG first decomposed the question into several sub-objectives, and then repeated the process of exploring reasoning paths, updating memory, and reflecting on the need to self-correct reasoning paths until arriving at the answer. To be specific, three important mechanisms were designed to work together to guarantee the adaptive breadth of self-correcting planning for graph reasoning, i.e., Guidance, Memory, and Reflection. Finally, extensive experiments on three real-world KGQA datasets validated not only the effectiveness but also the efficiency of the proposed PoG.
Acknowledgments and Disclosure of Funding
This work was supported in part by the National Key Research and Development Program of China (Grant No. 2023YFF0725001), the National Natural Science Foundation of China (Grant No. 92370204, 62306255), the Guangdong Basic and Applied Basic Research Foundation (Grant No. 2023B 1515120551 2024A151500 1839), the Hrungzhou-HKUSS (GZ) Joint Funding Program (Grant No. 2023A03J0008), and the Alibaba Research Intern Program.
References
[1] Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives. Dbpedia: A nucleus for web of open data. In international semantic web conference, pages 722-735. Springer, 2007.
[2] Agnes Axelsson and Gabriel Skantze. Using large language models for zero-shot natural language generation from knowledge graphs. In Proceedings of the Workshop on Multimodal, Multilingual Natural Language Generation and Multilingual WebNLG Challenge (MM-NLG 2023), pages 39-54, 2023.
[3] Jinheon Baek, Alham Aji, and Amir Saffari. Knowledge-augmmented language model prompting for zero-shot knowledge graph question answering. In The 61st Annual Meeting Of The Association For Computational Linguistics, 2023.
[4] Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, et al. Graph of thoughts: Solving elaborate problems with large language models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 17682-17690, 2024.
[5] Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: collaboratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 1247-1250, 2008.
[6] Tom Brown, Benjamin Mann. Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 13:7-1119 2020.
[7] Yong Cao, Xianzhi Li, Huiwen Liu, Wen Dai, Shuai Chen, Bin Wang, Min Chen, and Daniel Hershcovich. Pay more attention to relation exploration for knowledge base question answering. In Findings of the Association for Computational Linguistics: ACL 2023, pages 2119-2136.
2023.
[8] Liyi Chen, Zhi Li, Weidong He, Gong Cheng, Tong Xu, Nicholas Jing Yuan, and Enhong Chen. Entity summarization via exploiting description complementarity and salience. IEEE Transactions on Neural Networks and Learning Systems, 34(11):8297-830 2023.
10

---

[9] Liyi Chen, Zhi Li. Yijun Wang, Tong Xu, Zhefeng Wang, and Enhong Chen. Mmea: Entity alignment for multi-modal knowledge graph. In International Conference on Knowledge Science, Engineering and Management, pages 134-147. Springer, 2020.
[10] Liyi Chen, Zhi Li, Tong Xu, Han Wu, Zhefeng Wang. Nicholas Jing Yuan, and Enhong Chen. Multi-modal siamese network for entity alignment. In Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining, pages 118-126, 2022.
[11] Liyi Chen, Chuan Qin, Ying Sun, Xin Song, Tong Xu, Hengshu Zhu, and Hui Xiong. Collaboration-awar hybrid learning for knowledge development prediction. In Proceedings of the ACM on Web Conference 2024, pages 3976-3985. 2024.
[12] Liyi Chen, Ying Sun, Shengzhe Zhang. Yuyang Ye, Wei Wu, and Hui Xiong. Tackling uncertain correspondences for multi-modal entity alignment. In Proceedings of the 38th Conference on Neural Information Processing Systems, 2024.
[13] Xi Chen, Xinjiang Lu, Haoran Xin, Wenjun Peng, Haoyang Duan, Feihu Jiang, Jingbo Zhou, and Hui Xiong. A table-to-text framework with heterogeneous multidominance attention and self-evaluated multi-pass deliberation. In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 607-620, 2023.
[14] Xi Chen, Chuan Qin, Zhigaoyuan Wang. Yihang Cheng, Chao Wang, Hengshu Zhu, and Hui Xiong. Pre-dygae: Pre-training enhanced dynamic graph autoencoder for occupational skill demand forecasting. In Proceedings of the 33th International Joint Conference Artificial Intelligence, 2024.
[15] Zheng Gong and Ying Sun. Graph reasoning enhanced language models for text-to-sql. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 2447-2451, 2024.
[16] Yu Gu, Xiang Deng, and Yu Su. Don't generate, discriminate: A proposal for grounding language models to real-world environments. In Proceedings of the 61 Annual Meeting of the Association for Computational Linguisties (Volume 1: Long Papers). pages 1928-4949, 2023.
[17] Yu Gu, Sue Kase, Michelle Vanni, Brian Sadler, Percy Liang, Xifeng Yan, and Yu Su. Beyond iid: three levels of generalization for question answering knowledge bases. In Proceedings of the Web Conference 2021, pages 3477-3488, 2021.
[18) Bin Ji, Huijun Liu, Mingzhe Du, and KionKi Ng. Chain-of -fhthughh improves text generation with citations in large language models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 18345-18353, 2024.
[19] Jinhao Jiang, Kun Zhou, Zican Dong, Keming Ye, Wayne Xin Zhao, and Ji-Rong Wen. Structgpt: A general framework for large language model to reason over structured data. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 9237-9251, 2023.
[20] Jinhao Jiang, Kun Zhou, Xin Zhao, and Ji-Rong Wen. Unikgqa: Unified retrieval and rea- soning for solving multi-hop question answering over knowledge graph. In The International Conference Learning Representations, 2023.
[21] Byoungjip Kim, Youngsoo Jang, Lajanugen Logeswaran, Geon-Hyeong Kim, Yu Jin Kim, Honglak Lee, and Moontae Lee. Prospector: Improving Ilm agents with self-asking and trajectory ranking. 2023.
[22] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35:22199-22213. 2022.
[23] Tianle Li, Xueguang Ma, Alex Zhuang, Yu Gu, Yu Su, and Wenhu Chen. Few-shot in-context learning on knowledge base question answering. In Proceedings of the 61 Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 6966-6980, 2023.
[24] Xiaonan Li and Xipeng Qiu. Mot: Memory-of-thouge enables chatgpt to self-improve In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 6354-6374, 2023.
11

---

[25] Xiaoxi Li, Yujia Zhou, and Zhicheng Dou. Unigen: A unified generative framework for retrieval and question answering with large language models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 8688 8696, 2024.
[26] Zhenyu Li, Sunqi Fan, Yu Gu, Xiuxing Li, Zhichao Duan, Bowen Dong, Ning Liu, and Jianyong Wang. Flexkbqa: A flexible lmm-powered framework for few-shot knowledge base question answering. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 18608-18616, 2024.
[27] Linhao Luo, Yuan-Fang Li, Reza Haf, and Shirui Pan. Reasoning on graphs: Faithful and interpretable large language model reasoning. In The Twelfth International Conference on Learning Representations, 2024.
[28] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. Advances in Neural Information Processing Systems, 36, 2024.
[29] Ning Miao, Yee Whye Teh, and Tom Rainforth. Selfcheck: Using llms to zero-shot check their own step-by-step reasoning. In The Twelfth International Conference Learning Representa- tions, 2024.
[30] Xuefei Ning, Zinan Lin, Zixuan Zhou, Zifu Wang, Huazhong Yang, and Yu Wang. Skeleton- of-thought: Large language models can do parallel decoding. In The Twelfth International Conference on Learning Representations, 2024.
[31] Sanh. Distilbert, a distilled version of bert: Smaller, faster, cheaper and lighter. arXiv preprint arXiv: 1910.00 108, 2019.
[32) Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verhal reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
[33] Yiheng Shu and Zhiwei Yu. Distribution shifts are bottlenecks: Extensive evaluation for grounding language models to knowledge bases. In Proceedings of the 18th Conference of the European Chapter of the Association for Computational Linguisties: Student Research Workshop, pages 71-88, 2024.
[34] Yiheng Shu, Zhiwei Yu, Yuhan Li, Börje Karlsson, Tingting Ma, Yuzhong Qu, and Chin-Yew Lin. Tiara: Multi-grained retrieval for robust question answering over large knowledge base. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 3108-8121, 2022.
[35] Jiashuo Sun, Chengjin Xu, Lumingyuan Tang. Saizhuo Wang, Chen Lin, Yeyun Gong, Lionel Ni, Heung- Yeung Shum, and Jian Guo. Think-on-graph: Deep and responsible reasoning of large language model on knowledge graph. In The Twelfth International Conference on Learning Representations, 2024.
[36] Ying Sun, Hengshu Zhu, Lu Wang, Le Zhang, and Hui Xiong. Large-scale online job search behaviors reveal labor market shifts amid covid-19. Nature Cities, 1(2):150-163, 2024.
[37] Alon Talmor and Jonathan Berant. The web as knowledge-base for answering complex questions. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long Papers), pages 641-651, 2018
[38] Yanchao Tan, Hang Lv, Xinyi Huang. Jiawei Zhang, Shiping Wang, and Carl Yang. Musegraph: Graph-oriented instruction tuning of large language models for generic graph mining. arXiv preprint arXiv:2403. 04780, 2024.
[39] Jiabin Tang, Yuhao Yang, Wei Wei, Lei Shi, Lixin Su, Suqi Cheng, Dawei Yin, and Chao Huang. Graphgpt: Graph instruction tuning for large language models. arXiv preprint ar arXiv:2310.1302. 2023.
[40] Jianing Wang, Qiushi Sun, Nuo Chen, Xiang Li, and Ming Gao. Boosting language models reasoning with chain-of-knooleeee prompting. arXiv preprint arXiv:2306 06427, 2023.
[41] Keheng Wang, Feiyu Duan, Sirui Wang, Peiguang Li, Yunsen Xian, Chuantao Yin, Wenge Rong, and Zhang Xiong. Knowledge-driven cot: Exploring faithful reasoning llms for knowledge-intensing question answering, arXiv preprint
13259, 2023.
12

---

[42] Lei Wang, Yi Hu, Jiabang He, Xing Xu, Ning Liu, Hui Liu, and Heng Tao Shen. T-sciq: Teaching multimodal chain-of- thought reasoning via large language model signals for science question answering. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 19162-19170, 2024.
[43] Shuyao Wang, Yongduo Sui, Chao Wang, and Hui Xiong. Unleashing the power of knowledge graph for recommendation via invariant learning. In Proceedings of the ACM on Web Conference 2024, pages 3745-3755, 2024.
[44] Shuyao Wang. Yongduo Sui, Jiancan Wu, Zhi Zheng, and Hui Xiong. Dynamic sparse learning:
A novel paradigm for efficient recommendation. In Proceedings of the 17th ACM International Conference on Web Search and Data Mining, pages 740-749, 2024.
[45] Tianfu Wang. Qilin Fan, Chao Wang, Leilei Ding, Nicholas Jing Yuan, and Hui Xiong. Flagvne: A flexible and generalizable rl framework for network resource allocation. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence, 2024.
[46] Tianfu Wang. Li Shen, Qilin Fan, Tong Xu, Tongliang Liu, and Hui Xiong, Joint admission control and resource allocation of virtual network embedding via hierarchical deep reinforcement learning. IEEE Transactions on Services Computing, 17(03): 1(03):1001-1015, 2024.
[47] Xiaozhi Wang, Tianyu Gao, Zhaocheng Zhu, Zhengyan Zhang, Zhiyuan Liu, Juanzi Li, and Jian Tang. Kepler: unified model for knowledge embedding and pre-trained language representation. Transactions of the Association for Computational Linguistics, 9:176-194, 2021.
[48] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe V Le, Ed H Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In International Conference on Learning Representations, 2023.
[49] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. 2022.
Advances in neural information processing systems, 35:24824-2458
[50] Shiwei Wu, Joya Chen, Tong Xu, Liyi Chen, Lingfei Wu, Yao Hu, and Enhong Chen. Linking the characters: Video-oriented social graph generation via hiearchiial-cumullaiiee gen. In Proceedings of the 29th ACM International Conference on Multimedia, pages 4716-4724, 2021.
cumulative
[51] Wei Wu, Chao Wang, Dazhong Shen, Chuan Qin, Liyi Chen, and Hui Xiong. Afdgef: Adaptive feature de-correlation graph collaborative filtering for recommendations. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 1242-1252, 2024.
[52] Guanming Xiong, Junwei Bao, and Wen Zhao. Interactive- kbqa: Multi-turn interactions for knowledge base question answering with large language models. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers,
pages 10561-10582, 2024.
[53] Liang Yao, Chengsheng Mao, and Yuan Luo. Kg-bert: Bert for knowledge graph completion. arXiv preprint
03193, 2019.
[54] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Ad- vances in Neural Information Processing Systems, 36, 2024.
[55] Xi Ye, Semih Yavuz, Kazuma Hashimoto, Yingbo Zhou, and Caiming Xiong. Rng-kbqa: Generation augmented iterative ranking for knowledge base question answering. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics ( (Volume 1: Long Papers), pages 6032-6043, 2022.
[56] Wen-tau Yih, Matthew Richardson, Christopher Meek, Ming-Wei Chang, and Jina Suh. The value of semantic parse labeling for knowledge base question answering. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers). pages 201-206, 2016
[57] Donghan Yu, Sheng Zhang, Patrick Ng, Henghui Zhu, Alexander Hanbo Li, Jun Wang, Yiqun Hu, William Yang Wang. Zhiguo Wang, and Bing Xiang. Decaf: Joint decoding of answers and logical forms for question answering over knowledge bases. In The International Conference on Learning Representations, 2023.
13

---

[58] Lingxi Zhang, Jing Zhang, Yanling Wang, Shulin Cao, Xinmei Huang, Cuiping Li, Hong Chen, and Juanzi Li. Fe-kbqa: A fine-to-coarse composition framework for knowledge base question answering. In The 61st Annual Meeting Of The Association For Computational Linguistics, 2023.
[59] Shengzhe Zhang, Liyi Chen, Chao Wang, Shuangli Li, and Hui Xiong. Temporal graph contrastive learning for sequential recommendation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 9359-9367, 2024.
[60] Yuting Zhang, Ying Sun, Fuzhen Zhuang, Yongchun Zhu, Zhulin An, and Yongjun Xu. Triple dual learning for opinion- explainable recommendation, ACM Transactions on Information Systems, 42(3):1-27, 2023.
[61] Zhengyan Zhang, Xu Han, Zhiyuan Liu, Xin Jiang, Maosong Sun, and Qun Liu. Ernie: Enhanced language representation with informative entities. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 1441-1451, 2019.
[62] Lili Zhao, Qi Liu, Linan Yue, Wei Chen, Liyi Chen, Ruijun Sun, and Chao Song. Comi: Correct and mitigate shortcut learning behavior in deep neural networks. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 218-228, 2024.
[63] Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, et al. Least-to-most prompting enables complex reasoning in large language models. The International Conference Learning Representations, 2023.
14

---

Appendix
A
Prompts
Here, we provide all the prompts used in PoG. To facilitate the LLM output parsing, we require the LLM provide answers using specific data structures, such as lists and JSON, Besides, require the LLM not to output any other irrelevant information to the results. The specific in-context few-shot shown in code files.
A.1 Task Decomposition
Please break down the process answering the question into as few sub-objectives as possible based on aemantic analysis.
In-Content Few-Shot
Now you need to directly output sub-objectives of the following question in list format without other information or notes. Q: O
A.2 Path Exploration
A.2.1 Relation Exploration
Please provide few highly relevant relations possible the question and its aub-objectives from the following relations (separated by semicolons).
In-Content Few-Shot
Now you need directly output relations highly related the following question and its sub-objectives in list format without other information or notes. Q: O
Sub-Objectives: O
Topic Entity: O
Relations: O
A.2.2 Entity Exploration
Which entities following list (O) Triples) can used to answer the question? Please provide the minimum possible number of entities, and strictly adhering to the constraints mentioned in the question.
In-Content Pho-
Now you need to directly output the entities from [] in Triplets for the following question in list format without other information or notes.
Q: O
Triplets: O
A.3 Memory Updating
Based on provided information (which may have missing parts and require further retrieval) and your own knowledge, output the currently known information required to achieve the aub-objectives.
In-Content Few-Shot
Now you need to directly output the results of the following question in JSON format without other information or notes.
q: O
15

---

Sub-Objectives: +
Memory: 0
Knowledge Triplets: +
A.4 Evaluation
A.4.1 Answer Question
Please answer the question based on memory, related knowledge triplets and your knowledge.
Ca-Contezt Few-Shot
Now you need to directly output the results of the following question JSON format (must include "A" and "R") without other information or notes. If the triplets explicitly contain the answer to the question, prioritize the fact of the triplet over memory.
Q: O
Memory: 0 Knowledge Tripleta: O
A.4.2
Reflection
Based on the current set of entities to be retrieved and the known information including memory and triplets, is it necessary to add additional entities for answering the question?
In-Contewt Few-Shot
Now you need directly output the results of the following question in the JSON format (must include "Add" and "Reason") without other information or notes.
q: O
Entities set to be retrieved: 0
Memory: O
Knowledge Triplets: O
Please select the fewest necessary entities to be retrieved for answering the from Candidate Entities, based the known information (Memory), the for additional retrieval, and your own knowledge.
In-Contezt Few-Shot
you need directly output results following format without other information or notes.
Q: O
Reason: 0
Candidate Entities: 0
Memory: O
B Search SPARQL
To automatically process the KG data in PoG, we pre-define the SPARQL for Freebase queries, which be executed by filling in the entity's mid and relation.
B.1
Relation Search
PREFIX ns: <http://rdff. cereebase.com/nst. SELECT DISTINCT ?relation
WHERE {
ns:mid ?relation
16

---

PREFIX ns: <http://rdf. fttt:://rdf.rrebaaeeee com/ns/>
SELECT DISTINCT Prelation WHERE
?x Prelation ns:mid
B.2
Entity Search
PREFIX <http://rdf.. creebase.com//a.
SELECT ?tailEntity
WHERE { ns:mid ms:relation PtailEntity
PREFIX ns: <http://rdff attp::/rrfffrrebbas... www.baree.com//aaaaa com/ns/>
SELECT ?tailEntity
WHERE
?tailEntity ns:relation ns:mid
B.3 Entity Name Search
PREFIX ns: <http://rdf heat:://rd..freebaseee com/ns/>
SELECT DISTINCT ?tailEntity
WHERE (
Pentity ns:type.object.oo name ?tailEntity FILTER(Pentity ns: ns:mid)
} UNION {
Pentity <http://vuu.. w3. http://..rr//222/////o///aaaaae. ?tailEntity FILTER(rentity ns as:mid))
}
C Datasets
In this paper, we use three complex multi-hop KGQA datasets: WinQussonssssssinns [37], We- bQSP [56]. and GrailQA [I7]. The statistics of datasets are shown in Table 5 WebQSP contains questions from WebQuestions that are answerable by Freebase. tests L.D.. generalization on questions. Complex WebQuestions (CWQ) extends WebQSP and encompasses four types of complex questions: conjunction, composition, comparative, and superlative. GrailQA is a diverse KGQA dataset built on Freebase, and is designed to test three levels of generalization of models: I.I.D., compositional, and zero-shot.
Table 5: Statistics of KGQA datasets.
Dataset
Answer Format
Train
Test
Licence
Complex ComplexWeb WebQuestions WebQSP GrailQA
Entity
27,734
3,531
Entity/Number
3,098
1,639
CC Licence
Entity/Number
44,337
1,000
17

---

D Baseline Descriptions
The baselines we compare can be categorized into two groups: (1) LLM-only methods; (2) KG- augmented LLM methods, including fine-tuned and prompting methods.
LLM-Only Methods
Standard prompting (IO prompt) 66 verifies the ability of LLMs achieve better performance in task-agnostic, few-shot problems than traditional LMs.
Chain-of-Thougle prompting (CoT) 49 generates series of intermediate reasoning steps in prompts to help L.LMs perform better in several NI.P tasks.
ceff-Consistency (SC) 48 samples multiple, diverse reasoning paths through few-shot CoT,, and uses the generations to select the most consistent answer.
Finetuned KG-Augmented LLM Methods
UniKGQA 20 unifies the graph retrieval and reasoning process into a single model with
LLMs.
TIARA first uses BERT to retrieve set schema items, which are further used as input, together with the question, to T5 for plan generation. They also apply constrained decoding but only for grammaticality.
capitalizes relations in KGs to enhance entity representations and introduce additional supervision improve the selection of reasoning paths.
RE-KBQA 77
DeCAF (57 combines semantie parsing and LLMs reasoning to jointly generate answers, which also reach salient performance on KGQA tasks.
RoG [27 collaborates LLMs with KGs achieve trustworthy reasoning to leverage structural information.
RrG-KBQA 55 first uses BERT to rank set of enumerated candidate programs (up to limited complexity), and then uses edit the top programs into more complex programs.
58 proposes fine-to-coarse composition framework to avoid knowledge entan- glement and guarantee both generalization ability and logical interpretability.
FC-KBQA
Pangu considers leveraging the discriminative ability LLMSs. consists a symbolic agent with cooperative neural LLM.
FlexKBQA 26 is flexible KGQA framework with LLMs. It can utilize limited set of annotated data to build KGQA for different KGs and query languages.
GAIN 3 pays attention to the robustness of KGQA models. It proposes data augmentation method alleviate this problem and further evaluates the distribution shifts including from different aspects.
Prompting KG-Augmented LLM Methods
KB-BINDER 23 is developed challenge heterogeneity items from different KGs.
enables few-shot in-context learning over KGQA tasks.
KD-CoT 41 retrieves relevant knowledge from KGs generate faithful reasoning plans for LLMs.
StructGPT 119 defines the interface of KG data to implement knowledge access and filter- ing with finite quantity, and leverage the LLM to infer the answer or subsequent planning repeatedly.
Interactive KBQA [52] interacts with KGs directly and then generates logical forms. The interactions are under three designed universal APIs for KGs.
ToG 35 iteratively retrieves relevant triplets from KGs and employs the LLM to assess whether the reasoning paths in beam search are sufficient for answering the question and further retrieval of the next hop is necessary.
18

---

E Implementation Details
In our experiments, we use GPT-3.5 and GPT-4 to serve the underlying LLMs. We call them by the OpenAl official A We set the temperature parameter to 0.3, frequency penalty to 0, and presence penalty to The maximum token length for generation is 1024. In all experiments, the depth of exploration is set to 4 to avoid endless exploration. The experiments are conducted on server with two Intel(R) Xeo CPU E5-2682 y4 2.50GHz and 256 GB RAM memory.
Depth Sensitivity
66
64
Since LLMs are not entirely certain about when to stop,
Accuracy
62
we need to manually set the depth of KG exploration avoid endless exploration. To investigate the impact of exploration depth on PoG performance, we conduct exper- iments with depth settings ranging from 1 to 5 CWQ dataset. As shown in Figure 4 increasing the depth will improve the performance of PoG. Beyond depth of 4, the improvement becomes less noticeable. The increase in depth leads exponential growth in resource and time consumption. Considering the balance between efficiency and effectiivnesss, we the depth to 4.
60
56
54
52
Depth
Figure 4: The impact of exploration
depth the performance of PoG.
G Case Analysis
24%
In PoG, we design reflection mechanism to provide the opportunity for self-correction for exploring reasoning paths. In Figure [ calculate the proportion of cases with reverse occurrences among all questions in CWQ, and the results show that 24% of cases involve re- versing during the exploration process to achieve self-correction. This demonstrates that LLMs are indeed not always capable of making cor- rect judgments in KG exploration and that self-correction is necessary for -ug-augeeted LLMs.. Figure presents the proportion of correct answers obtained by PoG after self-correction on three datasets. Over- all, the self-correction in PoG appears have positively impacted the accuracy of KGQA, particularly for the WebQSP and CWQ datasets, where the proportion of correct answers reached 64% and 48% after the self-correction process. This analysis suggests that the reflection mechanism PoG has the potential enhance the reasoning capabilities KG-augmented LLM and improve the performance across various datasets by allowing for self-correction and exploration of alternative reasoning paths.
76%
Reverse
Not Reserse
Figure 5: The proportion of cases with reverse occur- rences among all data.
CWQ
WebQSP
GrailQA
Wrong 36%
Right 36%
Wrong 52%
Right 48%
Right 64%
Wrong %
Right
Wrong
Right
Wrong
Right
Wrong
Figure 6: The proportion of correct answers obtained by PoG after self-correction.
Besides, Figure 7 shows another typical case from the testing results on CWQ dataset. We compare the results PoG. ToG, and CoT in answering the question "What genre of music favored by Claude Debussy appears in the movie Suzanne Farrell: Elusive Muse?". PoG first adaptively identifies the
https:://pattooom.ppeet http:///wpppppooaoooo/a/aaaeeeee
19

---

Question: What genre music favored by Claude Debussy appears in the movie Suzanne Farrell: Elusive Muse?
Answer:
[hhe hallucinates.] First, Claude Debussy favored the genre music known Impressionism. Second, the movie Suzanne Farrell: Elusive Muse features music fron the Inpressionist genre.
CoT
Answer:
[The LLM hallucinates, inferring the answer with information of one condition.) Based on given knowledge triplets, the genre music favored by Claude Debussy that appears the movie Suzanne Farrell: Elusive Muse is Incidental music.
ToG
Paths:
Claude Debussy music.ortist.geg
Incidental music
French opera
Art song .....
Under the Brooklyn Bridge
Suzanne Farrell: Elusive Muse film.flm. genre Documentary film
FiLm.dtrector.ffi.
Deborah Dickson
Answer:
[Through adaptive breadth and sub-objectives, the answer was found. The genre of music favored by claude Debussy is Ballet, and the movie Suzanne Farrell: Elusive Muse falls under the genre Ballet.
Identify the music favored by Claude Debussy; 2. Determine the genre of music featured the movie Suzanne Farrell: Elusive Muse; Select the music genres that meet the two criteria.
Sub-Objectives:
PoG
The genre of music favored Claude Debussy is Ballet; 2. The movie Suzanne Farrell: Elusive Muse falls under the genre Ballet; Ballet is the final answer. Paths: Claude Debussy * music.artist.pe
Sub-Objective Status:
Incidental music French opera
Ballet
Suzanne Farrell: Elusive Muse
Film.fimm genre
Figure 7: A typical case to compare different methods answer the complex question. For the convenience of display, we only provide the sub-objective status and partial reasoning paths stored in memory. Topic entities, wrong answers, and correct answers are highlighted blue, red, and green.
most relevant relation imuusc.artist..eem. to the topic entity "Claude Debussy". Without constraining the breadth of reasoning paths, PoG considers multiple candidate entities as potentially relevant to the question. In the subsequent exploration of the topic entity "Suzanne Farrell: Elusive Muse", PoG adaptively chooses only "Ballet" as the relevant entity, as it records the known information of sub-objective #1 in memory. Through adaptive breadth and memorization of sub-objective status, PoG successfully and efficiently provides the correct answer. In contrast, ToG randomly explores paths when faced with multiple candidate entities, only finding one condition from sub-objective #1. Finally, ToG only remembers the genre of music favored by "Claude Debussy" but forgets the condition from sub-objective #2, answering "Incidental music". CoT directly hallucinates an irrelevant answer, "Impressionism". This case indicates the effectiveness of adaptive breadth and memorization of sub-objective status.
H Broader Impact & Limitation
In the current research landscape, PoG carries a significant broader impact, primarily reflected in its enhancement of complex reasoning capabilities for KG-augmented LLM. By innovatively integrating guidance, memory, and reflection mechanisms, PoG not only strengthens the model's flexibility and accuracy when facing complex queries but also enhances its ability self-correct erroneous reasoning paths. This self-correcting adaptive planning paradigm enables the model to backtrack and adjust reasoning directions when faced with invalid initial assumptions or impasses, resulting in an optimal solution search. Additionally, the broader impact of PoG is manifested in several other aspects: (1) Improving Efficiency and Effectiveness in Problem-Solving: By dynamically adjusting exploration breadth and employing self-correction mechanisms, PoG can more efficiently handle complex questions and provide more accurate answers, significantly enhancing the overall performance of KGQA systems. (2) Enhancing the Robustness and AnddAday Adaptability of LLMss: Through its memory mechanism, which records and tracks the completion status and reasoning paths of each sub-objective, PoG enables the LLM to more robustly deal with the uncertainty and complexity of questions, making more precise and reliable across wide range of applications. Innovation in the Field of Artificial Intelligence: PoG's integration of mota-cognitive capabilities into
(3) Fostering
20

---

reasoning and planning processes represents an innovative attempt that could further propel research and innovation broader AI technologies within the artificial intelligence field. (4) Improving User Experience and Expanding Application Domains: With PoG's reasoning capabilities, user experience greatly improved due to more accurate and quicker responses. Meanwhile, the domains where can be applied will also expand, particularly in environments that require handling complex queries and responses involving large volumes data.
There are still limitations in using PoG for addressing more complex problems. Some of the key limitations include: (1) Low Ceff-Coffidene: LLMs are still not entirely certain about what information is needed, how many steps are required to extract the information, when to perform dynamic updates, or if the current information is sufficient. evaluation of LLM's self ceff-confidence For example, this can be alleviated by training a small model specifically for this evaluation task to improve accuracy. (2) Efficiency: Answering complex questions requires multiple steps. In future work, we aim to design strategies to reduce steps and improve task execution efficiency in situations of high self-confidence. (3) non-Standardizze Query: For less standardized queries, semantic understanding might be insufficient due to limitations in the capabilities of the LLM itself, leading to decreased effectiveness. In future work, we will address this issue by employing SOTA query rewriting methods or interacting with the user to refine the query.
future work, we will focus on the
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Please see the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations in the Appendix
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
22

---

Justification:
Please see Section 3
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please Section 4.1 and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
23

---

Answer: [Yes]
Justification:
The datasets were released in public GitHub.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
ceciiooooolccyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /pipps.ccppullc//uuuii wwwiiccgguie//eeeeeeeeeis CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Please see Appendix E and Section 4.1
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Please see Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please Appendix
E
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https:: http::::///uriss../em
Answer:
[Yes]
Justification:
We conduct the research with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Please Appendix H
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
25

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
The datasets are from https://github.cc http://ttta.ccm////A/AAAAA////// main/ data and we present the licenses in Appendix
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwpsspipeaattteeeeee thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
26

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We will provide the documentation with assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "rlUp2UZ0VI", "reviewer": "Reviewer_kA7J", "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.", "questions": "Please refer to the questions raised in Weakness section.", "limitations": "Yes, the author has discussed the limitations in Appendix G, and leave them as future work.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "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.\n- 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.\n- 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. \n\n- 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. \n\n\n- Lack of critical evaluations: The paper is missing several important analyses, such as:\n  - The proportion of cases where the LLM needs to trigger reverse direction path visiting\n  - The frequency with which this revisiting leads to correct or incorrect answers\n  - How the number of breadth in each step affects the effectiveness of the proposed method\n  - Whether the length of hops from the query entity to the answer entity affects the number of revisiting and the method's effectiveness\n  - How consistent or diverse is the exploration path under the proposed method if experiment with multiple trails?\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable feedback on our paper. We appreciate your recognition of the novel approach, comprehensive context, and extensive experiments. In response to your concerns, we would like to address the following points:\n \n - **[W1: Missing prompt details & Implementation ambiguity]**:\n    Thank you for your valuable suggestions. Here, we provide two explicit examples to show how the KG is flattened in the prompts.\n\n    - Relation Exploration:\n        ```\n      Q: Name the president of the country whose main spoken language was Brahui in 1980?\n      Sub-objectives: ['Identify the countries where the main spoken language is Brahui', 'Find the president of each country', 'Determine the president from 1980']\n      Topic Entity: Brahui Language\n      Relations: language.human_language.main_country; language.human_language.language_family; language.human_language.iso_639_3_code; base.rosetta.languoid.parent; language.human_language.writing_system; base.rosetta.languoid.languoid_class; language.human_language.countries_spoken_in; kg.object_profile.prominent_type; base.rosetta.languoid.document; base.ontologies.ontology_instance.equivalent_instances; base.rosetta.languoid.local_name; language.human_language.region\n      Output: ['language.human_language.main_country', 'language.human_language.countries_spoken_in', 'base.rosetta.languoid.parent']\n        ```\n          \n    - Memory Update:\n        ```\n        Q: Find the person who said \"Taste cannot be controlled by law\", what did this person die from?\n        Sub-objectives: ['Search the person who said \"Taste cannot be controlled by law\"', 'Search the cause of death for that person']\n        Memory: {\n            \"1\": \"No information.\",\n            \"2\": \"No information.\"\n        }\n        Knowledge Triplets: Taste cannot be controlled by law. media_common.quotation.author [Thomas Jefferson]\n        Output: {\n            \"1\": \"Thomas Jefferson said 'Taste cannot be controlled by law'.\",\n            \"2\": \"It is not mentioned, and I also don't know.\"\n        }\n        \n        ```\n\n    We will add these details about prompts in our revised paper. Regarding the ambiguity in Figure 3 and 5, we will improve the description and presentation of figures. Additionally, to ensure reproducibility, we will release our full project including the code and prompts after this paper is published.\n\n\n - **[W2: LLM dependency]**: For your concern about the model dependency, we would like to emphasize that our method can be applicable to any LLM and we focus on how to utilize KGs to enhance LLMs by proposing a novel KG-augmented LLM paradigm which is model-agnostic.\n  Our goal is to enhance the reasoning capabilities of LLMs, rather than simply improving the performance of KGQA. In our experiments, we compared the KG-augmented LLM approaches with the LLM-only approaches using the same LLMs, validating the effectiveness of our method in enhancing the reasoning capabilities of LLMs.\n\n - **[W3: Lack of evaluations]**: Thank you very much for your valuable and constructive suggestions. Regarding your mentioned evaluations, we respond to each as follows:\n   - *The proportion of cases where the LLM needs to trigger reverse direction path visiting*: 24% on CWQ dataset.\n   - *The frequency with which this revisiting leads to correct or incorrect answers*: The results are presented in Appendix F (Figure 4), i.e., 48%, 64%, and 36% correct answers on three datasets.\n   - *How the number of breadth in each step affects the effectiveness of the proposed method*: We would like to clarify that the breadth in each step is adaptively chosen by the LLM, without any fixed setting. The detailed descriptions can be found in lines 144-146, 152-154, 162-164, and Appendix A.2.\n   - *Whether the length of hops from the query entity to the answer entity affects the number of revisiting and the method's effectiveness*: The results on CWQ dataset are presented as follows:\n\n        | Depth | 1    | 2    | 3    | 4    | 5    |\n        |-------|------|------|------|------|------|\n        | PoG   | 53.9 | 56.6 | 61.7 | 63.2 | 64.4 |\n    \n      This indicates that increasing the depth improves performance. Beyond a depth of 4, the improvement becomes less noticeable. Therefore, we set the depth to 4. \n\n   - *How consistent or diverse is the exploration path under the proposed method if experiment with multiple trails*: In applications of LLMs, the consistency of LLM's output from multiple runs depends on the temperature setting, which can be adjusted according to the requirements. If complete consistency is required, the temperature can be set to 0. In other cases, if diversity is needed, a higher temperature setting can be used to obtain more diverse results. As described in Appendix E, we set the temperature to 0.3 in our experiments. The results show that the changes in exploration paths are very small.\n  \n    In the revised paper, we will add supplemented evaluations on all datasets.\n\n - **[W4: Discussion on fine-tuned LLMs]**: Many thanks for your valuable advice. We would like to clarify that our proposed method is training-free, which is one of our advantages. From existing works, it is evident that training incurs high costs, and a training-free method offers a more cost-effective solution. Due to the short rebuttal period, we are currently unable to provide training results for the open-source LLM. In future work, we will explore whether constructing paths and memory in a post-training condition is more effective, and whether the current issue of LLMs' insufficient understanding of KG structures can be addressed through training.\n\n\nWe hope these responses effectively address your concerns. We will make revisions to further clarify these aspects in our revised paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7OayG0FmCl", "reviewer": "Reviewer_uH9F", "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.", "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?\n\n- How does PoG perform with larger and more complex KGs that were not part of the evaluation datasets?\n\n- How does PoG compare with other recent advancements in RAG methods?\n\n- 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.", "limitations": "discussed", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- novel reasoning framework with adaptive searching and reflective thinking. \n- 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.\n\n- The necessity for extensive prompt engineering and management of memory and reflection mechanisms could be resource-intensive.\n\n- While PoG performs well on the evaluated datasets, its generalization to other domains or types of KGs is not thoroughly explored.\n\n- Not compared with other RAG methods such as REPLUG[1]. \n\n- 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.\n\n\n\n\n[1] REPLUG: Retrieval-Augmented Black-Box Language Models", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your valuable feedback on our paper. We appreciate your recognition of the novel framework, great performance, and extensive experiments. In response to your concerns, we would like to address the following points:\n\n - **[W1: Complexity of implementation and optimization]**: Regarding your concern about complexity, we would like to clarify that we have implemented optimizations and improvements regarding efficiency such as adaptive exploration breadth and self-correction. As shown in Table 4, PoG presents ***a speedup of over 4 times*** on the CWQ dataset. We will continue to explore efficiency optimizations in the future. To ensure reproducibility, we will make the implementation of our method open-source.\n\n - **[W2: Resource consumption]**: We would like to clarify that our method is actually resource-efficient. Firstly, our approach is training-free, which inherently conserves resources. Typically, methods that incorporate KG's knowledge include training and training-free methods. Training methods need to fine-tune LLMs on nearly 400GB of Freebase data, which demands a substantial amount of resources. In contrast, in our method, the resource consumption for prompt engineering, and managing memory and reflection mechanisms, can be gauged from the input token counts listed in Table 4. Compared to the prompting baseline, even though PoG includes several components, PoG shows a reduction of approximately 4.6% in input token consumption.\n\n - **[W3 & Q2: Generalization]**: Regarding generalization, we would like to explain that Freebase is a suitable dataset for evaluating the generalization of the proposed method for the following reasons:\n   -  Among the most authoritative KGs and test sets used for this task, Freebase has been recognized as complex and large by previous works and includes 1.9 billion triples.\n   -  It covers a wide range of diverse domains such as movies, geography, business and sports. Correspondingly, datasets contain questions about different domains of knowledge, and we can retrieve different subgraphs from Freebase as smaller domain KGs.\n\n   To our knowledge, there currently exists no larger-scale, more complex KG dataset with high-quality question-answer pairs. However, we fully agree that the larger and more complex the KGs we use for evaluation, the more convincing our demonstration of the method's effectiveness will be. In the future, we will explore constructing a high-quality dataset that includes both KGs and corresponding QA pairs spanning diverse domains or types.\n  \n - **[W4 & Q3: Comparison with RAG methods]**: Thank you for your valuable suggestion. We would like to explain that the core idea of RAG involves constructing an index of chunks from documents, and then recalling content based on the similarity between the query and the index. This recalled content provides additional knowledge to the LLM. However, such RAG methods are not designed for understanding graph-structured information and cannot dynamically navigate the KG for KG-augmented LLMs. \nWe followed previous works like ToG and RoG, and did not compare with RAG methods.\nFor a better explanation, we will include a discussion in the revised paper addressing the distinctions between our method and RAG methods. Additionally, we will cite the REPLUG paper to provide further context.\n\n - **[W5: Outdated knowledge in KGs]**:\n  We fully agree that the update of KGs is an important topic, and there is a specialized research field dedicated to solving this problem [1]. \n  In this paper, our focus is on leveraging KGs to enhance LLM's reasoning, rather than on updating the KGs.\n\n   [1] KartGPS: Knowledge Base Update with Temporal Graph Pattern-based Semantic Rules. ICDE 2024.\n\n - **[Q1: Depth sensitivity]**: \n We have chosen the proper setting based on our preliminary experiments. Specifically, the results on CWQ dataset are presented as follows:\n    | Depth | 1    | 2    | 3    | 4    | 5    |\n    |-------|------|------|------|------|------|\n    | PoG   | 53.9 | 56.6 | 61.7 | 63.2 | 64.4 |\n\n    This indicates that increasing the depth improves performance. Beyond a depth of 4, the improvement becomes less noticeable. Therefore, we set the depth to 4.\n - **[Q4: Selection of usage]**:\n  Thank you for your valuable suggestion. The current best practice in real-world applications is query routing, which involves designing a router to determine whether to call an agent or a regular LLM. This practice has been successfully implemented in many popular projects like LlamaIndex and LangChain. These routers can also be applied to our PoG in case of real-world deployment. We will add this discussion in the revised paper.\n\nWe hope these responses effectively address your concerns. We will make revisions to further clarify these aspects in our revised paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CJtfrP0fgv", "reviewer": "Reviewer_QT9p", "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.", "questions": "1.How are the topic entities in the question obtained? \n2. When there are too many candidate entities, how does the model ensure the efficiency of reasoning? \n3. After selecting the wrong relation or entity, how does the model perform backtracking and reflection?", "limitations": "The paper could provide more details on the potential limitations and challenges of PoG.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tThe introduction of the self-correcting and adaptive planning mechanism enhances the reasoning capabilities of KG-augmented LLMs.\n2.\tThe experimental results support the effectiveness and efficiency of PoG. The comparison with state-of-the-art baselines demonstrates its superior performance.", "weaknesses": "1.\tAlthough 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.\n2.\tThere 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. \n3.\tThe paper could provide more details on the potential limitations and challenges of PoG, as well as possible strategies to overcome them.\n\n[1] Think-on-graph: Deep and responsible reasoning of large language model with knowledge graph\n[2] Temporal knowledge question answering via abstract reasoning induction\n[3] Reasoning on graphs: Faithful and interpretable large language model reasoning", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable feedback on our paper. We appreciate your recognition of the method design, well presentation, and superior performance. In response to your concerns, we would like to address the following points:\n\n - **[W1: Result analysis]**: Thank you for your constructive suggestion. \nHere, we provide a more detailed analysis of the results as follows:\n\n   - ToG explores reasoning paths with a fixed exploration breadth and cannot detect or correct the errors, showing the limitations in effect and efficiency. We specially design self-correction and adaptive planning mechanisms, which can effectively improve both performance and efficiency.\n   - ARI focuses on QA task for temporal KGs, whereas our work targets KG-augmented LLM task. ARI requires providing past answers and performing historical instance classification on historical information. In contrast, our method does not require historical answers or classification. By utilizing self-correction and adaptive breadth mechanisms to navigate the KG directly, we are able to achieve good performance and efficiency.\n   - RoG requires training and utilizes considerable computational resources and time for planning and reasoning optimization, while our method is training-free. Moreover, the three mechanisms we design (guidance, memory, and reflection) allow PoG's effect to surpass RoG.\n\n    We will add this analysis in the revised paper.\n - **[W2 & Q2: Excessive LLM calls]**: We would like to clarify that there is no need for hundreds of calls. For numerous candidate entities, we initially use a small model, Sentence Transformer, to calculate the similarity between entities and the question for recall. In contrast, the baseline ToG randomly selects candidates, which ignores semantic information and can easily result in incorrect recall.  It is noted that our method reduces LLM calls by at least 40.8\\%. \n\n - **[W3: More limitations and challenges]**: Many thanks for your valuable advice. Here, we provide more limitations/challenges and the possible solutions as follows:\n   - For less standardized queries, semantic understanding might be insufficient due to limitations in the capabilities of the LLM itself, leading to decreased effectiveness. We can address this issue by employing SOTA query rewriting methods or interacting with the user to refine the query.\n   - LLMs have limited capability in judging whether the available information is sufficient, potentially leading to incorrect answers when information is inadequate. This can be alleviated by training a small model specifically for this evaluation task to improve the accuracy of assessments.\n\n    We will add these contents in the revised paper.\n\n - **[Q1: Topic entity]**: In our datasets, topic entities are pre-annotated. Please refer to lines 105-107.\n  When such annotations are not provided, the typical approach in the KG domain is to first use named entity recognition and then entity linking methods to identify the topic entities.\n - **[Q3: Reflection & Backtracking]**: \n  For the details about reflection and backtracking, we introduce them as follows:\n      - Reflection: PoG utilizes the LLM to reflect on whether to correct the current exploration direction based on sub-objective states in $S$ and entities planned for the next iteration of retrieval in $E^D$ (defined in line 140) from memory. Specifically, the LLM assesses whether it is necessary to add entities beyond entities in $E^D$ on current reasoning paths. Please refer to the descriptions of the steps for the reflection in lines 196-200. \n      - Backtracking: PoG leverages the LLM to decide which entities in $E_{cand}$ (defined in lines 159-161 and 201) to backtrack to based on sub-objective states in $S$ and the reason for additional retrieval obtained from the reflection. Specifically, all candidate entities are provided to the LLM, and the LLM selects the specific entities to backtrack to. Please refer to the descriptions of the steps for the backtracking in lines 200-203. \n\n   The specific prompts for these two processes can be found in Appendix A.4.2. Additionally, in lines 308-313, we explained how backtracking and reflection are applied in the specific case shown in Figure 3.\n\n\nWe hope these responses effectively address your concerns. We will make revisions to further clarify these aspects in our revised paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xtXob96mjz", "reviewer": "Reviewer_vd15", "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.", "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.", "limitations": "Yes  the authors adequately addressed the limitations.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "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.\n\n2, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable feedback on our paper. We appreciate your recognition of the good presentation, excellent performance, and method design. In response to your concerns, we would like to address the following points:\n\n - **[W1 & Q1: Difference with GoT]**: We would like to emphasize that our method is very different from GoT. Although they all have the structure of a graph, the main difference between GoT and our proposed PoG lies in the ***source of information***: GoT primarily relies on the internal knowledge of the LLM, i.e., the information learned during the pre-training process, while our approach integrates KGs and can utilize additional domain knowledge. \nThis core difference results in GoT and other XoT techniques like CoT and ToT being suitable only for enhancing the problem-solving abilities of LLMs that have been covered in pre-training, such as mathematical and logical reasoning problems, but unable to address questions requiring new domain knowledge. To tackle this issue, we propose a novel PoG for KG-augmented LLMs, which has clear distinctions from GoT in the following specific aspects:\n\n   - The roles of the graphs. In our work, the KG is a pre-built external knowledge base, where each node represents an entity and the edges represent relationships between those entities, with the KG serving as ***input*** for the task. In GoT, the reasoning process of an LLM is modeled in graph form, where each node represents a thought and the edges depict relationships between thoughts, with the graph being the ***output***.\n\n   - The methods and objects for evaluation. Our evaluation involves using the LLM to determine whether the information in the current memory can answer the question, which is a ***global*** evaluation. In contrast, GoT scores specific thought nodes on the graph or ranks the nodes to assess whether the LLM thoughts represented by the nodes meet potential correctness criteria, which is a ***local*** evaluation. Besides, the evaluation in GoT is highly sensitive to prompts, requiring different constructions depending on the specific application.\n\n   - The contents of self-correction. We correct the agent's ***navigational process on the KG*** based on the information stored in memory and its own knowledge. The refine operation in GoT refers to looping over a specific thought node on the thought graph, i.e., correcting the ***content of specific thought***, not the navigation on the graph.\n\n   - The destinations of backtracking. We backtrack to ***entities*** in the KG that are related to the query. GoT backtracks to a ***specific thought node*** on the thought graph.\n\n\nWe hope these responses effectively address your concerns. We will make revisions to further clarify these aspects in our revised paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "404d3kDQ0o", "reviewer": "Reviewer_Gwnc", "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.", "questions": "1. In Table 4, is the number of input/output tokens the average of every single LLM call or for the whole QA?", "limitations": "See weakness above", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "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.\n2. The experimental results are also good, showing strong improvement over existing methods.\n3. 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.\n\n2. 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your valuable feedback on our paper. We appreciate your recognition of the method design, excellent performance, and generalization. In response to your concerns, we would like to address the following points:\n - **[W1: Query decomposition]**: Thank you for your constructive suggestion. We fully agree that refining query decomposition is crucial. For more complex queries, we can further improve our model by adapting SOTA query decomposition methods. Still, we would like to clarify that this research direction is orthogonal to our work.\nIn this paper, our self-correction focuses on the retrieval process, and our carefully designed decomposition mechanism has shown good results. In future work, we will consider self-correction for query decomposition in KG-augmented LLMs.\n\n - **[W2: Latency for real-time QA]**: Indeed, there is room for improvement in efficiency based on the results. We would like to clarify that the latency of our method is determined by both the algorithm and the engineering deployment. The current efficiency bottleneck lies in LLM calls and token consumption, which are general limitations in LLM applications. On the algorithmic aspect, where our focus lies, we have significantly reduced LLM calls and token consumption. On the engineering deployment side, there are existing technologies for prompt compression (e.g., LLMLingua) and inference acceleration (e.g., VLLM) that can enhance the system's speed and reduce latency. Recently, there have been increasing explorations of real-world applications based on LLM prompt engineering. We believe that in the future, there will definitely be more universal and efficient methods to improve the efficiency of LLM inference and multi-round interactions.\n - **[Q1: Token number]**: The number of input/output tokens is the average across all LLM calls for the whole QA. In lines 283-284, we explained that the data statistics pertain to answering a single question.\n\nWe hope these responses effectively address your concerns. We will make revisions to further clarify these aspects in our revised paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: In this work, the authors propose Plan-on-Graph (PoG), a self-correcting adaptive planning paradigm, which aim to help KG-augmented LLM systems to solve question answering task. Given a question, the pipeline first decomposes the question into a sequence of sub-objectives; then it repeats the loop of 1) reasoning path exploration in the KG; 2) updating useful information into a memory; and 3) reasoning to find an answer if with sufficient inforamtion or reflect for other reasoning paths otherwise. The authors tested their method on three KGQA tasks, they show PoG outperform a set of baseline systems on all tasks. 

This work has many merits, the all-positive scores from the five reviewers reflect this. All reviewers agree that the work is well motivated as self-correction and adaptive planning seem to enhance LLM system's reasoning capabilities; applying such idea and technique in KG path exploration for KGQA is novel; the presentation is clear, the paper is well structured, especially the related work section; the experiment design is good, experimental results support the claim well; the fact that the method is training-free makes it easy to plug-and-play. 

On the negative side, reviewers' main concerns were around the following aspects:
- Unclear how PoG connects/compares with prior works that also utilize graph-structured memory, such as Graph-of-Thought. 
- Unclear about efficiency, latency and cost limitation because PoG (as a inference-only method) may require huge amount of API calls when the question is compositional complex or the KG is huge. 
- Unclear about how PoG could be applied using more accessible models as backbone.
- Missing implementation details.

Reviewers agree that in general the authors did a good job addressing and clarifying the concerns, two reviewers have increased their score from 4 to 5. However, there are a few points remain less satisfied:
- The authors suggest that their proposed paradigm is model-agnostic, their goal is to enhance the reasoning capabilities of LLMs, rather than simply improving the performance of KGQA. This is only partially true, because there lacks of evidence the PoG could be directly applied to weaker/open-sourced LLM systems. What is the minimal requirements on the backbone end to make this working?
- In multiple steps of the pipeline, the LLM is asked to generate an output based on the provided information (e.g., retrieved from the KG) and `its own knowledge`. The fail of disentangling external knowledge and the LLM's embedded knowledge makes it less straightforward to understand the proposed method.
- It is only in the appendix that the authors say they are using in-context learning in all the prompts (Appendix A). Specifically, they use 5-shots learning on all datasets (Appendix E). They fail to provide any detail on how the five examples are being selected/retrieved, are they using the same in-context examples across datasets, across data points, or per data point? This makes it even more difficult to fully understand how the proposed method works. 
- Related to the above points, although the authors provide a good ablation study showing how each components could affect the overall system performance, they fail to discuss deeper how different design of each component could make a difference. Because PoG is a training-free method, specific prompt design, including the way to obtain the in-context examples could be rather important. This once again is related to how accessible the method is, because different backbone model may need very different prompt designing/engineering practice.

Given the all-positive scores, I tentatively recommend accept, but because:
- there are still some critical points unclear (see my review above); and
- all reviewers end up giving lukewarm scores,

I will not fight for acceptance if SAC suggests otherwise.
Decision: Accept (poster)