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

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. KARPA operates in three steps: pre-planning relation paths using the LLM’s global planning capabilities, matching semantically relevant paths via an embedding model, and reasoning over these paths to generate answers. Unlike existing KGQA methods, KARPA avoids stepwise traversal, requires no additional training, and is adaptable to various LLM architectures. Extensive experimental results show that KARPA achieves state-of-the-art performance in KGQA tasks, delivering both high efficiency and accuracy.

## introduction in recent years, large language models (llms) @xcite @xcite have revolutionized natural language processing, demonstrating impressive performance in areas such as information extraction @xcite , summarization @xcite , and question answering @xcite . however, despite these advancements, llms face notable challenges, particularly in maintaining upto-date knowledge, domain-specific knowledge @xcite , and dealing with hallucinations @xcite where llms produce incorrect or nonsensical outputs. knowledge graphs (kgs) enhance the reasoning capabilities of llms by providing structured, reliable external knowledge @xcite . existing approaches to integrating llms with kgs fall into two categories: (1) direct interaction between llms and kgs, where the llm explores the kg step-by-step @xcite , often relying on local search strategies like beam search. these methods can produce suboptimal answers by overlooking the llm's global planning and reasoning potential. additionally, they require numerous interactions between llms and kgs, as shown in figure 1(b) . to address these limitations, we propose knowledge graph assisted reasoning path aggregation (karpa), an innovative framework that leverages the global planning capabilities of llms alongside semantic embedding models for efficient and accurate kg reasoning. our approach consists of three key steps: pre-planning, matching, and reasoning, as shown in figure 2 . in the pre-planning phase, karpa enables the llm to generate initial relation paths for the provided question using llm's inherent reasoning and planning capabilities. with these inital relation paths, karpa employs a semantic embedding model @xcite to identify candidate relations that are semantically similar to the relations within the initial paths. the llm can then create coherent relation paths that logically connect the topic entity karpa offers several key advantages over existing llm-based kgqa methods: (1) karpa fully leverages the global planning and reasoning capabilities of llms to generate logically coherent paths, which aligns better with human-like reasoning processes. unlike methods limited to adjacent relations or requiring iterative traversal within the kg, karpa selects from all potential relations within the kg, significantly reducing interactions between llms and kgs. (2) our embedding-based matching strategy avoids the locally optimal solution that arises from the stepwise interactions between llms and kgs, ensuring more effective exploration of the kgs. (3) karpa is trainingfree, making it adaptable to various llms while enhancing reasoning capabilities with techniques such as chain-of-thought (cot) @xcite . our contributions can be summarized as follows: prompt-based reasoning with llms. llms such as llama @xcite , qwen @xcite , and gpt-4 @xcite have advanced reasoning by leveraging extensive internal knowledge. various prompt-based methods further enhance these capabilities. for instance, chain-of-thought (cot) @xcite improves reasoning by decomposing complex tasks into manageable steps, excelling in domains like mathematical reasoning @xcite and logical inference @xcite . variants such as auto-cot @xcite , zero-shot-cot @xcite , and complex-cot @xcite further optimize this approach. frameworks like tree of thoughts (tot) @xcite and graph of thoughts (got) @xcite have expanded the scope of llm reasoning. lately, openai o1 series models represent a significant advancement in llm reasoning. these methods underscore the role of tailored prompts in maximizing llm reasoning potential. llm-based kgqa. integrating kgs with llms enhances reasoning and mitigates hallucinations. unlike methods such as cot that rely solely on the internal knowledge of llms, incorporating kgs provides access to structured external knowledge @xcite . approaches like think-on-graph (tog) @xcite , interactive-kbqa @xcite and structgpt @xcite enable stepwise interactions between llms and kgs. methods such as reasoning on graphs (rog) @xcite , chain of knowledge @xcite and other techniques @xcite @xcite utilize pre-trained or fine-tuned llms to generate retrieval information for kgqa. furthermore, methods like unikgqa @xcite and kg-cot @xcite require training specific models for kg information retrieval, further complicating their implementation. ## preliminary knowledge graphs (kgs). kgs represent structured information as @xmath0, r), where e is the set of entities and r denotes the set of relations. each relation @xmath1, e j ), with e i , e @xmath2. ## approach in this section, we present karpa, a framework that leverages the strengths of llms and embedding models to enhance kgqa. our approach is composed of three key steps: pre-planning, matching, and reasoning, as illustrated in figure 2 . ## experiments in this section, we detail the experimental setup, present our main results, and conduct further analysis to evaluate the performance of karpa. ## conclusion in this paper, we propose karpa, a novel framework designed to enhance llm-based kgqa by utilizing the global planning and reasoning capabilities of llms. karpa addresses key limitations of existing methods, achieving superior accuracy and efficiency through its pre-planning, matching and reasoning processes. our experiments show that karpa consistently outperforms state-of-the-art methods across multiple datasets. its training-free design allows seamless integration with various llms, making it broadly applicable to different kgqa tasks. by optimizing llm-kg interactions, karpa enhances reasoning efficiency and effectiveness, highlighting its potential as a robust approach for future rag systems.