FiDeLiS: Faithful Reasoning in Large Language Model for Knowledge Graph Question Answering

We sincerely thank the reviewer for their thoughtful comments. Regarding the writing issues mentioned in W1, we will polish our paper in the revised version. For the other concerns, we provide detailed responses below:

---

W2: The experiments comparing Fine-tuned LLMs with GPT-4 seems unfair.

We acknowledge the concern due to GPT-4 being a proprietary model with limited accessibility for fine-tuning or deeper customization. Our decision for this comparison is intended to observe trends whether the proposed training-free framework can achieve similar or even better performance compared to methods requiring further training. Our findings demonstrate that the proposed method, as a training-free framework, outperforms fine-tuned models while requiring significantly less time and computational resources for training.

---

W3: The vanilla retriever compared in Section 3.3 is a relatively simple retriever.

We appreciate the reviewer's concern. To further validate this, we add another baseline from KAPING[1], and report the coverage ratio comparison on CWQ as follows:

These results demonstrate that Path-RAG consistently achieves higher coverage, especially for deeper reasoning paths. Unlike the triplet-based retrieval in KAPING, Path-RAG leverages graph structure to capture not only highly relevant nodes and edges but also intermediate “bridge” connecting other highly relevant nodes and edges in next hop neighbors. This design mitigates over-reliance on semantic similarity alone by ensuring that structural relationships are also considered, reducing the likelihood of errors in reasoning path construction.

• [1] Knowledge-Augmented Language Model Prompting for Zero-Shot Knowledge Graph Question Answering: https://arxiv.org/pdf/2306.04136

---

Q1: Does the accuracy of keyword extraction significantly impact the effectiveness of the retrieval approach?

Yes, the keyword extraction impacts the effectiveness of the retrieval approach. We add another ablation study to consider using keywords and without using keywords as follows: (we use coverage ratio to measure the effectiveness of different retrievers)

It shows that generating an exhaustive list of keywords related to the query can maximize the coverage of potential reasoning steps required to answer it. These keywords expand the search space for the beam search process by including additional, related information that may not be explicitly stated in the query. During the retrieval stage, this broader keyword list allows the system to identify more potential candidates, which enriches the input for the beam search. As a result, the expanded search space increases the chances of discovering relevant reasoning paths and improves the model’s ability to find accurate and effective solutions.

We sincerely thank the reviewer for the thoughtful comments. Below, we address each concern in detail:

---

W1: The reviewer is concerned that the novelty of the paper is limited, especially compared with existing retrieval-augmented methods.

We acknowledge that there are similarities between the proposed method and previous retrieval-augmented methods, especially we both follow the workflow of retrieving some information from external resource and use them to enhance the LLM reasoning. However, we would like to highlight that our contributions should be not considered as incremental efforts for the following reasons:

Paradigm shift from retrieving knowledge facts to reasoning paths from KG. Unlike existing retrieval-augmented methods that retrieve individual triplets from a knowledge graph (KG) as additional knowledge to support reasoning, our method leverages the structural information of the KG. Specifically, we retrieve reasoning paths—sequences of interconnected triplets—directly from the KG to guide LLM reasoning. These reasoning paths provide a more structured and factual basis for reasoning compared to the self-generated chain-of-thought (CoT) by LLMs, ensuring greater factual accuracy. Additionally, the reasoning paths enhance the explainability of the reasoning process, offering a clear rationale for how the final answer is derived.

In addition, our proposed method focus on two challenges when retrieving reasoning paths from KG as follows:

(a) Issues of premature stopping or excessive continuation when extending the reasoning paths: When retrieving reasoning paths from a KG, two critical challenges can arise: premature stopping, where the retrieval process halts before a complete reasoning path is constructed, or excessive continuation, where the path is extended unnecessarily, including irrelevant or incorrect steps. These issues will hinder the performance of LLMs’ decision making (as shown in the case study from lines 422 to 455). Our proposed method uses deductive reasoning as a clear and objective way to decide when to stop extending reasoning paths. Deductive reasoning involves verifying whether each reasoning step logically follows from the previous steps and the user query, making it more reliable and less ambiguous. This approach not only simplifies decision-making but also reduces bias in the reasoning process, ensuring fairer and more accurate stopping criteria. We would like to highlight that this straightforward shift in controlling the end point of reasoning paths demonstrates promising performance, particularly in cases requiring deeper reasoning steps (e.g., CoT and CL-RT with reasoning depths >3).

