Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models

Thank you for your detailed review and constructive feedback on our submission. We appreciate your recognition of the strengths of our work and your thoughtful comments on areas where we could improve. Below, we address your main concerns:

Weakness 1: Computational Expense of KG-Trie Construction

We want to clarify that there is no need to build a KG-Trie for all entities in KGs. In experiments, we only construct the KG-Trie for entities mentioned in questions. The KG-Trie can be either pre-computed or constructed on-demand to minimize pre-processing time. When the user’s questions are comping, we can identify the mentioned question entities and retrieve the question-related subgraphs from KGs for KG-Trie construction. This process is also very efficient, where the detailed analysis of time complexity and actual running time can be found in our responses to all reviewers. We also discuss the potential solutions to further improve the efficiency and scale into real-world applications with billion-scale KGs.

Weakness 2: Adaptability to Real-World KG Incompleteness

We thank you for the insightful comments. Facts in KGs are usually more clean and trustworthy than open-world knowledge, which could serve as a convincing source of knowledge to guide reasoning in GCR. However, the incompleteness of the KGs could still undermine the accuracy of the GCR. As shown in the error cases (response to weakness 3 of reviewer hR19), the missing knowledge would mislead the reasoning of GCR. We will explore the reasoning for incomplete KGs in the future.

To alleviate the effects of unreliable paths, we propose the graph inductive reasoning module. We adopt a powerful general LLM to reason over multiple generated paths and select useful paths to produce final answers. For example,

Question: who did jackie robinson first play for?
Ground-truth answer: UCLA Bruins football
Generated paths:
Jackie Robinson -> sports.pro_athlete.teams -> m.0hpgh_h -> sports.sports_team_roster.team -> UCLA Bruins football
Jackie Robinson -> baseball.baseball_player.batting_stats -> m.06sbpz2 -> baseball.batting_statistics.team -> Brooklyn Dodgers
Predicted answer: UCLA Bruins football

In this example, two reasoning paths about the team of Jackie Robinson are generated. However, only the first one is the first team of Jackie Robinson. Thus, based on the internal knowledge of powerful LLMs, we can filter out the irrelevant path and infer the final answer.

Weakness 3: Additional time cost for zero-shot generalizability.

Zero-shot transfer experiments are conducted on three new datasets: FreebaseQA, CSQA and MedQA. GCR was applied directly to these new datasets without additional fine-tuning. It showed greater improvements on FreebaseQA and CSQA, underscoring its zero-shot generalizability. We hypothesize that the less significant gains observed on MedQA may stem from LLMs having limited knowledge in the medical domain, which hampers their reasoning capabilities.

The additional time cost of implementing GCR mainly comes from the graph-constrained decoding. We present the additional time using different KG-specialized LLMs below. From the results, it is evident that the introduced additional time would decrease with the size of LLMs. Notably, the time can be further reduced with optimizations such as LLM quantization and flash attention.

Additional time (s) introduced by GCR under different KG-specialized LLMs.

Weakness 4: Discuss and summarize more KG-enhanced methods

Thanks for the suggestions. Due to the limited space, we add more discussion about existing KG-enhanced methods into Appendix A of the revision.

I appreciate the authors' response to my concerns. However, after reading the response, I still have the following concerns:

1. In practical applications, since users' inputs are unpredictable, I believe it is crucial to build a KG-Trie for all entities in the KG. Therefore, considering the time and space costs of constructing such a KG-Trie is necessary. Additionally, given the unpredictability of the input, I remain curious: if the entities in the input question cannot be retrieved from the KG-Trie, does this mean that GCR cannot provide any gain in such scenarios?

2. In the general reply, the authors reported time results for L=1,2,3. However, I am curious about the implications of a larger L, such as L=10 for highly complex inference tasks. Would the time cost grow exponentially with larger L, potentially limiting the practical applicability of GCR?

3. Have the authors considered using larger KG-specialized LLMs, such as Llama 3 (13B or 70B)? How would the performance improvement compare with the associated increase in time costs?

