Research map / Image generation / Fast diffusion sampling
Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PIADM-SDE and PIADM-ODE, which split diffusion sampling into O(1) time blocks and run Picard iterations in parallel within each block, proving poly-logarithmic approximate time complexity in data dimension d.
Problem
Diffusion model inference requires many sequential score-network evaluations, and prior theoretical bounds scale polynomially with data dimension d (O(d) for SDE, O(sqrt d) for ODE); the goal is provable sub-linear inference time complexity.
Approach
Divide the backward process into O(1)-length blocks and solve each block with parallel Picard iteration using exponential integrators, early stopping and a shrinking last-block step size; a generalized Girsanov theorem handles the dependence of successive Picard paths. The ODE variant adds a parallelized underdamped Langevin corrector step.
Key results
- PIADM-SDE achieves O~(poly log d) approximate time complexity (KN = O~(log^2(d delta^-2))) with O~(d^2 delta^-2) space, the first provable sub-linear time bound for diffusion inference.
- PIADM-ODE achieves the same poly-logarithmic time complexity while reducing space complexity to O~(d^{3/2}) (from O~(d^2) for SDE).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use parallel sampling with blockwise Picard iterations | SDE diffusion sampling · High-dimensional theoretical sampling; KL(p_η || q̂_{T−η}) | approximate time complexity: \widetilde\gO(d) -> \widetilde\gO(\poly \log (d \delta^{-2})) | Helped |
| Use parallel sampling with blockwise Picard iterations | Probability flow ODE diffusion sampling · High-dimensional theoretical sampling; TV(p_η, q̂_{T−η})² | approximate time complexity: \widetilde\gO(\sqrt{d} \delta^{-1}) -> \widetilde\gO(\poly \log (d \delta^{-2})) | Helped |
| Use the probability flow ODE implementation with its corrector step | Parallel diffusion sampling · High-dimensional theoretical sampling | space complexity: \widetilde\gO(d^2) -> \widetilde\gO(d^{3/2}) | Helped |
Surprising findings
- Parallelism trades time for memory: the poly-log time bound requires space scaling as d^2 (SDE) or d^{3/2} (ODE).
Limitations
- Theory-only: no experiments validating the bounds on real diffusion models.
- Space complexity grows to O~(d^2) for SDE, which is a practical memory burden.
- Requires strong assumptions such as bounded and Lipschitz learned scores and normalized data covariance.
Experimental setup
Metrics: approximate time complexity space complexity KL divergence bound TV distance bound
Baselines: ParaDiGMS ParaTAA SDE diffusion bounds (d-linear) probability flow ODE with UMLC corrector (sqrt d)
Builds on: ParaDiGMS Picard iteration exponential integrator Girsanov's theorem underdamped Langevin corrector
Closest papers by meaning
- A Simple Early Exiting Framework for Accelerated Sampling in Diffusion Models (ICML 2024 · similarity 0.92)
- Accelerating Parallel Sampling of Diffusion Models (ICML 2024 · similarity 0.92)
- DistriFusion: Distributed Parallel Inference for High-Resolution Diffusion Models (CVPR 2024 · similarity 0.91)
- Simple and Fast Distillation of Diffusion Models (NeurIPS 2024 · similarity 0.90)
- AsyncDiff: Parallelizing Diffusion Models by Asynchronous Denoising (NeurIPS 2024 · similarity 0.90)
- Accelerating Convergence of Score-Based Diffusion Models, Provably (ICML 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.