論文の概要: Global Resolution: Optimal Multi-Draft Speculative Sampling via Convex Minimization

• arxiv url: http://arxiv.org/abs/2511.15898v1
• Date: Wed, 19 Nov 2025 21:59:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-21 17:08:52.384499
• Title: Global Resolution: Optimal Multi-Draft Speculative Sampling via Convex Minimization
• Title（参考訳）: グローバルレゾリューション:凸最小化による最適マルチドラフト投機サンプリング
• Authors: Rahul Krishna Thomas, Arka Pal,
• Abstract要約: 1つのドラフトモデルから$n$トークンが選択されたとき、最適な投機的サンプリングのためのアルゴリズムを考案する。 提案手法は,生成トークン当たり90%の受信と100ミリ秒未満のオーバーヘッドで,ターゲットモデル分布から無視できないずれを生じさせるマルチドラフトアルゴリズムである。
• 参考スコア（独自算出の注目度）: 1.2674961594128336
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Speculative sampling reduces the latency of autoregressive decoding for target model LLMs without sacrificing inference quality, by using a cheap draft model to suggest a candidate token and a verification criterion to accept or resample this token. To improve acceptance and decoding efficiency, recent work has explored the multi-draft extension, where at each step $n$ draft tokens are generated, and the verification criterion is a distribution conditioned on these. When this criterion maximizes the probability of accepting some draft token, it is called the optimal transport (OT). However, finding the OT is difficult, as it is the solution of a linear program (OTLP) in over $V^n$ variables, with $V$ being the vocabulary size. Two recent theoretical works have reframed the OTLP in terms of importance sampling or subset selection. In this work, we prove that these formulations are equivalent to an exponentially large relaxed OTLP, so it remains infeasible to solve. Then, we reverse engineer subset selection to formulate the OTLP as a max-flow problem. With a novel application of polymatroid theory, we reduce the exponentially large OTLP to a convex optimization problem in at most $V$ variables. This allows us to devise an algorithm for optimal $n$-draft speculative sampling when the $n$ tokens are chosen i.i.d. from a single draft model, which can be tuned to arbitrary accuracy. Finally, we measure acceptance rates and algorithm runtimes for various $n$ and top-$k$ draft sampling settings. Our findings give the first multi-draft algorithm with 90% acceptance and under 100 ms of overhead per generated token with negligible deviation from the target model distribution.
• Abstract（参考訳）: 投機的サンプリングは、安価なドラフトモデルを用いて候補トークンと検証基準を提案することにより、推論品質を犠牲にすることなく、ターゲットモデルLLMの自己回帰復号のレイテンシを低減する。 受け入れと復号効率を向上させるため、最近の研究では、各ステップ$n$ドラフトトークンが生成されるマルチドラフト拡張について検討し、検証基準はこれらに条件付き分布である。 この基準がドラフトトークンを受け入れる確率を最大化するならば、最適な輸送(OT)と呼ばれる。 しかし、OTの発見は、$V^n$変数以上の線形プログラム(OTLP)の解であり、$V$は語彙サイズであるので困難である。 最近の2つの理論的研究は、重要なサンプリングやサブセットの選択の観点からOTLPを再編成している。 本研究では,これらの定式化が指数関数的に大きく緩和されたOTLPと等価であることを証明する。 そこで我々は,OTLPを最大フロー問題として定式化するために,サブセット選択をリバースエンジニアリングする。 ポリマトロイド理論の新たな応用により、少なくとも$V$変数において指数関数的に大きいOTLPを凸最適化問題に還元する。 これにより、1つのドラフトモデルから$n$トークンが選択されたとき、最適な$n$-draft投機サンプリングのためのアルゴリズムを考案できる。 最後に、様々な$n$とトップ$k$のドラフトサンプリング設定に対する受け入れ率とアルゴリズムランタイムを測定します。 提案手法は,生成トークン当たり90%の受信と100ミリ秒未満のオーバーヘッドで,ターゲットモデル分布から無視できないずれを生じさせるマルチドラフトアルゴリズムである。

関連論文リスト

• Foundations of Top-$k$ Decoding For Language Models [19.73575905188064]
  我々は、トップ$kの復号化を説明・一般化する理論的枠組みを開発する。 大規模な分岐に対して効率的に最適化する方法を示す。
  論文  参考訳（メタデータ） (2025-05-25T23:46:34Z)
• Towards Optimal Multi-draft Speculative Decoding [102.67837141152232]
  MDSD(Multi-Draft Speculative Decoding)は、各トークンを生成する際に、小さなドラフトモデルで複数のドラフトを生成する手法である。 本稿では、最適輸送問題の双対性について論じ、最適受容率を効率的に計算する方法を提供する。
  論文  参考訳（メタデータ） (2025-02-26T03:22:44Z)
• Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression [4.396860522241307]
  疎線形回帰の効率的な学習アルゴリズムは, 負のスパイクを持つスパースPCA問題を解くのに有効であることを示す。 我々は,低次および統計的クエリの低い境界を減らしたスパース問題に対して補う。
  論文  参考訳（メタデータ） (2024-02-21T19:55:01Z)
• SpecTr: Fast Speculative Decoding via Optimal Transport [30.18181671899423]
  このアルゴリズムはデコーディングの高速化を図り、デコードされた出力に品質劣化がないことを保証します。 提案手法は,最先端の大規模言語モデルに対して,標準的なベンチマーク上での投機的復号化よりもさらに1.37倍の高速化である2.13Xのウォールクロック高速化を実現することを実験的に実証した。
  論文  参考訳（メタデータ） (2023-10-23T17:47:34Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

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