技術要約：LLM推論におけるリセット＆ディスカード（ReD）

問題提起

大規模言語モデル（LLM）は、検証可能なタスク（コーディング、数学、形式的証明など）において、pass@k メトリックを用いて評価されることが増えています。これは、$k$ 回の試行内で単一のインスタンスを正しく解く確率を測定するものです。多くのタスクにおいて、失敗率（$1 - \text{pass@k}$）が $k$ に対してべき乗則（すなわち $1 - \text{pass@k} \propto k^{-\alpha}$）に従って減衰するという経験的な観察結果があります。

しかし、固定されたグローバル予算（試行回数、トークン数、または米ドルで測定）を伴う実用的な推論シナリオでは、関連する目的は単一の問題に対する成功率ではなく、総リソース制約下での「ユニークな問題の解決数の期待値」、すなわち coverage@cost です。標準的な割り当てポリシーである solve-to-completion（次の問題に移る前に、単一の問題を解決するまで繰り返しサンプリングする手法）は、べき乗則に従う難易度分布の下では非効率的です。なぜなら、困難な問題は不釣り合いに多くの試行回数を消費するためであり、このポリシーは $\alpha < 1$ の場合に coverage@cost において劣線形な成長をもたらします。これにより、追加の予算が投入されても得られる解決済み問題の数が減少していくという、収穫逓減の状態が生じます。

手法：リセット＆ディスカード（ReD）

著者らは、推論プロセスを問題セットに対する幅優先探索として扱うことで、グローバルなスループットを最適化する割り当てポリシーである Reset-and-Discard (ReD) を提案しています。

ReD プロトコル

1. Reset（リセット）: 単一の問題を解決するまで固執するのではなく、システムは各問題を固定された試行回数 $\tau$（最適なケースでは $\tau=1$、つまり毎回の試行）の間試行します。
2. Discard（破棄）: もし $\tau$ 回以内の試行で問題が解決された場合、その問題は直ちにキューから削除されます。
3. Rotation（ローテーション）: $\tau$ 回の試行後も問題が解決されない場合、その問題はキューの最後尾に移動され、システムは直ちに利用可能な次の問題へと進みます。

理論的枠組み

本論文は、再生理論（renewal theory）を用いて pass@k と coverage@cost の間の数学的なマッピングを確立しています。

• 標準的なポリシー: 難易度分布が $P(p) \sim p^{\alpha-1}$ （これによりべき乗則の pass@k が導かれる）である場合、問題を解決するための試行回数の期待値 $E[T]$ は、$\alpha < 1$ の場合に発散します。その結果、coverage@cost の成長は劣線形（$\propto t^\alpha$）になります。
• ReD ポリシー: $\tau$ 回ごとにリセットすることで、問題を解決するための実効的な試行回数 $E[T_\tau]$ は、基礎となる難易度分布に関わらず有限になります。
  • $0 < \alpha < 1$ の場合、ReD は coverage@cost の成長を劣線形から線形（$\propto t$）へと変貌させます。
  • $\alpha > 1$ の場合、ReD は線形な成長を維持しつつ、標準的なポリシーよりも急峻な傾き（より高い効率）を実現します。
• 最適性: 著者らは、あらゆる難易度分布において、問題あたりの期待試行回数を最小化するための最適な戦略は、毎試行ごとにリセットすること（$\tau=1$）であることを証明しています。これは、False Negative（偽陰性）率と False Positive（偽陽性）率の和が 1 未満である限り、不完全な検証器（verifier）が存在する場合でも成立します。

スケーリング則の推論

また、本論文は、ReD の軌跡を用いることで、高コストな大規模 $k$ 評価を必要とせずに べき乗則の指数 $\alpha$ を推論できることを示しています。ReD がラウンドを通じて進行するにつれ、未解決の問題の分布はベータ分布に収束します。ラウンド間の残存問題の比率 $\langle R_n \rangle / \langle R_{n+1} - R_n \rangle$ を分析することで、$\alpha$ を線形に推定することが可能です。

主な貢献

1. メトリックの接続: pass@k のべき乗則挙動（$0 < \alpha < 1$）がいかにして標準的な割り当てスキームにおける劣線形な成長を引き起こすかを特徴づけ、pass@k から coverage@cost への正確なマッピングを導出しました。
2. ReD アルゴリズム: リセット＆ディスガード戦略の最適性を提案・証明しました。これは、$\alpha < 1$ の場合に coverage@cost の線形な成長を保証し、$\alpha > 1$ の場合には効率を向上させます。
3. 理論的保証: ReD が、あらゆる難易度分布に対して試行あたりの期待報酬を厳密に最大化すること、および検証器のノイズに対して堅牢であることを証明しました。
4. 指数の推論: コストのかかる大規模 $k$ サンプリングを回避し、ReD の実行から直接、推論スケーリング指数を推定する手法を開発しました。
5. 実証的検証: 3 つの LLM（Llama-3.1-8b, Llama-3.3-70b, GPT-oss-20b）と 3 つのベンチマーク（HumanEval, GSM8K, MMLU-Pro）にわたって大幅な改善を実証しました。

実験結果

実験は、HumanEval（コーディング）、GSM8K（数学）、MMLU-Pro（推論）のデータセットに対して行われました。

• 効率性: ReD は、target coverage に到達するために必要な試行回数、トークン数、および USD コストを、solve-to-completion と比較して大幅に削減しました。
• モデル比較: HumanEval ベンチマークにおいて、ReD を適用した小規模モデル（Llama-3.1-8b）は、約 90% の coverage に達するまでの試行回数およびトークン数の観点で、より大規模なモデル（Llama-3.3-70b）の標準的な割り当てを上回りました。USD コストの観点では、ReD を適用した 8b モデルが、すべての coverage レベルにおいて最も費用対効果の高い戦略でした。
• スケーリング則の推論: 8b モデルを用いた ReD により、著者らは高 $k$ の pass@k 測定から導出された指数と一致する $\alpha \approx 0.34$ というべき乗則の指数を正常に推論しました。
• 堅牢性: ノイズのある検証器をシミュレートした場合でも、ReD の優位性は維持されました。

意義と主張

本論文は、ReD が検証可能なタスクにおける推論計算の割り当て方を根本的に変えるものであると主張しています。

• 「ペイ・パー・トークン」から「アウトカム・アズ・ア・サービス」へ: ReD は、システムが（収穫逓減を伴う困難なインスタンスにリソースを浪費するのではなく）「学習可能性の境界」（数回の試行で解決可能な問題）に計算リソースを集中させることを可能にします。
• 階層的ルーティング: この手法は、小規模モデルが ReD を通じて大半の問題を処理し、未解決の問題のみをより大規模なモデルにルーティングするという、効率的なハイブリッド戦略をサポートします。
• 汎用的な適用可能性: このアプローチは、繰り返しサンプリングと検証をサポートするあらゆるパイプラインに適用可能であり、モデルのアーキテクチャや学習を変更することなく、スループットの証明可能な向上を提供します。

著者らは、ReD が検証可能なタスク（解の正当性が自動的に評価できるタスク）に特化して設計されていることを強調し、その範囲について謙虚な姿勢を保っています。彼らは、非検証可能な生成タスクへの適用可能性を主張したり、学習された難易度予測器との統合を本研究の提案として行うものではありません。