Abstract
Knowledge Graph Question Answering (KGQA) aims to interpret natural languagequeries and perform structured reasoning over knowledge graphs by leveragingtheir relational and semantic structures to retrieve accurate answers. RecentKGQA methods primarily follow either retrieve-then-reason paradigm, relying onGNNs or heuristic rules for static paths extraction, or dynamic path generationstrategies that use large language models (LLMs) with prompting to jointlyperform retrieval and reasoning. However, the former suffers from limitedadaptability due to static path extraction and lack of contextual refinement,while the latter incurs high computational costs and struggles with accuratepath evaluation due to reliance on fixed scoring functions and extensive LLMcalls. To address these issues, this paper proposes Dynamically AdaptiveMCTS-based Reasoning (DAMR), a novel framework that integrates symbolic searchwith adaptive path evaluation for efficient and context-aware KGQA. DAMRemploys a Monte Carlo Tree Search (MCTS) backbone guided by an LLM-basedplanner, which selects top-$k$ relevant relations at each step to reduce searchspace. To improve path evaluation accuracy, we introduce a lightweightTransformer-based scorer that performs context-aware plausibility estimation byjointly encoding the question and relation sequence through cross-attention,enabling the model to capture fine-grained semantic shifts during multi-hopreasoning. Furthermore, to alleviate the scarcity of high-quality supervision,DAMR incorporates a dynamic pseudo-path refinement mechanism that periodicallygenerates training signals from partial paths explored during search, allowingthe scorer to continuously adapt to the evolving distribution of reasoningtrajectories. Extensive experiments on multiple KGQA benchmarks show that DAMRsignificantly outperforms state-of-the-art methods.