MCTS（LLM推論）（エムシーティーエスエルエルエムスイロン）

MCTS × LLM とは

Monte Carlo Tree Search（MCTS）をLLMの推論に適用する手法は、2024年後半のTest-Time Compute研究の中心的テーマとなった。ゲームAI（囲碁・将棋・チェス）で圧倒的な実績を持つMCTSを言語生成に転用することで、複雑な推論タスクでの精度を大幅に向上させる。

MCTSの基本構造

古典的なMCTSは4フェーズで動作する。

Selection（選択）: UCT（Upper Confidence Bound for Trees）スコアが最高のノードを選択する。

Expansion（展開）: 選択ノードから新しい子ノード（次の推論ステップ）を生成する。

Simulation（シミュレーション）: 末端まで探索してスコアを取得する。

Backpropagation（逆伝播）: 得られたスコアを親ノードに伝播させる。

LLM推論への適用

LLM推論でのMCTSでは、各ノードが「推論ステップ（Thought）」を表す。木の根ノードが問題文、各枝が中間推論ステップ、末端ノードが最終回答に対応する。

探索の流れは次のようになる。根ノードから出発し、UCTスコアで有望な枝を選択する。選択したノードからLLMに次のThoughtを複数生成させ展開する。PRMで各ノードをスコアリングし、スコアを逆伝播させる。このサイクルを計算バジェット内で繰り返す。

プロセス報酬モデル（PRM）の役割

各ノード（部分推論）の品質を評価するにはPRM（Process Reward Model）が必要だ。

ORM（Outcome RM）は最終答えのみで評価するシンプルな報酬モデルで、MCTSとの相性は劣る。PRM（プロセス報酬モデル）は各推論ステップで評価し、ノードごとのスコアリングが可能なためMCTSとの相性が良い。Math-Shepherd（2024）・Qwen2.5-Math-PRMなどのオープンソースモデルが利用可能だ。

UCTスコアの計算

UCTスコアは活用項（これまでの実績）と探索項（まだ訪問が少ない枝）のバランスで計算される。Q(s,a)は累積PRMスコア（活用項）、N(s)は親ノードの訪問回数、N(s,a)はこの行動の訪問回数、Cは探索係数（通常0.5〜2.0）を表す。探索係数Cを大きくすると未探索の枝を積極的に試み、小さくすると実績のある枝を深掘りする。

代表的な研究・実装

AlphaCode 2（DeepMind 2023）はコード生成にMCTSを適用し、競技プログラミングで人間上位10%水準を達成した。rStar（Microsoft 2024）はSLM（小型言語モデル）にMCTSを適用し、大型モデルを超える数学推論を実現した。OpenAI o1（2024推定）は内部MCTSとPRMの組み合わせを使っているとされる。Qwen QwQ-32B（2024）はOSSの推論モデルにMCTS系手法を採用している。

計算コストと効率

MCTSはBest-of-NやSelf-Consistencyと比較して計算効率が高い。同じ計算バジェットでより多くの有望な経路を探索できるためだ。ただしPRMの呼び出しコストが追加される点は注意が必要だ。

実用上はDepth（木の深さ）3〜6、Branching Factor 2〜4、Total Nodes 20〜100程度が妥当とされる。

課題

PRM構築コストが高い点が最大の課題だ。高品質PRMの学習には大規模なステップレベルアノテーションが必要で、数学・コード以外のドメインでは構築が難しい。実装複雑度もBest-of-Nと比較して大幅に高い。また、検証可能な数学・コードに強い反面、創作・対話では効果が限定的だ。

まとめ

MCTS × LLMは、ゲームAIの知見を言語推論に応用する最も有力なTest-Time Compute手法の一つ。PRMと組み合わせることで、同等のモデルサイズでGPT-4水準の推論を達成できる可能性を示しており、2025年以降の推論モデル開発の中核技術となっている。