Lune

STOC2026Top-tier venue

Parallel Sampling via Autospeculation

Nima Anari, Carlo Baronio, CJ Chen, Alireza Haqi, Frederic Koehler, Anqi Li, Thuy-Duong Vuong

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 [๐‘ž] ๐‘› through an oracle that provides conditional marginals, while a denoising diffusion model accesses a target distribution ๐œ‡ on โ„ ๐‘› through an oracle that provides conditional means under Gaussian noise. Standard sequential sampling algorithms require ๐‘‚(๐‘›) 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 ๐‘‚(๐‘› 1/2 ). This improves the previous ๐‘‚(๐‘› 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 ๐‘‚(๐‘› 1/2 ).

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper ยท the top-tier papers that cite it ยท related work

Get the answer

Free to start. No credit card required.

Lineage

  • Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization cites The probability flow ODE is provably fast
  • Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization cites Denoising Diffusion Probabilistic Models
  • Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization cites Score-Based Generative Modeling through Stochastic Differential Equations
  • The probability flow ODE is provably fast cites Denoising Diffusion Probabilistic Models
  • The probability flow ODE is provably fast cites Score-Based Generative Modeling through Stochastic Differential Equations
  • Lookahead Path Likelihood Optimization for Diffusion LLMs cites Language Models are Few-Shot Learners
  • Lookahead Path Likelihood Optimization for Diffusion LLMs cites Denoising Diffusion Probabilistic Models
  • Score-Based Generative Modeling through Stochastic Differential Equations cites Denoising Diffusion Probabilistic Models
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Lookahead Path Likelihood Optimization for Diffusion LLMsXuejie Liu, Vit Chun Yap, Yitao Liang, Anji LiuICML 2026 ยท 1 citation

Builds on15

  1. Language Models are Few-Shot LearnersTom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah et al.NeurIPS 2020 ยท 64,255 citations
  2. Denoising Diffusion Probabilistic ModelsJonathan Ho, Ajay Jain, Pieter AbbeelNeurIPS 2020 ยท 35,902 citations
  3. Score-Based Generative Modeling through Stochastic Differential EquationsYang Song, Jascha Sohl-Dickstein, Diederik P. Kingma, Abhishek Kumar et al.ICLR 2021 ยท 1,270 citations
  4. Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic LocalizationJoe Benton, Valentin De Bortoli, Arnaud Doucet, George DeligiannidisICLR 2024 ยท 203 citations
  5. The probability flow ODE is provably fastSitan Chen, Sinho Chewi, Holden Lee, Yuanzhi Li et al.NeurIPS 2023 ยท 179 citations

Related papers

  1. Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Auto SpeculationHengyuan Hu, Aniket Das, Dorsa Sadigh, Nima AnariICML 2025
  2. Accelerated Diffusion Models via Speculative SamplingValentin De Bortoli, Alexandre Galashov, Arthur Gretton, Arnaud DoucetICML 2025
  3. Parallel Sampling via CountingNima Anari, Ruiquan Gao, Aviad RubinsteinSTOC 2024 ยท 2 citations
  4. Accelerating Diffusion LLMs via Adaptive Parallel DecodingDaniel Israel, Guy Van den Broeck, Aditya GroverNeurIPS 2025 ยท 114 citations
  5. DFlash: Block Diffusion for Flash Speculative DecodingJian Chen, Yesheng Liang, Zhijian LiuICML 2026
Dusk over the sea between two cliffs drawn in fine vertical lines