Query Lower Bounds for Diffusion Sampling
Provides fundamental limits for diffusion sampling acceleration, relevant to researchers designing faster sampling algorithms.
This work establishes the first information-theoretic lower bounds on the number of score queries required for diffusion sampling, proving that any algorithm needs at least Ω̃(√d) adaptive queries for d-dimensional distributions with polynomial accuracy, explaining the necessity of multiscale noise schedules.
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 $L^p$ sense), any sampling algorithm requires $\widetildeΩ(\sqrt{d})$ adaptive score queries. In particular, our proof shows that any sampler must search over $\widetildeΩ(\sqrt{d})$ distinct noise levels, providing a formal explanation for why multiscale noise schedules are necessary in practice.