Parallel Sampling via Autospeculation

We present parallel algorithms to accelerate sampling via counting in two settings: any-order autoregressive models and denoising diffusion models. An any-order autoregressive model accesses a target distribution µ on [q]n through an oracle that provides conditional marginals, while a denoising diffusion model accesses a target distribution µ on ℝn through an oracle that provides conditional means under Gaussian noise. Standard sequential sampling algorithms require Õ(n) time to produce a sample from µ in either setting. We show that, by issuing oracle calls in parallel, the expected sampling time can be reduced to Õ(n1/2). This improves the previous Õ(n2/3) bound for any-order autoregressive models and yields the first parallel speedup for diffusion models in the high-accuracy regime, under the relatively mild assumption that the support of µ is bounded.