DeepSearch: 検証可能報酬を用いた強化学習におけるボトルネックを木探索で克服する

ICLR 2026 で発表された論文「DeepSearch: Overcome the Bottleneck of Reinforcement Learning with Verifiable Rewards via Tree-Based Search」の技術的サマリーを以下に示します。

1. 背景と課題 (Problem)

大規模言語モデル（LLM）の推論能力向上において、「検証可能報酬を用いた強化学習（RLVR）」は重要な手法となっています。しかし、既存の RLVR 手法には以下のような根本的な限界が存在します。

• 学習のプラトー現象: 数千ステップの最適化を行った後、計算コストを増大させても性能向上が頭打ちになる現象が観察されています。
• 探索の希薄さ: 従来の RLVR は、限られたロールアウト（試行）に依存しており、重要な推論経路を見逃したり、解空間の体系的な網羅ができていなかったりします。
• 推論と学習の乖離: 多くの先行研究では、木探索（Tree Search）などの構造化された探索は「推論時（Inference）」のみに行われ、「学習時（Training）」には統合されていません。この分離により、モデルは推論時に高度な探索行動を示すよう期待される一方で、学習時には体系的な探索経験を得られないという矛盾が生じています。

2. 提案手法：DeepSearch (Methodology)

DeepSearch は、モンテカルロ木探索（MCTS）を RLVR の学習ループに直接統合するフレームワークです。単に学習ステップ数を増やす（スケーリング）のではなく、学習時の「探索の質」を高めることで性能向上を図ります。

主要な構成要素

1. エントロピーに基づく拡張と選択 (Expansion with Entropy-Based Guidance)

   • 正解が見つからない場合、ランダムな誤りではなく、モデルが**最も自信を持っている誤った推論経路（エントロピーが最小の経路）**を選択して教師信号として利用します。これにより、モデルが体系的に犯している誤りを重点的に修正できます。

2. ハイブリッド選択戦略：グローバルフロンティア選択 (Hybrid Selection Strategy)

   • 従来の MCTS が使用する UCT（Upper Confidence Bounds for Trees）は、ルートからリーフまでの局所的な探索に偏りやすく、計算の無駄や視野の狭さ（Myopia）を招きます。
   • DeepSearch は、グローバルフロンティア選択を導入し、木全体にあるすべてのリーフノード（フロンティア）を同時に評価・比較します。
   • 選択スコアは以下の 3 つの要素で構成されます：
     • 品質ポテンシャル: 親ノードの価値（Q-value）。
     • 不確実性ボーナス: ポリシーのエントロピー（高い不確実性や高い自信を持つ領域を特定）。
     • 深さボーナス: より深い推論チェーンへの探索を促進。

3. 適応的トレーニングとリプレイバッファ (Adaptive Training with Replay Buffer)

   • 全問題に対して MCTS を実行するのは計算コストが高いため、逐次的なフィルタリングを行います。モデルがすでに解けるようになった問題は学習セットから除外し、計算リソースを「まだ解けていない難しい問題」に集中させます。
   • キャッシュされた解の再利用: 一度 MCTS で正解を見つけた問題は、その経路をリプレイバッファに保存し、次回以降のトレーニングでは MCTS 実行をスキップしてキャッシュされた解を直接使用します。これにより、重複計算を回避し、効率的な学習を実現します。

4. Tree-GRPO 学習目的

   • 木構造の推論痕跡から学習するために、ノードレベルの Q 値を正規化し、GRPO（Grouped Relative Policy Optimization）を拡張した目的関数（Tree-GRPO）を最適化します。中間ノードに対して、終端ノードの報酬だけでなく、経路ごとの Q 値に基づく微細なクレジット割り当てを行います。

3. 主要な貢献 (Key Contributions)

1. 学習時の探索の統合: 推論時のみに限られていた構造化探索を学習プロセスに組み込み、RLVR のボトルネックである「探索不足」を解決しました。
2. グローバルフロンティア選択戦略: 木全体を視野に入れたノード選択により、局所最適解に陥るのを防ぎ、効率的な探索を可能にしました。
3. エントロピーに基づく負のサンプル選択: 最も自信のある誤り（低エントロピーの誤り）を特定し、学習に活用することで、モデルの体系的な誤りを効果的に修正しました。
4. 適応的リプレイバッファ: 難易度に応じたフィルタリングと解のキャッシュにより、計算資源を最大限に活用する効率的なトレーニングパイプラインを構築しました。

4. 実験結果 (Results)

数学推論ベンチマーク（AIME 2024/2025, AMC2023, MATH500, Minerva, Olympiad など）において評価を行いました。

• 性能: 1.5B パラメータのモデルにおいて、平均精度 62.95% を達成し、既存の最良モデル（Nemotron-Research-Reasoning-Qwen-1.5B v2 の 61.70%）を上回る新たな SOTA を確立しました。
• 効率性: 従来の「学習ステップ数の延長（Extended Training）」アプローチと比較して、5.7 倍少ない GPU 時間（330 GPU 時間 vs 1883 GPU 時間）で同等以上の性能を達成しました。
  • 従来の手法は計算コストを増やしても性能が頭打ちになるのに対し、DeepSearch はアルゴリズム的な革新により、少ない計算量で高い性能向上を実現しました。
• アブレーション研究:
  • グローバルフロンティア選択は、従来の UCT 単独に比べて探索効率と経路の質を向上させました。
  • 「最も自信のある誤り」を選択する戦略が、ランダム選択や「最も自信のない誤り」の選択よりも優れていることが確認されました。

5. 意義と結論 (Significance)

DeepSearch は、LLM の推論能力を拡張する際のアプローチに重要な転換点を示しています。

• 計算スケーリングから探索スケーリングへ: 単にモデルサイズや学習時間を増やす（Brute-force scaling）のではなく、**体系的な探索（Systematic Exploration）**を学習プロセスに組み込むことで、より効率的かつ効果的な学習が可能であることを実証しました。
• 推論と学習の統合: 推論時に期待される高度な推論パターンを、学習プロセス自体に反映させることで、モデルがより堅牢な推論能力を獲得できることを示しました。
• 将来の展望: この手法は数学推論に限らず、検証可能な報酬が存在する他の複雑な推論タスクや、人間との協調が必要な領域への応用が期待されます。

結論として、DeepSearch は「学習時の探索の質」を最適化することによって、RLVR の限界を突破し、計算効率と推論性能の両立を実現する新たな方向性を提示しました。