技術的サマリー：適応的生成・ランキング・検証

問題定式化

本論文は、大規模言語モデル（LLM）におけるコスト感受性の推論時計算リソース配分問題を扱っている。現代の推論パイプラインはしばしば「生成・ランキング・検証」というパラダイムを採用する：LLM が複数の候補解を生成し、安価だがノイズの多い報酬モデルがそれらをランキングし、高価な検証器（例：コードにおける非公開テストの実行、または数学における正解の完全一致）が上位候補を検証する。

核心的な課題は、計算リソース（生成数対検証数）の最適配分がプロンプト依存である点にある。固定ポリシー（例、$N_{rew}$ サンプルを生成し、上位 $N_{ver}$ を検証する）は非効率的である：簡単なプロンプトでは過剰なコストを費やし、難しいプロンプトでは不足する。著者らはこれを能動探索として定式化する。これは、ポリシーが適応的に以下の操作を行う逐次意思決定問題である：

1. 候補を生成し、その報酬スコアを観測する（コスト $c_{rew}$）。
2. 選択された候補を検証し、真のラベルを取得する（コスト $c_{ver}$）。
3. 検証済みの正解が見つかるまで停止しない。

目標は、成功確率 100%（生成分布内に正解が存在する場合、それを見つけることを保証）を維持しつつ、期待総コスト $J = c_{rew}N_{rew} + c_{ver}N_{ver}$ を最小化することである。

手法

1. 分布認識ベンチマーク

著者らはまず、ポリシーが環境の完全な知識を持つと仮定することで、理論的下界を確立する：

• $D_x$：プロンプト $x$ に対する報酬スコアの分布。
• $h^*_x(r)$：条件付き成功関数。スコア $r$ を持つ候補が検証に合格する確率を表す。

定理 3.2 は、この理想化された設定における最適ポリシーを特徴づける。それは、条件付き成功確率 $h^*_x(r)$ が特定の損益分岐点閾値 $\tau^*$ を超える場合、候補を即座に検証し、そうでない場合は破棄するという閾値ルールが最適戦略であることを証明する。閾値 $\tau^*$ は、$c_{ver} \mathbb{E}[\max\{h^*(R) - \tau^*, 0\}] = \tau^* c_{rew}$ の唯一の解である。

2. ADAP アルゴリズム

実際には、$D_x$ と $h^*_x$ は未知である。著者らは、スコア分布や成功関数の事前知識を必要とせず、単調性の仮定（高い報酬スコアは、検証に合格する確率が少なくとも同等である）のみに依存するシェル単位オンラインアルゴリズムであるADAP（Adaptive Generate-Rank-Verify）を提案する。

ADAP のメカニズム：

• シェル単位探索：アルゴリズムは、サンプル数（$m$）と検証数（$k$）の二進スケーリングの「シェル」に対して探索を行う。各シェル $s$ は、コスト範囲 $[2^s c_{min}, 2^{s+1} c_{min})$ に対応する。
• 漸進的拡大：小さなシェルから開始し、ADAP は新しい候補のバッチを生成し、それらをプールに追加し、プール全体を報酬スコアでランキングする。
• 検証：プールの上位 $k$ 個の候補を検証する。正のラベルが見つかった場合は停止する。見つからなかった場合は、より大きな $m$ と $k$ を持つ次のシェルに進む。
• プールベースの効率性：未検証の候補を破棄するストリーミングポリシーとは異なり、ADAP はプールを維持する。初期シェルで生成された高報酬の候補は、まだ照会されていない場合、後続のシェルでの検証のために利用可能である。

3. 理論的保証

• 上界：単調性の仮定の下、定理 4.2 は、ADAP が分布認識最適解 $J^*$ の定数倍（具体的には $\le 400$）以内の期待コストを達成することを証明する。この保証は、すべての実行可能なプロンプトと未知の分布に対して一様に成り立つ。
• 下界と構造の必要性：著者らは、構造仮定が不可欠であることを示す。中心スター数（$s_0$）という学習理論的な複雑性尺度を用いて、定理 6.2 は、スコアとラベルの間の関係に関する仮定がない場合（すなわち、$s_0 = \infty$ の場合）、いかなる健全なオンラインポリシーも、分布認識オラクルに対して定数倍の競争比を達成できないことを示す。最悪ケースのギャップは、$\Omega(\min\{s_0, c_{ver}/c_{rew}\})$ としてスケーリングしうる。

主要な貢献

1. 定式化：生成・ランキング・検証パイプラインをコスト感受性の能動探索問題として定義し、固定プールの照会ではなくオンラインでの候補生成を必要とする点で、標準的な能動学習と区別した。
2. 最適ベンチマーク：損益分岐点の成功確率に基づく単純な閾値ルールとして、分布認識最適ポリシーを特徴づけた。
3. 適応的アルゴリズム（ADAP）：生成と検証の努力を適応的にスケーリングする実用的なオンラインアルゴリズムを提案した。単調性の下で、最適オラクルに対する証明可能な定数倍の保証を提供する。
4. 学習理論的限界：構造仮定（例えば単調性）は単なる技術的な便宜ではなく、効率的な能動探索のための根本的な要件であることを確立し、中心スター数を通じて定式化した。
5. 実証的検証：数学的推論（HMMT）と競技プログラミング（LiveCodeBench）のタスクでアプローチを検証した。

実験結果

著者らは ADAP を以下と比較評価した：

• SampleAware：各試行に対して最も安価な $(N_{rew}, N_{ver})$ を事後に選択するオラクル下界。
• DAPk：過去の通過率に基づいてプロンプトを $k$ 個の難易度クラスに分割し、それぞれに固定戦略を割り当てる難易度適応型ベースライン。
• Uniform：ADAP の平均コストに一致する固定ポリシー。

知見：

• コスト効率：実行可能なプロンプトのサブセットにおいて、ADAP は数学タスクで最良の固定ポリシーよりも平均コストが2.9 倍低く、コーディングタスクでは5.5 倍低いコストで 100% の成功率を達成した。
• DAPk との比較：ADAP は、歴史的難易度ラベルやオフライン調整を必要とせず、DAPk（$k=10$ の場合でも）と同等かそれ以上の性能を発揮した。コーディングタスクでは、DAPk は決して ADAP を上回らなかった。一方、数学タスクでは、DAPk は $k$ が十分大きく、問題ごとのオラクルを近似する場合にのみ ADAP の性能に近づいた。
• ロバスト性：生成コスト（$c_{rew}$）に対する検証コスト（$c_{ver}$）の比率が増加するにつれて、固定ポリシーに対する ADAP の優位性が増大した。

意義と主張

本論文は、推論時探索において、オンラインかつプロンプト依存の適応が、静的または歴史的に調整されたポリシーよりも優れていると主張する。能動探索として問題を扱い、報酬信号の単調性を活用することで、ADAP は特定のプロンプトの難易度に合わせ、計算リソースを動的に配分できる。

著者らは、自らの研究が以下の点を提供することを強調する：

• 証明可能な保証：基礎となる分布を知らなくても、最適コストに対する定数倍の近似を提供する。
• 実用的な効率性：高リスクの推論タスクにおける計算コスト（レイテンシ、GPU 時間、API 費用）の大幅な削減。
• 理論的必然性：効率的な探索を達成するために、報酬・検証器関係に関する構造仮定が避けられないことを示し、能動探索と能動学習理論の間のギャップを埋める。

論文は、可変コストや並列生成への拡張が将来の課題である一方、現在のフレームワークは、多様な候補を生成することと、最も有望なものを検証することの間の根本的な緊張関係に成功裏に対処していると結論づけている。