4. I believe contamination in the KG is an important factor to consider, as even widely used sources like Wikipedia contain many incorrect links. Therefore, I am somewhat concerned about the claim of "zero reasoning hallucination." I hope the authors can provide more detailed information on this aspect.

In conclusion, I will maintain my current score and look forward to the authors' further responses to these questions.

I appreciate the authors' response to my concerns. I still have some concerns regarding the construction of the kg-trie. If it does not require a complete kg-trie to be built, would user inputs in an open-ended setting risk not being captured or retrieved by the kg-trie even with the NER or EL tools? Given this, I remain focused on the issue of kg-trie construction time. I am inclined to maintain the current scores for now. I am expecting that the authors to provide more details for me to reconsider my evaluation.

We appreciate the reviewer’s positive comments. We have revised the manuscript based on your feedback and provided detailed responses to each point below. We hope our answers address your questions.

Weakness 1: Computational Expense of KG-Trie Construction

We want to clarify that there is no need to build a KG-Trie for all entities in KGs. In experiments, we only construct the KG-Trie for entities mentioned in questions. The KG-Trie can be either pre-computed or constructed on-demand to minimize pre-processing time. When the user’s questions are comping, we can identify the mentioned question entities and retrieve the question-related subgraphs from KGs for KG-Trie construction. This process is also very efficient, where the detailed analysis of time complexity and actual running time can be found in our responses to all reviewers. We also discuss the potential solutions to further improve the efficiency and scale into real-world applications with billion-scale KGs.

The number of hops is determined by the size of the graphs and the distribution of questions. Empirically, larger hops can improve answer coverage but increase KG-Trie construction time as shown in our general responses. Therefore, users must balance efficiency and effectiveness. In our experiments, we set the hops to 2 or 3, as this covers 99% of question answers.

Weakness 2: Difference with Post-validation of Paths

We thank you for your inspiring comments. While the post-validation can also verify the trustworthiness of the reasoning paths, it would bring significant additional computation costs and potential errors, which might not be suitable for inference. Thi et al. $1$ propose a post-validation strategy to verify the reasoning process by checking the existence of paths in KGs.

However, due to the unstructured nature and randomness of the generated text, it is hard to match it with paths in KGs. Additional steps like entity recognition, relation extraction, and entity linking are required in the post-validation stage. Each of the steps requires different techniques and additional computation costs, resulting in higher latency. Moreover, the errors could propagate and undermine the trustworthiness. In contrast, our graph-constrained decoding ensures trustworthiness during decoding without additional validation costs.

$1$ Thi Nguyen, Linhao Luo, Fatemeh Shiri, Dinh Phung, Yuan-Fang Li, Thuy-Trang Vu, and Gholamreza Haffari. 2024. Direct Evaluation of Chain-of-Thought in Multi-hop Reasoning with Knowledge Graphs. In Findings of the Association for Computational Linguistics: ACL 2024, pages 2862–2883, Bangkok, Thailand. Association for Computational Linguistics.

Weakness 3: Analysis of Error Cases

We appreciate your suggestion to include an analysis of error cases. Although our results show that GCR achieves 100% faithful reasoning, there are some failure cases where GCR generates incorrect answers.

Generated paths are unrelated to the questions: Although LLMs exhibit strong reasoning ability, they still cannot always find meaningful paths to the answers. For example,

Question: what electorate does anna bligh representt?
Ground-truth answer: Electoral district of South Brisbane
Generated paths: Anna Bligh -> government.politician.government_positions_held -> m.0cr320w -> government.government_position_held.jurisdiction_of_office -> Queensland
Predicted answer: Queensland

Although GCR provides a valid reasoning path that describes Anna Bligh's political position, it lacks information about her electoral district, resulting in incorrect answers.

KG incompleteness: Although KGs store abundant factual knowledge, there are still missing facts. For example,

Question: who plays ken barlow in coronation street?
Ground-truth answer: William Roache
Generated paths: Coronation Street -> tv.tv_program.program_creator -> Tony Warren -> fictional_universe.fictional_character_creator.fictional_characters_created -> Ken Barlow
Predicted answer: Ken Barlow

