論文の概要: Foundations of Top-$k$ Decoding For Language Models

• arxiv url: http://arxiv.org/abs/2505.19371v1
• Date: Sun, 25 May 2025 23:46:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-27 16:58:43.076723
• Title: Foundations of Top-$k$ Decoding For Language Models
• Title（参考訳）: 言語モデルのための上位$デコードの基礎
• Authors: Georgy Noarov, Soham Mallick, Tao Wang, Sunay Joshi, Yan Sun, Yangxinyu Xie, Mengxin Yu, Edgar Dobriban,
• Abstract要約: 我々は、トップ$kの復号化を説明・一般化する理論的枠組みを開発する。 大規模な分岐に対して効率的に最適化する方法を示す。
• 参考スコア（独自算出の注目度）: 19.73575905188064
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Top-$k$ decoding is a widely used method for sampling from LLMs: at each token, only the largest $k$ next-token-probabilities are kept, and the next token is sampled after re-normalizing them to sum to unity. Top-$k$ and other sampling methods are motivated by the intuition that true next-token distributions are sparse, and the noisy LLM probabilities need to be truncated. However, to our knowledge, a precise theoretical motivation for the use of top-$k$ decoding is missing. In this work, we develop a theoretical framework that both explains and generalizes top-$k$ decoding. We view decoding at a fixed token as the recovery of a sparse probability distribution. We consider \emph{Bregman decoders} obtained by minimizing a separable Bregman divergence (for both the \emph{primal} and \emph{dual} cases) with a sparsity-inducing $\ell_0$ regularization. Despite the combinatorial nature of the objective, we show how to optimize it efficiently for a large class of divergences. We show that the optimal decoding strategies are greedy, and further that the loss function is discretely convex in $k$, so that binary search provably and efficiently finds the optimal $k$. We show that top-$k$ decoding arises as a special case for the KL divergence, and identify new decoding strategies that have distinct behaviors (e.g., non-linearly up-weighting larger probabilities after re-normalization).
• Abstract（参考訳）: トップ$k$デコード(Top-k$ decoding)は、LLMからサンプリングするために広く使われているメソッドである。 Top-k$や他のサンプリング手法は、真の次トーケン分布はスパースであり、ノイズの多いLLM確率は切り離さなければならないという直感に動機付けられている。 しかし、私たちの知る限りでは、トップ$k$デコードを使用するための正確な理論的動機が欠落している。 本研究では,トップ$kの復号化を説明・一般化する理論的枠組みを開発する。 固定トークンでの復号化をスパース確率分布の回復とみなす。 分離可能なブレグマン発散(emph{primal} と \emph{dual} の両方の場合)をスパース性誘導の $\ell_0$ 正規化で最小化することによって得られる \emph{Bregman decoders} を考える。 目的の組合せ性にも拘わらず,多種多様な分野に対して効率的に最適化する方法を示す。 最適復号化戦略は欲求的であり、損失関数は$k$で離散的に凸であり、二進探索が有効かつ効率的に$k$を見つけることができることを示す。 KL分散の特別な場合として上位$kの復号が生じることを示し、異なる振る舞いを持つ新しい復号戦略(例えば、再正規化後の非線型アップウェイトなより大きな確率)を同定する。

関連論文リスト

• On Next-Token Prediction in LLMs: How End Goals Determine the Consistency of Decoding Algorithms [17.98959620987217]
  クロスエントロピー損失を用いて訓練された次のトーケン予測は、ほとんどの大きな言語モデルの基礎である。 本稿では、これらのアルゴリズムのいくつかを検証し、損失関数として符号化された様々な目標に対する一貫性について検討する。
  論文  参考訳（メタデータ） (2025-05-16T12:38:45Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Theoretical limits of descending $\ell_0$ sparse-regression ML algorithms [0.0]
  本研究では,emphmaximum-likelihood (ML)デコーディングの性能解析プログラムを開発した。 ML性能パラメータの鍵となるのは、残留エンフェロ平均二乗誤差(textbfRMSE$)を発見し、いわゆるエンフェロ遷移(PT)現象を示す。 Fl RDTの具体的実装と実用的妥当性は、典型的には、基礎となる数値評価のサイズのセットを実行する能力に依存している。
  論文  参考訳（メタデータ） (2024-10-10T06:33:41Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• SpecTr: Fast Speculative Decoding via Optimal Transport [30.18181671899423]
  このアルゴリズムはデコーディングの高速化を図り、デコードされた出力に品質劣化がないことを保証します。 提案手法は,最先端の大規模言語モデルに対して,標準的なベンチマーク上での投機的復号化よりもさらに1.37倍の高速化である2.13Xのウォールクロック高速化を実現することを実験的に実証した。
  論文  参考訳（メタデータ） (2023-10-23T17:47:34Z)
• Truncation Sampling as Language Model Desmoothing [115.28983143361681]
  ニューラルネットワークモデルからのテキストの長いサンプルは、品質が劣る可能性がある。 トランケーションサンプリングアルゴリズムは、各ステップでいくつかの単語の確率を0に設定する。 本稿では,単語をエントロピーに依存した確率閾値以下に切り詰める$eta$-samplingを導入する。
  論文  参考訳（メタデータ） (2022-10-27T05:52:35Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。 我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
  論文  参考訳（メタデータ） (2022-03-18T18:50:52Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。 この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
  論文  参考訳（メタデータ） (2021-06-29T12:49:54Z)

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

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