# Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity

arXiv: https://arxiv.org/abs/2405.15986 · HTML: https://mlsanity.com/paper/2405.15986/

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 110 of its 142 references that are in the map.
- First posted on arXiv 24 May 2024.

## Placed in

- Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/)

## Builds on (most cited first, 30 of 110)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [Denoising Diffusion Implicit Models](https://mlsanity.com/paper/2010.02502/) (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)
- [Hierarchical Text-Conditional Image Generation with CLIP Latents](https://mlsanity.com/paper/2204.06125/) (2022)
- [Flow Matching for Generative Modeling](https://mlsanity.com/paper/2210.02747/) (2022)
- [Zero-Shot Text-to-Image Generation](https://mlsanity.com/paper/2102.12092/) (2021)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Flow Straight and Fast: Learning to Generate and Transfer Data with Rectified Flow](https://mlsanity.com/paper/2209.03003/) (2022)
- [Elucidating the Design Space of Diffusion-Based Generative Models](https://mlsanity.com/paper/2206.00364/) (2022)
- [Video Diffusion Models](https://mlsanity.com/paper/2204.03458/) (2022)
- [DPM-Solver: A Fast ODE Solver for Diffusion Probabilistic Model Sampling in Around 10 Steps](https://mlsanity.com/paper/2206.00927/) (2022)
- [SDEdit: Guided Image Synthesis and Editing with Stochastic Differential Equations](https://mlsanity.com/paper/2108.01073/) (2021)
- [Consistency Models](https://mlsanity.com/paper/2303.01469/) (2023)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [Cascaded Diffusion Models for High Fidelity Image Generation](https://mlsanity.com/paper/2106.15282/) (2021)
- [Diffusion Models: A Comprehensive Survey of Methods and Applications](https://mlsanity.com/paper/2209.00796/) (2022)
- [Diffusion-LM Improves Controllable Text Generation](https://mlsanity.com/paper/2205.14217/) (2022)
- [Building Normalizing Flows with Stochastic Interpolants](https://mlsanity.com/paper/2209.15571/) (2022)
- [Stochastic Interpolants: A Unifying Framework for Flows and Diffusions](https://mlsanity.com/paper/2303.08797/) (2023)
- [DPM-Solver++: Fast Solver for Guided Sampling of Diffusion Probabilistic Models](https://mlsanity.com/paper/2211.01095/) (2022)
- [SiT: Exploring Flow and Diffusion-based Generative Models with Scalable Interpolant Transformers](https://mlsanity.com/paper/2401.08740/) (2024)
- [On Distillation of Guided Diffusion Models](https://mlsanity.com/paper/2210.03142/) (2022)
- [Pseudo Numerical Methods for Diffusion Models on Manifolds](https://mlsanity.com/paper/2202.09778/) (2022)
- [Maximum Likelihood Training of Score-Based Diffusion Models](https://mlsanity.com/paper/2101.09258/) (2021)
- [Diffusion Schr"odinger Bridge with Applications to Score-Based Generative Modeling](https://mlsanity.com/paper/2106.01357/) (2021)
- [Argmax Flows and Multinomial Diffusion: Learning Categorical Distributions](https://mlsanity.com/paper/2102.05379/) (2021)
- [MultiDiffusion: Fusing Diffusion Paths for Controlled Image Generation](https://mlsanity.com/paper/2302.08113/) (2023)
- [Fast Sampling of Diffusion Models with Exponential Integrator](https://mlsanity.com/paper/2204.13902/) (2022)

## Built on by (most cited first, 30 of 42)

- [How to build a consistency model: Learning flow maps via self-distillation](https://mlsanity.com/paper/2505.18825/) (2025)
- [3D and 4D World Modeling: A Survey](https://mlsanity.com/paper/2509.07996/) (2025)
- [A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Models](https://mlsanity.com/paper/2408.02320/) (2024)
- [How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Framework](https://mlsanity.com/paper/2410.03601/) (2024)
- [Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms](https://mlsanity.com/paper/2502.00234/) (2025)
- [Accelerated Diffusion Models via Speculative Sampling](https://mlsanity.com/paper/2501.05370/) (2025)
- [Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel](https://mlsanity.com/paper/2406.00924/) (2024)
- [Provable Acceleration for Diffusion Models under Minimal Assumptions](https://mlsanity.com/paper/2410.23285/) (2024)
- [Distributional Diffusion Models with Scoring Rules](https://mlsanity.com/paper/2502.02483/) (2025)
- [Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis](https://mlsanity.com/paper/2410.02321/) (2024)
- [Instance-dependent Convergence Theory for Diffusion Models](https://mlsanity.com/paper/2410.13738/) (2024)
- [On the Feature Learning in Diffusion Models](https://mlsanity.com/paper/2412.01021/) (2024)
- [Solving Inverse Problems via Diffusion-Based Priors: An Approximation-Free Ensemble Sampling Approach](https://mlsanity.com/paper/2506.03979/) (2025)
- [Lipschitz-Guided Design of Interpolation Schedules in Generative Models](https://mlsanity.com/paper/2509.01629/) (2025)
- [Generalised Flow Maps for Few-Step Generative Modelling on Riemannian Manifolds](https://mlsanity.com/paper/2510.21608/) (2025)
- [Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation](https://mlsanity.com/paper/2505.03983/) (2025)
- [Assessing the Quality of Denoising Diffusion Models in Wasserstein Distance: Noisy Score and Optimal Bounds](https://mlsanity.com/paper/2506.09681/) (2025)
- [Measurement Score-Based Diffusion Model](https://mlsanity.com/paper/2505.11853/) (2025)
- [Two-Steps Diffusion Policy for Robotic Manipulation via Genetic Denoising](https://mlsanity.com/paper/2510.21991/) (2025)
- [Predictability Enables Parallelization of Nonlinear State Space Models](https://mlsanity.com/paper/2508.16817/) (2025)
- [Sublinear iterations can suffice even for DDPMs](https://mlsanity.com/paper/2511.04844/) (2025)
- [High-accuracy and dimension-free sampling with diffusions](https://mlsanity.com/paper/2601.10708/) (2026)
- [Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models](https://mlsanity.com/paper/2412.07435/) (2024)
- [Parallel Sampling via Autospeculation](https://mlsanity.com/paper/2511.07869/) (2025)
- [Accelerating Discrete Diffusion Models with Parallel-In-Time Sampling](https://mlsanity.com/paper/2607.00773/) (2026)
- [Elucidating Rectified Flow with Deterministic Sampler: Polynomial Discretization Complexity for Multi and One-step Models](https://mlsanity.com/paper/2508.08735/) (2025)
- [On Efficiency-Effectiveness Trade-off of Diffusion-based Recommenders](https://mlsanity.com/paper/2510.17245/) (2025)
- [Steering Dynamical Regimes of Diffusion Models by Breaking Detailed Balance](https://mlsanity.com/paper/2602.15914/) (2026)
- [Ergodic Generative Flows](https://mlsanity.com/paper/2505.03561/) (2025)
- [Accelerating Speculative Diffusions via Block Verification](https://mlsanity.com/paper/2606.13426/) (2026)

## Abstract (arXiv)

Diffusion models have become a leading method for generative modeling of both image and scientific data. As these models are costly to train and evaluate, reducing the inference cost for diffusion models remains a major goal. Inspired by the recent empirical success in accelerating diffusion models via the parallel sampling technique~citeshih2024parallel, we propose to divide the sampling process into O(1) blocks with parallelizable Picard iterations within each block. Rigorous theoretical analysis reveals that our algorithm achieves widetildeO(poly log d) overall time complexity, marking the first implementation with provable sub-linear complexity w.r.t. the data dimension d. Our analysis is based on a generalized version of Girsanov's theorem and is compatible with both the SDE and probability flow ODE implementations. Our results shed light on the potential of fast and efficient sampling of high-dimensional data on fast-evolving modern large-memory GPU clusters.