KG-CoT: Chain-of-Thought Prompting of Large Language Models over Knowledge Graphs for Knowledge-Aware Question Answering

1 Introduction

Recently, large language models (LLMs) [OpenAI, 2023] have achieved remarkable results in various downstream natural language understanding and generating tasks with elaborate natural language prompts [Wei et al., 2022]. Despite their significant ability to generate fluent and coherent natural language responses, LLMs suffer from hallucination and factual errors when performing knowledge-intensive tasks [Ji et al., 2023]. The essential reason for these problems lies in the black-box nature of parametric knowledge, which makes it difficult to locate and update knowledge facts stored in the parameters [Zhu et al., 2020; Cao et al., 2021]. This results in two main challenges that hinder the adaptation of LLMs in knowledge-intensive tasks.

∗Corresponding author

(a) Lack of Responsible Factual Knowledge

LLM + CoT Prompt

Q: Whence is the artist nominated for awards for "Live from Paris"? A: Let's think step by step.

As of my last knowledge update in January 2022, I don't have specific information about an artist nominated for awards …

(b) Cognition Gap with Knowledge Retrievers

LLM + Knowledge Retriever

• Q: Whence is the artist nominated for awards for "Live from Paris"?

K: (Sakira, music.artist.album, Live from Paris)

(Shakira, music.artist.album, Las de la Intuicion)

(Shakira, people.person.places_lived, Los Angeles) …

Los Angeles

(c) KG-CoT (Ours)

LLM + Chain-of-Thought Prompting over Knowledge Graphs

Q: Whence is the artist nominated for awards for "Live from Paris"? K: Path1: Live from Paris →music.artist.album_reversed→Sakira →music.artist.origin→Colombia …

Based on the reasoning paths, we can infer that Shakira, the artist behind the album "Live from Paris", hails from Colombia.

Figure 1: (a) LLMs may struggle to provide responsible answer based on the static parametric knowledge. (b) The high relevance of fragmented knowledge facts doesn't necessarily imply the usefulness for LLM reasoning. (c) Our proposed KG-CoT enables LLMs to think with KGs for knowledge-aware reasoning.

Challenge 1: Lack of Responsible Factual Knowledge. Since it is challenging to revise and expand the parametric knowledge, LLMs are hard to access the most recent updates in various domains [Wang et al., 2023d]. Therefore, when encountering questions that require up-to-date or domainspecific knowledge, LLMs may struggle to provide responsible answers based on the static parametric knowledge [Chen et al., 2023]. Although elaborate prompts [Wei et al., 2022; Yao et al., 2023] can be used to decompose complex questions into multiple steps to enhance the logical reasoning capability of LLMs, it is difficult to fully compensate for the lack of explicit factual knowledge. As a result, the benefit of elaborate prompting diminishes [Wang et al., 2023a] especially in tasks where accurate and deep understanding of subject entity is crucial for generating correct response.

Challenge 2: Cognition Gap with Knowledge Retrievers.

Augmenting LLMs with external knowledge graphs is a natural and promising solution for addressing the lack of knowledge described above [Bollacker et al., 2007]. KGs are structured, explicit, and responsible, which can provide reliable knowledge subgraphs to explicitly enhance the knowledgeaware reasoning process of LLMs [Shi et al., 2021]. However, the cognition gap in understanding and reasoning between LLMs and knowledge retrievers significantly limits the performance of LLM+KG paradigm. Knowledge retrievers prioritize knowledge facts commonly based on representation similarity [Li et al., 2023], but the relevance in this context does not necessarily guarantee usefulness for specific reasoning tasks of LLMs [Sun et al., 2023]. This cognition gap results in LLMs being compelled to continuously evaluate the usefulness of fragmented knowledge facts and recurrently invoke knowledge retrievers to provide adequate knowledge for reasoning [Sun et al., 2023]. This leads to a significant increase in the complexity and cost of the LLM+KG paradigm.

To address these challenges, we propose a Chain-ofThought prompting over Knowledge Graphs (KG-CoT), a novel knowledge-augmented framework that utilizes a stepby-step graph reasoning model to augment LLMs with responsible chains of knowledge in a plug-and-play manner. To address the lack of responsible factual knowledge (Challenge 1), we propose a step-by-step graph reasoning model to reason over KGs. Starting from the question entity, the stepby-step graph reasoning model calculates scores for relations in a KG and constructs the transition matrix for each reasoning step. By utilizing the transition matrix, the graph reasoning model can traverse various paths in the KG, hopping among relations and exploring entities with high confidence for problem solving. To address the cognition gap between LLMs and knowledge retrievers (Challenge 2), we develop a reasoning path generation method. Starting from the question entity, it retraces the step-by-step reasoning process and generates explicit reasoning paths along the transition matrix. In this way, the graph reasoning model can plug into LLMs and enable joint reasoning of LLMs over KGs.

Our main contributions are as follows:

• Large + Small: We propose a knowledge-augmentation paradigm for LLMs that combines large-scale LLMs with small-scale step-by-step graph reasoning models to augment LLMs with KGs without fine-tuning LLMs.
• Responsibility: We propose using a graph reasoning model over KGs as a enhancement of CoT prompting to generate responsible chains of knowledge for improving knowledge-aware reasoning capability of LLMs.
• Efficiency: Our proposed KG-CoT prompting significantly improves the performance of LLMs on several knowledge-intensive benchmarks without fine-tuning LLMs, and outperforms prior retrieval-augmented and knowledge base question answering baselines.
• Adaptability and Generality: Our proposed KG-CoT can be generalized to various LLM backbones (e.g., closed-source or open-source LLMs) with reduced API calls and costs in a lightweight plug-and-play manner.

2 RelatedWork

In this section, we introduce related LLM-based QA systems from two categories based on their utilization of knowledge.

2.1 LLM+ Parametric Knowledge

As the model scale increases, the emergent ability enables LLMs to comprehend natural language instructions and activate the parametric knowledge [Petroni et al., 2019] stored in their parameters for downstream NLP tasks.

Recently, Wei et al. first introduces the concept of chainof-thought prompting (CoT), in which a series of intermediate reasoning steps is generated to solve complex problems through manually constructed prompts. Kojima et al. demonstrates the ability of LLMs to generate CoT, even in zero-shot scenarios. Consequently, Zhang et al., Shao et al., and Liang et al. leverage manually constructed CoT examples to automatically generate high-quality CoT demonstrations. Huang et al. fine-tunes LLMs based on their self-generated CoT examples and demonstrates the self-improvement capability of LLMs.

However, the difficulty of modifying and updating the parametric knowledge leads to LLMs utilizing outdated or incorrect implicit parametric knowledge for response generation, which strongly limits the validity and interpretability of black-box LLMs. In this case, a natural and promising solution is to augment LLMs with external world knowledge.

2.2 LLM+ External Knowledge

Retrieval-augmented generation (RAG) is a natural way to augment LLMs with external knowledge [Lewis et al., 2020]. This approach aims to retrieve relevant knowledge from massive knowledge bases (KBs) and directly augment LLMs with external world knowledge. Paranjape et al. enhances the ability of knowledge retriever to increase the probability of relevant passages being ranked among the top-10 most relevant. In addition, Ma et al. retrieves knowledge triplets over knowledge graphs (KGs) for question answering. Zhao et al. converts KGs to text descriptions to augment LMs. KGs are structured, explicit, and interpretable, since several paths from the question entity to the answer entity can be identified.

However, recent works generally utilized representationbased multi-model pre-training for augmenting LLMs with KGs [Zhao et al., 2024; Ye et al., 2023]. In addition to limiting the adaptability to closed-source LLMs, these methods ignore the elaborate knowledge structure and explicit reasoning paths, which can serve as explicit clues for joint reasoning with LLMs. Although Wang et al. has demonstrated that LLMs have preliminary graph reasoning abilities, the overreliance on LLMs results in limited adaptability when dealing with large-scale KGs and complex multi-hop tasks.

To address these challenges, we propose the KG-CoT prompting, which includes a lightweight joint reasoning model to alleviate a portion of the reasoning burden of LLMs and perform joint reasoning over KGs. The graph reasoning model can generate explicit reasoning paths relevant to the questions, enabling LLMs to "think with KGs" for answer generation.

3 KG-CoT

KG-CoT augments LLMs with relevant knowledge by applying a small graph reasoning model to reason over KGs and generate reasoning paths with high confidence in LLM reasoning. First, we propose a graph reasoning model to perform step-by-step reasoning over the KGs and find candidate entities with high confidence. Then, we introduce the reasoning path generation method to generate the reasoning paths based on the step-by-step reasoning process. Finally, we leverage the reasoning paths to prompt LLMs for answer generation.

3.1 Step-by-Step Graph ReasoningModel

Prior semantic parsing based models [Li and Ji, 2022] have shown that the natural language question can be converted into its logical form, which is called a query graph. These findings suggest that complex questions can be decomposed into multiple meta-questions over the KGs, which is similar to chain-of-thought prompting [Wei et al., 2022]. Inspired by this, we propose a graph reasoning model to imitate the question decomposition and step-by-step reasoning over KGs.

Initialization. Let G denote the KG, n denote the number of entities in the entity set, and m denote the number of relation in the relation set. We first initialize an entity state e0 ∈ [0, 1]n , which is a one-hot vector that indicates whether the corresponding entity is mentioned in the context of questions. For example, if only the i th entity is mentioned in the question, the e0i ∈ e0 is initialized to 1 and others are set to 0. Moreover, we initialize a triplet matrix M ∈ [0, 1]n×n , which is a one-hot matrix that indicates the relation index Mij = k if it exists between the entity i < n and entity j < n.

Relation Score Calculation. Inspired by [Shi et al., 2021], we separate the graph reasoning process into T steps. At step t < T , we calculate scores for all relations in the KGs Rt ∈ [0, 1]m. The score of each relation rt i ∈ Rt indicates the probability of a "hop" occurring for the current entity based on this relation. The calculation of relation score Rt is calculated as follows:

where qt is the question representation at step t. We consider the question representation at different steps to focus on different parts of the question context. In this way, we can implicitly decompose the question and and force the graph reasoning model to focus on different relations at different steps. At step t, the question representation qt can be formulated as follows:

where q is the question embedding and (h1, . . . , h|q|) is a sequence of hidden states associated with the question.f t is used to project the question embedding q to the attention query Qt at step t. We calculate the attention weights αt and calculate the question representation at step t by taking the weighted sum of the hidden states.

Step-by-Step Reasoning. Based on the relation score Rt , we first define a transition matrix Wt ∈ [0, 1]n×n , which is used to describe the transitions from the current entity states et-1 to the next entity states et . We leverage the triplet matrix M and relation score Rt to construct the transition matrix Wt :

where k is the index of the relation between entities i and j, and Rtk is the score of relation k. Finally, we can utilize the transition matrix to perform step-by-step reasoning over the KG. The step-by-step reasoning process can be formulated as follows:

The current entities et-1 "hop" along the relations within their 1-hop neighborhood and transmit to the next entity states et based on the relation score Rt .

After T steps reasoning, we utilize the question embedding q to determine the weight distribution β for each step, and calculate the final entity scores e by taking the weighted sum of the entity scores at each step.

Training. Given the one-hot vector a ∈ [0, 1]n of the golden answer, which indicates whether the corresponding entity is the answer entity. We use the L2 Euclidean distance between e and a to optimize the step-by-step graph reasoning model:

3.2 Reasoning Path GenerationMethod

During inference, once we obtain the top-k entities EK ⊆ E through the graph reasoning model, we utilize the transition matrices W1 , W2 ... , WT to generate the reasoning paths.

Initialization. During the generation of reasoning paths, we maintain two lists Lrp and Lmid, which are used to store the candidate reasoning paths and the intermediate paths.

Extraction. Starting from the question entity Eq, we first extract the corresponding row w1 i0 , w1 i1 , . . . , w1 i(n-1) ∈ W1 , w1 ij > 0, which indicates the relation score of transitioning from the question entity at step t = 0 to the entities at step t = 1. In this way, we can extract a set of 1-hop paths P1 :

where the "key" is the extracted path and the "value" is the score of relation within it. Relij denotes the relation between the entities i and j. For each path p1ij , we first append it to the Lrp. If the object entity Ej is contained in the top-k answer entities EK , we then append the extracted path to the Lrp.

Then, we start from the object entities Ej of the 1-hop paths in the Lmid and use the W2 to extract 2-hop paths P2 :

Algorithm 1 Inference process of LLM + KG-CoT

Input: Input question q, retrieved knowledge subgraph G, and a large language model LLM.

Initialize Entity score e0 ← extract question entity Eq from G, triplet matrixM←extract triplets fromG.

Output: Output answer y

• 1: for t = 1, ..., T do
• 2: Compute the question representation qt using (2)-(5).
• 3: Compute the relation score Rt using (1).
• 4: Compute transition matrixWt using (6).
• 5: Entity score et ← step-by-step reasoning using (7).
• 6: end for
• 7: Compute final scores e using (8)-(9) and select top-k entities EK
• 8: Initialize Lmid ←p0 = ¡"Eq", [0]¿.
• 9: for t = 1, ..., T do
• 10: Extract t-hop paths Pt usingWt and paths in Lmid.
• 11: Update intermediate path list Lmid with Ptqj
• 12: if Object entity Ej ∈ EK then
• 13: Update reasoning path list Lrp with Ptqj .
• 14: end if
• 15: end for
• 16: Select N paths for each top-k entity EK from Lrp.
• 17: Serialize reasoning paths to textual sentence s
• 18: Output answer y = Call(LLM, q, s).
• 19: return Output answer y

and update the Lrp and Lmid.

By repeating the above algorithm for T steps, we can generate candidate reasoning paths from the question entities to the top-k entities.

Ranking. Each answer entity may correspond to multiple candidate paths in Lrp, and the number of hops for different paths varies. Therefore, we take the average of the scores of relations in each path as the final path score.

3.3 Joint Reasoning

For the top K candidate entity with highest confidence, we extract the path with the highest path score for each candidate entity. Thus, for each question, we utilize the stepby-step graph reasoning model (Section 3.1) and a reasoning path generation method (Section 3.2) to generate K reasoning paths with various numbers of hops and answer entities.

To maintain the chain structure, we utilize "arrows" to connect the entities and relations to construct the KG-CoT. For example, a 2-hop path p2ik :

is serialized to a textual sentence, which is formulated as:

We serialize the K reasoning paths and concatenate them with the question context as the final input sequence. We utilize elaborate instructions to prompt LLMs to leverage these reasoning paths for answer generation.

4 Experiments

4.1 Datasets

We evaluate KG-CoT based on 4 challenging knowledgeintensive question answering benchmarks that heavily rely on knowledge-aware reasoning with external world knowledge.

WebQSP. WebQSP is a knowledge-intensive multi-hop question answering benchmark. It contains 4,037 questions that are all 1-hop or 2-hop questions based on the Freebase. Based on previous works, we retrieve knowledge triplets within 2-hop neighborhoods of the question entities and produce a knowledge subgraph with 1,886,684 entities, 1,144 relations, and 5,780,246 knowledge triplets.

CompWebQ. CompWebQ is a multi-hop question answering benchmark. It contains 34,672 questions with many hops and constraints, which makes it challenging for LLMs to process. We utilize the retrieved knowledge subgraph of [Shi et al., 2021] and utilize the original data splits for evaluation.

SimpleQuestions. SimpleQuestions is a single-hop question answering benchmark. Questions are generated based on information from Freebase, and ultimately, 108,442 questions that heavily rely on factual knowledge were generated in this study. We randomly select 1,000 questions and retrieved 1-hop neighborhood of the question entity for evaluation.

WebQuestions. WebQuestions is a challenging opendomain question answering benchmark. It contains 5,810 questions, with Freebase as the knowledge base. For each question, we retrieve the 2-hop neighborhood of the question entity and utilize the original data splits for evaluation.

4.2 Baselines

We compare with strong baselines, such as standard prompting baselines, state-of-the-art retrieval-augmented (RA) baselines and knowledge base question answering (KBQA) baselines, based on the above benchmark datasets.

Prompting Baselines. We compared with original IO prompts (IO prompts), chain-of-thought prompts (CoT prompts) and Self-Consistency (SC)

Retrieval-Augmented Baselines. We select previous SOTA of each benchmark, including direct fact retrieval DiFaR [Baek et al., 2023], case-based reasoning CBR [Das et al., 2021], and fusion in encoder FiE [Kedia et al., 2022].

Knowledge Base Question Answering Baselines. We compared with previous state-of-the-art knowledge base question answering model on each benchmark, including UniKGQA [Jiang et al., 2023] and RNG [Ye et al., 2022].

LLM+KG Baseline. We also compare with recent KGaugmented baseline ToG [Das et al., 2021]. Different from our motivation, it instructs LLM itself to perform retrieval, pruning and answer prediction.

4.3 Implementation Setting

We train the step-by-step graph reasoning model with RAdam optimizer at a learning rate of 1e-3 for 50 epochs. For the LLM, we leverage the OpenAI API to call ChatGPT and GPT-4 for evaluation. We select the "gpt-3.5-turbo" and "gpt4" as our LLM backbones and utilize the default setting of the OpenAI API. For each question, we generate 1 KG-CoT for each top-10 candidate entity (e.g., Hit@10 Path1) and establish instructions to prompt the LLMs to directly generate answer entity for evaluation. Our code and data is available at https://github.com/HUSTNLP-codes/KG-CoT.

4.4 Main Results

As shown in Table 1, our proposed KG-CoT achieved stateof-the-art performance on 3 knowledge-intensive question answering benchmarks, including WebQSP, SimpleQuestions, and WebQuestions. Moreover, KG-CoT significantly enhances the performance of LLMs on CompWebQ, the challenging knowledge-intensive multi-hop question answering benchmark, compared to LLM baselines relying on standard CoT prompting.

On the WebQSP benchmark, our proposed KG-CoT outperforms recent LLM+KG baseline ToG [Sun et al., 2023] for both LLM settings. Moreover, KG-CoT with the ChatGPT backbone even outperforms ToG with the GPT-4 backbone, demonstrating the effectiveness of our proposed "Large+Small" paradigm for LLMs.

For the single-hop and open-domain question answering benchmarks, our proposed KG-CoT also achieves competitive performances compared to previous state-of-the-art baselines. Notably, for the simple yet knowledge-intensive benchmark, LLMs that rely solely on the parametric knowledge struggle to generate the correct answer even with CoT prompting. On the one hand, the results demonstrate the effectiveness of our proposed KG-CoT in augmenting LLMs with explicit reasoning paths. On the other hand, these results align with previous findings of LLMs [Wang et al., 2023b], indicating that the effectiveness of these standard prompting methods (e.g., CoT and SC) diminishes for complex problems that require extensive factual knowledge.

On the CompWebQ benchmark, our proposed KG-CoT with ChatGPT yielded at 37.2% improvement over standard prompting baselines. We observe that the performance trend of KG-CoT varies compared to those of the other QA benchmarks. This difference is attributed to our proposed graph reasoning model performing less favorably for this challenging multi-hop question answering benchmark, consequently resulting in moderate improvements on CompWebQ.

4.5 Comparison with Different LLMBackbones

To further investigate the generality of our proposed KGCoT, we evaluate KG-CoT on different LLM backbones, such as open-source LLMs (e.g., Llama-7B and Llama-13B) and closed-source LLMs (e.g., ChatGPT and GPT-4). As shown in Table 2, our proposed KG-CoT yield significant improvements across all the LLM backbones. With the increasing intelligence of LLMs, the performance with KG-CoT consistently improves. When Llama2-13B, ChatGPT, and GPT-4 are used as the backbones, LLM+KG-CoT outperforms the existing state-of-the-art KGQA baselines.

4.6 Performance of Locating Answer Entity

To validate the effectiveness of the reasoning paths, we conducted comparative experiments with other retrieval methods (e.g., BM25 and DPR) to evaluate whether the retrieved top-ranked knowledge facts contain the golden answer entity. As shown in Figure 3, the experimental results indicate that our proposed KG-CoT achieves a significant high hit rate (e.g., Hit@1) in locating reasoning paths to the answer entity. Specifically, when considering the top-10 candidate entities (e.g., K=10), KG-CoT yields a coverage rate of up to 91.4% for the WebQSP benchmark, surpassing that of conventional knowledge retrievers. Moreover, for the complex multi-hop question answering benchmark CompWebQ, the hit rate for answers reaches 72.5%, reflecting a substantial improvement in LLM reasoning.

4.7 Hyper-parameter Sensitivity Analysis

In KG-CoT, two parameters that can influence the performance of LLMs are the number of candidate answer entities K and the number of paths extracted for each entity N.

As shown in the left part of Figure 4, we conduct experiments on the WebQSP benchmark to investigate the influence of the candidate answer entity number K. We observed that increasing the number of candidate answer entities from the top-5 to the top-10 yields in a discernible improvement in the performance of LLMs. This enhancement can be attributed to an increased coverage of correct answer entities along the reasoning paths, consequently reducing misguidance caused by the absence of correct reasoning paths. However, when extending the candidate answers from the top 10 to the top 15, we found minimal changes in the performance of LLMs. One one hand, this lack of improvement is attributed to the marginal increase in answer coverage. Moreover, the lower confidence associated with lower ranking reasoning paths contributes marginally to the reasoning process of LLMs.

As shown in the right part of Figure 4, we investigate the impact of the number of reasoning paths corresponding to each candidate answer entity. We observed that increasing the number of reasoning paths has minimal effect on LLM reasoning. This is attributed to the fact that our proposed stepby-step reasoning model already provides the reasoning path with high confidence, which significantly contributes to the LLM reasoning. The inclusion of low-confidence reasoning paths leads to little improvement in LLMs.

4.8 Case Study

In Table 3, our further investigation reveals how KG-CoT enhances the reasoning capability of LLMs by providing accurate factual knowledge and interpretable reasoning paths. For the question: "What is the source of the river which flows under the Dona Ana Bridge?", original prompting methods are influenced by hallucination problems, resulting in an erroneous answer "Willow Creek". Instead, KG-CoT links the question entity to the Freebase and leverages our proposed step-by-step reasoning model to extract reasoning paths with high confidence, enabling LLMs to utilize the responsible and interpretable reasoning paths to generate the correct answer.

4.9 Adaptability

As shown in Table 4, we analyze the advantages of KG-CoT in practical application from two perspectives.

Bandwidth Occupancy. Since we utilize the "Large + Small" paradigm, we only need to extract reasoning paths from the small-scale graph reasoning model and perform joint reasoning with LLMs. This eliminates the necessity of LLMs generating CoT prompts or acting as retrievers to filter triplets and determine the next-hop entity (i.e., ToG [Sun et al., 2023]). On the one hand, KG-CoT reduces the number of API calls to 1 per question, achieving more efficient knowledge enhancement. On the other hand, it diminishes the bandwidth occupancy of LLMs, allowing them to allocate more bandwidth to handle requests from other users.

Inference Cost. In contrast to previous LLM+KG baseline ToG [Sun et al., 2023] which requires an average of 11.2 API calls, KG-CoT can significantly reduce the cost of API calls. Furthermore, our proposed graph reasoning model focuses on "relations" within the KGs, eliminating the need for retraining the model when countering emerging entities.

5 Conclusion

In this work, we propose a novel chain-of-thought prompting over knowledge graphs (KG-CoT), which utilizes a lightweight step-by-step graph reasoning model to augment LLMs with responsible factual knowledge and explicit reasoning paths in a plug-and-play manner. This "Large + Small" paradigm alleviates the burden of LLM reasoning and enables joint reasoning with external world knowledge. Extensive experiments on 4 knowledge-intensive question answering benchmarks demonstrate the effectiveness of our proposed KG-CoT and can provide explicit reasoning paths for improving interpretability. We show that KG-CoT can utilize less bandwidth and reduce inference costs to enhance the capability of various LLMs for knowledge-aware reasoning.

Acknowledgements

This work was supported in part by the National Key R&D Program of China under Grant 2023YFF0905503, National Natural Science Foundation of China under Grants No.62072203, No.62072257 and the Australian Research Council Under Grants DP22010371, LE220100078.