(b) Issues of inefficiency in handling large reasoning steps candidates: In addition, previous work did not consider the retrieval process, which means it considers all neighboring entities/relations during reasoning path extension. This can be particularly problematic for large KGs that have a vast number of neighbors available. It will substantially increase the computational cost for LLM reasoning (as more tokens are considered) and introduces noise from irrelevant nodes and edges, which hampers the effectiveness of subsequent LLM’s decision making process. In contrast, our method first retrieves entities and relations relevant to the query to construct reasoning path candidates. This allows the LLM to focus on a smaller, more relevant set of candidates during decision-making, improving efficiency and reducing the need to filter out irrelevant noise. As demonstrated in our experiments, this retrieval-based approach (path-RAG) consistently achieves better overall performance on different settings (Table 1,2).

---

W2: Why use Path-RAG and what is the sensitivity of the hyperparameter $\alpha$?

Path-RAG is proposed to retrieve entities and relations relevant to the query to construct reasoning path candidates. This allows the LLM to focus on a smaller, more relevant set of candidates during decision-making, improving efficiency and reducing the need to filter out irrelevant noise. As demonstrated in our experiments, this retrieval-based approach (path-RAG) consistently achieves better overall performance on different settings (Table 1,2).

Quantitatively, the hyperparameter $\alpha$ in the scoring function (Eq. (3)) balances short-term outcomes and long-term potential in reasoning paths. A higher $\alpha$ prioritizes paths with long-term benefits, even if they appear sub-optimal initially, whereas a lower $\alpha$ emphasizes immediate gains, potentially overlooking future impacts. We select the $\alpha$ using grid search. As noted in lines 849 to 855, $\alpha$ does not significantly affect the overall system performance, indicating that Eq. (3) is not highly sensitive to variations in $\alpha$.

---

W3: Adding more recent baselines and more model backbones.

We acknowledge that KG-CoT and ToG-2.0 were recently published and are contemporaneous with our own. As they became available around the same time as our submission, we have not considered them as primary baselines in our study. However, we appreciate the reviewers bringing these to our attention and will take them into account in future work.

For the reference GNN-RAG, we acknowledge that this paper have shown better performance as a framework requires extra training, while our proposed method is more like a training-free framework. The comparison between these two frames may not be very fair.

To address the reviewers’ concerns about generalizability and robustness across different model architectures, we add more recent language models as follows:

---

Q1: Explanation for the concept of "deductive verification"

Thank you for pointing out this concern. We understand that the term “deductive verification” might traditionally suggest the use of a formal, rule-based system or a structured knowledge base. In our work, however, the term is used more broadly to describe how the LLM infers logical consequences by evaluating whether a given reasoning path aligns with the user query and retrieved evidence from the knowledge graph.

For instance, as described in the manuscript (Lines 989–1020), consider the question: “Who is the ex-wife of Justin Bieber’s father?” After one round of beam searching, the current reasoning path is:

“Justin_bieber → people.person.father → Jeremy_bieber.”

The next step candidates are:

1. people.married_to.person → Erin Wagner
2. people.person.place_of_birth → US, . . .

In this context, “deductive reasoning verification” operates as follows: The model evaluates whether the user query can be logically deduced by extending the current reasoning path with a candidate step. For instance, we assess whether the candidate people.married_to.person → Erin Wagner logically supports the query. Specifically, we represent reasoning paths as premises and the user query as a conclusion, then check whether the conclusion can be deduced from the premises.

Premise:

• Justin_bieber $\to$ people.person.father $\to$ Jeremy_bieber (from the current reasoning path)
• Jeremy_bieber $\to$ people.married_to.person $\to$ Erin Wagner (from the next step candidates)

Conclusion:

• Erin Wagner is the ex-wife of Justin Bieber’s father. (Using a large language model (LLM) zero-shot approach to reformat the question into a cloze filling task, we use the last entity from the next step candidates, "Erin Wagner", to fill the cloze.)

The LLM is prompted to evaluate whether the conclusion logically follows from the premises. If the answer is “yes,” the reasoning path extension is considered complete. If the answer is “no,” the reasoning path is either extended further or discarded entirely. This approach differs from traditional rule-based systems as it does not rely on a predefined set of rules or formalized knowledge bases. Instead, it leverages the LLM’s implicit knowledge and reasoning capabilities to dynamically evaluate each step in the context of the query

Q1: Does Path-RAG maintain the same retrieval strategy when obtaining the next possible reasoning step candidates $S_t$?

Yes, the retrieval strategy remains consistent when obtaining the next possible reasoning step candidates $S_t$.

A follow-up question: "Does it incorporate previously formed reasoning steps to aid in retrieval?"

By design, we do not explicitly use previously formed reasoning steps during the retrieval process. Instead, this information is utilized in the subsequent LLM reasoning step for enhanced decision-making. The rationale for this design is to keep the retrieval process lightweight and focused solely on identifying the most relevant next-hop candidates, rather than introducing additional complexity by conditioning on earlier steps. By separating the retrieval and reasoning processes, we aim to balance efficiency and accuracy while allowing the LLM to dynamically integrate information from prior reasoning steps.

