# Query Lower Bounds for Diffusion Sampling

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

## 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.

## Placed in

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

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

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [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)
- [Flow Matching for Generative Modeling](https://mlsanity.com/paper/2210.02747/) (2022)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Improved Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2102.09672/) (2021)
- [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)
- [DPM-Solver: A Fast ODE Solver for Diffusion Probabilistic Model Sampling in Around 10 Steps](https://mlsanity.com/paper/2206.00927/) (2022)
- [Consistency Models](https://mlsanity.com/paper/2303.01469/) (2023)
- [DPM-Solver++: Fast Solver for Guided Sampling of Diffusion Probabilistic Models](https://mlsanity.com/paper/2211.01095/) (2022)
- [Pseudo Numerical Methods for Diffusion Models on Manifolds](https://mlsanity.com/paper/2202.09778/) (2022)
- [Fast Sampling of Diffusion Models with Exponential Integrator](https://mlsanity.com/paper/2204.13902/) (2022)
- [UniPC: A Unified Predictor-Corrector Framework for Fast Sampling of Diffusion Models](https://mlsanity.com/paper/2302.04867/) (2023)
- [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)
- [Error Bounds for Flow Matching Methods](https://mlsanity.com/paper/2305.16860/) (2023)
- [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)
- [A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Models](https://mlsanity.com/paper/2408.02320/) (2024)
- [KL Convergence Guarantees for Score diffusion models under minimal data assumptions](https://mlsanity.com/paper/2308.12240/) (2023)
- [Wasserstein Convergence Guarantees for a General Class of Score-Based Generative Models](https://mlsanity.com/paper/2311.11003/) (2023)
- [Convergence Analysis for General Probability Flow ODEs of Diffusion Models in Wasserstein Distances](https://mlsanity.com/paper/2401.17958/) (2024)
- [O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions](https://mlsanity.com/paper/2409.18959/) (2024)

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

- [Parallelism, critical windows, and separations among diffusion language models](https://mlsanity.com/paper/2609.20539/) (2026)
- [Smoothed Score Queries and the Complexity of Sampling](https://mlsanity.com/paper/2605.27769/) (2026)

## 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.