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
Venue: ICML 2025 poster (2025)
Keywords: Large Language Model
Knowledge Graph
Primary area: deep_learning->large_language_models
TL;DR: We propose a novel framework called graph-constrained reasoning that eliminates hallucinations and ensures faithful reasoning by integrating the KG structure into the LLM decoding process.

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.

Despite their success, retrieval- based methods require additional accurate retrievers, which may not generalize well to unseen questions or account for the graph structure Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Linhao Luo"! 1 Zicheng Zhao 2 Gholamreza Haffari
Yuan-Fang Li
Chen Gong?
Shirui Pan
Abstract
1. Introduction
Large language models (LLMs) have demon- strated impressive reasoning abilities, but they still struggle with faithful reasoning due to knowl- edge gaps and hallucinations. To address these issues, knowledge graphs (KGs) have been uti- lized to enhance LLM reasoning through their structured knowledge. However, existing KG- enhanced methods, either retrieval-basee or agent- based, encounter difficulties in accurately retriev- ing knowledge and efficiently traversing KGs at scale. In this work, we introduce graph- constrained reasoning (GCR), novel framework that bridges structured knowledge in KGs with un- structured reasoning LLMs. To eliminate hallu- cinations, GCR ensures faithful KG- grounddd rea- soning by integrating KG structure into the LLM decoding process through KG-Trie, trie-based index that encodes KG reasoning paths. KG-Trie constrains the decoding process, allowing LLMs to directly reason on graphs and generate faith- ful reasoning paths grounded in KGs. Addition- ally, GCR leverages a lightweight KG-specialized LLM for graph-constrained reasoning alongside powerful general LLM for inductive reasoning over multiple reasoning paths, resulting in accu- rate reasoning with zero reasoning hallucination. Extensive experiments on several KGQA bench- marks demonstrate that GCR achieves state-of- the-art performance and exhibits strong zero-shot generalizability unseen KGs without additional training!.
Large language models (LLMs) have shown impressive rea- soning abilities in handling complex tasks (Qiao et al., 2023; Huang & Chang, 2023), marking a significant lapp that bridges the gap between human and machine intelligence. However, LLMs still struggle with conducting faithful rea- soning due to issues lack of knowledge and hallucination (Huang et al., 2024; Wang 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 informa- tion a structured format, to improve the reasoning abilitics of L.Mss (Pan et al., 2024; Luo et al., 2024). Nevertheless, because of the unstructured nature of LLMs, directly apply- ing 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- methods (Li et al., 2023; Yang et al., 2024b; Dehghan al., 2024) retrieve relevant facts from KGs with 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 agents that iteratively interact with KGs to find reasoning paths and answers.
Faithful Reasoning Path
Invalid Format Error
Invalid Relation Error
15.0%
18.0%
'Equal contribution Monash University "Nanjing University of Science and Technology 'Shanghai Jiao Tong University *Griffith University. Correspondence to: Shirui Pan <s.pan@griffth.edu..a nw..ino@monah..cuu..
(Mavromatis & Karypis, 2024). 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.,
67.0%
Conversely,
Linhao Luo <lin-
Figure Analysis of soning errors in RoG (Luo al., 2024).
Proceedings of the 42nd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
CCode and data available ptttpa:/githaai com/ RMan graph constra ned-neasoririeeeee reasoning

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
2024). Sui et al. (2024) indicates that RoG (Luo et al., 2024), leading KG-enhanced reasoning method, still experiences 33% hallucination errors during reasoning KGs, as shown in Figure 1.
2. Related Work
LLM reasoning. Many studies have been proposed to ana- lyze and improve the reasoning ability of LLMs (Wei et al., 2022: Wang et al., 2024b; Yao al., 2024). To elicit the reasoning ability of LLMs, Chain-of-thouge soning (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 con- sistent answer across them. The tree-of-though (Yao et al., 2024) structures reasoning as a branching process, exploring multiple steps in tree-like structure to find optimal solu- tions. Other studies focus fine-tuning LLMs various reasoning tasks to improve reasoning abilities ( (Yu et al., 2022; Hoffman et al., 2024). For instance, OpenAl (2024c) adopts reinforcement learning to train their most advanced LLMS called "OpenAl ol" to perform complex reasoning, which produces a long internal chain of thought before final answers.
To this end, we introduce graph-constraing reasoning (GCR), novel KG-guided reasoning paradigm that connects unstructured reasoning LLMs with structured knowledge in KGs, seeking eliminate hallucinations during reason- ing 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 de- coding process. This enables LLMs to directly reason on graphs by generating reliable reasoning paths grounded in KGs that lead to correct answers.
(CoT) rea-
In GCR, we first convert KG into a structured index, KG- Trie, to facilitate efficient reasoning KG using LLM. Trie is also known as the prefix tree (Wikipedia contributors, 2024) that compresses 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 pro- pose graph-constrained decoding that employs lightweight KG-specialized LLM to generate multiple KG-grounded reasoning paths and hypothesis answers. With the con- straints from KG-Trie, we ensure faithful reasoning while leveraging the strong reasoning capabilities of LLMs to ef- ficiently explore paths on KGs in constant time. Finally, we imput 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:
KG-enhanced LLM reasoning. To mitigate the knowledge gap and hallucination issues in LLM reasoning, research incorporates KGs to enhance L.LM 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 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 interact with KGs to find reasoning paths leading to the correct answers.
3. Preliminary
We propose a novel framework called graph- constrained reasoning (GCR) that bridges the gap be- tween structured knowledge in KGs and unstructured reasoning in LLMs, allowing for efficient reasoning KGs via LLM decoding.
Knowledge Graphs (KGs) represent a wealth of factual knowledge as a collection of triples: g = [(e,r, r,e') e & x R E), where and R denote the set of entities and relations, respectively.
Reasoning Paths are sequences of consecutive triples in KGs: W² eo 74 el 22 2n et, where (,, E G. The paths reveal the connections between knowledge that potentially facilitate reasoning. For example, the reasoning path: u² = Alice marry.to, Bob father.of 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 "Charlic".
We combine the complementary strengths of a lightweight KG-specialized L.M with powerful gen- eral LLM to enhance reasoning performance by lever- aging their respective graph- based reasoning and in- ductive reasoning capabilities.
We conduct extensive experiments several KGQA reasoning benchmarks, demonstrating that GCR not only achieves state-of-the-art performance with zero hallucination, but also shows zero-shot generalizabil- ity for reasoning on unseen KGs without additional training.
Knowledge Graph Question Answering (KGQA) is a representative reasoning task with the assistance of KGs. Given natural language question q and KG G, the task
2

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Knowledge Graph
General
KG specialized LLM
LLM Reasoning
LLM
Question
Answer
(a) Retrieval based LLM Reasoning
(b) Agent Agent-based LLM Reasoning
1776
Sasha Obama
Morther
Retrieved
Founded_in in
Obema t=2
Facts
LLM
LLM Agent
t=1
Ex-president
Spouse
A
Steps
Knowledge
Bormin in
Obama
Retriever
USA
Honolalu
(c) Ours: Knowledge Graph - constrainsdd LLM Reasoning
Knowledge Graph
1776
Spease
Lauts
Reasoning Paths and Hypothesis Answers
General LLM
Founded
Spacse_
presitene
Oburna
#7 Reasoning Path: Ex Se-president George W. Bush
Ee-presifent
Capital
Morry
Trurr
USA Spouze. of Laura Bush
Goraid Inump
Eeranfe
Trurro
Answer: Loura Bush
@ Trie Construction
craph-constrained becoding
f Reasoning Path:
KG-Trie Constraint
USA Speuse_ot Michelle Obama
president Barack Obama
4 Inductive Reasoning
t=2
Answer:
Michelle Oboma
Q: Who the spouse of the ex- president of USA?
R Reasoning Path:
A: Based on the paths, the answers are: Laura Bush, Michelle Obama, Melania Trump.
president Donald Trump
USA
Earry_to Molania Trump
KG-spccialized
Answer:
Melaria Trump
LLM
Figure Illustration of existing KG-enhanced LLM reasoning paradigms and proposed graph-come constrained reasoning (GCR), which consists of three main components: 1) Knowledge Graph Trie Construction: building 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.
aims to design function f to reason answers a A based on knowledge from G, i.e., a flg 9). The entities cg E Eg mentioned in q are linked to the corresponding entities in G, i.e., &g E.
reasoning steps 2 as
P(a = Σ Polalz, P((z2lg)))
|=
(I)
Σ Polalg 2) II Po(zala, 2w--1))
KG-constrained Zero-hallucination. As facts in KGs are usually verified, making them a reliable source for assessing the faithfulness of LLMM 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.
where g denotes the input question, a denotes the final an- swer, 0 denotes the parameters of LLMMs, and z; denotes the i-th step of the reasoning process To further enhance the reasoning ability, many previous works focus on improving the reasoning process (o l4) by exploring and aggregating multiple reasoning processes (Wang et al., 2024b; Yao et al., 2024).
4. Approach
Despite the effectivvness, major issue remains the faithful- ness of the reasoning process generated by LLMs (Huang et al., 2024). The reasoning is represented of tokens decoded step-by-step. which can accumulate er- rors 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.
4.1. From Shain-of-Thougeee Reasoning to Graph-constrained Reasoning
sequence
Chain-of-Thought Reasoning (CoT) (Wei et al., 2022) has been widely adopted enhance the reasoning ability of LLMs by autoregressively generating series of reasoning steps leading to the answer. Specifically, given question 4. CoT models the joint probability of the answer and
3

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
KG-enhanced Reasoning utilizes the structured knowledge in KGs improve the reasoning of L.MSs (Luo al., 2024; Sun et al., 2024), which can generally be expressed find- ing a reasoning path wy on KGs that connects the entities mentioned in the question and the answer. This can be formulated as
process can be formulated as:
W₂ BFS L),
(3)
T= = Tokenizer(Wa)),
(4)
Cs = (Tz)
(5)
where &g denotes all entities mentioned in the question, T. denotes the maximum hops of paths, and Tx denotes the tokens of reasoning paths. The KG-Trie Cg is used as a constraint to guide the LLM decoding process.
9) = Σ Pol wn Wx)Po(wxza, 9),
By constructing KG-Trie for each question entity, we can enable efficient traversal of reasoning paths in constant time (O(IW+))) 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- propprosssiing time. Detailed dis- cussions on construction efficiency and potential solutions for further improvements to scale into real-world applica- tions is available in Appendix B. This significantly reduces the computational cost and latency of reasoning on KGs, making it feasible for real-time applications.
where (s(wz q, 9) denotes the probability of discovering a reasoning path w2 on KGs 9 given the question by a function parameterized by Φb To acquire reasoning paths for reasoning, most prior studies follow the retrieval-based (Li et al., 2023) or agent-based paradigm (Sun al., 2024), as shown in Figure 2 (a) and (b), respectively. Nevertheless, retrieval-bee 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).
craph-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.3. Graph-constrained Decoding
Large language models (LLMs) have strong reasoning ca- pabilities but still suffer from severe hallucination issues, which undermines the trustworthiness of the reasoning pro- cess. 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 answers.
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 structured index of KGs to facilitate efficient reasoning on graphs using LLMs.
Given a question g, design an instruction prompt to har- ness the reasoning ability of LLMs to generate reasoning paths wy and hypothesis answers a. To eliminate the hal- lucination during reasoning on KGs, we adopt the KG-Trie Cg as constraints to guide the decoding process of LLMs and only generate reasoning paths that are valid in KGs, formulated as:
A Trie (a.k.a. prefix tree) (Wikipedia contributors, 2024; Fredkin, 1960) is a tree-like data structure that stores a dy- namic set of strings, where each node represents common prefix of its children. Tries can be used to restrict LLM out- put 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.
Regular decoding
(a wz1g) (alq wz)
w.
Po (w., lg, Wane (Co(ws, [ws (6)
Grapb-comstrained decoding
1, S..refix wz),Ew, Ewwz E We
Co(we,Wwant
(7)
0, clse,
Given a KG & and question g, we first retrieve paths W₂ within L hops starting from entities mentioned in the question e, E Eg. 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 L.LM and stored as a KG-Tric Cg. The overall
where Ws. denotes the i-th token of the reasoning path Wz, Pd denotes the token probabilities predicted by the LLM with parameters o, and Cg(w,, [Wa::-)) denotes the con- straint function that checks whether the generated tokens W...; is a valid prefix of the reasoning path using KG-Triee After valid reasoning path is generated, we switch back to the regular decoding process to generate a hypothesis answer conditioned on the path.
4

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
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.
Prompe Toput Please geacrate some reasoning paths in the KG starting from the topic entities answer the question.
# Question: what is the name of justin bicber brother?
LLM Output
Reusoming Path; <PATH> Justin Bjeber people--erson, parents pereppeeonnprretttsss...
Jeremy Bieher = ceople.prson.cciieee - Jaxon Bieher </FATH>
Answer: Jaxon Bieber
An example of the graph-constrained decoding. Detailed prompts can be found in Figure 10.
Figure 3.
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 paral- lel computation. Thus, given a question, we adopt graph- constrained decoding to simultaneously generate K' reason- ing 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:
To further enhance KG reasoning ability, we fine-tune lightweight KG-specialized LLM with parameters & on the graph-constrained decoding task. Specifically, given ques- tion q, the LLM is optimized to generate relevant reasoning paths w2 that are helpful for answering the question, then provide a hypothesis answer a based on it, which can be formulated as:
L= a) log (a u2lg))
3K= = {a wh arg top- Pa wz w= 4),
(9)
[wal
(8)
K II
E
log Poladl W2, 01:-11 II (o la Mag-n)
Po(Alg, 2k) ~
Po a², w k=1
(10)
where a, and way denote the i-th token of the answer and the j-th token of the reasoning path wz, respectively.
where A denotes the parameters of the general LLM, 2x denotes the set of top- reasoning paths and hypothesis answers, and A denotes the final answers.
The training data (g. W2,a) E DD consists of question- answer pairs and reasoning paths generated from KGs. We use the shortest paths connecting the entities in the ques- tion and answer as the reasoning path wz for training, where details can be found in Appendix C. An example of graph-constrained decoding is illustrated in Figure 3, where <P <PATH> and </PATH> are special tokens to control the start and end of graph-constrained decoding. Experi- ment results in Section 5.2 show that even a lightweight KG-specialized LLM (O.5B) can achieve satisfactory perfor- mance in KG reasoning.
We follow the FiD framework (Izacard & Grave, 2021; Singh al., 2021) to incorporate multiple reasoning paths and hypothesis answers to conduct inductive reasoning within one LLM call, i.e., Po g, Zx), where detailed prompts can be found in Figure 11. The general LLM can be any powerful I.LM, such as ChatGPT (OpenAI, 2022), or Llama-3 (Meta, 2024), which can effectively leverage their internal reasoning ability to reason over multiple rea- soning paths to produce final answers without additional fine-tuning.
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 un- structured 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.
5. Experiment
In our experiments, we aim to answer the following re- search questions: RQI: Can GCR achieve state-of-the- 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
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.
4.4. Graph Inductive Reasoning
Graph-conse Craph-constrained decoding harnesses the reasoning ability of a KG-specialized LLM to generate a faithful reasoning path and a hypothesis answer. However, complex reason- ing tasks typically admit multiple reasoning paths that lead
5

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Table Performance comparison with different basclines the two KGQA datasets.
WebQSP
CWQ
Types
Methods
Hit
F1
Hit
F1
Qwen2-0.5B (Yang al., 2024a)
26.2
17.2
12.5
11.0
Qwen2-1.55 (Yang al., 2024a)
41.3
28.0
18.5
15.7
Qwen2-7B (Yang al., 2024a)
50.8
35.5
25.3
21.6
Llama L-7ma-2-7B (Touvron et al., 2023)
56.4
36.5
28.4
21.4
LJama-3.1 3-88 (Meta, 2024)
55.5
34.8
28.1
22.4
LLM Reasoning
GPT-4o-mini (OpenAI, 2024a)
63.8
40.5
63.8
40.5
ChatGPT (OpenAI, 2022)
59.3
43.5
34.7
30.2
ChaGGPT-Fow-hott (Brown et 2020)
68.5
38.1
38.5
28.0
ChaGPTTCCo (Wei al., 2022)
73.5
38.5
47.5
31,0
ChuGPTT-Sef-CConsstenny (Wang al., 2024b)
83,5
63.4
56,0
48.1
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
Graph Reasoning
SR+NSM (Zhang et al., 2022)
68.9
64.1
50.2
47.1
ReaRey (Mavromatis & Karypis. 2022)
76.4
70.9
52.9
47.8
UuiKGQA (Jiang
2022)
77.2
72.2
51.2
49.1
KD-Cod (Wang et al., 2023)
68.6
$2.5
55.7
EWEK-QA (Delghan al., 2024)
71.3
$2.5
ToG (ChaiGPT) (Sun al., 2024)
76.2
57.6
ToG (GPT-4) (Sun al., 2024)
82.6
68.5
EMAQ (Dong et al., 2024)
82.9
69.5
KG+LLM
RoG (Lluma-2-7BB (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 (Mavromaris Karypis, 2024)
90.7
73.5
68.7
60.4
(Llama 3.1 8B CharGPT)
92.6
73.2
72.7
60.9
(Lluma-3. GPT-4o-mini)
92.2
74.1
75.8
61.7
To further evaluate the generalizability of GCR, 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 al., 2021). The details of the datasets are described in Appendix C.
GPT (OpenAI, 2022) and GPT-4o-mini (OpenAI, 2024a) as the general L.MSs for inductive reasoning. The detailed hyperparameters and experiment settings are described in Appendix E.
5.2. RQ1: Reasoning Performance and Efficiency
Main Results. In this section, we compare GCR with other baselines on KGQA benchmarks to evaluate the reason- ing performance. From the results shown in Table 1, GCR achieves the best performance on both datasets, outperform- ing the second-best by 2.1% and 9.1% 3.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-a reasoning performance.
Baselines. We compare GCR with the 22 baselines grouped into three categories: 1) I.IM 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 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-choit QA datasets, we adopt accuracy as the evaluation metric.
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 struc- tured data. Graph reasoning methods, such as ReaRev, achieve competitive performance on WebQSP by explic- itly modeling the graph strueture. But they struggle to generalize across different datasets and underperform on CWQ. In KG+LLM methods, both agent-based methods (c.g., ToG, EffiQA) and retrieval-based methods (c.g.. RoG, GNN-RAG) achieve the second-best performance. Nev- ertheless, they still suffer from inefficiency and reasoning hallucinations which limit their performance. In contrast,
Implementations. For GCR, we use the KG-Trie to index all the reasoning paths within 2 hops starting from ques- tion entities. For the LLMs, we use a fine-tuned Llama- 3-8B (Meta, 2024) as the KG-specialized LLM. We gen- erate top- reasoning paths and hypothesis answers from graph-constrained decoding. We adopt the advanced Chat-
6

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Table 2. Efficiency and performance comparison of different methods on WebQSP.
Types
Methods
Hit
Avg. Runtime (S)
Avg.
L.LM Calls
Avg. I.M Tokens
S.Ber
66.9
0.87
1
293
BGE
72.7
1,05
1
357
Retrieval-based
OpenAI-Emb.
79.0
1.77
1
330
GNN-RAG
85.7
1.52
1
414
RoG
85.7
2,60
2
521
ToG
75.1
16.14
11.6
7,069
Agent-based
EMQA
82.9
7.3
Ours
GUR
92.6
3.60
2
231
Table 3. Ablation studies of GCR two KGQA datasets.
GCR effectively eliminates hallucinations and conducts faith- ful reasoning by leveraging the structured KG index and graph-constrained decoding.
WeaQSP
CWQ
Variants
F1
Precision
Recall
F1
Procision
Recall
GCR (Llama-3.1133 ChT)
73.2
80.0
76.9
60.9
61.1
66.6
GCR w/ spespiiill LLM
52.9
66.3
50.2
37.5
40.8
37,9
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), OpenAl- 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 LLMSs for reasoning answers. For based methods, we compare with ToG (Sun et al., 2024) and Er- fiQA² (Dong et al., 2024), which heuristically search on KGs for answers. The detailed settings are described in Appendix E.
GCR ayo General LLM
57.0
$8.0
70.1
39.4
32.8
61.3
general LLM in GCR. As shown in Table 3. the full GCR achieves the best performance on both datasets. By remov- ing 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 rea- soning 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 L.LM for conducting inductive reasoning over multiple paths to derive final answers.
Dense retrievers are most efficient in terms of runtime and LLM calls they convert all paths into sentences and en- code them as embeddings in advance. However, they sacri- fice 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 it- erative 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 anal- ysis under different beam sizes used for graph-constrained decoding can be found in parameter analysis.
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 differ- ent LLMs to conduct graph-constrained decoding and use ChatGPT the general LLM for final reasoning. For gen- eral LLMs, we adopt the same reasoning paths generated by --eppccillzzed 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.
Results in Table 4 show that lightweight L.MM (0.5B) can outperform 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. 3.1--8.)1))) 1-8B), showcasing their stronger inductive reasoning abilities. This further emphasizes the need of paring powerful general LLMs with lightweight XGG-specialized LLMs to achieve better reasoning driven by both of them.
A blation Study. We first conduct an ablation study to an- alyze the effectiveness of the KG-specialized LLM and
"Since there is no available code for EffiQA, we directly copy the results from the original paper.
7

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Table Comparison of different L.LMs used in GCR.
Faithful Reasoning
Error Reasoning
Components
Learning Types
Variants
Hit
WebQSP
CWQ
Zero-shot
Llama-3.1-708
Lluma-3.1-88
38.53
28.25
10.32
12.53
Answer Hit
60
100.0%
60
100.0%
Llama-3.1
33.24
11.19
40
62.4%
Answer
40
48.1%
Few-shot
KGG-specialized
Llama-3.
1--00-
41.13
13.14
20-
20
LLM
Qwen2-0.55
87.48
Qwen2-I.5B
89.21
62.97
GCR GCR w/o comstriii
GCR GCR wio constrain
Fine-tuned
Qwen2-7B
92.31
72.74
Llama- 2-7B
92.55
73.23
Figure 5. Analysis of performance and reasoning errors in GCR.
I.aama3331
92.74
73.14
Qwen-2-7B
86.32
67.59
reasoning performance and efficiency by setting L = 2 and
Llama-3.1-88
90.24
71.19
General LLM
Zero-shot
Llama-3.1-77 1-70BB
89.85
71.47
K = 10.
ChatGPT
92.55
73.23
GPT-4o-mini
92.23
74.05
5.3. RQ2: Hallucination Elimination and Faithful Reasoning
Generation Time (8)
Precision
In this section, we investigate the effectiveness of KG con- straints in eliminating hallucinations and ensuring faithful reasoning. We first compare the difference of answer ac- curacy (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 rea- soning as faithful where the generated reasoning path can be found in KGs, and vice versa.
Hit
Recall
F1
Generation Time (8)
90
Answer Coverage (%)
8D
70
40
From the Figure we can observe that GCR achieves the 100% faithful reasoning ratio both datasets, which in- dicates 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 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 L.MSs 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).
Graph-constrained decoding beam size
Figure 4. Parameter analysis of beam size K.
Parameter Analysis. We first analyze the impact of dif- ferent beam sizes K for graph-constrained decoding on the performance of GCR. We conduct the experiments on We- bQSP 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 Fl score, peaks when the beam size is set to 10. This is because the beam size of 10 can provide a balance between the explo- ration and exploitation of the reasoming paths. When the beam size is set to 20, the performance drops due to the increased complexity of the search space, which may in- troduce noise and make the reasoning less reliable. This also highlights the importance of using general LLMs to conduct inductive reasoning over multiple paths to disre- gard the noise and find the correct answers. Although the graph-constraing 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 Appendix F. The results show that GCR can achieve a good balance between
Case Study. We further provide 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 gen- erates an incorrect reasoning path leading to an incorrect answer by hallucinating facts such as "Mabel Rose Fergu- son is the child of Naill Ferguson and her parent is Alyssa Mastromonaco". In contrast, GCR generates a faithful rea- soning path grounded in KGs that "Naill Ferguson has a child named Thomas Ferguson who has 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 L.M answers the question cor-
8

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Table 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
Reasoning Path: Niall Ferguson - ceopleepersonnchildren - Mabel Rose Ferguson +
GCR w/o constraint
pecple.person.pee. parentssaaa--teeeee Alyssa Mastromonaco
#Answer: Alyssa Mastromonaco
Reasoning Path: Niall Ferguson - people.person..hhldeen Thomas Ferguson
GCR
people.person.pacee pareents - 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
Reasoning Path: JaMarcus Russell people.person.placee of birth - Tampa
GCR w/o constraint
#Answer: Mobile, Alabama
Reasoning Path: JaMareus Russell >> people.person.place .ff birth + Mobile
GCR
#Answer: Mobile
Table 6. Zero-shot transterability to other KGQA datasets.
in accuracy on Freebase 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, medi- cal KGs are more specialized and require domain-specinf knowledge for reasoning, potentially limiting the generaliz- ability of our method.
Model
FreebascQA
CSQA
McdQA
ChatGPT
85
GCR (ChatGPT)
92
66
GPT-4o-mini
89
91
75
GCR (GPT-4o-mini)
94
79
rectly, the generated reasoning path is still hallucinated with incorrect facts. Conversely, GCR conducts faithful reason- ing with both correct answer and reasoning path. These results demonstrate that GCR can effectively eliminate hal- lucinations and ensure faithful reasoning by leveraging KG constraints in graph-constrained decoding.
6. Conclusion
5.4. RQ3: Zero-shot Generalizability to Unseen KGs
In this paper, we introduce novel LLM reasoning paradigm called graph-constrained reasoning (GCR) to eliminate hal- lucination 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 in- dex. KG-Trie constrains the decoding process to guide a KG-specialized LLM to generate faithful reasoning paths grounded in KGs. By imposing constraints, can not only eliminate hallucination in reasoning but also reduce the reasoning complexity, contributing more efficient and accurate reasoning. Last, a powerful general LLM is uti- lized as a complement to inductively reason over multiple reasoning paths to generate the final answer. Extensive experiments demonstrate that GCR excels in faithful rea- soning and generalizes well reason on new KGs without additional fine-tuning.
In GCR, the knowledge graph is converted into a constraint which is plugged into the decoding process of LLMs. This allows GCR to generalize unseen KGs without further training. To evaluate the generalizability of GCR, we con- duct 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-83 1--8B) trained on Freebase as well as two general L.MSs (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.
From the results, is evident that GCR outperforms Chat- GPT and -Pi--o-mini in zero-shot performance on both datasets. Specifically, GCR shows 8.2% and 7.6% increase

---

Graph-constraineed Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Acknowledgment
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 Pupers). pp. 14169-14187, Bangkok, Thailand, August 2024. Association for Computational Linguisties. URL https: http//attaaaaacaccac/ata org/ 2024. aa..aacl--0 aalaacllloo long. 764.
Haffari is supported by the DARPA Assured Neuro Symbolic Learning and Reasoning (ANSR) program un- der 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 ST21010009) and DP240101547 and the CSIRO National Science Foundation (US) AI Research Collabora- tion Program.
Dhuliawala, S., Komeili, M., Xu, J., Raileanu, R., Li, X., Celikyilmaz, A., and Weston, J. E. Chain-of- veriffiaiat reduces hallucination in large language models. In ICLR 2024 Workshop on Reliable and Responsible Foundation Models.
Impact Statement
Our research focuses exclusively scientific questions, with no involvement of human subjects, animals, or envi- ronmentally sensitive materials. Therefore, we foresee no ethical risks or confficts of interest. We are committed to maintaining the highest standards of scientific integrity and ethics to ensure the validity and reliability of our findings.
Dong. Z., Peng, B., Wang. Y., Fu, J., Wang. X., Shan, Y., and Zhou, X. Effiqa: Efficient question-answering with strategic multi-mode collaboration on knowledge graphs. arXiv preprint arXiv:2406.00 0/238, 2024.
References
Erling, O. and Mikhailov, I. Rdf support in the virtuoso dbms. In Networked Knowledge-Neworrel Media: Inte- grating Knowledge Management, New Media Technolo- gies and Semantic Systems, pp. 7-24. Springer, 2009.
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.12116 2024.
Evans, S. B. Intuition and reasoning: draceps perspective. Psychological Inquiry, 21(4):113-36,, 2010.
Bollacker, K., Evans, C., Paritosh, P., Sturge, T., and Taylor, J. Freebase: 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.
Federico, M., Cettolo, M., Brugnara, F., and Antoniol, G. Language modelling for efficient beam-search. Computer Speech and Language, 9(4):353 -355-00---11- 1995.
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.
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.
Fredkin, E. Trie memory. Communications of the ACM, (9):490-499, 1960.
Chen, C., Wang, Y., Li, B., and Lam, K.-Y. Knowledge is flat: A seq2seq generative framework for various knowl- edge graph completion. In Proceedings of the 29th Inter- national Conference on Computational Linguistics, pp. 4005 4017, 2022.
He, G., Lan, Y., Jiang, J. Zhao, W. X., and Wen, J.-R. Im- proving 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.
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 Pro- cessing Systems.
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 Pro- cessing Systems, 36, 2024.
De Cao, N., Izacard, G., Riedel, S., and Petroni, F. Autore- gressive entity retrieval. In International Conference on Learning Representations, 2022.
Huang, J. and Chang, K. C.-C. Towards reasoning in large language models: A survey. In Findings of the Asso- ciation for Computational Linguistics: ACL 2023, pp. 1049-1065, 2023.
Dehghan, M., Alomrani, M., Bagga, S., Alfonso-Hoere Hermme,, D., Bibi, K., Ghaddar, A., Zhang, Y., Li, X., Hao, J.,
10

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Huang, J., Chen, X., Míshra, 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.
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 reason- ing. In Proceedings of the 46th international ACM SIGIR conference on research and development in information retrieval, pp. 1559-1568, 2023.
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 Linguisties: Main Volume, pp. 874-880) 880, 2021.
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 modal knowledge graph reasoning. In Proceedings of the 32nd ACM International Conference on Multimedia, pp. 1554- 1563, 2024.
Jiang, J., Zhou, K., Zhao, X., and Wen, J.-R. Unikgqa: Uni- fied retrieval and reasoning for solving multi-hop ques- tion answering over knowledge graph. In The Eleventh International Conference on Learning Representations, 2022.
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.
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 Empirical Methods in Natural Language Processing, pp. 9237-9251, 2023.
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 Rep- resentations, 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 reasoming over knowledge graph. arXiv preprint arXiv:2402. 163, 2024.
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.011 2025.
Jinng 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 Com- putational Linguistics: Human Language Technologies, Volume I (Long and Short Papers), pp. 318-323, 2019.
Lv, Q., Wang, J., Chen, H. Li, B., Zhang. Y., and Wu, F. Coarse-to-fine highlighting: Reducing knowl- edge hallucination in large language models. In Forty- first International Conference on Machine Learning, 2024. URL https:/ openrevieww net/ forum? i 1d=JCGOKTPVYY.
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.
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 flex- ible and reliable reasoning framework for large language models. arXiv preprint arXiv:2409.03755. 2024.
Li, S., Gao, Y., Jiang, H., Yin, Q., Li, Z., Yan, X., Zhang, C., and Yin, B. Graph reasoning for question answering with triplet retricval. In Findings of the Association for Computational Linguistics: ACL 2023, pp. 3366-3375 2023.
Mavromatis, C. and Karypis, G. Rearev: Adaptive reason- ing for question answering over knowledge graphs. In Findings of the Association for Computational Linguis- tics: EMNLP 2022, pp. 2447-2458, 2022.
Li, Y.. Song. D., Zhou, C., Tian, Y., Wang, H., Yang, Z., and Zhang, S. A framework of knowledge graph eeahnee large language model based on question decomposition and atomic retrieval. In Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 11472- 11485, 2024.
Mavromatis, C. and Karypis, G. Gnn-rag: Graph neural re- trieval for large language model reasoning. arXiv preprint arXiv:2405.201 2024.
Meta. Build the future of ai with meta Ilama 3, 2024. URL. https: // 1///1aa00 llama, met com ama
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.
Nguyen, T., Luo, L., Shiri, F., Phung, D., Li, Y.-F, Vu, T.-T., and Haffari, G. Direct evaluation of chain-of-thougle in multi-hop reasoning with knowledge graphs. In Ku, L.-W., Martins, A., and Srikumar, V. (eds.), Findings

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
of the Association for Computational Linguistics ACL 2024, pp- 2862-2883, Bangkok, Thailand and virtual meeting, August 2024. Association for Computational Linguistics. URL https::t////t. http///aaaantooooo org/ 2024. f Findings-aaann 68.
Sun, H., Dhingra, B., Zaheer, M., Mazaitis, K., Salakhutdi- nov, R., and Cohen, W. Open domain question answering using early fusion of knowledge bases and text. In Pro- ceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 4231-4242, 2018.
OpenAL. Introducing chatgpt, 2022. URL https://
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 knowl- edge graph. In The Twelfth International Conference on Learning Representations, 2024.
OpenAl. Hello gpt-4o, 2024a. URL https: https::/openai. openai. homm/inndexhelloopptttoe
OpenAl. New embedding models and api updates,
2024b. URL https://openai..eo com index/
Talmor, A. and Berant, J. The web 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 (Long Papers), pp. 641-651, 2018.
new-enbeddingg-oooee -addaaa---mmo-------------------
OpenAI. Learning to reason with 1lms, 2024c. URL
https://opene com/ index/ learning-te to- reason- teraasoott-rr-ooo------- with 11ms/.
Pan, S., Luo, L., Wang, Y. Chen, C.,, Wang, J., and Wu, X. Unifying large language models and knowledge graphs: A roadmap. IEEE Transactions Knowledge and Data Engineering (TKDE), 2024.
Talmor, A., Herzig, J., Lourie, N., and Berant, J. Com- monsenseqa: A question answering challenge targeting commonsense knowledge. In Proceedings of the 2019 Conference of the North American Chapter of the Associ- ation for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pp. 4149 4158, 2019.
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 Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. $368-5393, 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.
Reimers, N. and Gurevych, Sentence-bert, Sentence em- beddings using siamese bert-networks. In Proceedings of the 2019 Conference on Empirical Methods in Natu- ral Language Processing. Association for Computational Linguistics, 11 2019. URL abs/1908 10084.
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 rea- soning. Thirty-Eighns Annual Conference on Neural In- formation Processing Systems, 2024a.
Singh, D., Reddy, S., Hamilton, W., Dyer, C., and Yogatama, D. End-to-end training of multi multi-document reader and retriever for open-domain question answering. Advances in Neural Information Processing Systems, 34:25968- 25981, 2021.
Wang, K., Duan, F., Wang, S., Li, P., Xian, Y., Yin, C., Rong, W., and Xiong, 7. Knowledge-drive cot: Exploring faith- ful reasoning in Ilms for knowledge-intensive question answering. arXiv preprint arXiv: 13259, 2023.
Speer, R., Chin, J., and Havasi, C. Conceptnet 5.5: An open multilingual graph of general knowledge. In Pro- ceedings of the AAAI conference on artificial intelligence, volume 31, 2017.
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 lan- guage models. In The Eleventh International Conference on Learning Representations, 2024b
Stanovich, K., West, R., and Hertwig, R. Individual dif- ferences in reasoning: Implications for the rationality debate?-open peer commentary-the questionable utility of cognitive ability in explaining cognitive illusions. 2000.
Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F,, Chi, E., Le, Q. V., Zhou, D., et al. Chain-of-thougih prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35: 24834-24837, 2022.
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.1 13873, 2024.
12

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Wikipedia contributors.
Trie. https://en.
Yu, Wang, T., Golovneva, O., AlKhamissi, B., Verma, S., Jin, Z.,, Ghosh, G., Diab, M., and Celikyilmaz, A. Alert: Adapting language models reasoning tasks. arXiv preprint arXiv:2212.08286. 2022.
wi wikipedia www..//ii//rrrriee... 2024. Accessed:
2024-09-11.
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Philip, S. Y. A comprehensive survey on graph neural networks. IEEE transactions neural networks and learning sys- lems, 32(1):4-22) 2020.
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 Pro- ceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume Long Pupers), pp. 5773-5784, 2022.
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.
Zhang, P., Xiao, S., Liu, Z., Dou, Z., and Nie, J.-Y. Re- trieve anything to augment large language models. arXiv 2023.
preprint arXiv:2310.075::
Xie, X., Zhang, N., Li, Z., Deng, S., Chen, H., Xiong, F., Chen, M., and Chen, H. From discrimination to gen- eration: Knowledge graph completion with generative transformer. In Companion Proceedings of the Web Con- ference 2022, pp. 162-165, 2022.
Zhu, Y., Qiao, S., Ou, Y., Deng, S., Zhang, N., Lyu, S., Shen, Y., Liang, L., Gu, J., and Chen, H. Knowagent: Showledge-augmenter augmented planning for lIm-based agents. arXiv preprint arXiv:2403. 03110001.11,,,000 2024.
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.1066
2024a.
Yang. R., Liu, H., Zeng, Q. Ke, 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 preprinl MrXiv:2403.058811 2024b.
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, M., Ren, H., Bosselut, A., Liang, P., and Leskovec, J. Qa-gnn: Reasoning with language models and knowledge graphs for question answering. In Pro- ceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 535-546, 2021.
Yih, W.t., Richardson, M., Meek, C., Chang, M.-W., and Suh, J. The value of semantic parse labeling for know]- edge base question answering. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 201 201-206, 2016.
13

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Appendix
Table of Contents
Detailed Related Work on KG-enhanced LLMs
B KG-Trie Construction
15
B.1 Construction Strategies
15
B.2 Time and Space Complexity Analysis
15
B.3 Strategies for Optimizing Efficiency...
Real-World Applicability
C Datasets
18
D Baselines
19
E Implementation Details and Experiment Settings
20
F Additional Experiment Results
21
F.I Performance on Different Hops KG-Trie
21
F2 Performance Multi-path Reasoning
22
F3 Performance Multi-hop putti-hop Reasoning
22
F4 Logical Coherence in KG Reasoning Paths
22
F5 Analysis of the Failure Cases
22
Limitations
22
H Templates and Prompts
23
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 al., 2024) by reducing the hallucinations (Nguyen al., 2024; Dhuliawala et al.; Ly al., 2024). In this section, provide detailed review of the related work KG-enhanced LLMs, which can be categorized into paradigms: retrieval-based and agent-based 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 al., 2024) proposes a planning-retriees ectrieval-reasoning framework that retrieves reasoning paths from KGs guide LLMs conducting faithful reasoning. GNN-RAG (Mavromatis & Karypis, 2024) adopts 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.
14

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Agent-based Methods. Agent-based methods treat LLMs as agents that iteratively interact with KGs to find reasoning paths and answers. For example, StruetGPT (Jiang et al., 2023) treats LLMs agents to interact with KGs find 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. EfñiQA (Jiang et al., 2024) proposes an efficient agent-based method to reason on KGs. Plan-on-Grrahh (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.
B. KG-Trie Construction
KG-Trie converts KG structures into the format that LLMs can handle. can been incorporated into the LLM decoding process as constraints, allowing for faithful reasoning paths that align with the graph's 's structure. The KG-Trie can be either pre-computed for fast inference or constructed on-demand 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, the frequency of their occurrence in the questions.
On-demand Construction. Alternatively, we can construct the KG-Trie on-demand. When 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 L.LSs 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 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 question-specift KG-Trie on-demand. The cache can be updated periodically to remove the least frequently used KG-Trie and add the new ones.
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-fin first search, whose complexities are:
1.2.1. THEORETICAL ANALYSIS
Time Complexity. Constructing the KG-Trie involves a BFS traversal to explore paths up a maximum length of L starting from certain entities. The time complexity of this traversal is O(E"), 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(FL T), where 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.
15

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Q: Who is the president
Australia?
Entity Recognition
Graph craph-constrained
Q
Trie
Q: Who is the spouse of the ex- president of USA?
Reasoning
Australia
USA
Return Trie
User Queries
KG- Trie Cache
KG-Trie Cache
Cache
Key
Value
Update
Key
Value
Australia
Trie 1
Australia
Trie 1
China
Trie 2
China
Trie 2
Initialization With Popular Entities
USA
Trie
Cache Management
USA
Graph Retrieval
KG-Trie Construction
KG storage
Question-related subgraph
KGiTrie
Figure 6. The illustration of dynamic cache KG-Trie construction.
Table System settings overview 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 rumning time and space consumption. The BFS is executed on the Freebase KG stored 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 <= which highlights efficiency KG-Trie construction. Although larger hop can lead to better coverage of the possible answer, it would significantly increase the time and space complexity. Thuus set hops to 2 or 3 in experiments balance between efficiency and effectiveness. Notably, time can be further reduced by utilizing multi-threading. Space consumption can be optimized by storing data in database.
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- 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.
B.3. Strategies for Optimizing Efficiency
We provide several strategies that can be used to further speed up the KG-Trie construction.
16

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Table 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
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 entitics in user questions
Spacy
0.0059
Entity Linking (NI.)
Link to entities KGs
ColBERTv2
0.0457
Graph Retrieval
Retrieve question relevant subgraphs for <rie construction (Ezy. 3).
2-hup BFS implemented with SPARQL.
0,0133
Tokenizer
Tokenize paths into tokens for building LLM constraints (Bq. 4).
Llama-3-8B Tekenizer implemented by Huggingface.
0.1227
Trie construction
Store the tokenized paths with Tric (Eq.
Python MARISA Trie
0.0962
Total
0.2838
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%
The BFS 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.
Efficiency Graph Traversal Algorithms:
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, could only construct the KG-Trie for certain entities. We can select the entities based on their popularity, importance, 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 industrial-leved 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-processo prepprocssiing 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
17

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
C. Datasets
KGQA Datasets. To compare the reasoning performance with existing methods, we use two benchmark KGQA datasets in this study: WebQuestionSP (WebQSP) (Yih 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 al., 2024). Details of the datasets be found in Table 11.
Both WehQSP and CWQ can be reasoned using Freebase KGs (Bollacker et al., 2008). To reduce the size of the KGs, we use subgraph of Freebase by extracting all triples that start from question entities within the maximum reasoning hops provided by previous works* (Luo et al., 2024). The statistics of the knowledge graphs are shown in Table 13.
Fine-tuning Datasets. enhance the KG reasoning ability of LLMs, we construct ane-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 cesitioonanswer pairs, respectively. For each question, the question entity to the answer entity. We then convert the reasoning paths into formatted strings and pair them with the question-answe 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 guestion-reasonie path-answer triples for WebQSP and CWQ, respectively. The statistics of the fine-tuning datasets are shown in Table 12.
find all the shortest reasoning paths on KGs that connect
Zero-shot Generalization Datasets. To evaluate the transferability of GCR, further select three new KGQA datasets: FreebaseQA (Jiang et al., 2019), CommonsenseQA (CSQA) (Talmor et al., 2019) and MedQA-USMLE (MedQA) (Jin et al., 20 FreebaseQA is open-ended question answering dataset. CSQA is a 5-way multiple choice QA dataset that involves reasoming with commonsense knowledge. MedQA is 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 general-purre 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), 2-hop subgraph is extracted from the KGs to form the zero-shot generalization datasets.
Table 11. Statistics of datasets.
Dataset Statistics
Statistics of Answer Numbers
Dataset
#Train
#Test
#Ans =1 2 #Ans < 4
2 #Ans 9
#Ans 2 10
WebQSP CWQ
2,826
1,628
51.2%
27.4%
8.3%
12.1 1%
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
"WehQSP: https: http:///wgggggga....caaaaatettte http://setteemmaeee/////e//e RRGg//GGG-eeppp CWQ:
datasets//mannuo//Reee
18

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
D. Baselines
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:
Owen2-0.5B/L.5B. (Yang al., 2024a) provides 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 diverse range of tasks.
Llama-3.1-8B (Meta, 2024) 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 (OpenAl, 2024a) is the new flagship model of OpenAl that could reason across different modalities and tasks.
Few-shot prompt (Brown et al., 2020) is few-shot learning method that provides LLMs with a few examples in the prompts to conduct reasoning.
CoT (Wei et al., 2022) is chain-of thain-tf 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 KGs using graph neural networks (GNNs) (Wu al., 2020) or graph-based reasoning mechanisms. We include the following baselines:
GraftNet (Sun et al., 2018) is a graph-based reasoning method that retricves relevant subgraphs from KGs with entity linking.
NSM (He 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 GNN-based method that reasons KGs by considering complex graph information.
UniKGQA (Jiang et al., 2022) 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 based paradigms. We include the following baselines:
Retrieval-bune 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-QL -AA (Dehghan et al., 2024) enriches the retrieved knowledge by searching from both KGs and web.
RoG (Luo et al., 2024) proposes plamiin--rrriivvllreeonnng 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.
19

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Table 14. Training time and memory usage for different KG-specialized LLMss.
Model
Time
Mem. Usage per GPU
Qwen2-0.5B
3,47h
10G
Qwen2-1.5
4.11h
25G
Qwen2-7B
14.37h
81G
Llama-2-7B
13.93h
80G
Llama-3.1-8B
14.52h
85G
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 agents that iteratively interact with KGs to find reasoning paths and answers:
ToG (Sun al., 2024) conducts the reasoning 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 reason on KGs.
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 set to 4 and the learning rate set to 2e-5, We use the cosine learning rate scheduler policy with the warmup ratio set to 0.03. The training conducted on 2 A100-800 GPUs for each model. The training time and memory usage shown in Table 14.
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, I-BB 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 for both WebQSP and CWQ. The beam size is set to 10 for graph-constrained decoding. For vanilla LLMs baselines, we use the reot 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), OpenAl-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 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 the number of tokens inputted into LLMs answer the questions, such as questions and retrieved reasoning paths. The experiments are conducted on a single A 100-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/ tw/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.
20

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Different LLMs. We also analyze the different LLMs used for KG-specialized LLMs and general LLMs on WebQSP. For KG-specialized L.LMs, 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 Figure 11.
Parameter Analysis. We first analyze the performance of GCR with different beam sizes for graph-constrained decoding. We conduct the experiments the WebQSP datasets with beam sizes of 1, 3, 5, 10, and 20. Then, 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 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-88 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-BB 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 decoding. For vanilla LLMs baselines (i.e.,
are set to 2 for both datasets. The beam size is set to 10 for ChatGPT and GPT-40-mini), we use the zero-shot prompting to ask the models answer the questions.
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 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 I 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.
Avg. KG-Tric size (MB)
Precision Recall
Hit
Avg. KG-Trie size (MB)
90
Answer Coverage (%)
4
70
2
60
2
3
4
KG-Trie Path Length
Figure 7. Parameter analysis of path hop for KG-Trie construction on WchQSP.
21

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
E.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 single LLM call. The effectiveness of different K is analyzed in Figure where larger K can lead to better recall of the answers. In addition, we compare the F1 performance under different numbers of ground-trute 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. Fl comparison against RoG under different numbers of ground-truth answers.
WebQSP
CWQ
Methods
Ans =1
<=## # Ans <=4 <==# # Ans <=
# Ans >= 10
Ans 1
2 <= # Ans <=4
5 <== # Ans <=9
Ans >=
10
GCR RoG
71.31
78.14
83.47 75.04
63.20
55.80
64.08
62.57 58.36
55.32
67.89
79.39
58.33
56.9
53.73
43.62
E3. Performance 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. Fl comparison against RoG under different hops of reasoning.
WebQSP
CWQ
Methods
hop
2 hop
>=3 hop
hop
2 hop
>=3 hop
GCR RoG
75.05
72.72
64.54
62.44 58.46
43.82
77.03
64.86
62.88
37.82
F.4. Logical Coherence in KG Reasoning Paths
Due to the lack of ground truth and 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 score from to 5. The results show that GCR achieves average 3.9 in evaluation score, which demonstrates the logical coherence of the generated paths. Moreover, the LLM--bsee evaluation can be further used for selecting meaningful paths for training.
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 's political position, which lacks information about her electoral district. Although L.LMs 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 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.
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- nero-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
22

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Table 17. Failure cases predicted by GCR.
Case 1: Generated paths unrelated to the questions.
Question
What electorate does anna bligh representt?
Answer
Electoral district of South Brishane
www.tiiian.goooeeeeeee. positoons.sillllleoeeelll m.0cr320w ~> govern ment.government position held.jurisdiction of office Queensland
Anna Bligh ->
Generated Path
Predicted answer
Queensland
Case 2: KG incompleteness.
Question
who plays ken barlow in coronation street?
Answer
William Roache
Coronation
Street +
tv.tv www.progrrm.prograan prrator creator
Tony Warren
fic-
Generated Path
tional
Ken Barlow
Predicted answer
Ken Barlow
potential of integrating cross-references from multiple knowledge sources-sure as KGs, web data, and documents- improve reasoning faithfulness.
Time Complexity Complex Questions. Highly complex questions usually require conduct reasoning with multiple steps. However, directly constructing KG-Trie for larger can be time-cossuming. To address this, GCR be integrated with existing planning- baased 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 smaller I. for each subtask to conduct reasoning, thereby reducing computational overhead while maintaining inference quality.
Irrelevant Reasoning Path. As shown in Appendix 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 LLMSs, especially under the settings of incomplete knowledge graphs.
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 reasoning path w, eo 24 13 "4 et.
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.
The few-shot prompt template for graph-constrained decoding is shown Figure 12. We provide a few examples in the prompts to guide the L.Ms to generate reasoning paths. Since the LLMs with few-shot prompt learning are not fine-tuned on the graph-constrained decoding task, only apply the constraint 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 Figure 8. The LLMs are asked evaluate the logical coherence of the generated paths and provide a score from 5.
23

---

<Path> Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Path Evaluation Prompt
Prompt Input
As advanced reasoning evaluator, your task is analyze whether the following reasoning path presents a *tlogically 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 grounded and just fied manner.
### Instructions:
1. Focus on whether the ressoning 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 weak steps.
Moderate: Some steps unclear, general, weak, but the general direction acceptable.
2 Poor: Contains major logical leaps or unclear connections
1 Very Poor: Illogical or invalid path from question to answer.
### Cutput: Score: [1 to 5]
Explanation: (Brief explanation of the logical quality of the path from question to answer]
### Question: <Question>
### Answer:
<Answer>
## Path:
LLM Output
<Score>
Figure 8. The prompt template for path evaluation.
Path Sentence Template
<PATH> + + ri + </PATH>
Figure 9. The template for converting reasoning paths into formatted sentences.
24

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Graph oraph-constrained Decoding Prompt
Prompt Input =
Reasoning path is sequence of triples in the KG that connects the topic entities in the question to answer entities. Given question, please generate some reasoning paths in the KG starting from the topic entitics answer the question.
# Question:
<Question>
# Topic entities: <Question Entities>
L.M Output
# Reasoning Path:
<PATH> <Reasoning Path> </PATH>
# Answer:
<Hypothesis Answer>
Figure 10. The prompt template for graph-constrained decoding.
Graph Inductive Reasoning Prompt
Prompt Input
# Reasoning Paths:
<Reasoning Path l><Hypothesis Answer
1>
<Reasoning Path x><aypothesis Answer
X>
# 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 new line.
LLM Output
<nnswer 1>
<Answer 2>
Figure 11. The prompt template for graph inductive reasoning.
25

---

Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Few-shot Graph- conptt-nnstt Decoding Prompt
Prompt Input
Reasoning path is sequence of triples in the KG that connects the topic entities in the question entities. Given question, please generate some reasoning paths KG starting from topic entities 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>
Pigure 12. The few-shot prompt template for graph-constrainedd decoding.
26


Reviews:
[{"review_id": "4Xzs6UM0VI", "reviewer": "Reviewer_Q2KS", "summary": "This paper introduces a new approach called Graph-Constrained Reasoning (GCR), which integrates the structured reasoning capabilities of a KG-specialized LLM with the general reasoning abilities of a general-purpose LLM. GCR uses KG-Trie to encode potential KG reasoning paths, to constrain the KG-specialized LLM decoding process, ensuring each step is grounded by KG. The method outperforms previous methods on KGQA datasets and shows generalization ability across other KGQA benchmarks.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your time and effort in reviewing our submission. Below, we address your specific concerns:\n\n### R1. Handling Filtering Conditions in Queries\n\nGCR can solve this type of query by combining the power of both KG and powerful general LLM. GCR first constrains the reasoning process within the KG to obtain the relevant knowledge, such as the population of all the states in the US. Then, GCR leverages the general-purpose LLM to conduct inductive reasoning on the knowledge to solve queries that require numerical comparison.\n\n### R2. Discrepancy Between F1 Score and Hit@1\n\nIn experiments, we select top-K paths generated by KG-specialized LLM for answer generation, which might lead to some missing answers, causing a discrepancy between F1 and Hit@1. The results in Fig. 4 show that the recall of the answers increases as the K and reduces the discrepancy.\n\n### R3. Logical Coherence in KG Reasoning Paths\n\nThanks for bringing up this interesting point. Due to the lack of ground truth and a great number of paths, we utilize the LLMs to evaluate the logical coherence and semantic meanings of the generated paths. The prompt and evaluation result are shown below:\n```\nAs 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.\n\n### Instructions:\n1. Focus on whether the reasoning path makes logical sense from the question to the answer.\n2. Check whether each relation contributes meaningfully and validly to reaching the final answer.\n3. Penalize paths that make unjustified jumps, overly general connections, or weak associations.\n\n### Rating Scale:\n5 - Excellent: Every step is logically valid and contributes clearly toward the answer.  \n4 - Good: Mostly coherent with minor assumptions or weak steps.  \n3 - Moderate: Some steps are unclear, general, or weak, but the general direction is acceptable.  \n2 - Poor: Contains major logical leaps or unclear connections.  \n1 - Very Poor: Illogical or invalid path from question to answer.\n\n### Output:\n- Score: [1 to 5]  \n- Explanation: [Brief explanation of the logical quality of the path from question to answer]\n\n### Question:\n{question}\n### Answer:\n{answer}\n### Path:\n{path}\n```\n\n| Method | Score |\n| :---- | :---- |\n| GCR | 3.9 |\n\nThe results show that GCR achieves an average 3.9 in evaluation score, which demonstrates the logical coherence of the generated paths. Moreover, the LLM-based evaluation can be further used for selecting meaningful paths for training. Some meaningful cases can be found in Table 5\\.\n\n### R4. Conflicts Between KG-Specialized LLM and KG Knowledge\n\nWe want to clarify that this difference only happens when **no constraints are applied** (GCR w/o constraint in Table 5), where LLMs purely rely on their internal knowledge for reasoning, which leads to hallucinations. This can be addressed by applying the KG-Trie constraints during reasoning (GCR) to ensure faithful and transparent LLM reasoning, which aligns with the motivation of our method.\n\n### R5. Soundness of BFS Shortest Paths in Training\n\nWe acknowledge that the shortest paths found via BFS may not always be the most semantically meaningful reasoning paths. However, due to the lack of golden reasoning paths, it would be a great choice to unsupervisedly obtain the paths for training. We will enhance path selection by incorporating LLMs for judging the semantics (as discussed in R3) to ensure that paths adhere to the logical coherence in the KG’s relationships.\n\n### R6. Necessity of LLM for Path Selection\n\nAs discussed Sec. 4.1, LLMs conduct reasoning by decoding reasoning step-by-step, which purely relies on their internal knowledge and leads to hallucinations. GCR adapts this reasoning behavior to KGs and decodes reasoning paths that are valid on KGs. This well aligns with the reasoning paradigm of LLMs and is faster than other methods adopting LLMs for path selection (e.g., ToG in Table 2).\n\n### R7. Edge Direction\n\nWe consider the direction of the relations during KG-Trie construction. Therefore, only `US -> is_contained_by -> North America` will be generated. The inverse relations can be added during KG construction.\n\n### R8. Word-level Tokenization\n\nWe adopt the token-level tokenizer of the original LLMs to avoid retraining it on new KGs. The entity and relations in any KG can be tokenized into tokens for KG-Trie construction. This ensures the transferability of GCR to unseen KGs (Table 6\\).", "claims_and_evidence": "N/A", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths\nThe motivation is clear and addresses a hallucination problem in KGQA tasks, while the method is technically sound and shows strong empirical performance.\n\nThe conversion of the KG into a KG-Trie and introduction of the graph-constrained decoding are practical, as they do introduce not much time and space complexity in the reasoning process.\n\n\nWeaknesses\n\nDoes the GCR method effectively handle filtering conditions, such as the query \"Which state in the US has the largest population?\" Or is it limited to relying solely on the knowledge of the powerful general LLM for such cases?\n\nThe main results show a significantly lower F1 score compared to hit@1. In KGQA tasks, if the correct reasoning path is predicted, all answers are contained in the KG-Trie and they should all be retrieved. Therefore, the F1 score should not be much lower than hit@1. This discrepancy indicates that the KG-specialized LLM may be missing answers in KG due to its inherent knowledge limitations. \n\nIn Section 5.3, the comparison between GCR and RoG only addresses the hallucination issue of whether the predicted paths exist in the KG, which is necessary but insufficient. A valid path should not only be present in the KG but also exhibit logical coherence. Is it possible to include an evaluation of the quality of paths generated by KG specialized LLM, assessing whether these paths truly represent logical reasoning processes for the given query?", "other_comments_or_suggestions": "As shown in Case 2 of Table 5, the answer generated by GCR’s reasoning path differs from the final answer, revealing that the KG-specialized LLM relies on its internal knowledge to answer KG-related questions. This creates conflicts between its internal knowledge and the KG’s knowledge, leading to inconsistencies or omissions in answers. These conflicts introduce new errors, which may affect the method’s overall performance.\n\nAs mentioned in Section 4.2, GCR employs the shortest paths in BFS for training. Is this path always logical correct? There are cases where the training data paths may exhibit semantic or logical inconsistencies as below. To address this, could the authors compare these paths with the relationships specified in the original query to verify their accuracy and relevance?\nQuery：Who is the brother of A's grandfather?\nShortest Path(2 hops): A-> gender -> male -> gender -> Answer\nReasonable Path(3 hops): A -> father -> C -> father -> D ->brother -> Answer\n\nThe GCR method uses a small LLM to select path within the KG. However, since LLMs are inherently language models, the decoding process can be viewed as identifying semantically related edges, a task that may not align with the core capabilities of LLMs. Is the use of an LLM truly necessary for this purpose?\n\nIs the direction of edges within the KG considered in GCR method? For example, considering the query “what is the continent of the USA” and the KG facts 1) USA -> contain -> New York and 2) US <- contain <- North America, how does GCR handle the query? Will both New York and North America both contained in the output of KG specialized LLM? \n\nThe tokenization strategy may affect the GCR decoding process, maybe a word level strategy is more reasonable?", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "pe9JHjE7Bo", "reviewer": "Reviewer_SJco", "summary": "The paper introduces **Graph-Constrained Reasoning (GCR)**, a novel framework to address hallucination and knowledge gaps in large language models (LLMs) when reasoning over knowledge graphs (KGs). GCR bridges structured KG knowledge with unstructured LLM reasoning by constructing a **KG-Trie**, a trie-based index that encodes valid reasoning paths from the KG. During decoding, the KG-Trie constrains the LLM’s output to generate only KG-grounded paths, ensuring faithfulness. GCR employs a two-stage process: (1) a lightweight KG-specialized LLM generates multiple hypothesis answers and constrained reasoning paths via graph-constrained decoding, and (2) a powerful general LLM performs inductive reasoning over these paths to produce final answers. Experiments on KGQA benchmarks (WebQSP, CWQ) show state-of-the-art performance with **zero hallucination** and strong zero-shot generalizability to unseen KGs (e.g., ConceptNet, medical KGs). Key results include **92.6% Hit@1** on WebQSP and **75.8%** on CWQ, outperforming prior methods like RoG and ToG. The framework reduces latency by avoiding iterative KG traversal and leverages parallel decoding for efficiency.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your positive and insightful review of our paper. Below, we address your comments and concerns point by point.\n\n### R1. Scalability of KG-Trie construction for billion-edge KGs.\n\nScalability is indeed a vital concern, especially for billion-edge KGs. In our current implementation, we optimize KG-Trie construction by leveraging efficient graph traversal techniques and parallelized batch processing. Detailed analysis can be found in Appendix B.2, where the average running time for KG-Trie construction is **0.0133s.**\n\nWe also present further optimizations to handle industrial-scale KGs by incorporating graph retrieval techniques to reduce the size of KG for Trie construction (Appendix B.3 and Figure 6). The breakdown of time consumption in Table 9 also shows its efficiency of when combined with graph retrieval techniques (**0.2838s**)\n\nFuture work could explore better trie structures or hierarchical indexing to improve efficiency on industrial-scale KGs.\n\n### R2. Analysis of Path Diversity vs. Answer Correctness\n\nWe appreciate this suggestion and agree that path diversity plays a crucial role in reasoning quality. GCR first adopts the beam-search to generate top-K paths with KG-specialized LLM (Sec 4.3). Therefore, the path diversity would increase with the size of K. Then, we conduct graph inductive reasoning to incorporate diverse paths for deliberate reasoning with a powerful general LLM (Sec 4.4). \n\nAs shown in Figure 4, we analyze the impact of different beam sizes K for graph-constrained decoding on the performance of GCR. We observe that the hit and recall of GCR increase with the beam size. Because, with a larger beam size, the LLMs can explore more diverse paths and find the correct answers. However, a larger K would increase the decoding time and diverse paths might introduce noises. Thus, we select the K to 10 to balance between the exploration and exploitation of the reasoning paths.\n\n### R3.  Impact of Longer Reasoning Paths (L \\> 3\\) on Performance\n\nWe agree that extending path length could potentially enhance performance on complex multi-hop queries. We evaluate the performance of GCR with L up to 4 in Section F.1. The results in Figure 7 show that the performance in WebQSP slightly drops when L \\> 2\\. This could be because the question in WebQSP only requires up to 2 hops to solve \\[1\\]. \n\nAdmittedly, a larger L could improve the performance on complex questions that require longer hop reasoning but the trade-offs would be the size of the KG-Trie. As shown in Figure 7 at Appendix F.1, the size of the KG-Trie is increased from 0.5MB to 7.5MB as the L change from 1 to 4\\. This would lead to extra complexity for storage and reasoning.\n\n\\[1\\] LUO, LINHAO, et al. \"Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning.\" ICLR 2024\\.", "claims_and_evidence": "1. GCR eliminates hallucinations by constraining decoding to KG-grounded paths. Evaluations show **100% faithful reasoning ratio** (Table 5, Figure 5), with all generated paths verifiable in the KG. Ablation studies confirm that removing KG constraints leads to hallucinated paths (e.g., Case 1 in Table 5).  \n\n2. GCR achieves SOTA performance on KGQA tasks. Results on WebQSP (92.6% Hit@1) and CWQ (75.8% Hit@1) surpass retrieval-based (RoG: 85.7%) and agent-based (ToG: 68.5%) methods (Table 1).  \n\n3. GCR generalizes to unseen KGs without fine-tuning. Zero-shot tests on FreebaseQA (94% accuracy) and CSQA (91%) demonstrate adaptability (Table 6). Performance drops on MedQA (79%) are attributed to domain specificity.", "methods_and_evaluation_criteria": "- **Methods**:  \n  - **KG-Trie** efficiently encodes KG paths as token sequences, enabling prefix-based constrained decoding.  \n  - **Graph-constrained decoding** uses a fine-tuned LLM (e.g., Llama-3-8B) to generate hypothesis answers and paths under Trie constraints.  \n  - **Inductive reasoning** with a general LLM (e.g., GPT-4) aggregates multiple paths for final answers.  \n\n- **Evaluation Criteria**:  \n  - **Datasets**: Standard KGQA benchmarks (WebQSP, CWQ) and zero-shot tests on FreebaseQA, CSQA, MedQA.  \n  - **Metrics**: Hit@1, F1, accuracy. Faithfulness is measured via path grounding in KGs.  \n  - **Baselines**: Include LLM-only (ChatGPT+CoT), graph-based (ReaRev), and KG-enhanced methods (RoG, ToG).  \n\nAppropriate for assessing faithfulness, efficiency, and generalization.", "theoretical_claims": "The paper lacks formal theoretical proofs but provides algorithmic formulations.", "experimental_designs_or_analyses": "- Confirm the necessity of both KG-specialized and general LLMs (Table 3).  \n- Beam size (K=10) and path hops (L=2) are optimized (Figure 4, Appendix F.1).  \n- GCR achieves **3.6s runtime** vs. 16.14s for ToG (Table 2), leveraging parallel decoding.  \n- **Zero-Shot Generalization**: Tests on medical/commonsense KGs highlight domain limitations.  \n- Soundness: Rigorous and reproducible.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "- **Strengths**:  \n  - Novel integration of KG structure into LLM decoding.  \n  - Practical efficiency (parallel decoding, pre-computable KG-Trie).  \n  - Strong empirical results and reproducibility.  \n- **Weaknesses**:  \n  - Scalability of KG-Trie construction for billion-edge KGs.  \n  - Limited analysis of path diversity vs. answer correctness.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Could longer reasoning paths (L > 3) improve performance on complex questions, and what are the trade-offs?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Y2oIAXHfBD", "reviewer": "Reviewer_V86Q", "summary": "This paper proposed the GCR framework, where a trie-based index leverages structured knowledge from KGs to address knowledge gaps and hallucinations in LLM reasoning. GCR employs a lightweight KG-specialized LLM for graph-constrained reasoning and a general LLM for inductive reasoning. Experimental results on KGQA benchmarks show that GCR achieves state-of-the-art performance, and demonstrates strong zero-shot generalizability to unseen KGs without additional training.\n\n## update after rebuttal: \nThank the authors for their detailed responses. The clarifications provided have addressed my initial concerns regarding the method's efficiency and its handling of special cases. As a result, I see no need to revise my original assessment score and will maintain it as is.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your positive and constructive review of our paper. Your feedback is invaluable in helping us refine and clarify our work. Below, we address your comments and questions in detail.\n\n### Efficiency of KG-Trie Construction and Practical time costs of the KG-Trie construction\n\nWe appreciate your emphasis on the efficiency of the KG-Trie construction process. In our current implementation, we optimize KG-Trie construction by leveraging efficient graph traversal techniques and parallelized batch processing. To provide a concrete perspective, we conducted additional experiments measuring the construction time on real-word KG (Freebase) in Appendix B.2, where the average time for KG-Trie construction is only **0.0133s.**\n\nWe also present further optimizations to handle industrial-scale KGs by incorporating graph retrieval techniques to reduce the size of KG for Trie construction (Appendix B.3 and Figure 6). The breakdown of time consumption in Table 9 also shows the efficiency of the KG-Trie construction when combined with graph retrieval techniques (**0.2838s**).\n\nFuture work could explore better trie structures or hierarchical indexing to improve efficiency on industrial-scale KGs.\n\n### Adaptability to Missing Entities and Questionable Reasoning Paths\n\nThank you for raising this important concern. Our method is designed to be robust against incomplete KGs in two folds:\n\n**Exploring Alternative Paths**  \nWhen the entities are missing, the GCR can explore alternative paths to fulfill the reasoning. For example, for the question “What is the  \nnationality of Joe Biden?” One of the reasoning paths could be:  \n`Joe Biden -> born_in -> Scranton -> city_of -> USA`.  \nWhen the entity `Scranton` is missing and leading to the disconnection of the path, GCR could explore other paths like:  \n`Joe Biden -> profession -> President -> work_in -> Washington D.C -> city_of -> USA`.  \nThis path can also be used to deduce the correct answer: `USA`. In implementation, we explore the top-10 paths for comprehensive reasoning.\n\n**Combining Internal Knowledge of Powerful General LLMs**  \nDue to the noises and incompleteness of KGs, the generated reasoning paths might be unsatisfying. To address this, in the graph inductive reasoning (Section 4.4), we employ a powerful general LLM (e.g., GPT-4o-mini) to incorporate diverse paths for deliberate reasoning. \n\nThe powerful general LLM exhibits massive internal knowledge and strong inductive reasoning ability. Therefore, it could disregard the questionable paths and deduce final answers accurately.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "The motivation is clear and the proposed method is technically sound.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "Yes, extensive experiments have verified the effectiveness of the proposed method.", "relation_to_broader_scientific_literature": "The issues of knowledge gaps and hallucinations are significantly important in the current LLM area. The proposed faithful Graph-constrained reasoning may provide a new technical view to the community.", "essential_references_not_discussed": "I do not have suggestions for additional references.", "other_strengths_and_weaknesses": "Please check the above suggestions.", "other_comments_or_suggestions": "In my opinion, the efficiency of this approach is vital, and I am curious about the practical time costs of the KG-Trie construction stages on real-world KGs.", "questions_for_authors": "How does your method adapt when real-world KGs have missing entities or questionable reasoning paths?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The provided context details the development and evaluation of a novel framework called Graph-Constrained Reasoning (GCR), which aims to eliminate hallucinations and ensure faithful reasoning by integrating Knowledge Graph (KG) structure into the Large Language Model (LLM) decoding process.
The GCR framework employs a two-tiered process involving a KG-specialized LLM for graph-constrained decoding and a powerful general LLM for inductive reasoning over multiple reasoning paths. 
This approach not only improves the reasoning capabilities of LLMs but also ensures that the reasoning paths are faithful to the KG, thus reducing the rate of hallucinations. 
The framework has demonstrated state-of-the-art performance on several KG query answering (KGQA) benchmarks and exhibits strong zero-shot generalizability to unseen KGs without additional training.
The use of a KG-Trie to encode valid reasoning paths from the KG allows for the efficient retrieval of knowledge and ensures that the reasoning process is grounded in the KG. 
The integration of the KG structure into the LLM decoding process is a practical and innovative approach to improving the performance of LLMs in reasoning tasks. 
The main concerns raised by the reviewers have been address by the authors in response.
Decision: Accept (poster)