mlsanityData to 7 Oct 2026

Diffusion Language Models are Provably Optimal Parallel Samplers

arXiv 2512.25014 ↗First posted 31 Dec 2025cs.LG cs.CCcited by 5

On the map: Diffusion models → Discrete and text diffusion

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.

Key facts. Cited by 5 papers in the map (data through 7 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.

Builds on

17 of 22 references.

Closest ancestors · 8

Same direction, newest first

  1. 2025Dream-Coder 7B: An Open Diffusion Language Model for Code1 Sep
  2. 2025Dream 7B: Diffusion Large Language Models21 Aug
  3. 2025Seed Diffusion: A Large-Scale Diffusion Language Model with High-Speed Inference4 Aug
  4. 2025Large Language Diffusion Models14 Feb
  5. 2025Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions10 Feb
  6. 2024Simple and Effective Masked Diffusion Language Models11 Jun
  7. 2023Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution25 Oct
  8. 2022DiffusionBERT: Improving Generative Masked Language Models with Diffusion Models28 Nov

Other references · 9

  1. 2020Denoising Diffusion Probabilistic Modelscited by 20,851
  2. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  3. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,005
  4. 2021Structured Denoising Diffusion Models in Discrete State-Spacescited by 1,665
  5. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 256
  6. 2025MMaDA: Multimodal Large Diffusion Language Modelscited by 241
  7. 2025Mercury: Ultra-Fast Language Models Based on Diffusioncited by 225
  8. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  9. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 5.

5 papers.

  1. 2026Generalized Discrete Diffusion with Self-Correctioncited by 1
  2. 2026Differences in Text Generated by Diffusion and Autoregressive Language Modelscited by 1
  3. 2026K-Forcing: Joint Next-K-Token Decoding via Push-Forward Language Modelingcited by 1
  4. 2026Conditional Total Correlation and the Serial Depth of Adaptive Parallel Samplingcited by 1
  5. 2026DiPOD: Diffusion Policy Optimization without Drifting Apartcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026A Tale of Two Temperatures: Simple, Efficient, and Diverse Sampling from Diffusion Language Models
  2. 2026Fork-dLLM: Avoiding the Flexibility Trap in Diffusion Language Models
  3. 2026Adaptation to Intrinsic Dependence in Diffusion Language Models
  4. 2025Optimal Inference Schedules for Masked Diffusion Models
  5. 2025Breaking AR's Sampling Bottleneck: Provable Acceleration via Diffusion Language Models
  6. 2025Diffusion Language Model Inference with Monte Carlo Tree Search
  7. 2025A Survey on Diffusion Language Models
  8. 2026Accelerating Masked Diffusion Large Language Models: A Survey of Efficient Inference Techniques