KARPA: A Training-free Method of Adapting Knowledge Graph as References for Large Language Model's Reasoning Path Aggregation

Authors: Siyuan Fang, Kaijing Ma, Tianyu Zheng, Xeron Du, Ningxuan Lu, Ge Zhang, Qingkun Tang
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords: Knowledge Graph, Large Language Models, Chain-of-Thought, Reasoning

Abstract:
Large language models (LLMs) demonstrate exceptional performance across a variety of tasks, yet they are often affected by hallucinations and the timeliness of knowledge. Leveraging knowledge graphs (KGs) as external knowledge sources has emerged as a viable solution, but existing methods for LLM-based knowledge graph question answering (KGQA) are often limited by step-by-step decision-making on KGs, restricting the global planning and reasoning capabilities of LLMs, or they require fine-tuning or pre-training on specific KGs. To address these challenges, we propose Knowledge graph Assisted Reasoning Path Aggregation (KARPA), a novel framework that harnesses the global planning abilities of LLMs for efficient and accurate KG reasoning on KGs. KARPA operates through a three-step process: pre-planning, retrieving, and reasoning. First, KARPA uses the LLM's global planning ability to pre-plan logically coherent relation paths based on the provided question and relevant relations within the KG. Next, in the retrieving phase, relation paths with high semantic similarity to the pre-planned paths are extracted as candidate paths using a semantic embedding model. Finally, these candidate paths are provided to the LLM for comprehensive reasoning. Unlike existing LLM-based KGQA methods, KARPA fully leverages the global planning and reasoning capabilities of LLMs without requiring stepwise traversal or additional training, and it is compatible with various LLM architectures. Extensive experimental results show that KARPA achieves state-of-the-art performance in KGQA tasks, delivering both high efficiency and accuracy.

Decision: reject
Reviewer scores: 3, 5, 5, 5, 5

Reviews and discussion:
<thread>
creation date:
1729704135665

thread_type:
official_review

<thread_object>
creator: reviewer_oyxy

<content>
summary:
The paper introduces a novel framework called KARPA designed to enhance the reasoning capabilities of LLMs in Knowledge Graph Question Answering (KGQA) tasks. The authors identify limitations in existing methods that either rely on step-by-step traversal of KGs, which restricts the global planning abilities of LLMs, or require fine-tuning on specific KGs, making them less adaptable.

KARPA addresses these challenges through a three-step process: 
(1) Pre-planning: The LLM generates initial relation paths based on the question and relevant KG relations, leveraging its inherent global reasoning and planning capabilities.
(2) Retrieving: A semantic embedding model is used to find candidate paths in the KG that are semantically similar to the LLM-generated paths, avoiding local optima and reducing interactions with the KG.
(3) Reasoning: The candidate paths and corresponding entities are provided back to the LLM for comprehensive reasoning to produce the final answer.

The framework operates in a training-free manner, making it adaptable to various LLM architectures without additional fine-tuning or pre-training. Experimental results demonstrate that KARPA achieves state-of-the-art performance on multiple KGQA benchmark datasets, delivering both high efficiency and accuracy.

strengths:
- By eliminating the need for fine-tuning or pre-training on specific KGs, KARPA offers a flexible and adaptable solution compatible with various LLMs.
- KARPA reduces the number of interactions between the LLM and the KG, enhancing efficiency without compromising accuracy. Moreover, the semantic embedding-based retrieval mitigates the risk of the LLM getting trapped in locally optimal solutions, leading to more effective exploration of KGs.
- KARPA fully leverages the LLM's global reasoning and planning abilities, enabling it to generate comprehensive relation paths beyond adjacent relations.

weaknesses:
- The experimental evaluation is focused on KGQA tasks; the framework's effectiveness on other knowledge-intensive tasks remains unaddressed.
- KARPA assumes access to comprehensive and accurate KGs, but the performance may degrade with incomplete or noisy KGs. Further, the effectiveness of KARPA may vary across different domains, especially if the KG lacks sufficient coverage of the required knowledge.
- The retrieval of candidate paths depends heavily on the quality of the semantic similarity measures used in the embedding model, which may affect the overall performance if the embeddings are not optimal.

