Parallelism, critical windows, and separations among diffusion language models

TL;DR - This paper theoretically compares parallel sampling in masked, uniform, and Gaussian diffusion language models. It proves complexity-dependent speedups and the first formal separation showing cases where uniform and Gaussian diffusion require asymptotically fewer forward passes than masked diffusion.

• Uniform and Gaussian diffusion can sample in a number of forward passes scaling with the distribution’s dual total correlation, which may be much smaller than context length.
• For a family of random empirical measures, uniform and Gaussian diffusion need and achieve roughly (\widetilde{\Theta}(\sqrt{d})) forward passes.
• Some approximate score oracles force masked diffusion to use (\widetilde{\Omega}(d)) forward passes on the same family.
• The separation arises from asymptotically narrower critical sampling windows in masked diffusion, rather than from committing early to token values.