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

We sincerely appreciate your positive and constructive review of our paper. Your feedback is invaluable in helping us refine and clarify our work. Below, we address your comments and questions in detail.

Efficiency of KG-Trie Construction and Practical time costs of the KG-Trie construction

We appreciate your emphasis on the efficiency of the KG-Trie construction process. In our current implementation, we optimize KG-Trie construction by leveraging efficient graph traversal techniques and parallelized batch processing. To provide a concrete perspective, we conducted additional experiments measuring the construction time on real-word KG (Freebase) in Appendix B.2, where the average time for KG-Trie construction is only 0.0133s.

We also present further optimizations to handle industrial-scale KGs by incorporating graph retrieval techniques to reduce the size of KG for Trie construction (Appendix B.3 and Figure 6). The breakdown of time consumption in Table 9 also shows the efficiency of the KG-Trie construction when combined with graph retrieval techniques (0.2838s).

Future work could explore better trie structures or hierarchical indexing to improve efficiency on industrial-scale KGs.

Adaptability to Missing Entities and Questionable Reasoning Paths

Thank you for raising this important concern. Our method is designed to be robust against incomplete KGs in two folds:

Exploring Alternative Paths
When the entities are missing, the GCR can explore alternative paths to fulfill the reasoning. For example, for the question “What is the
nationality of Joe Biden?” One of the reasoning paths could be:
Joe Biden -> born_in -> Scranton -> city_of -> USA.
When the entity Scranton is missing and leading to the disconnection of the path, GCR could explore other paths like:
Joe Biden -> profession -> President -> work_in -> Washington D.C -> city_of -> USA.
This path can also be used to deduce the correct answer: USA. In implementation, we explore the top-10 paths for comprehensive reasoning.

Combining Internal Knowledge of Powerful General LLMs
Due to the noises and incompleteness of KGs, the generated reasoning paths might be unsatisfying. To address this, in the graph inductive reasoning (Section 4.4), we employ a powerful general LLM (e.g., GPT-4o-mini) to incorporate diverse paths for deliberate reasoning.

The powerful general LLM exhibits massive internal knowledge and strong inductive reasoning ability. Therefore, it could disregard the questionable paths and deduce final answers accurately.

We sincerely appreciate your positive and insightful review of our paper. Below, we address your comments and concerns point by point.

R1. Scalability of KG-Trie construction for billion-edge KGs.

Scalability is indeed a vital concern, especially for billion-edge KGs. In our current implementation, we optimize KG-Trie construction by leveraging efficient graph traversal techniques and parallelized batch processing. Detailed analysis can be found in Appendix B.2, where the average running time for KG-Trie construction is 0.0133s.

We also present further optimizations to handle industrial-scale KGs by incorporating graph retrieval techniques to reduce the size of KG for Trie construction (Appendix B.3 and Figure 6). The breakdown of time consumption in Table 9 also shows its efficiency of when combined with graph retrieval techniques (0.2838s)

Future work could explore better trie structures or hierarchical indexing to improve efficiency on industrial-scale KGs.

R2. Analysis of Path Diversity vs. Answer Correctness

We appreciate this suggestion and agree that path diversity plays a crucial role in reasoning quality. GCR first adopts the beam-search to generate top-K paths with KG-specialized LLM (Sec 4.3). Therefore, the path diversity would increase with the size of K. Then, we conduct graph inductive reasoning to incorporate diverse paths for deliberate reasoning with a powerful general LLM (Sec 4.4).

As shown in Figure 4, we analyze the impact of different beam sizes K for graph-constrained decoding on the performance of GCR. We observe that the hit and recall of GCR increase with the beam size. Because, with a larger beam size, the LLMs can explore more diverse paths and find the correct answers. However, a larger K would increase the decoding time and diverse paths might introduce noises. Thus, we select the K to 10 to balance between the exploration and exploitation of the reasoning paths.

R3. Impact of Longer Reasoning Paths (L > 3) on Performance

We agree that extending path length could potentially enhance performance on complex multi-hop queries. We evaluate the performance of GCR with L up to 4 in Section F.1. The results in Figure 7 show that the performance in WebQSP slightly drops when L > 2. This could be because the question in WebQSP only requires up to 2 hops to solve $1$ .

Admittedly, a larger L could improve the performance on complex questions that require longer hop reasoning but the trade-offs would be the size of the KG-Trie. As shown in Figure 7 at Appendix F.1, the size of the KG-Trie is increased from 0.5MB to 7.5MB as the L change from 1 to 4. This would lead to extra complexity for storage and reasoning.

$1$ LUO, LINHAO, et al. "Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning." ICLR 2024.

We sincerely appreciate your time and effort in reviewing our submission. Below, we address your specific concerns:

R1. Handling Filtering Conditions in Queries

GCR can solve this type of query by combining the power of both KG and powerful general LLM. GCR first constrains the reasoning process within the KG to obtain the relevant knowledge, such as the population of all the states in the US. Then, GCR leverages the general-purpose LLM to conduct inductive reasoning on the knowledge to solve queries that require numerical comparison.

R2. Discrepancy Between F1 Score and Hit@1

In experiments, we select top-K paths generated by KG-specialized LLM for answer generation, which might lead to some missing answers, causing a discrepancy between F1 and Hit@1. The results in Fig. 4 show that the recall of the answers increases as the K and reduces the discrepancy.

R3. Logical Coherence in KG Reasoning Paths

Thanks for bringing up this interesting point. Due to the lack of ground truth and a great number of paths, we utilize the LLMs to evaluate the logical coherence and semantic meanings of the generated paths. The prompt and evaluation result are shown below:

As an advanced reasoning evaluator, your task is to analyze whether the following reasoning path presents a **logically coherent connection from the question (subject entity) to the answer (target entity)**. You will assess whether each step in the path is valid and necessary, and whether the overall reasoning supports the final answer in a grounded and justified manner.

### Instructions:
1. Focus on whether the reasoning path makes logical sense from the question to the answer.
2. Check whether each relation contributes meaningfully and validly to reaching the final answer.
3. Penalize paths that make unjustified jumps, overly general connections, or weak associations.

### Rating Scale:
5 - Excellent: Every step is logically valid and contributes clearly toward the answer.  
4 - Good: Mostly coherent with minor assumptions or weak steps.  
3 - Moderate: Some steps are unclear, general, or weak, but the general direction is acceptable.  
2 - Poor: Contains major logical leaps or unclear connections.  
1 - Very Poor: Illogical or invalid path from question to answer.

### Output:
- Score: [1 to 5]  
- Explanation: [Brief explanation of the logical quality of the path from question to answer]

### Question:
{question}
### Answer:
{answer}
### Path:
{path}

The results show that GCR achieves an average 3.9 in evaluation score, which demonstrates the logical coherence of the generated paths. Moreover, the LLM-based evaluation can be further used for selecting meaningful paths for training. Some meaningful cases can be found in Table 5.

R4. Conflicts Between KG-Specialized LLM and KG Knowledge

We want to clarify that this difference only happens when no constraints are applied (GCR w/o constraint in Table 5), where LLMs purely rely on their internal knowledge for reasoning, which leads to hallucinations. This can be addressed by applying the KG-Trie constraints during reasoning (GCR) to ensure faithful and transparent LLM reasoning, which aligns with the motivation of our method.

R5. Soundness of BFS Shortest Paths in Training

We acknowledge that the shortest paths found via BFS may not always be the most semantically meaningful reasoning paths. However, due to the lack of golden reasoning paths, it would be a great choice to unsupervisedly obtain the paths for training. We will enhance path selection by incorporating LLMs for judging the semantics (as discussed in R3) to ensure that paths adhere to the logical coherence in the KG’s relationships.

R6. Necessity of LLM for Path Selection

As discussed Sec. 4.1, LLMs conduct reasoning by decoding reasoning step-by-step, which purely relies on their internal knowledge and leads to hallucinations. GCR adapts this reasoning behavior to KGs and decodes reasoning paths that are valid on KGs. This well aligns with the reasoning paradigm of LLMs and is faster than other methods adopting LLMs for path selection (e.g., ToG in Table 2).

R7. Edge Direction

We consider the direction of the relations during KG-Trie construction. Therefore, only US -> is_contained_by -> North America will be generated. The inverse relations can be added during KG construction.

R8. Word-level Tokenization

We adopt the token-level tokenizer of the original LLMs to avoid retraining it on new KGs. The entity and relations in any KG can be tokenized into tokens for KG-Trie construction. This ensures the transferability of GCR to unseen KGs (Table 6).