DAMR: Efficient and Adaptive Context-Aware Knowledge Graph Question Answering with LLM-Guided MCTS
Authors: Yingxu Wang
Shiqi Fan
Mengzhu Wang
Siyang Gao
Chao Wang
Nan Yin
Venue: ICLR 2026 Poster (2026)
Keywords: Knowledge Graphs
Question Answering
LLMs
Primary area: other topics in machine learning (i.e., none of the above)

Abstract: Knowledge Graph Question Answering (KGQA) aims to interpret natural language queries and perform structured reasoning over knowledge graphs by leveraging their relational and semantic structures to retrieve accurate answers. Existing methods primarily follow either the retrieve-then-reason paradigm, which relies on Graph Neural Networks (GNNs) or heuristic rules to extract static candidate paths, or dynamic path generation strategies that employ large language models (LLMs) with prompting to jointly perform retrieval and reasoning. However, the former lacks adaptability due to static path extraction and the absence of contextual refinement, while the latter suffers from high computational costs and limited evaluation accuracy because of their dependence on fixed scoring functions and repeated LLM calls. To address these issues, this paper proposes Dynamically Adaptive MCTS-based Reasoning (DAMR), a novel framework that integrates LLM-guided Monte Carlo Tree Search (MCTS) with adaptive path evaluation to enable efficient and context-aware KGQA. DAMR leverages MCTS as a backbone, where an LLM-based planner selects the top-k semantically relevant relations at each expansion step to effectively reduce the search space. To enhance evaluation accuracy, we introduce a lightweight Transformer-based scorer that performs context-aware plausibility estimation by jointly encoding the question and relation sequence through cross-attention, thereby capturing fine-grained semantic shifts during multi-hop reasoning. Furthermore, to mitigate the scarcity of high-quality supervision, DAMR incorporates a dynamic pseudo-path refinement mechanism that periodically generates training signals from partial paths explored during search, enabling the scorer to continually adapt to the evolving distribution of reasoning trajectories. Extensive experiments on multiple KGQA benchmarks show that DAMR significantly outperforms state-of-the-art methods.

Published as a conference paper at ICLR 2026
DAMR: EFFICIENT AND ADAPTIVE CONTEXT-AWARE KNOWLEDGE GRAPH QUESTION ANSWERING WITH LLM-GUIDED MCTS
Yingxu Wang', Shiqi Fan"; Mengzhu Wingn, Gao", Chao Wang', Nan Yin
Mohamed bin Zayed University of Artificial Intelligence Hong Kong Polytechnic University
3 Hebei University of Technology 4 City University of Hong Kong
$ Ke Holdings Inc. Hong Kong Space Robotics and Energy Centre Limited
{y fyingxv. wang, dreamkily, chanceycn, yinnan yiwnan8911/emmaala..... @maail,.m@......m1111..111111. com si siyangaoecityu edu. hk, comp-shigi. http-sshhi..fa@cooooo.o.. fan@connecteec. pow.u...oooo..............
ABSTRACT
Knowledge Graph Question Answering (KGQA) aims to interpret natural lan- guage queries and perform structured reasoning over knowledge graphs by lever- aging their relational and semantic structures to retrieve accurate answers. Existing methods primarily follow either the retrieve-then-reasonn paradigm, which relies Graph Neural Networks (GNNs) heuristic rules extract static candidate paths, or dynamic path generation strategies that employ large language models (LLMs) with prompting jointly perform retrieval and reasoning. However, the former lacks adaptability due to static path extraction and the absence of contex- tual refinement, while the latter suffers from high computational costs and limited evaluation accuracy because of their dependence on fixed scoring functions and repeated LLM calls. To address these issues, this paper proposes Dynamically Adaptive MCTS-bass
Reasoning (DAMR), a novel framework that integrates LLM-guided Monte Carlo Tree Search (MCTS) with adaptive path evaluation to back-
enable efficient and context-aware KGQA. DAMR leverages MCTS bone, where an LLM-based planner selects the top-k semantically relevant rela- tions each expansion step effectively reduce the search space. To enhance evaluation accuracy, we introduce a lightweight Transformer-based scorer that performs context-aware plausibility estimation by jointly encoding the question and relation sequence through cross-attention, thereby capturing fine-grained se- mantic shifts during multi-hop reasoning. Furthermore, to mitigate the scarcity of high-quality supervision, DAMR incorporates a dynamic pseudo-path path refinement mechanism that periodically generates training signals from partial paths explored during search, enabling the scorer to continually adapt to the evolving distribution of reasoning trajectories. Extensive experiments on multiple KGQA benchmarks show that DAMR significantly outperforms -hhe-----rh-rtt methods.
INTRODUCTION
Knowledge Graph Question Answering (KGQA) (Dammu et al., 2025 Saxena et al. 2020 Choi
et al. 2023) leverages structured relational knowledge to enable factual, interpretable, and robust reasoning. By combining the expressiveness of natural language with the precision of knowledge graphs, KGQA provides grounded framework for complex reasoning and reliable answer genera- tion (Liu et al. 2025 Yao et al. 2025). Recent advances integrate Large Language Models (LLMs) into KGQA to enhance semantic understanding and generalization, bridging the gap between sym- bolic reasoning and neural representation learning.
Existing KGQA approaches can be broadly categorized into two paradigms according to how rea- soning paths are constructed: retrieve-then-reant methods and dynamic path generation strategies.
"Equal contribution.
Corresponding author.

---

Published as a conference paper at ICLR 2026
In the former, candidate paths extracted prior to answer prediction, typically using Graph Neural Networks (GNNs) (Ma et al. 2025a Yao et al., 2025) or rule-based heuristics (Fang et al. 2024). However, such methods exhibit limited adaptability, semantics during inference, while heuristic rules remain inherently inflexible and cannot support dynamic refinement of reasoning (Liu al.) 2025 Yao et al. 2025). In contrast, dynamic path gen- eration strategies unity retrieval and reasoning by constructing paths dynamically during question processing. These methods either leverage LLMs to iteratively generate paths through in-context learning or Chain-of Th-Tuhhhh (CoT) (Sui et al. 2024; Li et al. 2024b). or employ guided search techniques such as MCTS, where paths are incrementally expanded with path scorer (Ma et al., 2025b Shen et al.) 2025). While offering greater flexibility, such approaches suffer from substantial computational overhead due to repeated LLM calls and limited evaluation accuracy, as static scorers cannot capture the evolving semantics of reasoning paths (Chang et al. 2024 Lee et al. 2024).
GNNs fail to incorporate guesttionspeecilee
This paper investigates the design of an adaptive KGQA framework to address challenges of compu- tational inefficiency and limited path evaluation accuracy in dynamic reasoning. However, develop- ing such a framework raises three key challenges: (1) How to modularize reasoning to reduce LLM overuse in search? Inefficiency in dynamic KGQA stems from repeatedly invoking LLMs for rela- tion retrieval and reasoning in multi-hop path construction (Shen et al.] [025 Long et al. 2025b). Although methods such as CoT and MCTS enable flexible exploration, they bind LLMs to every decision step, causing high inference cost and poor scalability. The challenge is to design a modular framework that leverages LLMs efficiently, guiding search without direct involvement each step. (2) How to accurately evaluate evolving reasoning paths? ? As multi-hop paths are incrementally con- structed, their semantics evolve with each added relation and context. Yet existing methods rely on static scoring or shallow similarity metrics that fail to capture these semantic shifts (Xu et al. 2024 Sui et al., 2024). This highlights the challenge of designing path evaluation model that adaptively captures ine-grained changes conditioned on both the question and evolving relation sequence. (3) How to train a reliable evaluation model with limited supervision? Accurate path ranking requires well-calibrated scorer, yet dynamic reasoning generates many incomplete paths with only a few valid ones. This results in imbalanced, noisy supervision, especially for multi-hop questions where successful trajectories
scarce. While reinforcement learning has been explored (Ma et al. (2024a] Zhai et al. 2024), it suffers from sparse rewards and unstable optimization. The key challenge is to construct reliable learning signals from limited supervision support adaptive scorer training.
To address these challenges, we propose Dynamically Adaptive MCTS- Reasoning (DAMR), an efficient framework that integrates LLM-guided MCTS with context-aware semantic modeling for accurate and efficient KGQA. DAMR employs an MCTS backbone, where an LLM-based plan- ner dynamically guides path expansion by selecting semantically relevant relations at each step, thereby reducing the search space and improving answer identification. For path evaluation, we introduce a lightweight Transformer-baas based scorer that jointly encodes the question and relation se- quence via cross-attention, enabling context-sensitive plausibility estimation and capturing evolving semantics during multi-hop reasoning. To mitigate supervision scarcity, DAMR further incorporates dynamic pseudo-path mechanism that continuously adapts the scorer during search: partial paths from MCTS rollouts are ranked by predicted plausibility and converted into pseudo-path supervision pairs, amplifying signals from promising trajectories while suppressing noise from suboptimal ones. Our contributions are summarized as follows:
We study adaptive path reasoning in KGQA, where the key challenges lie in capturing the evolv- ing semantics of multi-hop reasoning paths and ensuring computational efficiency during search, motivating the need for dynamic and context-aware reasoning strategies.
We propose DAMR, a novel framework that integrates MCTS with a dynamically adapted path evaluation model, enhancing evaluation accuracy while maintaining computational efficiency.
We conduct extensive experiments across multiple KGQA benchmarks, demonstrating that DAMR consistently outperforms state-of state-of-the-art the-art methods.
2 RELATED WORK
Knowledge Graph Question Answering (KGQA). KGQA aims to enhance reasoning capabili- ties by incorporating external knowledge graphs to answer natural language questions (Choi et al.) 2023
Xu et al. 2025). Existing KGQA approaches can be broadly classified into two categories:
2

---

Published as a conference paper at ICLR 2026
eetrieve-then-reee then-resonn and dynamic path generation. The first category extracts candidate reasoning paths using Graph Neural Networks (GNNs) et al. 2025a; Yao et al. 2025) or rule-based heuris- (ics(Fang al. 2024). followed by LLM-basee answer generation. While GNNs learn embeddings to identity relevant paths and rule-based methods apply predefined patterns (Zhao et al. 2023] Liu al., 2025), these approaches lack the flexibility to adapt dynamically to question-specife context during inference, In contrast, dynamic path generation methods, such as CoT prompting (Sui et al.) 2024 Li al. 2024b) and MCTS (Ma et al. 2025b| Shen et al.) (025), unify retrieval and reason- ing for more flexible exploration. However, they suffer from high computational overhead due to repeated LLM calls, and static scorers often fail to adapt to evolving path semantics (Long et al.) 2025b Luo et al. 2025, Ma et al., 2024b). To address these challenges, we propose an adaptive framework that integrates symbolic search with a fine-tuned evaluation model, aiming to improve both computational efficiency and reasoning accuracy in KGQA.
Adaptive and Self-Improving Reasoning Models. A promising approach to developing adaptive reasoning models is to frame the process within reinforcement learning (RL) paradigm, where an agent learns a policy to navigate a state space. Early methods such as DeepPath (Xiong et al. 2017) and MINERVA (Das et al. 2018) used RL to discover reasoning paths by rewarding the agent only when a correct answer is reached. However, this leads to the sparse rewards problem, as pos- itive feedback arrives only after long action sequences, resulting in weak learning signals and poor exploration efficiency (Zhai et al.] 2024] Chang et al. (023). To address this challenge, an alter- native self-training via pseudo-labeling predictions (Lee et al. 2013] Xie et al. 2020). While commonly used in semi-supervised learning, pseudo-labeling proves especially effective reasoning tasks with limited supervision (Wang al.) 2022 Huang et al. 2025). Instead of relying on sparse terminal rewards, we leverage intermedi- ate search paths as dynamic pseudo-paths offering dense and adaptive supervision. This facilitates continual refinement of the path evaluator to better capture the evolving semantics of reasoning.
where the model learns from its own high-confidence
3
METHODOLOGY
Q: What structure opened in 1922 Hollywood, CA?
3.1 PROBLEM FORMULATION
Pre-training Evaluator S
b. Selection
We define Knowledge Graph Question Answering (KGQA) as the task of answer- ing a natural language question by reason- ing over a knowledge graph (KG). The KG is typically represented as set of triples A. = ((e,,r,e.)) C & x R x E, where E and R denote the sets of en- tities and binary relations. The goal of KGQA is to find a set of answers A, C for question q. such that a reasoning path through the KG leads from a topic entity to the correct answer. Formally, this is often framed as mapping q to an exccutable query program Pq. where (LM KC) = Aq.
Emityy d)
valsc: We, concet:
Relations
Pi
PC
value
Yuguet
Context-Aware Path Evaluation
c. LJM Guided
Simulation & Backpropagation
((e1, (1,,,T1,e)) (e2, ez)
Expansion
LLM
P
Path-based Dynamic Refinement
3.2 OVERVIEW OF FRAMEWORK
S(q.P)) S(G.P)) >S(p.s)
In this paper, we propose a dynamically adaptive reasoning framework DAMR for KGQA, as shown in Fig. [ DAMR comprises three components: (1) LLM
Answer: Graumnn's Egyptian Theatre
Figure I: Overview of DAMR. The reasoning process begins with an MCTS guided by an LLM-based plan- ner, which selects top-k semantically relevant relations at each expansion step. A context-aware path evalua- tor scores each candidate path during simulation. To enable continual adaptation, high-confidence pseudo- paths generated during search are used to dynamically fine-tune the evaluator.
Guided Expansion. DAMR employs MCTS to incrementally expand reason- ing paths, guided by an LLMM-baee plan- ner that proposes relevant relations. This reduces computational overhead and en- hances efficiency in KG exploration; (2)
3

---

Published as a conference paper at ICLR 2026
Context-Aware Path Evaluation. To capture the evolving semanties of reasoning paths, DAMR employs a lightweight Transformer- based scorer with cross-attention to jointly encode the question and path embeddings. This enables context-sensitig evaluation and improves the accuracy and rel- evance of multi-hop reasoning; (3) Path-based Dynamic Refinement. DAMR uses intermediate paths from MCTS as dynamic pseudo-pate to iteratively fine-tune the path evaluator, enhancing its ability to capture question-specific semantics and improving reasoning accuracy.
3.3 LLM GUIDED EXPANSION
A key challenge in KGQA is efficiently exploring the vast search space of multi-hop reason- ing paths, especially under weak or no supervision. Existing methods often struggle to balance search efficiency and semantic relevance, resulting in either redundant exploration or missed correct paths (Long et al., 2025b; Li et al. 2024a). To address this, the LLM-Guided Expansion module employs MCTS (Koesis & Szepesvári (006) the backbone for symbolic path expansion. At each step, an LLM proposes semantically relevant relations, narrowing the search space and improving path quality, while MCTS ensures balanced trade-off between exploration and exploitation.
Specifically, each node in the MCTS represents a reasoning state anchored at a specific entity in the KG. Given the current state, possible actions correspond to selecting outgoing relation to extend the reasoning path. During the Selection phase, the search traverses from the root to a leaf node by recursively choosing children with the highest Upper Confidence Bound for Trees (UCT) score (Kocsis & Szepesvári 2006), which is defined as:
In
UCT +
C
74
74
where w; denotes the accumulated reward of node i, n, its visit count, N the visit count of its parent, and C a constant that balances exploration and exploitation. This criterion guides the search to relations and exploiting promising paths. In the Expansion phase, the selected leaf node is expanded by retrieving the outgoing relations of its entity e; denoted as
trade off between exploring
Re, = [ri, r2 ). J. To avoid exhaustive branching, we prompt an L.M with the question g and candidate relations Re,, selecting the top-k relations most semantically aligned with q:
Rtop- k LLM Re:).
These top-k relations are then used to generate new child nodes, ensuring that expansion favors semantically meaningful directions and remains computationally efficient.
3.4 CONTEXT-AWARE PATH EVALUATION
While LLM-guided expansion effectively narrows the search space by selecting semantically rel- evant relations, it does not ensure that all expanded paths remain valid in the broader reasoning context. As the search progresses, path semantics evolve dynamically, and early promising trajec- tories may later become misleading or irrelevant. Prior works attempt to filter or pre-plan paths to improve relevance (Fang et al. 2024) Long al,, 2025a)), but still leave gaps in capturing evolving path semantics during search. To address this, we integrate a lightweight Transformer-basee path scorer into MCTS's simulation phase, employing cross- cross-attention to jointly encode the question and current path, enabling adaptive evaluation that reflects evolving semantics.
Context-Aware Path Evaluator. the Simulation phase, we assess the quality of candidate paths generated during MCTS rollouts. Given question q and candidate relation path p, (ri, "r,,,,...,,17 rt), where pr is formed by sequentially selecting relations during expansion, both and P, are first encoded using pre-trained L.M.. Let 2, E RRd denote the embedding of q and zr, Bd the embedding of relation r,. To capture the sequential structure of pr. we introduce a learnable positional encoding e,t" for each relation. The final input sequence is obtained by combining Zr, with e,00 and feeding the sequence into Transformer encoder:
Ep. = Transformer(iz, + + ..... Zr, 1r,+te e 1)
(3)
where e,th E is the positional embedding of the i-th hop, drawn from trainable matrix Epos RLxd where L is the maximum path length and d the embedding dimension. To further
4

---

Published as a conference paper at ICLR 2026
incorporate question-specifie information, apply cross cross-attention mechanism, allowing the en- coded path representation ep, to attend to the question embedding Zy:
H Ep. + CrossAtta (Ep,. zn), with ProssAttn(Ep,.. zyy) softmax (E,," 1 /zz) Zq. (4)
We then apply attention pooling over the relation H to obtain the hidden state of the relation path:
Sp. Σi= I'a.b, ar Softmax Softmax (MLP(H)),
(5)
where h, is the hidden state of the i-th relation and a, its learned attention weight. This pooling allows the model to emphasize informative steps along the reasoning path. The pooled path rep- resentation Sp- is then concatenated with the question embedding Zy. and the combined vector passed through multi-layer perceptron to compute the plausibility score of the question-path pair:
(( = MLP %z))-
(6)
This context-aware evaluator assigns plausibility scores to partial reasoning paths by jointly encod- ing the question and relation sequence, providing accurate, context-sensitive guidance for MCTS.
Pre-training of Evaluator. To train the context-aware evaluator, we construct supervision by sam- pling positive and negative paths from local subgraphs. A path is positive if links the head entity to a correct answer within a hop limit. Negatives come from two sources: hard negatives that terminate near but miss the answer, and random negatives from walks that avoid answer entities. Each training instance is a triplet (g. p" p* .p"), ). with sequences prro-padded and masked for efficient batch training.
The model computes a plausibility score S(g. p) for each question-path pair and is optimized using the Pair-wise Ranking loss (Rendle et al. 2012) to encourage higher scores for positive paths:
M
CPR
logo (S(q, ),,) -(g.
M
where (.) is the sigmoid function. This training strategy equips the evaluator with the ability to dis- tinguish plausible reasoning paths, thereby improving the guidance signal during MCTS inference.
3.5 PATH-BASED BASED DYNAMIC REFINEMENT
While LLM-guided expansion and semantic scoring improve path exploration, the static evaluator may fail to generalize to the evolving search space. To address this, we introduce dynamic refine- ment mechanism that leverages high-confidence paths from MCTS rollouts as pseudo-paths, These pseudo-paths serve as supervision signals, enabling continual adaptation of the evaluator to new reasoning contexts without requiring additional labeled data.
Specifically, during Backpropagation phase, the plausibility score estimated by the context-aware path evaluator is propagated along the visited nodes in the MCTS tree after each simulation. For every entity e, on the simulated path, we update its visit count and aggregated value as follows:
We. E, Rey Wey
ne. ne. +
where ne, is the visit count and We, is the aggregated value of entity e;. The value is computed as weighted average over its child nodes {ej], and reflects the plausibility scores Wey assigned during simulation. These updates refine the UCT estimates used in future selection steps, progressively biasing the search toward high-quality reasoning paths.
To construct supervision signals for fine-tuning, we dynamically sample pseudo-path pairs W/ 13)) from the set of explored paths during MCTS. Instead of relying the evaluator's predictions, we assign pseudo-labels based on empirically grounded values derived from the search process. Specif- ically, for entity e along a reasoning path pr, we define its search value as: We. me.
War where wp.
is the cumulative reward from all rollouts passing through pr., and ne, is the visite count of entity e,. Given pair of paths, we assign pseudo-labels based their relative values:
(p/. Pby), if We, > Wey! (p/ p)), otherwise.
(Φt
The path evaluator is then fine-tuned using the Pair-wise Ranking loss in Eq. encouraging higher scores for more promising paths.
5

---

Published as a conference paper at ICLR 2026
3.6 REASONING PROCESS
The overall reasoning process is outlined in Appendix [A] The framework first initializes a path evaluator discriminate between plausible and implausible KG paths, providing a foundation for downstream search. During dynamic MCTS, the algorithm iteratively performs selection, expan- sion, simulation, and backpropagation. In expansion, an LLM-based planner adaptively selects the top-k relations most relevant to the question, steering the search toward semantically meaningful paths. The evaluator guides simulation by prioritizing trajectories likely to yield correct answers, while pseudo-pade -athh pairs sampled during search are periodically used for refinement. Finally, entities reached by high-scoring paths are aggregated to form the answer set.
3.7 THEORETICAL ANALYSIS
While DAMR dynamically refines the path evaluator during search, an important question remains: this self-improving process stable and convergent? this part, we provide a theoretical analysis showing that DAMR's dynamic pseudo-label refinement is both statistically stable and provably convergent. The analysis focuses on three properties: (1) variance reduction of the pseudo-label estimator, (2) directional consistency of the pairwise ranking objective, and (3) global convergence of the joint refinement process.
Lemma (Stability of Pseudo-label Aggregation) Under the assumption that rollout samples $j
for node e are i..dd. sub-Gaussin Gaussian with variance proxy of and n!! increases monotonically, then:
= (e),
Varlw[++]] s oft/n!t)) /n!(+))
As of decreases with (the scorer becomes more consistent) and ne grows, the variance of pseudo- labels exhibits double decay and converges to zero.
Proof Sab-Gaussian aggregation implies variance reduction by Var 0² /n. Applying this to (t)
8j yields the stated bound, with of capturing rollout dispersion. As ne and of 4o w(()) converges to its expectation (=)) in L2-
This lemma guarantees that the pseudo-labels for self-supervision become statistically stable as training proceeds. Even if early rollouts are noisy, repeated exploration and averaging prevent error amplification, ensuring subsequent scorer updates rely on smooth, reliable targets.
Lemma (Directional Consistency of Scorer Updates) Let (p=,p=) denote a pseudo-pair where 1/2 for some margin 0, then
pt has a higher aggregated value than p If the expected gradient of the pairwise loss is aligned with the gradient of the true ranking risk:
LPVL)R(S)) VRrank(S) S -crl|/VRranxxS))
where c depends on the curvature of the logistic link. This means that each update step reduces ranking error in expectation, even when pseudo-labell are noisy.
Proof Under the margin condition, the logistic surrogate is a proper scoring rule: the expected sign the score difference A =SS(q.p)) (Sq.pp))-S(g ") positive with probability at least } ty, Taking expectation over pairwise samples yields a negative correlation between the expected gradient of Len and the gradient of true ranking risk, scaled by et > 0 determined by logistic curvature.
This result ensures that each scorer update reduces ranking eтror in expectation, rather than drifting due to noisy pseudo-labels. The scorer thus consistently learns to prefer plausible reasoning paths, stabilizing the refinement process and mitigating self eeff-coniiratioon bias.
Proposition 1 (Contraction and Fixed-point Convergence) Define thecomposite refinement map:
(()(0)) Update(5(0) ((((1)))))) (s(())
where (S(()) is the label map generated by MCTS aggregation and Update(-) performs a gradient step on LpR. If both maps are Lipschitz continuous with constants Lu and Lg satisfying Lgs < 1, then
[| G(S L.g Tow -5'1l2

---

Published as a conference paper at ICLR 2026
and G is contraction mapping. By Banach's 's fixed-point theorem, there exists unique stable point S" such that 550) as oc..
Proof Since Update is Ls-Lipschitz and w (+(++)) is Lng-Lipschitz in expectation, we have [[g(S)- ((2)) S L. - 1/ When Lig Toe < 1, 9 is a contraction, implying convergence to unique fixed point.
This proposition provides a formal guarantee that DAMR's dynamic refinement process converges: the interaction between evolving pscudo-labels and scorer updates constitutes contraction map- ping, ensuring that the model stabilizes rather than oscillating or diverging.
Overall, the analysis reveals that DAMR's dynamic refinement achieves statistical stability, direc- tional consistency, and convergence to a fixed equilibrium. These theoretical properties elucidate the mechanism by which DAMR mitigates feedback drift and sustains robustness when trained solely on self-generated supervision.
EXPERIMENTS
4.1 EXPERIMENTAL. SETTINGS
Datasets. To evaluate the effectiveness of DAMR, we conduct experiments on two widely used KGQA benchmarks: WehQSP Talmor& Berant 2018) and CWQ Yih et al. (2016). Following prior work|Sun et al. (2023): Liu et al. (2025), , we uniformly sample 1,000 questions from the test sets of
both datasets to evaluate the performance. More details about datasets are provided in Appendix B
Baselines. We compare DAMR with comprehensive set of baselines. These baselines include: the semantic parsing methods, e.g., KV-Mem (Miller et al. 2016), EmbedKGQA (Saxena et al. 2020).
QGG (Lan & Jiang] 2020), NSM (He et al.) 2021), TransferNet (Shi et al.] 2021). and KGT5 (Saxena
cct al.
2022); the retrieval-based methods, c.g., GraftNet (Sun et al.] 2018). PullNet (Sun et al. SR+NSM (Zhang al. (022), and SR+NSM+E2E (Zhang al. 2022); the general L.Ms,
2019).
including Flan-T5-xl (Chung et 20024).. Alpaca-7B (Taori et al. (023)) Llama3-8B (Dubey et al. Qwen2.5-7B [Team] 2024), CharGPT (Schulman al. (022)) and ChaiGPT+CoT (Wei al.
2024).
2022
and recent LLMs with KG methods, including UniKGQA (Jiang et al. 2022) Yu
2022). KD-CoT (Wang al., 2023). Nutrea (Choi al.
2023). ToG (Sun al. 2023).
RoG
et al. 2023), KAPING (Back et al. 2023). ReasoningLMM M (Jiag et al. 2023). FiDeLis (Sui 2024). GNN-RAG (Mavromatis Karypis [2224). DoG (Ma al.] 2025a). DualR (Liu al.
al.
2025
DP (Ma et al. 2025b), and RwT (Shen et al. 2025). The details are provided in Appendix
Implementation Details. We implement the DAMR framework using PyTorch, and all experiments are conducted on NVIDIA A100 GPUs. The LLM based planner is implemented with GPT-4.1 (Liu jet al.] 2003),, while question and relation embeddings are generated from Qwen3-Embedding- 8B (Yang et al. 2025) with embedding dimension of 1024. For the path evaluation module, we use a dimeniinaa embedding and employ the Adam optimizer (Kingmal (0144) with a learning rate of 1 x 10 during pretraining and 1 x 10 during fine-tuning. The model consists of two Transformer layers and is trained for 15 epochs in the pretraining stage and 10 epochs in the fine- tuning stage. Following (Luo al. 2023 Yao et al. 2025 Ma al. (0255), evaluate DAMR using Hits@1 and F1 score, assessing answer correctness and overall accuracy for questions with potentially multiple correct answers.
4.2 PERFORMANCE COMPARISON
We report the experimental results of DAMR in Table benchmarking its performance against state- of-the-art baselines across KGQA datasets. From the results, we find that: (1) Semantic parsing and retrieval-basel methods serve as early foundations for KGQA by extracting subgraphs and capturing structural semantics. However, embedding while retrieval- -ased methods rely on rigid pipelines that limit generalization. In contrast, LLM with KG approaches combine the language understanding of LLMs with structured reasoning over KGs, diverse, multi-hop queries. (2)
models struggle with complex relational patterns,
enabling more flexible path exploration and improved adaptability General-purpose LLMs, such as ChatGPT and Llama3-88 3-B, show basic reasoning ability but often perform worse than methods that combine L.MSs with KGs in KGQA tasks. This is mainly because

---

Published as a conference paper at ICLR 2026
WebQSP
CWQ
Type
Methods
Hits
Hits
F1
KV-Mem (Miller et al.
2016
46.7
34.5
18.4
15.7
EmbedKGQA [Saxeaa ct
2020
66.6
45.9
QGG (Lan & Jiang 2020
73.0
73.8
36,9
37.4
Semantic Parsing
NSM HH al. 2021
68.7
62.8
47.6
42.4
TransferNet (Shi
2021
71.4
48.6
KGT5 (Saxeña al.
2022)
56.1
36.5
GraftNet (Sun al. 2018)
66.4
60.4
36.8
32.7
PullNet (Sun et al.
2019)
45.9
Retrieval
SR+NSM (Zhang ct al.
2022
68.9
64.1
50.2
47.1
SR+NSM EZE (Zhngg et al.
2022
69.5
64.1
49.3
46.3
Alpaca-7B Taori et al. (2023)
51.8
27.4
Llama3-8P (Dubey
2024
30.3
25.7
30.5
27.8
Qwen2.5- 7B Team 2024
28.4
23.7
25.9
24.1
LLMs
ChatGPT (Schulman al.
2022
39.9
ChatGPT+Cor Wei et al.
2022
75.6
48.9
Nutrea (Choi 2023
2023
72.7
53.6
49.5
ToG (Sun et al.
81.9
76.0
68.5
60.2
RoG [Luo et al.
2023
80.8
70.8
57.8
56.2
KAPING BBck
2023
72.4
65.1
53.4
50.3
Reasoning (Jiane
2023
78.5
69.0
64.0
FiDeLis Sui et al. (2024]
84.3
78.3
71.5
64.3
LLMs+KGs
GNN-RAL (Mavromatis & Karypis 2024
82.8
73.5
62.8
60.4
DoG (Ma et al., 2((25a
65.4
55.6
41.0
46.4
DualR (Liu
20025
81.5
71.6
65.3
62.1
DP MM et al. (0025
87.5
75.8
69.4
RwT RwT(SShn el al. 2025
87.0
79.7
72.4
66.7
DAMR
94.0
81.7
78.0
75.1
Table Performance comparison (%) on WebQSP and CWQ datasets. Bold indicate the best results.
they are not grounded in domain-specific knowledge, making them more likely to produce incor- rect or made-up answers. (3) DAMR consistently outperforms baselines across both datasets, showcasing its strong reasoning capability. This superior performance is driven by its integration of an LL-M-based planner, which selectively retrieves relevant relations to reduce noise and guide the search toward high-quality reasoning paths, and path evaluation model that is dynamically fine-tuned during search to capture semantic differences among candidate paths and accurately rank those most likely yield correct answers.
4.3 EFFICIENCY ANALYSIS
As shown in Table DAMR achieves substantial improvements in computational efficiency, It duces the average number of LLM calls to 7.1 on WebQSP and 16.8 on CWQ, with corresponding token usage of 3,931 and 9,266. These correspond to reductions over 50% in LLM calls and 75% in token consumption relative to the strongest baseline. This efficiency is achieved by invoking the LLM only during the expansion phase of MCTS to select the top-k semantically relevant relations, which effectively narrows the search space and avoids redundant reasoning steps that lead to un- necessary computational overhead. During simulation, the context-aware path evaluator efficiently assesses candidate paths based on question-path alignment without requiring any further LLM in- teraction or model inference. These design choices reduce both the frequency and verbosity LLM usage while maintaining strong reasoning performance, making DAMR more efficient, scalable, and practically deployable than previous work.
4.4 ABLATION STUDY
the contributions of key components in DAMR: (1) DAMR w/o PE: removing the path evaluation module; (2) DAMR w/o FT: disabling fine-tuning of the evaluator; and (3) DAMR w/ 1PT-4.1: replacing the context-aware evaluator with general LLM.
We conduct ablation studies
8

---

Published as a conference paper at ICLR 2026
WcbQSP
CWQ
WebQSP
CWQ
Method
Method
#Tokens
#Calls
#Tokens
#Calls
Hits@1
F1
Hits
F1
DoG
22,538
30.9
37,741
58.1
DAMR w/o PE
91.2
78.2
74.3
72.1
ToG
16,372
23.2
26,183
41.9
DAMR w/o FT
91.9
80.1
75.1
73.0
RWT
10,680
15.1
17,885
28.6
DAMR w/ GPT 4,1
92.5
79.8
74.9
72.4
DAMR
3,931
7.1
9,266
16.8
DAMR
94.0
81.7
78.0
75.1
Table 2: Statisties of average number of LLM calls and token consumption per question on WebQSP and CWQ datasets.
Table 3: The results of ablation studies on the WebQSP and CWQ datasets. Bold results indi- cate the best performance.
Experimental results are summarized in Table From the results, we find that: (1) Removing the path evaluation module (DAMR w/o PH) causes noticeable performance drop on both datasets, un- derscoring critical role in guiding the search process. Without this component, the model cannot effectively assess rank candidate paths, leading to suboptimal reasoning and reduced accuracy. (2) Compared to DAMR w/o FT, the proposed DAMR consistently achieves superior results on both datasets, highlighting the importance of the finetuning mechanism in the path evaluation module. This mechanism enables the model to adapt to the evolving distribution of explored paths, improv- ing its ability to distinguish plausible from implausible reasoning trajectories. (3) Replacing the context-aware path evaluation module with general LLMs yields degraded performance, confirming the advantage of our fine-tuned path scorer. By capturing fine-grained semantic distinctions among candidate paths, it provides more accurate evaluation signals, enhancing overall search effectiveness.
4.5 SENSITIVITY ANALYSIS
We conduct a sensitivity analysis to assess the impact of two key hyper- parameters in DAMR: the number of selected relations & and the maximum reasoning path length L. The parame- ter k controls how many relations proposed by the LLM-based planner each step, while L determines the number of reasoning hops allowed during path construction.
Accuracy
0.8
0.7
0.7
(a) Number of selected relations kt (b) Reasoning path length L
Figure 2: Sensitivity analysis of hyperparameter on the We-
bQSP and CWQ datasets.
Figure 2 illustrates how h and L affect the performance of DAMR on the WebQSP and CWQ datasets. We vary and L within the range of {2, 3, 4, 5). From the results, we observe that: (1) As shown in Figure a), increasing l initially leads to performance gains, which then stabilize be- fore experiencing a slight decline. While larger & values encourage broader relational exploration, they may also introduce irrelevant candidates and increased computational cost. Conversely, smaller restrict the diversity of the search. To balance these trade-offs, we select a moderate k 3 as the default setting. (2) As shown in Figure 2),), on the WebQSP dataset, performance improves from = 2 to 3, then fluctuates between L and 5, suggesting limited gains beyond three hops. In contrast, performance the CWQ dataset steadily increases up L = 4 before slightly declining I. -= 5, reflecting its need for deeper reasoning due to more complex questions. Balancing effective- ness and efficiency across both datasets, we set L the default path length in all experiments.
More results are provided in Appendix E.4
4.6 IMPACT OF DIFFERENT LLMS
WebQSP
CWQ
Method
To evaluate the impact of dif- ferent LLMM-based planners within the DAMR framework, we com- pare several backbones including Llama2-13B (Roque) (025). Qwen3- 14B (Tam 2024), GPT 4.1 mini, and GPT 4.1, as shown in Table Across both datasets, stronger L.MMs consis-
Hits@1 1
F1
Hits 1
F1
DAMR (Llama2-13B)
91.0
76.7
73.9
69.5
DAMR (Qwen3-14B)
91.5
77.8
74.4
70.1
DAMR (GPT 4.1-mini)
93.1
80.6
76.1
72.7
DAMR (GPT 4.1)
94.0
81.7
78.0
75.1
Table 4: Performance of DAMR using different LLM--based planners backbones different datasets.

---

Published as a conference paper at ICLR 2026
Question
Where does greck language come fron?
Question
opened in 1922 Hollywood CA?
Answer
Atiie Gooup
Anewer
Cramman's Figyptian Theatm
langagg uniiusac frum the Prtt--lik-- Buspetan language family. which spread to around developed into Modern Creck.
Graumen's Cainese Theatre
moste poicce. Sul Graman Clarles Hollywoo.
opardd
Llmma2-138
lmngage, dialecs,
1.mma22133
become famous kadlark no! loufst straction
The TCL Chinele Theatre, ociiiaaly knowa the Chinese Ocand Thearre opezed in 1922 in Ltolywood, CA. It is livoric novis theser renowned its unque architccure edebidly handptans fooiptints
The Gaok langugg oiginates from the Picto Hallonis heanch the Indo tumopar langrage fammy. y. I! excined from the Myoenazan Creak socod millemiinn became foundation for Classicl Greek. spokic
Qwen-3-18h
Ownnd-144
The Hallywoed Bool, iconic amphiheater Hallyweed, Callfoma, opened 1922, Is renowred for disitactive hand shell and has hossed mimerous conserts and evems, be- coning a sgttificmn cahand landuck is Bee irca.
The Greek he onginates from the Indo inrpppn iin- guage family. developel in the waathen Bulkans smond the 3ed nillezalam BCE and is the oldes secooded living langrngs, with wiitice recoeds doting lock to the 15th con tuy BCE (Livcrr scrije).
GPT 4.1
amphrheater Hollywoed. Cáiifomia opeaed 1922 and has
Hollyyood
GPT 4.1/mini
for
and cultural
The Creek of the Indo Eusopeat language funily. It develaped in the reglon of Greece and the Aegren aroud the 3rd milken niun BCE, crdlvng through antieni malional, and mocken sages.
orginates from the Helleric hranch
Path 1: Ensty Ed:
KM06) +
lock-
son evcaconeeeelss tavel mrvdd dostiaationnommmii sitrationss + Gnuman's Egyptian
time event locacous
GPT miai
DAMR
830/8)
Entry
120026)
desiinatioon.ssiii atbractions
Grummnn's
DAMR
Thearr.
(a) One example from the WebQSP dataset.
(b) One example from the CWQ dataset.
Figure 3: Case studies of DAMR on the WebQSP and CWQ datasets. We highlight the correct answers in Red and the wrong answers in Blue.
tently yield higher FI and Hits scores, with GPT 4.1 achieving the best performance across all metries. These results highlight the pivotal role of advanced LLMs in guiding relation selection and reasoning path expansion, where improved fluency, contextual awareness, and semantic precision translate into more accurate and faithful reasoning trajectories. Notably, the consistent performance gap between smaller and larger backbones illustrates the sensitivity of KGQA systems to the plan- ner's reasoning capability, reinforcing the necessity of leveraging high-capacity models when avail- able. Overall, these findings emphasize the importance of backbone selection and further validate the design of DAMR, which capitalizes on powerful LLMs achieve robust, generalizable, and effective multi-hop reasoning.
4.7
CASE STUDY
Figure 3 presents detailed case studies on the WebQSP and CWQ datasets comparing the reasoning process of DAMR with four representative LLMs: Llama-2-13B, Qwen-3-14B, GPT 4.1-mini, and GPT 4.1. In Figure 3a| the baseline LLMs generate fluent and seemingly plausible answers such or "Proto-Hellenic" when asked about the origin of the Greek language, yet fail to identify the correct answer Attic Group. In contrast, DAMR accurately predicts the correct entity by explicitly traversing the base.rosetta.luu htw.:ttaa.anngui..ppaa.... edge graph. In Figure 3b) none of the baseline models are able to identify the structure that opened in Hollywood in 1922, while the proposed DAMR successfully locates Grauman's s Egypti an Theat re by explicitly following relevant relation paths in the knowledge graph and integrating complementary reasoning trajectories. These examples collectively highlight the strength of DAMR in grounding its reasoning in the knowledge graph and explicitly modeling multi-step reasoning paths, enabling it to provide accurate and faithful answers to complex, antology-speciffe questions that general- LLMs often struggle to resolve.
as Erroto-Indo-uurope
relation within the knowl-
5 CONCLUSION
In this work, we presented DAMR, a dynamically adaptive MCTS-based framework for knowledge graph question answering that integrates an LLMM-gidded planner, a context-aware path evaluator, and dynamic pseudo-path refinmment mechanism. By narrowing the search space, reducing redun- dant LLM calls, and continually adapting path evaluation, DAMR achieves efficient and accurate multi-hop reasoning. Extensive experiments on WebQSP and CWQ demonstrate that DAMR con- sistently surpasses satte-oftth--ee art baselines in both performance and efficiency, while ablation and case studies highlight its interpretability and robustness. These results establish DAMR as scalable solution for real-worlh KGQA and open avenues for extending adaptive symbolic-neure reasoning to broader domains such as scientific discovery and recommendation.
10

---

Published as a conference paper at ICLR 2026
ETHICS STATEMENT
This work complies with the ICLR Code of Ethics. Our study on KGQA relies solely on publicly available datasets, which contain no personal or sensitive information. The proposed DAMR frame- work is developed enhance the efficiency and reliability of multi-hop reasoning while avoiding harm or discrimination. All experimental settings are transparently reported, with fair comparisons to prior methods, and proper credit is given to related work. The contributions are intended exclu- sively for scientific and educational purposes, supporting the advancement of Al research.
ACKNOWLEDGMENT
This research was supported in part by Hong Kong Research Grants Council (Grant 1 11217925) and National Science Foundation of China (Grant 72371214).
REFERENCES
Jinheon Back, Alham Fikri Aji, and Amir Saffari. Knowledge-augment language model prompt- ing for zero-shot knowledge graph question answering. arXiv preprint vrXiv:2306.04136 2023.
Jonathan D Chang, Kiante Brantley, Rajkumar Ramamurthy, Dipendra Misra, and Wen Sun. Learn- ing to generate better than your Ilm. arXiv preprint arXiv:2306. 1816, 2023.
Yupeng Chang, Xu Wang, Jindong Wang, Yuan Wu, Linyi Yang. Kaijie Zhu, Hao Chen, Xiaoyuan Yi, Cunxiang Wang, Yidong Wang, et al. A survey on evaluation of large language models. ACM transactions on intelligent systems and technology, 15(3):1-455 2024.
Hycong Kyu Choi, Seunghun Lee, Jaewon Chu, and Hyunwoo Kim. Nutrea: Neural tree search for context-guided multi-hop kgqa. Proceedings the Conference on Neural Information Processing Systems, 36:35954-35966 2023.
Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang. Mostafa Dehghani, Siddhartha Brahma, al. Scaling Instruction-inntuue finetuned lan- guage models. Journal of Machine Learning Research, 25(70):1 2024.
Preetam Prabhu Srikar Dammu, Himanshu Naidu, and Chirag Shah. Dynamic-kgqa: A scalable framework for generating adaptive question answering datasets. In Proceedings of the 48th In- ternational ACM SIGIR Conference on Research and Development Information Retrieval, pp- 1498-3508, 2025.
Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishna- murthy, Alex Smola, and Andrew McCallum. Go for walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. In Proceedings of the International Conference on Learning Representations, 2018
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The Ilama 3 herd of models. arXiv e-prints, pp. arXiv-2407, 2024.
Siyuan Fang, Kaijing Ma, Tianyu Zheng, Xinrun Du, Ningxuan Lu, Ge Zhang, and Qingkun Tang- Karpa: A training-free method of adapting knowledge graph as references for large language model's reasoning path aggregation. arXiv preprint arXiv:24/2.20990 2024.
Gaole He, Yunshi Lan, Jing Jiang, Wayne Xin Zhao, and Ji-Rong Wen. Improving multi-hop knowl- edge base question answering by learning intermediate supervision signals. In Proceedings of the International ACM Conference on Web Search Data Mining, pp. 553-561, 2021.
Jiaxin Huang, Runnan Chen, Ziwen Li. Zhengqing Gao, Xiao He, Yandong Guo, Mingming Gong, and Tongliang Liu. Mllm-for3d: Adapting multimodal large language model for 3d reasoning segmentation. arXiv preprint arXiv:2503.1811 2025.

---

Published as a conference paper at ICLR 2026
Jinhao Jiang, Kun Zhou, Wayne Xin Zhao, and Ji-Rong Wen. Unikgqa: Unified retrieval and reasoning for solving multi-hop question answering over knowledge graph. arXiv preprint arXiv:2212.00955, 2022.
Jinhao Jiang, Kun Zhou, Wayne Xin Zhao, Yaliang Li, and Ji-Rong Wen. Reasoninglm: Enabling structural subgraph reasoning pre-trained language models for question answering over knowl- edge graph. arXiv preprint 1xXiv2240.000555 2023.
Diederik Kingma. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6988) 2014.
Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning, In European conference on machine learning. pp. 282-293. Springer, 2006.
Yunshi Lan and Jing Jiang. Query graph generation for answering multi-hop complex questions from knowledge bases. Proceedings of the Annual Meeting of the Association for Computational Linguistics, 2020.
Dong-Hyun Lee et al. Pseudo-label: The simple and efficient suni-supervised learning method for deep neural networks. In Workshop on challenges in represenlation learning, ICML, number 2, pp. 896. Atlanta, 2013.
Seongmin Lee, Jaewook Shin, Youngjin Ahn, Seokin Seo, Ohjoon Kwon, and Kee-Eung Kim. Zero- shot multi-hop question answering via monte-carlo tree search with large language models. arXiv preprint arXiv:2409. 19382, 2024.
Mufei Li, Siqi Miao, and Pan Li. Simple is effective: The roles of graphs and large language mod- els in 2024a.
retrieval-augmentte generation. arXiv preprint arX1v:2410.20724,
Yading Li, Dandan Song. Changzhi Zhou, Yuhang Tian, Hao Wang, Ziyi Yang, and Shuhao Zhang. A framework of knowledge graph-enhanced large language model based on question decompo- sition and atomic retrieval. In Proceedings of the Conference Empirical Methods in Natural Language Processing, pp. 14422-14485, 2024b.
Guangyi Liu, Yongqi Zhang, Yong Li, and Quanming Yao. Dual reasoning: A gnn-llm collaborative framework for knowledge graph question answering. In The Second Conference on Parsimony and Learning (Proceedings Track), 2025.
Hanmeng Liu, Ruoxi Ning, Zhiyang Teng, Jian Liu, Qiji Zhou, and Yue Zhang. Evaluating the logical reasoning ability of chatgpt and gpt-4. arXiv preprint arXiv:2304 03439, 2023.
Xiao Long, Liansheng Zhuang, Aodi Li, Minghong Yao, and Shafei Wang. Eperm: An evidence path enhanced reasoning model for knowledge graph question and answering. In Proceedings of the AAAI Conference Artificial Intelligence, volume 39, pp. 12282-12290 2025a
Xiao Long, Liansheng Zhuang, Chen Shen, Shaotian Yan, Yifei Li, and Shafei Wang. Enhancing large language models with reward-guided tree search for knowledge graph question and answer- ing. arXiv preprint arXiv:2505./244 2025b.
Haoran Luo, Yikai Guo, Qika Lin, Xiaobao WU, Xinyu Mu, Wenhao Liu, Meina Song, Yifan Zhu, Luu Anh Tuan, et al. Kbqa-ol: Agentic knowledge base question answering with monte carlo tree search. arXiv preprint arXiv:2501.18922 2025.
Linhao Luo, Yuan-Fant Fang Li, Gholamreza Haffari, and Shirui Pan. Reasoning on graphs: Faithful and interpretable large language model reasoning, arXiv preprint arXiv:2310.01061, 2023.
Hao Ma, Tianyi Hu, Zhiqiang Pu, Liu Boyin, Xiaolin Ai, Yanyan Liang, and Min Chen. Coevolving with the other you: Fine-tuning Ilm with sequential cooperative multi-agent reinforcement leamn ing. Proceedings of the Conference on Neural Information Processing Systems, pp. 15497-15525, 2024a.
12

---

Published as a conference paper at ICLR 2026
Jie Ma, Zhitao Gao, Qi Chai, Wangehun Sun, Pinghui Wang, Hongbin Pei, Jing Tao, Lingyun Song, Jun Liu, Chen Zhang, et al. Debate on graph: a flexible and reliable reasoning framework for large language models. In Proceedings of the AAAI Conference Artificial Intelligence, number 23, pp. 24766, 2025a.
Jie Ma, Ning Qu, Zhitao Gao, Rui Xing, Jun Liu, Hongbin Pei, Jiang Xie, Linyun Song, Pinghui Wang, Jing Tao, et al. Deliberation on priors: Trustworthy reasoning of large language models on knowledge graphs. arXiv preprint arXiv:2505.
2025b.
Shengjie Ma, Chengjin Xu, Xuhui Jiang, Muzhi Li, Huaren Qu, Cehao Yang, Jiaxin Mao, and Jian Guo. Think-on-graph 2.0: Deep and faithful large language model reasoning with knowledge- guided retrieval augmented generation. arXiv preprint arXiv:2407. 10805, 2024b.
Costas Mavromatis and George Karypis. Gnn-rag: Graph neural retrieval for large language model reasoning. arXiv preprint arXiv:2405.20133 2024.
Alexander Miller, Adam Fisch, Jesse Dodge, Amir-Hossein Karimi, Antoine Bordes, and Ja- son Weston. Key-value memory networks for directly reading documents. arXiv preprint arXiv:1606.03126, 2016.
Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieee Bpr: Bayesian personalized ranking from implicit feedback. arXiv preprint arXiv: 2012.
Luís Roque The evolution of llaaa: From Ilama to llama 3.1, 2025.
Apoorv Saxena, Aditay Tripathi, and Partha Talukdar. Improving multi-hop question answering over knowledge graphs using knowledge base embeddings. In Proceedings of the 58th annual meeting of the association for computational linguistics, pp. 4498-4507, 2020.
Apoorv Saxena, Adrian Kochsiek, and Rainer Gemulla. Sequence-to-sequence knowledge graph completion and question answering. arXiv preprint arXiv:2203.1032), 2022.
John Schulman, Barret Zoph, Christina Kim, Jacob Hilton, Jacob Menick, Jiayi Weng, Juan Fe- lipe Ceron Uribe, Liam Fedus, Luke Metz, Michael Pokorny, et al. Chatgpt: Optimizing language models for dialogue. OpenAl blog, 2(4), 2022.
Tiesunlong Shen, Jin Wang, Xuejie Zhang, and Erik Cambria. Reasoning with trees: Faithful ques- tion answering over knowledge graph. In Proceedings of the Annual Meeting of the Association for Computational Linguistics, pp. 3138-3157, 2025.
Jiaxin Shi, Shulin Cao, Lei Hou, Juanzi Li, and Hanwang Zhang. Transfernet: An effective and transparent framework for multi-hop question answering over relation graph. arXiv preprint arXiv:2104.07302 2021.
Yuan Sui. Yufei He, Nian Liu, Xiaoxin He, Kun Wang, and Bryan Hooi. Fidelis: Faithful reasoning in large language model for knowledge graph question answering. arXiv preprint arXiv:2405. 13873, 2024.
Haitian Sun, Bhuwan Dhingra, Manzil Zaheer, Kathryn Mazaitis, Ruslan Salakhutdinov, and William W Cohen. Open domain question answering using early fusion of knowledge bases and text. arXiv preprint
2018
Haitian Sun, Tania with iterative retrieval on knowledge bases and text. arXiv preprint
and William W Cohen. Pullnet: Open domain question answering
09537, 2019.
Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang, Chen Lin, Yeyun Gong, Lionel M Ni, Heung- Yeung Shum, and Jian Guo. Think-on on-grrph: Deep and responsible reasoning of large language model on knowledge graph. arXiv preprint 2.0.::2207.07677, 2023.
Alon Talmor and Jonathan Berant. The web as knowledge-base for answering complex questions. arXiv preprint 1803. 06643,664332 2018.
Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B Hashimoto. Stanford alpaca: An instruction-following llama model, 2023.
13

---

Published as a conference paper at ICLR 2026
Qwen Team. Qwen2 technical report. arXiv preprint arXiv:2407.10671 2024.
Keheng Wang, Feiyu Duan, Sirui Wang, Peiguang Li, Yunsen Xian, Chuantao Yin, Wenge Rong, and Zhang Xiong, Knowledge-driven cot: Exploring faithful reasoning in Ilms for knowledge- intensive question answering. arXiv preprint arXiv:2308. 13259, 2023.
Yuchao Wang, Haochen Wang, Yujun Shen, Jingjing Fei, Wei Li, Guoqiang Jin, Liwei Wu, Rui Zhao, and Xinyi Le. Semi-supervised semantic segmentation using unreliable pseudo-labels. In The IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 4248 4257, 2022.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thouggh prompting elicits reasoning in large language models. Proceedings of the Conference on Neural Information Processing Systems, 35:24824 24837, 2022.
Qizhe Xie, Minh-Thang Thang Luong, Eduard Hovy, and Quoc V Le. Self-training with noisy student improves imagenet classification. In The IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10687-10698, 2020.
Wenhan Xiong, Thien Hoang, and William Yang Wang. Deeppath: A reinforcement learning method for knowledge graph reasoning. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pp. 564-573, 2017.
Mufan Xu, Kehai Chen, Xuefeng Bai, Muyun Yang, Tiejun Zhao, and Min Zhang. Llm-based dis- criminative reasoning for knowledge graph question answering. arXiv preprint 2r211:24 2024.
Mufan Xu, Gewen Liang Kehai Chen, Wei Wang. Xun Zhou, Muyun Yang, Tiejun Zhao, and Min Zhang. Memory-augmented query reconstruction for Ilm iim-baed knowledge graph reason- ing. arXiv preprint arXiv:2503.05. 00.5000..59..3 193, 2025.
An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, et al. Qwen3 technical report. arXiv preprint arXiv:2505.09388, 2025.
Tianjun Yao, Haoxuan Li, Zhiqiang Shen, Pan Li, Tongliang Liu, and Kun Zhang. Learning effi- cient and generalizable graph retriever for Knowledge-grapp question answering. arXiv preprint 2rXiv:2506.09645, 2025.
Wen-tau Yih, Matthew Richardson, Christopher Meek, Ming- Wei Chang, and Jina Suh. The value of semantic parse labeling for knowledge base question answering. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Pupers), pp. 201-206, 2016.
Donghan Yu, Sheng Zhang, Patrick Ng. Henghui Zhu, Alexander Hanbo Li, Jun Wang, Yiqun Hu, William Wang, Zhiguo Wang, and Bing Xiang. Decaf: Joint decoding of answers and logical forms for question answering over knowledge bases. arXiv preprint urXiv:2210.000 10,0003,, 2022.
Simon Zhai, Hao Bai, Zipeng Lin, Jiayi Pan, Peter Tong, Yifei Zhou, Alane Suhr, Saining Xie, Yann LeCun, Yi Ma, et Fine-tuning large vision-language models as decision-making agents via reinforcement learning. Advances in neural information processing systems, 37:1 10935-110971, 2024.
Jing Zhang, Xiaokang Zhang, Jifan Yu, Jian Tang, Jie Tang, Cuiping Li, and Hong Chen. Sub- graph retrieval enhanced model for multi-hop knowledge base question answering. arXiv preprint arXiv:2202.1332 13296, 2022.
Wenting Zhao, Ye Liu, Tong Niu, Yao Wan, Philip S Yu, Shafiq Joty, Yingbo Zhou, and Semih Yavuz. Divknowqa: assessing the reasoning ability of 1lms via open-domain question answering over knowledge base and text. arXiv preprint 2311222310 2023.
14

---

Published as a conference paper at ICLR 2026
A ALGORITHM
Algorithm Dynamic MCTSS-base KGQA with Path Model Pretraining and Online Refinement
Input: Question knowledge graph G (E, R, T), number of selected relations k, MCTS itera- tions N, length of reasoning path L
Output: Answer set A
1: / Stage 1: Path Evaluation Model Pre-training
2: Construct reasoning path pairs (q.p*,p" from
3: Initialize path evaluation model -;
4: for each batch in pretraining data do
5: Update S(g, ②) by minimizing the Pair-wise Ranking loss in Eq.(4)
6: end for
/ Stage 2: Dynamic MCTS Reasoning
8: for i = 1 tooNN N do
9: Selection: Traverse the tree from root a leaf node by selecting child nodes according to
UCT criterion in (q.
10:
Expansion:
11:
i. At the selected node, enumerate all candidate relations from current entities and use the
LLM-based planner to select the top-k most relevant relations
12:
ii Expand new child node for each selected relation
13:
Simulation: For each expanded node, perform rollout by sequentially selecting relations (guided by the path evaluation model) up to L hops until a correct answer is reached
14:
Backpropagation: Update the value (w;) and visit (n;) statistics along the traversed path from the leaf node back to the root using the score from the simulation, as per Eq.(6)
15: Path Evaluation Model Fine-tuning: Generate the explored pseudo-pant pairs (p )-) via (5,(5) and fine-tune the path evaluation model S(g, -; O) based on Pair-wise Ranking loss in Eq.(4)
16: end for
17: / Stage 3: Answer Extraction
18: Collect entities reached by high-scoring reasoning paths as A
19: return A
B DATASETS
B. DATASET DESCRIPTION
Datasets
#Train
#Valid
#Test
WebQSP
2,848
250
1,639
CWQ
27,639
3,519
3,531
Table Statistics of KGQA datasets.
We conduct extensive experiments on two widely used multi-hop Knowledge Graph Question An- swering (KGQA) benchmarks: WebQSP Talmor & Berant (2018) and CWQ Yih et al. (2016). The statistics of these two benchmarks can be found in Table and their details are shown follows:
The WebQuestionsSP (WebQSP) dataset is widely adopted benchmark for evaluating single-hop and simple multi-hop KGQA Yih et al. (2016). It consists of 4,837 natural lan- guage questions annotated with corresponding SPAROL queries over the Freebase knowl- edge graph. The dataset is partitioned into 2,848 training, 250 validation, and 1,639 test instances.
The Complex WebQuestions (CWQ) dataset is challenging benchmark designed for multi- hop KGQA Talmor Berant (0118. comprises 34,689 questions derived from We- bQuestionsSP, reformulated to include more complex and compositional queries. Each
15

---

Published as a conference paper at ICLR 2026
question typically requires multi-step reasoning the Freebase knowledge graph, often involving conjunctions, comparatives, or nested logical structures. The dataset is divided into 27,639 training, 3,519 validation, and 3,531 test examples.
B.2 DATA PROCESSING
Following prior work Shen et al. (022)) Long et al. (2025b); Ma et al. (2025b), we preprocess the datasets by constructing localized subgraphs centered around each question entity reduce the size of the search space. Specifically, for each question in WebQSP Yih et al. (2016) and CWQ Talmor & Berant (2018), we extract a subgraph from the Freebase knowledge graph by including all triples within predefined number of hops from the topic entity. This approach preserves the essential context required for multi-hop reasoning while significantly improving computational efficiency.
C BASELINES
In this part, we introduce the details of the compared baselines as follows:
Semantic Parsing Methods. We compare our DAMR with six semantic parsing methods:
KV-Mem: KV-Mem Miller et al. (2016) introduce neural architecture that stores facts as key-value pairs and enables question answering by attending over memory slots, directly retrieving relevant information to infer answers.
EmbedKGQA: EmbedKGQA Saxena al. (2020) enhances multi-hop question an- swering over knowledge graphs by leveraging pretrained knowledge base embeddings, enabling the model reason over entity and relation representations without explicit path enumeration during answer prediction.
QGG: QGG Lan & Jiang (2020) generates query graphs to answer multi-hop complex questions over knowledge bases, formulating question answering as query graph pre- diction and enabling structured reasoning through graph matching and path ranking mechanisms.
NSM: NSM He al. (2021) enhances multi-hop KBQA by leveraging intermediate supervision signals, decomposing questions into reasoning steps, and training a neural state machine to sequentially predict relations and entities for accurate path-based reasoning.
TransferNet: TransferNet Shi et al. (2021) proposes transparent framework for multi-hop QA over relational graphs by transferring question semantics to relation paths through interpretable path ranking and structured reasoning, enabling effective and explainable answer prediction.
KGT5; KGT5 Saxena et al. (2022) formulates knowledge graph completion and ques- tion answering as unified models to jointly encode input queries and generate answer entities or triples in a flex- ible and end-to-end manner.
tasks, leveraging pre-trained language
Retrieval- Based Methods. We compare our DAMR with four retrieval- methods:
Sun et al. (2018) proposes an early fusion framework that jointly encodes knowledge base facts and supporting text by constructing a heterogeneous graph, enabling effective reasoning through graph convolutional networks for open- domain question answering.
GraftNet: GraftNet
PullNet: PSl et al. (2019) introduces an iterative retrieval mechanism that ex- pands query- query-specific subgraph by pulling relevant facts from both knowledge bases and text, enabling joint reasoning over heterogeneous evidence for open-domain ques- tion answering.
-R+NNMM SR+NSM Zhang et al. (022)) enhances multi-hop KBQA by first retriev- ing a cuuestiionrelevane subgraph and then performing symbolic reasoning over it using Neural Symbolic Machines, improving efficiency and accuracy through constrained
and focused logical inference.
16

---

Published as a conference paper at ICLR 2026
SR+NSM+EZE: SR+NSM+E2E Zhang al. (2022 extends SR+NSM by enabling end-to-end training that jointly optimizes subgraph retrieval and reasoning. This in- tegration enhances model coherence and allows better alignment between retrieved subgraphs and final answer prediction.
General Large Language Models (LLMss), We compare our DAMR with six general LLMs:
Flan-T5-xl: Flan-T5-xl Chung al. 2024) is instruction-finetune variant of the T5 model, trained on a diverse collection of tasks with natural language instructions. By leveraging large-scale instruction tuning, it improves zero-shot and few-shot per- formance across diverse NLP benchmarks.
Alpaca-7B: Alpaca-7B Taori et al. (2023) is an cestructioo-followiing language model fine-tuned from LLaMA-7B using self-instruct techniques. demonstrates strong zero-shot and few-shot performance by aligning with human instructions across vari- ous NL.P tasks.
Llama3-8B: Llama3-8B Dubey et al. (2024) part of the LLaMA 3 family mod- els, designed for improved instruction following, reasoning. and code generation. Pre- trained on a high-quality corpus and fine-tuned with supervised signals, achieves strong performance across diverse benchmarks.
Qwen2.5-7B. Qwen2.5-7BB Team (222) is 7B-parameter instruction-tune tunde language model developed by Alibaba, optimized for tasks such as reasoning, code generation, and dialogue. It supports multi-turn conversation and demonstrates competitive per- formance on standard benchmarks.
ChatGPT: CharGPT Schulman et al. (2022) is conversational AI developed by Ope- nAI, based on the GPT architecture. It is designed to understand natural language, engage in dialogue, answer questions, and assist with wide range of tasks across domains.
ChatGPT+CoT: ChatGPT with -fhough (CoT) Wei et al. (2022) prompting enhances the model's 's reasoning capabilities by encouraging it to generate intermediate reasoning steps before arriving at a final answer, improving performance on complex, multi-step problems.
LLMs with KG. We compare our DAMR with fourteen LLMs with KG methods:
UniKGQA: UniKGQA Jiang al. 2022) is unified framework that integrates trieval and reasoning for multi-hop question answering over knowledge graphs, com- bining subgraph retrieval, query decomposition, and neural reasoning in an end-to-end manner.
DECAF: DECAF Yu et al. (2022) is joint framework for question answering over knowledge bases that simultancously decodes logical forms and answers. By leverag- ing dual supervision, it enhances both symbolic reasoning accuracy and direct answer prediction unified architecture.
KD-CoT: KD-CoT Wang al. (2023) is framework that enhances the faithfulness of large language models by guiding Chain-of-Thouue reasoning with external knowl- edge, improving accuracy in knowledge-intene inneeddge-nneniveeeeeee question answering tasks.
Nutrea: Nutrea et al. (2023) proposes a neural tree search framework for context- guided multi-hop KGQA. incrementally constructs reasoning trees by integrating question semantics and graph context, enabling efficient exploration of multi-hop paths for accurate answer prediction.
ToG: ToG Sun al. (2023) is a framework that enables large language models to perform deep and responsible reasoning over knowledge graphs by combining struc- tured graph information with iterative thinking and verification mechanisms for reli- able multi-hop QA.
RoG: RoG [Luo et al. (0023) is framework that enhances the faithfulness and inter- pretability of large language model reasoning by grounding multi-hop question an- swering knowledge graphs, integrating symbolic path tracking with natural lan- guage generation.
KAPING: KAPING Back et al. (2023) introduces knowledge-augmentt prompting by integrating structured triples into Chain-of-Though) (Co'T) reasoning. It guides
17

---

Published as a conference paper at ICLR 2026
Methods
WehQSP-wiki
MetaQA
BioGraphletQA
Hits@
F1
Hits@
F1
Hits@ 1
F1
ChatGPT
60.1
47.8
59.5
47.6
39.7
27.8
FiDeLiS
81.7
67.3
98.7
91.2
70.0
52.3
DoG
62.6
53.1
90.1
93.1
73.3
56.4
DAMR
88.2
72.5
99.2
87.9
80.9
60.7
Table 6: Performance comparison on WebQSP-wiki, MetaQA, and BioGraphlerQA datasets.
WebQSP
CWQ
Methods
Hits@1
F1
Hits@ 1
F1
DAMR w/ history
94.5
81.7
79.8
76.3
DAMR
94.0
81.7
78.0
75.1
Table Performance of DAMR with and without historical reasoning traces on WebQSP and CWQ.
large language models generate intermediate reasoning steps, enabling zero-shot multi-hop KGQA without task-specific tin-ttunigg
LMM MeasoningL.Mjiang et al. (2023) enhances pre- pre-trained language mod- els for KGQA by injecting subgraph structures into the input representation. It enables structural reasoning over retrieved subgraphs through reasoning aware encoder, im- proving performance on complex multi-hop queries.
FiDeLis: FiDeLis Sui et al. 2024) proposes a faithfulness-wwae KGQA framework that enhances reasoning consistency in LLMs by aligning generated logical forms with answer predictions. It introduces fidelity constraints reduce hallucinations and improve answer correctness.
GNN-RAG: GNN-RAG Mavromatis & Karypis (2024) integrates graph neural net- works with retrieval-augmennte generation by encoding knowledge subgraphs into LLMs' context. It enables structural reasoning over retrieved subgraphs, improving answer accuracy in KGQA through explicit graph-aware representations.
DoG Ma al. (2025a) flexible and reliable reasoning framework that en- ables large language models to generate and evaluate multiple reasoning paths over knowledge graphs through a debate-style process, enhancing robustness and answer faithfulness.
DoG:
DuarL: DuarL [iu et 2025 is a collaborative framework that integrates GNNs and LLMs for KGQA, where GNNs capture structural semantics and LLMs perform adaptive reasoning, enabling accurate and interpretable multi-hop QA.
DP: DP Ma et al.] (2025b) is trustworthy reasoning framework that guides large language models using prior knowledge from knowledge graphs. It iteratively verifies and refines reasoning paths to enhance faithfulness, robustness, and answer accuracy in KGQA.
RwT: RwT [Shen et al. (025 faithful KGQA framework that models multi-hop reasoning as tree-structured exploration over knowledge graphs, enabling large lan- guage models to generate interpretable reasoning paths and improve answer consis- tency and accuracy.
D MORE IMPLEMENTATION DETAILS.
In DAMR, the LLM-based planner operates entirely through external API calls without fine-tuning. It follows fixed prompt template containing the input question and local outgoing relations, with a k- k-per-hop value of and decoding temperature 0.3. When no valid relation is produced, the planner outputs empty list terminate expansion. Owen3-Embeddingg-e frozen embeddings for questions and relations. The path evaluation model is pre-trained on path pairs with batch size of 8, learning rate of 1e-5, and 1:1 negative sampling ratio, then dynamically
is used to generate
18

---

Published as a conference paper at ICLR 2026
Method
WebQSP
CWQ
Hits@
F1
p-valuc
Hits@1 1
F1
p-value
FiDeLiS
83.8 + 0.3
77.9 1 0.2
<0.01
71.3 + 0.3
64.1 1: 0.2
<0.01
DoG
64.8 - 0.5
54.7
0.3
<0.01
40.8 0.3
46.3 = 0.3
<0.01
DAMR
93.9 - 0.2
81.5 0.3
77.8 - 0.2
74.9 0.3
Table 8:
Performance (%) of DAMR and baselines on the WebQSP and CWQ datasets. Mean + standard deviation and paired t-test p-values are reported.
WebQSP
CWQ
Methods
#Reasoning time
#GPU
#Reasoning time
#GPU
FiDeLis
5.4
0
10.1
DoG
9.8
0
19.3
0
DAMR
4.3
0.6
7.6
0.8
Table 9: Average reasoning time (seconds) and GPU consumption on WebQSP and CWQ datasets.
fine-tuned during search using rollout-based pseudo-labels with smaller learning rate of 5e-6 and batch size of 4. The hop limits are set to 3 for WebQSP and 4 for CWQ, and all experiments use fixed random seeds for reproducibility.
E
MORE EXPERIMENTAL RESULTS
E. MORE PERFORMANCE COMPARISON
To further evaluate the generality of DAMR beyond Freebase-based datasets, we conducted exper- iments on three additional KGQA benchmarks that differ in schema complexity and domain char- acteristics: MetaQA Ma et al. 2225a b), BioGraphlertAAT] and WebQSP-Win (Sun et al. (2023). MetaQA contains balanced subsets 1-hop. 2-hop, and 3-hop questions, enabling controlled analysis of multi-hop reasoning scalability. BioGraphlerQA is biomedical-domain benchmark de- signed to assess generalization to dense, domain-specific knowledge graphs. WebQSP- Wiki Wikidata-based reconstruction of WebQSP in which missing Freebase relations explicitly la- beled as PAD RELATION, introducing realistic incompleteness and alias noise. As shown Ta- ble 6 DAMR achieves -fthe-of- performance across all three datasets when compared with ChatGPT, FiDel Suu et (2024), and DoG Ma et (2025a), demonstrating strong generalization across diverse schemas, reasoning depths, and noise conditions.
To better understand how the planner benefits from feedback, we analyze its behavior from three per- spectives. First, the LLM planner remains static ensure stability and efficiency, since fine-tuning externally hosted APIs is impractical. Instead, DAMR decouples symbolic exploration (MCTS) from neural adaptation (path evaluation). Second, the planner implicitly benefits from the MCTS process, where plausible relations are reinforced through UCT updates and less effective ones are pruned over time. Third, to incorporate non- paramereetriic feedback, we augment the planner's prompt with historical reasoning traces from previous rollouts. As shown in Table 7 this in-context adapta- tion consistently improves performance, indicating that accumulated reasoning experience helps the planner make more stable and informed decisions.
To verify the reliability our findings, we performed additional statistical analyses by rerunning all experiments with five independent random seeds and conducting paired t-tests between DAMR and each baseline. This evaluation measures performance consistency across runs. The low vari- ance and p- pavuuu below 0.01, reported in Table g confirm that DAMR's 's performance gains
Fi (Sui et al.] (2044) and DoG Ma et al. 2025a) are statistically significant and not caused by random variation.
httpss//zendd..nggrrood/////
19

---

Published as a conference paper at ICLR 2026
WebQSP
CWQ
Method
#Tokens
#Calls
#Tokens
#Calls
DAMR w/o PE
5,037
8.9
13,870
22.9
DAMR w/o FT
4,929
8.3
12,432
21.5
DAMR w/ GPT-4.1
7,742
13.8
23,773
42.3
DAMR
3,931
7.1
9,266
16.8
Table 10: Statistics of average number of LLM calls and token consumption per question We- bQSP and CWQ datasets.
Method
WebQSP
CWQ
Hits@1
Hits@1
DAMR w/o CT
93.4
81.0
77.4
74.3
DAMR w/o
93.6
81.2
77.6
74.6
DAMR w/o PR
92.7
80.3
76.5
73.2
DAMR
94.0
81.7
78.0
75.1
Table 11: The results of ablation studies on the WebQSP and CWQ datasets. Bold results indicate the best performance.
E.2 INFERENCE TIME AND MEMORY COMPARISON
To evaluate the practical runtime efficiency of DAMR, we compared its end-to-end reasoning latency and GPU usage with two representative baselines, FiDeLis Sui et al. (2024) and DoG Ma et al. (225a),, both of which also rely asynchronous API calls to external LLMs. As shown in Table DAMR achieves the lowest latency on both WebQSP and CWQ, demonstrating superior efficiency in API-dependent reasoning workflows. This improvement primarily results from restricting LLM invocations to the expansion phase and employing a lightweight Transformer-base for local reasoning. During training and inference, DAMR requires only 0.6 GB and 0.8 GB of GPU memory on WebQSP and CWQ. respectively, while the baselines do not use GPU resources. CPU utilization for all models mainly comes from data preprocessing and handling asynchronous LLM calls.
path evaluator
E.3 MORE ABLATION STUDY
To further assess the contribution of each module to computational efficiency, we measured the av- erage number of tokens and API calls during reasoning, shown in Table 10 The results indicate that both the path evaluator and the fine-tuning mechanism are critical for reducing LLM depen- dency and improving efficiency. Compared with directly evaluating reasoning paths using LLM,, DAMR significantly reduces token usage and API calls while maintaining high reasoning accuracy, demonstrating that its modular design effectively balances performance and computational cost.
To evaluate the sensitivity of DAMR to the design of its path scorer, we conducted ablation stud- ies three variants: DAMR w/o CT, which replaces the cross-attention mechanism with simple concatenation; DAMR w/o PE, which removes positional encodings; and DAMR w/o PR, which replaces the pairwise ranking loss with binary cross-entropy loss. As shown in Table IT] DAMR achieves the best performance across both WebQSP and CWQ, demonstrating that each component contributes to effectiveness. The removal cross-attention or positional encodings causes mod- erate degradation, confirming their importance for modeling compositional semantics in multi-hop reasoning, while substituting the ranking loss leads to larger drop, indicating that pairwise ranking better captures relative path plausibility.
E.4 MORE SENSITIVITY ANALYSIS
To more thoroughly illustrate the impact of hyperparameter variations on model performance, we re- port detailed numerical results showing how performance fluctuates under different hyperparameter
20

---

Published as a conference paper at ICLR 2026
WchQSP
CWQ
Method
Hits@1
F1
@its@1
F1
k 93.0
80.9
76.6
73.8
k
94.0
81.7
78.0
75.1
k 94.0
81.8
77.8
75.0
h 93.9
81.7
78.0
75.2
Table Hyperparameter sensitivity analysis the number of selected relations on the WehQSP and CWQ datasets.
WebQSP
CWQ
Method
Hits@1
F1
Hits@
F1
81.2
77.4
74.5
= 3
94.0
81.7
77.6
74.7
I, = 4
93.7
81.4
78.0
75.1
I. 1 5
93.8
81.6
77.9
74.9
Table 13: Hyperparameter sensitivity analysis the reasoning path length L on the WebQSP and CWQ datasets.
settings. As presented in Table and Table these results provide a comprehensive understanding of the model's sensitivity and stability across range of configurations.
E.5 MORE THEORETICAL ANALYSIS
To empirically examine the stability and robustness of the online fine-tuning process in DAMR, analyze the evolution of the path evaluator and its sensitivity to confidence margins. As shown in Figure 4 the predicted plausibility scores for positive and negative paths evolve steadily across refinement rounds, with positive-path scores (blue) increasing and negative-pate scores (orange) decreasing, indicating stable convergence and clear separation without oscillation. To further evalu- ate robustness to noisy pseudo-pairs, we tested different confidence margins when forming training pairs. As presented in Table [4, performance remains consistent across margins ranging from 0.05 to 0.2, demonstrating that DAMR is largely insensitive to the threshold choice. Smaller margins slightly improve stability by filtering uncertain pairs, whereas larger margins remove too many sam- ples and marginally reduce recall, confirming that the margin criterion effectively balances pseudo- label quality and robustness.
F DISCUSSION
The design of DAMR is inspired by key limitations observed in previous KGQA frameworks. Ex- isting LLM-based planners often entangle reasoning with generation, resulting in high computa- tional overhead and limited adaptability. Static path scorers in prior graph reasoning models lack the ability to adjust to evolving exploration dynamics, while end-to-end reinforcement approaches frequently suffer from sparse and unstable rewards. DAMR overcomes these challenges through decoupled and modular architecture that employs the L.M solely for semantic expansion, integrates a lightweight adaptive scorer for trajectory evaluation, and incorporates empiricall-reurn-baal back for stable self-correction. Together, these components enable DAMR to achieve both efficiency and adaptability, effectively bridging symbolic search LLM-guided reasoning.
feed-
G PROMPT TEMPLATE
We provide the prompt templates used by the LLM-based planner to select the top-k most relevant relations from the candidate set at each step of path expansion Figure as part of the LLM Guided Path Expansion module.
21

---

"who was the president after jfk died" Published as a conference paper at ICLR 2026
WebQSP
CWQ
Methods
Hits@1 1
Fl
Hits 1
F1
DAMR margin=0.05
93.9
81.8
78.1
75.1
DAMR margin=0.1
93.9
81.7
77.9
75.1
DAMR margin=0.2
93.7
81.6
78.1
75.2
DAMR
94.0
81.7
78.0
75.1
Table 14: Performance of DAMR under different confidence margin settings on WebQSP and CWQQ
0.0935
Negative Positive
0.8705
Negative Positive
0.7550
0.0930
0.0520
0.7500
Negative Path
0.0925
Positive Path
Negative Path
0.7450
Positive Path
0.0500
0.0920
0.8693
0.7400
0.0915
0.0480
0.7350
0.0910
0.0690
0.0905
0.0460
0.7300
15
20
15
Rerations
iterations
(a) WebQSP.
(b) CWQ.
Figure 4: Average predicted scores of the path evaluation model for real positive and negative paths during MCTS iterations on WebQSP and CWQ.
Prompt Template for L-GMGdddde Path Expansion
Role
You expert assistant for Knowledge Graph Question Answering (KGQA). Your core capability to deeply understand natural language questions and the semantics of knowledge graph relations find the most relevant reasoning paths.
Task
Your task to act as "Relation Retriever." Given natural language question and a list of candidate relations, you must analyze the semantics of the question and each relation to select up relations that are most likely to lead the correct answer.
Rules and Constraints
Fidelity to Candidates: Your selection of relations MUST come strictly from the pro- vided Candidate Relations list. Do not invent modify relations.
Quantity Limit: Return more than k relations. If multiple relations highly rele- vant, order them from most to least relevant. there are fewer than k relevant relations, return only those.
Output Format: Your response MUST be a list of strings, containing the names the relations you have selected.
Example
Input:
Question:
Candidate Relation ions: ggooerrment..rreiddeee
"govern- "peo-
mentppreidenntssccesss"""
"locattionlocattooccomnaeeee
pfaceoo
K: 2
Output:
"government. outprmeeerrprrrreeeeeeuuucesss
Your Task
Question: {question}
Candi dandidate Relations: (relations list)
K: (k}
Output:
[]
22

---

Published as a conference paper at ICLR 2026
Figure 5: Prompt template used in the LLM-based planner to select top-k relations during reasoning.
H THE USE OF LARGE LANGUAGE MODELS (LLMS)
Large language models (LLMs) were only used to improve the clarity, grammar. and fluency of the manuscript. They were not involved the development of research ideas, experimental design, data analysis, or any other aspect of the scientific content.
23


Reviews:
[{"review_id": "ulX6ZPTxMz", "reviewer": "Reviewer_oPog", "summary": "This paper introduces DAMR, an MCTS-based framework for Knowledge Graph Question Answering that utilizes LLM-guided expansion, a lightweight transformer-based, cross-attention path evaluator, and dynamic pseudo-path refinement for continual scorer adaptation. The paper provides substantive ablation, efficiency, and sensitivity analyses, as well as qualitative examples highlighting the method’s strengths.", "questions": "see weaknesses.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. Dynamic Pseudo-Path Refinement: The method innovates by using high-confidence partial paths from MCTS rollouts to generate pseudo labels for continual fine-tuning , thus improving generalizability and adapting to the non-stationary search space.\n\n2. Rigorous Empirical Validation: Extensive benchmarks across both standard datasets, with direct comparisons to at least 20 strong baselines  are provided in Table 1, consistently showing DAMR outperforming all competitors.", "weaknesses": "1. It is unclear under what distributional shifts the scorer avoids reinforcing suboptimal trajectories. Since the path scorer is continually adapted with self-generated pseudo-paths, there is risk of feedback loops or bias accumulation, especially if the LLM suggestions are systematically biased early in training.\n\n2. Scalability and practicality on large KGs not addressed. All experiments are conducted on localized subgraphs derived from WebQSP and CWQ. The scalability of DAMR for web-scale or multi-million entity KGs is not empirically or mathematically analyzed. How does the MCTS backbone behave when the entity degree is very high, or when context selection via LLMs requires thousands of candidates? Is the method robust under significant KG incompleteness or noise? Discussion is notably absent.\n\n3. Lack of feedback for LLM planner improvement. While DAMR incorporates dynamic refinement for the path evaluator, the LLM-based planner, which determines the search direction, receives no feedback signal from the search process. As a result, the planner cannot benefit from experience or adapt its relation selection strategy over time. \n\n4. Lack of variance and statistical significance reporting. The experimental results are reported only as single-point metrics, without variance or statistical significance analysis. Including standard deviations across multiple random seeds, confidence intervals, or hypothesis testing (e.g., paired t-test, bootstrap) would strengthen the reliability of the claimed performance improvements.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JHmDSx6XFZ", "reviewer": "Reviewer_9F1L", "summary": "The paper presents a new framework for knowledge graph question answering that addresses adaptability, accuracy, and computational cost issues raised by previous approaches. This is implemented by combining an LLM-based planner, a lightweight Transformer-based scorer, and a dynamic pseudo-path refinement mechanism on top of a Monte Carlo Tree Search (MCTS) backbone. The paper is well motivated, clearly presented, and shows promising results according to experiments to achieve the design purposes.", "questions": "1. Why are the three baseline methods selected in particular for the computational efficiency comparison?\n2. What are the (positive or negative) impacts of each key component on the overall accuracy and computation efficiency of the proposed framework? Current paper only partially answers this question.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The overall approach is novel to me, though not entirely new due to extensive existing efforts in this field of research. The authors describe a clear step-wise procedure with sufficient details to show how the approach works. The approach presents as a sound solution to address the identified limitations of the existing approaches.\n\n2. Effectively modularizes reasoning by limiting the LLM's role to an initial, high-leverage search guidance step, significantly reducing computational overhead.\n\n3. The experiments were comprehensive with convincing results, covering performance comparisons, efficiency analysis, ablations, sensitivity studies, and the impact of LLMs. The case study also helps with understanding of the final outcome.", "weaknesses": "1. The comparative discussion against related work could be strengthened to reveal more details about the rationale of designs in the proposed framework. \n\n2. The selection of baseline methods in Table 2 should be discussed. More specifically, why are the three baseline methods selected in particular for the computational efficiency comparison?\n\n3. A clear mapping between the technical components and the advantages/edge achieved by the proposed framework might be better explained, demanding studying the impact of key components on the overall accuracy and computational efficiency of the framework.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XwHWeV1mIp", "reviewer": "Reviewer_qmee", "summary": "DAMR is an LLM-guided Monte-Carlo Tree Search framework for KGQA that decomposes reasoning into three coordinated parts: (i) an LLM planner used only for expansion, proposing the top-k relations at each node to aggressively prune the graph; (ii) a lightweight cross-attention path scorer that jointly encodes the question and the evolving relation sequence to estimate path plausibility; and (iii) an online pseudo-path refinement loop that converts high-value (partial) paths discovered during search into pairwise supervision, continually adapting the scorer to the search distribution. On WebQSP and CWQ, DAMR reports higher Hits@1/F1 than semantic-parsing, retrieval, and LLM+KG baselines while markedly reducing LLM calls and tokens. Comprehensive ablations (removing the scorer/refinement or replacing the scorer with a general LLM), sensitivity analyses (k and max hop L), and backbone swaps (Llama/Qwen/GPT-4.1) support the design. The approach emphasizes efficiency, path-level interpretability, and modularity (LLM for direction, small Transformer for judgment, MCTS for integration). Current evidence is Freebase-centric (WebQSP/CWQ); extending to Wikidata or domain KGs (e.g., biomedical) and clarifying the evaluation protocol (full test vs. sampled subsets, confidence intervals) are natural next steps.", "questions": "1. Why did you evaluate on 1,000 sampled test questions instead of the full official splits, and can you report full-test metrics and/or confidence intervals across multiple samples?\n2. What are the exact prompts for relation selection, including decoding parameters, the per-hop value of (k), and the procedure for mapping LLM-suggested relations to graph edges when multiple lexicalizations exist?\n3. What is the fallback when the LLM proposes relations absent from the local subgraph or yields fewer than (k) candidates (e.g., degree-based backup or other heuristics)?\n4. How do you prevent the online fine-tuning loop from overfitting to early search biases, and did you test confidence margins or require minimum value gaps for training pairs? Do you have curves of scorer AUC versus refinement rounds?\n5. What are the end-to-end wall-clock latencies per query and GPU/CPU utilizations for DAMR compared with baselines, beyond token and call counts?\n6. Have you evaluated on Wikidata or a domain KG such as UMLS, and what challenges do you anticipate (schema size, relation lexicalization diversity, entity alias noise)?\n7. How sensitive is performance to the scorer’s design choices: (a) cross-attention versus simple concatenation, (b) the presence and type of positional encodings, and (c) pairwise ranking loss versus regression?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Uses the LLM only for expansion and a small Transformer for evaluation, cutting LLM calls by >50% and tokens by ~75% without hurting accuracy, lowering cost/latency and allowing easy module swaps under resource limits.\n2. Employs a cross-attention scorer conditioned on the question to model relation sequences hop-by-hop, capturing semantic buildup and constraints for steadier rankings and better generalization than a general LLM scorer.\n3. Converts promising/contrasting partial paths into pairwise supervision during search, continually adapting the scorer to the current distribution and mitigating early-stage bias without sparse-reward RL instability.\n4. Demonstrates consistent gains on WebQSP and CWQ with strong baselines, component ablations, sensitivity to 𝑘 and max hop 𝐿, and backbone swaps (Llama2-13B, Qwen3-14B, GPT-4.1/mini), supporting accuracy, efficiency, and robustness.\n5. Outputs explicit KG paths as reasoning traces, making the question-to-answer chain transparent and easing auditing/error localization versus black-box LLM reasoning.", "weaknesses": "1. Reporting on 1,000 uniformly sampled test questions rather than full official splits inflates variance and hinders comparability; the absence of confidence intervals, significance tests, and an error taxonomy (e.g., compositional, comparative failures) weakens claims of robustness and external validity.\n2. Dynamic pseudo-labeling lacks stability analysis: pair generation driven by search stats is not evaluated for convergence or early-noise sensitivity, and safeguards (confidence margins, temperature/top-p thresholds, value-gap filters) against confirmation bias/drift are unspecified.\n3. Reproducibility and fairness are under-detailed: planner prompts, 𝑘-per-hop policy, decoding/tie-breaking, and failure handling are undisclosed; use of external services (GPT-4.1 planner, Qwen3-Embedding-8B) lacks API versions, costs, and train/freeze settings; it’s unclear whether baselines were re-run under comparable planner strength.\n4. Generality is unproven beyond Freebase (WebQSP, CWQ); no evidence on other schemas or domains (e.g., Wikidata, biomedical) or on how schema size, relation lexicalization diversity, and alias noise affect performance.\n5. Practical replication is hindered by notation/editorial issues (typos, cross-refs) and missing training hyperparameters (batch sizes, negative sampling ratios, per-dataset hop limits), obscuring the path to matching the reported accuracy/efficiency trade-offs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)