Provable Sampling Acceleration in Diffusion Language Models via Adaptation to Low-Dimensional Structures

Thomas M. Menino Convention & Exhibition Center 

Diffusion language models (DLMs) have emerged as a compelling alternative to autoregressive (AR) models by enabling parallel, non-sequential token generation. Despite their strong empirical performance, the theoretical understanding of how decoding strategies affect sampling efficiency remains limited. In this talk, we present recent theoretical advances showing that DLM sampling can be substantially accelerated through decoding strategies that exploit low-dimensional structure in the target data distribution. We establish convergence guarantees for both uniform and confidence-based decoding strategies, proving that high-quality samples can be generated in a sublinear number of iterations. In particular, the iteration complexity depends on information-theoretic quantities that capture the intrinsic complexity of the target distribution. These results provide a theoretical foundation for efficient diffusion-based language generation and offer principled insights into decoding strategy design.