{"id":"arxiv/2604.10857","url":"https://arxiv.org/abs/2604.10857","tags":["cs.LG","cs.AI","cs.DS","math.ST","stat.ML"],"score":0,"title":"Query Lower Bounds for Diffusion Sampling","domain":"cs.LG","source":"arxiv","authors":["Zhiyang Xun","Eric Price"],"reviews":0,"subject":"cs.LG","summary":"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,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-12","reactions":{}}