Diffusion Language Models are Provably Optimal Parallel Samplers
Diffusion language models (DLMs) have emerged as a promising alternative to autoregressive models for faster inference via parallel token generation. We provide a rigorous foundation for this advantage by formalizing a model of parallel sampling and showing that DLMs augmented with polynomial-length chain-of-thought (CoT) can simulate any parallel sampling algorithm using an optimal number of sequential steps. Consequently, whenever a target distribution can be generated using a small number of sequential steps, a DLM can be used to generate the distribution using the same number of optimal sequential steps. However, without the ability to modify previously revealed tokens, DLMs with CoT can still incur large intermediate footprints. We prove that enabling remasking (converting unmasked tokens to masks) or revision (converting unmasked tokens to other unmasked tokens) together with CoT further allows DLMs to simulate any parallel sampling algorithm with optimal space complexity. We further justify the advantage of revision by establishing a strict expressivity gap: DLMs with revision or remasking are strictly more expressive than those without. Our results not only provide a theoretical justification for the promise of DLMs as the most efficient parallel sampler, but also advocate for enabling revision in DLMs.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Understanding Parallel Samplers in Masked Diffusion via Random Walks on Graphs
In this paper, we propose using random walks on graphs as a verifiable sandbox to study different parallel sampling strategies in masked diffusion models (MDMs). We train an MDM on random walk samples from a fixed graph.…
It Takes Two to Tango: Two Parallel Samplers Improve Quality in Diffusion Models for Limited Steps
We consider the situation where we have a limited number of denoising steps, i.e., of evaluations of a diffusion model. We show that two parallel processors or samplers under such limitation can improve the quality of th…
Provable Acceleration for Diffusion Models under Minimal Assumptions
Score-based diffusion models, while achieving minimax optimality for sampling, are often hampered by slow sampling speeds due to the high computational burden of score function evaluations. Despite the recent remarkable …
Self-Refining Diffusion Samplers: Enabling Parallelization via Parareal Iterations
In diffusion models, samples are generated through an iterative refinement process, requiring hundreds of sequential model evaluations. Several recent methods have introduced approximations (fewer discretization steps or…
Discrete Predictor-Corrector Diffusion Models for Image Synthesis
We introduce Discrete Predictor-Corrector diffusion models (DPC), extending predictor-corrector samplers in Gaussian diffusion models to the discrete case. Predictor-corrector samplers are a class of samplers for diffusi…
Conditional Image GenerationImage Generation