# Parallel Sampling via Autospeculation arXiv: https://arxiv.org/abs/2511.07869 · HTML: https://mlsanity.com/paper/2511.07869/ ## Key facts - Cited by 6 papers in the map (data through 14 Oct 2026). - Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models. - Builds on 28 of its 51 references that are in the map. - First posted on arXiv 11 Nov 2025. ## Placed in - Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/) ## Builds on (most cited first, 28 of 28) - [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017) - [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018) - [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020) - [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020) - [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020) - [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015) - [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019) - [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019) - [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023) - [Pixel Recurrent Neural Networks](https://mlsanity.com/paper/1601.06759/) (2016) - [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022) - [Blockwise Parallel Decoding for Deep Autoregressive Models](https://mlsanity.com/paper/1811.03115/) (2018) - [Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization](https://mlsanity.com/paper/2308.03686/) (2023) - [The probability flow ODE is provably fast](https://mlsanity.com/paper/2305.11798/) (2023) - [Parallel Sampling of Diffusion Models](https://mlsanity.com/paper/2305.16317/) (2023) - [The Randomized Midpoint Method for Log-Concave Sampling](https://mlsanity.com/paper/1909.05503/) (2019) - [A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Models](https://mlsanity.com/paper/2408.02320/) (2024) - [Training and Inference on Any-Order Autoregressive Models the Right Way](https://mlsanity.com/paper/2205.13554/) (2022) - [Convergence Analysis for General Probability Flow ODEs of Diffusion Models in Wasserstein Distances](https://mlsanity.com/paper/2401.17958/) (2024) - [Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity](https://mlsanity.com/paper/2405.15986/) (2024) - [Sampling, Diffusions, and Stochastic Localization](https://mlsanity.com/paper/2305.10690/) (2023) - [Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel](https://mlsanity.com/paper/2406.00924/) (2024) - [Convergence of Deterministic and Stochastic Diffusion-Model Samplers: A Simple Analysis in Wasserstein Distance](https://mlsanity.com/paper/2508.03210/) (2025) - [Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation](https://mlsanity.com/paper/2505.03983/) (2025) - [Parallel Sampling via Counting](https://mlsanity.com/paper/2408.09442/) (2024) - [Non-asymptotic error bounds for probability flow ODEs under weak log-concavity](https://mlsanity.com/paper/2510.17608/) (2025) - [Sampling Arborescences in Parallel](https://mlsanity.com/paper/2012.09502/) (2020) - [Computing the permanent of (some) complex matrices](https://mlsanity.com/paper/1405.1303/) (2014) ## Built on by (most cited first, 6 of 6) - [Accelerating Speculative Diffusions via Block Verification](https://mlsanity.com/paper/2606.13426/) (2026) - [Lookahead Path Likelihood Optimization for Diffusion LLMs](https://mlsanity.com/paper/2602.03496/) (2026) - [Understanding Parallel Samplers in Masked Diffusion via Random Walks on Graphs](https://mlsanity.com/paper/2606.22976/) (2026) - [A Mathematical Introduction to Diffusion Models](https://mlsanity.com/paper/2607.01693/) (2026) - [Conditional Total Correlation and the Serial Depth of Adaptive Parallel Sampling](https://mlsanity.com/paper/2608.25505/) (2026) - [Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure](https://mlsanity.com/paper/2609.37841/) (2026) ## Abstract (arXiv) 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 ℝn through an oracle that provides conditional means under Gaussian noise. Standard sequential sampling algorithms require widetildeO(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 widetildeO(n1/2). This improves the previous widetildeO(n2/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~nu 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 nu out of the same oracle that defines~μ. In contrast, speculative decoding typically requires a separate, faster, but potentially less accurate ``draft'' model nu. 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 widetildeO(n1/2).