questions:
- How does KARPA perform when the underlying KG is incomplete or contains inaccuracies? Have you tested the robustness of the framework in such scenarios?
- Have you evaluated the computational efficiency and scalability of KARPA on larger KGs or with more complex queries?
- Can KARPA be extended or adapted to other knowledge-intensive tasks beyond KGQA? If so, how would it perform?
- How does KARPA's performance compare with state-of-the-art models that utilize fine-tuning or pre-training on specific KGs?
- Do you consider ncorporating user feedback mechanisms to handle ambiguous queries or to refine the reasoning paths generated by the LLM. If so, how to make it. 

Missing References
- Knowledge Graph-Enhanced Large Language Models via Path Selection (ACL 2024, Findings)
- KnowledgeNavigator: Leveraging Large Language Models for Enhanced Reasoning over Knowledge Graph (Complex & Intelligent Systems, 2024)
- Paths-over-Graph: Knowledge Graph Enpowered Large Language Model Reasoning (2024)
- LightRAG: Simple and Fast Retrieval-Augmented Generation (2024)
- ……
</content>
</thread_object>

</thread>
<thread>
creation date:
1730109134946

thread_type:
official_review

<thread_object>
creator: reviewer_uom3

<content>
summary:
The paper addressed the task of KGQA and focused on the LLM-based method. The paper proposed a knowledge graph-assisted reasoning path aggregation approach, which contains three main steps: pre-planning, retrieving and reasoning. The proposed approach employs LLM and heuristic value-based relation path retrieval to extract potential relational paths for the questions. At last, the extracted candidate paths are provided to the LLM for reasoning. The results show the effectiveness of the proposed approach.

strengths:
1. The proposed heuristic value-based relation path retrieval method is interesting to compute the semantic similarity between paths with different lengths. 
2. The experimental comparisons with baselines on KGQA show the effectiveness.

weaknesses:
1) The Figure 1 is not very clear. Totally, there are two limitations for different previous methods: 1) local search strategies and 2) struggle with unseen KGs. I am not sure how the proposed method could resolve the aforementioned limitations. In specific, how about the performance of unseen KGs? Why the simple embedding-based semantic similarity, such as beam search deduce suboptimal answers?

2) The advantage of the proposed heuristic value-based relation path retrieval method is to compute the semantic similarity between paths with different lengths. Why do we need to extend relation paths with different lengths? The authors should exploit some experiments to prove it.

3) I wonder how about the performance when the given KG is not in the scope of LLM training sets. The used WebQSP and CWQ datasets, in my opinion, have been seen when pre-training LLMs.

questions:
See the weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730603556682

thread_type:
official_review

<thread_object>
creator: reviewer_kvb3

<content>
summary:
This paper proposes KARPA, a training-free KGQA method that utilizes LLMs to reason over KGs. KARPA uses a pre-planning step to extract candidate relation paths in a three-stage manner (initial planning, relation extraction, and re-planning) and ranks top candidates in the later reasoning step. The main difference between KARPA and previous LLM x KGQA methods (e.g. ToG and Pangu) is that KARPA is more efficient in LLM usage as it avoids the stepwise interaction between LLM and KG, and yet achieves superior performance. Regarding the experimental results, KARPA consistently outperforms baseline methods on WebQSP and CWQ datasets.

Despite these strengths, KARPA also exhibits several limitations. First, KARPA relies heavily on LLM's planning and reasoning abilities since it needs LLM to propose candidate relation paths or rank candidates in one single call, which may be harder to succeed when the candidate subgraph is complex and large. Second, in the pre-planning stage, KARPA uses a traditional sentence transformer to embed relations and calculate similarity, which may fail in multilingual scenarios (for example, the initial relations proposed by LLM is English, but the relation surface form in KG is Chinese). Overall, I may doubt the performance of KARPA on more complex KG (larger subgraphs, more relations) and multilingual scenarios.

strengths:
- The proposed method is well-motivated and reasonable under certain scenarios.
- The presented experimental results are strong.

weaknesses:
- KARPA relies heavily on LLM's planning and reasoning abilities since it needs LLM to propose candidate relation paths or rank candidates in one single call, which may be harder to succeed when the candidate subgraph is complex and large.
- In the pre-planning stage, KARPA uses a traditional sentence transformer to embed relations and calculate similarity, which may fail in multilingual scenarios (for example, the initial relations proposed by LLM is English, but the relation surface form in KG is Chinese). 
- Some experiment details are not clear enough. See questions.

