There is a mathematical 'speed limit' to how fast an AI can generate an image, and we just found it.
April 14, 2026
Original Paper
Query Lower Bounds for Diffusion Sampling
arXiv · 2604.10857
The Takeaway
This paper provides a formal proof that any sampling algorithm requires at least Ω(√d) queries, explaining why multiscale noise schedules are necessary. It sets a hard physical limit on how much we can accelerate the diffusion process.
From the 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