R e KG - MCTS : Reinforcing LLM Reasoning on Knowledge Graphs via Training-Free M onte C arlo Tree Search (2025)

Abstract: Recent advancements in combining knowledge graphs (KGs) with large language models (LLMs) have demonstrated promising potential in complex KG reasoning tasks, yet existing approaches face limitations in path exploration strategies or excessive computational overhead. We propose ReKG-MCTS, a novel training-free framework that synergizes Monte Carlo Tree Search (MCTS) with LLM capabilities to enable dynamic reasoning over KGs. The framework conceptualizes KG reasoning as a decision-making process, where MCTS strategically explores paths over KG while LLMs provide semantic guidance for reasoning paths. The framework consists of four phases: (1) UCB-based node selection that balances exploration-exploitation on KG, (2) path expansion with KG structural constraints, (3) LLM-guided MC rollouts for simulation, and (4) value backpropagation. Experimental results on WebQSP and CWQ demonstrate that ReKG-MCTS outperforms existing training-free methods and achieves competitive performance compared to fine-tuned baselines. These findings suggest a new paradigm for leveraging language models in KG reasoning tasks. The code is available at https://github.com/ShawnKS/rekgmcts.

## introduction large language models (llms) have brought transformative advancements to various natural language processing (nlp) tasks, exhibiting remarkable capabilities in semantic understanding and inference generation @xcite @xcite @xcite . despite these successes, llms still suffer from hallucination and knowledge inconsistency issues @xcite @xcite , highlighting the need for grounding † corresponding authors their responses in factual knowledge. knowledge graphs (kgs) emerge as a promising solution to this challenge, as they provide structured and reliable factual information @xcite @xcite . however, leveraging kgs for reasoning remains challenging, as it requires precise multi-hop traversal and pathfinding capabilitiestasks where llms, designed primarily for unstructured text processing, face inherent limitations. recently, significant efforts have been made to augment llms with kg reasoning mechanisms @xcite @xcite . to search for relevant paths in knowledge graphs, these methods typically rely on pre-defined heuristics (e.g., beam search @xcite or llm-based relation pruning @xcite ), or delegate the path evaluation process to an llm @xcite . while yielding promising initial results, these approaches often face limitations in effectively utilizing path quality feedback during search @xcite @xcite . specifically, greedy or random strategies cannot adaptively adjust their search priorities based on the "goodness" of intermediate states, leading to either local optima or inefficient exploration of the solution space, particularly in complex multi-hop inference scenarios @xcite @xcite . monte carlo tree search (mcts) presents a compelling solution to these limitations by naturally incorporating path quality feedback into the search process @xcite @xcite . unlike static heuristics or one-shot sampling approaches, mcts dynamically evaluates and adjusts search priorities through its four fundamental steps: selection, expansion, simulation, and backpropagation. this iterative process enables the algorithm to learn from previous search attempts and adaptively balance between exploring new promising paths and exploiting known successful routes @xcite @xcite . building upon these intuitions, we propose rekg-mcts, a training-free framework that unifies mcts with llm-guided heuristics for efficient and interpretable kg reasoning. by viewing reasoning as a sequential decision-making process, our method adaptively refines search paths while balancing exploration and exploitation via mcts. in this paradigm, the llm simultaneously acts as a policy model, suggesting plausible entities and relations exploration, and as a value method, assessing the correctness of kg reasoning paths. this synergy enables effective kg exploration without finetuning or dedicated reward model engineering. the experiments on cwq and webqsp demonstrate that rekg-mcts achieves state-of-the-art performance among training-free methods and shows competitive performance with fine-tuned methods. in summary, our contributions are threefold: ## conclusion in this work, we introduce rekg-mcts, a novel training-free framework that combines monte carlo tree search (mcts) with llms to solve multi-hop reasoning tasks over kg. this approach frames kg reasoning as a decision-making process, where mcts explores promising paths and llms provide semantic guidance on knowledge graphs. by leveraging this framework, rekg-mcts enables effective multi-hop reasoning without the need for additional training or fine-tuning. extensive experiments on webqsp and cwq demonstrate that rekg-mcts not only outperforms existing training-free methods but also narrows the performance gap with fine-tuned approaches, indicating that structured search paradigms can effectively enhance llms' kg reasoning capabilities while preserving their semantic strengths. limitation rekg-mcts demonstrates competitive performance on kg reasoning tasks but has several limitations. first, the iterative search process is computationally expensive compared to simpler retrieval methods, resulting in higher token usage. second, the llm's context window constrains our ability to handle complex queries with numerous entities or lengthy reasoning chains. additionally, performance depends on both kg coverage and the llm's parametric knowledge-incomplete graph information or llm-generated spurious triples can lead to inaccuracies in the reasoning process. scott wen-tau yih, ming-wei chang, xiaodong he, and jianfeng gao. 2015. semantic parsing via staged query graph generation: question answering with knowledge base. in proceedings of the joint conference of the 53rd annual meeting of the acl and the 7th international joint conference on natural language processing of the afnlp. wen-tau yih, matthew richardson, christopher meek, ming-wei chang, and jina suh. 2016. 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 papers), pages 201-206. dan zhang, sining zhoubian, ziniu hu, yisong yue, yuxiao dong, and jie tang. 2024a. rest-mcts*: llm self-training via process reward guided tree search. in the thirty-eighth annual conference on neural information processing systems. qinggang zhang, junnan dong, hao chen, daochen zha, zailiang yu, and xiao huang. 2024b. knowgpt: knowledge graph based prompting for large language models. in the thirty-eighth annual conference on neural information processing systems. dengwei zhao, shikui tu, and lei xu. 2024. efficient retrosynthetic planning with mcts exploration enhanced a* search. communications chemistry, 7(1):52. peixiang zhao and jiawei han. 2010. on graph query optimization in large networks. proceedings of the vldb endowment, 3(1-2):340-351. lingfeng zhong, jia wu, qian li, hao peng, and xindong wu. 2023. a comprehensive survey on automatic knowledge graph construction. acm computing surveys, 56(4):1-62. zhaocheng zhu, zuobai zhang, louis-pascal xhonneux, and jian tang. 2021. neural bellman-ford networks: a general graph neural network framework for link prediction. advances in neural information processing systems, 34:29476-29490.