Because there is no information about the character's player stored in KGs, GCR cannot generate the correct answer. We will explore the reasoning for incomplete KGs in the future. These failure cases will be included in Appendix F.4 to discuss the limitations and potential future directions.

Thank you for your detailed review and constructive feedback. We appreciate your insightful comments, which have provided valuable guidance for improving our work. Below, we address your main concerns by clarifying some misunderstandings.

Weakness 1: Clarification on GCR’s Advantage over RoG

We want to clarify the advantages of GCR over RoG in the following aspects:

Integration of KG-Trie: RoG uses a planning-retrieval framework, where reasoning paths are retrieved from knowledge graphs (KGs) based on plans generated by large language models (LLMs). However, the lack of constraints in LLMs can lead to hallucinations, resulting in 33% invalid plans, as shown in Fig. 1. In contrast, GCR integrates a KG-Trie into the LLM decoding process without retrieval, ensuring that only valid KG-based paths are produced. This method prevents hallucinations and maintains high reasoning accuracy, demonstrated by the 100% faithful reasoning ratio in Figure 5.

Combination of LLMs: GCR leverages both a lightweight KG-specialized LLM and a powerful general LLM, combining their strengths for constrained graph reasoning and inductive reasoning. This dual approach enables GCR to explore multiple reasoning paths efficiently and provide more accurate answers.

Weakness 2: Tokenizer-Level Decoding Concerns

We want to clarify that our token-level graph-constrained decoding would not lead to entities or relationships that do not exist in KGs. During decoding, we use the KG-Trie to restrict the tokens generated by the LLM to those starting with valid prefixes stored in the Trie. This approach has been used by previous methods to limit LLM output within a specific scope, such as all entities in KGs $1$ . Our KG-Trie is constructed from paths within KGs. Therefore, under these constraints, only valid entities and relations from KGs can be generated by LLMs to form reasoning paths. We have thoroughly checked the generated results and found zero invalid entities or relations, as shown in Figure 5.

Meanwhile, the token-level graph-constrained decoding is more efficient and effective than other LLM-based graph reasoning methods. Due to the unstructured nature of LLMs, they are difficult to apply directly for reasoning on structured knowledge graphs (KGs). Previous LLM-based graph reasoning methods, such as ToG $2$ , typically follow an agent paradigm where LLMs iteratively query information from KGs. This approach incurs multiple API calls, resulting in high computational costs and latency. With KG-Trie, we enable LLMs to reason on KGs within a single decoding process, significantly reducing computation overhead and latency. Additionally, incorporating KG-Trie into LLM decoding does not introduce extra computational costs since it only masks out the probabilities of invalid tokens. Furthermore, this integration leverages GPU parallel computation to traverse multiple paths using beam search.

Table 2 shows that GCR requires less running time and fewer LLM calls than LLM agent-based methods, such as ToG. While retriever-based methods are slightly more efficient than GCR, their performance is limited by the accuracy of additional retrievers, leading to worse results compared to GCR.

Efficiency Comparison with Agent-based LLM methods.

$1$ Nicola De Cao, Gautier Izacard, Sebastian Riedel, and Fabio Petroni. Autoregressive entity retrieval.
In International Conference on Learning Representations, 2022.

$2$ Sun, J., Xu, C., Tang, L., Wang, S., Lin, C., Gong, Y., ... & Guo, J. Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph. In The Twelfth International Conference on Learning Representations.

Weakness 3: Definition of Faithful Reasoning

Thank you for the inspiring comments. In this paper, we define faithful reasoning as generating paths that can be found within KGs, ensuring that the reasoning process aligns with real-world facts. Unlike noisy open-world knowledge, KGs contain abundant factual information verified by experts, which has been used to assess the faithfulness of LLM reasoning $3$ . Therefore, it is reasonable to classify reasoning as faithful or not based on the existence of paths in KGs. While KGs are incomplete and some valid paths may not be present (false negatives), we will explore this further in future work.

$3$ Thi Nguyen, Linhao Luo, Fatemeh Shiri, Dinh Phung, Yuan-Fang Li, Thuy-Trang Vu, and Gholamreza Haffari. 2024. Direct Evaluation of Chain-of-Thought in Multi-hop Reasoning with Knowledge Graphs. In Findings of the Association for Computational Linguistics: ACL 2024, pages 2862–2883, Bangkok, Thailand. Association for Computational Linguistics.

We sincerely appreciate your thorough review and valuable feedback on our submission. We have provided a detailed response to each comment below. We hope our answers can properly address your concerns.

Weakness 1: Computational Expense of KG-Trie Construction

We want to clarify that there is no need to build a KG-Trie for all entities in KGs. In experiments, we only construct the KG-Trie for entities mentioned in questions. The KG-Trie can be either pre-computed or constructed on-demand to minimize pre-processing time. When the user’s questions are coming, we can identify the mentioned question entities and retrieve the question-related subgraphs from KGs for KG-Trie construction. This process is also very efficient, where the detailed analysis of time complexity and actual running time can be found in our responses to all reviewers. We also discuss the potential solutions to further improve the efficiency and scale into real-world applications with billion-scale KGs.

Weakness 2: Inclusion of Graph Reasoning Baselines

We appreciate your suggestion to include additional state-of-the-art graph reasoning methods. However, we want to mention that some GNN reasoning models, like NBFNet and ULTRA, cannot be easily adapted to the question-answering task. NBFNet and ULTRA are designed for inductive knowledge graph completion tasks, which cannot handle the richer semantics in the user’s natural language questions to predict the possible answers.

To compare with GNN-based methods, we select several baselines that utilize the power of GNN in question answering, which are illustrated below. From the results, it is evident that our GCR outperforms all the baselines, demonstrating the superiority of LLMs in graph reasoning. These baselines are included in the graph reasoning section of Table 1.

Comparison with GNN-based graph reasoning baselines.

$1$ Sun, H., Dhingra, B., Zaheer, M., Mazaitis, K., Salakhutdinov, R., & Cohen, W. (2018). Open Domain Question Answering Using Early Fusion of Knowledge Bases and Text. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing (pp. 4231-4242).

$2$ Jiang, J., Zhou, K., Zhao, X., & Wen, J. R. UniKGQA: Unified Retrieval and Reasoning for Solving Multi-hop Question Answering Over Knowledge Graph. In The Eleventh International Conference on Learning Representations.

$3$ Mavromatis, C., & Karypis, G. (2022, December). ReaRev: Adaptive Reasoning for Question Answering over Knowledge Graphs. In Findings of the Association for Computational Linguistics: EMNLP 2022 (pp. 2447-2458).

Weakness3: Limited Datasets

Your feedback on the number of evaluated datasets is appreciated. To further demonstrate our method’s efficacy across a broader range of benchmarks and strengthen its contributions, we extend our zero-shot experiments to additional datasets: FreebaseQA $4$ . The results are presented below. The FreebaseQA is another question-answering dataset based on Freebase knowledge graphs. From the results, we can observe that GCR achieves significant improvements in FreebaseQA, demonstrating its generalizability and transferability.

Zero-shot transferability to other KGQA datasets.

$4$ K. Jiang, D. Wu and H. Jiang, "FreebaseQA: A New Factoid QA Data Set Matching Trivia-Style Question-Answer Pairs with Freebase," Proc. of North American Chapter of the Association for Computational Linguistics (NAACL), June 2019.

As the KG-Trie is independently constructed for each entity, it can be easily scaled with parallel processing. We provide the total running time of constructing 2-hop KG-Trie of all question entities in WebQSP dataset to show the improvement of parallel processing. It shows that the efficiency can be greatly improved with parallel processing. This parallel nature enables it to be executed on distributed computing systems such as Hadoop and Spark in real-world applications. More strategies to further improve efficiency and support real-world billion-scale KGs can be found in Appendix B.3 and B.4 of the revision.

Total running time and improvement under different processing threads.