HIGH-ACCURACY PARALLEL DIFFUSION SAMPLING: NEAR-LINEAR QUERIES AND SQUARE-ROOT DEPTH

Standard diffusion samplers are sequential: every denoiser call depends on the previous state. Parallel proposals reduce this dependency, but at high accuracy they can require far more denoiser calls. We give a parallel sampler with near-linear query complexity under only a finite-second-moment assumption. For any zero-mean distribution $\pi$ on ${\mathbb{R}}^n$ with a known second-moment bound and exact access to its Gaussian posterior mean, the sampler uses $\tilde{O}(n)$ expected full-vector queries and $\tilde{O}(\sqrt{n})$ expected adaptive rounds. We use Euler discretization only for parallel proposals and correct them by rejection sampling against the high-accuracy FORS diffusion path of Chen et al. (2026). We introduce a mechanism we call a causal guard to handle rare, large changes in the diffusion drift. Compared with the recursive parallel result of Anari et al. (2026), this removes bounded support and replaces polynomial dependence on accuracy, smoothing, and support radius with polylogarithmic dependence.