aiqbench analysis
This research establishes fundamental information-theoretic limits for diffusion model sampling, proving that any algorithm requires at least $\widetilde{\Omega}(\sqrt{d})$ adaptive score queries in $d$-dimensional spaces. The findings provide a formal theoretical justification for the practical necessity of multiscale noise schedules by demonstrating that successful sampling inherently demands searching over a proportional number of distinct noise levels.
Query Lower Bounds for Diffusion Sampling
arXiv:2604.10857v2 Announce Type: replace Abstract: 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{\Omega}(\sqrt{d})$ adaptive score queries. In particular, our proof shows that, within any polynomial total-query budget, successful sampling requires searching over $\widetilde{\Omega}(\sqrt{d})$ distinct noise levels, providing a formal explanation for why multiscale noise schedules are necessary in practice.
Abstract: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{\Omega}(\sqrt{d})$ adaptive score queries. In particular, our proof shows that, within any polynomial total-query budget, successful sampling requires searching over $\widetilde{\Omega}(\sqrt{d})$ distinct noise levels, providing a formal explanation for why multiscale noise schedules are necessary in practice.
Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Data Structures and Algorithms (cs.DS); Statistics Theory (math.ST); Machine Learning (stat.ML)
arXiv:2604.10857 [cs.LG]
(or arXiv:2604.10857v2 [cs.LG] for this version)
Full text under the publisher's open licence · 133 words
Related coverage
Lower Bounds for Parallel Diffusion Sampling
arXiv · Oct 8, 2026
Private Decentralized Optimization with Noise Reduction and Bias Correction
arXiv · Sep 24, 2026
Build a Physical AI model factory with NVIDIA Cosmos 3 on SageMaker HyperPod
AWS · Sep 4, 2026
Implementing and Evaluating a Basic Per-Action Monitor for Safer Evals
METR · Sep 27, 2026