# Lower Bounds for Parallel Diffusion Sampling

arXiv: https://arxiv.org/abs/2610.09166 · HTML: https://mlsanity.com/paper/2610.09166/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 3 of its 54 references that are in the map.
- First posted on arXiv 6 Oct 2026.

## Placed in

- Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/)

## Builds on (most cited first, 3 of 3)

- [Oracle Lower Bounds for Stochastic Gradient Sampling Algorithms](https://mlsanity.com/paper/2002.00291/) (2020)
- [Parallelism, critical windows, and separations among diffusion language models](https://mlsanity.com/paper/2609.20539/) (2026)
- [A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model](https://mlsanity.com/paper/2609.30215/) (2026)

## Abstract (arXiv)

Standard diffusion samplers generate samples through repeated evaluations of a learned score function. Parallel sampling methods seek to accelerate generation by trading additional evaluations for fewer sequential rounds. This raises the question of how much sequential dependence is unavoidable, even when many score queries can be made simultaneously. We establish the first polynomial parallel-round lower bounds for diffusion sampling with approximate scores. Specifically, we prove (1) a widetildeOmega(d1/3)-round lower bound for sampling smooth, near-isotropic Gaussian mixtures in Rd, and (2) an Omega(d)-round lower bound for uniform sampling from anisotropic axis-aligned boxes contained in the unit ball. Both bounds hold for arbitrary randomized algorithms making polynomially many queries per round at arbitrary locations and noise levels, with inverse-polynomial score error and constant total variation accuracy. The linear bound is tight for our box family. Our constructions use fixed approximate score oracles that enforce sequential access to hidden information while satisfying the accuracy guarantee at every noise level.