Deliberation on Priors: Trustworthy Reasoning of Large Language Models on Knowledge Graphs
Authors: Jie Ma
Ning Qu
Zhitao Gao
Xing Rui
Jun Liu
Hongbin Pei
Jiang Xie
Lingyun Song
Pinghui Wang
Jing Tao
su zhou
Venue: NeurIPS 2025 poster ()
Keywords: Knowledge Graph-based Retrieval Augmentation
Knowledge Graph Question Answering
Large Language Models
Primary area: deep_learning
TL;DR: We propose a trustworthy reasoning framework for LLMs to reason over knowledge graphs.

Abstract: Knowledge graph-based retrieval-augmented generation seeks to mitigate hallucinations in Large Language Models (LLMs) caused by insufficient or outdated knowledge. However, existing methods often fail to fully exploit the prior knowledge embedded in knowledge graphs (KGs), particularly their structural information and explicit or implicit constraints. The former can enhance the faithfulness of LLMs' reasoning, while the latter can improve the reliability of response generations. Motivated by these, we propose a trustworthy reasoning framework, termed Deliberation over Priors (\texttt{DP}), which sufficiently utilizes the priors contained in KGs. Specifically, \texttt{DP} adopts a progressive knowledge distillation strategy that integrates structural priors into LLMs through a combination of supervised fine-tuning and Kahneman-Tversky Optimization, thereby improving the faithfulness of relation path generation. Furthermore, our framework employs a reasoning-introspection strategy, which guides LLMs to perform refined reasoning verification based on extracted constraint priors, ensuring the reliability of response generation. Extensive experiments on three benchmark datasets demonstrate that \texttt{DP} achieves new state-of-the-art performance, especially a H@1 improvement of 13% on the ComplexWebQuestions dataset, and generates highly trustworthy responses. We also conduct various analyses to verify its flexibility and practicality. Code is available at [https://github.com/mira-ai-lab/Deliberation-on-Priors](https://github.com/mira-ai-lab/Deliberation-on-Priors).

Deliberation on Priors: Trustworthy Reasoning of Large Language Models on Knowledge Graphs
Jie Ma "t, Ning Qu Qu2 Zhitao Gao Rui Xing', Jun Liu Honghin Pei', Jiang Xie Lingyun Song", Pinghui Wang', Jing Tao', Zhou Su
'MOE KLINNS Lab, Xi'an an Jiaotong University
School of Computer Science and Technology. Xi'an Jiaotong University
Shaanxi Province Key Laboratory of Big Data Knowledge Engineering
School of Artificial Intelligence, Chongqing University of Post and Telecommunications
Schooo of Computer Science, Northwestern Polytechnical University
"Equal contribution
t 'Corresponding Author
j ema@xj tu. wad.edu.co cn
Abstract
Knowledge graph-based retrieval-augmented generation seeks to mitigate hallucina- tions in Large Language Models (LLMs) caused by insufficient outdated knowl- edge. However, existing methods often fail to fully exploit the prior knowledge embedded in knowledge graphs (KGs), particularly their structural information and explicit or implicit constraints. The former can enhance the faithfulness of LLMs' reasoning, while the latter can improve the reliability of response generation. Motivated by these, we propose trustworthy reasoning framework, termed De- liberation over Priors (DP), which sufficiently utilizes the priors contained KGs. Specifically, DP adopts progressive knowledge distillation strategy that integrates structural priors into LLMs through a combination of supervised tinettuning and Kahneman-Tveel Tversky optimization, thereby improving the faithfulness of relation path generation. Furthermore, our framework employs strategy, which guides LLMs to perform refined reasoning verification based on extracted constraint priors, ensuring the reliability of response generation. Exten- sive experiments three benchmark datasets demonstrate that DP achieves new state-of- oftt--of-the-rrt performance, especially a H@I improvement 13% on the Com- plex WebQuestions dataset, and generates highly trustworthy responses. We also conduct various analyses to verify its flexibility and practicality. Code available at https::/ com/mira-an ai- -all-labDDoee Taab/Delleeaaiiee on-rriors.
soooning-ittooppcction
Introduction
Large Language Models (LLMs) [1-4], distinguished by their massive parameter scale and training on vast amounts diverse, unlabeled data, have demonstrated impressive capabilitics across a wide range of natural language understanding and generation tasks. They have also achieved substantial success in practical applications, such as intelligent virtual assistants and customer service systems. However, recent research [5-7] has revealed that LLMs are prone to hallucinations, producing plausible-sounding but incorrect or outdated responses, especially in real-world scenarios. This issue, often stemming from insufficient or obsolete knowledge, can lead to serious consequences and undermine the reliability of LLMs in high-stakes domains such as legal decision-making and medical diagnosis [8, 9].
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Question: year the directed Ang starring Yun the Golden
The movie Life of Pl, directed by Ang Lee and starring Chow Yun-fat, won the Golden Horse Award in 2001.
Oscar Academy Awards
directed
Life
Compourd Value Typei
Cleord yottrr
2001
directed
Croucting Tiger
Storred
dwordLyyer .... ewond
2000
Compourd Value Type2
Ang Lee
Brokebsok Mourfain
Structural Information Collection
Constroints Extraction
Pots I: Ang 12 diusted is 6 winLewer is GVT snen 15 Patn 2: Chow Yun not sharmed R
Ma il: fattly cess
The cwerd von the move et the device Horie Awordd
directed Ang storring Yun the Golden Horse Award 2000.
Figure I: An illustration of LLM reasoning over knowledge graphs based exploiting priors sufficiently. We collect weak supervision signals of the mapping from questions to relation paths by identifying the shortest traversal sequence from topic entities to answers. We predefine 5 constraints, such as type, multi-entity, and ordinal constraints, following [17] which employs them to develop the Complex dataset but does not leverage the prior in reasoning.
To equip LLMs with up-to-date, domain-spectie knowledge, an emerging line of research [10-12] has focused on knowledge graph-based gtrieval-augmeeter generation, which aims to enhance response generation through the dynamic retrieval of relevant external knowledge. Current methods [7, 13, 14] employ an end-to-end or step-by-step manner to retrieve and reason on Knowledge Graphs (KGs). The former retrieves the top K triples based on the semantic similarity between questions and knowledge facts, while the latter transforms complex questions into multiple subquestions by step-by-step retrieval. After obtaining sufficient knowledge, they utilize LLMs to generate responses directly.
However, existing approaches [7. 8, 13-16] fail to exploit the prior knowledge embedded in KGs fully, particularly (1) the structural information and (2) the explicit and implicit constraints. In partieular, relation paths that connect topic entities in questions to their corresponding answers, such as the path "Ang Lee + directed - ... E" in Figure 1, can be leveraged not only to enhance the structural pattern awareness within KGs but also to support response generation. This, turn, can significantly improve the faithfulness of LLM reasoning over KGs. Additionally, constraints, such as the multi-entity and type constraints, can serve a dual purpose: they can be used to filter candidate relation paths (select path 2 in Figure I considering the mentioned two types of constraints) and also to guide LLMs in backtracking during inference, thereby improving the reliability and robustness of reasoning processes. Motivated by these, propose trustworthy reasoning framework over KGs named DP (Deliberation on Priors). The framework comprises four key modules: Distillation, Planning, Instantiation, and Introspection, which guide LLMs to generate faithful and reliable responses through a two-stage process:
offline and online.
In the offline stage, DP first collects weak supervision signals in the form of mappings from questions to corresponding sets of relation paths. The paths are constructed by identifying the shortest traversal sequences from topic entities to answer entities in KGs. This prior structural knowledge is then distilled into the LLM through a combination of fine-tuning and Kahneman-Tversk
optimization
[18]. The former is supervised using the weak supervision signal, while the latter is optimized by maximizing the expected utility of generation under the human utility model that Kahneman and Tversky proposed to describe how humans make decisions about uncertain monetary outcomes. This process enhances the ability of LLMs to plan and reason over the KG structure effectively.
During the online stage, the trained LLM is used to Plan for reasoning and generate faithful candidate relation paths. Subsequently, DP utilizes LLMs to perform relation path selections by evaluating the se- mantic relevance between the candidate path and the input question. Next, to obtain a complete reason- ing path, the framework retrieves topic entities and relations from KGs and instantiates the selected re- lation path in the Instantiation module, such as the transformation from "[directed, won award)"

---

Table I: Constraint definitions and samples.
ORO
Category
Definition & Sample
Type
eg.. What city did Esther live in?
The question specifies required type categury for
Pooprtan
Malti-
The question demunds
saisly condition multiple Which team owned by Malcolm Glazer has Tim Howard playing for it?
Emilty
The question clearly defines specific time period
he referenced.
Explicit Time
Who was the governoe of Atizona. in 2009 that hold his goveramental position
before
Implicit Time
The question implics a temporal frame that the answer should consider.
1200
Mall lut kagall lise Vnuiii Oriial
Categoty
e.g. Who was the Socretary State
Jackson
president
Oedinal
eg.. Lou Seal is the mascot for the team that last won the World Series when?
The question contains the sorting mile and requires the answer in speciffi onder.
Figure 2: Constraint distribution on three datasets.
Compound Value Type 2". After obtain- ing the reasoning path, current frameworks [7, 8, 13-16] utilize LLMs to generate responses based on them without deliberation. In contrast, to enhance reasoning reliability, DP employs the Introspection module to verify whether the selected reasoning path satisfies the constraints extracted from questions, where the constraints, such as multi-entity and ordinal constraints, are predefined following [17]. Feedback is then provided to the L.M to guide subsequent decisions. If the reasoning path passes the verification, the LLM is instructed to generate a response. Otherwise, the information about which constraints are violated is fed back to the LLM to trigger relation path backtracking.
to "Ang Lee directed
Crouching Tiger
WOD, non_award
To evaluate the effectiveness of DP, we conduct extensive experiments on three benchmark Knowledge Graph Question Answering (KGQA) datasets. The experimental results on WebQuestionSP [19], Complex WebQuestions [20], and MetaQA [21] show that, compared with baselines, our method achieves state-of-te satte-of-the-aad art performance while minimizing interaction frequency with LLMs and gener- ates more faithful and reliable responses.
The main contributions this work are summarized as follows:
We introduce a trustworthy reasoning framework DP that empowers large language models generate faithful and reliable responses through deliberate reasoning the priors embedded in knowledge graphs.
We propose a progressive knowledge distillation strategy, enabling LLMs to generate faithful relation paths by exploiting prior structural information.
strategy that enhances the reliability of large language model generation by incorporating predefined constraint priors as guidance.
We propose reasoning-introspee
We conduct extensive experiments three public datasets verify the effectiveness and superiority of DP. Furthermore, we demonstrate the flexibility of DP in integrating with various large language models, well its practicality in scenarios requiring fewer interactions with them.
Preliminary
KGQA Task Formulation. Given question q. a knowledge graph G, and topic entity e, mentioned in q, KGQA requires the intelligent system, such LLMs, to generate responses based of knowledge triples (facts) retrieved from G. should noted that question q may contain multiple topic entities.
Relation Path Definition. relation path is formally defined as an ordered sequence of relations P P= (r1,72,.... ,,), where each E 'R denotes the i-th relation in the path and I represents the path length. Here, R denotes the set of all possible relations in G.
Path Instantiation. Given a relation path P, an instantiation path is called a reasoning path, denoted by PP co ب _2, "3 ... It e,, where each e; E & denotes the i-th entity in the path and r; corresponds to the i-th relation in the relation path P. Here, E represents the set of all entities the KG. It should be noted that a relation path P may have multiple instantiations in G.

---

Dishillation
Part 2: Planning & Instantiation
Part 3: Introspaction
Question Topic entihies
KI
Generation
Consirrint Extraction
Multi-ent-ly
Explicit
Implici Time
Ordinsl
Feedbook
Relation path L: nu, nay ru))
Relation path fau, ras. fta?
Constraint X-X
Selection
Verification
Relation path
Answer:
Selected Path
WI
2eraaioo
Path
Week Supervision Collection
Preference Data Construction
Supervised Fine-Tuning
Preference Optimization
Figure 3: Trustworthy reasoning framework DP of LLMs over KGs. In Part 1, DP employs progressive knowledge distillation strategy enhance the structural pattern awareness of KGs for LLMs. In Part 2, the reasoning path is produced by relation path generation and instantiations. In Purt 3, DP utilizes a reasoning-inin iesoning-nttoospcctoon strategy to verify whether the reasoning satisfies extracted constraint.
Constraint Predefining. The constraints listed in Table were initially introduced by [17] to facilitate the development of complex questions. In this paper, we leverage these constraint priors for reasoning verification. Specifically, we utilize multiple constraints like "type" and "multi-entity" extracted from questions in Figure to assess whether selected reasoning path satisfies the required conditions. To this end, define constraint base C' and conduct statistical analysis across three datasets, sampling 200 examples from each. Figure demonstrates that most datasets encompass range of constraint categories, with the "type" constraint being the most frequently occurring in each.
3 Methodology
Our proposed framework, DP, illustrated in Figure 3, is composed of four key components. Distillation: This module employs a progressive knowledge distillation strategy to guide LLMs in capturing the structural patterns of KGs from set of demonstrations. Planning and Instantiation: In this stage, DP first generates a diverse set of candidate relation paths, which are subsequently grounded into KG triples to obtain instantiated paths. Introspection: This component performs deliberative selection and verification of reasoning paths by evaluating whether they meet the constraints derived from the input question. Once satisfactory instantiated path is identified, the LLM employed to generate responses accordingly.
3.1 Distillation
DP employs progressive knowledge-distillatoo strategy to guide LLMs in exploiting the struc- tural information and enabling faithful reasoning over KGs. This is achieved by a combination of Supervised Fine-Tuning (SFT) and Kahneman-Tversse Optimization (KTO) [18]. The former fine-tunes the LLM using collected weak supervision signals, while the latter further refines based automatically derived preference data.
Specifically, DP leverages weak supervision signals the form of question-to-path mappings, which are derived from the annotations within training splits. Given question and topic entity e, identified q, we define function M that maps g E Q to a set of plausible relation paths P, where each P P sequence of relations such that traversing from e, via (f1,...,,7) leads to the answer

---

entity in the KG g = (E, R). To extract these paths, our framework first extracts a k-hop subgraph (ex) centered on cç. where l is the maximum reasoning depth allowed by the dataset. Then, the Dijkstra algorithm is employed to identify all shortest relation paths from es to the ground-truth answer entity et within (es). These shortest paths constitute the weak supervision set (w. for question g. serving as structurally mapping relation exemplars. While not exhaustive, ( captures plausible multi-hop reasoning trajectories within the KG structure and provides guidance for the LLM to generalize to similar questions. The weak supervision of question-to-pati mappings P (q) can be defined as follows:
Pw M(g, Ca. 9, k) ShortestPathoiiuuass (atneeeseePatiiinnGG(e.e..) (ex, Cs, et).
(I)
We then apply SFT train the LLM to generate relation paths conditioned the input question
and its corresponding topic entity c.. This training stage encourages LLMs to align the semantic
content of the question with structural relation traversals over G. Let P (ri, r ...... .,,,, ri) denote
gold relation path extracted using Equation (1) for question q. The objective of SFT is to maximize the conditional ooglliieldoood LSFT of the target path sequence pa given the input (g, es):
Csrr(Os) = - log Po. (r) (,)))
(2)
where 0, represents the parameters of the LLM and r-x denotes the prefix subsequence (ri...., .......... 1)- This formulation enables the LLM to learn autoregressively generate faithful relation paths that connect 6s to plausible answer entities within the KG.
To further enhance the reliability of relation path generation, incorporate a preference optimization stage to explicitly encourage LLMs to prefer semantically coherent and structurally faithful relation paths. Specifically,
construct relation path data D consisting of positive paths and negative paths given question q. The negative or undesirable path is synthetically generated from the original weak supervision data P (q) through targeted perturbations for the positive path:
Path Truncation. Removing the final hop r from a gold relation path p yield an incomplete relation chain.
Swapping relation paths between different topic entities associated with the same question, resulting in semantically inconsistent paths.
Entity-Path Swapping.
Relation Deletion. Randomly deleting the relation path of a certain topic entity, resulting in incomplete paths.
These synthetic negative paths are constructed superficially valid relation paths while being semantically invalid due to violations of critical structural or semantic constraints. Notably, such perturbations introduce severe class imbalance in path data, where positive paths constitute only of the dataset, and negative paths account for 4. This imbalance poses significant challenges to conventional preference optimization like direct preference optimization. Therefore, we train the LLM using KTO [18), more robust approach that accommodates imbalanced supervision. KTO maximizes the expected utility of generation under the human utility model that Kahneman and Tversky proposed to describe how humans make decisions about uncertain monetary outcomes. This utility maximization objective is equivalent to minimizing the KTO loss LKTO:
Cxro (To T (a Dy v(x, y)]
Here, we define the key components the KTO loss formulation. Let x = (q,ea) denote the input, and let represent its corresponding relation path label, where y Y, and Y, indicate a positive and negative label, respectively. (-) is the current LLM's output distribution and )-e((-) is the reference model supervised by SFT. The parameter by takes the value Ap (for positive
X, (for negative y), controlling class-specific weighting. The value function u(-) models human utility perception, defined as:
Aporr (f(ro(a,)) v) 20)) if Yp xr 8(x, v) (2oo Nnn (3(2) - re(zz 1 v))) if ~ Ya x.
where o-)) denotes the logistic function, 3 modulates risk aversion, re v) = log xu(y(e) )
represents the implied reward and the reference point 2p is obtained via the KL divergence 2o KT. (To(s/ x) merly x)). In brief, the progressive knowledge distillation strategy equips DP with reliable structural priors of KGs, enabling faithful online reasoning in the subsequent stages.
5

---

3.2 Planning and Instantiation
In this stage, DP utilizes the path generator, which has been trained through the aforementioned progressive knowledgeedistillation strategy, to generate multiple candidate relation paths. One of these paths is then selected and instantiated by retrieving entities from the KG, beginning with the given topic entity eg. Importantly, the selection of the relation path this stage is guided solely by its semantic alignment with the input question, without imposing any constraints.
More formally, given a question q and its associated topic entity c.. DP invokes the path generator to produce set of candidate relation paths {Pi, P2....., }. where each P; denotes a traversal sequence of relations representing a multi-hop reasoning trajectory over the KG. In scenarios where a question contains multiple topic entities, the path generator independently produces candidate paths for each entity. These paths are subsequently merged into a unified pool, thereby enriching semantic diversity and increasing the probability that at least one reasoning trajectory satisfies the implicit or explicit constraints embedded in the question. For given relation path P, the corresponding instantiated reasoning path P is obtained by traversing the KG starting from the topic entity eg. The instantiation process is described in detail in Section 2.
3.3 Introspection
To ensure the reliability of LLM reasoning, our framework utilizes reasoning- introspection strategy to verify whether the reasoning path satisfies the extracted constraint from questions. As introduced in Section 2, we predefine 5 constraint types, which are prior knowledge embedded in KGs and can be employed to guide LLMs. Specifically, given question g. DP first prompts LLMs to extract the contained constraint C(g) from the predefined constraint base C: C(q) Foons(y, C, Loons). where coons represents the prompt and in-context exemplars. Subsequently, the LLM is prompted to determine whether the instantiated reasoning path P satisfies C(q) given g and e., The verification outcome is formalized as:
P) (1. P C(g):
otherwise.
If the constraint is satisfied, DP instructs the LLM to generate a reason and produce final response grounded on the validated reasoning path. Conversely, if the constraint is violated, the LLM is prompted to provide explicit feedback identifying the unsatisfied condition. This feedback subse- quently triggers a backtracking mechanism, wherein the framework iteratively re-executes the process of relation path selection, instantiation, and introspection. This mechanism reduce the negative impact of false-pone sossitivevvve reasoning paths, promoting the reliability of response generation. The iterative loop continues until either constraint-satisfyee reasoning path is found or the candidate relation path set is reduced to a singleton.
4 Experiment
We conduct various experiments on three benchmarks to verify the following aspects: (1) the superiority DP; (2) the flexibility in integrating different L.Ms;; (3) the effectiveness individual components; (4) the necessity of deliheration on prior knowledge; and (5) the practicality of DP.
4.1 Experimental Setting
Dataset and Evaluation Metric. We evaluate our approach on three public multi-hop KGQA datasets: WebQuestionSP (WebQSP) [19] and WenpuexnebQusssooss (CWQ) [20], and MetaQA [21]. WebQSP is developed by gathering semantic parses in SPARQL from the WebQuestions dataset. CWQ features a large collection of compositional questions, requiring reasoning over up 4-hop relation paths based on multiple web snippets. MetaQA is built upon a movie ontology derived from the WikiMovies dataset and provides question-ansse answer pairs spanning 1-hop, 2-hop, and 3-hop queries. The KGs used in WebQSP and CWQ are subset of Freebase. To account for computational constraints, we uniformly sample 500 questions from the test set of WebQSP and CWQ, following the setup in [22, 15]. A total of 600 instances are uniformly sampled from the MetaQA dataset, with exactly 200 samples selected for each of the 1-hop, 2-hop, and 3-hop types. Evaluation conducted using three standard metrics: Hit, Hits @ 1, and Fl score, consistent with prior studies [8, 23, 24). The

---

Table 2: Comparison of KGQA performance (%) across three datasets with previous sfate-of-the- art methods. DP results are averaged over three independent evaluations. We highlight the best performance in bold and the second-best in underline. Baseline methods are categorized into three groups: Supervised Learning (SL), In-Context Learning (ICL), and Hybrid Learning (HL). LM denotes the language model used. denotes the performance on h-hop questions.
WebQSP
CWQ
MetaQA
Type
Year
II
Hil
F1
H
H611
F1
H
B@1
FI
2022
ChaiGPT
59.3
59.3
43.5
34.7
34.7
30.2
Vanilla
Zeno-shot
2023
GPT4
67.
49.5
46.1
2024
LLaMA3.1-30
34.8
EmbedKGQA
2020
RoBERTa
56.6
97.0
TransferNat
2021
BERT
71.4
48.6
99.2
SL
UniKGQA
RoG
2034
2023
1MAZ-Chuu77
RobERTa
85.7
77.2
80.8
72.2
70.8
62.6
51.2
$7.8
49.0
56.2
89.0"
99.4
50.7
AMAR
2025
81.2
78.5
GNN-RAG
LLaMA2-Cha-78
73.5
ToG
2024
GPT-4
82.6
36.4
69.5
31.8
ICT.
Readi
PoG
2024
2024
ChaiGPT
ChaRGPT
GPT44
GPT-4
87.3
82.0
74.3
75.0
63.2
55.6
CharGPT
DoG
2025
GPT-4
91.0
65.4
55.6
56.0
41.0
46.4
98.3
90.]
93.1
InteracrieeKBOQ
2024
GPT-4
71.2
49.1
96.3
LightPDD
2025
LLaMAS-S8 SB
83.8
59.3
HI.
LLaMA3,1-BB
87 Stanz
82.8
75.7am
70.8ass
61.1asa
S8.5aro
90.2sm
87.4
84.1aso
CharGPT
89.7nn
86.9
79.2am3
80.0ao6
72.66m1
89.2104
96.7am1
95.4103
90.8144
(Ours)
90.7
81.4
85.6
74.0.00
70.51s5
96.7202
9655
95.2
44.4
GPT-4.1
30.8mn3
86.7
80.1.s
87.2
75.8
69.4100
96.8.2
95.5103
94.9101
Hit (H) metric assesses whether any of the ground-truth answers are present the generated response. Hits@1 1 (H@) 1) measures the proportion of questions for which the top-ranked predicted answer exactly matches correct answer. The Fl score accounts for scenarios with multiple correct answers by computing the harmonic mean of precision and recall, thereby providing a more comprehensive evaluation of answer quality.
is fine-tuned by the weak supervision signal in the form of question-to-panl mapping for epochs and further optimized for epoch through preference optimization with KTO [18]. We apply low-rank adaptation [25] adapt large-scale parameters during both SFT and KTO training efficiently. In the Planning stage, we employ the trained path generator in zero-shot manner to produce a set of relation paths for each topic entity in the question. In the Introspection stage, DP guides LLMs to perform path selection, constraint extraction, and verification under a few-shot setting. Specifically, we provide one exemplar for each possible scenario within these three procedures, which consist of 3, 5, and 2 scenarios, respectively. The detailed settings are provided in Appendix B. and B.2.
Implementation Detail. During the Distillation stage, the path generator LLLaMA3.1-8B-mme
Baseline Selection. Inspired by the setup in [15, 8]. compare DP against previous statc-of-the-an approaches, including Supervised Learning (SI.), In-Context Learning (ICL), and Hybrid Learning Sl-based methods train models using the answer labels provided in KGQA datasets to directly predict answers, including EmbedKGQU [26]. TransferNet [27], UniKGQA (28), RoG [8]. AMAR [10], and GNN-RAG [24]. ICL-based methods employ th-oughf reasoning to generate responses based on few-shot exemplars, including PoG [29]. ToG [22], Readi [30], and DoG [15].
HL-based methods combine SL and ICL to produce responses, including Interactive-KBQA [31] and LightPROF [32].
4.2 Reasoning on Different KGs
Main Result. We compare DP with previous state-of-the-art methods, categorized into three types: SL, ICL, and HL. Based on the results presented in Table 2, we draw the following key insights. First, incorporating deliberation over prior knowledge significantly enhances the reliability of response generation. The results for DP are averaged over three independent runs. Our framework consistently achieves new state-of-the-art performance across most datasets, with low variance. In contrast, the vanilla LLMs (without DP) exhibit unstable performance and often fail to achieve competitive H@ or scores, particularly on CWQ and WehQSP, highlighting their limitations in complex reasoning tasks. Notably, DP surpasses the HL-based method LightPROF by 16.5% in H@ on the CWQ
7

---

dataset. Second, existing methods struggle in scenarios where the correct answer must appear in the top-ranked position or where the output is expected contain accurate answers with high precision. For instance, ToG exhibits a 46.2% gap between its H and Fl scores on the WebQSP dataset. In contrast, DP narrows this gap to approximately 10%, further underscoring its robustness and reliability, Third, we observe that some prior works have misinterpreted evaluation metrics such as H and H@] 1. According to the code released by [10, 22], certain results reported as H@ are actually H. potentially leading to unfair comparisons and misleading evaluations. In this work, we rigorously report DP's performance using H. H@1 I, and Fl metrics, respectively. Overall, the DP framework demonstrates robust and reliable performance across diverse datasets, validating the effectiveness of incorporating prior knowledge deliberation.
Flexibility Verification. Table 2 also reports the integration experiments. which are designed to evaluate whether DP can enhance the reasoning reliability of various L.MMs, including L.LMAA31 1- 8B, GPT-3.5, GPT-4.0, GPT-4o, and G.T-4.1. The results show that DP consistently improves the reasoning performance of these LLMs across three benchmark datasets. Notably, our framework enables GPT-4o and G to achieve the best performance respectively. Overall, these findings highlight the flexibility and effectiveness of DP in enhancing diverse LLMs, with lower variance observed across multiple runs, indicating that the improvements are stable and reliable.
the WebQSP and CWQ datasets,
4.3 Ablation Study
We perform comprehensive ablation studies on two benchmark datasets (WehQSP and CWQ) to systematically evaluate the contribution of
Table 3: Ablation experiments. PT, EPS, and RD denote path truncation, entity-path swapping, and relation deletion, respectively, which are pertur- bations introduced in Section 3.1. "w/o CPD" in- dicates the constraint is automatically induced by LLMs rather than being manually predefined.
each DP component. As shown in Table 3, our analysis reveals five critical observations. First, LLMs such GPT-4.1 demonstrate sig- nificant performance degradation when deprived of knowledge augmentation. Specifically, the Fl score drops by 25.5% on WebQSP and 20.5% on CWQ, highlighting the necessity of exter- nal knowledge integration for complex question answering tasks. Second, our progressive knowl- edge distillation strategy effectively promotes the prior awareness of LLMs for the structural patterns of KGs. When removing KTO, we ob- serve a 2.0% decrease in H@1 score on We- bQSP and 1.2% decrease on CWQ, confirming its role in improving pattern recognition capa-
WebQSP
CWQ
Setting
H@1
DP (GPT 4.1)
90.6
86.7
80.1
87.2
75.8
69.4
GPT 4.1
74.0
71.0
54.6
56.0
53.0
48.9
w/o KTO
88.3
84.7
77.3
86.0
74.6
67.3
who PT
88.4
84.8
77.6
86.4
75.0
68.4
who EPS
90.0
85.8
79.4
86.6
73.8
68.1
w/a RD 88.3
84,8
77.8
87.2
74.1
67.7
wlo Introspection
86.6
82.0
75.7
85.3
70.8
65.2
w/o CPD
87.8
83.4
76.4
74.4
68.5
who feedback
88.0
83.0
76.5
85.4
73.2
67.1
bilities. Third, among the three perturbation methods examined, relation deletion demonstrates the most substantial impact on path generation. Fourth, the ceusoning-introspen the most critical component for ensuring response reliability. Compared to other ablated conditions, removing introspection leads to the most pronounced performance deterioration across both datasets. Finally, both constraint predefinition and verification feedback contribute significantly to the overall reasoning process. Notably, substituting manual constraint definitions with LLM -..--eeeerdedd sum- maries results in 2.8% drop in H score on WebQSP and 1.0% decrease CWQ, underscoring the value of human-defined constraints in guiding accurate reasoning. These findings collectively demonstrate the complementary roles of different DP components in enhancing the faithfulness and reliability of LLM reasoning.
strategy proves to be
4.4 Impact of Priors on LLM Reasoning
To investigate the impact of prior knowledge on LLM reasoning, we conduct extensive experiments on two benchmark datasets: WebQSP and CWQ. First, Table 4 presents the results of path generation and constraint extraction on 500 and 100 uniformly sampled examples from each dataset, respec- tively. To improve the faithfulness of LLM reasoning, we collect all relation paths that satisfy the condition defined in Equation
(1) for each question. This leads to a mee-to-many question-to-relatton mapping, in contrast to the one-to-one mapping adopted by RoG [8]. Our approach yields significant improvements in the Fl score of path generation, with relative gains of 29.3% on WebQSP and 43.0%
8

---

Table 4: Results of Path
Generation (PG) and Constraint
24.7%
20.0%
Extraction (CE).
Peth Gener stler
20
Path Selection Verification
Conctraint Extraction
WebQSP
CWQ
Setting
59
Reazoring
H
F1
H
F1
PG (1:
83.0
59.3
81.2
49.8
PG (1:
93.0
76.7
94.0
71.1
CB
99.0
90.2
99.0
92.9
Figure 4: Error distribution on two datasets.
on CWQ. demonstrating the benefits of leveraging priors. Second, we analyze the failure cases of DP with GPT-4.1 in the main experiment. As shown Figure 4, the majority of errors stem from path generation, path selection, reasoning, and instruction coneetioonfflooiing.. Among these, path generation and selection are closely tied to the utilization of priors, underscoring the importance of effectively incorporating prior knowledge. Reasoning errors, despite the correct path selection, indicate that LLMs may rely excessively on their internal knowledge during response generation. Moreover, we observe that LLMs occasionally fail to adhere to the required answer format for instance, producing "2008" instead of "2008 World Cup." " We found that incorporating cestrcciionfoollwwie exemplars mitigates this issue and yields performance improvements, such 1.1% Hit@) gain on CWQ.
4.5 Backtracking Analysis
Backtracking refers the iterative re-execution of relation path selection, instantiation, and introspec- tion when constraint violation is detected. To
Table 5: Average number of backtracking steps per question across datasets and models.
explore the practical impact of backtracking, we measure how often is triggered during test time. Table 5 reports the average number of backtrack- ing steps per question across CWQ and WebQSP. We observe that GPT-4.1 triggers backtracking more frequently than GPT-3.5 (e.g., 0.21 vs. 0.07 on WebQSP), likely due to its stronger instruction-
Method
Dataset
Model
Backtrack
GPT-3,5
0.10
CWQ
GPT-4.1
0.42
DP
GPT-3,5
0.07
WebQSP
GPT-4.1
0.21
following ability, which enforces stricter constraint checking. This aligns with the performance
differences presented in Table 2, suggesting that more reliable backtracking contributes to better overall reasoning quality.
4.6 Analysis for LLM Interaction
We conduct experiments on CWQ and WebQSP to evaluate the practicality and efficiency of DP. Table 6 presents a comparative analysis of the av- erage number of LLM calls and token consump- tion required by different methods to answer a question across the for DoG and DP are obtained using GPT-3.5,, while additional results of DP with other LLMS are provided in Appendix B.5. Across both datasets, DP consistently outperforms strong baselines across all evaluation metrics. Specif- ically, our framework requires only 2.9 and 2.5 LLM calls on CWQ and WebQSP, respec- hiolly-hgghighhting its efficient utilization of prior knowledge embedded in KGs. In terms of token consumption, DP achieves the lowest output token count while also requiring the least input token consumption. This reflects DP's effec- tiveness in reducing overall token usage during the reasoning process, relying on fewer instructions and exemplars. These findings underscore the superiority of DP compared to existing basclines.
Table 6: Practicality and efficiency Comparison. Call denotes the number of LLM interactions. In- put, Output, and Total represent the number of corresponding tokens. The results of DP are aver- aged over three independent runs.
datasets. The results
Dataset
Method
Call
Input
Output
Total
ToG
22.6
8,182.9
1,486.4
9,669.4 4
PoG
13.3
7.803.0
353.2
8.156.2
CWQ
DoG
12.7
8,298.0
384.6
8,682.6
DP
2.9
2.928.6
186.4
3,115.0
ToG
15.9
6,031.2
987.7
7.018.9
PoG
9.0
5,234.8
282.9
5,517.7
WebQSP
DoG
10.4
7.332.1
277.2
7.604.3
DP
2.5
2,552.8
146.7
2,699.5

---

5 Conclusion and Limitation
This paper presents a trustworthy reasoning framework, DP, which empowers Large Language Models (LLMs) to generate faithful and reliable responses by deliberately reasoning over the priors embedded in knowledge graphs. In the offline stage, DP enables LLMs to generate faithful relational paths through progressive knowledge distillation strategy. In the online stage, it enhances response strategy. These strategies effectively explore and leverage
reliability via structural patterns and constraint priors within knowledge graphs, respectively. Extensive exper- iments conducted on three benchmark datasets demonstrate that DP achieves new state-of-the-ee performance, highlighting its effectiveness, flexibility, and practical applicability. Moreover, the results emphasize the importance of prior exploitation, particularly path generation and constraint extraction, in supporting trustworthy reasoning over knowledge graphs. While this work advances trustworthy LLM reasoning by incorporating knowledge priors, it still relies on human intervention to define constraints when applied vertical domains. In future work, we plan investigate automatic methods for extracting and summarizing constraint types, aiming to further reduce manual effort and enhance scalability.
Acknowledgments and Disclosure of Funding
This work was supported in part by the National Key Research and Development Program of China (2022YF3330300), the National Natural Science Foundation of China (62306229, 62137002, U22B2019, 62477037, 62293553), the Natural Science Basic Research Program of Shaanxi (2023- JC-YBB-533, the Key Research and Development Program of Shaanxi Youth Innovation Team of Shaanxi Universities "Multi-modal Data Mining and Fusion", the Shaanxi Undergraduate and Higher Education Teaching Reform Research Program (23BY195) the Youth Talent Support Program of Shaanxi Science and Technology Association (202401 13), the China Postdoctoral Science Foundation (2024M752585, 2025T180425), and the fund of Laboratory for Advanced Computing and Intelligence Engineering.
the
References
[1] D. Guo, D. Yang, H. Zhang, J. Song, R. Zhang, R. Xu, Q. Zhu, S. Ma, P. Wang, X. Bi et al., "Deepseek-rl: Incentivizing reasoning capability in Ilms via reinforcement learning," arXiv preprint arXiv:2501.12948, 2025.
[2] A. Hogan, X. L. Dong, D. Vrandečić, and G. Weikum, "Large language models, knowledge graphs and search engines: crossroads for answering users' questions." " arXiv preprint arXiv:2501. 0066999, 2025.
[3] Ma, Z. Gao, Q Chai, J. Liu, P. Wang, J. Tao, and Z. Su, "Fortisavqa and maven: a benchmark dataset and dehiasing framework for robust multimodal reasoning," arXiv preprint arXiv:2504.00455 2025.
[4] R. Dominguez-Olmedo, M. Hardt, and C. Mendler- "Questioning the survey responses of large language models," in NeurlPS, 2024, pp. 45 850-45 878.
[5] D. Yang. D. Xiao, J. Wei, M. Li. Z. Chen, K. Li, and L. Zhang, "Improving factuality in large language models via decoding time hallucinatory and truthful comparators," in AAAI, 2025, pp. 606 25 614.
[6] V. Rawte, Sheth, and A. Das, "A survey of hallucination large foundation models," arXiv preprint 20Xiv:2309.05922.20 2023.
[7] M. Li, S. Miao, and P. Li, "Retrieval or reasoning: The roles of graphs and large language models in efficient knowledge-graph-baacc retrieval-augmentee generation," in ICLR, 2025.
[8] L. LUO, Y.-F Li, R. Haf, and S. Pan, "Reasoning on graphs: Faithful and interpretable large language model reasoning," " in ICLR, 2024.
X. Guan, Y. Liu, Lin, Y. Lu, B. He, X. Han, and L. Sun, "Mitigating large language model hallucinations via autonomous knowledge graph-base based retrofitting," in AAAI, 2024, pp. 18 126-18 134.
[10] D. Xu, X. Li. Z. Zhang. Z. Lin, Z. Zhu, Z. Zheng. X. Wu. X. Zhao, T. Xu, and E. Chen, "Harnessing large language models for knowledge graph question answering via adaptive caplict retrieval-augneee "ugmentation,"" in Proceedings of the AAAI Conference Artificial Intelligence, 2025, pp. 25 570-25 578.
10

---

[11] M. Li. S. Miao, and P. Li. "Simple is effective: The roles of graphs and large language models in knowledge-graph-busee
aarrevallaugmmetted generation." in ICLR, 2025.
[12] X. Liang and Z. Gu, "Fast think-on on graph: Wider, deeper and faster reasoning of large language model on knowledge graph." " arXiv preprint arXiv:2501. 143000 2025.
[13] J. Jiang, K. Zhou, Z. Dong, K. Ye, W. X. Zhao, and J.RR. Wen, "Structgpt: A general framework for large language model to reason over structured data," in EMNLP, 2023, pp. 9237-9251.
[14] R. Zhao, F. Zhao, L. Wang, X. Wang, and G. Xu, "Kg-cot: Chain-of-thought prompting of large language models over knowledge graphs for knowledge-aware question answering," in IJCAI, 2024, pp. 6642-6650.
[15] J. Ma, Z. Gao, Q. Chai, W. Sun, P. Wang. H. Pei, J. Tao, L. Song. J. Liu, C. Zhang et al., "Debate on graph: flexible and reliable reasoning framework for large language models," in AAAI. 2025, pp. 24 768 24 776.
[16] S. Ma, C. Xu, X. Jiang, M. Li, H. Qu, C. Yang. J. Mao, and Guo, "Think-or taaik-oo-grree onngraph 2.0: Deep and faithful large language model reasoning with knowledge-guiee retrieval augmented generation," in ICLR, 2025.
[17] Bao, N. Duan, Z. Yan, M. Zhou, and Zhao, (Constraint-basee question answering with knowledge graph," in COLING, 2016, pp. 2503-2514.
[18] K. Ethayarajh, Xu, Muennighoff, D. Jurafsky, and D. Kiela, "Kto: Model alignment as prospect theoretic optimization," arXiv preprint arXiv:2402.01300 2024.
[19] W.-t Yih, M. Richardson, C. Meek, M.-W. Chang, and Suh, "The value of semantic parse labeling for knowledge base question answering." in ACL, 2016, pp. 201-206.
[20] A. Talmor and J. Berant, "The web as knowledge-base for answering complex questions," in ACI, 2018, pp. 641-651.
[21] Y. Zhang, H. Dai, Z. Kozareva, A. Smola, and L. Song, "Variational reasoning for question answering with knowledge graph," AAAI, 2018, pp. 6069-6076.
[22] J. Sun, C. Xu, L. Tang. S. Wang, C. Lin, Y. Gong, L. Ni, H.-Y. Shum, and J. Guo, "Think-on-graph: Deep and responsible reasoning of large language model on knowledge graph." ICLR, 2024.
[23] Z. Li. S. Fan, Y. Gu. X. Li. Z. Duan, B. Dong, N. Liu, and J. Wang. "Flexkbqa: A flexible Ilm-powered framework for few-shot knowledge base question answering." in AAAI, 2024, pp. 18 608-18616.
[24] C. Mavromatis and G. Karypis. "Gnn-rag: Graph neural retrieval for large language model reasoning." arXiv preprint arXiv:2405.20 240.220199
2024. 2024.
[25] E. J. Hu, Y. Shen, P. Wallis, Z. Allen-Zhu, Y. Li, S. Wang, L. Wang, and W. Chen, "LoRA: Low-rank adaptation of large language models," in ICLR, 2022.
[26] A. Saxena, A. Tripathi, and P. Talukdar, "Improving multi-hop question answering over knowledge graphs using knowledge base embeddings," in ACL, 2020. pp. 4498-4507.
[27] J. Shi. S. Cao, L. Hou, J. Li, and H. Zhang, "Transfernet: An effective and transparent framework for multi-hop question answering over relation graph," in EMNLP, 2021, pp. 4149-4158.
[28] J. Jiang, K. Zhou, X. Zhao, and J.-R. Wen, "Unikgqu: Unified retrieval and reasoning for solving multi-hop question answering over knowledge graph." in ICLR, 2023.
[29] L. Chen, P. Tong. Z. Jin, Y. Sun, J. Ye, and H. Xiong, "Plan-on-grape Self-correctigg adaptive planning of large language model on knowledge graphs," in NeurIPS, 2024.
[30] S. Cheng, Z. Zhuang, Y. Xu, F. Yang, C. Zhang. X. Qin, X. Huang, L. Chen, Q Lin, D. Zhang et al., "Call me when necessary: Lims can efficiently and faithfully reason over structured environments," in Findings of the ACI., 2024, pp. 4275-4295.
[31] G. Xiong, J. Bao, and W. Zhao, "Interactive-khqa: Multi-turn interactions for knowledge base question answering with large language models." in ACL, 2024, pp. 10 10561-10558 582.
[32]
T. Ao, Y. Yu, Y. Wang. Y. Deng, Z. Guo, L. Pang, P. Wang. T.-S. Chua, X. Zhang. and Z. Cai, "Lightprof: A lightweight reasoning framework for large language model on knowledge graph." in AAAI, 2025, pp. 23 2244-33499 432.
[33] J. Back, A. F. Aji, and A. Saffari, KKnowledge-augmentt language model prompting for zero-shot knowledge graph question answering," arXiv preprint arXiv:2306.043.5 2023.
11

---

[34] Y. Shu, Z. Yu, Y. Li, B. Karlsson, T. Ma. Y. Qu, and C.-Y. Lin, "Tiara: Multi-grained retrieval for robust large knowledge base," in EMNLP, 2022, pp. 8108-8121.
question answering
[35] M. Galkin, Z. Zhu, H. Ren, and J. Tang, "Inductive logical query answering in knowledge graphs." in NewrIPS, 2022. pp. 15 15 243.
[36] Y. Cui, Z. Sun, and W. Hu, "A prompt-based knowledge graph foundation model for universal in-context reasoning," " in NeurlPS, 2024, pp. 7095-7124.
[37] G. Dong, R. Li, S. Wang, Y. 7hang, Y. Xian, and W. Xu, "Bridging the kb-text gap: Leveraging structured knowledge-aware pre-training for kbqa," in CIKM, 2023, pp. 3854-3859.
[38] M. Yasunaga, A. Bosselut, H. Ren, X. Zhang, C. D. Manning. P. S. Liang, and J. Leskovec, "Deep bidirectional language-knowlegee graph pretraining." " in NeurlPS, 2022, pp. 37 309-37323.
[39] X. He, Y. Tian, Y. Sun, N. Chawla, T. Laurent, Y. LeCun, X. Bresson, and B. Hooi, "G-retriever: Retrieval- augmented generation for textual graph understanding and question answering." in NeurlPS, 2024, pp. 132 822-771132900 907.
[40] P. Jiang, I.. Cao, C. D. Xiao, Bhatia, Sun, and Han, "Kg-fit: Knowledge graph fine-tuning upon open- world knowledge." in NeurlPS, 2024, pp. 136 220-1362522 258.
[41] J. Zhang, X. Zhang, J. Yu, J. Tang, J. Tang, C. Li, and H. Chen, "Subgraph retrieval enhanced model for multi-hop knowledge base question answering," ACL, 2022, pp. 5773-5784.
[42] J. Kim, Y. Kwon, Y. Jo, and E. Choi, "Kg-gpt: general framework for reasoning on knowledge graphs using large language models." EMNLP, 2023, pp. 9410-9421.
[43] Y. Wu, Y. Huang, N. Hu, Y. Hua, G. J. Chen, and Pan, "Cotkr: Chain-of-thought enhanced knowledge rewriting for complex knowledge graph question answering," " EMNLP, 2024, pp- 3501-3520.
[44] Y. Ji, K. Wu, Li, W. Chen, M. Zhong, X. Jia, and M. Zhang, "Retrieval and reasoning on kgs: Integrate knowledge graphs into large language models for complex question answering," Findings of the EMNLP, 2024, pp. 7598-7610.
[45] P. Yixing, Q. Wang, I.. Zhang, Y. Liu, and Z. Mao, "Chain-of-question: A progressive question decom- position approach for complex knowledge base question answering," in Findings of the ACL, 2024, pp- 4763
[46] K. Liang, I.. Meng, M. Liu, Y. Liu, W. Tu, S. Wang, S. Zhou, X. Liu, F. Sun, and K. He, "A survey of knowledge graph reasoning on graph types: Static, dynamic, and multi-modal," IEEE TPAMI, pp- 9456 9478, 2024.
12

---

Technical Appendix
A Related Work
End-to-end Reasoning. To achieve quick and efficient responses, several studies [31,33, 34] directly feed questions along with retrieved triples from Knowledge Graphs (KGs) into text decoders. These approaches primarily focus on extracting critical knowledge to answer the questions. One line of research [33, 35, 36] retrieves relevant facts by performing exact entity matching between the input question and the knowledge graph. The retrieved facts are then provided to Large Language Models (LLMs) through prompt engineering to generate answers. To support more semantically rich queries, another line of work [37, 28, 38-40) incorporates knowledge facts into pre-trained models inspired by masked language modeling and subsequently fine-tunes the retriever within the KGQA task. However, such methods often retrieve only the facts associated with the explicit information present in the question, overlooking implicit cues. To address this limitation, some studies [41, 42, 9] propose decomposing complex questions into sub-questions and retrieving knowledge based semantic similarity between the sub-questions and triples. Nevertheless, these methods often struggle with complex questions, particularly when large number of retrieved facts are directly input into the text decoder, which can overwhelm the model and impair answer quality. In contrast, our proposed framework, DP, employs the reasoning-introspecte and backtracking, effectively avoiding the introduction of false positive paths. It should be noted that our work is the first to employ constraint priors in reasoning to the best of our knowledge.
strategy to perform path selection
Chain-of- oftthttttt Reasoning. With the remarkable success of chain-of- slmin-of-thouur thought prompting, re- searchers [14, 43, 44] have extended step-by-step reasoning to knowledge graph-based tasks. A prevalent approach [13, 22, 45] first identifies the topic entity in the question, then iteratively retrieves and refines a reasoning path until sufficient factual knowledge is gathered or the answer is obtained, and finally leverages L.MMs for answer generation. During the path refinement phase, methods such as DoG [15] utilize in-context learning and multi-agent debate to improve the reliability of generated answers. In contrast to this line of work that decomposes questions step-by-step, another research direction [29, 46, 16] encourages LLMs to directly identify sub-goals of questions and perform rea- soning over retrieved knowledge triples. However, both paradigms may produce unfaithful answers. which is a critical issue in high-stakes domains like legal Docision-making or medical diagnosis. To mitigate this limitation, recent methods [8. 30] first prompt or fine-tune LLMs generate relation paths according to questions and then retrieve relevant knowledge triples based on those paths to ground the final answer more faithfully. Unlike previous approaches [8, 30), DP adopts a progressive knowledge distillation strategy to fine-tune LLMs, enabling them to generate more faithful relation paths by more effectively exploiting structural information. This enhanced exploitation is achieved through a more comprehensive collection of weak supervision signals and a preference-aware path generation.
B Experiment
B.1 Experimental Setting
loaded from Hugging Face and trained using the LLaMA-Factory" framework. All training is conducted on two NVIDIA A800- 80GB GPUs, with bfloat16 precision enabled reduce memory usage and accelerate training. We employ Low-Rank Adaptation (LoRA) to perform an efficient adaptation of large-scale parameters in SFT and KTO. The LoRA configuration uses rank of 16, an alpha of 32, and a dropout rate of 0. and applies to the query, key, value, and output of the self-attention layers. The initial learning rate of SFT training is set to 5c-5, with a warm-up up ratio of 0. The KTO training uses an initial learning rate of le-5, with a preference beta of 0.1 and a warm-up ratio of 0.1. We use the default weights for positive and negative samples, setting A, = >, 1. The batch size of SFT and KTO training is set to 4. The datset statistics are shown in Table 7.
Training Detail. The path generator
Baseline Introduction. We compare existing state-of-the-art SL, ICL, and HL-based methods with DP to verify the effectiveness and superiority.
lncrpe://huggingface.co hattgp///gthabl.ccm/hyyyggggaaaa www.tioyogg//LLaa......o Pactorry
13

---

Table 7: The statistics of WebQSP, CWQ, and MetaQA.
Dataset
KG
Entities
Relations
Triples
Train
Test
Hop
WebQSP
Freebase
2,566,291
7,058 7,058
8,309,105
2,826
1,628
2
CWQ
Freebase
2,566,291
8,309,105
27,639
3,531
MetaQA
Wiki-Movie
43,234
9
133,592
329,282
30,903
3
The SL-based methods are introduced as follows. (1) EmbedKGQA [26] addresses multi-hop question answering over sparse KGs by leveraging KG embeddiings to predict missing links, effectively mitigating KG incompleteness. Unlike prior approaches, it relaxes answer selection constraints, significantly improving multi-hop reasoning performance on sparse KGs. (2) TransferNet [27] is transparent and effective model for multi-hop question answering that unifies reasoning over labeled KG relations and textual relations. It iteratively attends to question components and transfers entity scores along activated relations in differentiable manner, achieving high improvements with interpretable intermediate results. (3) UniKGQA [28] unifies retrieval and reasoning for multi-hop KGQA through shared model architecture and joint parameter learning. By combining semantic matching with information propagation over KGs, it jointly optimizes retrieval and reasoning, improving accuracy and efficiency complex questions. (4) RoG [8] integrates LLMs with KGs via a aaammingrerrievallreasonnn framework that generates KG-grounded relation paths as faithful plans to guide reasoning. This approach enhances reasoning accuracy and interpretability by leveraging structural KG information and supports flexible integration with diverse LLMs. Different from RoG, our proposed framework DP collects question-to-path mappings in the one-to-many form rather than one-to-one. (5) AMAR [10] is an adaptive multi-aspect retrieval framework that enhances LLM reasoning by retrieving and embedding entities, relations, and subgraphs from KGs. It incorporates self-alignment and relevance gating modules to reduce noise and selectively integrate pertinent knowledge, significantly improving accuracy and logical form generation in KGQA tasks. (6) GNN- RAG [24] integrates the graph reasoning capabilities of Graph Neural Networks (GNNs) with the language understanding of LLMs in a aaurieval-augment dense subgraph reasoning paths via GNNs and verbalizing them for LLM reasoning, it effectively addresses multi-hop KGQA and achieves oate-of-thh-as performance with efficient model sizes.
generation framework. By extracting
The ICL-based methods are described below. (1) PoG [29] presents a self-correcting, adaptive planning framework for KG-augmented LLMs that decomposes questions into sub-goah and itera- tively explores, updates, and refines reasoning paths over KGs. By integrating guidance, memory, and reflection mechanisms, PoG improves reasoning efficiency and accuracy complex KGQA tasks. (2) ToG [22] proposes an interactive LLM-KG integration paradigm in which the LLM acts as agent performing beam search over KGs identify and reason along promising paths. This training-frre,, plug-and-play method improves reasoning, knowledge traceability, and correctability, achieving good results with smaller LLMSs and reduced computational cost. (3) Readi [30] enables LLMs to efficiently perform multi-hop reasoning over structured data by generating and iteratively editing reasoning paths only when needed. improves reasoning accuracy and faithfulness while minimizing unnecessary edits, outperforming prior LLM-based methods both KGQA and TableQA benchmarks. (4) DoG [15] is an iterative interactive KGQA framework that improves LLM reasoning through a subgraph- focppiig mechanism and multi-role debate strategy. By reducing distractions from long reasoning paths and mitigating false- positivesiie relations, DoG enables more accurate and reliable answers in complex KGQA scenarios.
The HL-based methods are summarized follows. (1) Interactive- [31] enables LLMs to generate executable logical forms through direct interaction with knowledge bases under minimal supervision. By introducing general APIs and few-shot exemplars for complex questions, it supports step-by-step reasoning and iterative refinement, achieving strong results in low-resource KGQA settings. (2) LightPROF [32] is lightweight and efficient framework for KGQA that enhances LLM reasoning by structurally integrating KGs into prompts. It retrieves relevant subgraphs, encodes their factual and structural information via a trainable Knowledge adapter, and maps them into the LLM embedding space, enabling effective reasoning with minimal parameter updates.
14

---

B.2 Instruction and Exemplar
We show the instructions and exemplars utilized in the module within the Planning and Introspection stages.
B.2.1 Path Generation
Please generate relation paths that can help in reasoning to answer the question. The relation paths must from the tepic entities mentioned in the question. The question is: {question), and the topic entities are: (topic_entities)
B.2.2 Constraint Extraction
You will be given question. Your task is identify and extract any constraints present question.
**Types of constraints to extract:**
1. Type Constraint:
The answer should of a specific type or category.
2. Multi-Entity Constraint:
The question contains multiple entities and requires the simultaneously satisfy conditions related to these entities.
3. Explicit Time Constraint:
specific time period or date is mentioned explicitly.
Implicit Time Constraint:
time period or date is indirectly implied.
5. Order Constraint:
The question involves sequence or ordering.
Instructions:
**Extract only present constraints**: Do not add constraints not explicitly implicitly mentioned in the question.
**Output Format**: Return **List object** with the identified constraints.
constraint type should either contain the relevant information or an empty string if not applicable.
In-Content Few-Shot
Example 1:
Question: What country bordering France contains an airport that serves Nijmegen?
Output: ["1. The ansver should be country", "2. The country borders France", "3. The country contains airport that serves Nijmegen.")
Example 2:
Question: what did james k polk do before he was president
Output: ["1. The question implies the time before James K. Polk was president")]
Example
Question: Who was the 1996 coach of the team owned by Jerry Jones?
Output: ["1. The team is owned by Jerry Jones", "2. The person was the coach in 1996"]
Example 4:
Question: What was the last World Seriea won by the team whose mascot is Lou Seal? Output: ["1. The team is the one whose mascot is Lou Seal", "2. The answer should by the team"]
be World Series", "3. The World Series is the last
Example 5:
Question: What genre is the movie Titanic?
Output: ["1. The answer should be genre of the movie"]
15

---

#*#**
Input question: {question)
Output:
B.2.3
Path Selection
Based on the reasoning relation paths in Freebase, think step by step to select the most one relevant path to anaver the question.
You will be given:
Question: The question to answered.
Topic Entities: The main entities identified the question.
Memory: Paths have been selected and the feedback of the previous step.
Reasoning Paths: A set of reasoning paths starting from the topic entities.
In- Contentt Few-Shol
Example 1:
Question: What aports team owned by George Steinbrenner did Deion Sanders play baseball for?,
Topic Entities: ['Baseball', *Deion Sanders', GGeorge Steinbrenner'),
Memory: 0,
Reasoning Paths: ['Path 1: Baseball -> base www.sspstttbesspeoeeeeo saartt.paayd__bee bluubb clubs Unknown Entity', 'Path 2: Deion Sanders -> sports poorts.pro.tt wtw.ateeleeaattee -> Unknown
Entity apprts.ssprrte.
team -> Unknown Entity', 'Path 3: Deion Sanders
batting stats Unknown Entity baseball. batting_statistice team Unknown Entity', 'Path 4: George Steinbrenner -> sports. spprts_team_ovae owner.. teams_owaar -> Unknown Entity']
Output: ((Path 2}} This path starts from Deion Sanders, follous his professional athlete teams, and connects to a specific sports team. Since the question for the team he played baseball for, this path is the most relevant in identifying the correct team.
Example 2:
Question: What movie was Charlie Hunnam in that was about human extinction?, Topic Entities: ['Human extinction', 'Charlie Hunnam'],
Memory: prrseeeecee_ppthh Charlie Hunnam -> -> film. www.orranceeeeeeeem.mm -> Unknown Entity', 'feedback'; "This path connects Charlie Hunnam films he has acted in,
fflm -> Unknown Entity
need find which movie about human
extinction. '}}},
Reasoning Paths: ['Path 1: Human extinction -> film.ffilll sall__ubject.... films -> Unknown Entity', *atth 2: Charlie Hunnam -> film.actor
actor film -> Unknown Entity -> film. performance. film Unknown Entity', 'atth Charlie Hunnam common. common.topic. notable_types Unknown Entity', 'Path Charlie Hunnam -> tv.tv_actor. starring_roles -> Unknown Entity >> Entity']
character -> Unknown
Output: {[Path 1}} The previous selected path connected Charlie Hunnam films he acted but did not enaure the movie was about human extinction. This path directly connects "Human extinction" to relevant films, making it the best choice to identify the correct movie.
Example 3:
Question: Which state with Colorado River that Larry Owens was born in? Topic Entities: ['Colorado River', 'Larry Owens'], Memory: [('sselecte__path's 'Colorado River -> 1ocation.1ocation. partially_containedby
Unknown Entity', 'feedback'; *This path connects Colorado River to a location, we need to find the state Larry Owens was born in, ?}}, Reasoning Patha: ['Path 1: Larry Owena -> people. peraon.spouse_s -> Unknown Entity -> people. www.sssllnlelaaiiaiaeeeeeeeeeeee saaiiiiiissi.....nnngg -> Unknown Entity²]
Output: {[no path)} None of the available paths lead information about the state where Larry Ovena was born.
16

---

B.2.4 Constraint Verification
Given a question and the associated retrieved knowledge triplets from Freebase, your
task is to answer the question with these triplets and your knowledge.
You will be given:
Question: The question to answered.
Topic Entity: The main entity identified in the question.
Constraints: The constraints extracted from the question that should be verified.
Reasoning Paths: Paths starting from the topic entity (contains only relations). Knowledge Triplets: The instantiated reasoning paths in the form of tripleta entity, relation, entity).
Think step step to answer the question:
List all potential answers (**tail entities**) based the knowledge triplets, ranking them by how likely they satisfy the question constraints, and placing the most likely ones first.
Check if the answer satisfies the constraints and provide an explanation detailing the reasoning process and any missing knouledge needed for full verification. Return **JSON object** with the identified constraints.
Important:
DO NOT output anything except the JSON result. DO NOT add explanations, headers, markdown formatting. Return only the JSON object shown examples.
Output must be a valid JSON object. All strings keys must be enclosed double quotes.
Only return the JSON object, no explanation prefix like "Output:".
Format the output: (("answer"; [...], "sufficient"; "Yes"/"No", "reason"; "..."}}
In Content Few-Shot
Example 1:
Question: what is the name of justin bieber brother
Topic Entity: ["Justin Bieber"],
Constraints: 0,
Reasoning Path: ("Justin Bieber Unknown Entity"],
siblinggs -> Unknown Entity ->
people. wawleessssiingnerlliiieeeeeeeeee relatiiosship.siliing
Knowledge Triplets: [[["Justin Bieber", "people, poople..erson..o. sarroon.sibing... "m. Omxnnuu""")
["m. Ogg.nppp'""", people.sibling, hoaplee.sblingg.elttiinnan www..reetaaaap.siillllllli...
"Jaxon Bieber"]11
Output: {("answer": ["Jaxon Bieber"], "sufficient": "Yes", "reason": "Based the reasoning path, the answer Jaxon Bieber, which the sibling Justin Bieber "}}}
Example 2:
Question: What movie was Charlie Hunnam that was about human extinction?,
Topic Entities: ["Human extinction", "Charlie Hunnam"),
Constraints: ["1. The movie is film Charlie Hunnam acted in.", "2. The movie is about human extinction."],
Reasoning Path: ["Charlie Hunnam -> film. act.r. film Unknown Entity film.
performance film -> Unknown Entity"],
Knowledge Triplets: [[[["Charlie Hunnam", "film, actor, film", "m.Ojwksr" juker", "film. performance. film", "Cold Mountain"]] [["]]]][[[[[ril] [["Charlie Humnam", "film. film", "m.Ojy_sj"], ["m. Ojy_sj", "film. ffilm.eero film", "Green Street"]], [[" Charlie Hunnam", www.aator.ffin "m.066668c"), ("m.046168c", "film "film.performaa performance film", "Children Men"]]]]
["m.0
["Children of Men", "Green Street", "Cold Mountain"], sufficient"; "No", "reason": "The reasoning path connects Charlie Hunnam to films has acted in, we need to find which movie about human extinction," "}}
Output: {["answer":

---

B.3 DP performance with various LLMs
The detailed DP performance with various LLMs, presented mean values with standard deviations, on WebQSP and CWQ is summarized in Table 8.
Table 8: DP performance (mean with standard deviation) on WebQSP and CWQ. The results are averaged over three independent evaluations. We highlight the best performance in bold and the second-best in underline. LM denotes the language model used.
WebQSP
CWQ
MetaQA
LM
H@1
F1
H
H@1
F1
H
H@1
LLaMA311-88 1-BB
87.9+002
82.8=04
75.7=00
70.8
61.1=04
28.9
90.2
87 07
84.1
Qwen3-8B
15.5
82.7
72.3
76.1 10.6
61.7204
60.210.7
90.410.3
89.2
88 88.6102
GPT-3.5
89.7.10.6
86,9103
79.2.00
80.010.
72.610.1
69.2 19.4
96.710..
95.4_03
90.8104
GPT-4o
90.7
87.5=0x
81.4205
85.2+04
74.6=0.5
70.5
96.5+06
95.2-04
94,4+04
GPT-4.1
90.6.10.5
86.7=04
80.1
87.2.10.2
75.8
69.440.
96.8
95.5
94,9
B.4
Exemplar Impacts
We conduct experiments on CWQ and WebQSP to investigate how the number of exemplars influences response generation. As shown in Figure 5, the performance, measured by H@ 1, declines as the number of exemplars increases. This degradation may stem from two main factors: (1) A larger number exemplars results in a longer input context, making more challenging for the model to capture semantic information effectively. (2) The diversity of exemplars remains relatively unchanged despite the increased quantity, which may cause L.LMs to become less confident when encountering out-of ofstiiitibtttinn scenarios.
Constraint Extraction
Path Selection
Constraint Verification
H00 196
CWQ
WebOSP
Number of Exemplars
Number of Exemplars
Number Exemplors
Figure 5: Impact of the number of exemplars response generation. The results are evaluated by H@l. 1.
B.5 Interaction with Different LLMs
Figure presents the token consumption and LLM invocation statistics DP when interacting with various LLMs on the CWQ and WebQSP datasets. The results are averaged over three runs. We see that DP with various LLMs consumes similar tokens and LLM calls answer question, except for Qwen3-8B, which shows higher consumption due to its inherently slow thinking mechanisms. It is worth noting that the token consumption for path generation excluded from this analysis, as that component is executed offline. Overall, these results further validate the practicality and efficiency of the proposed DP framework in real-workk scenarios.
B.6 Case Study
We conduct case studies to qualitatively analyze the strengths and limitations of the proposed framework DP. Figure and illustrate successful cases, while Figure 9 and 10 showcase failure cases. In the successful examples, DP effectively guides LLMS to generate accurate answers by selecting appropriate reasoning paths. When a reasoning path fails to satisfy certain extracted constraints, DP can provide informative feedback, explicitly indicating which constraint is violated.
18

---

Output
CWQ: Average Token
WebQSP: Average Token
4200
4000
2200
2000
CWQ: Average
Average
1.5
2.5
25
2.0
1.-
10
1LAMA3.1-00
Qete33-00 sB
ChanGPT
GFF4
GPY to
G
Ownnn 20
ChanGPt
GP74.8
GPT-40
GPT4
Figure Average token usage and calls of different LLMs.
In contrast, the failure cases highlight two types of errors: incorrect path generation and flawed reasoning. Notably, in the case of path generation errors, the generated paths by DP closely resemble the ground-truth paths, implying that a more robust mechanism may be required better to capture the structural patterns inherent in KGs. In the case of reasoning errors, we see that the LLM fails cover all accurate answers, although the reasoning paths contain the required knowledge facts.
19

---

Question: [Mary] a notable figure in which religion that is observed in [Indonesia]]
Generation:
Path Indonesia oeccttoonaarissiiloeeeeoo..ineio ->Unknown Entity locctioorelligoo.eeennne....eeee
Unknown Entity
Path 2: Mary poople.person.reliionn Unknown Entity
Path 3: Mary
-> Unknown Entity
Constraint Extraction:
answer should religion
2. The religion observed in Indonesia
3. Mary is notable Figure in the religion
Path Selection:
[Path - This path starts from Indonesia and connects to religions observed the country, Since the question is asking about the religion that Mary is notable figure that observed Indonesia, this path is the most relevant to identify the religion.
Q.P
0g Instantiation:
[[['Indonesia", Vecationsfatistiil_gggoo..eeeee 'm.03xf2_w), (tm.:/ll.mm...m.... ['m.03xf2_w, "ecathorreijoonpprrenngggrgrergo
Islam']].
["Indonesia', lecerionsttiistiaaleegooaniiiiii 'm.03xf301"), ['m.03xf301', 'ecctio.relioonneerrrtttgrrrrrrp
Protestontism'll
[[Indonesiaa, iraationstaaiiiiiilaeeeiinnnnnni mm.064sz22), Tm.004szk2", locationnelliioopprrrettagggreee
'atholicism'Ill!
Constraint Verification:
"answer": ["Islam", "Protestantism", "Catholicism").
"sufficient": "No",
"reason": "The reasoning path connects Indonesia to religions observed country. However, we need to further verify which religion Mary, as notable figure, is associated with Indonesia.") (Constraint Constraint 2: Constraint
Feedback
Path:
Path 1: Mary >> people..ersonnreligonn >> Unknown Entity
Path 2: Mary -> base.saints.soint.eeree wwwttttwweeetteeeeeoooooo >> Unknown Entity
Selection:
(Path This path starts from Mary and connects religion. the question specifically about the religion associated with Mary as notable figure, this path directly provides the required information.
6gb Instantiation:
[[['Indonesia', oncationssaiiiiiicaleeeeennnniii 'm.03xf2_w'] ('m.0333 ['m.03xf2_w, locetionellioo__.rrrntggrrrrrggi
Islam']].
[[Indonesia', pncctiinssatisticllleeeioonngngo 'm.03xf301"), ['m.03xf301', 'ecottoneellginn.perrmtttegeeooo
Protestantism"],
[['ndonesia'' pucatiio.statisiioa_eeegoooo.oeo 'm.064szk2'), ('m.064szk2', locctia.rtligoo..errnnttgeeeeeei
'aathliicss'']].
[[[Mary',
Judaism']], [[Mary'', ppople..erson.reliiionn 'Catholicism']]]
Constraint Verification:
'aanswe"; ["Catholicism").
"sufficient": "Yes".
"reason": "Based on the reasoning paths, find that Indonesia observes Islam, Protestantism, and Catholicism. Mary is associated with both Judaism and Catholicism. Considering the constraints, the answer is Catholicism, which is religion observed in Indonesia and Mary, notable figure, is associated with it.")
(Constraint Constraint 2; Constraint 3:
Answer: "Catholicism"
Figure Successful case requiring path selection again.
20

---

Question: What [German Language] speaking European country is also home to the state of [Tyrol]?
Path Generation:
Path Tyrol <> location.admingg aoroiis trative, tww.iie__iiiiiioonocoommmm wiiiiiion.ccnntry... -> Unknown Entity
Path 2:
Tyrol -> location.location containedby Unknown Enfity
Path 3: Tyrol base.aareds.ccheree faihemmmddiiiistratiive http://rrriiieeeeeddmiitsssrrrrr
aireea.dministtrtive__ddd
Unknown Entity
Path 4: Tyrol
_evel__dvviiion Unknown Entity
Path 5: German Language language.human wwnguunnnnnnngeeaaaaaaaaa wwwga/age..ounrrre_...o....ee countries_spoken__n Unknown Enfity
Constraint Extraction:
The country is European country
2. The country speaks Germanic languages
country home state of Tyrol
Path Selection:
(Path 13 This path starts from "Tyrol" and leads to the country it located in, which directly helps identify the European country that is home to the state of Tyrol. The question is asking for country (that is in Europe, is home to Tyrol, and where Germanic languages are spoken): since Tyrol is state/province, following the path from most direct and relevant way to answer. Path 5 may help identify Germanic language- speaking countries, but combining the criteria, starting Tyrol its country primary; you then check if that country Germanic language-speaking.
Tyrol its country
QLP
ogo Instantiation:
[[[['Tyrol',
wdwministrativv_dddiiiio.mmm 'Austria']]])
Constraint Verification:
"answer": ["Austria"),
"sufficient": "Yes".
"reason": "The reasoning path directly connects Tyrol to Austria as its country. Austria is European country and, according to general knowledge, German is the official language of Austria. Therefore, Austria satisfies all the cons constraints: it is European country, speaks Germanic language, and is home to the state of Tyrol.") (Constraint Constraint 2: Constraint 3:
Answer: "Austtria"
Figure 8: Successful case without another iteration.
Question: Before the Euro, what was the currency where [Louis-Eugene Cavaignac] was appointed to governmental position?
Generation:
Path
Louis Eugèèe Cavaignac >> people.person.naionddiie Unknown Enfity locction.ounffy.currresyy.uee
Unknown Entity
(Ground Relation Path: [peeple,.ersom..ationniifff -> location. conittinncountyy. currency _fomerry_ueel
Constraint Extraction:
The answer should currency
2. The currency was before the Euro
3. The currency used the place where Louis-Eugene Cavaignac appointed to governmental position [Only path, need to select]
a
o Instantiation:
[[['Louis-Eugénn Cavalgnac',
'France'], ['France", "locttio.couttyyccureeyyy.uuu 'CFP
franc'l],
[[Louis Bugène Cavaignac', people.persom.nationliit/ 'France'), ['Fancce', docation.country.co cuw.rryy.ccrrency_useee. 'Euro']]]]
Constraint Verification:
"answer": CFC franc", "Euro"),
"sufficient": "No",
"reason": "The reasoning links Gavaignac to France and lists CFP franc and Euro as currencies. However, the Euro is excluded due timing, and the CFP franc is mainly used in overseas territories, not mainland France where Cavaignac served. Thus, neither currency fully satisfies the constraints."? (Constraint Constraint 2: Constraint (No remaining path, end iteration)
Answer: "CFP franc", "Euro"
Ground truth the question: ['Assignat', FFrech franc]
Figure 9: Case of path generation enror.
21

---

Question: Which Super Bowl was won by the team that also won the AFC Championship Game in 2013?
Generation
Path I: Super bowl freebose.type__rofiiee htw.pepproflleeeeuivllleee..eeee
Unknown Entity -fiimerecurring ennerriineeeeeettiiineeeees
Unknown Enfity
Path 2: Super bowl ->
>> Unknown Entity ->
eeneiis -> Unknown Enfity
Path 3: 2013 AFC Championship Game -> https//por...ccoooooooeeeeeeeeer >> Unknown Entity
+> Unknown Entity >>
lime.recuuring_eev event instances -> Unknown Entity
4:m2013 AFC Championship
pports.ports_chappione eeeeotstssppeeeetssssseeee events Unknown Entity
Path S:m2013 AFC Championship Game hooors/pprrs...chmooooooppeeeeep
Unknown Entity
poorts.sports_temm wwt._taa.ccamaaaa championships Unknown Entity
Path 6: 2013 AFC Championship Game -> www.sppts_cchmppishhpppeeee
>> Unknown Entity ->
-> Unknown Enfity
Constraint Extraction:
1. The should be Super Bowl
2. The team won both the Super Bowl and the AFC Championship Game in 2013
Path Selection:
(Path 5) This path starts from the 2013 AFC Championship Game, follows to the champion of the event, and then connects team their championships. Since question asks which Super Bowl was won by the team that the 2013 Championship 6ame, this path the most relevant identify the Super Bowl by that
specific team.
ogo Instantiation:
2013 AFC Championship Game', Ravens', sports.sports__ti searrts__ttammhte ttam.champlonshipps 'Super Bowl XLVII'],
championship_eevent.ooo
'Baltimore Ravens'), ('Bal timore
httpsshii_eeeet.chheeeee chammttcomiion, 'Boltimore Ravens'), ['Baltimore Ravens', 'sports.sports_ httpa/aaaaamcccsiiiee..p.. '2001 AFC Championship Game']],
[[20033 AFC Championship Game',
[[2013 AFC Championship Game', sportsssports_chameee
cetilpeeeeeeeeceeeee nent.cchompion, 'Baltimore Ravens'], ['Baltimore
Ravens', sports.sports__ess seoorss__taammeeem team.championshipst 'Super Bowl XXXV'III]
Constraint Verification:
"aanwwer: ("Super Bowl XLVII"),
"sufficient": "Yes",
"reason": "According the triplets, the Baltimore Ravens Game and have several championships, including Super Bowl XLVII, Super Bowl XXXV, and the 2001 AFC Championship Game. However, the constraints specify the Super Bowl by the team that also won the AFC Championship Game in 2013. Only Super Bowl XLVII matches both constraints, following the 2012 NFL season, with the AFC Championship Game played in early 2013 and both won by the Bal timore Ravens. The other listed championships not satisfy the year constraint. Therefore, 'Super Bowl XLVII' only onswer satisfies constraints.")
champions of the 2013 AFC Championship
it was the Super Bowl played
(Constraint Constraint 2: Constraint
Ground truth of the question: ('Super Bowl XXV 'Super Bowl XL VII)
Figure 10: Case of reasoning error.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We show the main claim in the abstract and introduction. Specifically, we have concluded four contributions in Section 1.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have discussed the limitation Section 5. While this work advances trustworthy LLM reasoning by incorporating knowledge priors, it still relies human intervention to define constraints when applied to vertical domains. the ablation experi- ment, explore replacing the manual definition with automatic summarization. The results present a significant decrease. future work, we plan to investigate automatic methods for extracting and summarizing constraint types, aiming further reduce manual effort and enhance scalability.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification: NA.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have introduced the detailed settings such as implementation details and baselines in Section 4.1 and B.1. We also have released the code with a detailed "readme.md"
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have released the code in https: //github. wwwmmioamaaaiiiaaaeeo aillab/ Deliberation- on- an-Priors with detailed "readme.md" md."" We have clearly described and cited the work of datasets.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
We have described the training and test details in Section 4.1 and B.I. The full details shown in the released code bttps:///githae httpg/gtthu.......iiieeeoee www.mcaaaammaaaalaaa...
Justification:
Deliberation-oe cewloonnoo-PPiice on-Priors.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
23

---

Answer: [Yes]
Justification: The results shown in Table 2 and are obtained by computing the average performance and the standard deviation based three independent runs.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have shown the computing resources such GPU in Section B.1.
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our paper and code adhere to the NeurlPS Code of Ethics.
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We explore the integration of DP and various LLMs in Table The societal impact, such as generating trustworthy responses has been discussed in the analysis.
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [Yes]
Justification: We propose trustworthy framework for large language model reasoning, which has been described in Section 3. The framework employs a progressive knowledge distillation strategy to enhance faithfulness and cassoing-inttoopectiin strategy to promote the reliability response generation. We have verified the effectiveness on various LLMs.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We have cited the corresponding work of the owners of assets used this paper.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We have introduced our released code and model using a clear "readme.md.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: NA.
Institutional review board (IRB) approvals or equivalent for research with human subjects
24

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: NA.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [Yes]
Justification: We have described the usage of LLMs in the analysis of Table 2 and 6.
25


Reviews:
[{"review_id": "5z4EBI8ZdK", "reviewer": "Reviewer_iFUY", "summary": "The paper presents a framework called DP to enhance the reasoning capabilities of LLMs when performing tasks such as KGQA. The framework incorporates a progressive knowledge distillation strategy that integrates the structural priors of KGs into LLMs, improving the faithfulness of relation path generation. Furthermore, DP employs a reasoning-introspection strategy, which verifies whether generated relation paths satisfy predefined constraints, thereby improving the reliability of responses. Extensive experiments on several benchmark datasets demonstrate that DP outperforms current methods, with a 13% improvement in Hit@1 on ComplexWebQuestions.", "questions": "1. The framework relies on predefined constraints for introspection. Could the authors elaborate on potential methods for automating the extraction of these constraints? How would this work in more diverse domains or with complex, domain-specific knowledge graphs?\n\n2. Can the authors provide further insights into the failure cases where DP struggled to generate reliable paths? This would help in understanding its limitations better, especially in more complex reasoning tasks.\n\n3. While the proposed method performs well on benchmark datasets, how does it handle real-world applications where knowledge graphs may be incomplete or noisy?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\nThe paper provides a thorough methodology for improving LLM reasoning by incorporating priors from knowledge graphs, which is a relevant issue in current LLM research. The proposed framework (DP) is novel and is shown to outperform existing methods on multiple benchmark datasets.\n\nThe paper is well-structured and provides clear explanations of the methodology, experimental setup, and results. The figures and examples further aid in understanding the approach and its effectiveness.\n\nThe use of a combination of knowledge distillation and reasoning introspection for enhancing reasoning over knowledge graphs is a novel contribution to the field of LLMs and KG-based retrieval-augmented generation.\n\n**Weaknesses:**\n\n1. While the experiments are extensive, the paper could benefit from deeper analysis of the failure cases, especially those that involve complex, multi-hop reasoning where the proposed method might still struggle. While error analysis is presented, more detailed insights into these cases could help improve the robustness of the framework.\n\n2. The framework relies heavily on predefined constraints, which could limit its flexibility. The authors mention plans for automating the extraction of these constraints, but further discussion on how this would work in diverse domains would be valuable.\n\n3. The method relies on high-quality KGs, which limits its usefulness in real-world scenarios.", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable and constructive comments.\n\n**A1** Our DP framework does rely on a set of predefined constraints that are universal and effective. In **Tabel 3**, we conducted an ablation study where constraints were not manually predefined (**row “w/o CPD”**), but instead a prompt-based approach was used to enable LLM to automatically identify constraint types from the input problem. While this automatic variant slightly underperforms the version with predefined constraints, it still shows promising results (the average decrease in the three indicators on WebQSP and CWQ is only **2.18%**). This may suggest that the manually defined constraint types align well with the specific characteristics of the benchmark datasets. \n\nWe fully agree that automatically extracting constraints is a crucial step to ensure that the framework generalizes to more diverse and specialized domains. In future work, we plan to explore the following aspects:\n\n- **LLM-based In-Context Induction** This method leverages the powerful instruction-following and pattern-learning capabilities of LLMs. By designing specific prompts and providing a few (few-shot) examples of \"question-constraint\" pairs, we can guide the LLM to learn and generalize the patterns for identifying corresponding constraint structures in new questions. For instance, by showing the model that \"Who was the first person to walk on the moon?\" corresponds to an \"ordinal constraint,\" the model can learn to identify similar ordinal logic in other questions.\n- **Semantic Parsing to Logical Forms** This approach involves translating the natural language question into an intermediate, machine-readable logical form (e.g., λ-Calculus or a SPARQL query sketch). The resulting logical form inherently and explicitly contains the core constraints of the question. For example, the question \"Which films were directed by Ang Lee and starred Chow Yun Fat?\" could be parsed into `λx.(directed_by(x, Ang_Lee) ∧ starred_by(x, Chow_Yun_Fat))`. By analyzing this logical form, we can directly and accurately extract the two \"multi-entity constraints.\"\n- **KG** **Schema and** **Ontology** **Analysis** This method directly utilizes the structured *a priori* knowledge defined within the KG itself. By analyzing the KG's schema or ontology, we can automatically extract the rules embedded within. For instance, if a relation `award_year` has a \"domain\" of \"Award\" and a \"range\" of \"Year,\" then any question involving this relation can be automatically associated with a type constraint specifying that \"the answer must be a year.\" This is a high-precision method, though its coverage is limited by the completeness of the KG schema.\n\nIn more complex domains such as law, finance, or medicine, a question's constraints are often more nuanced and implicit. The methods above can work in synergy to address these challenges:\n\n- **Handling Implicit Constraints**: For questions like, \"What public offices did Roosevelt hold before he became president?\", the temporal constraint (\"before he became president\") is relative and implicit. **LLM-based induction** is particularly effective in such scenarios due to its superior ability to understand the contextual and temporal logic of natural language.\n- **Ensuring Logical Rigor**: In domains requiring high precision, such as law or finance, **semantic parsing** can translate complex clauses or questions into unambiguous logical forms. This ensures all conditions are captured accurately, avoiding reasoning errors that can arise from the ambiguity of natural language.\n- **Leveraging Domain-Specific Priors**: In specialized KGs (e.g., a biomedical KG), the schema is often highly detailed. **KG schema analysis** can extract a large number of high-confidence, domain-specific constraints (e.g., \"Protein A *participates in* Biological Process B\"), providing a solid foundation of domain knowledge for the reasoning process.\n\n**A2** Based on our experiments and case analyses (as illustrated in Figures 9 and 10), the failures of the DP framework during the path generation phase can be attributed to the following key factors:\n\n- **Subtle Structural Variations in Complex Reasoning Scenarios**: In some challenging reasoning cases, incorrect paths may exhibit high structural similarity to the ground-truth paths, differing only in a critical relation. For example, in the failure case shown in Figure 9, the model-generated path is nearly identical to the correct one, but a minor deviation ultimately leads to reasoning failure. This suggests that although our progressive knowledge distillation strategy (including SFT and KTO) effectively equips the LLM with a strong understanding of structural patterns in the knowledge graph, it still struggles to distinguish between such \"high-fidelity\" incorrect paths. A potential reason is the lack of sufficiently diverse and contrastive negative samples, which limits the model's ability to capture decisive semantic differences.\n- **Error Accumulation in Multi-Hop Reasoning**: For tasks requiring long-chain reasoning, minor deviations in early steps of path generation can compound and result in significant divergence from the correct path. Although the DP framework incorporates introspection and backtracking mechanisms for error correction, their effectiveness is constrained when the initially generated candidate path set is of low overall quality. In such cases, even the subsequent selection and verification processes may fail to identify a completely correct path.\n\n**Future Directions**:\n\n- **Developing Minimal Yet Informative Negative Sampling:** Rather than introducing overly complex or synthetic negative examples, we aim to design *simple but impactful* negative sampling strategies. For instance, we can mine naturally occurring “borderline” paths within the KG that deviate from gold paths by only one relation or entity. These naturally occurring “near-miss” paths not only reflect realistic ambiguity but also improve the model’s robustness in a lightweight manner. This approach balances discriminative training and implementation simplicity.\n- **Enabling Lightweight and Targeted Path Revision:** Instead of overhauling the entire reasoning path upon constraint violation, we advocate for a **modular, token-level correction mechanism**. This involves allowing the model to revise *only* the faulty component—such as a misaligned relation or misplaced intermediate entity—while retaining valid portions of the path. This incremental correction strategy reduces computational overhead, encourages reusability of partial reasoning, and fits well into few-shot or constrained-interaction settings.\n\n**A3**  DP is intentionally designed with several mechanisms that enable it to handle the aforementioned issues to a certain extent:\n\n- **Decoupling** **of Path Planning and Instantiation**: The DP framework first employs an LLM to generate candidate relation paths and then proceeds to instantiate these paths within the KG to identify concrete entities and facts. This decoupling provides several inherent advantages:\n  - **Handling Incomplete Knowledge**: If a particular fact is missing from the KG, the corresponding path will fail during instantiation and be discarded during the verification phase. The framework then attempts to instantiate alternative candidate paths. Since the path generator typically outputs multiple candidates, this increases the likelihood of discovering a viable reasoning route even under incomplete knowledge conditions.\n  - **Mitigating Noisy Knowledge**: If a spurious fact exists in the KG, leading to an incorrect yet superficially plausible reasoning path, the introspection module plays a crucial role. It evaluates each path against constraints extracted from the question (e.g., type constraints, multi-entity constraints). If the noisy path violates these constraints, it is identified and filtered out, triggering the framework’s backtracking mechanism.\n- **Multiple Candidate Paths with Semantic Selection**: The framework generates multiple candidate paths and applies semantic relevance filtering to prioritize plausible ones. This design ensures that even if some paths are invalidated due to KG noise or incompleteness, the system can still fall back on other semantically valid and executable alternatives within the KG, increasing the robustness of answer retrieval.\n\n**Remaining Challenges and Future Directions**:\n\nDespite these design advantages, we acknowledge that the DP framework faces limitations when deployed on large-scale, noisy, and highly incomplete real-world KGs:\n\n- **Collective Failure of Candidate Paths**: In scenarios where critical portions of the KG are severely missing, all generated candidate paths may fail during instantiation, resulting in the inability to derive an answer.\n- **Constraint-Evasive Noise**: In rare edge cases, an erroneous fact may structurally satisfy all predefined constraints, allowing it to pass through the introspection mechanism undetected.\n\nWhile such extreme conditions are uncommon, they highlight important areas for further enhancement:\n\n- **Integrating** **Knowledge Graph** **Completion**: Although KG completion is a separate research domain, it can be incorporated into our pipeline. During the path instantiation stage, if a path fails due to missing links, a KG completion model can be invoked to predict the missing relations and potentially “repair” the broken reasoning chain.\n- **Incorporating Fact Verification Mechanisms**: Before finalizing an answer, a fact verification step can be introduced to cross-check key facts within the reasoning path using external textual corpora or more trustworthy sources, thereby improving the framework’s resilience to noise.\n\nIn summary, DP demonstrates a degree of robustness in handling imperfect knowledge graphs through its modular design. However, continued research is necessary to further enhance its performance in complex, real-world applications."}, {"review_id": "CuQdQQXtgi", "reviewer": "Reviewer_jD5U", "summary": "The paper tackles hallucinations and factual inaccuracies in knowledge graph-based retrieval-augmented generation by introducing Deliberation on Priors (DP). This two-stage framework leverages structural and logical priors from KGs. In the Progressive Knowledge Distillation stage, LLMs are fine-tuned using KG-derived reasoning paths with a combination of supervised learning and Kahneman-Tversky optimization to incorporate structural priors. The subsequent Reasoning-Introspection stage employs a deliberative verification process that utilises symbolic logical constraints to iteratively refine and filter reasoning paths, thereby reducing hallucinations and enhancing output reliability. Experiments on three KGQA benchmarks demonstrate improved performance, supported by ablation studies that validate the contribution of each component. The authors also experiment and report LLM calls and token counts for practical deployment consideration.", "questions": "* In L125, shouldn’t the function $M$ also have $G$ as the input? Additionally, it is somewhat confusing to write the function defined over the full question set; perhaps writing it over $q$ itself is better. \n* L128, what is the backup option when the reasoning depth is not available? \n* A minor suggestion: Eq (1), *P_w (q)* is a set, so maybe as a convention, write it in bold so that it is clear straightaway. \n* As with any KG or RAG-based framework, performance is highly dependent on the quality of the retrievals/ KG. Can the DP framework also be used to send feedback to the KG retrieval and improve it?\n* SFT and KTO are interesting approaches. In practice, how is this performed? First, SFT is done, and then KTO, or do we keep alternating between them? Was there any ablation performed on this?\n* L178: What does the author precisely mean by semantic alignment? How is this calculated?\n* L200: Backtracking is an interesting part of the framework, and it would be interesting to see in practice how often, for each dataset, backtracking was triggered. \n* Minor: I found Figures 7-9 very interesting and believe there should be discussion or references to them in the main paper as well. \n* Table 2: \n    - I believe the std-dev should be reported here itself rather than a different table in the appendix. \n    - Grouping the methods on the models would be better to see the performance increase. \n    - Why is that with ICL, GPT-4o, GPT-4.1, Llama3.1-8B are not experimented with?\n    - Minor: WebQSP: Llama2-Chat-7B also has 90.7. \n    - In terms of stochasticity in DP, what is the main source of randomness here? Is a higher temperature used in LLMs in the experiments?\n* Table 5, isn’t it a bit unfair comparison as DP has a substantial fine-tuning cost associated, which is not reflected here?\n* Table 4: Why is the performance close to 99 (H) for CE? If it is uniformly sampled, then it should roughly be close to what is presented in Table 2. What am I missing here? \n* In future, what do authors see as the possible methods to incorporate more dynamic constraints and big KGs with not pre-defined reasoning hops?", "limitations": "Authors briefly discuss the limitations with the conclusions in the paper. Authors can discuss the limitations in detail in the appendix. I do not see any direct negative societal impacts.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper presents a technically solid and methodologically rigorous approach addressing hallucination and faithfulness issues in knowledge graph-augmented large language model reasoning. The authors’ two-stage framework—combining progressive knowledge distillation, which incorporates structural priors through supervised fine-tuning augmented with Kahneman-Tversky optimization, and a reasoning-introspection module that leverages symbolic logical constraints for output verification. This is a well-motivated and novel integration. The experimental evaluation is good, covering multiple KGQA benchmarks with comprehensive ablations that isolate the contributions of each component. The inclusion of practical efficiency metrics, such as LLM call and token usage, demonstrates awareness of deployment constraints, thereby increasing the work’s applicability. The paper effectively reduces hallucinations while improving interpretability, offering a promising direction for integrating structured priors into LLM reasoning.\n\nI see a few weaknesses in the paper related to reliance on constraints in the introspection stage, effectiveness of the KTO optimization step, and experiment with different LLMs, which I discuss in the questions section below.", "was_revised": true, "final_justification": "I will update my score as all my concerns are addressed.", "rebuttal": "We thank you for your thoughtful and constructive feedback. We appreciate your recognition of this work.\n\n**A1** We agree that the function definition in Line 125 could be made more precise and readable. To improve clarity, we will revise the statement in Line 125 to：\"**we define a function $\\mathcal{M}$ that maps a question $q \\in \\mathcal{Q}$ to a set of plausible relation paths...**\". This change emphasizes that the function operates on individual questions, rather than on the full question set. The complete input to the function $\\mathcal{M}$ is clearly specified in Equation 1: $\\mathcal{M}(q, e_s, \\mathcal{G}, k)$ .\n\n**A2** When the reasoning depth is not available, our framework defaults to a general backup strategy: we perform shortest-path search over the entire knowledge graph. Specifically, the parameter k in our implementation represents the maximum allowed reasoning depth and is typically provided by the dataset. Extracting a k-hop subgraph centered at the topic entity serves to narrow the search space, significantly improving efficiency during path extraction and instantiation. However, in the absence of such a predefined depth, we fall back to querying the full graph for shortest paths between the topic and target entities. While this ensures correctness, it results in increased computational overhead and longer runtimes due to the expanded search space.\n\n**A3**  You are absolutely right that $\\mathcal{P}_w(q)$ represents a set, and using boldface notation would improve clarity and consistency. We will revise the notation accordingly in the final version to better reflect its set nature. \n\n**A4**  Yes, the DP framework does include a feedback mechanism that improves the effectiveness of KG retrieval, though not in the traditional sense of updating the retriever module directly.\n\nDP transforms the triple retrieval into relation path generation. Specifically, it first generates multiple candidate relation paths and then instantiates them over the KG to ground the answer. In this architecture, retrieval is guided by structured reasoning paths rather than by query-keyword matching, and path selection becomes the central mechanism of retrieval.\n\nThe introspection module plays a critical role in enabling feedback. It evaluates whether the instantiated answers satisfy the pre-extracted constraints. If a candidate path leads to an answer that violates these constraints or lacks sufficient information, the system triggers backtracking to select an alternative relation path from the candidate pool. This mechanism functions as an implicit feedback loop that iteratively refines the path selection process to improve final answer quality.\n\nLooking forward, such feedback could inform KG completion (e.g., when certain paths repeatedly fail to instantiate) or guide refinement of the path generator (e.g., when paths consistently violate constraints).\n\n**A5**  In our framework, the training is conducted in two distinct stages: SFT followed by KTO. We do not alternate between them during training.\n- SFT teaches the model to generate plausible reasoning paths from input questions in a supervised manner, establishing the basic question-to-path mapping.\n- KTO then refines this ability by using preference data to distinguish high-quality paths from suboptimal ones, encouraging the generation of semantically coherent and structurally valid reasoning.\n\nAs shown in Table 3, removing KTO leads to a clear performance drop, highlighting its essential role in enhancing the robustness and faithfulness of the overall DP pipeline.\n\n**A6**  We agree that the use of the term semantic alignment was not clearly defined in the original text, and we will revise the description to improve clarity.\n\nWhat we intended to convey is that semantic alignment refers to the initial relation path selection step, where the model selects the most semantically relevant path to the input question from a set of candidates. At this stage, no verification feedback is available yet—the model relies solely on the semantics of the question and the candidate paths. In subsequent iterations (after backtracking), the model can incorporate feedback signals from the constraint verification module to refine the selection process.\n\nWe will clarify this distinction between initial and feedback-informed path selection in the revised version and refer to Appendix B.2.3 for further details.\n\n**A7**  It is indeed one of the core innovations of our framework. Measuring how frequently backtracking is triggered in practice provides useful insight into how often the system encounters and resolves constraint violations during reasoning.\n\nWe analyzed our test-time logs and computed the average number of backtracking steps per question for each dataset, summarized below:\n|Dataset|GPT-3.5|GPT-4.1|\n|:-:|:-:|:-:|\n|WebQSP|0.07|0.21|\n|CWQ|0.10|0.42|\n\nGPT-4.1 triggers backtracking more often than GPT-3.5, likely due to its stronger instruction-following ability, which leads to stricter constraint checking. In contrast, GPT-3.5 may rely more on internal heuristics and skip verification steps. This also corresponds with Table 2, where GPT-4.1 yields better performance.\n\n**A8**  In the final version, we will add a dedicated case study section to highlight the significance of these examples, along with relevant references and brief discussions in Sections 3.2 and 3.3 to further illustrate their connection to the strengths and limitations of our framework.\n\n**A9**  We appreciate your detailed suggestions regarding Table 2. Below we address each point in turn:\n\n1. You are absolutely right that reporting the std-dev directly in Table 2 improves clarity. The reason we placed it in the appendix originally was due to space limitations in the main paper. In our revised version, we will integrate the std-dev values into the main table for better accessibility.\n2. This is a very helpful suggestion. We have reorganized the table to group methods based on the underlying LLMs, which makes performance comparisons more intuitive. Please see the updated version below (**W, C, and M denote the WebQSP, CWQ, and MetaQA datasets, respectively.**):\n|Model|Method|H(W)|H@1(W)|F1(W)|H(C)|H@1(C)|F1(C)|H(M)|H@1(M)|F1(M)|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|GPT-3.5|ToG|76.2|-|-|58.9|-|-|-|-|-|\n||PoG|82.0|-|-|63.2|-|-|-|-|-|\n||DoG|88.6|62.6|54.2|58.2|49.4|56.6|95.4|85.1|87.2|\n||**DP**|**89.7**|**86.9**|**79.2**|**80.0**|**72.6**|**69.2**|**96.7**|**95.4**|**90.8**|\n|GPT-4|ToG|82.6|-|36.4|69.5|-|31.8|-|-|-|\n||PoG|87.3|-|-|75.0|-|-|-|-|-|\n||DoG|**91.0**|65.4|55.6|56.0|41.0|46.4|**98.3**|90.1|93.1|\n||**DP**|90.4|**86.7**|**81.7**|**85.6**|**74.6**|**71.1**|96.7|**95.4**|**94.8**|\n\n3. Our main experimental setting uses GPT-3.5 and GPT-4, which are also the backbones used in baseline works like ToG, PoG, and DoG. This ensures a fair comparison under consistent model conditions. The additional experiments with GPT-4o, GPT-4.1, and LLaMA3.1-8B are primarily meant to validate the generalizability and compatibility of DP across a range of modern models, rather than to compare with prior baselines under few-shot ICL.\n\n4. Thank you for pointing this out—we acknowledge this omission and will correct it in the updated table.\n\n5. Yes, the DP pipeline does involve a certain level of randomness, mainly due to using a sampling temperature of 0.8 when invoking LLMs during path generation and introspection. However, as shown in Table 7, the std-dev across runs remains below 1.0, indicating that DP produces stable and reliable results despite this inherent stochasticity.\n\n**A10** We agree that DP has fine-tuning costs, but in this analysis, we focus on the costs associated with generation and inference.\n\nThe training cost is a one-time cost, whereas the inference cost is incurred repeatedly with each query. Therefore, the total cost for generating responses is a combination of both the training and inference costs. As the number of queries (n) increases, the training cost can be spread over more queries, which makes it less significant in comparison to the growing inference cost.  \n\nTo clarify this, we use the following formula to express the total cost: $C_{\\text{total}} = \\frac{C_{\\text{train}}}{n} + n \\cdot C_{\\text{infer}}$.  \n\nAs $n$ increases, the inference cost becomes more important, and the training cost for each query decreases. This means that as the number of queries increases, inference cost becomes the main factor and becomes increasingly important over time. This gives DP an efficiency advantage in real-world scenarios.\n\n**A11**  We appreciate your attention to the evaluation details. There may be a misunderstanding regarding the hit rate (H) reported for CE in Table 4. Here, CE stands for **Constraint Extraction**, and the H metric measures how accurately the model extracts constraints from questions—not answer correctness. Specifically, we annotated 100 examples with gold-standard constraints and computed how often the model’s output matched them. The high score (~99) reflects strong extraction accuracy on this subset and is not directly comparable to the H scores in Table 2.\n\n**A12** Our current DP framework uses a set of predefined constraints, which work well in controlled settings. However, enabling automatic constraint acquisition is essential for broader applicability. In future work, we plan to:\n\n- Use LLMs to analyze representative questions and generalize common constraint patterns within a domain.\n- Leverage KG schema or ontology (e.g., entity types, relation domains/ranges) to infer likely constraints. For example, if a relation’s range is “Year,” the system can enforce type consistency for answers.\n\nAdditionally, as noted in our response to Q2, the fixed reasoning hop limit is used only during training to bound the subgraph for efficient path extraction. The framework does not rely on a fixed number of hops and can naturally scale to large KGs with flexible or unbounded reasoning depth."}, {"review_id": "plkmNdG4uQ", "reviewer": "Reviewer_K6r7", "summary": "This paper proposes \"Deliberation on Priors\" (DP), a trustworthy reasoning framework for Large Language Models (LLMs) on Knowledge Graphs (KGs). The framework addresses hallucinations in LLMs by better exploiting prior knowledge embedded in KGs, specifically structural information and constraints. DP consists of four modules: (1) Distillation - using progressive knowledge distillation with supervised fine-tuning and Kahneman-Tversky optimization to integrate structural priors; (2) Planning - generating candidate relation paths; (3) Instantiation - grounding paths in KG triples; and (4) Introspection - verifying reasoning paths against extracted constraints with backtracking capability. The authors evaluate DP on three KGQA benchmarks (WebQSP, CWQ, MetaQA) and demonstrate state-of-the-art performance with improved faithfulness and reliability.", "questions": "1. Is it feasible to design an automatic constraint extraction strategy to replace the manual predefinition of constraint types? This would further improve the scalability and practicality of your approach in real-world applications, where manual annotation may not be viable.\n2. In Section 3.1, you employ Dijkstra's algorithm to identify all shortest relation paths from the subject entity $e_s$ to the ground-truth answer entity $e_t$. In this setting, is there always a unique shortest path for a specific entity pair, or can multiple shortest paths of equal length exist?\n3. Table 3 provides a comprehensive ablation study across WebQSP and CWQ datasets, showing the contribution of each component in the DP framework. I notice that removing any of the three modules leads to a similar drop in performance. Could you elaborate on why these three perturbations result in comparable degradation? Does this imply that each component contributes independently and equally to the overall performance?\n4. Appendix B.5 (Figure 6) shows the token consumption and LLM invocation statistics for different model integrations. I am curious why integrating DP with **Qwen3-8B** leads to the highest token consumption compared to other LLMs. Is this due to specific characteristics of the model, such as verbosity in generation, or differences in decoding strategies?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n1. The challenge addressed in this paper, enhancing the faithfulness and reliability of response generation, is highly relevant to KG-based Retrieval-Augmented Generation (RAG). To this end, the authors introduce a trustworthy reasoning framework, DP, which enables large language models to generate faithful and reliable responses through deliberate reasoning over priors embedded in knowledge graphs. \n\n2. Extensive experiments across three datasets with multiple LLMs (LLaMA, GPT variants) demonstrate the framework's flexibility and consistent improvements. The ablation studies provide good insights into component contributions.\n\n3. The method requires significantly fewer LLM calls (2.5-2.9 vs 10-22 for baselines) while maintaining superior performance, making it practically valuable.\n\n**Weaknesses**\n1. One limitation of the proposed method is the manual definition of constraint types. As shown in Table 1, these types are predefined rather than automatically extracted. However, in real-world applications, it is often necessary to extract such constraints automatically. Although the authors include experiments comparing the performance of DP with and without manually defined constraints, the performance of response generation degrades without manual input. \n\n2. Testing on only 500 samples from WebQSP/CWQ due to \"computational constraints\" raises questions about the robustness of conclusions, especially given the relatively small performance margins in some cases. The shortest-path heuristic for collecting supervision signals may not capture all valid reasoning paths, potentially limiting the diversity of learned patterns. The paper acknowledges this limitation but doesn't thoroughly investigate its impact.", "was_revised": true, "final_justification": "The authors have provided a detailed and thoughtful rebuttal that effectively addresses the key concerns raised in my initial review. Specifically, the authors convincingly elaborate on how the current use of predefined constraints can be extended to more diverse domains through a combination of LLM-based in-context induction, semantic parsing to logical forms, and KG schema analysis. Also, I appreciate the authors’ acknowledgment of the limitations when faced with noisy or incomplete KGs. Moreover, their discussion of future extensions (e.g., integrating KG completion and fact verification) shows promising pathways toward deploying the method in real-world settings. So I increased my rating from \"borderline accept\" to \"accept\".", "rebuttal": "We sincerely thank you for your thoughtful and constructive review. We greatly appreciate your recognition of the motivation and contributions of our work—particularly the trustworthiness of the DP framework, the practical value of reduced LLM calls, and the thoroughness of our experiments and ablations.\nYour comments and questions helped us reflect more deeply on both the strengths and limitations of the current design. Below, we address each of your concerns in detail and clarify several points that were unclear in the original version.\n\n**A1** You raise an important point regarding the scalability of our framework when constraint types are manually defined. We fully agree that enabling automatic constraint acquisition would significantly improve the practicality of our approach in real-world applications.\n\nIn fact, we conducted an ablation study (see **Table 3, row “w/o CPD”**) where constraints were not manually predefined. Instead, we used a prompt-based method to let the LLM automatically identify constraint types from the input question. While this automatic variant slightly underperforms the version with predefined constraints, it still shows promising results. This may suggest that the manually defined constraint types align well with the specific characteristics of the benchmark datasets. However, their effectiveness may not generalize to more diverse or open-domain settings, where more flexible and adaptive constraint extraction strategies would be required.\n\nIn future work, we plan to explore this direction through the following approaches:\n- Leveraging prompt-based methods to guide large language models in analyzing representative questions and automatically identifying, abstracting, and generalizing common constraint patterns within a target domain.\n- Exploiting the schema or ontology of the knowledge graph, which encodes valuable structural and semantic information (e.g., entity types, relation domains and ranges). By analyzing this metadata, the system can infer potential constraints. For example, if a relation’s domain is “Film” and its range is “Year,” any query involving this relation can be automatically linked to a constraint such as “the answer type must be a year.”\n\n**A2** In our setting, multiple shortest paths of equal length may exist between a given subject entity $e_s$ and answer entity $e_t$, and we account for this in our supervision process. For instance, for the question `\"What is the name of Justin Bieber’s brother?\"`, both of the following reasoning paths can lead to the correct answer `\"Jaxon Bieber\"`:\n\n```text\n1. [\"Justin Bieber\", \"people.person.sibling_s\", \"m.0gxnnwp\"], [\"m.0gxnnwp\", \"people.sibling_relationship.sibling\", \"Jaxon Bieber\"]\n2. [\"Justin Bieber\", \"people.person.parents\", \"Jeremy Bieber\"], [\"Jeremy Bieber\", \"people.person.children\", \"Jaxon Bieber\"]\n```\nTo capture such diversity, we use Dijkstra’s algorithm to collect all shortest-length relation paths, rather than selecting just one. This helps us maximize the supervision signal and enables the model to learn from multiple semantically equivalent reasoning routes.\n\n**A3** While Table 3 shows that removing any of the three modules—constraint extraction, path selection, or constraint verification—results in a comparable performance drop, this does not imply that these modules contribute independently or equally to the overall performance.\n\nEach of the three modules plays a distinct yet interdependent role in the DP framework:\n- Constraint extraction provides semantic guidance by identifying meaningful conditions to be satisfied.\n- Path selection ensures the reasoning process focuses on plausible paths that align with both the query and the extracted constraints.\n- Constraint verification serves as a filtering mechanism that enforces answer validity by cross-checking constraints post hoc.\n\nAlthough the degradation appears numerically similar across ablations, this is likely due to the fact that removing any single module breaks the coherence of the pipeline. For instance, without constraint extraction, the subsequent modules lack semantic grounding; without path selection, the search space becomes noisy and inefficient; and without constraint verification, spurious or weakly supported answers may be retained.\n\nIn this sense, the performance drops are not indicative of independent or redundant contributions but rather suggest that these components are synergistic—each is critical, and disabling one disrupts the end-to-end reasoning process.\n\n**A4** The higher token consumption observed with Qwen1.5-8B is mainly due to its verbose generation style. Qwen3-8B is optimized for reasoning tasks and tends to explicitly articulate its intermediate reasoning steps, resulting in longer outputs compared to other models like GPT or LLaMA. This verbosity, while potentially beneficial for transparency and interpretability, naturally increases token usage during inference."}, {"review_id": "I09GxEpKwn", "reviewer": "Reviewer_BKJv", "summary": "The manuscript introduces Deliberation on Priors (DP), a reasoning framework for knowledge graph-based retrieval-augmentation generation (KG-RAG) that utilizes priors embedded in knowledge graphs (KGs). DP first fine-tunes an LLM on a given KG and then distills its knowledge using Kahneman-Tversky optimization. The distilled LLM generates relation paths for each entity mentioned in a question. These paths are instantiated and validated using manually-defined constraints extracted from the question. If validated, the path is used by another LLM to generate an answer. Experiments on three KG question-answering (QA) datasets show that DP outperforms existing approaches.", "questions": "1. In the knowledge distillation stage, any path from the source entity to the ground truth entity that involves the source entity’s neighbor within k hops is used as ground truth. However, such paths may be irrelevant to the question. Why are these potentially irrelevant paths not filtered before being used for training?\n2. When both DP and the baselines are evaluated using the same language model, does DP still achieve state-of-the-art performance?\n3. The test sets for each dataset were uniformly sampled by the authors. Are these samples identical to those used to evaluate the baseline models?\n4. How well do naïve LLMs perform on these tasks? In line 261, while the authors state that ‘DP can enhance the reasoning reliability of various LLMs,’ the performance of naïve LLMs is not reported, which weakens this claim.", "limitations": "The proposed framework, DP, requires fine-tuning on a specific KG. Consequently, applying it to a different KG requires additional fine-tuning, which limits its scalability and applicability across diverse KGs.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n1. The manuscript is clearly written and easy to follow. Figures and tables are used appropriately and effectively to enhance understanding. Additionally, terms and notations are consistently defined before use, contributing to overall clarity.\n2. The idea of validating relation paths using constraints extracted from the questions is compelling. These constraints help ensure that the validated paths align with the question's intent, thereby enhancing the precision of the reasoning process.\n\n**Weaknesses**\n1. The constraints are manually defined, requiring manual effort for each domain and question type. This heuristic limits the generalizability of the proposed method. Moreover, manually crafted constraints may not be optimal, which could cap the performance of the framework.\n2. In the distillation stage, an LLM is fine-tuned on a specific KG and before knowledge distillation. This approach limits the framework’s scalability, as it requires separate fine-tuning for each KG, reducing its applicability across diverse domains.\n3. The supervised learning baselines employ different language models, making it difficult to attribute performance differences solely to the framework. To ensure a fair comparison, experiments using the same underlying language model for both DP and the baselines are necessary.\n\n**Minor Issue**\n1. Line 97: ‘a instantiation’ should be corrected to ‘an instantiation’.", "was_revised": true, "final_justification": "The manuscript initially raised concerns regarding the fairness of its experimental comparisons, particularly due to the use of different test sets. However, this issue has been addressed in the rebuttal. Taking into account the methodology, the authors' response, and the subsequent discussion, I decided to rate the manuscript as \"4: borderline accept\".", "rebuttal": "We sincerely thank you for your thoughtful and constructive feedback. We appreciate your recognition of the clarity of our writing, the novelty of validating relation paths through question constraints, and the effectiveness of our experimental results. We also value your insightful concerns regarding the manual definition of constraints, the scalability of our knowledge distillation process, and the fairness of model comparisons. Your comments have helped us better understand the limitations of our current submission and guided several improvements and clarifications in both the revised draft and the responses below.\n\nIn what follows, we address each of your questions and concerns in detail. We also provide additional experimental results to support our claims, clarify methodological decisions, and discuss possible directions for improving the generalizability of our approach.  \n\n**W2** The primary goal of fine-tuning in the distillation stage is to enhance the **faithfulness** of LLMs in generating relation paths that align with the structural patterns of the target KG. This is critical not only because the subsequent instantiation module directly relies on these generated paths to retrieve and ground entities from the KG, forming complete reasoning trajectories, but also because high faithfulness is particularly indispensable in **specialized domains such as healthcare and legal services**—fields where the accuracy and trustworthiness of responses are paramount, as unreliable information can lead to severe consequences. Without such fine-tuning, while in-context learning (ICL) can indeed prompt LLMs to generate relation paths, their faithfulness is significantly compromised.  \n\nThe root cause is that existing LLMs, despite broad knowledge, lack sufficient exposure to the specific structural nuances and relation semantics of a given KG. This leads to paths that are semantically plausible but structurally inconsistent with the KG, undermining downstream reliability.  \n\nNotably, our fine-tuning is designed to be **cost-efficient**. We employ LoRA during both SFT and KTO, which efficiently adapts large-scale parameters with minimal computational overhead. Furthermore, the training data for fine-tuning is automatically acquired: the weak supervision signals (question-to-path mappings) are extracted by identifying the shortest traversal sequences from topic entities to answer entities in the KG using the Dijkstra algorithm, eliminating the need for manual construction.  \n\nEmpirically, our fine-tuning strategy yields substantial improvements in path generation quality: Table 4 shows that the Hit rate of our path generation reaches 94.0% after fine-tuning, confirming the enhanced faithfulness of the generated relation paths. This improvement directly translates to better overall performance, as reflected in Table 2, where our method outperforms ICL-based baselines by over 20 percentage points in F1 score across datasets.  \n\n**Minor Issue**: Thank you for pointing this out. We will carefully review the manuscript and revise any potential typos.  \n\n**A1** Thank you for raising this important concern. We agree that including irrelevant paths during the distillation stage could introduce noise and affect the model’s reasoning quality. In fact, we have explored several filtering strategies during development, including semantic similarity filtering and LLM-based relevance prediction. However, we observed that these approaches tended to over-filter and remove semantically plausible but indirect reasoning paths.\nFor instance, in the case of the question `\"What is the name of Justin Bieber’s brother?\"`, both of the following paths can lead to the correct answer `\"Jaxon Bieber\"`:\n1. \n```text\n[\"Justin Bieber\", \"people.person.sibling_s\", \"m.0gxnnwp\"],  \n[\"m.0gxnnwp\", \"people.sibling_relationship.sibling\", \"Jaxon Bieber\"]\n```\n2. \n```text\n[\"Justin Bieber\", \"people.person.parents\", \"Jeremy Bieber\"],  \n[\"Jeremy Bieber\", \"people.person.children\", \"Jaxon Bieber\"]\n```\nWhile the second path is logically valid and factually correct, it is often mistakenly filtered out due to low semantic overlap with the original question. As a result, these filtering methods, though effective at removing noise, risk eliminating valuable reasoning paths and reducing coverage of the answer space.\n\nAlthough we ultimately chose not to apply a filtering mechanism during the distillation phase, this decision allows us to retain a diverse set of reasoning paths, including those that are logically valid but semantically distant from the question. We acknowledge that this choice inevitably introduces some irrelevant paths, which may interfere with downstream reasoning.\n\nTo address this, our framework incorporates path selection and constraint validation during the introspection stage. These components are designed to identify and promote paths that are both answer-relevant and constraint-compliant, thereby substantially reducing the negative impact of irrelevant paths on final answer generation.\n\n\n**A2** Thank you for raising this important point regarding model comparability.  In our study, the main baselines we compare against are **ToG**, **PoG**, and **DoG**, as these works all follow the iterative reasoning paradigm similar to **DP**. These baselines represent the state-of-the-art in KGQA, and therefore serve as the most appropriate points of comparison for our proposed method.  \n\nTo ensure fairness, we conducted experiments using **ChatGPT(GPT-3.5)** and **GPT-4** as the backbone LLMs, aligning with the backbone choices in ToG, PoG, and DoG. These results are reported in **Table 2** of our paper.\n\nFor clarity, we reproduce the relevant results from Table 2 below to directly compare the performance of DP with ToG, PoG, and DoG under the same backbone LLMs (**W, C, and M denote the WebQSP, CWQ, and MetaQA datasets, respectively.**):\n|Model|Method|H(W)|H@1(W)|F1(W)|H(C)|H@1(C)|F1(C)|H(M)|H@1(M)|F1(M)|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|ChatGPT|ToG|76.2|-|-|58.9|-|-|-|-|-|\n||PoG|82.0|-|-|63.2|-|-|-|-|-|\n||DoG|88.6|62.6|54.2|58.2|49.4|56.6|95.4|85.1|87.2|\n||**DP**|**89.7**|**86.9**|**79.2**|**80.0**|**72.6**|**69.2**|**96.7**|**95.4**|**90.8**|\n|GPT-4|ToG|82.6|-|36.4|69.5|-|31.8|-|-|-|\n||PoG|87.3|-|-|75.0|-|-|-|-|-|\n||DoG|**91.0**|65.4|55.6|56.0|41.0|46.4|**98.3**|90.1|93.1|\n||**DP**|90.4|**86.7**|**81.7**|**85.6**|**74.6**|**71.1**|96.7|**95.4**|**94.8**|\n\n\n**A3** Thank you for highlighting this important issue regarding test set consistency. \nIndeed, we observed that the baseline methods vary in how they select their test sets—some use the full test set, while others use randomly sampled subsets. This inconsistency makes it difficult to directly align test samples across all prior works. \nIn our case, due to the high cost of LLM inference, we sampled a fixed number of examples for evaluation:\n- 500 examples each for WebQSP and CWQ,\n- 600 examples for MetaQA.\nTo ensure the fairness and reliability of our comparison, we selected DoG—a strong and representative baseline—and re-evaluated it on the exact same sampled test sets used for DP. This allows for a controlled, head-to-head evaluation using identical data.\nWe present the comparison results below:\n\n|Model|Method|H(W)|H@1(W)|F1(W)|H(C)|H@1(C)|F1(C)|H(M)|H@1(M)|F1(M)|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|ChatGPT|DoG*|88.6|62.6|54.2|58.2|49.4|56.6|95.4|85.1|87.2|\n||DoG**|87.2|62.9|54.1|59.1|48.5|57.5|94.2|86.6|86.8|\n||**DP**|**89.7**|**86.9**|**79.2**|**80.0**|**72.6**|**69.2**|**96.7**|**95.4**|**90.8**|\n|GPT-4|DoG*|**91.0**|65.4|55.6|56.0|41.0|46.4|**98.3**|90.1|93.1|\n||DoG**|90.8|65.8|54.9|58.1|39.2|46.2|97.8|91.0|93.2|\n||**DP**|90.4|**86.7**|**81.7**|**85.6**|**74.6**|**71.1**|96.7|**95.4**|**94.8**|\n\nThe \"*\" represents the original results in the paper, and \"**\" represents the results when using the same sampling set as DP. W, C, and M denote the WebQSP, CWQ, and MetaQA datasets, respectively.\n\nAs shown above, DP consistently outperforms DoG across all datasets when evaluated on the same sampled test sets, further validating the effectiveness of our method under controlled conditions.\n\n**A4** Thank you for raising this point. We would like to clarify that the performance of naïve LLMs was evaluated as part of our ablation study, specifically in Table 3, second row. This row corresponds to the setting where GPT-4.1 is used directly for question answering without any retrieval or reasoning augmentation, representing the baseline performance of a naïve LLM on these tasks.\nAs shown in Table 3, the naïve GPT-4.1 model performs significantly worse than our framework on both WebQSP and CWQ datasets. This empirical result directly supports our claim that DP can enhance the reasoning reliability of various LLMs (**W and C denote the WebQSP and CWQ datasets, respectively.**).\n|Setting|H(W)|H@1(W)|F1(W)|H(C)|H@1(C)|F1(C)|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|**DP(GPT-4.1)**|**90.6**|**86.7**|**80.1**|**87.2**|**75.8**|**69.4**|\n|GPT-4.1|74.0|71.0|54.6|56.0|53.0|48.9|\n|w/o KTO|88.3|84.7|77.3|86.0|74.6|67.3|\n|w/o PT|88.4|84.8|77.6|86.4|75.0|68.4|\n|w/o EPS|90.0|85.8|79.4|86.6|73.8|68.1|\n|w/o RD|88.3|84.8|77.8|87.2|74.1|67.7|\n|w/o Introspection|86.6|82.0|75.7|85.3|70.8|65.2|\n|w/o CPD|87.8|83.4|76.4|86.2|74.4|68.5|\n|w/o feedback|88.0|83.0|76.5|85.4|73.2|67.1|\n\nWe appreciate your attention to this aspect and hope this clarification helps demonstrate the effectiveness of our approach more clearly."}]

Author rebuttal:

Meta-review: (a) Summarize the scientific claims and findings of the paper based on your own reading and characterizations from the reviewers.
This paper introduces "Deliberation on Priors" (DP), a novel framework designed to enhance the trustworthiness of Large Language Models (LLMs) when reasoning over Knowledge Graphs (KGs). The primary claim is that by explicitly leveraging both structural and logical "priors" from the KG, the framework can mitigate LLM hallucinations and improve the faithfulness and reliability of generated responses. The DP framework operates in two main stages: (1) a Progressive Knowledge Distillation stage that integrates the KG's structural priors into the LLM via supervised fine-tuning (SFT) and Kahneman-Tversky Optimization (KTO), teaching the model to generate structurally valid reasoning paths; and (2) a Reasoning-Introspection stage where the LLM uses extracted logical constraint priors from the question to verify, filter, and refine these paths via a backtracking mechanism. The authors demonstrate through extensive experiments on three benchmark KGQA datasets (WebQSP, CWQ, MetaQA) that DP achieves new state-of-the-art results, significantly outperforming existing methods in accuracy and faithfulness, while also being more efficient in terms of LLM API calls.

(b) What are the strengths of the paper?
The paper has several strengths, as also highlighted by the reviewers:

High Relevance and Novelty: The work addresses the critical and timely problem of LLM hallucination in the context of retrieval-augmented generation. The proposed DP framework is a novel and well-motivated contribution, cleverly combining knowledge distillation of structural information with a symbolic, constraint-based verification loop.

Strong Empirical Results: The method demonstrates substantial performance gains over strong baselines across multiple datasets and LLMs. The authors' claims of state-of-the-art performance are well-supported by the evidence, which was further strengthened during the rebuttal period with statistical significance tests.

Methodological Rigor and Clarity: The paper is well-written, clearly structured, and easy to follow. The proposed framework is explained in detail, and the ablation studies are comprehensive, effectively isolating and validating the contribution of each component of the DP framework.

Practical Considerations: The authors show awareness of real-world deployment constraints by analyzing and reporting on the efficiency of their method, noting that DP requires significantly fewer LLM calls than competing iterative reasoning approaches.

(c) What are the weaknesses of the paper? What might be missing in the submission?
The initial submission had a few weaknesses, which were largely addressed during the rebuttal but are still worth noting as limitations of the approach:

Reliance on Predefined Constraints: The framework's introspection module, in its highest-performing configuration, relies on a set of manually defined constraint types. This limits its out-of-the-box generalizability to new domains where such constraints are not readily available. While the authors demonstrated a feasible automated alternative, it came with a performance trade-off.

KG-Specific Fine-tuning: The approach requires a fine-tuning stage for each target KG. While the authors argue this is efficient due to LoRA, it still presents a scalability hurdle compared to purely zero-shot or in-context learning methods, making it less suitable for applications that need to query many different KGs dynamically.

Dependence on KG Quality: Like all KG-based reasoning methods, DP's performance is inherently capped by the quality, completeness, and accuracy of the underlying knowledge graph.

(d) Provide the most important reasons for your decision to accept/reject. For spotlights or orals explain why the paper stands out (other than by high scores or popularity trends).
The primary reason for acceptance is that this is a technically solid paper that makes a valuable contribution to an important area of research. The strengths—a novel and effective framework, strong and now rigorously validated empirical results, and clear presentation—outweigh the acknowledged limitations.

The authors engaged with the feedback, conducting extensive new experiments to address reviewer concerns about evaluation fairness, statistical significance, and baseline comparisons. This strengthened the paper, its scientific rigor, and the validity of the work. The final paper, incorporating the results of these discussions, will be a valuable addition to the NeurIPS program.

(e) Summarize the discussion and changes during the rebuttal period. What were the points raised by the reviewers? How were each of these points addressed by the authors? How did you weigh in each point in your final decision? (Do not mention reviewer names. Use their anon ids instead.)
The discussion period was productive and led to significant improvements in the paper's evaluation and claims. The main points raised and addressed were:

Manual Constraints (raised by iFUY, K6r7, BKJv): Reviewers were concerned about the scalability of relying on manually defined constraints. The authors addressed this by pointing to an ablation study in the paper that used an automated, prompt-based approach and showed it was still effective, though slightly less so than the manual version. They also detailed several promising avenues for future work on automatic constraint extraction, which satisfied the reviewers (e.g., K6r7).

Evaluation Fairness and Robustness (raised by jD5U, K6r7, BKJv): This was the most critical area of discussion.

Sampled Test Sets: Reviewer BKJv questioned the use of sampled test sets. The authors responded by first re-evaluating a key baseline on their exact sampled set to ensure a fair head-to-head comparison. Following further discussion, they went above and beyond by re-running their method on the full test sets for WebQSP and CWQ, demonstrating that their method remains state-of-the-art. This was a crucial change that significantly strengthened the paper's claims.

Inconsistent Base LLMs: Reviewer BKJv pointed out that comparing methods using different underlying LLMs was problematic. The authors provided new results comparing DP with other supervised methods using the exact same LLaMA2-Chat-7B model, as well as a comprehensive table comparing naive LLM performance vs. DP-enhanced performance for a wide range of models.

Statistical Significance: Reviewer jD5U correctly noted the absence of statistical tests for the results. In response, the authors ran their model 10 times, performed one-tailed t-tests against the best baselines, and confirmed that their improvements were highly statistically significant (p<0.001). They committed to updating the tables to only bold results that meet this criterion.

Scalability due to Fine-Tuning (raised by BKJv): The authors defended the necessity of fine-tuning for achieving high faithfulness and argued that their use of LoRA makes it computationally efficient. They also provided specific details on the computational cost.

The authors' thorough responses grounded in empirical results led reviewers jD5U, K6r7, and BKJv to explicitly state their concerns were addressed and raise their scores. This engagement and the resulting improvements were a major factor in my final recommendation to accept the paper. The paper is now substantially stronger and more convincing as a result of the review process.
Decision: Accept (poster)