mlsanityData to 14 Oct 2026

Query Lower Bounds for Diffusion Sampling

arXiv 2604.10857 ↗First posted 12 Apr 2026cs.LG cs.AI cs.DScited by 2

On the map: Diffusion models → Diffusion foundations and sampling

Abstract (arXiv)

Diffusion models generate samples by iteratively querying learned score estimates. A rapidly growing literature focuses on accelerating sampling by minimizing the number of score evaluations, yet the information-theoretic limits of such acceleration remain unclear. In this work, we establish the first score query lower bounds for diffusion sampling. We prove that for d-dimensional distributions, given access to score estimates with polynomial accuracy varepsilon=d-O(1) (in any Lp sense), any sampling algorithm requires widetildeOmega(√d) adaptive score queries. In particular, our proof shows that, within any polynomial total-query budget, successful sampling requires searching over widetildeOmega(√d) distinct noise levels, providing a formal explanation for why multiscale noise schedules are necessary in practice.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models. Builds on 47 of its 59 references that are in the map. First posted on arXiv 12 Apr 2026.

Builds on

47 of 59 references.

Closest ancestors · 36

Same direction, newest first

  1. 2026High-accuracy sampling for diffusion models and log-concave distributions1 Feb
  2. 2026High-accuracy and dimension-free sampling with diffusions15 Jan
  3. 2025Sublinear iterations can suffice even for DDPMs6 Nov
  4. 2025Optimal Convergence Analysis of DDPM for General Distributions31 Oct
  5. 2025Assessing the Quality of Denoising Diffusion Models in Wasserstein Distance: Noisy Score and Optimal Bounds11 Jun
  6. 2025Beyond Log-Concavity and Score Regularity: Improved Convergence Bounds for Score-Based Generative Models in W2-distance4 Jan
  7. 2024Instance-dependent Convergence Theory for Diffusion Models17 Oct
  8. 2024Stochastic Runge-Kutta Methods: Provable Acceleration of Diffusion Models7 Oct
  9. 2024O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions27 Sep
  10. 2024A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Models5 Aug
  11. 2024Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel3 Jun
  12. 2024Accelerating Convergence of Score-Based Diffusion Models, Provably6 Mar
24 more
  1. 2024Convergence Analysis for General Probability Flow ODEs of Diffusion Models in Wasserstein Distances31 Jan
  2. 2023Improved Sample Complexity Bounds for Diffusion Model Training23 Nov
  3. 2023Wasserstein Convergence Guarantees for a General Class of Score-Based Generative Models18 Nov
  4. 2023KL Convergence Guarantees for Score diffusion models under minimal data assumptions23 Aug
  5. 2023Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization7 Aug
  6. 2023Error Bounds for Flow Matching Methods26 May
  7. 2023The probability flow ODE is provably fast19 May
  8. 2023Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-Type Samplers6 Mar
  9. 2023Consistency Models2 Mar
  10. 2023UniPC: A Unified Predictor-Corrector Framework for Fast Sampling of Diffusion Models9 Feb
  11. 2022Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions3 Nov
  12. 2022DPM-Solver++: Fast Solver for Guided Sampling of Diffusion Probabilistic Models2 Nov
  13. 2022Convergence of score-based generative modeling for general data distributions26 Sep
  14. 2022Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions22 Sep
  15. 2022Convergence of denoising diffusion models under the manifold hypothesis10 Aug
  16. 2022Convergence for score-based generative modeling with polynomial complexity13 Jun
  17. 2022DPM-Solver: A Fast ODE Solver for Diffusion Probabilistic Model Sampling in Around 10 Steps2 Jun
  18. 2022Elucidating the Design Space of Diffusion-Based Generative Models1 Jun
  19. 2022Fast Sampling of Diffusion Models with Exponential Integrator29 Apr
  20. 2022Pseudo Numerical Methods for Diffusion Models on Manifolds20 Feb
  21. 2021Improved Denoising Diffusion Probabilistic Models18 Feb
  22. 2020Score-Based Generative Modeling through Stochastic Differential Equations26 Nov
  23. 2020Denoising Diffusion Implicit Models6 Oct
  24. 2020Denoising Diffusion Probabilistic Models19 Jun

Other references · 11

  1. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,058
  2. 2022Flow Matching for Generative Modelingcited by 5,702
  3. 2019Generative Modeling by Estimating Gradients of the Data Distributioncited by 4,101
  4. 2022Flow Straight and Fast: Learning to Generate and Transfer Data with Rectified Flowcited by 3,700
  5. 2017Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlocited by 33
  6. 2024Flow matching achieves almost minimax optimal convergencecited by 29
  7. 2021The query complexity of sampling from strongly log-concave distributions in one dimensioncited by 18
  8. 2022Fisher information lower bounds for samplingcited by 12
  9. 2023Query lower bounds for log-concave samplingcited by 12
  10. 2025On the query complexity of sampling from non-log-concave distributionscited by 5
  11. 2025Posterior Sampling by Combining Diffusion Models with Annealed Langevin Dynamicscited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Parallelism, critical windows, and separations among diffusion language modelscited by 1
  2. 2026Smoothed Score Queries and the Complexity of Samplingcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Lower Bounds for Parallel Diffusion Sampling
  2. 2025Improved Sample Complexity For Diffusion Model Training Without Empirical Risk Minimizer Access
  3. 2026Diffusion Models Are Statistically Optimal for Learning Low-Dimensional Multi-Modal Distributions
  4. 2024Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions
  5. 2024Provable Acceleration for Diffusion Models under Minimal Assumptions
  6. 2026Generalization Properties of Score-matching Diffusion Models for Intrinsically Low-dimensional Data
  7. 2026Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees
  8. 2025Faster Diffusion Models via Higher-Order Approximation