KARPA: A Training-free Method of Adapting Knowledge Graph as References for Large Language Model's Reasoning Path Aggregation
Knowledge Graph;Large Language Models;Chain-of-Thought;Reasoning
Yes
No ethics review needed.
- 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.
- 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.
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.
- 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.
Yes
No ethics review needed.
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.
The idea is reasonable. The paper clearly describes their model.
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.
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.
Yes
No ethics review needed.
- 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?
- The proposed method is well-motivated and reasonable under certain scenarios.
- The presented experimental results are strong.
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.
- 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.
Yes
No ethics review needed.
See the weakness.
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.
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.
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.
Yes
No ethics review needed.
- 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)
- ……
- 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.
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.
- 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.
We introduce KG Assisted Reasoning Path Aggregation (KARPA), a novel framework that enhances LLM-based KG reasoning by leveraging the global planning capabilities of LLMs, enabling efficient and accurate question answering without training process.
@inproceedings{
anonymous2024karpa,
title={{KARPA}: A Training-free Method of Adapting Knowledge Graph as References for Large Language Model's Reasoning Path Aggregation},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=Hw1tOjCWBZ},
note={under review}
}
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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Knowledge Graph Large Language Models Chain-of-Thought Reasoning
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/125eca3d3ff03e923f1fa2874fda404f1b59619b.pdf
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
KARPA: A Training-free Method of Adapting Knowledge Graph as References for Large Language Model's Reasoning Path Aggregation
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission