Dynamically Adaptive Reasoning via LLM-Guided MCTS for Efficient and Context-Aware KGQA

Yingxu Wang, Shiqi Fan, Mengzhu Wang, Siyang Gao, Siwei Liu, Nan Yin · 2025

Read Dynamically Adaptive Reasoning via LLM-Guided MCTS for Efficient and Context-Aware KGQA by Yingxu Wang, Shiqi Fan, Mengzhu Wang, Siyang Gao, Siwei Liu, Nan Yin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-00719.txt.

Introduction

Answering questions over a knowledge graph means walking its web of facts, often several hops deep. Yingxu Wang and co-authors present DAMR, a framework that searches that web with a game-tree method guided by a language model. At each step the model proposes only the most promising relations, which keeps the branching small.

A light transformer scores each partial path against the question, catching subtle shifts in meaning as the walk lengthens. Training data for that scorer is scarce, so the system refines practice paths from its own searches as it goes. On standard benchmarks the method beat the best published rivals. The authors frame it as a way to get careful, step-by-step reasoning without paying for constant calls to a giant model.

Catalog record

CREATORYingxu Wang, Shiqi Fan, Mengzhu Wang, Siyang Gao, Siwei Liu, Nan Yin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-00719

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Dynamically Adaptive Reasoning via LLM-Guided MCTS for Efficient and Context-Aware KGQA Yingxu Wang, Shiqi Fan, Mengzhu Wang, Siyang Gao, Siwei Liu, Nan Yin 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. Recent KGQA methods primarily follow either retrieve-then-reason paradigm, relying on GNNs or heuristic rules for static paths extraction, or dynamic path generation strategies that use large language models (LLMs) with prompting to jointly perform retrieval and reasoning. However, the former suffers from limited adaptability due to static path extraction and lack of contextual refinement, while the latter incurs high computational costs and struggles with accurate path evaluation due to reliance on fixed scoring functions and extensive LLM calls. To address these issues, this paper proposes D ynamically A daptive M CTS-based R easoning (DAMR), a novel framework that integrates symbolic search with adaptive path evaluation for efficient and context-aware KGQA. DAMR employs a Monte Carlo Tree Search (MCTS) backbone guided by an LLM-based planner, which selects top- k k relevant relations at each step to reduce search space. To improve path 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, enabling the model to capture fine-grained semantic shifts during multi-hop reasoning. Furthermore, to alleviate 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, allowing the scorer to continuously adapt to the evolving distribution of reasoning trajectories. Extensive experiments on multiple KGQA benchmarks show that DAMR significantly outperforms state-of-the-art methods. Introduction Large Language Models (LLMs) have demonstrated impressive reasoning capabilities across diverse tasks, including mathematical problem solving ( Pei et al. 2025 ; Didolkar et al. 2024 ) , commonsense inference ( Wang et al. 2023b ; Toroghi et al. 2024 ) , and open-domain question answering ( Zhao et al. 2023 ) . Despite their generalization ability, LLMs often struggle in domain-specific scenarios due to the lack of grounded external knowledge, resulting in factual hallucinations and high inference costs ( Huang et al. 2025b ; Wang et al. 2024c ) . To address these limitations, recent efforts have explored integrating domain knowledge into LLM reasoning. A promising direction to overcome these limitations is Knowledge Graph Question Answering (KGQA) ( Dammu, Naidu, and Shah 2025 ; Saxena, Tripathi, and Talukdar 2020 ; Choi et al. 2023 ; Yin et al. 2024b ) , which integrates symbolic relational structures into the reasoning process to provide factual grounding and structural interpretability. By combining the expressiveness of natural language with the precision of knowledge graphs, KGQA offers a scalable solution to improve factual consistency, reasoning transparency, and answer reliability ( Liu et al. 2025 ; Yao et al. 2025 ) . Existing KGQA approaches can be broadly categorized into two main paradigms based on how they construct reasoning paths: retrieve-then-reason methods and dynamic path generation strategies. The first category adopts a retrieve-then-reason paradigm, where candidate reasoning paths are extracted using either Graph Neural Networks (GNNs) ( Ma et al. 2025a ; Yao et al. 2025 ; Yin et al. 2024c ; Wang et al. 2024d ; Wang et al. 2024b ) or rule-based heuristics ( Chen et al. 2023 ; Fang et al. 2024 ; Yin et al. 2022 ) prior to answer prediction. However, these methods lack adaptability, as GNNs fail to incorporate question-specific semantics at inference time, while heuristic rules are inherently inflexible to support dynamic reasoning refinement ( Liu et al. 2025 ; Yao et al. 2025 ) . In contrast, dynamic path generation strategies unify retrieval and reasoning by constructing reasoning paths dynamically during question processing. These methods either prompt LLMs to iteratively generate paths via in-context learning or Chain-of-Thought (CoT) prompting ( Sui et al. 2024 ; Li et al. 2024 ; Yin et al. 2024a ) , or employ guided search techniques such as Monte Carlo Tree Search (MCTS) to incrementally expand paths with the aid of a path scorer ( Ma et al. 2025b ; Shen et al. 2025 ) . Despite their flexibility, these approaches incur substantial computational overhead due to repeated LLM invocation and exhibit limited evaluation accuracy, as static scorers fail to capture the evolving semantics of reasoning paths ( Chang et al. 2024 ; Shen et al. 2025 ) . This paper investigates the design of an adaptive KGQA framework to address the challenges of computational inefficiency and limited path evaluation accuracy in dynamic reasoning. However, developing such a framework presents several key challenges: (1) How to modularize reasoning to reduce LLM overuse during search? A major source of computational inefficiency in dynamic KGQA lies in repeatedly invoking LLMs for both relation retrieval and reasoning during multi-hop path construction ( Shen et al. 2025 ; Long et al. 2025 ) . While methods such as CoT and MCTS provide flexible exploration, they tightly couple LLMs with each decision step, resulting in high inference costs and limited scalability. The key challenge is to design a modular reasoning framework that utilizes LLMs efficiently, guiding the search process without requiring direct involvement in every reasoning step. (2) How to accurately evaluate evolving reasoning paths? As multi-hop reasoning paths are incrementally constructed, their semantics evolve with each newly added relation and contextual information. However, existing methods typically rely on static scoring functions or shallow similarity metrics, which fail to capture the nuanced semantic shifts that occur throughout the reasoning process ( Xu et al. 2024 ; Sui et al. 2024 ) . This raises a key challenge: how to design a path evaluation model that adaptively captures fine-grained semantic changes conditioned on both the question and the evolving relation sequence. (3) How to train a reliable path evaluation model with limited supervision? Accurate path ranking in KGQA hinges on a well-calibrated evaluation model. However, dynamic reasoning methods typically produce a large number of incomplete or irrelevant paths, with only a small subset corresponding to valid reasoning trajectories. This results in highly imbalanced and noisy supervision, especially for multi-hop questions where successful paths are extremely sparse. Although reinforcement learning has been explored to mitigate this issue ( Ma et al. 2024 ; Zhai et al. 2024 ) , it frequently suffers from sparse rewards and unstable optimization. Therefore, the key challenge is how to construct meaningful learning signals from limited or implicit supervision to enable adaptive training of the path scorer. To address the above challenges, we propose D ynamically A daptive M CTS-based R easoning (DAMR), an efficient and adaptive reasoning framework that integrates symbolic search with context-aware semantic modeling to enable accurate and LLM-efficient multi-hop reasoning for KGQA. DAMR is built on an MCTS backbone, where an LLM-based planner dynamically guides path expansion by proposing semantically relevant relations at each step, significantly reducing search space and improving answer identification efficiency. To enable accurate and context-sensitive path evaluation, we introduce a lightweight Transformer-based scorer that estimates path plausibility by jointly encoding the question and relation sequence via cross-attention, effectively capturing evolving semantics during multi-hop reasoning. To address supervision scarcity, DAMR incorporates a dynamic pseudo-path mechanism that

Read the complete text