# Breaking AR's Sampling Bottleneck: Provable Acceleration via Diffusion Language Models arXiv: https://arxiv.org/abs/2505.21400 ยท HTML: https://mlsanity.com/paper/2505.21400/ ## Key facts - Cited by 23 papers in the map (data through 14 Oct 2026). - Placed in Discrete and text diffusion, one of 14 directions in Diffusion models. - Builds on 48 of its 54 references that are in the map. - First posted on arXiv 27 May 2025. ## Placed in - Diffusion models / [Discrete and text diffusion](https://mlsanity.com/diffusion/discrete-and-text-diffusion/) ## Builds on (most cited first, 30 of 48) - [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020) - [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020) - [Denoising Diffusion Implicit Models](https://mlsanity.com/paper/2010.02502/) (2020) - [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015) - [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019) - [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021) - [Diffusion-LM Improves Controllable Text Generation](https://mlsanity.com/paper/2205.14217/) (2022) - [Large Language Diffusion Models](https://mlsanity.com/paper/2502.09992/) (2025) - [Simple and Effective Masked Diffusion Language Models](https://mlsanity.com/paper/2406.07524/) (2024) - [Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution](https://mlsanity.com/paper/2310.16834/) (2023) - [Simplified and Generalized Masked Diffusion for Discrete Data](https://mlsanity.com/paper/2406.04329/) (2024) - [Diffusion Schr"odinger Bridge with Applications to Score-Based Generative Modeling](https://mlsanity.com/paper/2106.01357/) (2021) - [Efficiently Scaling Transformer Inference](https://mlsanity.com/paper/2211.05102/) (2022) - [A Continuous Time Framework for Discrete Denoising Models](https://mlsanity.com/paper/2205.14987/) (2022) - [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022) - [Analog Bits: Generating Discrete Data using Diffusion Models with Self-Conditioning](https://mlsanity.com/paper/2208.04202/) (2022) - [Generative Flows on Discrete State-Spaces: Enabling Multimodal Flows with Applications to Protein Co-Design](https://mlsanity.com/paper/2402.04997/) (2024) - [Scaling Diffusion Language Models via Adaptation from Autoregressive Models](https://mlsanity.com/paper/2410.17891/) (2024) - [Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization](https://mlsanity.com/paper/2308.03686/) (2023) - [Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions](https://mlsanity.com/paper/2211.01916/) (2022) - [DiffusionBERT: Improving Generative Masked Language Models with Diffusion Models](https://mlsanity.com/paper/2211.15029/) (2022) - [Continuous diffusion for categorical data](https://mlsanity.com/paper/2211.15089/) (2022) - [SSD-LM: Semi-autoregressive Simplex-based Diffusion Language Model for Text Generation and Modular Control](https://mlsanity.com/paper/2210.17432/) (2022) - [Convergence of score-based generative modeling for general data distributions](https://mlsanity.com/paper/2209.12381/) (2022) - [Convergence for score-based generative modeling with polynomial complexity](https://mlsanity.com/paper/2206.06227/) (2022) - [Score Approximation, Estimation and Distribution Recovery of Diffusion Models on Low-Dimensional Data](https://mlsanity.com/paper/2302.07194/) (2023) - [Score-based Continuous-time Discrete Diffusion Models](https://mlsanity.com/paper/2211.16750/) (2022) - [Diffusion Models are Minimax Optimal Distribution Estimators](https://mlsanity.com/paper/2303.01861/) (2023) - [Likelihood-Based Diffusion Language Models](https://mlsanity.com/paper/2305.18619/) (2023) - [Concrete Score Matching: Generalized Score Matching for Discrete Data](https://mlsanity.com/paper/2211.00802/) (2022) ## Built on by (most cited first, 23 of 23) - [Optimal Inference Schedules for Masked Diffusion Models](https://mlsanity.com/paper/2511.04647/) (2025) - [Confidence-Based Decoding is Provably Efficient for Diffusion Language Models](https://mlsanity.com/paper/2603.22248/) (2026) - [Optimal Convergence Analysis of DDPM for General Distributions](https://mlsanity.com/paper/2510.27562/) (2025) - [Error Bounds and Optimal Schedules for Masked Diffusions with Factorized Approximations](https://mlsanity.com/paper/2510.25544/) (2025) - [Adaptation to Intrinsic Dependence in Diffusion Language Models](https://mlsanity.com/paper/2602.20126/) (2026) - [Latent Refinement Decoding: Enhancing Diffusion-Based Language Models by Refining Belief States](https://mlsanity.com/paper/2510.11052/) (2025) - [Beyond Confidence: Adaptive and Coherent Decoding for Diffusion Language Models](https://mlsanity.com/paper/2512.02044/) (2025) - [Sharp Convergence Rates for Masked Diffusion Models](https://mlsanity.com/paper/2602.22505/) (2026) - [The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity](https://mlsanity.com/paper/2608.13520/) (2026) - [Learnable Sampler Distillation for Discrete Diffusion Models](https://mlsanity.com/paper/2509.19962/) (2025) - [On the Reasoning Abilities of Masked Diffusion Language Models](https://mlsanity.com/paper/2510.13117/) (2025) - [Decoding Large Language Diffusion Models with Foreseeing Movement](https://mlsanity.com/paper/2512.04135/) (2025) - [Discrete-WAM: Unified Discrete Vision-Action Token Editing for World-Policy Learning](https://mlsanity.com/paper/2606.05645/) (2026) - [Provably adaptive sampling with uniform and remasking discrete diffusion models](https://mlsanity.com/paper/2608.23554/) (2026) - [Diffusion Models Are Statistically Optimal for Learning Low-Dimensional Multi-Modal Distributions](https://mlsanity.com/paper/2605.30153/) (2026) - [ConvergeFlow: Language Flow with Provable Convergence to Token Embeddings](https://mlsanity.com/paper/2608.23551/) (2026) - [Infinite Mask Diffusion for Few-Step Distillation](https://mlsanity.com/paper/2605.10518/) (2026) - [Differences in Text Generated by Diffusion and Autoregressive Language Models](https://mlsanity.com/paper/2605.12522/) (2026) - [Diffusion Models Adapt to Low-Dimensional Structure Under Flexible Coefficient Choices](https://mlsanity.com/paper/2606.23627/) (2026) - [Extracting Training Data from Diffusion Language Models via Infilling](https://mlsanity.com/paper/2605.24173/) (2026) - [One-step lowest-variance selection in a Gaussian random-field model motivated by masked diffusion: Total correlation and a square root collision threshold](https://mlsanity.com/paper/2607.17522/) (2026) - [Schedule optimization for tau-leaping in masked discrete diffusion](https://mlsanity.com/paper/2609.21960/) (2026) - [Sample complexity bounds for categorical Markov random fields via Discrete Diffusions](https://mlsanity.com/paper/2610.02128/) (2026) ## Abstract (arXiv) Diffusion models have emerged as a powerful paradigm for modern generative modeling, demonstrating strong potential for large language models (LLMs). Unlike conventional autoregressive (AR) models that generate tokens sequentially, diffusion models allow for parallel sampling, offering a promising path to accelerate generation and eliminate the left-to-right generation constraints. Despite their empirical success, theoretical understandings of diffusion language models remain underdeveloped. In this work, we develop convergence guarantees for diffusion language models from an information-theoretic perspective. Our analysis demonstrates that the sampling error, measured by the Kullback-Leibler (KL) divergence, decays inversely with the number of iterations T and scales linearly with the mutual information between tokens in the target text sequence. Crucially, our theory covers the regime T