MCTS-KBQA: Monte Carlo Tree Search for Knowledge Base Question Answering

arXiv:2502.13428 · cs.CL, cs.AI · Submitted 2026-08-18 · Read on arXiv

Guanming Xiong, Haochen Li, Zonghong Dai, Liqiang Wen, Wen Zhao

cs.CL, cs.AI

Submitted: 2026-08-18

Updated: 2026-08-19

Comments: Accepted to CIKM 2026

DOI: 10.1145/3799682.3840891

Code: https://github.com/JimXiongGM/MCTS-KBQA

License: http://creativecommons.org/licenses/by/4.0/

The gist: This work investigates how to improve large language model (LLM)-based reasoning for knowledge base question answering (KBQA) via Monte Carlo Tree Search (MCTS).

Terminology

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.

Sources

Related papers