# Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
**Authors**: Linhao Luo, Zicheng Zhao, Gholamreza Haffari, Yuan-Fang Li, Chen Gong, Shirui Pan
Abstract
Large language models (LLMs) have demonstrated impressive reasoning abilities, but they still struggle with faithful reasoning due to knowledge gaps and hallucinations. To address these issues, knowledge graphs (KGs) have been utilized to enhance LLM reasoning through their structured knowledge. However, existing KG-enhanced methods, either retrieval-based or agent-based, encounter difficulties in accurately retrieving knowledge and efficiently traversing KGs at scale. In this work, we introduce graph-constrained reasoning (GCR), a novel framework that bridges structured knowledge in KGs with unstructured reasoning in LLMs. To eliminate hallucinations, GCR ensures faithful KG-grounded reasoning by integrating KG structure into the LLM decoding process through KG-Trie, a trie-based index that encodes KG reasoning paths. KG-Trie constrains the decoding process, allowing LLMs to directly reason on graphs and generate faithful reasoning paths grounded in KGs. Additionally, GCR leverages a lightweight KG-specialized LLM for graph-constrained reasoning alongside a powerful general LLM for inductive reasoning over multiple reasoning paths, resulting in accurate reasoning with zero reasoning hallucination. Extensive experiments on several KGQA benchmarks demonstrate that GCR achieves state-of-the-art performance and exhibits strong zero-shot generalizability to unseen KGs without additional training Code and data are available at: https://github.com/RManLuo/graph-constrained-reasoning.
Machine Learning, ICML
\doparttoc \faketableofcontents
1 Introduction
Large language models (LLMs) have shown impressive reasoning abilities in handling complex tasks (Qiao et al., 2023; Huang & Chang, 2023), marking a significant leap that bridges the gap between human and machine intelligence. However, LLMs still struggle with conducting faithful reasoning due to issues of lack of knowledge and hallucination (Huang et al., 2024; Wang et al., 2023). These issues result in factual errors and flawed reasoning processes (Nguyen et al., 2024), which greatly undermine the reliability of LLMs in real-world applications.
To address these issues, many studies utilize knowledge graphs (KGs), which encapsulate extensive factual information in a structured format, to improve the reasoning abilities of LLMs (Pan et al., 2024; Luo et al., 2024). Nevertheless, because of the unstructured nature of LLMs, directly applying them to reason on KGs is challenging.
Existing KG-enhanced LLM reasoning methods can be roughly categorized into two groups: retrieval-based and agent-based paradigms, as shown in Figure 2 (a) and (b). Retrieval-based methods (Li et al., 2023; Yang et al., 2024b; Dehghan et al., 2024) retrieve relevant facts from KGs with an external retriever and then feed them into the inputs of LLMs for reasoning. Agent-based methods (Sun et al., 2024; Zhu et al., 2024; Jiang et al., 2024) treat LLMs as agents that iteratively interact with KGs to find reasoning paths and answers.
<details>
<summary>x1.png Details</summary>
### Visual Description
\n
## Pie Chart: Reasoning Path Validity
### Overview
The image is a pie chart illustrating the distribution of reasoning path validity. It categorizes reasoning paths into three types: "Faithful Reasoning Path", "Invalid - Format Error", and "Invalid - Relation Error", and shows the percentage each category represents.
### Components/Axes
The chart consists of three segments, each representing a category. A legend is positioned in the top-left corner, associating colors with each category:
* **Faithful Reasoning Path:** Blue
* **Invalid - Format Error:** Pink
* **Invalid - Relation Error:** Peach/Light Orange
The chart displays percentages for each segment. There are no explicit axes, as it's a pie chart representing proportions of a whole.
### Detailed Analysis
The pie chart segments represent the following data:
* **Faithful Reasoning Path (Blue):** The largest segment, occupying approximately 67.0% of the pie.
* **Invalid - Format Error (Pink):** Represents 18.0% of the pie.
* **Invalid - Relation Error (Peach/Light Orange):** Represents 15.0% of the pie.
The segments are arranged clockwise, starting with the largest (Faithful Reasoning Path) at the top.
### Key Observations
The majority of reasoning paths (67.0%) are classified as "Faithful Reasoning Path". The remaining paths are almost evenly split between "Invalid - Format Error" (18.0%) and "Invalid - Relation Error" (15.0%). The "Faithful Reasoning Path" segment is significantly larger than the other two combined.
### Interpretation
The data suggests that while a substantial portion of reasoning paths are considered faithful, a significant number are invalid due to either format or relational errors. This could indicate issues in the data processing pipeline, the reasoning engine itself, or the quality of the input data. The relatively similar percentages of "Format Error" and "Relation Error" suggest that both aspects of reasoning validity require attention. The large proportion of "Faithful Reasoning Path" is positive, but the 33% of invalid paths warrants investigation to improve the overall reliability of the reasoning process. The chart provides a clear visual representation of the distribution of reasoning path validity, highlighting areas for potential improvement.
</details>
Figure 1: Analysis of reasoning errors in RoG (Luo et al., 2024).
Despite their success, retrieval-based methods require additional accurate retrievers, which may not generalize well to unseen questions or account for the graph structure (Mavromatis & Karypis, 2024). Conversely, agent-based methods necessitate multiple rounds of interaction between agents and KGs, leading to high computational costs and latency (Dehghan et al., 2024). Furthermore, existing works still suffer from serious hallucination issues (Agrawal et al., 2024). Sui et al. (2024) indicates that RoG (Luo et al., 2024), a leading KG-enhanced reasoning method, still experiences 33% hallucination errors during reasoning on KGs, as shown in Figure 1.
To this end, we introduce graph-constrained reasoning (GCR), a novel KG-guided reasoning paradigm that connects unstructured reasoning in LLMs with structured knowledge in KGs, seeking to eliminate hallucinations during reasoning on KGs and ensure faithful reasoning. Inspired by the concept that LLMs reason through decoding (Wei et al., 2022), we incorporate the KG structure into the LLM decoding process. This enables LLMs to directly reason on graphs by generating reliable reasoning paths grounded in KGs that lead to correct answers.
In GCR, we first convert KG into a structured index, KG-Trie, to facilitate efficient reasoning on KG using LLM. Trie is also known as the prefix tree (Wikipedia contributors, 2024) that compresses a set of strings, which can be used to restrict LLM output tokens to those starting with valid prefixes (De Cao et al., 2022; Xie et al., 2022). KG-Trie encodes the reasoning paths in KGs as formatted strings to constrain the decoding process of LLMs. Then, we propose graph-constrained decoding that employs a lightweight KG-specialized LLM to generate multiple KG-grounded reasoning paths and hypothesis answers. With the constraints from KG-Trie, we ensure faithful reasoning while leveraging the strong reasoning capabilities of LLMs to efficiently explore paths on KGs in constant time. Finally, we input multiple generated reasoning paths and hypothesis answers into a powerful general LLM to utilize its inductive reasoning ability to produce final answers. In this way, GCR combines the graph reasoning strength of KG-specialized LLMs and the inductive reasoning advantage in general LLMs to achieve faithful and accurate reasoning on KGs. The main contributions of this work are as follows:
- We propose a novel framework called graph-constrained reasoning (GCR) that bridges the gap between structured knowledge in KGs and unstructured reasoning in LLMs, allowing for efficient reasoning on KGs via LLM decoding.
- We combine the complementary strengths of a lightweight KG-specialized LLM with a powerful general LLM to enhance reasoning performance by leveraging their respective graph-based reasoning and inductive reasoning capabilities.
- We conduct extensive experiments on several KGQA reasoning benchmarks, demonstrating that GCR not only achieves state-of-the-art performance with zero hallucination, but also shows zero-shot generalizability for reasoning on unseen KGs without additional training.
2 Related Work
LLM reasoning. Many studies have been proposed to analyze and improve the reasoning ability of LLMs (Wei et al., 2022; Wang et al., 2024b; Yao et al., 2024). To elicit the reasoning ability of LLMs, Chain-of-thought (CoT) reasoning (Wei et al., 2022) prompts the model to generate a chain of reasoning steps in response to a question. Wang et al. (2024b) propose a self-consistency mechanism that generates multiple reasoning paths and selects the most consistent answer across them. The tree-of-thought (Yao et al., 2024) structures reasoning as a branching process, exploring multiple steps in a tree-like structure to find optimal solutions. Other studies focus on fine-tuning LLMs on various reasoning tasks to improve reasoning abilities (Yu et al., 2022; Hoffman et al., 2024). For instance, OpenAI (2024c) adopts reinforcement learning to train their most advanced LLMs called “OpenAI o1” to perform complex reasoning, which produces a long internal chain of thought before final answers.
KG-enhanced LLM reasoning. To mitigate the knowledge gap and hallucination issues in LLM reasoning, research incorporates KGs to enhance LLM reasoning (Pan et al., 2024). KD-CoT (Wang et al., 2023) retrieve facts from an external knowledge graph to guide the CoT performed by LLMs. RoG (Luo et al., 2024) proposes a planning-retrieval-reasoning framework that retrieves reasoning paths from KGs to guide LLMs conducting faithful reasoning. To capture graph structure, GNN-RAG (Mavromatis & Karypis, 2024) and GFM-RAG (Luo et al., 2025) adopt the graph neural network to effectively retrieve from KGs. Instead of retrieving, StructGPT (Jiang et al., 2023) and ToG (Sun et al., 2024) treat LLMs as agents to interact with KGs to find reasoning paths leading to the correct answers.
<details>
<summary>x2.png Details</summary>
### Visual Description
\n
## Diagram: Knowledge Graph-constrained LLM Reasoning
### Overview
The image presents a comparative diagram illustrating three different approaches to Large Language Model (LLM) reasoning: Retrieval-based, Agent-based, and a novel Knowledge Graph-constrained approach. The diagram visually breaks down the process of question answering in each method, highlighting the role of knowledge graphs and specialized LLMs. The diagram is divided into three main sections (a, b, and c), each representing a different reasoning approach.
### Components/Axes
The diagram consists of several key components:
* **Knowledge Graph:** Represented as interconnected nodes and edges, symbolizing a structured knowledge base.
* **General LLM:** A standard Large Language Model.
* **KG-specialized LLM:** An LLM specifically trained on knowledge graph data.
* **Question (Q):** The input query.
* **Answer (A):** The output response.
* **Knowledge Retriever:** A component that fetches relevant facts from the knowledge graph.
* **LLM Agent:** A component that orchestrates reasoning steps.
* **KG-Trie Construction:** A process for building a knowledge graph trie.
* **Graph-constrained Decoding:** A process for decoding information using the knowledge graph.
* **Reasoning Paths and Hypothesis Answers:** A section displaying reasoning paths and corresponding answers.
* **Inductive Reasoning:** A process for generating answers based on reasoning paths.
* **Time Steps (t=1, t=2, t=3):** Indicate the progression of reasoning steps.
### Detailed Analysis or Content Details
**(a) Retrieval-based LLM Reasoning:**
* A question (Q) is input into a General LLM.
* The General LLM interacts with a Knowledge Graph via a KG-specialized LLM.
* The KG-specialized LLM provides an answer (A).
**(b) Agent-based LLM Reasoning:**
* A question (Q) is input into an LLM Agent.
* The LLM Agent takes 'T Steps' to reason.
* The LLM Agent interacts with a Knowledge Graph, retrieving facts.
* The LLM Agent uses the retrieved facts to generate an answer (A).
* Example: Question: "Who is Sasha Obama?" Answer: "Mother_of_3 Michelle Obama". The Knowledge Graph shows "Founded_in" Barack Obama, "Ex-president" Barack Obama, "Born_in" Honolulu.
**(c) Ours: Knowledge Graph-constrained LLM Reasoning:**
* **KG-Trie Construction:** A Knowledge Graph is used to construct a KG-Trie. The graph includes nodes like "USA", "Ex-president", "George W. Bush", "Laura Bush", "Barack Obama", "Donald Trump", "Melania Trump", "Ivana Trump", "Washington D.C.", and relationships like "Spouse_of", "Marry_to", "Founded_in", "Capital".
* **Graph-constrained Decoding:** The KG-Trie is used to constrain the decoding process.
* **Inductive Reasoning:** A General LLM performs inductive reasoning based on the constrained decoding.
* **Question:** "Who is the spouse of the ex-president of USA?"
* **Reasoning Paths and Hypothesis Answers:**
* Path 1: USA → Ex-president → George W. Bush. Answer: Laura Bush.
* Path 2: USA → Ex-president → Barack Obama. Answer: Michelle Obama.
* Path 3: USA → Ex-president → Donald Trump. Answer: Melania Trump.
* **Final Answer:** Based on the paths, the answers are: Laura Bush, Michelle Obama, Melania Trump.
### Key Observations
* The Knowledge Graph-constrained approach (c) explicitly incorporates the knowledge graph into the reasoning process at multiple stages (trie construction and decoding).
* The Agent-based approach (b) uses the knowledge graph as a source of retrieved facts, but the reasoning is primarily driven by the LLM Agent.
* The Retrieval-based approach (a) is the simplest, relying on a KG-specialized LLM to directly provide answers.
* The diagram highlights the importance of structured knowledge (Knowledge Graph) in enhancing LLM reasoning capabilities.
* The example question in (c) demonstrates how the knowledge graph enables the LLM to consider multiple possible answers based on different reasoning paths.
### Interpretation
The diagram illustrates a progression in LLM reasoning techniques, moving from simple retrieval to more sophisticated graph-constrained approaches. The core idea is that integrating structured knowledge from a knowledge graph can significantly improve the accuracy, reliability, and explainability of LLM responses. The Knowledge Graph-constrained approach (c) appears to be the most promising, as it leverages the knowledge graph not only as a data source but also as a constraint on the reasoning process itself. This constraint helps to focus the LLM's attention on relevant information and avoid generating incorrect or nonsensical answers. The inclusion of reasoning paths and hypothesis answers provides transparency into the LLM's decision-making process, which is crucial for building trust and understanding. The diagram suggests that future LLM research should focus on developing more effective methods for integrating knowledge graphs into the reasoning pipeline. The use of KG-Tries is a novel approach to encoding the knowledge graph for efficient reasoning.
</details>
Figure 2: Illustration of existing KG-enhanced LLM reasoning paradigms and proposed graph-constrained reasoning (GCR), which consists of three main components: 1) Knowledge Graph Trie Construction: building a structural index of KG to guide LLM reasoning, 2) Graph-constrained Decoding: generating KG-grounded paths and hypothesis answers using LLMs, and 3) Graph Inductive Reasoning: reasoning over multiple paths and hypotheses to derive final answers.
3 Preliminary
Knowledge Graphs (KGs) represent a wealth of factual knowledge as a collection of triples: ${\mathcal{G}}=\{(e,r,e^{\prime})∈{\mathcal{E}}×{\mathcal{R}}×{%
\mathcal{E}}\}$ , where ${\mathcal{E}}$ and ${\mathcal{R}}$ denote the set of entities and relations, respectively.
Reasoning Paths are sequences of consecutive triples in KGs: ${\bm{w}}_{\bm{z}}=e_{0}\xrightarrow{r_{1}}e_{1}\xrightarrow{r_{2}}...%
\xrightarrow{r_{l}}e_{l}$ , where $∀(e_{i-1},r_{i},e_{i})∈{\mathcal{G}}$ . The paths reveal the connections between knowledge that potentially facilitate reasoning. For example, the reasoning path: ${\bm{w}}_{\bm{z}}=\text{Alice}\xrightarrow{\texttt{marry\_to}}\text{Bob}%
\xrightarrow{\texttt{father\_of}}\text{Charlie}$ indicates that “Alice” is married to “Bob” and “Bob” is the father of “Charlie”. Therefore, “Alice” could be reasoned to be the mother of “Charlie”.
Knowledge Graph Question Answering (KGQA) is a representative reasoning task with the assistance of KGs. Given a natural language question $q$ and a KG ${\mathcal{G}}$ , the task aims to design a function $f$ to reason answers $a∈{\mathcal{A}}$ based on knowledge from ${\mathcal{G}}$ , i.e., $a=f(q,{\mathcal{G}})$ . The entities $e_{q}∈{\mathcal{E}}_{q}$ mentioned in $q$ are linked to the corresponding entities in ${\mathcal{G}}$ , i.e., ${\mathcal{E}}_{q}⊂eq{\mathcal{E}}$ .
KG-constrained Zero-hallucination. As facts in KGs are usually verified, making them a reliable source for assessing the faithfulness of LLM reasoning (Nguyen et al., 2024). In this paper, we define KG-constrained zero hallucinations as the LLM generated reasoning paths can be fully grounded within KGs, ensuring the alignment of reasoning process with real-world facts.
4 Approach
4.1 From Chain-of-Thought Reasoning to Graph-constrained Reasoning
Chain-of-Thought Reasoning (CoT) (Wei et al., 2022) has been widely adopted to enhance the reasoning ability of LLMs by autoregressively generating a series of reasoning steps leading to the answer. Specifically, given a question $q$ , CoT models the joint probability of the answer $a$ and reasoning steps ${\bm{z}}$ as
$$
\displaystyle P(a|q) \displaystyle=\sum_{{\bm{z}}}P_{\theta}(a|{\bm{z}},q)P_{\theta}({\bm{z}}|q) \displaystyle=\sum_{{\bm{z}}}P_{\theta}(a|q,{\bm{z}})\prod_{i=1}^{|{\bm{z}}|}P%
_{\theta}(z_{i}|q,z_{1:i-1}), \tag{1}
$$
where $q$ denotes the input question, $a$ denotes the final answer, $\theta$ denotes the parameters of LLMs, and $z_{i}$ denotes the $i$ -th step of the reasoning process ${\bm{z}}$ . To further enhance the reasoning ability, many previous works focus on improving the reasoning process $P_{\theta}({\bm{z}}|q)$ by exploring and aggregating multiple reasoning processes (Wang et al., 2024b; Yao et al., 2024).
Despite the effectiveness, a major issue remains the faithfulness of the reasoning process generated by LLMs (Huang et al., 2024). The reasoning is represented as a sequence of tokens decoded step-by-step, which can accumulate errors and result in hallucinated reasoning paths and answers (Nguyen et al., 2024). To address these issues, we utilize knowledge graphs (KGs) to guide LLMs toward faithful reasoning.
KG-enhanced Reasoning utilizes the structured knowledge in KGs to improve the reasoning of LLMs (Luo et al., 2024; Sun et al., 2024), which can generally be expressed as finding a reasoning path ${\bm{w}}_{\bm{z}}$ on KGs that connects the entities mentioned in the question and the answer. This can be formulated as
$$
P(a|q,{\mathcal{G}})=\sum_{{\bm{w}}_{\bm{z}}}P_{\phi}(a|q,{\bm{w}}_{\bm{z}})P_%
{\phi}({\bm{w}}_{\bm{z}}|q,{\mathcal{G}}), \tag{2}
$$
where $P_{\phi}({\bm{w}}_{\bm{z}}|q,{\mathcal{G}})$ denotes the probability of discovering a reasoning path ${\bm{w}}_{\bm{z}}$ on KGs ${\mathcal{G}}$ given the question $q$ by a function parameterized by $\phi$ . To acquire reasoning paths for reasoning, most prior studies follow the retrieval-based (Li et al., 2023) or agent-based paradigm (Sun et al., 2024), as shown in Figure 2 (a) and (b), respectively. Nevertheless, retrieval-based methods rely on precise additional retrievers, while agent-based methods are computationally intensive and lead to high latency. To address these issues, we propose a novel graph-constrained reasoning paradigm (GCR).
Graph-constrained Reasoning (GCR) directly incorporates KGs into the decoding process of LLMs to achieve faithful reasoning. The overall framework of GCR is illustrated in Figure 2 (c), which consists of three main components: 1) Knowledge Graph Trie Construction, 2) Graph-constrained Decoding, and 3) Graph Inductive Reasoning.
4.2 Knowledge Graph Trie Construction
Knowledge graphs (KGs) store abundant knowledge in a structured format. However, large language models (LLMs) struggle to efficiently access and reason on KGs due to their unstructured nature. To address this issue, we propose to convert KGs into knowledge graph Tries (KG-Tries), which serve as a structured index of KGs to facilitate efficient reasoning on graphs using LLMs.
A Trie (a.k.a. prefix tree) (Wikipedia contributors, 2024; Fredkin, 1960) is a tree-like data structure that stores a dynamic set of strings, where each node represents a common prefix of its children. Tries can be used to restrict LLM output tokens to those starting with valid prefixes (De Cao et al., 2022; Xie et al., 2022; Chen et al., 2022). The tree structure of Trie is an ideal choice for encoding the reasoning paths in KGs for LLMs to efficiently traverse.
Given a KG ${\mathcal{G}}$ and a question $q$ , we first retrieve paths ${\mathcal{W}}_{{\bm{z}}}$ within $L$ hops starting from entities mentioned in the question $e_{q}∈{\mathcal{E}}_{q}$ . We adopt the breadth-first search (BFS) algorithm to retrieve reasoning paths, but it can be replaced with other efficient graph-traversing algorithms, such as random walk (Xia et al., 2019). The retrieved paths are formatted as sentences using the template shown in Figure 9. The formatted sentences are then split into tokens by the tokenizer of LLM and stored as a KG-Trie ${\mathcal{C}}_{{\mathcal{G}}}$ . The overall process can be formulated as:
$$
\displaystyle{\mathcal{W}}_{{\bm{z}}}=\text{BFS}({\mathcal{G}},{\mathcal{E}}_{%
q},L), \displaystyle{\mathcal{T}}_{\bm{z}}=\text{Tokenizer}({\mathcal{W}}_{{\bm{z}}}), \displaystyle{\mathcal{C}}_{{\mathcal{G}}}=\text{Trie}({\mathcal{T}}_{\bm{z}}), \tag{3}
$$
where ${\mathcal{E}}_{q}$ denotes all entities mentioned in the question, $L$ denotes the maximum hops of paths, and ${\mathcal{T}}_{\bm{z}}$ denotes the tokens of reasoning paths. The KG-Trie ${\mathcal{C}}_{{\mathcal{G}}}$ is used as a constraint to guide the LLM decoding process.
By constructing KG-Trie for each question entity, we can enable efficient traversal of reasoning paths in constant time ( $O(|{\mathcal{W}}_{\bm{z}}|)$ ) without costly graph traversal (Sun et al., 2024). Moreover, KG-Trie can be pre-constructed offline and loaded during reasoning for fast inference, or it can be built on-demand to reduce pre-processing time. Detailed discussions on construction efficiency and potential solutions for further improvements to scale into real-world applications is available in Appendix B. This significantly reduces the computational cost and latency of reasoning on KGs, making it feasible for real-time applications.
4.3 Graph-constrained Decoding
Large language models (LLMs) have strong reasoning capabilities but still suffer from severe hallucination issues, which undermines the trustworthiness of the reasoning process. To tackle this issue, we propose graph-constrained decoding, which unifies the reasoning ability of LLMs with the structured knowledge in KGs to generate faithful KG-grounded reasoning paths leading to answers.
Given a question $q$ , we design an instruction prompt to harness the reasoning ability of LLMs to generate reasoning paths ${\bm{w}}_{\bm{z}}$ and hypothesis answers $a$ . To eliminate the hallucination during reasoning on KGs, we adopt the KG-Trie ${\mathcal{C}}_{{\mathcal{G}}}$ as constraints to guide the decoding process of LLMs and only generate reasoning paths that are valid in KGs, formulated as:
where $w_{z_{i}}$ denotes the $i$ -th token of the reasoning path ${\bm{w}}_{\bm{z}}$ , $P_{\phi}$ denotes the token probabilities predicted by the LLM with parameters $\phi$ , and ${\mathcal{C}}_{{\mathcal{G}}}(w_{z_{i}}|w_{z_{1:i-1}})$ denotes the constraint function that checks whether the generated tokens $w_{z_{1:i}}$ is a valid prefix of the reasoning path using KG-Trie. After a valid reasoning path is generated, we switch back to the regular decoding process to generate a hypothesis answer conditioned on the path.
To further enhance KG reasoning ability, we fine-tune a lightweight KG-specialized LLM with parameters $\phi$ on the graph-constrained decoding task. Specifically, given a question $q$ , the LLM is optimized to generate relevant reasoning paths ${\bm{w}}_{\bm{z}}$ that are helpful for answering the question, then provide a hypothesis answer $a$ based on it, which can be formulated as:
where $a_{i}$ and $w_{z_{j}}$ denote the $i$ -th token of the answer $a$ and the $j$ -th token of the reasoning path ${\bm{w}}_{\bm{z}}$ , respectively.
The training data $(q,{\bm{w}}_{\bm{z}},a)∈\mathcal{D_{\mathcal{G}}}$ consists of question-answer pairs and reasoning paths generated from KGs. We use the shortest paths connecting the entities in the question and answer as the reasoning path ${\bm{w}}_{\bm{z}}$ for training, where details can be found in Appendix C. An example of graph-constrained decoding is illustrated in Figure 3, where <PATH> and </PATH> are special tokens to control the start and end of graph-constrained decoding. Experiment results in Section 5.2 show that even a lightweight KG-specialized LLM (0.5B) can achieve satisfactory performance in KG reasoning.
The graph-constrained decoding method differs from retrieval-based methods by integrating a pre-constructed KG-Trie into the decoding process of LLMs. This not only reduces input tokens, but also bridges the gap between unstructured reasoning in LLMs and structured knowledge in KGs, allowing for efficient reasoning on KGs regardless of its scale, which results in faithful reasoning leading to answers. Additionally, experimental results in Section 5.4 demonstrate that KG-Trie can integrate with new KGs on the fly, showcasing its zero-shot generalizability for reasoning on unseen KGs without further training.
============== Prompt Input ============== Please generate some reasoning paths in the KG starting from the topic entities to answer the question. # Question: what is the name of justin bieber brother? ============== LLM Output ============== # Reasoning Path: <PATH> Justin Bieber $→$ people.person.parents $→$ Jeremy Bieber $→$ people.person.children $→$ Jaxon Bieber </PATH> # Answer: Jaxon Bieber
Figure 3: An example of the graph-constrained decoding. Detailed prompts can be found in Figure 10.
4.4 Graph Inductive Reasoning
Graph-constrained decoding harnesses the reasoning ability of a KG-specialized LLM to generate a faithful reasoning path and a hypothesis answer. However, complex reasoning tasks typically admit multiple reasoning paths that lead to correct answers (Stanovich et al., 2000). Incorporating diverse reasoning paths would be beneficial for deliberate thinking and reasoning (Evans, 2010; Wang et al., 2024b). To this end, we propose to input multiple reasoning paths and hypothesis answers generated by the KG-specialized LLM into a powerful general LLM to leverage its inductive reasoning ability to produce final answers.
The graph-constrained decoding seamlessly integrates into the decoding process of LLMs, allowing it to be paired with various LLM generation strategies like beam-search (Federico et al., 1995) to take advantage of the GPU parallel computation. Thus, given a question, we adopt graph-constrained decoding to simultaneously generate $K$ reasoning paths and hypothesis answers with beam search in a single LLM call, which are then inputted into a general LLM to derive final answers. The overall process can be formulated as:
$$
\displaystyle{\mathcal{Z}}_{K}=\{a^{k},{\bm{w}}^{k}_{{\bm{z}}}\}_{k=1}^{K}=%
\mathop{\mathrm{arg\,top}\text{-}K}P_{\phi}(a,{\bm{w}}_{\bm{z}}|q), \displaystyle P_{\theta}({\mathcal{A}}|q,{\mathcal{Z}}_{K})\simeq\prod_{k=1}^{%
K}P_{\theta}({\mathcal{A}}|q,a^{k},{\bm{w}}^{k}_{{\bm{z}}}), \tag{9}
$$
where $\theta$ denotes the parameters of the general LLM, ${\mathcal{Z}}_{K}$ denotes the set of top- $K$ reasoning paths and hypothesis answers, and ${\mathcal{A}}$ denotes the final answers.
We follow the FiD framework (Izacard & Grave, 2021; Singh et al., 2021) to incorporate multiple reasoning paths and hypothesis answers to conduct inductive reasoning within one LLM call, i.e., $P_{\theta}({\mathcal{A}}|q,{\mathcal{Z}}_{K})$ , where detailed prompts can be found in Figure 11. The general LLM can be any powerful LLM, such as ChatGPT (OpenAI, 2022), or Llama-3 (Meta, 2024), which can effectively leverage their internal reasoning ability to reason over multiple reasoning paths to produce final answers without additional fine-tuning.
5 Experiment
In our experiments, we aim to answer the following research questions: RQ1: Can GCR achieve state-of-the-art reasoning performance with balances between efficiency and effectiveness? RQ2: Can GCR eliminate hallucinations and conduct faithful reasoning? RQ3: Can GCR generalize to unseen KGs on the fly?
5.1 Experiment Setups
Table 1: Performance comparison with different baselines on the two KGQA datasets.
| Types | Methods | WebQSP | CWQ | | |
| --- | --- | --- | --- | --- | --- |
| Hit | F1 | Hit | F1 | | |
| LLM Reasoning | Qwen2-0.5B (Yang et al., 2024a) | 26.2 | 17.2 | 12.5 | 11.0 |
| Qwen2-1.5B (Yang et al., 2024a) | 41.3 | 28.0 | 18.5 | 15.7 | |
| Qwen2-7B (Yang et al., 2024a) | 50.8 | 35.5 | 25.3 | 21.6 | |
| Llama-2-7B (Touvron et al., 2023) | 56.4 | 36.5 | 28.4 | 21.4 | |
| Llama-3.1-8B (Meta, 2024) | 55.5 | 34.8 | 28.1 | 22.4 | |
| GPT-4o-mini (OpenAI, 2024a) | 63.8 | 40.5 | 63.8 | 40.5 | |
| ChatGPT (OpenAI, 2022) | 59.3 | 43.5 | 34.7 | 30.2 | |
| ChatGPT+Few-shot (Brown et al., 2020) | 68.5 | 38.1 | 38.5 | 28.0 | |
| ChatGPT+CoT (Wei et al., 2022) | 73.5 | 38.5 | 47.5 | 31.0 | |
| ChatGPT+Self-Consistency (Wang et al., 2024b) | 83.5 | 63.4 | 56.0 | 48.1 | |
| Graph Reasoning | GraftNet (Sun et al., 2018) | 66.7 | 62.4 | 36.8 | 32.7 |
| NSM (He et al., 2021) | 68.7 | 62.8 | 47.6 | 42.4 | |
| SR+NSM (Zhang et al., 2022) | 68.9 | 64.1 | 50.2 | 47.1 | |
| ReaRev (Mavromatis & Karypis, 2022) | 76.4 | 70.9 | 52.9 | 47.8 | |
| UniKGQA (Jiang et al., 2022) | 77.2 | 72.2 | 51.2 | 49.1 | |
| KG+LLM | KD-CoT (Wang et al., 2023) | 68.6 | 52.5 | 55.7 | - |
| EWEK-QA (Dehghan et al., 2024) | 71.3 | - | 52.5 | - | |
| ToG (ChatGPT) (Sun et al., 2024) | 76.2 | - | 57.6 | - | |
| ToG (GPT-4) (Sun et al., 2024) | 82.6 | - | 68.5 | - | |
| EffiQA (Dong et al., 2024) | 82.9 | - | 69.5 | | |
| RoG (Llama-2-7B) (Luo et al., 2024) | 85.7 | 70.8 | 62.6 | 56.2 | |
| GNN-RAG (Mavromatis & Karypis, 2024) | 85.7 | 71.3 | 66.8 | 59.4 | |
| GNN-RAG+RA (Mavromatis & Karypis, 2024) | 90.7 | 73.5 | 68.7 | 60.4 | |
| GCR (Llama-3.1-8B + ChatGPT) | 92.6 | 73.2 | 72.7 | 60.9 | |
| GCR (Llama-3.1-8B + GPT-4o-mini) | 92.2 | 74.1 | 75.8 | 61.7 | |
Datasets. Following previous research (Luo et al., 2024; Sun et al., 2024), we first evaluate the reasoning ability of GCR on two benchmark KGQA datasets: WebQuestionSP (WebQSP) (Yih et al., 2016) and Complex WebQuestions (CWQ) (Talmor & Berant, 2018). Freebase (Bollacker et al., 2008) is adopted as the knowledge graph for both datasets. To further evaluate the generalizability of GCR, we conduct zero-shot transfer experiments on three new KGQA datasets: FreebaseQA (Jiang et al., 2019), CSQA (Talmor et al., 2019) and MedQA (Jin et al., 2021). FreebaseQA adopts the same Freebase KG. For CSQA, we use ConceptNet (Speer et al., 2017) as the KG, while for MedQA, we use a medical KG constructed from the Unified Medical Language System (Yasunaga et al., 2021). The details of the datasets are described in Appendix C.
Baselines. We compare GCR with the 22 baselines grouped into three categories: 1) LLM reasoning methods, 2) graph reasoning methods, and 3) KG-enhanced LLM reasoning methods. The detailed baselines are listed in Appendix D.
Evaluation Metrics. We adopt Hit and F1 as the evaluation metrics following previous works (Luo et al., 2024; Sun et al., 2024) on WebQSP and CWQ. Hit checks whether any correct answer exists in the generated predictions, while F1 considers the coverage of all answers by balancing the precision and recall of predictions. Because CSQA and MedQA are multiple-choice QA datasets, we adopt accuracy as the evaluation metric.
Implementations. For GCR, we use the KG-Trie to index all the reasoning paths within 2 hops starting from question entities. For the LLMs, we use a fine-tuned Llama-3-8B (Meta, 2024) as the KG-specialized LLM. We generate top-10 reasoning paths and hypothesis answers from graph-constrained decoding. We adopt the advanced ChatGPT (OpenAI, 2022) and GPT-4o-mini (OpenAI, 2024a) as the general LLMs for inductive reasoning. The detailed hyperparameters and experiment settings are described in Appendix E.
Table 2: Efficiency and performance comparison of different methods on WebQSP.
| Types | Methods | Hit | Avg. Runtime (s) | Avg. # LLM Calls | Avg. # LLM Tokens |
| --- | --- | --- | --- | --- | --- |
| Retrieval-based | S-Bert | 66.9 | 0.87 | 1 | 293 |
| BGE | 72.7 | 1.05 | 1 | 357 | |
| OpenAI-Emb. | 79.0 | 1.77 | 1 | 330 | |
| GNN-RAG | 85.7 | 1.52 | 1 | 414 | |
| RoG | 85.7 | 2.60 | 2 | 521 | |
| Agent-based | ToG | 75.1 | 16.14 | 11.6 | 7,069 |
| EffiQA | 82.9 | - | 7.3 | - | |
| Ours | GCR | 92.6 | 3.60 | 2 | 231 |
5.2 RQ1: Reasoning Performance and Efficiency
Main Results. In this section, we compare GCR with other baselines on KGQA benchmarks to evaluate the reasoning performance. From the results shown in Table 1, GCR achieves the best performance on both datasets, outperforming the second-best by 2.1% and 9.1% in terms of Hit on WebQSP and CWQ, respectively. The results demonstrate that GCR can effectively leverage KGs to enhance LLMs and achieve state-of-the-art reasoning performance.
Among the LLM reasoning methods, ChatGPT with self-consistency prompts demonstrates the best performance, which indicates the powerful reasoning ability inherent in LLMs. However, their performances are still limited by the model size and complex reasoning required over structured data. Graph reasoning methods, such as ReaRev, achieve competitive performance on WebQSP by explicitly modeling the graph structure. But they struggle to generalize across different datasets and underperform on CWQ. In KG+LLM methods, both agent-based methods (e.g., ToG, EffiQA) and retrieval-based methods (e.g., RoG, GNN-RAG) achieve the second-best performance. Nevertheless, they still suffer from inefficiency and reasoning hallucinations which limit their performance. In contrast, GCR effectively eliminates hallucinations and conducts faithful reasoning by leveraging the structured KG index and graph-constrained decoding.
Efficiency Analysis. To show the efficiency of GCR, we compare the average runtime, number of LLM calls, and number of input tokens with retrieval-based and agent-based methods in Table 2. For retrieval-based methods, we compare with dense retrievers (e.g., S-Bert (Reimers & Gurevych, 2019), BGE (Zhang et al., 2023), OpenAI-Emb. (OpenAI, 2024b)) and graph-based retrievers (e.g., GNN-RAG (Mavromatis & Karypis, 2024), RoG (Luo et al., 2024)), which retrieve reasoning paths from KGs and feed them into LLMs for reasoning answers. For agent-based methods, we compare with ToG (Sun et al., 2024) and EffiQA Since there is no available code for EffiQA, we directly copy the results from the original paper. (Dong et al., 2024), which heuristically search on KGs for answers. The detailed settings are described in Appendix E.
Dense retrievers are most efficient in terms of runtime and LLM calls as they convert all paths into sentences and encode them as embeddings in advance. However, they sacrifice their accuracy in retrieving as they are not designed to encode graph structure. Graph-based retrievers and agent-based methods achieve better performance by considering graph structure; however, they require more time and LLM calls. Specifically, the retrieved graph is fed as inputs to LLMs, which leads to a large number of input tokens. Agent-based methods, like ToG, require more LLM calls and input tokens as the question difficulty increases due to their iterative reasoning process. In contrast, GCR achieves the best performance with a reasonable runtime and number of LLM calls. With the help of KG-Trie, GCR explores multiple reasoning paths at the same time during the graph-constrained decoding, which does not involve additional LLM calls or input tokens and benefits from the parallel GPU computation with low latency. More efficiency analysis under different beam sizes used for graph-constrained decoding can be found in parameter analysis.
Table 3: Ablation studies of GCR on two KGQA datasets.
| Variants | WebQSP | CWQ | | | | |
| --- | --- | --- | --- | --- | --- | --- |
| F1 | Precision | Recall | F1 | Precision | Recall | |
| GCR (Llama-3.1-8B + ChatGPT) | 73.2 | 80.0 | 76.9 | 60.9 | 61.1 | 66.6 |
| GCR $w/o$ KG-specialized LLM | 52.9 | 66.3 | 50.2 | 37.5 | 40.8 | 37.9 |
| GCR $w/o$ General LLM | 57.0 | 58.0 | 70.1 | 39.4 | 32.8 | 64.3 |
Ablation Study. We first conduct an ablation study to analyze the effectiveness of the KG-specialized LLM and general LLM in GCR. As shown in Table 3, the full GCR achieves the best performance on both datasets. By removing the KG-specialized LLM, we feed all 2-hop reasoning paths into the general LLM. This results in a significant performance drop, indicating its importance in utilizing reasoning ability to find relevant paths on KGs for reasoning. On the other hand, removing the general LLM and relying solely on answers predicted by KG-specialized LLM leads to a noticeable decrease in precision, due to noises in its predictions. This highlighting the necessity of the general LLM for conducting inductive reasoning over multiple paths to derive final answers.
Different LLMs. We further analyze LLMs used for KG-specialized and general LLMs in Table 4. For KG-specialized LLMs, we directly plug the KG-Trie into different LLMs to conduct graph-constrained decoding and use ChatGPT as the general LLM for final reasoning. For general LLMs, we adopt the same reasoning paths generated by KG-specialized LLMs to different LLMs to produce final answers. For zero-shot and few-shot learning, we adopt the original LLMs without fine-tuning, whose prompt templates can be found in Figures 10 and 12.
Table 4: Comparison of different LLMs used in GCR.
| Components | Learning Types | Variants | Hit | F1 |
| --- | --- | --- | --- | --- |
| KG-specialized LLM | Zero-shot | Llama-3.1-8B | 28.25 | 10.32 |
| Llama-3.1-70B | 38.53 | 12.53 | | |
| Few-shot | Llama-3.1-8B | 33.24 | 11.19 | |
| Llama-3.1-70B | 41.13 | 13.14 | | |
| Fine-tuned | Qwen2-0.5B | 87.48 | 60.03 | |
| Qwen2-1.5B | 89.21 | 62.97 | | |
| Qwen2-7B | 92.31 | 72.74 | | |
| Llama-2-7B | 92.55 | 73.23 | | |
| Llama-3.1-8B | 92.74 | 73.14 | | |
| General LLM | Zero-shot | Qwen-2-7B | 86.32 | 67.59 |
| Llama-3.1-8B | 90.24 | 71.19 | | |
| Llama-3.1-70B | 89.85 | 71.47 | | |
| ChatGPT | 92.55 | 73.23 | | |
| GPT-4o-mini | 92.23 | 74.05 | | |
Results in Table 4 show that a lightweight LLM (0.5B) can outperform a large one (70B) after fine-tuning, indicating the effectiveness of fine-tuning in enhancing the ability of LLMs and make them specialized for KG reasoning. However, the larger LLMs (e.g., 7B and 8B) still perform better than smaller ones, highlighting the importance of model capacity in searching relevant reasoning paths on KGs. Similar trends are observed in general LLMs where larger models (e.g., GPT-4o-mini and ChatGPT) outperform smaller ones (e.g., Qwen-2-7B and Llama-3.1-8B), showcasing their stronger inductive reasoning abilities. This further emphasizes the need of paring powerful general LLMs with lightweight KG-specialized LLMs to achieve better reasoning driven by both of them.
<details>
<summary>x3.png Details</summary>
### Visual Description
\n
## Line Chart: Performance Metrics vs. Decoding Beam Size
### Overview
This chart displays the relationship between Graph-constrained decoding beam size (K) and several performance metrics: Generation Time, Hit, Precision, Recall, and F1 score. The chart uses a dual y-axis, with Generation Time on the left and Answer Coverage (representing Precision, Recall, and F1) on the right.
### Components/Axes
* **X-axis:** Graph-constrained decoding beam size K, with markers at 1, 3, 5, 10, and 20.
* **Y-axis (left):** Generation Time (s), ranging from 0 to 8.
* **Y-axis (right):** Answer Coverage (%), ranging from 40 to 90.
* **Legend:** Located in the top-right corner.
* Green: Generation Time (s)
* Red: Hit
* Orange: Precision
* Blue dashed: Recall
* Blue triangle: F1
### Detailed Analysis
* **Generation Time (Green Bars):** The Generation Time increases with increasing beam size.
* K=1: Approximately 0.2 seconds.
* K=3: Approximately 1.8 seconds.
* K=5: Approximately 2.5 seconds.
* K=10: Approximately 3.7 seconds.
* K=20: Approximately 4.2 seconds.
* **Hit (Red Line):** The Hit rate increases rapidly from K=1 to K=3, then plateaus.
* K=1: Approximately 25%.
* K=3: Approximately 70%.
* K=5: Approximately 74%.
* K=10: Approximately 76%.
* K=20: Approximately 78%.
* **Precision (Orange Line):** The Precision increases from K=1 to K=3, then decreases slightly.
* K=1: Approximately 45%.
* K=3: Approximately 72%.
* K=5: Approximately 68%.
* K=10: Approximately 65%.
* K=20: Approximately 63%.
* **Recall (Blue Dashed Line):** The Recall increases steadily with increasing beam size.
* K=1: Approximately 40%.
* K=3: Approximately 55%.
* K=5: Approximately 60%.
* K=10: Approximately 75%.
* K=20: Approximately 78%.
* **F1 (Blue Triangle Line):** The F1 score increases from K=1 to K=3, then plateaus.
* K=1: Approximately 0.
* K=3: Approximately 50%.
* K=5: Approximately 55%.
* K=10: Approximately 68%.
* K=20: Approximately 72%.
### Key Observations
* The Generation Time increases linearly with beam size, suggesting a computational cost associated with larger beam sizes.
* The Hit rate shows diminishing returns after K=3, indicating that increasing the beam size beyond this point provides minimal improvement in hit rate.
* Precision peaks at K=3 and then declines, while Recall continues to increase. This suggests a trade-off between precision and recall as the beam size increases.
* The F1 score, which balances precision and recall, also plateaus after K=3, similar to the Hit rate.
### Interpretation
The data suggests that a beam size of K=3 represents a sweet spot for this graph-constrained decoding task. Increasing the beam size beyond K=3 results in increased Generation Time without significant improvements in Hit rate, F1 score, or overall Answer Coverage. The trade-off between Precision and Recall indicates that larger beam sizes may introduce more false positives (lower precision) while capturing more relevant answers (higher recall). The chart demonstrates the importance of optimizing the beam size to balance computational cost and performance metrics. The plateauing of the Hit, F1, and Precision metrics after K=3 suggests that other factors may become limiting as the beam size increases, such as the quality of the underlying graph or the decoding algorithm itself.
</details>
Figure 4: Parameter analysis of beam size $K$ .
Parameter Analysis. We first analyze the impact of different beam sizes $K$ for graph-constrained decoding on the performance of GCR. We conduct the experiments on WebQSP with different beam sizes of 1, 3, 5, 10, and 20. The results are shown in Figure 4. 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 reasoning paths and find the correct answers. However, the F1 score, peaks when the beam size is set to 10. This is because the beam size of 10 can provide a balance between the exploration and exploitation of the reasoning paths. When the beam size is set to 20, the performance drops due to the increased complexity of the search space, which may introduce noise and make the reasoning less reliable. This also highlights the importance of using general LLMs to conduct inductive reasoning over multiple paths to disregard the noise and find the correct answers. Although the graph-constrained decoding benefits from the parallel GPU computation to explore multiple reasoning paths at the same time, the time cost still slightly increases from 1.4s to 7.8s with the increase of the beam size. Thus, we set the beam size to 10 in the experiments to balance the performance and efficiency. We also investigate the impact of $L$ hops paths used for KG-Trie construction in Section F.1. The results show that GCR can achieve a good balance between reasoning performance and efficiency by setting $L=2$ and $K=10$ .
5.3 RQ2: Hallucination Elimination and Faithful Reasoning
<details>
<summary>x4.png Details</summary>
### Visual Description
\n
## Bar Chart: Answer Hit Rate Comparison - Faithful vs. Error Reasoning
### Overview
This image presents a comparison of "Answer Hit" rates between "Faithful Reasoning" and "Error Reasoning" across two datasets: "WebQSP" and "CWQ". The comparison is made for two conditions within each dataset: "GCR" and "GCR w/o constraint". The data is visualized using bar charts.
### Components/Axes
* **X-axis:** Represents the conditions being compared: "GCR" and "GCR w/o constraint".
* **Y-axis:** Represents the "Answer Hit" rate, scaled from 0 to 60.
* **Legend:** Located at the top-center of the image, distinguishing between "Faithful Reasoning" (light blue) and "Error Reasoning" (light red).
* **Chart Titles:** "WebQSP" is above the left chart, and "CWQ" is above the right chart.
### Detailed Analysis
The image contains two separate bar charts.
**WebQSP Chart (Left):**
* **Faithful Reasoning (Light Blue):**
* For "GCR", the "Answer Hit" rate is 100.0%.
* For "GCR w/o constraint", the "Answer Hit" rate is 62.4%.
* **Error Reasoning (Light Red):**
* For "GCR", the "Answer Hit" rate is approximately 60%.
* For "GCR w/o constraint", the "Answer Hit" rate is approximately 60%.
**CWQ Chart (Right):**
* **Faithful Reasoning (Light Blue):**
* For "GCR", the "Answer Hit" rate is 100.0%.
* For "GCR w/o constraint", the "Answer Hit" rate is 48.1%.
* **Error Reasoning (Light Red):**
* For "GCR", the "Answer Hit" rate is approximately 60%.
* For "GCR w/o constraint", the "Answer Hit" rate is approximately 60%.
### Key Observations
* In both datasets (WebQSP and CWQ), "Faithful Reasoning" achieves a 100% "Answer Hit" rate for the "GCR" condition.
* Removing the constraint ("GCR w/o constraint") significantly reduces the "Answer Hit" rate for "Faithful Reasoning" in both datasets.
* "Error Reasoning" maintains a relatively consistent "Answer Hit" rate of approximately 60% across all conditions in both datasets.
* The difference in performance between "Faithful Reasoning" and "Error Reasoning" is most pronounced in the "GCR" condition.
### Interpretation
The data suggests that the "GCR" method, when combined with "Faithful Reasoning", leads to perfect performance ("Answer Hit" of 100%). However, removing the constraint associated with "GCR" degrades the performance of "Faithful Reasoning" substantially. "Error Reasoning" appears to be less sensitive to the presence or absence of the constraint, maintaining a consistent, but lower, performance level.
This could indicate that the "GCR" method relies heavily on the constraint to ensure accurate reasoning. Without the constraint, "Faithful Reasoning" is more susceptible to errors. "Error Reasoning", on the other hand, may be less reliant on the constraint, or may benefit from its removal in some way, resulting in a stable, albeit lower, performance. The consistent performance of "Error Reasoning" suggests it may be employing a different strategy that is not as affected by the constraint. The data highlights the importance of the constraint in achieving high accuracy with "Faithful Reasoning".
</details>
Figure 5: Analysis of performance and reasoning errors in GCR.
In this section, we investigate the effectiveness of KG constraints in eliminating hallucinations and ensuring faithful reasoning. We first compare the difference of answer accuracy (Hit) and faithful reasoning ratio by removing KG constraints in graph-constrained decoding. The faithful reasoning ratio is calculated as the percentage of faithful reasoning in correctly predicted answers. We define a reasoning as faithful where the generated reasoning path can be found in KGs, and vice versa.
From the Figure 5, we can observe that GCR achieves the 100% faithful reasoning ratio on both datasets, which indicates that GCR can eliminate hallucinations and ensure faithful reasoning during reasoning on KGs. In contrast, when removing KG constraints, both the answer accuracy and faithful reasoning decrease significantly on WebQSP. This shows that KG constraints not only improve reasoning by reducing the searching space, but also play a crucial role in preventing hallucinations for accurate reasoning. While the answer hit rate on CWQ remains almost unchanged, the ratio of faithful reasoning still decreases to 48.1%. This implies that even if LLMs can produce correct answers, the reasoning process is still prone to hallucinations and cannot be trusted, which is aligned with the findings in previous studies (Nguyen et al., 2024).
Table 5: Examples of the faithful reasoning conducted by GCR. Red denotes the incorrect reasoning paths and answers, while bold denotes the correct paths and answers.
| Case 1: Incorrect answers and hallucinated reasoning paths without constraints. | |
| --- | --- |
| Question | Who is niall ferguson ’s wife? |
| Answer | Ayaan Hirsi Ali |
| GCR $w/o$ constraint | # Reasoning Path: Niall Ferguson $→$ people.person.children $→$ Mabel Rose Ferguson $→$ people.person.parents $→$ Alyssa Mastromonaco #Answer: Alyssa Mastromonaco |
| GCR | # Reasoning Path: Niall Ferguson $→$ people.person.children $→$ Thomas Ferguson $→$ people.person.parents $→$ Ayaan Hirsi Ali #Answer: Ayaan Hirsi Ali |
| Case 2: Correct answers but hallucinated reasoning paths without constraints. | |
| Question | Where is jamarcus russell from? |
| Answer | Mobile |
| GCR $w/o$ constraint | # Reasoning Path: JaMarcus Russell $→$ people.person.place_of_birth $→$ Tampa #Answer: Mobile, Alabama |
| GCR | # Reasoning Path: JaMarcus Russell $→$ people.person.place_of_birth $→$ Mobile #Answer: Mobile |
Case Study. We further provide a case study to illustrate the effectiveness of GCR in eliminating hallucinations and ensuring faithful reasoning. As shown in Table 5, the first case demonstrates that, without constraints, the model generates an incorrect reasoning path leading to an incorrect answer by hallucinating facts such as “Mabel Rose Ferguson is the child of Naill Ferguson and her parent is Alyssa Mastromonaco”. In contrast, GCR generates a faithful reasoning path grounded in KGs that “Naill Ferguson has a child named Thomas Ferguson who has a parent named Ayaan Hirsi Ali”. Based on the paths we can reason the correct answer to the question is “Ayaan Hirsi Ali”. In the second case, although the LLM answers the question correctly, the generated reasoning path is still hallucinated with incorrect facts. Conversely, GCR conducts faithful reasoning with both correct answer and reasoning path. These results demonstrate that GCR can effectively eliminate hallucinations and ensure faithful reasoning by leveraging KG constraints in graph-constrained decoding.
5.4 RQ3: Zero-shot Generalizability to Unseen KGs
In GCR, the knowledge graph is converted into a constraint which is plugged into the decoding process of LLMs. This allows GCR to generalize to unseen KGs without further training. To evaluate the generalizability of GCR, we conduct zero-shot transfer experiments on three unseen KGQA datasets: FreebaseQA (Jiang et al., 2019), CSQA (Talmor et al., 2019) and MedQA (Jin et al., 2021). Specifically, we use the same KG-specialized LLM (Llama-3.1-8B) trained on Freebase as well as two general LLMs (ChatGP, GPT-4o-mini). During reasoning, we directly plug the KG-Trie constructed from Freebase, ConceptNet and medical KGs into the GCR to conduct graph-constrained decoding without additional fine-tuning. The results are shown in Table 6.
Table 6: Zero-shot transferability to other KGQA datasets.
| Model | FreebaseQA | CSQA | MedQA |
| --- | --- | --- | --- |
| ChatGPT | 85 | 79 | 64 |
| GCR (ChatGPT) | 92 | 85 | 66 |
| GPT-4o-mini | 89 | 91 | 75 |
| GCR (GPT-4o-mini) | 94 | 94 | 79 |
From the results, it is evident that GCR outperforms ChatGPT and GPT-4o-mini in zero-shot performance on both datasets. Specifically, GCR shows 8.2% and 7.6% increase in accuracy on FreebaseQA and CSQA, respectively. This highlights the strong zero-shot generalizability of its graph reasoning capabilities to unseen datasets and KGs without additional training. However, the improvement on MedQA is not as significant as that on CSQA. We hypothesize this difference may be due to LLMs having more common sense knowledge, which aids in reasoning on common sense knowledge graphs effectively. On the other hand, medical KGs are more specialized and require domain-specific knowledge for reasoning, potentially limiting the generalizability of our method.
6 Conclusion
In this paper, we introduce a novel LLM reasoning paradigm called graph-constrained reasoning (GCR) to eliminate hallucination and ensure faithful reasoning by incorporating structured KGs. To bridge the unstructured reasoning in LLMs with the structured knowledge in KGs, we propose a KG-Trie to encode paths in KGs using a trie-based index. KG-Trie constrains the decoding process to guide a KG-specialized LLM to generate faithful reasoning paths grounded in KGs. By imposing constraints, we can not only eliminate hallucination in reasoning but also reduce the reasoning complexity, contributing to more efficient and accurate reasoning. Last, a powerful general LLM is utilized as a complement to inductively reason over multiple reasoning paths to generate the final answer. Extensive experiments demonstrate that GCR excels in faithful reasoning and generalizes well to reason on new KGs without additional fine-tuning.
Acknowledgment
G Haffari is supported by the DARPA Assured Neuro Symbolic Learning and Reasoning (ANSR) program under award number FA8750-23-2-1016. C Gong is supported by NSF of China (Nos: 62336003, 12371510). S Pan was partly funded by Australian Research Council (ARC) under grants FT210100097 and DP240101547 and the CSIRO – National Science Foundation (US) AI Research Collaboration Program.
Impact Statement
Our research focuses exclusively on scientific questions, with no involvement of human subjects, animals, or environmentally sensitive materials. Therefore, we foresee no ethical risks or conflicts of interest. We are committed to maintaining the highest standards of scientific integrity and ethics to ensure the validity and reliability of our findings.
References
- Agrawal et al. (2024) Agrawal, G., Kumarage, T., Alghamdi, Z., and Liu, H. Mindful-rag: A study of points of failure in retrieval augmented generation. arXiv preprint arXiv:2407.12216, 2024.
- Bollacker et al. (2008) Bollacker, K., Evans, C., Paritosh, P., Sturge, T., and Taylor, J. Freebase: a collaboratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pp. 1247–1250, 2008.
- Brown et al. (2020) Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in Neural Information Processing Systems, 33:1877–1901, 2020.
- Chen et al. (2022) Chen, C., Wang, Y., Li, B., and Lam, K.-Y. Knowledge is flat: A seq2seq generative framework for various knowledge graph completion. In Proceedings of the 29th International Conference on Computational Linguistics, pp. 4005–4017, 2022.
- (5) Chen, L., Tong, P., Jin, Z., Sun, Y., Ye, J., and Xiong, H. Plan-on-graph: Self-correcting adaptive planning of large language model on knowledge graphs. In The Thirty-eighth Annual Conference on Neural Information Processing Systems.
- De Cao et al. (2022) De Cao, N., Izacard, G., Riedel, S., and Petroni, F. Autoregressive entity retrieval. In International Conference on Learning Representations, 2022.
- Dehghan et al. (2024) Dehghan, M., Alomrani, M., Bagga, S., Alfonso-Hermelo, D., Bibi, K., Ghaddar, A., Zhang, Y., Li, X., Hao, J., Liu, Q., Lin, J., Chen, B., Parthasarathi, P., Biparva, M., and Rezagholizadeh, M. EWEK-QA : Enhanced web and efficient knowledge graph retrieval for citation-based question answering systems. In Ku, L.-W., Martins, A., and Srikumar, V. (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 14169–14187, Bangkok, Thailand, August 2024. Association for Computational Linguistics. URL https://aclanthology.org/2024.acl-long.764.
- (8) Dhuliawala, S., Komeili, M., Xu, J., Raileanu, R., Li, X., Celikyilmaz, A., and Weston, J. E. Chain-of-verification reduces hallucination in large language models. In ICLR 2024 Workshop on Reliable and Responsible Foundation Models.
- Dong et al. (2024) Dong, Z., Peng, B., Wang, Y., Fu, J., Wang, X., Shan, Y., and Zhou, X. Effiqa: Efficient question-answering with strategic multi-model collaboration on knowledge graphs. arXiv preprint arXiv:2406.01238, 2024.
- Erling & Mikhailov (2009) Erling, O. and Mikhailov, I. Rdf support in the virtuoso dbms. In Networked Knowledge-Networked Media: Integrating Knowledge Management, New Media Technologies and Semantic Systems, pp. 7–24. Springer, 2009.
- Evans (2010) Evans, J. S. B. Intuition and reasoning: A dual-process perspective. Psychological Inquiry, 21(4):313–326, 2010.
- Federico et al. (1995) Federico, M., Cettolo, M., Brugnara, F., and Antoniol, G. Language modelling for efficient beam-search. Computer Speech and Language, 9(4):353–380, 1995.
- Feng et al. (2020) Feng, Y., Chen, X., Lin, B. Y., Wang, P., Yan, J., and Ren, X. Scalable multi-hop relational reasoning for knowledge-aware question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1295–1309, 2020.
- Fredkin (1960) Fredkin, E. Trie memory. Communications of the ACM, 3(9):490–499, 1960.
- He et al. (2021) He, G., Lan, Y., Jiang, J., Zhao, W. X., and Wen, J.-R. Improving multi-hop knowledge base question answering by learning intermediate supervision signals. In Proceedings of the 14th ACM international conference on web search and data mining, pp. 553–561, 2021.
- Hoffman et al. (2024) Hoffman, M. D., Phan, D., Dohan, D., Douglas, S., Le, T. A., Parisi, A., Sountsov, P., Sutton, C., Vikram, S., and A Saurous, R. Training chain-of-thought via latent-variable inference. Advances in Neural Information Processing Systems, 36, 2024.
- Huang & Chang (2023) Huang, J. and Chang, K. C.-C. Towards reasoning in large language models: A survey. In Findings of the Association for Computational Linguistics: ACL 2023, pp. 1049–1065, 2023.
- Huang et al. (2024) Huang, J., Chen, X., Mishra, S., Zheng, H. S., Yu, A. W., Song, X., and Zhou, D. Large language models cannot self-correct reasoning yet. In The Twelfth International Conference on Learning Representations, 2024.
- Izacard & Grave (2021) Izacard, G. and Grave, É. Leveraging passage retrieval with generative models for open domain question answering. In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, pp. 874–880, 2021.
- Jiang et al. (2022) Jiang, J., Zhou, K., Zhao, X., and 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, 2022.
- Jiang et al. (2023) Jiang, J., Zhou, K., Dong, Z., Ye, K., Zhao, W. X., and Wen, J.-R. Structgpt: A general framework for large language model to reason over structured data. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 9237–9251, 2023.
- Jiang et al. (2024) Jiang, J., Zhou, K., Zhao, W. X., Song, Y., Zhu, C., Zhu, H., and Wen, J.-R. Kg-agent: An efficient autonomous agent framework for complex reasoning over knowledge graph. arXiv preprint arXiv:2402.11163, 2024.
- Jiang et al. (2019) Jiang, K., Wu, D., and Jiang, H. Freebaseqa: A new factoid qa data set matching trivia-style question-answer pairs with freebase. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pp. 318–323, 2019.
- Jin et al. (2021) Jin, D., Pan, E., Oufattole, N., Weng, W.-H., Fang, H., and Szolovits, P. What disease does this patient have? a large-scale open domain question answering dataset from medical exams. Applied Sciences, 11(14):6421, 2021.
- Li et al. (2023) Li, S., Gao, Y., Jiang, H., Yin, Q., Li, Z., Yan, X., Zhang, C., and Yin, B. Graph reasoning for question answering with triplet retrieval. In Findings of the Association for Computational Linguistics: ACL 2023, pp. 3366–3375, 2023.
- Li et al. (2024) Li, Y., Song, D., Zhou, C., Tian, Y., Wang, H., Yang, Z., and Zhang, S. A framework of knowledge graph-enhanced large language model based on question decomposition and atomic retrieval. In Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 11472–11485, 2024.
- Li et al. (2025) Li, Y., Zhang, X., Luo, L., Chang, H., Ren, Y., King, I., and Li, J. G-refer: Graph retrieval-augmented large language model for explainable recommendation. In Proceedings of the ACM on Web Conference 2025, pp. 240–251, 2025.
- Liang et al. (2023) Liang, K., Meng, L., Liu, M., Liu, Y., Tu, W., Wang, S., Zhou, S., and Liu, X. Learn from relational correlations and periodic events for temporal knowledge graph reasoning. In Proceedings of the 46th international ACM SIGIR conference on research and development in information retrieval, pp. 1559–1568, 2023.
- Liang et al. (2024) Liang, K., Meng, L., Liu, Y., Liu, M., Wei, W., Liu, S., Tu, W., Wang, S., Zhou, S., and Liu, X. Simple yet effective: Structure guided pre-trained transformer for multi-modal knowledge graph reasoning. In Proceedings of the 32nd ACM International Conference on Multimedia, pp. 1554–1563, 2024.
- Liu et al. (2025) Liu, B., Zhang, J., Lin, F., Yang, C., Peng, M., and Yin, W. Symagent: A neural-symbolic self-learning agent framework for complex reasoning over knowledge graphs. In Proceedings of the ACM on Web Conference 2025, pp. 98–108, 2025.
- Luo et al. (2024) Luo, L., Li, Y.-F., Haffari, G., and Pan, S. Reasoning on graphs: Faithful and interpretable large language model reasoning. In International Conference on Learning Representations, 2024.
- Luo et al. (2025) Luo, L., Zhao, Z., Haffari, G., Phung, D., Gong, C., and Pan, S. Gfm-rag: Graph foundation model for retrieval augmented generation. arXiv preprint arXiv:2502.01113, 2025.
- Lv et al. (2024) Lv, Q., Wang, J., Chen, H., Li, B., Zhang, Y., and Wu, F. Coarse-to-fine highlighting: Reducing knowledge hallucination in large language models. In Forty-first International Conference on Machine Learning, 2024. URL https://openreview.net/forum?id=JCG0KTPVYy.
- Ma et al. (2024) Ma, J., Gao, Z., Chai, Q., Sun, W., Wang, P., Pei, H., Tao, J., Song, L., Liu, J., Zhang, C., et al. Debate on graph: a flexible and reliable reasoning framework for large language models. arXiv preprint arXiv:2409.03155, 2024.
- Mavromatis & Karypis (2022) Mavromatis, C. and Karypis, G. Rearev: Adaptive reasoning for question answering over knowledge graphs. In Findings of the Association for Computational Linguistics: EMNLP 2022, pp. 2447–2458, 2022.
- Mavromatis & Karypis (2024) Mavromatis, C. and Karypis, G. Gnn-rag: Graph neural retrieval for large language model reasoning. arXiv preprint arXiv:2405.20139, 2024.
- Meta (2024) Meta. Build the future of ai with meta llama 3, 2024. URL https://llama.meta.com/llama3/.
- Nguyen et al. (2024) Nguyen, T., Luo, L., Shiri, F., Phung, D., Li, Y.-F., Vu, T.-T., and Haffari, G. Direct evaluation of chain-of-thought in multi-hop reasoning with knowledge graphs. In Ku, L.-W., Martins, A., and Srikumar, V. (eds.), Findings of the Association for Computational Linguistics ACL 2024, pp. 2862–2883, Bangkok, Thailand and virtual meeting, August 2024. Association for Computational Linguistics. URL https://aclanthology.org/2024.findings-acl.168.
- OpenAI (2022) OpenAI. Introducing chatgpt, 2022. URL https://openai.com/index/chatgpt/.
- OpenAI (2024a) OpenAI. Hello gpt-4o, 2024a. URL https://openai.com/index/hello-gpt-4o/.
- OpenAI (2024b) OpenAI. New embedding models and api updates, 2024b. URL https://openai.com/index/new-embedding-models-and-api-updates/.
- OpenAI (2024c) OpenAI. Learning to reason with llms, 2024c. URL https://openai.com/index/learning-to-reason-with-llms/.
- Pan et al. (2024) Pan, S., Luo, L., Wang, Y., Chen, C., Wang, J., and Wu, X. Unifying large language models and knowledge graphs: A roadmap. IEEE Transactions on Knowledge and Data Engineering (TKDE), 2024.
- Qiao et al. (2023) Qiao, S., Ou, Y., Zhang, N., Chen, X., Yao, Y., Deng, S., Tan, C., Huang, F., and Chen, H. Reasoning with language model prompting: A survey. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 5368–5393, 2023.
- Reimers & Gurevych (2019) Reimers, N. and Gurevych, I. Sentence-bert: Sentence embeddings using siamese bert-networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 11 2019. URL https://arxiv.org/abs/1908.10084.
- Singh et al. (2021) Singh, D., Reddy, S., Hamilton, W., Dyer, C., and Yogatama, D. End-to-end training of multi-document reader and retriever for open-domain question answering. Advances in Neural Information Processing Systems, 34:25968–25981, 2021.
- Speer et al. (2017) Speer, R., Chin, J., and Havasi, C. Conceptnet 5.5: An open multilingual graph of general knowledge. In Proceedings of the AAAI conference on artificial intelligence, volume 31, 2017.
- Stanovich et al. (2000) Stanovich, K., West, R., and Hertwig, R. Individual differences in reasoning: Implications for the rationality debate?-open peer commentary-the questionable utility of cognitive ability in explaining cognitive illusions. 2000.
- Sui et al. (2024) Sui, Y., He, Y., Liu, N., He, X., Wang, K., and Hooi, B. Fidelis: Faithful reasoning in large language model for knowledge graph question answering. arXiv preprint arXiv:2405.13873, 2024.
- Sun et al. (2018) Sun, H., Dhingra, B., Zaheer, M., Mazaitis, K., Salakhutdinov, R., and Cohen, W. 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, 2018.
- Sun et al. (2024) Sun, J., Xu, C., Tang, L., Wang, S., Lin, C., Gong, Y., Ni, L., Shum, H.-Y., and Guo, J. Think-on-graph: Deep and responsible reasoning of large language model on knowledge graph. In The Twelfth International Conference on Learning Representations, 2024.
- Talmor & Berant (2018) Talmor, A. and Berant, J. The web as a knowledge-base for answering complex questions. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), pp. 641–651, 2018.
- Talmor et al. (2019) Talmor, A., Herzig, J., Lourie, N., and Berant, J. Commonsenseqa: A question answering challenge targeting commonsense knowledge. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pp. 4149–4158, 2019.
- Touvron et al. (2023) Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288, 2023.
- Wang et al. (2024a) Wang, J., Sun, K., Luo, L., Wei, W., Hu, Y., Liew, A. W.-C., Pan, S., and Yin, B. Large language models-guided dynamic adaptation for temporal knowledge graph reasoning. Thirty-Eighth Annual Conference on Neural Information Processing Systems, 2024a.
- Wang et al. (2023) Wang, K., Duan, F., Wang, S., Li, P., Xian, Y., Yin, C., Rong, W., and Xiong, Z. Knowledge-driven cot: Exploring faithful reasoning in llms for knowledge-intensive question answering. arXiv preprint arXiv:2308.13259, 2023.
- Wang et al. (2024b) Wang, X., Wei, J., Schuurmans, D., Le, Q. V., Chi, E. H., Narang, S., Chowdhery, A., and Zhou, D. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2024b.
- Wei et al. (2022) Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D., et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35:24824–24837, 2022.
- Wikipedia contributors (2024) Wikipedia contributors. Trie. https://en.wikipedia.org/wiki/Trie, 2024. Accessed: 2024-09-11.
- Wu et al. (2020) Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Philip, S. Y. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4–24, 2020.
- Xia et al. (2019) Xia, F., Liu, J., Nie, H., Fu, Y., Wan, L., and Kong, X. Random walks: A review of algorithms and applications. IEEE Transactions on Emerging Topics in Computational Intelligence, 4(2):95–107, 2019.
- Xie et al. (2022) Xie, X., Zhang, N., Li, Z., Deng, S., Chen, H., Xiong, F., Chen, M., and Chen, H. From discrimination to generation: Knowledge graph completion with generative transformer. In Companion Proceedings of the Web Conference 2022, pp. 162–165, 2022.
- Yang et al. (2024a) Yang, A., Yang, B., Hui, B., Zheng, B., Yu, B., Zhou, C., Li, C., Li, C., Liu, D., Huang, F., Dong, G., Wei, H., Lin, H., Tang, J., Wang, J., Yang, J., Tu, J., Zhang, J., Ma, J., Xu, J., Zhou, J., Bai, J., He, J., Lin, J., Dang, K., Lu, K., Chen, K., Yang, K., Li, M., Xue, M., Ni, N., Zhang, P., Wang, P., Peng, R., Men, R., Gao, R., Lin, R., Wang, S., Bai, S., Tan, S., Zhu, T., Li, T., Liu, T., Ge, W., Deng, X., Zhou, X., Ren, X., Zhang, X., Wei, X., Ren, X., Fan, Y., Yao, Y., Zhang, Y., Wan, Y., Chu, Y., Liu, Y., Cui, Z., Zhang, Z., and Fan, Z. Qwen2 technical report. arXiv preprint arXiv:2407.10671, 2024a.
- Yang et al. (2024b) Yang, R., Liu, H., Zeng, Q., Ke, Y. H., Li, W., Cheng, L., Chen, Q., Caverlee, J., Matsuo, Y., and Li, I. Kg-rank: Enhancing large language models for medical qa with knowledge graphs and ranking techniques. arXiv preprint arXiv:2403.05881, 2024b.
- Yao et al. (2024) Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T., Cao, Y., and Narasimhan, K. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36, 2024.
- Yasunaga et al. (2021) Yasunaga, M., Ren, H., Bosselut, A., Liang, P., and Leskovec, J. Qa-gnn: Reasoning with language models and knowledge graphs for question answering. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 535–546, 2021.
- Yih et al. (2016) Yih, W.-t., Richardson, M., Meek, C., Chang, M.-W., and Suh, J. The value of semantic parse labeling for knowledge base question answering. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 201–206, 2016.
- Yu et al. (2022) Yu, P., Wang, T., Golovneva, O., AlKhamissi, B., Verma, S., Jin, Z., Ghosh, G., Diab, M., and Celikyilmaz, A. Alert: Adapting language models to reasoning tasks. arXiv preprint arXiv:2212.08286, 2022.
- Zhang et al. (2022) Zhang, J., Zhang, X., Yu, J., Tang, J., Tang, J., Li, C., and Chen, H. Subgraph retrieval enhanced model for multi-hop knowledge base question answering. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 5773–5784, 2022.
- Zhang et al. (2023) Zhang, P., Xiao, S., Liu, Z., Dou, Z., and Nie, J.-Y. Retrieve anything to augment large language models. arXiv preprint arXiv:2310.07554, 2023.
- Zhu et al. (2024) Zhu, Y., Qiao, S., Ou, Y., Deng, S., Zhang, N., Lyu, S., Shen, Y., Liang, L., Gu, J., and Chen, H. Knowagent: Knowledge-augmented planning for llm-based agents. arXiv preprint arXiv:2403.03101, 2024.
Appendix
\parttoc
Appendix A Detailed Related Work on KG-enhanced LLMs
Knowledge graph (KG), as a structured representation of factual knowledge, has been widely used to enhance the factual knowledge and reasoning abilities of LLMs (Pan et al., 2024; Liang et al., 2024) by reducing the hallucinations (Nguyen et al., 2024; Dhuliawala et al., ; Lv et al., 2024). In this section, we provide a detailed review of the related work on KG-enhanced LLMs, which can be categorized into two paradigms: retrieval-based and agent-based methods.
Retrieval-based Methods. Retrieval-based methods retrieve relevant facts from KGs with an external retriever and then feed them into the inputs of LLMs for reasoning. These methods aim to provide LLMs with external knowledge to enhance their reasoning abilities (Li et al., 2025). For example, KD-CoT (Wang et al., 2023) retrieves relevant knowledge from KGs to generate faithful reasoning plans for LLMs. EWEK-QA (Dehghan et al., 2024) enriches the retrieved knowledge by searching from both KGs and the web. RoG (Luo et al., 2024) proposes a planning-retrieval-reasoning framework that retrieves reasoning paths from KGs to guide LLMs conducting faithful reasoning. GNN-RAG (Mavromatis & Karypis, 2024) adopts a lightweight graph neural network to effectively retrieve from KGs. GNN-RAG+RA (Mavromatis & Karypis, 2024) combines the retrieval results of both RoG and GNN-RAG to enhance the reasoning performance. GFM-RAG (Luo et al., 2025) utilizes KG as the structural index of knowledge and designs a graph foundation model to reason on KGs and retrieve relevant knowledge for LLMs. Studies have also been proposed to retrieve from dynamic KGs to enhance the temporal reasoning abilities of LLMs (Wang et al., 2024a; Liang et al., 2023). However, these methods may suffer from the retrieval accuracy, which limits the reasoning performance.
Agent-based Methods. Agent-based methods treat LLMs as agents that iteratively interact with KGs to find reasoning paths and answers. For example, StructGPT (Jiang et al., 2023) treats LLMs as agents to interact with KGs to find a reasoning path leading to the correct answer. ToG (Sun et al., 2024) extends the method and conducts reasoning on KGs by exploring multiple paths and concludes the final answer by aggregating the evidence from them. EffiQA (Jiang et al., 2024) proposes an efficient agent-based method to reason on KGs. Plan-on-Graph (Chen et al., ) proposes an adaptive planing paradigm to decompose the question into sub-tasks and guide the LLMs to reason on KGs. Debate on Graph (Ma et al., 2024) asks LLM as agents to debate with each other to gradually simplify complex questions and find the correct answers. SymAgent (Liu et al., 2025) introduces a collaborative agent framework that autonomously utilizes tools to integrate information from KGs and external documents, tackling the problem of KG incompleteness. Although these methods are effective, they face high computational costs and challenges in designing the interaction process.
Appendix B KG-Trie Construction
KG-Trie converts KG structures into the format that LLMs can handle. It can been incorporated into the LLM decoding process as constraints, allowing for faithful reasoning paths that align with the graph’s structure. The KG-Trie can be either pre-computed for fast inference or constructed on-demand to minimize pre-processing time.
B.1 Construction Strategies
Offline Construction. The KG-Trie can be pre-computed offline, allowing them to be used during inference at no additional cost. Instead of constructing the KG-Trie for all entities in the KG, we could only construct the KG-Trie for certain entities. We can select the entities based on their popularity, importance, or the frequency of their occurrence in the questions.
On-demand Construction. Alternatively, we can construct the KG-Trie on-demand. When a question is given, we first identify the question entities with named entity recognition (NER) tools. Then, we retrieve the question-related subgraphs around the question entities from the KGs. Finally, we construct a question-specific KG-Trie based on the retrieved subgraphs. The KG-Trie is then used to guide the LLMs to reason on the KGs.
Dynamic Cache for KG-Trie Construction. Users can also develop their own strategies to balance pre-processing and inference overhead. For example, we can maintain a dynamic cache to store the KG-Trie for the most frequently asked questions, as shown in Figure 6. When a new question is given, they first check whether the KG-Trie for the question is in the cache. If it is, they directly use the KG-Trie for inference. Otherwise, they construct a question-specific KG-Trie on-demand. The cache can be updated periodically to remove the least frequently used KG-Trie and add the new ones.
<details>
<summary>x5.png Details</summary>
### Visual Description
\n
## Diagram: Knowledge Graph Trie Caching System
### Overview
This diagram illustrates a system for caching Knowledge Graph (KG) Tries to accelerate question answering. The system takes user queries, performs entity recognition, retrieves relevant subgraphs from KG storage, constructs KG-Tries, caches them, and then uses graph-constrained reasoning to answer the query. The diagram shows the flow of data and control between different components.
### Components/Axes
The diagram consists of the following components:
* **User Queries:** Represented by two example questions: "Who is the president of Australia?" and "Who is the spouse of the ex-president of USA?".
* **Entity Recognition:** A box labeled "Entity Recognition" that identifies entities in the user queries.
* **KG-Trie Cache (x2):** Two rectangular boxes labeled "KG-Trie Cache" representing the cache storage. Each cache contains a "Key" and "Value" column.
* **KG Storage:** A cloud-shaped object labeled "KG storage" representing the main knowledge graph database.
* **Question-related subgraph:** A network of nodes and edges representing a subgraph extracted from the KG storage.
* **KG-Trie:** A tree-like structure representing the KG-Trie constructed from the subgraph.
* **Cache Management:** A box labeled "Cache Management" that handles cache updates.
* **Graph-constrained Reasoning:** A box labeled "Graph-constrained Reasoning" that uses the KG-Trie to answer the query.
The diagram also includes directional arrows indicating the flow of data and control.
### Detailed Analysis or Content Details
**1. User Queries:**
* Query 1: "Who is the president of Australia?"
* Query 2: "Who is the spouse of the ex-president of USA?"
**2. Entity Recognition:**
* Identified entities: Australia, USA.
**3. KG-Trie Cache (Initialization):**
* Key: Australia, Value: Trie 1
* Key: China, Value: Trie 2
* Key: ..., Value: ... (Indicates more entries exist)
**4. KG-Trie Cache (After Update):**
* Key: Australia, Value: Trie 1
* Key: China, Value: Trie 2
* Key: USA, Value: Trie 3
**5. KG Storage:**
* The KG storage is represented as a cloud, implying a large and complex knowledge graph.
**6. Graph Retrieval:**
* The arrow from KG storage to "Question-related subgraph" indicates that a relevant subgraph is retrieved based on the identified entities.
**7. KG-Trie Construction:**
* The arrow from "Question-related subgraph" to "KG-Trie" indicates that a KG-Trie is constructed from the subgraph.
**8. Cache Update:**
* A dashed arrow from the first "KG-Trie Cache" to the second "KG-Trie Cache" indicates a cache update process.
**9. Graph-constrained Reasoning:**
* The arrow from "KG-Trie" to "Graph-constrained Reasoning" indicates that the KG-Trie is used for reasoning.
### Key Observations
* The system utilizes a cache to store KG-Tries for frequently accessed entities (Australia, China, USA).
* The cache is updated when new queries require the construction of new KG-Tries.
* The system retrieves relevant subgraphs from the KG storage based on the entities identified in the user queries.
* The KG-Trie structure is used to facilitate graph-constrained reasoning.
* The diagram shows a two-stage caching process, potentially for redundancy or different caching strategies.
### Interpretation
The diagram illustrates a system designed to improve the efficiency of question answering over a knowledge graph. By caching KG-Tries, the system avoids the need to repeatedly retrieve and construct these structures for common entities. This caching mechanism significantly reduces the latency of query processing. The use of graph-constrained reasoning suggests that the system leverages the relationships within the knowledge graph to provide more accurate and informative answers. The two-stage caching system might be implemented to handle cache misses or to provide a backup in case of cache failures. The diagram highlights the key components and data flow involved in this process, providing a clear understanding of how the system operates. The system is designed to handle natural language queries, extract relevant entities, and utilize a knowledge graph to provide answers. The diagram does not provide specific performance metrics or scalability information, but it suggests a well-structured and optimized approach to knowledge graph-based question answering.
</details>
Figure 6: The illustration of dynamic cache for KG-Trie construction.
B.2 Time and Space Complexity Analysis
The time and space complexity for KG-Trie construction is affordable and can be easily improved in industry-level applications to support billions of scale graphs. To support this, we provide detailed theoretical analysis and empirical evidence. In experiments, we adopt the breadth-first search, whose complexities are:
B.2.1 Theoretical Analysis
Time Complexity. Constructing the KG-Trie involves a BFS traversal to explore paths up to a maximum length of $L$ starting from certain entities. The time complexity of this traversal is $O(E^{L})$ , where $E$ is the average number of edges per entity, and $L$ is the maximum path length. BFS ensures that all reachable paths up to length $L$ are considered. However, BFS can be replaced with other efficient graph-traversing algorithms, such as random walk (Xia et al., 2019) to further improve efficiency.
Space Complexity. The space complexity of the KG-Trie depends on the number of unique paths and their tokenized representations. In the worst case, the space complexity is $O(E^{L}× T)$ , where $T$ represents the average number of tokens per path. Trie structures are efficient for storing shared prefixes, which reduces redundancy and optimizes memory usage. Moreover, it supports efficient traversal of reasoning paths in constant time.
B.2.2 Empirical Analysis
We have provided the average BFS running time and space consumption of the KG-Trie construction to demonstrate its efficiency. The system settings are illustrated at Table 7.
Table 7: System settings overview for efficiency experiments.
| System Setting | Specification |
| --- | --- |
| CPU | Intel(R) Xeon(R) Silver 4214R CPU @ 2.40GHz |
| Memory | 32G |
| BFS Implementation | Virtuoso SPARQL |
| Space Storage | Pickle |
In the experiment, we build the KG-Trie for all question entities of WebQSP dataset and measure the average running time and space consumption. The BFS is executed on the Freebase KG stored in a Virtuoso database (Erling & Mikhailov, 2009). We retrieve the $L$ -hop paths, then save the constructed KG-Trie with Pickle. The statistics show that both running time and space usage are acceptable when $L<=3$ , which highlights efficiency in KG-Trie construction. Although a larger hop can lead to better coverage of the possible answer, it would significantly increase the time and space complexity. Thus, we set hops to 2 or 3 in experiments to balance between efficiency and effectiveness. Notably, time can be further reduced by utilizing multi-threading. Space consumption can be optimized by storing data in a database.
Table 8: Average running time and space utilization of the KG-Trie construction.
| Hop | Avg. Running Time (s) | Space (Mb) |
| --- | --- | --- |
| L=1 | 0.0058 | 0.4 |
| L=2 | 0.0133 | 0.5 |
| L=3 | 0.0219 | 2.5 |
B.2.3 Time Consumption Breakdown
In addition, we have provided a detailed breakdown of the time consumption for each component involved in the KG-Trie construction. As shown in Table 9, the overall time for constructing the KG-Trie under the open-end setting is approximately 0.28 seconds. This includes the time for all necessary stages, such as Named Entity Recognition, Entity Linking, graph retrieval, tokenization, and trie construction.
Table 9: Breakdown of the time consumption for each component involved in the KG-Trie construction.
| Component | Description | Implementation | Time (s) |
| --- | --- | --- | --- |
| Named Entity Recognition (NER) | Identify mentioned entities in user questions | Spacy | 0.0059 |
| Entity Linking (NL) | Link to entities in KGs | ColBERTv2 | 0.0457 |
| Graph Retrieval | Retrieve question-relevant subgraphs for KG-Trie construction (Eq. 3). | 2-hop BFS implemented with SPARQL. | 0.0133 |
| Tokenizer | Tokenize paths into tokens for building LLM constraints (Eq. 4). | Llama-3-8B Tokenizer implemented by Huggingface. | 0.1227 |
| Trie construction | Store the tokenized paths with Trie (Eq. 5). | Python MARISA Trie | 0.0962 |
| Total | | | 0.2838 |
B.3 Strategies for Optimizing Efficiency
We provide several strategies that can be used to further speed up the KG-Trie construction.
Parallel Processing: 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 in Table 10 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.
Table 10: Total running time and improvement under different processing threads.
| Total time (s) | Total Time (min) | Improvement |
| --- | --- | --- |
| Thread=1 | 4.03 | 100% |
| Thread=4 | 3.21 | 126% |
| Thread=10 | 2.31 | 174% |
| Thread=20 | 1.92 | 210% |
Efficiency Graph Traversal Algorithms: The BFS or DFS enumerates all the paths around the entities which might lead to computational overhead. However, they can be easily replaced with other graph traversal algorithms, such as random walk, to reduce time complexity.
Combination with Graph Retrieval Algorithms: To reduce the overhead of graph traversal, we can construct the KG-Trie on the question-related subgraphs. To this end, our methods can be combined with other graph retrieval algorithms, such as GNN-RAG (Mavromatis & Karypis, 2024) and RoG (Luo et al., 2024). They would retrieve meaningful and relevant paths from KGs to speed up the KG-Trie construction. However, the performance might be limited by the retrieval accuracy.
Reduce Entities Number: Instead of constructing the KG-Trie for all entities in the KG, we could only construct the KG-Trie for certain entities. We can select the entities based on their popularity, importance, or the frequency of their occurrence in the questions.
B.4 Real-World Applicability
To support real-world applications with billion-scale KGs, KG-Trie construction can be implemented in industrial-level settings. For instance, billion-scale KGs can be stored in scalable graph databases like Neo4j. The parallel nature of KG-Trie construction allows it to be executed on distributed computing systems such as Hadoop and Spark, enabling pre-computation and offline storage. The constructed KG-Trie can then be stored in a database and loaded for inference without additional computation, facilitating real-time responses. To reduce the overhead in pre-processing, we can design a cache mechanism that only builds KG-Trie for popular accessed entities and caches them for faster inference. The illustration of the framework can be found in Figure 6.
Appendix C Datasets
KGQA Datasets. To compare the reasoning performance with existing methods, we use two benchmark KGQA datasets in this study: WebQuestionSP (WebQSP) (Yih et al., 2016) and Complex WebQuestions (CWQ) (Talmor & Berant, 2018). To ensure fairness, we adopt the same train and test splits as previous works (Jiang et al., 2022; Luo et al., 2024). Details of the datasets can be found in Table 11.
Both WebQSP and CWQ can be reasoned using Freebase KGs https://github.com/microsoft/FastRDFStore (Bollacker et al., 2008). To reduce the size of the KGs, we use a subgraph of Freebase by extracting all triples that start from question entities within the maximum reasoning hops provided by previous works WebQSP: https://huggingface.co/datasets/rmanluo/RoG-webqsp, CWQ: https://huggingface.co/datasets/rmanluo/RoG-cwq (Luo et al., 2024). The statistics of the knowledge graphs are shown in Table 13.
Fine-tuning Datasets. To enhance the KG reasoning ability of LLMs, we construct fine-tuning datasets by generating reasoning paths from the KGs. Specifically, we adopt the training split of WebQSP and CWQ, which contain 2,826 and 27,639 question-answer pairs, respectively. For each question, we find all the shortest reasoning paths on KGs that connect the question entity to the answer entity. We then convert the reasoning paths into formatted strings and pair them with the question-answer pairs with the template shown in Figure 10 to form the fine-tuning datasets. Since there could be multiple reasoning paths for a question, we generate multiple training instances paired with different reasoning paths for each question-answer pair. The fine-tuning datasets contain 28,307 and 181,602 question-reasoning path-answer triples for WebQSP and CWQ, respectively. The statistics of the fine-tuning datasets are shown in Table 12.
Zero-shot Generalization Datasets. To evaluate the transferability of GCR, we further select three new KGQA datasets: FreebaseQA (Jiang et al., 2019), CommonsenseQA (CSQA) (Talmor et al., 2019) and MedQA-USMLE (MedQA) (Jin et al., 2021). FreebaseQA is an open-ended question answering dataset. CSQA is a 5-way multiple choice QA dataset that involves reasoning with commonsense knowledge. MedQA is a 4-way multiple choice QA task that requires biomedical and clinical knowledge. FreebaseQA adopts the same Freebase KG used in WebQSP and CWQ. For CSQA, we use the ConceptNet (Speer et al., 2017), which is a general-purpose KG that contains commonsense knowledge. For MedQA, we use a medical KG constructed from the Unified Medical Language System (Yasunaga et al., 2021). The statistics of the knowledge graphs are shown in Table 13. We respectively select 100 questions from each dataset. For each question, following previous studies (Feng et al., 2020; Yasunaga et al., 2021), a 2-hop subgraph is extracted from the KGs to form the zero-shot generalization datasets.
Table 11: Statistics of datasets.
| Dataset | Dataset Statistics | Statistics of Answer Numbers | | | | |
| --- | --- | --- | --- | --- | --- | --- |
| #Train | #Test | #Ans = 1 | 2 $≥$ #Ans $≤$ 4 | 5 $≥$ #Ans $≤$ 9 | #Ans $≥$ 10 | |
| WebQSP | 2,826 | 1,628 | 51.2% | 27.4% | 8.3% | 12.1% |
| CWQ | 27,639 | 3,531 | 70.6% | 19.4% | 6% | 4% |
Table 12: Statistics of fine-tuning datasets for graph-constrained decoding.
| Total | WebQSP | CWQ |
| --- | --- | --- |
| 209,909 | 28,307 | 181,602 |
Table 13: Statistics of constructed knowledge graphs.
| KG | #Entities | #Relations | #Triples |
| --- | --- | --- | --- |
| Freebase | 2,566,291 | 7,058 | 8,309,195 |
| ConceptNet | 799,273 | 17 | 2,151,303 |
| MedKG | 9,958 | 15 | 49,974 |
Appendix D Baselines
We compare GCR with the 22 baselines grouped into three categories: 1) LLM reasoning methods, 2) graph reasoning methods, and 3) KG-enhanced LLM reasoning methods. The details of each baseline are described as follows.
LLM reasoning methods only rely on LLMs for reasoning without utilizing external KGs. We include both the vanilla LLMs with different sizes and the LLMs with advanced reasoning mechanisms. Specifically, we consider the following baselines:
- Qwen2-0.5B/1.5B.7B (Yang et al., 2024a) provides a series of pre-trained LLMs with different sizes, including 0.5B, 1.5B, and 7B parameters.
- Llama-2-7B (Touvron et al., 2023) is a large-scale LLM pre-trained on a diverse range of tasks.
- Llama-3.1-8B (Meta, 2024) is the updated version of Llama-2 with more powerful reasoning capabilities.
- ChatGPT (OpenAI, 2022) is a powerful closed-source LLM that could follow instructions to conduct complex tasks.
- GPT-4o-mini (OpenAI, 2024a) is the new flagship model of OpenAI that could reason across different modalities and tasks.
- Few-shot prompt (Brown et al., 2020) is a few-shot learning method that provides LLMs with a few examples in the prompts to conduct reasoning.
- CoT (Wei et al., 2022) is a chain-of-thought reasoning method that prompts LLMs to generate a chain of reasoning steps.
- Self-consistency (Wang et al., 2024b) generates multiple reasoning paths and selects the most consistent answer.
Graph reasoning methods focus on reasoning on KGs using graph neural networks (GNNs) (Wu et al., 2020) or graph-based reasoning mechanisms. We include the following baselines:
- GraftNet (Sun et al., 2018) is a graph-based reasoning method that retrieves relevant subgraphs from KGs with entity linking.
- NSM (He et al., 2021) utilizes the sequential model to mimic the multi-hop reasoning process on KGs.
- SR+NSM (Zhang et al., 2022) proposes a relation-path retrieval to retrieve subgraphs for multi-hop reasoning.
- ReaRev (Mavromatis & Karypis, 2022) is a GNN-based method that reasons on KGs by considering complex graph information.
- UniKGQA (Jiang et al., 2022) is a unified framework that combines graph-based reasoning of GNNs and LLMs for KGQA.
KG-enhanced LLM reasoning methods incorporate KGs to enhance the reasoning abilities of LLMs which can be further divided into retrieval-based and agent-based paradigms. We include the following baselines:
Retrieval-based methods retrieve relevant facts from KGs with an external retriever and then feed them into the inputs of LLMs for reasoning:
- KD-CoT (Wang et al., 2023) retrieves relevant knowledge from KGs to generate faithful reasoning plans for LLMs.
- EWEK-QA (Dehghan et al., 2024) enriches the retrieved knowledge by searching from both KGs and web.
- RoG (Luo et al., 2024) proposes a planning-retrieval-reasoning framework that retrieves reasoning paths from KGs to guide LLMs conducting faithful reasoning.
- GNN-RAG (Mavromatis & Karypis, 2024) adopts a lightweight graph neural network to effectively retrieve from KGs.
- GNN-RAG+RA (Mavromatis & Karypis, 2024) combines the retrieval results of both RoG and GNN-RAG to enhance the reasoning performance.
Agent-based methods treat LLMs as agents that iteratively interact with KGs to find reasoning paths and answers:
- ToG (Sun et al., 2024) conducts the reasoning on KGs by exploring multiple paths and concludes the final answer by aggregating the evidence from them.
- EffiQA (Jiang et al., 2024) proposes an efficient agent-based method to reason on KGs.
Appendix E Implementation Details and Experiment Settings
In this section, we will detail the implementation of GCR as well as the experiment settings.
Fine-tuning KG-specialized LLMs. We fine-tune several lightweight LLMs ranging from 0.5B to 8B (Yang et al., 2024a; Touvron et al., 2023; Meta, 2024) on the fine-tuning datasets for 3 epochs. The batch size is set to 4 and the learning rate is set to 2e-5. We use the cosine learning rate scheduler policy with the warmup ratio set to 0.03. The training is conducted on 2 A100-80G GPUs for each model. The training time and memory usage are shown in Table 14.
Table 14: Training time and memory usage for different KG-specialized LLMs.
| Model | Time | Mem. Usage per GPU |
| --- | --- | --- |
| Qwen2-0.5B | 3.47h | 10G |
| Qwen2-1.5B | 4.11h | 25G |
| Qwen2-7B | 14.37h | 81G |
| Llama-2-7B | 13.93h | 80G |
| Llama-3.1-8B | 14.52h | 85G |
KGQA Experiment Settings. The KGQA experiment shown in Table 1 aims to compare the reasoning performance of GCR with existing methods. For our method, we use the fine-tuned Llama-3.1-8B as KG-specialized LLMs, the general LLM is selected as ChatGPT and GPT-4o-mini. The KG-Trie is constructed from the subgraph of Freebase KGs. The maximum reasoning hops are set to 2 for both WebQSP and CWQ. The beam size is set to 10 for graph-constrained decoding. For vanilla LLMs baselines, we use the zero-shot prompting to ask the models to answer the questions. For other baselines, we strictly check whether the original papers follow the same settings and copy the results for fair comparison.
Efficiency Analysis Settings. The efficiency analysis shown in Table 2 aims to compare the efficiency and performance of different methods on WebQSP. For GCR, we use the same settings as the KGQA experiment. For dense retriever methods (e.g., S-Bert (Reimers & Gurevych, 2019), BGE (Zhang et al., 2023), OpenAI-Emb. (OpenAI, 2024b)), we first search all paths within 2-hops on the KGs which are formatted as sentences with the template in Figure 9. Then, we adopt the embedding model to encode the path sentences as embeddings which are stored in a vector database. During inference, we retrieve 10 paths from the vector database with the question as query and feed them into the LLMs for reasoning. For GNN-RAG (Mavromatis & Karypis, 2024) and RoG (Luo et al., 2024), we strictly follow the original papers to retrieve reasoning paths and conduct the experiments. For agent-based methods (e.g., ToG (Sun et al., 2024)), we use the same settings detailed in the original papers. For EffiQA (Jiang et al., 2024), since there is no available code, we directly copy the results from the original paper.
The average runtime is measured by the time taken to answer the questions. The average number of LLM calls is the number of times the LLMs are called to answer the questions. The average number of LLM tokens is the number of tokens inputted into LLMs to answer the questions, such as questions and retrieved reasoning paths. The experiments are conducted on a single A100-80G GPU for each method.
Ablation Study. In ablation study, we first try to analyze the effectiveness of different components in GCR. We conduct the experiments on WebQSP and CWQ datasets. By removing the KG-specialized LLM ( $w/o$ KG-specialized LLM), we search all the 2-hop paths starting from question entities and feed them into the general LLMs for reasoning. By removing the general LLM ( $w/o$ general LLM), we directly use the hypothesis answers generated by the KG-specialized LLMs as the final answers.
Different LLMs. We also analyze the different LLMs used for KG-specialized LLMs and general LLMs on WebQSP. For KG-specialized LLMs, we first use the vanilla LLMs with different learning types (i.e., zero-shot and few-shot prompting). For zero-shot prompting, we directly ask the models to generate the reasoning paths with the constraints. For few-shot prompting, we provide the models with a few examples in the prompts to conduct path generation. Detailed prompts can be found in Figures 10 and 12. Then, we fine-tune the lightweight LLMs with different sizes (0.5B to 8B) on the graph-constrained decoding task. For general LLMs, we use the vanilla LLMs to directly conduct reasoning over multiple reasoning paths. The detailed reasoning prompts can be found in Figure 11.
Parameter Analysis. We first analyze the performance of GCR with different beam sizes for graph-constrained decoding. We conduct the experiments on the WebQSP datasets with beam sizes of 1, 3, 5, 10, and 20. Then, we analyze the performance of GCR with different hops of paths encoded in the KG-Trie. We conduct the experiments on the WebQSP datasets with maximum paths hops ranging from 1 to 4.
Faithful Reasoning Analysis. We investigate the effect of the KG constraints on ensuring faithful reasoning. We adopt the fine-tuned Llama-3.1-8B as KG-specialized LLMs. Then, we compare the faithful reasoning rate and answer hit of GCR with and without the KG constraints in graph-constrained decoding. The faithful reasoning rate is the percentage of the faithful reasoning in the correctly predicted answers. A reasoning path is considered faithful if it can be found in the KGs, and vice versa. The answer hit is the percentage of the correct answers in the predictions.
Zero-shot Generalization Analysis. We evaluate the transferability of GCR on two zero-shot generalization datasets: CSQA and MedQA. We use the fine-tuned Llama-3.1-8B as KG-specialized LLMs and ChatGPT as well as GPT-4o-mini as the general LLMs. The KG-Trie is constructed from the subgraph of ConceptNet and MedKG. The maximum reasoning hops are set to 2 for both datasets. The beam size is set to 10 for graph-constrained decoding. For vanilla LLMs baselines (i.e., ChatGPT and GPT-4o-mini), we use the zero-shot prompting to ask the models to answer the questions.
Appendix F Additional Experiment Results
F.1 Performance on Different Hops of KG-Trie
In this section, we analyze the impact of different hops of reasoning paths on the performance of GCR. We conduct the experiments on WebQSP with different maximum hops of reasoning paths encoded in the KG-Trie. The results are shown in Figure 7. We observe that the performance of GCR increases with the number of hops of reasoning paths. The performance peaks when the maximum hops of reasoning paths are set to 2. This is because the 2-hop paths can provide sufficient information for the LLMs to conduct reasoning. When the hops are set to 3 or 4, the performance drops due to the increased complexity of the reasoning paths, which may introduce noise and make the reasoning less reliable. Additionally, the size of the KG-Trie slightly increases from 0.5 MB to 7.5 MB with the increase of the hops from 1 to 4. This indicates that the KG-Trie can be efficiently constructed with a small size and guide the LLMs to reason on graphs effectively.
<details>
<summary>x6.png Details</summary>
### Visual Description
\n
## Chart: KG-Trie Performance vs. Path Length
### Overview
The image presents a chart illustrating the performance of a KG-Trie (Knowledge Graph Trie) system as a function of the KG-Trie path length, denoted as *L*. The chart displays four metrics: Average KG-Trie size (in MB), Hit rate, Precision, and Recall. The Average KG-Trie size is represented by a bar chart, while the other three metrics are plotted as lines against the path length. A secondary y-axis on the right side of the chart represents Answer Coverage (in %).
### Components/Axes
* **X-axis:** KG-Trie Path Length *L* (with markers at 1, 2, 3, and 4)
* **Primary Y-axis (left):** Avg. KG-Trie size (MB) - Scale ranges from 0 to 8.
* **Secondary Y-axis (right):** Answer Coverage (%) - Scale ranges from 60% to 90%.
* **Legend (top-right):**
* Avg. KG-Trie size (MB) - Purple
* Hit - Red
* Precision - Orange
* Recall - Dotted Orange
* F1 - Blue (dashed)
### Detailed Analysis
**Average KG-Trie Size (Purple Bars):**
* L = 1: Approximately 0.4 MB
* L = 2: Approximately 1.2 MB
* L = 3: Approximately 2.4 MB
* L = 4: Approximately 7.2 MB
*Trend:* The average KG-Trie size increases significantly with increasing path length *L*. The increase is roughly exponential.
**Hit Rate (Red Line):**
* L = 1: Approximately 3.8 (Answer Coverage)
* L = 2: Approximately 8.5 (Answer Coverage)
* L = 3: Approximately 8.8 (Answer Coverage)
* L = 4: Approximately 8.8 (Answer Coverage)
*Trend:* The Hit rate increases sharply from L=1 to L=2, then plateaus, remaining relatively constant from L=2 to L=4.
**Precision (Orange Line):**
* L = 1: Approximately 4.2 (Answer Coverage)
* L = 2: Approximately 5.2 (Answer Coverage)
* L = 3: Approximately 4.6 (Answer Coverage)
* L = 4: Approximately 4.4 (Answer Coverage)
*Trend:* The Precision increases slightly from L=1 to L=2, then decreases gradually from L=2 to L=4.
**Recall (Dotted Orange Line):**
* L = 1: Approximately 6.4 (Answer Coverage)
* L = 2: Approximately 7.4 (Answer Coverage)
* L = 3: Approximately 6.8 (Answer Coverage)
* L = 4: Approximately 6.6 (Answer Coverage)
*Trend:* The Recall increases slightly from L=1 to L=2, then decreases gradually from L=2 to L=4.
**F1 Score (Blue Dashed Line):**
* L = 1: Approximately 1.2 (Answer Coverage)
* L = 2: Approximately 3.4 (Answer Coverage)
* L = 3: Approximately 3.6 (Answer Coverage)
* L = 4: Approximately 3.8 (Answer Coverage)
*Trend:* The F1 score increases steadily with increasing path length *L*.
### Key Observations
* The KG-Trie size grows rapidly with increasing path length.
* The Hit rate plateaus after L=2, suggesting diminishing returns in terms of answer retrieval with longer paths.
* Precision and Recall both decrease slightly after L=2, indicating a potential trade-off between coverage and accuracy.
* The F1 score, which balances precision and recall, shows a consistent increase with path length, but at a decreasing rate after L=2.
### Interpretation
The chart demonstrates the relationship between KG-Trie path length and performance metrics. Increasing the path length *L* initially improves the Hit rate and F1 score, but also leads to a significant increase in the KG-Trie size. Beyond a certain path length (around L=2 in this case), the gains in performance become marginal, while the memory footprint continues to grow. This suggests an optimal path length exists, balancing performance and resource usage. The plateauing of the Hit rate and the slight decrease in Precision and Recall after L=2 indicate that longer paths may introduce noise or redundancy, potentially degrading the quality of the retrieved answers. The data suggests that for this specific KG-Trie implementation, a path length of 2 or 3 might represent a good compromise between performance and efficiency. The chart highlights the importance of carefully tuning the path length parameter to optimize the KG-Trie system for a given application.
</details>
Figure 7: Parameter analysis of path hop $L$ for KG-Trie construction on WebQSP.
F.2 Performance on Multi-path Reasoning
GCR could take advantage of the GPU parallel computation to conduct multi-path explorations on KGs with beam-search. It could generate simultaneously generate $K$ reasoning paths and hypothesis answers with beam search in a single LLM call. The effectiveness of different $K$ is analyzed in Figure 4 where larger $K$ can lead to a better recall of the answers. In addition, we compare the F1 performance under different numbers of ground-truth answers with RoG, which requires reasoning across multiple reasoning paths to find all answers. From the results shown in Table 15, we can observe that GCR exhibits better performance in exploring multiple paths for reasoning.
Table 15: F1 comparison against RoG under different numbers of ground-truth answers.
| Methods | WebQSP | CWQ | | | | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| # Ans = 1 | 2 <= # Ans <= 4 | 5 <= # Ans <= 9 | # Ans >= 10 | # Ans = 1 | 2 <= # Ans <= 4 | 5 <= # Ans <= 9 | # Ans >= 10 | |
| GCR | 71.31 | 78.14 | 83.47 | 63.20 | 55.80 | 64.08 | 62.57 | 55.32 |
| RoG | 67.89 | 79.39 | 75.04 | 58.33 | 56.9 | 53.73 | 58.36 | 43.62 |
F.3 Performance on Multi-hop Reasoning
To demonstrate the effectiveness of multi-hop reasonings. We illustrate the F1 performance under different hops. From results shown in Table 16, we can observe that GCR also outperforms baselines in multi-hop reasoning.
Table 16: F1 comparison against RoG under different hops of reasoning.
| Methods | WebQSP | CWQ | | | | |
| --- | --- | --- | --- | --- | --- | --- |
| 1 hop | 2 hop | >=3 hop | 1 hop | 2 hop | >=3 hop | |
| GCR | 75.05 | 72.72 | - | 64.54 | 62.44 | 43.82 |
| RoG | 77.03 | 64.86 | - | 62.88 | 58.46 | 37.82 |
F.4 Logical Coherence in KG Reasoning Paths
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 is shown in Figure 8. The LLMs are asked to evaluate the logical coherence of the generated paths and provide a score from 1 to 5. 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.
Path Evaluation Prompt
⬇ ============================= Prompt Input ================================ 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 > ============================= LLM Output ================================ < Score >
Figure 8: The prompt template for path evaluation.
F.5 Analysis of the Failure Cases
Although GCR achieves 100% trustful reasoning, there are still some failure cases due to the noise and redundant information in KGs. Two failure cases are presented in Table 17. In the first case, the generated path is unrelated to the question. GCR provides a valid reasoning path that describes Anna Bligh’s political position, which lacks information about her electoral district. Although LLMs exhibit strong reasoning ability, they still cannot always find meaningful paths, resulting in incorrect answers. In the second case, the KG is incomplete, and the generated path does not contain facts for generating answers. Although KGs store abundant factual knowledge, there are still missing facts. Because there is no information about the character’s player stored in KGs, GCR cannot generate the correct answer. These failure cases indicate that the performance of GCR can be further improved by enhancing the reasoning ability of LLMs and the completeness of KGs.
Table 17: Failure cases predicted by GCR.
| Case 1: Generated paths are unrelated to the questions. | |
| --- | --- |
| Question | What electorate does anna bligh representt? |
| Answer | Electoral district of South Brisbane |
| Generated Path | Anna Bligh $→$ government.politician.government_positions_held $→$ m.0cr320w $→$ government.government_position_held.jurisdiction_of_office $→$ Queensland |
| Predicted answer | Queensland |
| Case 2: KG incompleteness. | |
| Question | who plays ken barlow in coronation street? |
| Answer | William Roache |
| Generated Path | Coronation Street $→$ tv.tv_program.program_creator $→$ Tony Warren $→$ fictional_universe.fictional_character_creator.fictional_characters_created $→$ Ken Barlow |
| Predicted answer | Ken Barlow |
Appendix G Limitations
In this section, we discuss the limitations and future directions of the proposed method.
- Definition of Zero-hallucination. This paper defines KG-constrained zero-hallucination as the generated reasoning paths are fully grounded in the KG. However, KGs often face issues of incompleteness and incorrect facts, leading to occasional false positives. Detecting such hallucinations without external evidence remains challenging, highlighting the potential of integrating cross-references from multiple knowledge sources—such as KGs, web data, and documents—to improve reasoning faithfulness.
- Time Complexity of Complex Questions. Highly complex questions usually require conduct reasoning with multiple steps. However, directly constructing a KG-Trie for a larger $L$ can be time-consuming. To address this, GCR can be integrated with existing planning-based methods to decompose complex questions into multiple shorter steps (Li et al., 2024). By breaking down the reasoning process, we can construct a KG-Trie with a smaller $L$ for each subtask to conduct reasoning, thereby reducing computational overhead while maintaining inference quality.
- Irrelevant Reasoning Path. As shown in Section F.5, although LLMs exhibit strong reasoning ability, they still cannot always find meaningful paths, resulting in incorrect answers. It is worth to investigate how to further improve the reasoning ability of LLMs, especially under the settings of incomplete knowledge graphs.
Appendix H Templates and Prompts
In this section, we illustrate all the templates and prompts used in the experiments.
Path Sentence Template. The template for converting reasoning paths into natural language sentences is shown in Figure 9, where the $e_{*}$ and $r_{*}$ denotes the entities and relations in a reasoning path ${\bm{w}}_{\bm{z}}=e_{0}\xrightarrow{r_{1}}e_{1}\xrightarrow{r_{2}}...%
\xrightarrow{r_{l}}e_{l}$ ,
Path Sentence Template
<PATH> $e_{1}$ $→$ $r_{1}$ $→$ $e_{2}$ $→$ $...$ $→$ $r_{l}$ $→$ $e_{l}$ </PATH>
Figure 9: The template for converting reasoning paths into formatted sentences.
Graph-constrained Decoding Prompt. The prompt for graph-constrained decoding is shown in Figure 10, where the question and mentioned entities are provided to the LLMs to generate reasoning paths and hypothesis answers. In the fine-tuning datasets, the supervised LLM outputs are constructed from the ground-truth answers and reasoning paths extracted from the KGs.
Graph-constrained Decoding Prompt
============================= Prompt Input ================================ Reasoning path is a sequence of triples in the KG that connects the topic entities in the question to answer entities. Given a question, please generate some reasoning paths in the KG starting from the topic entities to answer the question. # Question: <Question> # Topic entities: <Question Entities> ============================= LLM Output ================================ # Reasoning Path: <PATH> <Reasoning Path> </PATH> # Answer: <Hypothesis Answer>
Figure 10: The prompt template for graph-constrained decoding.
The few-shot prompt template for graph-constrained decoding is shown in Figure 12. We provide a few examples in the prompts to guide the LLMs to generate reasoning paths. Since the LLMs with few-shot prompt learning are not fine-tuned on the graph-constrained decoding task, we only apply the constraint to generate reasoning paths.
Graph Inductive Reasoning Prompt. The prompt for graph inductive reasoning is shown in Figure 11. We adopt the graph-constrained decoding to generate $K$ reasoning paths and hypothesis answers for each question. The reasoning paths and hypothesis answers are provided to the general LLMs to answer the questions without fine-tuning.
Path Evaluation Prompt. The prompt for evaluating the logical coherence of reasoning paths is shown in Figure 8. The LLMs are asked to evaluate the logical coherence of the generated paths and provide a score from 1 to 5.
Graph Inductive Reasoning Prompt
============================= Prompt Input ================================ # Reasoning Paths: <Reasoning Path 1><Hypothesis Answer 1> $...$ <Reasoning Path K><Hypothesis Answer K> # Question: <Question> Based on the reasoning paths, please answer the given question. Please keep the answer as simple as possible and only return answers. Please return each answer in a new line. ============================= LLM Output ================================ <Answer 1> <Answer 2> $...$
Figure 11: The prompt template for graph inductive reasoning.
Few-shot Graph-constrained Decoding Prompt
============================= Prompt Input ================================ Reasoning path is a sequence of triples in the KG that connects the topic entities in the question to answer entities. Given a question, please generate some reasoning paths in the KG starting from the topic entities to answer the question. Example 1 # Question: <Question> # Topic entities: <Question Entities> # Reasoning Path: <Reasoning Path> Example 2 # Question: <Question> # Topic entities: <Question Entities> # Reasoning Path: <Reasoning Path> Example 3 # Question: <Question> # Topic entities: <Question Entities> # Reasoning Path: <Reasoning Path> Input # Question: <Question> # Topic entities: <Question Entities> ============================= LLM Output ================================ # Reasoning Path: <Reasoning Path>
Figure 12: The few-shot prompt template for graph-constrained decoding.