# MCTS-KBQA: Monte Carlo Tree Search with Information Gain Rewards for Knowledge Base Question Answering

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 18 of its 36 references that are in the map.
- First posted on arXiv 19 Feb 2025.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)
- LLM alignment / RLHF / preference optimisation / [Process reward models for reasoning](https://mlsanity.com/alignment/process-reward-models-for-reasoning/)

## Builds on (most cited first, 18 of 18)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Gemma 2: Improving Open Language Models at a Practical Size](https://mlsanity.com/paper/2408.00118/) (2024)
- [Large Language Models Cannot Self-Correct Reasoning Yet](https://mlsanity.com/paper/2310.01798/) (2023)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [The Web as a Knowledge-base for Answering Complex Questions](https://mlsanity.com/paper/1803.06643/) (2018)
- [ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search](https://mlsanity.com/paper/2406.03816/) (2024)
- [StructGPT: A General Framework for Large Language Model to Reason over Structured Data](https://mlsanity.com/paper/2305.09645/) (2023)
- [Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning](https://mlsanity.com/paper/2405.00451/) (2024)
- [Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph](https://mlsanity.com/paper/2307.07697/) (2023)
- [Beyond I.I.D.: Three Levels of Generalization for Question Answering on Knowledge Bases](https://mlsanity.com/paper/2011.07743/) (2020)
- [AlphaMath Almost Zero: Process Supervision without Process](https://mlsanity.com/paper/2405.03553/) (2024)
- [Accessing GPT-4 level Mathematical Olympiad Solutions via Monte Carlo Tree Self-refine with LLaMa-3 8B](https://mlsanity.com/paper/2406.07394/) (2024)
- [KG-Agent: An Efficient Autonomous Agent Framework for Complex Reasoning over Knowledge Graph](https://mlsanity.com/paper/2402.11163/) (2024)
- [LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning](https://mlsanity.com/paper/2410.02884/) (2024)
- [DecAF: Joint Decoding of Answers and Logical Forms for Question Answering over Knowledge Bases](https://mlsanity.com/paper/2210.00063/) (2022)
- [TIARA: Multi-grained Retrieval for Robust Question Answering over Large Knowledge Bases](https://mlsanity.com/paper/2210.12925/) (2022)

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

- [A Survey of LLM-based Deep Search Agents: Paradigm, Optimization, Evaluation, and Challenges](https://mlsanity.com/paper/2508.05668/) (2025)
- [Synergizing RAG and Reasoning: A Systematic Review](https://mlsanity.com/paper/2504.15909/) (2025)
- [LLM/Agent-as-Data-Analyst: A Survey](https://mlsanity.com/paper/2509.23988/) (2025)
- [GraphRAG-R1: Graph Retrieval-Augmented Generation with Process-Constrained Reinforcement Learning](https://mlsanity.com/paper/2507.23581/) (2025)
- [KnowCoder-A1: Incentivizing Agentic Reasoning Capability with Outcome Supervision for KBQA](https://mlsanity.com/paper/2510.25101/) (2025)
- [Beyond Fixed Budgets: Characterizing the Inelasticity and Limitations of Tree-of-Thought Reasoning Strategies](https://mlsanity.com/paper/2606.20599/) (2026)
- [When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models](https://mlsanity.com/paper/2608.30395/) (2026)

## Abstract (arXiv)

This work investigates how to improve large language model (LLM)-based reasoning for knowledge base question answering (KBQA) via Monte Carlo Tree Search (MCTS). Applying MCTS to LLM-based KBQA remains challenging because reward design is difficult and rollout-based search is computationally expensive. Existing MCTS-style methods either rely on direct LLM scoring or require substantial data to train separate reward models, and they often provide rewards only at terminal states. To address these limitations, we propose Fast MCTS, which replaces terminal rollouts with an information gain (IG) reward for intermediate states. The IG reward is implemented as a question-conditioned PPL-ratio proxy over sanitized interaction histories, computed by forward passes of an open-source instruction LLM without additional reward-model training. Experiments on four KBQA benchmarks show that Fast MCTS consistently outperforms linear baselines and generally improves the accuracy-cost trade-off relative to rollout-based Classic MCTS. Code and data are available at https://github.com/JimXiongGM/MCTS-KBQA.