ReKG-MCTS: Reinforcing LLM Reasoning on Knowledge Graphs via Training-Free Monte Carlo Tree Search

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 . Celestial Body Mars Europa Riverbed traces Mars Polar Caps Reasoning Paths of Best Tree Node Question: Which celestial body in the solar system is most likely to have liquid water (besides Earth)? Label: Europa Celestial body Topic Entity Celestial Body Mars Europa Riverbed traces Mars Polar Caps Subsurface Ocean Hydrother mal activity Celestial Body Mars Europa Riverbed traces Mars Polar Caps Subsurface Ocean Hydrother mal activity Liquid water Celestial Body Mars Europa Riverbed traces Mars Polar Caps Subsurface Ocean Hydrother mal activity Liquid water