Combinatorics Seminar

We present parallel algorithms for speeding up sampling procedures in two settings: any-order autoregressive models and denoising diffusion models. In an autoregressive model, the algorithm interacts with a distribution $\mu$ on $[q]^n$ through an oracle that returns conditional probabilities. In a diffusion model, it interacts with a distribution $\mu$ on $R^n$ through an oracle that gives conditional means under Gaussian noise. Standard sampling methods in both settings require O(n) sequential steps. We show that, by issuing these oracle calls in parallel, the expected sampling time can be reduced to \tilde{O}(n^{1/2}). This improves the previous \tilde{O}(n^{2/3}) bound for any-order autoregressive models and gives the first parallel speedup for diffusion models in the high-accuracy regime, under the mild assumption that the support of μ is bounded. Our analysis is based on new variants of the pinning lemma, and "autospeculative rejection sampling", a recursive rejection sampling algorithm that uses the same oracle for $\mu$ to build distribution(s) $\nu$ that approximate(s) the target distribution $\mu$ well enough to accelerate sampling. Joint work with Nima Anari, Carlo Baronio, CJ Chen, Alireza Haqi, Frederic Koehler, and Anqi Li.