questions:
- In lines 408-409, what does "For each LLM, we sample 300 KGs instances across the datasets to optimize computational cost" mean?
- It seems that KARPA only requires 3 LLM calls: initial planning, re-planning, and reasoning. Can you explain more about the results in Table 3?
- Instead of call frequency, token usage is a more effective measure for illustration. Do you have a token usage comparison between KARPA and ToG?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730609054604

thread_type:
official_review

<thread_object>
creator: reviewer_es96

<content>
summary:
The paper proposes Knowledge graph Assisted Reasoning Path Aggregation (KARPA), a novel framework that harnesses the global planning abilities of LLMs for efficient and accurate KG reasoning on KGs. KARPA operates through a three-step process: pre-planning, retrieving, and reasoning.

strengths:
The idea is reasonable. The paper clearly describes their model.

weaknesses:
1. The comparison in Table1 is unfair, the baseline all use 3-7B LLM but the proposed model uses GPT. The proposed model heavily depends on the output of the LLMs. Whether the authors have tried the effect of using 7B LLMs.

2. The claimed "training-free" contribution comes from the pre-trained LLMs and relies on the ability of LLMs. Therefore, KARPA lacks substantive technical contributions.

3. For a specific problem, what if the path given by LLM does not match the knowledge graph? In the face of diverse query problems, how can the output of LLM remain effective? In this sense, ToG may be more realistic and efficient.

questions:
1. What is the difference between KARPA and other prompt-based methods? It seems they are just involved in the change of input.

2. How to control the quality of LLM output, since it is the most important in this kind of methods. What if LLM outputs some meaningless paths or hallucinations?

3. How should KARPA work when KG is very dense (eg, too many paths)? It is hard to prove that the selection of Embedding models is better than the selection of LLM.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731121972108

thread_type:
official_review

<thread_object>
creator: reviewer_fyqd

<content>
summary:
The framework operates through a three-step process: pre-planning, retrieving, and reasoning. KARPA is designed to address the limitations of existing LLM-based KGQA methods by fully utilizing the global planning and reasoning capabilities of LLMs without requiring stepwise traversal or additional training. The paper claims that KARPA achieves state-of-the-art performance in KGQA tasks, offering both high efficiency and accuracy.

strengths:
- The three-step process of pre-planning, retrieving, and reasoning is a easy-to-fellow approach to leverage external knowledge sources for enhancing LLMs.

- KARPA's training-free nature is an advantage, as it allows for easy integration with various LLM architectures without the need for fine-tuning or pre-training on specific KGs, which can be time-consuming and resource-intensive.

weaknesses:
- To my knowledge, The proposed method lacks novelty; employing an agent-based approach for KGQA tasks is not particularly innovative.  For instance, RoG recently introduced a planning-retrieval-reasoning framework for KGQA, and  this manuscript is the expansion of the planning phase in RoG's framework into two processes: pre-planning and re-planning. 

- Secondly, the authors claim in their motivation that "Pre-training or fine-tuning the LLM for KGQA, which is prone to hallucinations and struggles to adapt to unseen KGs without an extensive training process." I believe this is a point worth discussing. Taking RoG as an example again, it did employ instruction-tuning for the LLM, but I think such instruction-tuning for LLMs possesses a certain ability to learn from few samples, meaning that generalization can be reflected in the mitigation of hallucinations. Of course, I also feel that this is worth experimenting with and discussing further.

- Considering the forward-looking nature of RoG in initially proposing the planning-retrieval-reasoning approach, it is somewhat unfair that this manuscript did not use the same large model as a backbone in its comparison with RoG (Table 1).

- There is a noticeable absence of robust agent-like methods, such as Interactive-KBQA, which directly perform inference over KGs with LLMs.

questions:
- Could the authors elaborate on the choice of semantic embedding models and how different models affect the performance of KARPA?


- How does KARPA perform on the strict EM (Etract Match) metric, as many baselines have used this metric for experiments.
</content>
</thread_object>

</thread>


Metareview: