Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning
图推理：忠实且可解释的大型语言模型推理

Recently, many techniques have been explored to improve the reasoning ability of LLMs by planning, which first prompts LLMs to generate a reasoning plan and then conduct reasoning based on it (Wang et al., 2023c). However, LLMs are known for having hallucination issues, which are prone to generating incorrect plans and leading to wrong answers (Ji et al., 2023). To address this issue, we present a novel planning-retrieval-reasoning framework, which makes the reasoning plans grounded by KGs and then retrieves faithful reasoning paths for LLM reasoning.

By treating relation paths as plans, we can make sure the plans are grounded by KGs, which enables LLMs to conduct faithful and interpretable reasoning on graphs. In a nutshell, we formulate our RoG as an optimization problem that aims to maximize the probability of reasoning the answer from a knowledge graph ${\mathcal{G}}$ w.r.t the question $q$ by generating relation paths $z$ as the plan:

where $\theta$ denotes the parameters of LLMs, $z$ denotes the relation paths (plans) generated by LLMs, and ${\mathcal{Z}}$ denotes the set of possible relation paths. The latter term $P_{\theta}(z|q)$ is the probability of generating a faithful relation path $z$ grounded by KG, given the question $q$, which is realized by the planning module. The former term $P_{\theta}(a|q,z,{\mathcal{G}})$ is the probability of reasoning an answer $a$ given the question $q$, relation path $z$, and KG ${\mathcal{G}}$, which is computed by the retrieval-reasoning module.

Despite the advantage of generating relation paths as plans, the LLMs have zero knowledge of the relations contained in KGs. Therefore, LLMs cannot directly generate relation paths grounded by KGs as faithful plans. Moreover, LLMs might not understand the reasoning paths correctly and conduct reasoning based on them. To address these issues, we design two instruction tuning tasks: 1) planning optimization, which distills the knowledge from KGs into LLMs to generate faithful relation paths as plans; 2) retrieval-reasoning optimization, which enables LLMs to reason based on the retrieved reasoning paths.

The objective function in equation 1 can be optimized by maximizing the evidence lower bound (ELBO) (Jordan et al., 1999), which is formulated as

where $Q(z)$ denotes the posterior distribution of faithful relation paths grounded by KGs. The latter term minimizes the KL divergence between the posterior and the prior, which encourages LLMs to generate faithful relation paths (planning optimization). The former term maximizes the expectation that retrieval-reasoning module generates correct answers based on the relation paths and KGs (retrieval-reasoning optimization).

Planning optimization. In planning optimization, we aim to distill the knowledge from KGs into LLMs to generate faithful relation paths as plans. This can be achieved by minimizing the KL divergence with the posterior distribution of faithful relation paths $Q(z)$, which can be approximated by the valid relation paths in KGs.

Given a question $q$ and answer $a$, we could find the path instances $w_{z}(e_{q},e_{a})=e_{q}\xrightarrow{r_{1}}e_{1}\xrightarrow{r_{2}}\ldots\xrightarrow{r_{l}}e_{a}$ connecting $e_{q}$ and $e_{a}$ in KGs. The corresponding relation path $z=\{r_{1},r_{2},\dots,r_{l}\}$ can be considered valid and serve as a faithful plan for answering the question $q$. Therefore, the posterior distribution $Q(z)$ can be formally approximated as

where $\exists w_{z}(e_{q},e_{a})\in{\mathcal{G}}$ denote the existence of a path instance connecting the question $e_{q}$ and answer $e_{a}$ entities in ${\mathcal{G}}$. To reduce the number of valid relation paths, we only consider the shortest paths between $e_{q}$ and $e_{a}$ in KGs (Zhang et al., 2022). Therefore, the KL divergence can be calculated as

By optimizing the equation 4, we maximize the probability of LLMs generating faithful relation paths through distilling the knowledge from KGs.

Retrieval-reasoning optimization. In retrieval-reasoning optimization, we aim to enable LLMs to conduct reasoning based on the retrieved reasoning paths. For the retrieval-reasoning module, we follow the FiD framework (Izacard & Grave, 2021), which allows reasoning on multiple retrieved reasoning paths, formulated as

By approximating the expectation with K sampled plans ${\mathcal{Z}}_{K}$, the objective function of reasoning optimization can be written as

This maximizes the probability of LLMs generating correct answers based on the retrieved reasoning paths.

The final objective function of RoG is the combination of the planning optimization and retrieval-reasoning optimization, which can be formulated as

From equation 7, we can see that we adopt the same LLM for both planning and reasoning, which are jointly trained on two instruction-tuning tasks, i.e., (planning and retrieval-reasoning). We will discuss the implementation details of these two tasks in the following subsections.

The planning module aims to generate faithful relation paths as plans for answering the question. To utilize the instruction-following ability of LLMs (Wei et al., 2021), we design a simple instruction template that prompts LLMs to generate relation paths:

