# Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 37 of its 51 references that are in the map.
- First posted on arXiv 3 Jun 2024.

## Placed in

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

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

- [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)
- [Scaling Rectified Flow Transformers for High-Resolution Image Synthesis](https://mlsanity.com/paper/2403.03206/) (2024)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [DiffWave: A Versatile Diffusion Model for Audio Synthesis](https://mlsanity.com/paper/2009.09761/) (2020)
- [Maximum Likelihood Training of Score-Based Diffusion Models](https://mlsanity.com/paper/2101.09258/) (2021)
- [Score-based Generative Modeling in Latent Space](https://mlsanity.com/paper/2106.05931/) (2021)
- [Diffusion Schr"odinger Bridge with Applications to Score-Based Generative Modeling](https://mlsanity.com/paper/2106.01357/) (2021)
- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [Convergence of denoising diffusion models under the manifold hypothesis](https://mlsanity.com/paper/2208.05314/) (2022)
- [Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization](https://mlsanity.com/paper/2308.03686/) (2023)
- [Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions](https://mlsanity.com/paper/2211.01916/) (2022)
- [Convergence of score-based generative modeling for general data distributions](https://mlsanity.com/paper/2209.12381/) (2022)
- [Convergence for score-based generative modeling with polynomial complexity](https://mlsanity.com/paper/2206.06227/) (2022)
- [The probability flow ODE is provably fast](https://mlsanity.com/paper/2305.11798/) (2023)
- [Score-Based Generative Models Detect Manifolds](https://mlsanity.com/paper/2206.01018/) (2022)
- [Generative Modeling with Denoising Auto-Encoders and Langevin Sampling](https://mlsanity.com/paper/2002.00107/) (2020)
- [Protein structure generation via folding diffusion](https://mlsanity.com/paper/2209.15611/) (2022)
- [Parallel Sampling of Diffusion Models](https://mlsanity.com/paper/2305.16317/) (2023)
- [Let us Build Bridges: Understanding and Extending Diffusion Generative Models](https://mlsanity.com/paper/2208.14699/) (2022)
- [Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models](https://mlsanity.com/paper/2306.09251/) (2023)
- [The Randomized Midpoint Method for Log-Concave Sampling](https://mlsanity.com/paper/1909.05503/) (2019)
- [Accelerating Convergence of Score-Based Diffusion Models, Provably](https://mlsanity.com/paper/2403.03852/) (2024)
- [Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-Type Samplers](https://mlsanity.com/paper/2303.03384/) (2023)
- [Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity](https://mlsanity.com/paper/2405.15986/) (2024)
- [On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method](https://mlsanity.com/paper/2011.03176/) (2020)
- [Diffusion Posterior Sampling is Computationally Intractable](https://mlsanity.com/paper/2402.12727/) (2024)
- [Outlier-Robust Sparse Estimation via Non-Convex Optimization](https://mlsanity.com/paper/2109.11515/) (2021)
- [Improved Sample Complexity Bounds for Diffusion Model Training](https://mlsanity.com/paper/2311.13745/) (2023)

## Built on by (most cited first, 29 of 29)

- [A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Models](https://mlsanity.com/paper/2408.02320/) (2024)
- [Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms](https://mlsanity.com/paper/2502.00234/) (2025)
- [Low-dimensional adaptation of diffusion models: Convergence in total variation](https://mlsanity.com/paper/2501.12982/) (2025)
- [Stochastic Runge-Kutta Methods: Provable Acceleration of Diffusion Models](https://mlsanity.com/paper/2410.04760/) (2024)
- [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)
- [Advancing Wasserstein Convergence Analysis of Score-Based Models: Insights from Discretization and Second-Order Acceleration](https://mlsanity.com/paper/2502.04849/) (2025)
- [Optimal Convergence Analysis of DDPM for General Distributions](https://mlsanity.com/paper/2510.27562/) (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)
- [Provable Efficiency of Guidance in Diffusion Models for General Data Distribution](https://mlsanity.com/paper/2505.01382/) (2025)
- [Towards a unified framework for guided diffusion models](https://mlsanity.com/paper/2512.04985/) (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)
- [Diffusion Models with Heavy-Tailed Targets: Score Estimation and Sampling Guarantees](https://mlsanity.com/paper/2601.06715/) (2026)
- [Fast Score-Based Sampling via Log-Concave Reductions](https://mlsanity.com/paper/2512.24152/) (2025)
- [Accelerating Discrete Diffusion Models with Parallel-In-Time Sampling](https://mlsanity.com/paper/2607.00773/) (2026)
- [Dimension-free error estimate for diffusion model and optimal scheduling](https://mlsanity.com/paper/2512.01820/) (2025)
- [Query Lower Bounds for Diffusion Sampling](https://mlsanity.com/paper/2604.10857/) (2026)
- [Provably Reliable Classifier Guidance via Cross-Entropy Control](https://mlsanity.com/paper/2601.21200/) (2026)
- [On the Robustness of Distribution Support under Diffusion Guidance](https://mlsanity.com/paper/2605.07220/) (2026)
- [Diffusion Models Adapt to Low-Dimensional Structure Under Flexible Coefficient Choices](https://mlsanity.com/paper/2606.23627/) (2026)
- [Improved sampling algorithms and functional inequalities for non-log-concave distributions](https://mlsanity.com/paper/2507.11236/) (2025)
- [Are First-Order Diffusion Samplers Really Slower? A Fast Forward-Value Approach](https://mlsanity.com/paper/2512.24927/) (2025)
- [Breaking the Bottlenecks: Scalable Diffusion Models for 3D Molecular Generation](https://mlsanity.com/paper/2601.08963/) (2026)

## Abstract (arXiv)

Sampling algorithms play an important role in controlling the quality and runtime of diffusion model inference. In recent years, a number of works~citechen2023sampling,chen2023ode,benton2023error,lee2022convergence have proposed schemes for diffusion sampling with provable guarantees; these works show that for essentially any data distribution, one can approximately sample in polynomial time given a sufficiently accurate estimate of its score functions at different noise levels. In this work, we propose a new scheme inspired by Shen and Lee's randomized midpoint method for log-concave sampling~citeShenL19. We prove that this approach achieves the best known dimension dependence for sampling from arbitrary smooth distributions in total variation distance (widetilde O(d5/12) compared to widetilde O(√d) from prior work). We also show that our algorithm can be parallelized to run in only widetilde O(log2 d) parallel rounds, constituting the first provable guarantees for parallel sampling with diffusion models. As a byproduct of our methods, for the well-studied problem of log-concave sampling in total variation distance, we give an algorithm and simple analysis achieving dimension dependence widetilde O(d5/12) compared to widetilde O(√d) from prior work.