---

Q2: How sensitive is the method to the quality of the knowledge graph?

To address the question, we add a new experimental setting where we deliberately manipulated the KG’s quality. Specifically, we perturbed the relations within the KGs to simulate real-world scenarios where some edges may be mislabeled, missing, or incorrectly connected to unrelated nodes. We consider four perturbation heuristics—relation swapping, replacement, rewiring, and deletion to represent the main manifestations of inaccuracies of KG as follows (Find the results in Appendix H):

• Relation swapping simulates misclassified or mislabeled relationships.
• Replacement introduces spurious links to emulate noise.
• Rewiring reflects structural distortions in graph connectivity.
• Deletion models missing edges or incomplete knowledge.

Our findings, presented in the revised paper (refer to the Appendix H), indicate that the performance of our method remains robust to a reasonable level of perturbation. This robustness is primarily due to our method’s reliance on both semantic similarity and structural information during retrieval, which helps mitigate the effects of incorrect or incomplete edges. Additionally, the LLM’s reasoning capabilities provide further resilience by dynamically compensating for some inaccuracies in the retrieved reasoning paths.

---

Q3: How does the method handle questions that require commonsense reasoning during the inference process?

In this paper, we did not explicitly design mechanisms to handle common sense question answering, as our primary focus is on the KGQA task, where the model answers questions based on knowledge graph (KG) information. However, our proposed method can be adapted to handle commonsense reasoning in the following ways:

(1) Utilizing Commonsense Knowledge Graphs: There are existing commonsense knowledge graphs (e.g., ConceptNet) that could serve as valuable resources for providing commonsense knowledge. By integrating such graphs into our framework, the proposed method can construct plausible commonsense reasoning paths to support the question-answering process.

(2) Leveraging LLMs for Final Reasoning: Our method relies on LLMs for the final reasoning step, and these models are inherently equipped with fundamental commonsense reasoning capabilities and pre-trained on vast amounts of general knowledge. This enables the LLMs to handle aspects of commonsense reasoning that are not explicitly covered by the knowledge graph.

We sincerely thank the reviewer for their thoughtful comments. Regarding the writing issues mentioned in W1, we have revised the manuscript and corrected the errors. For the other concerns, we provide detailed responses below:

---

W2: Why deductive reasoning verification is more suitable compared to traditional logit-based scoring methods?

Logit-based scoring methods rely on softmax-based probability scores to assess plausibility. These scores lack interpretability and often exhibit overconfidence, where invalid reasoning steps can sometimes be assigned higher probabilities due to inherent model biases. In contrast, our proposed deductive verification follows the idea that each intermediate reasoning step should be verified whether it is logically consistent with the previous steps and whether it can contribute to answering the user query (as shown in the example in Lines 987–1020). This mechanism helps minimize the error propagation when extending the reasoning paths, especially for cases when reasoning paths seem plausible but contain subtle errors in intermediate steps.

To validate this claim, we add additional experiment setting using "logit-based scoring", where the endpoint of reasoning path extension was framed as a binary classification task (“yes” or “no”) and we use the corresponding probability scores as the decision criteria. The comparison between deductive reasoning verification and logit-based scoring, as well as adequacy verification (used in ToG), is shown below:

The results show that deductive reasoning consistently outperforms logit-based scoring by ensuring better logical grounding and reducing overconfidence errors.

---

W3: Does Path-RAG perform well across varying complexities, and does it over-rely on semantic similarity?

We appreciate the reviewer's concern. As shown in Figure 3(a) and (b), Path-RAG consistently achieves a higher coverage ratio of ground-truth reasoning steps compared to baseline across varying complexities of questions (controlled by the reasoning depths required to answer each question). Unlike vanilla retrievers that rely solely on semantic similarity, Path-RAG incorporates structural information via next-hop connections (as shown in Eq. (3)), which significantly enhance the retrieval performance.

To further validate this, we add another baseline from KAPING[1], and report the coverage ratio comparison on CWQ as follows:

These results demonstrate that Path-RAG consistently achieves higher coverage, especially for deeper reasoning paths. Unlike the triplet-based retrieval in KAPING, Path-RAG leverages graph structure to capture not only highly relevant nodes and edges but also intermediate “bridge” connecting other highly relevant nodes and edges in next hop neighbors. This design mitigates over-reliance on semantic similarity alone by ensuring that structural relationships are also considered, reducing the likelihood of errors in reasoning path construction.

• [1] Knowledge-Augmented Language Model Prompting for Zero-Shot Knowledge Graph Question Answering: https://arxiv.org/pdf/2306.04136

---

W4 - Clarification of some minor concerns

(1) Are the reasoning step candidates all from $E_m$ and $R_m$? Does beam search only execute on the candidates?

