Best-of-Nサンプリング（ベストオブエヌサンプリング）
LLMに同じプロンプトからN個の候補回答を並列生成させ、報酬モデルやヒューリスティクスで最も高品質な回答を選択する推論時計算手法。計算コストはN倍になるが、実装が単純で効果が安定している。
Best-of-Nサンプリングとは
Best-of-Nサンプリング（BoN）とは、大規模言語モデルの推論時にN個の独立した候補回答を生成し、何らかの評価基準に基づいて最良の1つを選択する手法である。Rejection Sampling（棄却サンプリング）とも呼ばれる。テスト時計算を増やす最もシンプルかつ効果的な方法の一つであり、2023年以降のLLMアライメント研究やコード生成タスクで広く活用されている。
基本アルゴリズム
Best-of-Nサンプリングの手順は以下の通りである：
- 入力プロンプト$x$をLLMに与え、温度パラメータ$T > 0$でN個の候補 $y_1, y_2, ..., y_N$ を独立に生成する
- 報酬モデル$R(x, y)$で各候補にスコアを付与する
- 最高スコアの候補$y^* = \arg\max_i R(x, y_i)$を最終出力として返す
温度パラメータの選択が重要であり、低すぎると候補の多様性が失われ、高すぎると低品質な候補が増える。一般的には$T = 0.7 \sim 1.0$が推奨される。
N値と性能の関係
| N値 | 計算コスト倍率 | MATH改善幅 | HumanEval改善幅 | 実用性 |
|---|---|---|---|---|
| 1 | 1x | 基準 | 基準 | 通常推論 |
| 4 | 4x | +8〜12% | +10〜15% | 推奨最小値 |
| 16 | 16x | +15〜22% | +20〜28% | コスト効率の最適点 |
| 64 | 64x | +20〜28% | +25〜35% | 研究用途向け |
| 256 | 256x | +22〜30% | +28〜38% | 収穫逓減が顕著 |
性能向上は$\log(N)$にほぼ比例するため、Nを4倍にしても改善幅は約2倍にしかならない。コスト効率の観点から、N=16〜32が実用的な最適値とされる。
報酬モデルの選択
Best-of-Nの性能は報酬モデルの品質に大きく依存する。
Outcome Reward Model（ORM）:
- 最終回答の正誤のみを評価する
- 訓練が容易でデータ効率が高い
- 推論過程の質は評価できない
Process Reward Model（PRM）:
- 推論の各ステップを段階的に評価する
- ORM比で10〜20%の精度向上が見込める
- 訓練データの作成コストが高い
Self-Evaluation（自己評価）:
- LLM自身に候補を評価させる
- 外部報酬モデルが不要でデプロイが簡単
- 自己バイアスの影響を受けやすい
ヒューリスティクス:
- コード実行テスト（コード生成タスク）
- 形式チェック（構造化出力タスク）
- 長さやフォーマットの検証
主要な実装と事例
| システム | N値 | 報酬モデル | タスク | 結果 |
|---|---|---|---|---|
| AlphaCode | 1,000,000 | クラスタリング+フィルタ | 競技プログラミング | Codeforces上位54% |
| AlphaCode 2 | 10,000 | Gemini Pro評価 | 競技プログラミング | Codeforces上位15% |
| Anthropic BoN | 16〜256 | Constitutional AI RM | 安全性アライメント | 有害出力90%削減 |
| CodeT | 100 | テストケース実行 | コード生成 | HumanEval 65.8%→85.2% |
Self-Consistencyとの関係
Self-Consistency（自己整合性）はBest-of-Nの特殊ケースであり、報酬モデルの代わりに多数決（Majority Voting）を使用する。
- 各候補から最終回答を抽出し、最も頻出する回答を選択する
- 報酬モデルが不要であり、追加の訓練コストがかからない
- 数学やクイズなど、離散的な正解が存在するタスクで特に有効
- 連続的な出力（文章生成、要約）には適用が難しい
コスト最適化テクニック
- Speculative Rejection: 途中まで生成した候補を報酬モデルで早期評価し、明らかに低品質なものを途中で打ち切る
- Adaptive N: 問題の難易度に応じてNを動的に調整する。簡単な問題ではN=4、難問ではN=64など
- バッチ推論: N個の候補を並列バッチで生成し、レイテンシを最小化する。vLLMのContinuous Batchingが有効
- KVキャッシュ共有: 同じプロンプトのKVキャッシュを共有し、候補生成のメモリ効率を向上させる
よくある質問（FAQ）
Q1: Best-of-NとBeam Searchの違いは何か？ A: Best-of-Nは完全な候補回答をN個独立に生成してから最良を選ぶ。Beam Searchはトークンレベルで逐次的にビーム幅分の候補を維持しながら生成する。Best-of-Nは実装が単純で並列化しやすく、Beam Searchはトークンレベルの品質最適化に優れる。
Q2: Nはいくつに設定すべきか？ A: コスト効率の観点からN=16が推奨される。性能改善が$\log(N)$に比例するため、N=16からN=64への増加で得られる改善は、N=1からN=16への改善の約半分に留まる。予算に余裕がある場合はN=32〜64を検討する。
Q3: 報酬モデルなしでBest-of-Nを使えるか？ A: 可能である。Self-Consistency（多数決）、コード実行テスト、形式検証、あるいはLLM自身による自己評価（LLM-as-Judge）が報酬モデルの代替として使える。ただし、専用の報酬モデルに比べて選択精度は低下する傾向がある。
まとめ
- Best-of-Nサンプリングは複数候補から最良を選ぶ、最もシンプルなテスト時計算手法である
- 性能改善は$\log(N)$に比例し、N=16が実用的な最適点である
- 報酬モデルの品質がBoNの最終性能を大きく左右する
- AlphaCodeでは100万候補のBoNで競技プログラミング上位54%を達成した
- コスト最適化にはSpeculative RejectionやAdaptive Nが有効である