Research map / Image generation / Fast diffusion sampling

Query Lower Bounds for Diffusion Sampling

NeurIPS 2026 · Image generation › Fast diffusion sampling · approach: Diffusion theory and design space · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves that diffusion sampling with polynomially L^p-accurate smoothed score oracles needs Omega~(sqrt d) adaptive score queries (Omega(d^{1/4}) under subexponential error), via a hypothesis-testing reduction over random product-circle mixtures.

Problem

Information-theoretic limits on the number of score-function queries needed for diffusion sampling in high dimension, given polynomially accurate smoothed score estimates; whether polylog(d) queries could suffice.

Approach

Shows that any sampler must scan Omega~(sqrt d) distinct noise levels because the score signal from a random planted mixture is localized to a narrow window of smoothing scales (width ~sqrt d in log n), constructed via a likelihood-masked oracle that answers with the null score elsewhere.

Key results

• Any diffusion sampler with polynomially L^p-accurate score estimates and TV error below 0.99 requires Omega~(sqrt d) adaptive score queries.
• Under a subexponential error tail assumption, the lower bound weakens to Omega(d^{1/4}) queries.
• A Wasserstein analog gives Omega~(sqrt d) queries for W_q error below c*sqrt(d).

Surprising findings

• The hard instances have globally O(d)-Lipschitz scores, so Lipschitz-based accelerated upper bounds of the form L^a d^b are ruled out when a+b<1/2.

Limitations

• Gap between the Omega~(sqrt d) lower bound and the best known O~(d) upper bound remains open.
• Lower bound is for the adversarial oracle model; does not cover neural-network-restricted score functions or exact scores.
• Subexponential-error variant gives a weaker Omega(d^{1/4}) bound.

Experimental setup

Metrics: total variation distance Wasserstein distance

Baselines: DDPM

Builds on: DDPM Tweedie's formula Bernstein inequality Fano's inequality

Closest papers by meaning

• Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions (ICML 2024 · similarity 0.90)
• Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel (ICLR 2025 · similarity 0.90)
• Adapting to Unknown Low-Dimensional Structures in Score-Based Diffusion Models (NeurIPS 2024 · similarity 0.90)
• Accelerating Convergence of Score-Based Diffusion Models, Provably (ICML 2024 · similarity 0.89)
• Dimension-free Score Matching and Time Bootstrapping for Diffusion Models (NeurIPS 2025 · similarity 0.89)
• O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions (ICLR 2025 · similarity 0.89)