mlsanityData to 7 Oct 2026

Perfect diffusion is mathsfTC0 -- Bad diffusion is Turing-complete

arXiv 2507.12469 ↗First posted 20 Apr 2025cs.CC cs.CL cs.LGcited by 3

On the map: Diffusion models → Discrete and text diffusion

Abstract (arXiv)

This paper explores the computational complexity of diffusion-based language modeling. We prove a dichotomy based on the quality of the score-matching network in a diffusion model. In one direction, a network that exactly computes the score function of some initial distribution can only perform language modeling within the mathsfTC0 complexity class, reflecting limitations tied to rapid convergence. In the other direction, we show that if there is no requirement for the network to match any score function, then diffusion modeling can simulate any Turing machine in a certain sense. This dichotomy provides a theoretical lens on the capabilities and limitations of diffusion models, particularly concerning tasks requiring sequential computation. We conjecture extensions of our theoretical results, including for the case where the diffusion model is not perfect, but merely good. We also discuss the wider context and practical implications, and hypothesize that a machine learning architecture that can interpolate between sequential and parallel modes of operation would be superior to both Transformers and diffusion models.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Placed in Discrete and text diffusion, one of 14 directions in Diffusion models. Builds on 15 of its 20 references that are in the map. First posted on arXiv 20 Apr 2025.

Builds on

15 of 20 references.

Closest ancestors · 2

Same direction, newest first

  1. 2025Block Diffusion: Interpolating Between Autoregressive and Diffusion Language Models12 Mar
  2. 2022DiffuSeq: Sequence to Sequence Text Generation with Diffusion Models17 Oct

Other references · 13

  1. 2021Diffusion Models Beat GANs on Image Synthesiscited by 8,185
  2. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,005
  3. 2021Structured Denoising Diffusion Models in Discrete State-Spacescited by 1,665
  4. 2021Variational Diffusion Modelscited by 1,145
  5. 2022Understanding Diffusion Models: A Unified Perspectivecited by 337
  6. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  7. 2022Transformers Learn Shortcuts to Automatacited by 260
  8. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 256
  9. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  10. 2024The Illusion of State in State-Space Modelscited by 181
  11. 2024O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptionscited by 48
  12. 2024Scaling Properties of Diffusion Models for Perceptual Taskscited by 15
1 more
  1. 2025Spatial Reasoning with Denoising Modelscited by 15

Built on by

Cited by year

Citing papers per year: 2025: 3.

3 papers.

  1. 2025The Serial Scaling Hypothesiscited by 11
  2. 2025On the Reasoning Abilities of Masked Diffusion Language Modelscited by 6
  3. 2025Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspectivecited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Parallelism, critical windows, and separations among diffusion language models
  2. 2026Scaling Beyond Masked Diffusion Language Models
  3. 2025On the Role of Discreteness in Diffusion LLMs
  4. 2026Breaking the Factorization Barrier in Diffusion Language Models
  5. 2025Breaking AR's Sampling Bottleneck: Provable Acceleration via Diffusion Language Models
  6. 2026ALoDLM: Adaptively Looped Diffusion Language Models
  7. 2023Likelihood-Based Diffusion Language Models
  8. 2025Large Language Models to Diffusion Finetuning