where <Question> indicates the question $q$. The question together with the instruction template is fed into LLMs to generate the relation paths, which are structurally formatted as a sentence:

where <PATH>, <SEP>, </PATH> are special tokens indicating the start, separator, and end of the relation path, respectively²²2The relation name $r_{*}$ could be split into multiple tokens. For example, “born_in” could be split into “born” and “_in” by tokenizer. In this way, we could fully utilize the semantic information in relation names and generalize to different KGs..

Therefore, the optimization of ${\mathcal{L}}_{\text{plan}}$ can be achieved as

where $P_{\theta}(z|q)$ denotes the prior distribution of generating faithful relation path $z$, and $P_{\theta}(r_{i}|r_{<i},q)$ denotes the probability of each token in $z$ generated by LLMs.

Retrieval. Given a question $q$ and a relation path as plan $z$, the retrieval module aims to retrieve the reasoning paths $w_{z}$ from KG ${\mathcal{G}}$. The retrieval process can be conducted by finding paths in ${\mathcal{G}}$ that start from the question entities $e_{q}$ and follow the relation paths $z$, formulated as

We adopt a constrained breadth-first search to retrieve the reasoning paths $w_{z}$ from KGs. In experiments, all retrieved paths are used for reasoning. The detailed retrieval algorithm can be found in Section A.2.

Despite we can utilize the retrieved reasoning paths and directly get the answers with majority voting. The retrieved reasoning paths could be noisy and irrelevant to the questions, which leads to incorrect answers (He et al., 2021; Zhang et al., 2022). Therefore, we propose a reasoning module to explore the ability of LLMs to identify the important reasoning paths and answer the questions based on them.

Reasoning. The reasoning module takes the question $q$ and a set of reasoning paths ${\mathcal{W}}_{z}$ to generate answers $a$. Similarly, we design a reasoning instruction prompt to guide LLMs to conduct reasoning based on the retrieved reasoning paths ${\mathcal{W}}_{z}$:

where <Reasoning Paths> denotes the retrieved reasoning paths ${\mathcal{W}}_{z}$ which are also formatted as a series of structural sentences. The detailed of prompts can be found in Section A.9.

The optimization of ${\mathcal{L}}_{\text{reason}}$ can be written as

where $P_{\theta}(a|q,{\mathcal{Z}}_{K},{\mathcal{G}})$ denotes probability of reasoning the correct answer $a$ based on $K$ relation paths ${\mathcal{Z}}_{K}$, and $t_{*}$ denote the tokens of answers $a$.

Datasets. We evaluate the reasoning ability of RoG on two benchmark KGQA datasets:

WebQuestionSP (WebQSP) (Yih et al., 2016) and Complex WebQuestions (CWQ) (Talmor & Berant, 2018), which contain up to 4-hop questions. The statistic of the datasets are given in Table 1. Freebase (Bollacker et al., 2008) is the background knowledge graph for both datasets, which contains around 88 million entities, 20 thousand relations, and 126 million triples. The details of the datasets are described in Section A.3.

Baselines. We compare RoG with 21 baselines grouping into 5 categories: 1) Embedding-based methods, 2) Retrieval-augmented methods, 3) Semantic parsing methods, 4) LLMs, and 5) LLMs+KGs methods. The details of each baseline are described in Section A.4.

Evaluation Metrics. Following previous works, we use Hits@1 and F1 as the evaluation metrics. Hits@1 measures the proportion of questions whose top-1 predicted answer is correct. Since a question may correspond to multiple answers, F1 considers the coverage of all answers, which balances the precision and recall of the predicted answers.

Implementations. For RoG, we use LLaMA2-Chat-7B (Touvron et al., 2023) as the LLM backbone, which is instruction finetuned on the training split of WebQSP and CWQ as well as Freebase for 3 epochs. We generate the top-3 relation paths using beam-search for each question. Since UniKGQA (Jiang et al., 2022) and DECAF (Yu et al., 2022a) are state-of-the-art methods, we directly refer their results and those of the other baselines reported in their papers for comparisons. For LLMs, we use zero-shot prompting to conduct KGQA. The detailed settings are described in Section A.5.

Main Results. In this section, we compare RoG with other baselines on KGQA tasks. The results are shown in Table 2. Our method achieves the best performance on both datasets across most metrics. Specifically, compared to the SOTA method DECAF (Yu et al., 2022a) on WebQSP, our method improves Hits@1 by 4.4%. On the CWQ dataset, which is more challenging due to multi-hop questions, our method improves both Hits@1 and F1 by 22.3% and 14.4% against the SOTA model UniKGQA (Jiang et al., 2022). These results demonstrate the superior reasoning ability of our method in KGQA.

Among other methods, retrieval-augmented approaches outperform conventional embedding-based methods by retrieving relevant subgraphs from KGs, which reduces reasoning complexity. Furthermore, SR+NSM and SR+NSM+E2E adopt relation paths-based retrieval which achieves better performance, highlighting the importance of relation paths. Semantic parsing methods perform better than retrieval methods on WebQSP but worse on CWQ due to the complexity of generating logical queries for complex questions in CWQ. Although LLMs-based methods achieve comparable performance, they are limited by hallucinations and lack of knowledge as shown in Section 5.5. The LLMs+KGs methods achieve the second-best performance, which demonstrates the effectiveness of unifying KGs and LLMs for reasoning.

Ablation Study. We conduct an ablation study to analyze the effectiveness of the planning module and reasoning module in our method (RoG). We compare four variants: 1) w/o planning, where we remove the planning module and perform reasoning without retrieved reasoning paths; 2) w/o reasoning, where we remove the reasoning module and use all answers from retrieved reasoning paths as results; 3) w/ random plans, where we randomly retrieve reasoning paths from KGs and feed them into the reasoning module; 4) w/ vote reasoning, where we adopt the majority voting to select top-5 answers from retrieved reasoning paths. The results are shown in Table 3.

From the results, it is evident that without a planning module, our method degenerates to conventional LLMs that solely rely on questions as input, suffering from the lack of knowledge issue. Although removing the reasoning module leads to high recall due to an increased number of answers, precision drops significantly because of noise in retrieved paths. This demonstrates the effectiveness of the reasoning module in identifying important reasoning paths and filtering out noise. Furthermore, using random plans achieves worse performance than removing the planning module, highlighting the importance of a planning module who generates faithful reasoning plans. Using a simple majority vote reasoning can improve the results which also demonstrate the necessity of reasoning module.

In this section, we evaluate the effectiveness of integrating the planning module of RoG with different LLMs during inference to improve their performance. Specifically, we first adopt the planning module of RoG to generate relation paths and feed the retrieved reasoning paths as context into different LLMs for reasoning. The results are presented in Table 4. To account for the fact that it is difficult to extract the number of answers from LLM’s output. We only report the Hits@1 and Recall metrics.

From the results, we can notice that the performance of all LLMs is substantially improved by integrating the planning module of RoG. Specifically, the Hits@1 of ChatGPT, Alpaca, LLaMA2, and Flan-T5 are improved by 8.5%, 15.3%, and 119.3%, respectively. This demonstrates that the planning module of RoG can be seamlessly integrated with other LLMs to improve their performance without retraining.

We also evaluate the transferability of RoG to other KGs. We select the MetaQA-3hop dataset (Zhang et al., 2018) which is based on Wiki-Movies KGs³³3https://research.fb.com/downloads/babi.. We select 1000 samples from the training split and utilize two training strategies to finetune RoG: 1) training from scratch, where we directly optimize RoG with 1000 samples; 2) transfer from Freebase, where we conduct a further finetuning based on RoG trained for Freebase. The results are shown in Table 5. From results, we can see that transfer from Freebase achieves better performance than training from scratch, which demonstrates the transferability of RoG to other KGs.
我们还评估了 RoG 向其他 KG 的可转移性。我们选择基于Wiki-Movies KG ³ 的MetaQA-3hop数据集（Zhang et al.， 2018）。我们从训练拆分中选择 1000 个样本，并利用两种训练策略来微调 RoG：1） 从头开始训练，我们直接用 1000 个样本优化 RoG;2）从Freebase转移，我们根据为Freebase训练的RoG进行进一步的微调。结果如表5所示。从结果中，我们可以看到从Freebase转移比从头开始训练的性能更好，这表明RoG可以转移到其他KG。

Quantitative Results. To evaluate the faithfulness of the relation paths, we illustrate the quantitative results in Figure 3. In experiments, we sweep the number of top-$K$ relation paths generated by RoG. From results, we can see that the number of retrieved reasoning paths increases with $K$, which also leads to more answers to be covered (recall). This demonstrates the faithfulness of the relation paths by retrieving the answers. However, more retrieved reasoning paths also lead to more noise and retrieval time (shown in Section A.6.1), which decreases the precision and makes little contribution to the final results (reasoning-f1). Therefore, we set $K=3$ in experiments.

Case studies. We also illustrate two case studies in Table 6 and Table 7. In Table 6, we can find that ChatGPT+CoT suffers from the lack of knowledge issue and cannot answer the question. On the contrary, RoG can generate faithful relation paths and retrieve valid reasoning paths from KGs for reasoning. Besides, RoG can provide interpretable explanations based on the reasoning paths. In Table 7, we can see that ChatGPT+CoT suffers from hallucinations and generates incorrect answers. In contrast, although the retrieved reasoning paths contain noises, the reasoning module can identify the correct reasoning paths and conduct faithful reasoning. These results demonstrate the effectiveness of RoG in conducting faithful reasoning and generating interpretable results. More cases can be found in Sections A.7 and A.8.