# Diffusion Language Models are Provably Optimal Parallel Samplers

arXiv: https://arxiv.org/abs/2512.25014 · HTML: https://mlsanity.com/paper/2512.25014/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in Discrete and text diffusion, one of 14 directions in Diffusion models.
- Builds on 17 of its 22 references that are in the map.
- First posted on arXiv 31 Dec 2025.

## Placed in

- Diffusion models / [Discrete and text diffusion](https://mlsanity.com/diffusion/discrete-and-text-diffusion/)

## Builds on (most cited first, 17 of 17)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [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)
- [Dream 7B: Diffusion Large Language Models](https://mlsanity.com/paper/2508.15487/) (2025)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [MMaDA: Multimodal Large Diffusion Language Models](https://mlsanity.com/paper/2505.15809/) (2025)
- [Mercury: Ultra-Fast Language Models Based on Diffusion](https://mlsanity.com/paper/2506.17298/) (2025)
- [DiffusionBERT: Improving Generative Masked Language Models with Diffusion Models](https://mlsanity.com/paper/2211.15029/) (2022)
- [Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions](https://mlsanity.com/paper/2502.06768/) (2025)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Seed Diffusion: A Large-Scale Diffusion Language Model with High-Speed Inference](https://mlsanity.com/paper/2508.02193/) (2025)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [Dream-Coder 7B: An Open Diffusion Language Model for Code](https://mlsanity.com/paper/2509.01142/) (2025)

## Built on by (most cited first, 6 of 6)

- [Generalized Discrete Diffusion with Self-Correction](https://mlsanity.com/paper/2603.02230/) (2026)
- [Differences in Text Generated by Diffusion and Autoregressive Language Models](https://mlsanity.com/paper/2605.12522/) (2026)
- [K-Forcing: Joint Next-K-Token Decoding via Push-Forward Language Modeling](https://mlsanity.com/paper/2606.10820/) (2026)
- [Conditional Total Correlation and the Serial Depth of Adaptive Parallel Sampling](https://mlsanity.com/paper/2608.25505/) (2026)
- [DiPOD: Diffusion Policy Optimization without Drifting Apart](https://mlsanity.com/paper/2606.13795/) (2026)
- [Limitations on Autoregressive Token Generation via Sequential Sampling](https://mlsanity.com/paper/2610.14615/) (2026)

## Abstract (arXiv)

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.