# DAMR: Efficient and Adaptive Context-Aware Knowledge Graph Question Answering with LLM-Guided MCTS

arXiv: https://arxiv.org/abs/2508.00719 · HTML: https://mlsanity.com/paper/2508.00719/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 50 of its 67 references that are in the map.
- First posted on arXiv 1 Aug 2025.

## Builds on (most cited first, 30 of 50)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Scaling Instruction-Finetuned Language Models](https://mlsanity.com/paper/2210.11416/) (2022)
- [Qwen2 Technical Report](https://mlsanity.com/paper/2407.10671/) (2024)
- [A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions](https://mlsanity.com/paper/2311.05232/) (2023)
- [Self-training with Noisy Student improves ImageNet classification](https://mlsanity.com/paper/1911.04252/) (2019)
- [A Survey on Evaluation of Large Language Models](https://mlsanity.com/paper/2307.03109/) (2023)
- [The Web as a Knowledge-base for Answering Complex Questions](https://mlsanity.com/paper/1803.06643/) (2018)
- [Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning](https://mlsanity.com/paper/2310.01061/) (2023)
- [DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning](https://mlsanity.com/paper/1707.06690/) (2017)
- [Key-Value Memory Networks for Directly Reading Documents](https://mlsanity.com/paper/1606.03126/) (2016)
- [Semi-Supervised Semantic Segmentation Using Unreliable Pseudo-Labels](https://mlsanity.com/paper/2203.03884/) (2022)
- [Evaluating the Logical Reasoning Ability of ChatGPT and GPT-4](https://mlsanity.com/paper/2304.03439/) (2023)
- [PullNet: Open Domain Question Answering with Iterative Retrieval on Knowledge Bases and Text](https://mlsanity.com/paper/1904.09537/) (2019)
- [Open Domain Question Answering Using Early Fusion of Knowledge Bases and Text](https://mlsanity.com/paper/1809.00782/) (2018)
- [Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning](https://mlsanity.com/paper/1711.05851/) (2017)
- [Fine-Tuning Large Vision-Language Models as Decision-Making Agents via Reinforcement Learning](https://mlsanity.com/paper/2405.10292/) (2024)
- [GNN-RAG: Graph Neural Retrieval for Large Language Model Reasoning](https://mlsanity.com/paper/2405.20139/) (2024)
- [UniKGQA: Unified Retrieval and Reasoning for Solving Multi-hop Question Answering Over Knowledge Graph](https://mlsanity.com/paper/2212.00959/) (2022)
- [Improving Multi-hop Knowledge Base Question Answering by Learning Intermediate Supervision Signals](https://mlsanity.com/paper/2101.03737/) (2021)
- [Knowledge-Driven CoT: Exploring Faithful Reasoning in LLMs for Knowledge-intensive Question Answering](https://mlsanity.com/paper/2308.13259/) (2023)
- [Subgraph Retrieval Enhanced Model for Multi-hop Knowledge Base Question Answering](https://mlsanity.com/paper/2202.13296/) (2022)
- [DecAF: Joint Decoding of Answers and Logical Forms for Question Answering over Knowledge Bases](https://mlsanity.com/paper/2210.00063/) (2022)
- [Metacognitive Capabilities of LLMs: An Exploration in Mathematical Problem Solving](https://mlsanity.com/paper/2405.12205/) (2024)
- [Simple Is Effective: The Roles of Graphs and Large Language Models in Knowledge-Graph-Based Retrieval-Augmented Generation](https://mlsanity.com/paper/2410.20724/) (2024)
- [Sequence-to-Sequence Knowledge Graph Completion and Question Answering](https://mlsanity.com/paper/2203.10321/) (2022)
- [Factuality of Large Language Models: A Survey](https://mlsanity.com/paper/2402.02420/) (2024)
- [Think-on-Graph 2.0: Deep and Faithful Large Language Model Reasoning with Knowledge-guided Retrieval Augmented Generation](https://mlsanity.com/paper/2407.10805/) (2024)

## Built on by (most cited first, 6 of 6)

- [Why Reasoning Fails to Plan: A Planning-Centric Analysis of Long-Horizon Decision Making in LLM Agents](https://mlsanity.com/paper/2601.22311/) (2026)
- [When Safety Collides: Resolving Multi-Category Harmful Conflicts in Text-to-Image Diffusion via Adaptive Safety Guidance](https://mlsanity.com/paper/2602.20880/) (2026)
- [When Agents Learn to Be You: Benchmarking Privacy Leakage, Impersonation Risk, and Defenses in Persona Skills](https://mlsanity.com/paper/2608.03700/) (2026)
- [PIME: Prototype-based Interpretable MCTS-Enhanced Brain Network Analysis for Disorder Diagnosis](https://mlsanity.com/paper/2602.21046/) (2026)
- [TRACE: An Experiential Framework for Coherent Multi-hop Knowledge Graph Question Answering](https://mlsanity.com/paper/2604.11193/) (2026)
- [Reward on Path: Learning Intermediate Supervision Signals for Knowledge Graph Question Answering](https://mlsanity.com/paper/2605.10791/) (2026)

## Abstract (arXiv)

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 or heuristic rules to extract static candidate paths, or dynamic path generation strategies that employ 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 SOTA methods.