Yes, you are right. All the reasoning step candidates are constructed from $E_m$ and $R_m$ based on the Eq (3). And the beam search process is executed on the reasoning step candidates at each timestamp.

(2) How to obtain the conclusion that the proposed method shows superior efficiency compared to the ToG from Table 6.

We would like to clarify that Table 6 includes results when replacing Path-RAG with ToG for the retrieval mechanism (labeled as “w/o Path-RAG using ToG”). These results show significantly higher average runtime (e.g., 74.26s on WebQSP and 132.59s on CWQ) and increased token usage using ToG compared to our proposed Path-RAG. This directly highlights the efficiency improvements achieved by using Path-RAG.

In addition, on both WebQSP and CWQ, our method consistently achieves lower runtime and token usage while maintaining or improving performance (Hits@1). This demonstrates that our approach streamlines the reasoning process, leading to more efficient use of resources compared to the ToG.

We sincerely thank the reviewer for the thoughtful comments. Below, we address each concern in detail:

---

W1: The reviewer is concerned that the novelty of the paper is limited, especially compared with previous work ToG.

We acknowledge that there are indeed similarities between the proposed method and previous work ToG, especially we both consider using the beam search paradigm for retrieving reasoning paths from KG to guide the LLM reasoning. However, we would like to highlight that our contributions should be not considered as incremental efforts for the following reasons:

(a) Issues of premature stopping or excessive continuation: as noted in the manuscript (lines 77 to 81), ToG relies on LLMs to determine when to stop extending a reasoning path by assessing whether the current path is adequate to answer the question. However, this evaluation primarily focuses on superficial relevance and does not ensure that each reasoning step is factually accurate or logically consistent with previous steps. This limitation often results in challenges such as premature stopping or excessive continuation of reasoning paths, leading to retrieved paths that are either incomplete or contain incorrect steps. This issue will hinder the performance of LLMs’ decision making (as shown in the case study from lines 422 to 455).

In contrast, our proposed method uses deductive reasoning as a clear and objective way to decide when to stop extending reasoning paths. Deductive reasoning involves verifying whether each reasoning step logically follows from the previous steps and the user query, making it more reliable and less ambiguous. This approach not only simplifies decision-making but also reduces bias in the reasoning process, ensuring fairer and more accurate stopping criteria. We would like to highlight that this straightforward shift in controlling the end point of reasoning paths demonstrates promising performance, particularly in cases requiring deeper reasoning steps (e.g., CoT and CL-RT with reasoning depths >3), where ToG sometimes struggles to perform effectively.

(b) Issues of inefficiency in handling large reasoning steps candidates: In addition, ToG did not consider the retrieval process, which means it considers all neighboring entities/relations during reasoning path extension. This can be particularly problematic for large KGs that have a vast number of neighbors available. It will substantially increase the computational cost for LLM reasoning (as more tokens are considered) and introduces noise from irrelevant nodes and edges, which hampers the effectiveness of subsequent LLM’s decision making process.

In contrast, our method first retrieves entities and relations relevant to the query to construct reasoning path candidates. This allows the LLM to focus on a smaller, more relevant set of candidates during decision-making, improving efficiency and reducing the need to filter out irrelevant noise. As demonstrated in our experiments, this retrieval-based approach (path-RAG) consistently achieves better overall performance on different settings (Table 1,2).

Overall, we believe these contributions substantiate the novelty of our work and demonstrate meaningful advancements over ToG, particularly in addressing the key limitations mentioned above.

---

W2: Unfair comparison regarding hyper-parameters of beam width and depth.

Thank you for pointing out this issue. We would like to clarify that the results presented in Table 2 are based on our reproduction of ToG. In these experiments, we ensured that both methods used the same beam width and depth (both set to 4) to maintain a fair comparison. We have explicitly added this clarification in the revised version of our paper. Your observation that ToG achieves higher performance with a beam width and depth of 4 is correct, as both methods leverage beam search, and generally, increasing the search space tends to increase the possibility of finding the promising solutions, which could further enhance the overall performance.

---

W3: Does the overall performance mainly relies on Path-RAG as shown ablation study in Table 2?

We appreciate the reviewer's observations regarding the role of Path-RAG in our ablation study in Table 2. While Path-RAG plays a significant role in enhancing the overall performance, we would like to emphasize that the improvements are the result of synergy between Path-RAG and our deductive reasoning verification mechanism. As shown in Table 2, replacing Path-RAG with ToG results in a performance decline, but still achieves 1.88% improvement on CWQ and 0.99% on CR-LT compared to ToG. It demonstrates that the proposed deductive reasoning perform better on cases requires more complex and multi-step reasoning (where CWQ and CR-LT requires longer reasoning steps) and also verify that the performance enhancement is not solely rely on Path-RAG module.