High-Accuracy Sampling for Diffusion Models and Log-Concave Distributions

We present algorithms for diffusion model sampling which obtain $\delta$-error in $\mathrm{polylog}(1/\delta)$ steps, given access to $\widetilde O(\delta)$-accurate score estimates in $L^2$. This is an exponential improvement over all previous results. Specifically, under minimal data assumptions, the complexity is $\widetilde O(d\mathrm{polylog}(1/\delta))$ where $d$ is the dimension of the data; under a non-uniform $L$-Lipschitz condition, the complexity is $\widetilde O(\sqrt{dL}\mathrm{polylog}(1/\delta))$; and if the data distribution has intrinsic dimension $d_\star$, then the complexity reduces to $\widetilde O(d_\star\mathrm{polylog}(1/\delta))$. Our approach also yields the first $\mathrm{polylog}(1/\delta)$ complexity sampler for general log-concave distributions using only gradient evaluations.

Sampling from diffusion models typically requires a number of steps, and neural network evaluations, that grows with the target accuracy. We ask whether diffusion models can reach very high accuracy in fewer steps. We introduce a new method, first-order rejection sampling (FORS), and use it to design diffusion samplers whose number of steps grows only logarithmically with the desired accuracy. This gives an exponential improvement in the accuracy dependence over prior guarantees. Our guarantees also depend only on the intrinsic dimension of the data, which can be much smaller than the ambient embedding dimension. These theoretical results suggest a path toward faster and more accurate generative sampling. The same framework also yields high-accuracy samplers for log-concave distributions using only gradient evaluations.