mlsanityData to 7 Oct 2026

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

arXiv 2405.15986 ↗First posted 24 May 2024cs.LG cs.DC cs.NAcited by 42

On the map: Diffusion models → Diffusion foundations and sampling

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.

Key facts. Cited by 42 papers in the map (data through 7 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.

Builds on

110 of 142 references.

Closest ancestors · 62

Same direction, newest first

  1. 2024Learning general Gaussian mixtures with efficient score matching29 Apr
  2. 2024Learning Mixtures of Gaussians Using Diffusion Models29 Apr
  3. 2024Convergence Analysis of Probability Flow ODE for Score-based Generative Models15 Apr
  4. 2024An Overview of Diffusion Models: Applications, Guided Generation, Statistical Rates and Optimization11 Apr
  5. 2024Quantum State Generation with Structure-Preserving Diffusion Model9 Apr
  6. 2024Tutorial on Diffusion Models for Imaging and Vision26 Mar
  7. 2024Diffusion Model for Data-Driven Black-Box Optimization20 Mar
  8. 2024Multistep Consistency Models11 Mar
  9. 2024Accelerating Convergence of Score-Based Diffusion Models, Provably6 Mar
  10. 2024Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion27 Feb
  11. 2024Accelerating Parallel Sampling of Diffusion Models15 Feb
  12. 2024Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformization12 Feb
38 more
  1. 2024Convergence Analysis for General Probability Flow ODEs of Diffusion Models in Wasserstein Distances31 Jan
  2. 2024Deconstructing Denoising Diffusion Models for Self-Supervised Learning25 Jan
  3. 2024SiT: Exploring Flow and Diffusion-based Generative Models with Scalable Interpolant Transformers16 Jan
  4. 2023A Note on the Convergence of Denoising Diffusion Probabilistic Models10 Dec
  5. 2023Fast ODE-based Sampling for Diffusion Models in Around 5 Steps30 Nov
  6. 2023Closing the ODE-SDE gap in score-based diffusion models through the Fokker-Planck equation27 Nov
  7. 2023Generative Diffusion Models for Lattice Field Theory6 Nov
  8. 2023Quantum circuit synthesis with diffusion models3 Nov
  9. 2023Improved Techniques for Training Consistency Models22 Oct
  10. 2023DPM-Solver-v3: Improved Diffusion ODE Solver with Empirical Model Statistics20 Oct
  11. 2023Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Models20 Sep
  12. 2023Diffusion on the Probability Simplex5 Sep
  13. 2023Renormalizing Diffusion Models23 Aug
  14. 2023Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization7 Aug
  15. 2023Restart Sampling for Improving Generative Processes26 Jun
  16. 2023Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models15 Jun
  17. 2023Exploring the Optimal Choice for Generative Processes in Diffusion Models: Ordinary vs Stochastic Differential Equations3 Jun
  18. 2023Parallel Sampling of Diffusion Models25 May
  19. 2023Improved Convergence of Score-Based Diffusion Models via Prediction-Correction23 May
  20. 2023The probability flow ODE is provably fast19 May
  21. 2023Blackout Diffusion: Generative Diffusion Models in Discrete-State Spaces18 May
  22. 2023Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-Type Samplers6 Mar
  23. 2023Consistency Models2 Mar
  24. 2022Score-based Continuous-time Discrete Diffusion Models30 Nov
  25. 2022Fast Sampling of Diffusion Models via Operator Learning24 Nov
  26. 2022From Denoising Diffusions to Denoising Markov Models7 Nov
  27. 2022Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions3 Nov
  28. 2022DPM-Solver++: Fast Solver for Guided Sampling of Diffusion Probabilistic Models2 Nov
  29. 2022Categorical SDEs with Simplex Diffusion26 Oct
  30. 2022GENIE: Higher-Order Denoising Diffusion Solvers11 Oct
  31. 2022On Distillation of Guided Diffusion Models6 Oct
  32. 2022Convergence of score-based generative modeling for general data distributions26 Sep
  33. 2022Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions22 Sep
  34. 2022Diffusion Models: A Comprehensive Survey of Methods and Applications2 Sep
  35. 2022Convergence for score-based generative modeling with polynomial complexity13 Jun
  36. 2022DPM-Solver: A Fast ODE Solver for Diffusion Probabilistic Model Sampling in Around 10 Steps2 Jun
  37. 2022Elucidating the Design Space of Diffusion-Based Generative Models1 Jun
  38. 2022Fast Sampling of Diffusion Models with Exponential Integrator29 Apr

50 newest of 62 All 62 (JSON)

Other references · 48

  1. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,005
  2. 2022Hierarchical Text-Conditional Image Generation with CLIP Latentscited by 6,539
  3. 2022Flow Matching for Generative Modelingcited by 5,426
  4. 2021Zero-Shot Text-to-Image Generationcited by 4,276
  5. 2019Generative Modeling by Estimating Gradients of the Data Distributioncited by 4,067
  6. 2022Flow Straight and Fast: Learning to Generate and Transfer Data with Rectified Flowcited by 3,550
  7. 2022Video Diffusion Modelscited by 2,280
  8. 2021SDEdit: Guided Image Synthesis and Editing with Stochastic Differential Equationscited by 1,903
  9. 2022Diffusion-LM Improves Controllable Text Generationcited by 1,006
  10. 2022Building Normalizing Flows with Stochastic Interpolantscited by 964
  11. 2023Stochastic Interpolants: A Unifying Framework for Flows and Diffusionscited by 897
  12. 2021Argmax Flows and Multinomial Diffusion: Learning Categorical Distributionscited by 566
36 more
  1. 2023MultiDiffusion: Fusing Diffusion Paths for Controlled Image Generationcited by 529
  2. 2021Solving Inverse Problems in Medical Imaging with Score-Based Generative Modelscited by 514
  3. 2022GeoDiff: a Geometric Diffusion Model for Molecular Conformation Generationcited by 511
  4. 2024Generative Flows on Discrete State-Spaces: Enabling Multimodal Flows with Applications to Protein Co-Designcited by 294
  5. 2022Diffusion Probabilistic Modeling for Video Generationcited by 237
  6. 2021Autoregressive Diffusion Modelscited by 208
  7. 2021Symbolic Music Generation with Diffusion Modelscited by 152
  8. 2022Concrete Score Matching: Generalized Score Matching for Discrete Datacited by 144
  9. 2020Generative Modeling with Denoising Auto-Encoders and Langevin Samplingcited by 118
  10. 2022Parallel Diffusion Models of Operator and Image for Blind Inverse Problemscited by 113
  11. 2024Dirichlet Flow Matching with Applications to DNA Sequence Designcited by 110
  12. 2019Theoretical guarantees for sampling and inference in generative models with latent diffusionscited by 97
  13. 2020Interacting particle solutions of Fokker-Planck equations through gradient-log-density estimationcited by 87
  14. 2019The Randomized Midpoint Method for Log-Concave Samplingcited by 77
  15. 2023Dirichlet Diffusion Score Model for Biological Sequence Generationcited by 73
  16. 2024Provably Robust Score-Based Diffusion Posterior Sampling for Plug-and-Play Image Reconstructioncited by 73
  17. 2023The Blessing of Randomness: SDE Beats ODE in General Diffusion-based Image Editingcited by 61
  18. 2023Scalable Diffusion for Materials Generationcited by 52
  19. 2024Symbolic Music Generation with Non-Differentiable Rule Guided Diffusioncited by 52
  20. 2023Provable Probabilistic Imaging using Score-Based Generative Priorscited by 51
  21. 2022Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localizationcited by 48
  22. 2022Probability flow solution of the Fokker-Planck equationcited by 46
  23. 2023Reverse Diffusion Monte Carlocited by 41
  24. 2023Sampling, Diffusions, and Stochastic Localizationcited by 38
  25. 2018Monge-Amp`ere Flow for Generative Modelingcited by 33
  26. 2023ArchiSound: Audio Generation with Diffusioncited by 20
  27. 2023Self-Consistent Velocity Matching of Probability Flowscited by 17
  28. 2023Multimarginal generative modeling with stochastic interpolantscited by 17
  29. 2023Deep Equilibrium Diffusion Restoration with Parallel Samplingcited by 17
  30. 2023Score-based Transport Modeling for Mean-Field Fokker-Planck Equationscited by 13
  31. 2023Flow-based Distributionally Robust Optimizationcited by 13
  32. 2024Fast parallel sampling under isoperimetrycited by 12
  33. 2024Parallelized Midpoint Randomization for Langevin Monte Carlocited by 9
  34. 2023Diffusion Methods for Generating Transition Pathscited by 8
  35. 2024A score-based particle method for homogeneous Landau equationcited by 6
  36. 2023Parallelising Glauber dynamicscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 8; 2025: 24; 2026: 10.

42 papers.

Sort:

By area:

  1. 2025How to build a consistency model: Learning flow maps via self-distillationcited by 96
  2. 2024A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Modelscited by 64
  3. 20253D and 4D World Modeling: A Surveycited by 64
  4. 2024How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Frameworkcited by 48
  5. 2025Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithmscited by 47
  6. 2025Accelerated Diffusion Models via Speculative Samplingcited by 30
  7. 2024Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallelcited by 29
  8. 2024Provable Acceleration for Diffusion Models under Minimal Assumptionscited by 27
  9. 2025Distributional Diffusion Models with Scoring Rulescited by 25
  10. 2024Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysiscited by 24
  11. 2024Instance-dependent Convergence Theory for Diffusion Modelscited by 21
  12. 2024On the Feature Learning in Diffusion Modelscited by 19
30 more
  1. 2025Solving Inverse Problems via Diffusion-Based Priors: An Approximation-Free Ensemble Sampling Approachcited by 18
  2. 2025Lipschitz-Guided Design of Interpolation Schedules in Generative Modelscited by 15
  3. 2025Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculationcited by 11
  4. 2025Generalised Flow Maps for Few-Step Generative Modelling on Riemannian Manifoldscited by 10
  5. 2025Assessing the Quality of Denoising Diffusion Models in Wasserstein Distance: Noisy Score and Optimal Boundscited by 8
  6. 2025Measurement Score-Based Diffusion Modelcited by 7
  7. 2025Predictability Enables Parallelization of Nonlinear State Space Modelscited by 7
  8. 2025Two-Steps Diffusion Policy for Robotic Manipulation via Genetic Denoisingcited by 7
  9. 2025Sublinear iterations can suffice even for DDPMscited by 7
  10. 2026High-accuracy and dimension-free sampling with diffusionscited by 7
  11. 2024Parallel Simulation for Log-concave Sampling and Score-based Diffusion Modelscited by 6
  12. 2025Parallel Sampling via Autospeculationcited by 5
  13. 2025Elucidating Rectified Flow with Deterministic Sampler: Polynomial Discretization Complexity for Multi and One-step Modelscited by 3
  14. 2026Steering Dynamical Regimes of Diffusion Models by Breaking Detailed Balancecited by 3
  15. 2025Ergodic Generative Flowscited by 2
  16. 2025On Efficiency-Effectiveness Trade-off of Diffusion-based Recommenderscited by 2
  17. 2026Accelerating Speculative Diffusions via Block Verificationcited by 2
  18. 2026Accelerating Diffusion Sampling via Speculative Draft Treescited by 2
  19. 2025Ctrl-Z Sampling: Scaling Diffusion Sampling with Controlled Random Zigzag Explorationscited by 1
  20. 2026Scheduling Thoughts: Learning the Order of Thought in Diffusion Language Modelscited by 1
  21. 2026Accelerating Discrete Diffusion Models with Parallel-In-Time Samplingcited by 1
  22. 2026FluxLite: Inference-Time Proposal Control for Discrete Diffusion Modelscited by 1
  23. 2026Improved Distributional Diffusion Modelscited by 1
  24. 2025Dual-domain Multi-path Self-supervised Diffusion Model for Accelerated MRI Reconstructioncited by 0
  25. 2025Planning with Diffusion Models for Target-Oriented Dialogue Systemscited by 0
  26. 2025SAGE: Semantic-Aware Shared Sampling for Efficient Diffusioncited by 0
  27. 2025Learning Causal States Under Partial Observability and Perturbationcited by 0
  28. 2025Are First-Order Diffusion Samplers Really Slower? A Fast Forward-Value Approachcited by 0
  29. 2026ReAL: Accelerating Flow Matching through Segment Advancement with Shared Lookaheadcited by 0
  30. 2026Rank-Aware Speculative Sampling for Diffusion Draft Treescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025CHORDS: Diffusion Sampling Accelerator with Multi-core Hierarchical ODE Solvers
  2. 2024Partially Conditioned Patch Parallelism for Accelerated Diffusion Model Inference
  3. 2024DistriFusion: Distributed Parallel Inference for High-Resolution Diffusion Models
  4. 2024A Simple Early Exiting Framework for Accelerated Sampling in Diffusion Models
  5. 2026DRiffusion: Draft-and-Refine Process Parallelizes Diffusion Models with Ease
  6. 2026Accelerating Diffusion via Hybrid Data-Pipeline Parallelism Based on Conditional Guidance Scheduling
  7. 2025Diffusion Language Models are Provably Optimal Parallel Samplers
  8. 2024Self-Refining Diffusion Samplers: Enabling Parallelization via Parareal Iterations