検証器ガイド探索（ケンショウキガイドタンサク）
LLMの推論時に検証器（Verifier）モデルを用いて推論パスを評価・選別しながら解空間を探索する手法。報酬モデルやプロセス報酬モデルを検証器として活用し、Beam SearchやMonte Carlo Tree Searchと組み合わせることで高精度な推論を実現する。
検証器ガイド探索とは
検証器ガイド探索（Verifier-Guided Search）とは、大規模言語モデルの推論時に検証器モデル（Verifier）を活用して推論パスの品質を評価しながら解空間を体系的に探索する手法である。単純なBest-of-Nサンプリングでは候補生成が独立・並列であるのに対し、検証器ガイド探索では探索の各段階で検証器のフィードバックを受けて次のステップの方向性を制御する。
探索アルゴリズムの分類
検証器ガイド探索で使用される主要なアルゴリズムは以下の通りである。
| アルゴリズム | 探索方式 | 検証頻度 | 計算コスト | 適用事例 |
|---|---|---|---|---|
| Beam Search + Verifier | 幅優先、固定ビーム幅 | ステップごと | 中 | 数学推論全般 |
| Monte Carlo Tree Search | 木探索、UCB選択 | ノード展開時 | 高 | AlphaProof、DeepSeek-R1 |
| Iterative Refinement | 逐次改善、1パス | 改善後に毎回 | 低〜中 | Self-Refine、LATS |
| Diverse Verifier Tree Search | 多様性重視木探索 | ステップごと | 高 | DVTS（OpenAI内部研究） |
Beam Search + Verifierの仕組み
最もシンプルな検証器ガイド探索は、Beam Searchと検証器の組み合わせである。
- 初期プロンプトからビーム幅$B$本の推論パスを並列に開始する
- 各ステップで全パスの次のトークン（またはステップ）を生成する
- 検証器（PRM/ORM）で各パスにスコアを付与する
- 上位$B$本のパスのみを残し、残りを枝刈りする
- 終了条件（EOSトークン生成、最大長到達）まで繰り返す
- 最終的に最高スコアのパスを出力する
具体的なベンチマーク結果：
| 手法 | MATH (Pass@1) | GSM8K (Pass@1) | 計算コスト（相対） |
|---|---|---|---|
| Greedy Decoding | 52.9% | 87.2% | 1x |
| Best-of-16 (ORM) | 67.2% | 92.1% | 16x |
| Best-of-16 (PRM) | 72.4% | 94.3% | 16x |
| Beam Search B=4 (PRM) | 74.8% | 95.1% | 8x |
| MCTS 400 rollouts | 78.5% | 96.2% | 50x |
Beam Search + PRMはBest-of-N + PRMより少ない計算コストで高い精度を達成している点が特徴的である。
Monte Carlo Tree Search（MCTS）の統合
MCTSはAlphaGoで有名になった木探索アルゴリズムであり、LLMの推論ステップをゲームの「手」に見立てて探索する。
MCTSの4フェーズ:
- Selection: UCB（Upper Confidence Bound）に基づいて探索するノードを選択する
- Expansion: 選択したノードからLLMで新しい推論ステップを生成する
- Evaluation: 検証器（PRM）で新ノードの価値を評価する
- Backpropagation: 評価値をルートまで逆伝播してUCBを更新する
LLM推論へのMCTS適用事例:
| システム | 対象タスク | ロールアウト数 | 結果 |
|---|---|---|---|
| AlphaProof | IMO数学問題 | 数千〜数万 | IMO 2024で銀メダル相当の4問正解 |
| DeepSeek-R1 | 一般数学推論 | 64〜256 | MATH 97.3%（SOTA） |
| rStar-Math | 数学問題解法 | 128 | MATH 90.0%（7Bモデルで達成） |
| LATS | コード生成 | 32 | HumanEval 94.4% |
Iterative Refinement（逐次改善）
検証器のフィードバックを受けて回答を繰り返し改善するアプローチである。
Self-Refine:
- LLM自身が生成した回答を自己批評し、改善版を生成する
- 検証器は外部モデルまたはLLM自身が担当する
- 2〜5回のイテレーションで収束する場合が多い
LATS（Language Agent Tree Search）:
- 環境からのフィードバック（コード実行結果、テスト結果）を検証シグナルとして使用する
- 失敗した探索パスの情報を蓄積して次の試行に活用する
- ReAct + MCTSのハイブリッドとして設計されている
検証器の設計パターン
| 検証器タイプ | 入力 | 出力 | 長所 | 短所 |
|---|---|---|---|---|
| ORM（結果報酬） | 最終回答 | スコア（0-1） | 訓練容易 | 中間指導不可 |
| PRM（過程報酬） | 各ステップ | ステップスコア | 精密な枝刈り | 訓練データ高価 |
| 自己評価 | 回答全体 | テキスト批評 | 追加モデル不要 | バイアスあり |
| 環境フィードバック | コード/数式 | 実行結果 | 客観的 | 適用範囲限定 |
| アンサンブル | 複数モデル出力 | 合意スコア | 頑健 | 計算コスト大 |
コスト効率の最適化
検証器ガイド探索は計算コストが高いため、以下の最適化が重要である：
- 適応的探索深度: 検証器の初期スコアが高い場合は浅い探索で打ち切る
- Progressive Widening: 探索幅を段階的に広げ、有望なパスにのみ計算資源を集中する
- キャッシュ再利用: 共通の推論プレフィックスのKVキャッシュを共有する
- 非同期並列化: 候補生成と検証を非同期パイプラインで並列実行する
- 軽量検証器: 本番検証器の蒸留版（1.5B〜7Bパラメータ）を高速フィルタとして使用する
よくある質問（FAQ）
Q1: 検証器ガイド探索とBest-of-Nの使い分けはどうすべきか？ A: 計算予算が限られる場合や実装の簡潔さを重視する場合はBest-of-Nが適している。精度を最大化したい場合や探索空間が広い問題（数学証明、コード生成）では検証器ガイド探索が優れる。Beam Search + PRMはBest-of-N + PRMの半分の計算コストで同等以上の精度を達成できる。
Q2: 検証器の品質が低い場合でも効果はあるか？ A: 検証器の精度が50%程度（ランダムに近い）でも、多数回の探索を通じて統計的に正しいパスが選択される確率は向上する。ただし、検証器の精度が70%を下回ると費用対効果が急激に悪化するため、最低70%の精度が実用上の下限とされる。
Q3: オープンソースで検証器ガイド探索を実装するには？ A: SGLangフレームワークがTree Search機能を内蔵しており、カスタム検証器との統合が容易である。検証器にはMath-Shepherd（Mistral-7Bベース）やSkywork-o1-PRM（Qwen2.5-1.5Bベース）がオープンソースで利用可能。vLLMでも独自のサンプリングパイプラインを構築できる。
まとめ
- 検証器ガイド探索は推論パスを評価しながら解空間を体系的に探索する手法である
- Beam Search + PRMが計算効率と精度のバランスに最も優れる
- MCTSはAlphaProofやDeepSeek-R1で最高精度を達成しているが計算コストが非常に高い
- Iterative Refinementは実装が簡単でコード生成タスクに特に有効である
- 探索の効率化には適応的探索深度とキャッシュ再利用が鍵となる