Diffusion Language Models are Provably Optimal Parallel Samplers

This paper establishes a theoretical framework for diffusion language models (DLMs), positioning them as mathematically optimal parallel samplers compared to sequential autoregressive models. By using circuit complexity as a benchmark, the authors prove that DLMs can generate complex distributions in the minimum number of sequential steps when paired with chain-of-thought reasoning. The research highlights that advanced inference techniques like remasking and revision are essential for minimizing memory usage while maximizing the model's expressive power. Without these capabilities, standard DLMs fail to perform tasks like parity sampling that involve high token correlation. Ultimately, the findings provide a rigorous justification for the superior efficiency and speed of DLMs in large-scale language generation.