論文の概要: A Simple and Provable Scaling Law for the Test-Time Compute of Large Language Models
- arxiv url: http://arxiv.org/abs/2411.19477v1
- Date: Fri, 29 Nov 2024 05:29:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-02 15:23:13.215641
- Title: A Simple and Provable Scaling Law for the Test-Time Compute of Large Language Models
- Title（参考訳）: 大規模言語モデルのテスト時間計算のための簡易かつ予測可能なスケーリング法
- Authors: Yanxi Chen, Xuchen Pan, Yaliang Li, Bolin Ding, Jingren Zhou,
- Abstract要約: 大規模言語モデル(LLM)のテスト時間計算において、証明可能なスケーリング法則を享受する一般二段階アルゴリズムを提案する。
入力問題を前提として,提案アルゴリズムはまず$N$の候補解を生成し,その後,複数ラウンドのノックアウトトーナメントによって最適な解を選択する。
理論的には、提案アルゴリズムの失敗確率は、$N$と$K$に対して指数関数的に崩壊する。
- 参考スコア（独自算出の注目度）: 70.07661254213181
- License:
- Abstract: We propose a general two-stage algorithm that enjoys a provable scaling law for the test-time compute of large language models (LLMs). Given an input problem, the proposed algorithm first generates $N$ candidate solutions, and then chooses the best one via a multiple-round knockout tournament where each pair of candidates are compared for $K$ times and only the winners move on to the next round. In a minimalistic implementation, both stages can be executed with a black-box LLM alone and nothing else (e.g., no external verifier or reward model), and a total of $N \times (K + 1)$ highly parallelizable LLM calls are needed for solving an input problem. Assuming that a generated candidate solution is correct with probability $p_{\text{gen}} > 0$ and a comparison between a pair of correct and incorrect solutions identifies the right winner with probability $p_{\text{comp}} > 0.5$ (i.e., better than a random guess), we prove theoretically that the failure probability of the proposed algorithm decays to zero exponentially with respect to $N$ and $K$: $$\mathbb{P}(\text{final output is incorrect}) \le (1 - p_{\text{gen}})^N + \lceil \log_2 N \rceil e^{-2 K (p_{\text{comp}} - 0.5)^2}.$$ Our empirical results with the challenging MMLU-Pro benchmark validate the technical assumptions, as well as the efficacy of the proposed algorithm and the gains from scaling up its test-time compute.
- Abstract（参考訳）: 本稿では,大規模言語モデル(LLM)のテスト時間計算において,証明可能なスケーリング法則を享受する一般2段階アルゴリズムを提案する。
入力問題が発生した場合、提案アルゴリズムはまずN$の候補解を生成し、次に、各候補をK$で比較し、勝者のみが次のラウンドに進む多重ラウンドノックアウトトーナメントを介して最良の解を選択する。
最小限の実装では、両方のステージはブラックボックス LLM だけで実行でき、入力問題を解決するには外部検証や報酬モデルが不要で、合計$N \times (K + 1)$高並列化可能な LLM コールが必要である。
生成された候補解が確率 $p_{\text{gen}} > 0$ で正しいと仮定すると、正解と誤解のペアの比較により、確率 $p_{\text{comp}} > 0.5$ が確率 $p_{\text{comp}} > 0.5$ (つまり、ランダムな推測よりも良い) で正解であることが証明される。
挑戦的なMMLU-Proベンチマークによる実証的な結果から,提案アルゴリズムの有効性と,テスト時間計算のスケールアップによるメリットを検証した。
関連論文リスト
- Sample-Optimal Locally Private Hypothesis Selection and the Provable
Benefits of Interactivity [8.100854060749212]
本研究では,局所的な差分プライバシーの制約下での仮説選択の問題について検討する。
我々は$varepsilon$-locally-differentially-private ($varepsilon$-LDP)アルゴリズムを考案し、$Thetaleft(fracklog kalpha2min varepsilon2,1 right)$を使って$d_TV(h,hatf)leq alpha + 9 min_fin MathcalFを保証する。
論文 参考訳（メタデータ） (2023-12-09T19:22:10Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - A Spectral Approach to Item Response Theory [6.5268245109828005]
本稿では,Raschモデルに対する新しい項目推定アルゴリズムを提案する。
我々のアルゴリズムの中核は、アイテム-イムグラフ上で定義されたマルコフ連鎖の定常分布の計算である。
合成および実生活データセットの実験により、我々のアルゴリズムは、文献でよく使われている手法とスケーラブルで正確で競合することを示した。
論文 参考訳（メタデータ） (2022-10-09T18:57:08Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Clustering with Queries under Semi-Random Noise [13.817228853960655]
一般半ランダム雑音を許容する頑健な学習法を開発した。
理論的には$Oleft(fracnk log n (1-2p)2right)$ query suffice to learn any cluster of enough large size。
論文 参考訳（メタデータ） (2022-06-09T16:02:00Z) - Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。
このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
論文 参考訳（メタデータ） (2021-09-14T11:12:32Z) - A New Minimax Theorem for Randomized Algorithms [1.2284934135116514]
新しいタイプのミニマックス定理を導入し、全てのバイアスレベルに一度に作用するハード分布の$mu$を提供する。
ランダム化クエリの複雑性,ランダム化通信の複雑性,近似度数,近似対数に対して有効であることを示す。
また、Impagliazzoのハードコアの改良版も証明した。
論文 参考訳（メタデータ） (2020-02-25T11:46:08Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。