Overview
This research investigates the capacity for parallelism within different paradigms of diffusion large language models (dLLMs). Specifically, it provides a fine-grained comparison among masked, uniform, and Gaussian diffusion approaches regarding their ability to generate text sequences efficiently. The study addresses the limited principled understanding of how these competing dLLM paradigms compare in terms of parallelism, a key advertised advantage over autoregressive models.
Research Context
Diffusion large language models (dLLMs) are promoted for their capacity for parallelism, which allows for more efficient text sequence generation compared to autoregressive models. Autoregressive models necessitate one forward pass per token, whereas dLLMs offer potential for parallel generation. The field includes various dLLM paradigms, such as masked, uniform, and Gaussian diffusion. However, a comprehensive, principled understanding of their comparative parallelism has been absent.
Approach
The study initiated a fine-grained comparison to assess the parallelism capabilities across three prominent dLLM paradigms: masked diffusion, uniform diffusion, and Gaussian diffusion. This comparative analysis sought to establish a clearer understanding of their relative efficiencies in sequence generation. The methodology involved theoretical proofs to delineate the performance characteristics of each approach regarding the number of forward passes required for sampling.
Findings
- Uniform diffusion and Gaussian diffusion can sample in a number of forward passes that scales with the dual total correlation of the underlying distribution. This dual total correlation is characterized as a measure of intrinsic complexity. Prior to this work, achieving sampling efficiency scaling with dual total correlation was only known to be possible using masked diffusion.
- For a specific family of random empirical measures, the research demonstrates that approximately $\widetilde{\Theta}(\sqrt{d})$ forward passes are both necessary and sufficient for sampling when employing uniform or Gaussian diffusion.
- Conversely, for the same family of random empirical measures, the study showed that approximately $\widetilde{\Omega}(d)$ forward passes are required for masked diffusion when approximate score oracles are used.
- These findings collectively establish the first provable separation in parallelism among the three prevailing dLLM paradigms: masked, uniform, and Gaussian diffusion.
- Contrary to a common intuition that masked diffusions are more difficult to parallelize due to their need to commit to token values, the established separation suggests an alternative explanation. The difference is attributed to the critical windows in masked diffusion sampling being asymptotically narrower than those observed in uniform and Gaussian diffusion sampling.