Tutorials
MCTS-KBQA: Monte Carlo Tree Search with Information Gain Rewards for Knowledge Base Question Answering
arXiv:2502.13428v2 Announce Type: replace-cross Abstract: This work investigates how to improve large language model (LLM)-based reasoning for knowledge base question answering (KBQA) via Monte Carlo
arXiv:2502.13428v2 Announce Type: replace-cross Abstract: 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.
Related
- SCPRM: A Schema-aware Cumulative Process Reward Model for Knowledge Graph Question Answering
- Beyond the Node: Clade-level Selection for Efficient MCTS in Automatic Heuristic Design
- Learning from Contrasts: Synthesizing Reasoning Paths from Diverse Search Trajectories
Source: arXiv cs.AI | 2026-08-19