論文の概要: Parallel Sampling via Autospeculation

• arxiv url: http://arxiv.org/abs/2511.07869v1
• Date: Wed, 12 Nov 2025 01:25:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-12 20:17:03.51333
• Title: Parallel Sampling via Autospeculation
• Title（参考訳）: 自己特定による並列サンプリング
• Authors: Nima Anari, Carlo Baronio, CJ Chen, Alireza Haqi, Frederic Koehler, Anqi Li, Thuy-Duong Vuong,
• Abstract要約: 我々は,任意の順序の自己回帰モデルと拡散モデルという2つの設定において,サンプリングを高速化するアルゴリズムを提案する。 オラクルコールを並列に発行することで、期待されるサンプリング時間を$widetildeO(n1/2)$に削減できることを示す。 我々は投機的拒絶サンプリングという新しい手法を導入する。
• 参考スコア（独自算出の注目度）: 13.643401888306398
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present parallel algorithms to accelerate sampling via counting in two settings: any-order autoregressive models and denoising diffusion models. An any-order autoregressive model accesses a target distribution $μ$ on $[q]^n$ through an oracle that provides conditional marginals, while a denoising diffusion model accesses a target distribution $μ$ on $\mathbb{R}^n$ through an oracle that provides conditional means under Gaussian noise. Standard sequential sampling algorithms require $\widetilde{O}(n)$ time to produce a sample from $μ$ in either setting. We show that, by issuing oracle calls in parallel, the expected sampling time can be reduced to $\widetilde{O}(n^{1/2})$. This improves the previous $\widetilde{O}(n^{2/3})$ bound for any-order autoregressive models and yields the first parallel speedup for diffusion models in the high-accuracy regime, under the relatively mild assumption that the support of $μ$ is bounded. We introduce a novel technique to obtain our results: speculative rejection sampling. This technique leverages an auxiliary ``speculative'' distribution~$ν$ that approximates~$μ$ to accelerate sampling. Our technique is inspired by the well-studied ``speculative decoding'' techniques popular in large language models, but differs in key ways. Firstly, we use ``autospeculation,'' namely we build the speculation $ν$ out of the same oracle that defines~$μ$. In contrast, speculative decoding typically requires a separate, faster, but potentially less accurate ``draft'' model $ν$. Secondly, the key differentiating factor in our technique is that we make and accept speculations at a ``sequence'' level rather than at the level of single (or a few) steps. This last fact is key to unlocking our parallel runtime of $\widetilde{O}(n^{1/2})$.
• Abstract（参考訳）: 我々は,任意の順序自己回帰モデルと拡散モデルという2つの設定において,サンプリングを高速化する並列アルゴリズムを提案する。 任意の順序自己回帰モデルは、条件境界を提供するオラクルを通して、ターゲット分布に$μ$ on $[q]^n$をアクセスし、一方、デノナイズ拡散モデルは、ガウス雑音の下で条件平均を提供するオラクルを介して、ターゲット分布に$μ$ on $\mathbb{R}^n$をアクセスする。 標準的なシーケンシャルサンプリングアルゴリズムは、どちらも$μ$からサンプルを生成するのに$\widetilde{O}(n)$時間を必要とする。 オラクルコールを並列に発行することで、期待されるサンプリング時間を$\widetilde{O}(n^{1/2})$に削減できることを示す。 これにより、任意の階自己回帰モデルに対する以前の$\widetilde{O}(n^{2/3})$boundが改善され、$μ$のサポートが有界であるという比較的穏やかな仮定の下で、高精度な状態における拡散モデルに対する最初の並列スピードアップが得られる。 我々は投機的拒絶サンプリングという新しい手法を導入する。 この手法は補助的な `speculative'' 分布~$ν$ を利用してサンプリングを加速する。 提案手法は, 大規模言語モデルで広く普及している「投機的復号化」技術に着想を得たものであるが, キーとなる方法が異なる。 まず、'`autospeculation,' を使い、—$μ$ を定義する同じオラクルから$ν$ という憶測を構築します。 対照的に、投機的復号法は通常、分離され、高速だが、より正確でない ``draft'' モデル $ν$ を必要とする。 第2に,我々の技術における重要な差別化要因は,単一(あるいは少数の)ステップではなく,‘シーケンス’レベルでの推測と受け入れを行うことです。 この最後の事実は、$\widetilde{O}(n^{1/2})$の並列ランタイムをアンロックする鍵となります。

関連論文リスト

• Parallel Sampling via Counting [3.6854430278041264]
  任意の分布からのサンプリングを高速化するために並列化を用いる方法を示す。 我々のアルゴリズムは、$O(n2/3cdot operatornamepolylog(n,q))$ parallel timeである。 この結果は自己回帰モデルにおけるサンプリングに影響を及ぼす。
  論文  参考訳（メタデータ） (2024-08-18T11:42:54Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)

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

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