テスト時コンピュートの戦略的スケーリング：バンディット学習アプローチ

要旨: テスト時の計算量（test-time compute）をスケールすることは、大規模言語モデルの性能を向上させるための効果的な戦略として注目されている。 しかし、既存の手法は通常、すべてのクエリに対して計算量を一様に割り当てており、クエリの難しさのばらつきを見落としている。 この非効率を解決するために、我々はテスト時の計算量割り当てを新しいバンディット学習問題として定式化し、クエリの難しさをその場で推定して、それに応じて計算量を割り当てる適応的アルゴリズムを提案する。 一様な割り当てと比べて、我々のアルゴリズムは難しいクエリにはより多くの計算量を割り当てる一方で、易しいクエリの精度は維持する。 難しいクエリの中でも、我々のアルゴリズムはさらに解ける（解決可能な）インスタンスを優先するように学習し、解けないインスタンスに対する過剰な計算を効果的に減らす。 我々は理論的に、これらのアルゴリズムが一様な割り当てよりも計算効率が良くなることを証明し、数学およびコードのベンチマークで経験的にその有効性を検証する。 具体的には、MATH-500データセットで最大11.10%の性能改善（15.04%相対）、AIME25データセットで最大10.82%（14.44%相対）、LiveCodeBenchデータセットで最大11.23%の性能改善（15.29%相対）を達成する。