論文の概要: Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models

• arxiv url: http://arxiv.org/abs/2411.19477v2
• Date: Fri, 07 Feb 2025 07:08:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-10 14:54:44.284551
• Title: Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models
• Title（参考訳）: 大規模言語モデルのテスト時間計算のための単純かつ予測可能なスケーリング法則
• Authors: Yanxi Chen, Xuchen Pan, Yaliang Li, Bolin Ding, Jingren Zhou,
• Abstract要約: 大規模言語モデルのテスト時間計算のための2つの原理的アルゴリズムを提案する。 理論的には、1つのアルゴリズムの故障確率は、そのテスト時間計算が大きくなるにつれて指数関数的に減衰する。
• 参考スコア（独自算出の注目度）: 70.07661254213181
• License:
• Abstract: We propose two simple yet principled algorithms that enjoy provable scaling laws for the test-time compute of large language models (LLMs), which require a black-box LLM and nothing else (e.g., no external verifier or reward model) for a minimalistic implementation. (i) The first one is a two-stage knockout-style algorithm: given an input problem, it first generates multiple candidate solutions, and then aggregate them for a final output, via a knockout tournament where pairwise comparisons among the candidates are conducted. Assuming that the LLM can generate a correct solution with non-zero probability and do better than a random guess in comparing a pair of correct and incorrect solutions, we prove theoretically that the failure probability of this algorithm decays to zero exponentially or by a power law (depending on the specific way of scaling) as its test-time compute grows. (ii) The second one is a two-stage league-style algorithm, where each candidate solution is evaluated by its average win rate against multiple opponents, rather than eliminated upon loss to a single opponent. Under certain technical assumptions that are analogous to but more robust than those required by the knockout-style algorithm, we prove theoretically that the failure probability of the league-style algorithm also decays to zero exponentially as its test-time compute grows. Through extensive experiments with two challenging benchmarks, namely GPQA and MMLU-Pro, we validate the proposed theories and demonstrate the outstanding scaling properties of both algorithms.
• Abstract（参考訳）: 我々は,大規模言語モデル(LLM)のテスト時間計算における証明可能なスケーリング法則を享受する,単純だが原則化された2つのアルゴリズムを提案する。 一 第一に、2段階ノックアウト方式のアルゴリズムで、入力問題を与えられた場合、まず複数の候補解を生成し、次に各候補のペア比較を行うノックアウトトーナメントを介して最終出力に集約する。 LLMが正解をゼロでない確率で生成でき、正解と誤解の比較においてランダムな推測よりも優れていると仮定すると、このアルゴリズムの故障確率は指数関数的にゼロになるか、テスト時間計算が大きくなるにつれて(スケーリングの特定の方法に依存する)電力法則によって崩壊する。 (二)二段リーグ方式のアルゴリズムで、各候補の解は、各相手に対する平均勝利率で評価される。 ノックアウト型アルゴリズムと類似するが、より堅牢な特定の技術的仮定の下では、このリーグ型アルゴリズムの故障確率は、テスト時間計算が増加するにつれて指数関数的に低下する。 GPQA と MMLU-Pro という2つの挑戦的ベンチマークによる広範な実験を通じて,提案した理論を検証し,両アルゴリズムの優れたスケーリング特性を実証する。

関連論文リスト

• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
  我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。 このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
  論文  参考訳（メタデータ） (2021-09-14T11:12:32Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Faster Matchings via Learned Duals [31.61057940283721]
  機械学習予測のアイデアと「スタート・ウォーム」原始二元アルゴリズムのアイデアを組み合わせる。 まず、予測可能な双対は実現不可能である可能性があるので、予測できない双対を近くの実現可能な解に効率的にマッピングするアルゴリズムを提供する。 第二に、一度双対が実現可能ならば、それらは最適ではないかもしれない。
  論文  参考訳（メタデータ） (2021-07-20T21:11:09Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Sparse Hashing for Scalable Approximate Model Counting: Theory and Practice [36.8421113576893]
  n 変数上の CNF 式 F が与えられたとき、モデルカウントや #SAT の問題は F の満足な割り当ての数を計算することである。 近年,効率的なアルゴリズム技術開発への取り組みが急増している。
  論文  参考訳（メタデータ） (2020-04-30T11:17:26Z)
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives [10.291482850329892]
  混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。 数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。 さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
  論文  参考訳（メタデータ） (2020-01-17T18:47:02Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。