Parallelism, critical windows, and separations among diffusion language models
Ranking
Overall
78
Content
95
Popularity
39
Observed public metrics from 1 member.
Merged summary
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.
Sources (1)
Parallelism, critical windows, and separations among diffusion language models
Public signals
Semantic Scholar citations 0 · Semantic Scholar influential citations 0
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.