Pith. sign in

REVIEW 3 major objections 4 minor 25 references

Perfect diffusion is $\mathsf{TC}^0$ -- Bad diffusion is Turing-complete

T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Perfectly score-matched diffusion models compute only within TC0, while deliberately bad diffusion processes can simulate any Turing machine.

desk verdict A promising dichotomy, but the perfect-side theorem leans on an unverified convergence bound and a hand-waved derandomization; the central claim is not yet proven. read the letter →

arxiv 2507.12469 v1 pith:G7SBKQOG submitted 2025-04-20 cs.CC cs.CLcs.LG

Yuxi Liu This is my paper · ORCID
classification cs.CCcs.CLcs.LG MSC 68Q15
keywords diffusionmodelsTC0circuitcomplexityscorematchinglanguagemodelingTuringcompletenesscountermachinescomputational
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes a dichotomy in what diffusion-based language models can compute, depending on whether their score networks are perfect or not. The author proves that if a family of constant-depth, polynomial-width score networks exactly computes the score function of some initial distribution with bounded first moment, and the resulting infinite-time denoising solves next-token prediction with a constant probability advantage, then the predicted language problem lies in TC0, the class of problems solvable by constant-depth threshold circuits. The reason is that a universal convergence bound forces the sampler to be accurate after a fixed number of denoising steps independent of the token length, so only constant sequential depth is available. In the opposite direction, the paper constructs a deliberately 'bad' diffusion process—an arbitrary smooth force field on a high-dimensional space—that simulates a counter machine, showing that without the score-matching constraint diffusion-like sampling can be Turing-complete. If true, the dichotomy gives a precise sense in which rapid parallel convergence is a computational ceiling.

What carries the argument

The load-bearing machinery is the score function, the gradient of the log-density of the noisy data distribution, together with a universal total-variation bound imported from convergence theory for diffusion models. Under exact score matching and an initial distribution with bounded first moment, the bound reads $\mathrm{TV}(\rho_{\mathrm{DDPM},T}, \rho_{\hat{x},0}) \leq c d (\log T)^3 / T$; because the constant $c$ is universal, choosing $T = c c' d^2$ makes the error smaller than any fixed $\varepsilon' > 0$ for every dimension $d$, and in particular for every input length $n$. The second piece is derandomization: a proposition of threshold-circuit theory converts the constant-probability sampler into a deterministic $\mathsf{TC}^0$ circuit family by hard-coding a magic advice string and taking a majority over polynomially many samples. For the converse direction, the machinery is a pinball construction: the state space is divided into cubic cells representing registers, a program counter, and a jump workspace, and a smooth Lipschitz force field with grooves guides a noisy ball along the instruction paths of a counter machine.

What would settle it

Take an initial distribution that satisfies the bounded-first-moment assumption but has infinite variance, and compute the total-variation error of the exact-score DDPM sampler after $T = c c' d^2$ steps. If the error does not go to zero uniformly in the dimension, or if the required step count grows with the input length $n$, the TC0 theorem fails at its key step. A direct disproof would be a TC0 family of exact-score networks that solves the word problem for the permutation group $S_5$ at infinite-time SMLD with a constant probability advantage.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central discovery is the theorem of Section III: any TC0 family of score networks that exactly matches the score function of some initial distribution with bounded first moment, and that solves a prefix language modeling problem at infinite-time SMLD with constant probability bound, places that problem in TC0. The proof shows that $T = cc'd^2$ denoising steps suffice for total-variation error below any fixed positive value, and since the dimension $d$ does not grow with the token length $n$, the needed number of steps is constant; derandomizing the sampling with a hard-coded advice string then yields a deterministic TC0 circuit family. The paper also proves a converse construction: a 'pinball' SDE driven by an arbitrary smooth force field can implement any counter machine, hence any Turing machine, so the constraint is not inherent to stochastic differential equations but to the requirement of matching a true score function.

Load-bearing premise

The whole perfect-diffusion half rests on a single imported inequality: with an exact score network and an initial distribution whose average length is at most 1, a fixed number of denoising steps that does not grow with the input already makes the error as small as one likes; if that inequality secretly needs extra conditions, such as finite variance, smooth score functions, or a step count that grows with the dimension, the theorem no longer follows.

Editorial extensions

If this is right

  • A perfectly score-matched diffusion language model cannot solve any prefix prediction problem that lies outside TC0, no matter how many denoising steps it takes.
  • The TC0 ceiling applies to any score-network family whose forward pass is in TC0, including Transformers and state-space models, not only feedforward networks.
  • Constant-probability success does not circumvent the ceiling: derandomization converts a constant-probability sampler into a deterministic TC0 circuit family.
  • Removing the exact-score requirement changes the picture completely: an arbitrary smooth force field can simulate any counter machine, so diffusion-like SDEs are Turing-complete.
  • The realistic intermediate case of approximate score matching remains open; the paper conjectures, but does not prove, that sufficiently good approximations inherit the TC0 limitation.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Pith inference: If the author's conjecture for approximate scores holds, real diffusion language models should show a sharp performance cliff on inherently sequential tasks regardless of denoising budget; this is directly testable by comparing accuracy on TC0-easy versus sequential-hard task families.
  • Pith inference: The pinball construction implies that adding an autoregressive component to a diffusion model is not just an engineering trick but a way to buy back the sequential depth that exact score matching gives away; hybrid samplers that adaptively alternate parallel and sequential denoising would test this trade-off explicitly.
  • Pith inference: The paper's compact-state-space hypothesis suggests discrete diffusion over finite alphabets should be TC0-limited even with imperfect scores, because a finite state space exhausts the signal-to-noise ratio before any deep computation can occur; a clean test is to measure whether discrete diffusion can learn regular languages with known non-TC0 circuit requirements.
  • Pith inference: The dichotomy also bears on image generation: if exact-score diffusion is TC0-limited, then tasks requiring global sequential dependencies (for example, arranging multiple objects with occlusion constraints) should be where parallel denoising fails, mirroring the Sudoku results cited in the paper.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The manuscript claims a dichotomy in the computational power of diffusion-based language models. On the 'perfect' side, it argues that if a TC0-family of score networks exactly matches the score function of some initial distribution with bounded first moment and the resulting infinite-time SMLD process solves a prefix language modeling problem with constant probability, then that problem lies in TC0. The proof relies on an external discretization bound from [LY24] to replace the infinite-time process by finitely many DDPM steps with total-variation error independent of the input length, and then on a derandomization argument from [HMP+93] to obtain a TC0 circuit family. On the 'bad' side, the paper sketches a pinball-machine construction in which an unconstrained smooth drift field simulates a counter machine, and hence any Turing machine. The final sections discuss conjectures for approximate score matching, empirical predictions, and possible hybrid architectures.

Significance. If the main theorem were fully rigorous, it would provide a striking complexity-theoretic explanation of empirical observations that diffusion language models converge quickly and struggle with sequential reasoning: exact-score diffusion would be confined to constant-depth parallel computation. The paper also offers a clean, falsifiable conjecture for the approximate-score regime and identifies an interesting contrast with unconstrained drift models. Its strengths are the clarity of the high-level dichotomy and the explicit use of quantitative convergence bounds. However, the paper does not ship machine-checked proofs or reproducible code, and the main theorem depends on external results whose precise hypotheses are not stated. As it stands, the contribution is an attractive research program and a plausible proof sketch rather than a fully demonstrated theorem.

major comments (3)
  1. [Section III, Eq. (7)] The proof of the theorem rests on the discretization inequality (7), cited to [LY24] as a universal-constant bound TV(ρDDPM,T, ρ_x̂,0) ≤ c d (log T)^3 / T under only E_{ρ0,n}[∥x0∥] ≤ 1. The manuscript does not state the hypotheses of the quoted result. If [LY24] requires, for example, finite second moments, Lipschitz score regularity, or a distribution-dependent constant, the displayed bound is not available for the distributions allowed in the theorem. The subsequent sentence 'The key is that T does not increase with n' also presupposes that the ambient dimension d is constant or independent of n, which the theorem statement never says; if d grows with n, then T = cc'd^2 grows with n and the constant-depth conclusion no longer follows. This is the load-bearing step and it needs to be made fully explicit.
  2. [Section III, derandomization step] The step 'Now we can derandomize this family' is not justified. TC0 is defined in Section II.B for boolean circuits over finite inputs, whereas the SDE sampling in Eqs. (3)-(5) uses real-valued states, exact real arithmetic, and Gaussian noise. The cited [HMP+93, Proposition 4.2] derandomizes bounded-depth threshold circuits on boolean inputs; it does not by itself convert a continuous stochastic process into a constant-depth, poly-width boolean circuit with polynomially many advice bits. The proof must specify a finite-precision encoding of x and the score values, a construction of the relevant random bits, the number of repeated samples and the majority circuit, and show that the resulting circuit family has constant depth and polynomial size uniformly in n. Without this, the claimed TC0 membership is not demonstrated.
  3. [Section IV, Turing-completeness construction] The pinball-machine construction is presented informally and lacks a rigorous theorem statement. The force field is described through examples of grooves rather than defined explicitly, and the claim that the leakage probability is of order e^{-L^2} is not proved. The sentence 'for any fixed N,S, because L grows faster than sqrt(ln(NSL)), there exists a big enough L' does not yield a uniform family of diffusions parameterized by input length n, because N and S depend on n and the required L is allowed to grow with them. A precise theorem with quantified probability, running time, uniformity, and Lipschitz-constant bounds is needed before the 'Turing-complete' claim can be evaluated.
minor comments (4)
  1. [Section II.C] The definition of a prefix language modeling problem does not specify how the continuous sample x(T) is mapped to a discrete token, how the context x1,...,xn is encoded, or how the 'correct response' is defined for a probabilistic model. Clarifying these conventions would make the theorem statement unambiguous.
  2. [Section III, Eq. (8)] After substituting T = cc'd^2 into (7), the right-hand side should read log^3(cc'd^2)/(c'd), which is what is written, but the left side is the total variation distance rather than its upper bound; the notation would be clearer if the inequality were written with an explicit bound.
  3. [References] Since the main theorem depends on a precise form of the [LY24] bound, the authors should quote the exact theorem from that preprint and verify that the constants and assumptions match the present setting rather than citing it at the level of an arXiv abstract.
  4. [Footnote 2] The self-referential editorial footnote about a reviewer's comment is out of place in a formal paper and should be removed in the journal version.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the main theorem relies on external discretization and derandomization results, and the Turing-completeness construction is an explicit construction, so no load-bearing step reduces to its own inputs.

full rationale

I walked the derivation chain of the main theorem. The load-bearing analytic input is inequality (7), imported from Li and Yan [LY24], which supplies a distribution-free DDPM discretization bound under exact score matching. This is an external result by different authors, not a self-citation, and it does not assume the paper's TC0 conclusion. The proof then chooses T = c c' d^2, applies the TV bound to transfer the constant-probability margin, and invokes [HMP+93, Proposition 4.2] to derandomize the bounded-depth sampling circuit into TC0. None of these steps defines the conclusion in terms of the assumptions: exact score matching plus a TC0 family of score networks plus external bounds genuinely imply that the language modeling problem is in TC0. The Turing-completeness side is also not circular: it explicitly constructs a smooth force field whose grooves implement a counter machine, relying on [FMR68] for counter-machine universality. This is an existence proof, not a prediction smuggled in from an input. The main caveat, namely whether the [LY24] bound really holds under only E||x0|| ≤ 1, is a correctness risk about an external theorem's hypotheses, not a circular reduction. The inserted reviewer footnote and the sketchiness of the groove construction do not introduce self-reference or definitional circularity. Overall, the paper's derivation chain is self-contained apart from ordinary, non-circular reliance on prior work.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces no new physical entities. The pinball groove field is a mathematical construction rather than a postulated entity, so no 'graviton' style ledger entries apply. The main external load is carried by the [LY24] convergence bound and the derandomization theorem.

assumptions (5)
  • domain assumption The [LY24] total variation bound (Eq. 7) holds with a universal constant c under exact score matching and bounded first moment.
    Section III proof uses this bound as its engine; the paper does not state the precise hypotheses of [LY24], and bounded first moment may be weaker than the cited theorem requires.
  • domain assumption A constant number of TC0 forward passes composed with polynomial-sample majority derandomization ([HMP+93, Prop. 4.2]) remains in TC0 and works for real-valued SDE sampling.
    The proof handwaves the translation from continuous SDE sampling and derandomization of Gaussian randomness into a boolean TC0 circuit; no construction is given.
  • domain assumption A smooth, Lipschitz-bounded vector field can stably guide a Brownian particle along the prescribed counter-machine groove paths with leakage probability arbitrarily small for large L.
    Section IV describes grooves and corner smoothing but does not prove stability or give the force-field formula; the Turing-completeness claim depends on this.
  • standard math Counter machines with the stated instruction set are Turing-complete, and any Turing machine decidable within tape O(f(n)) is decidable by a counter machine in e^{O(f(n))} steps.
    Used in Section IV to reduce Turing machines to pinball trajectories; accepted background in computability theory from [Min67] and [FMR68].
  • domain assumption The state-space dimension d of the diffusion model is constant or at least independent of n, so T=O(d^2) is independent of n.
    Section III says T does not increase with n, but this is only true if d is not growing with n; the theorem does not state this explicitly.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Perfect diffusion is $\mathsf{TC}^0$ -- Bad diffusion is Turing-complete." pith.science (2026). https://pith.science/paper/G7SBKQOG

@misc{pith2026250712469,
  author       = {Pith},
  title        = {Pith review of: Perfect diffusion is $\mathsfTC^0$ -- Bad diffusion is Turing-complete},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G7SBKQOG}},
  note         = {Machine review of arXiv:2507.12469}
}
abstract

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 $\mathsf{TC}^0$ 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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 9 canonical work pages

  1. [1]

    merlin.mbs aapmrev4-1.bst 2010-07-25 4.21a (PWD, AO, DPC) hacked

    FUNCTION id.bst "merlin.mbs aapmrev4-1.bst 2010-07-25 4.21a (PWD, AO, DPC) hacked" ENTRY address archive archivePrefix author bookaddress booktitle chapter collaboration doi edition editor eid eprint howpublished institution isbn issn journal key language month note number organization pages primaryClass publisher school SLACcitation series title translat...

    2010

  2. [2]

    merlin.mbs aipauth4-1.bst 2010-07-25 4.21a (PWD, AO, DPC) hacked

    FUNCTION id.bst "merlin.mbs aipauth4-1.bst 2010-07-25 4.21a (PWD, AO, DPC) hacked" ENTRY address archive archivePrefix author bookaddress booktitle chapter collaboration doi edition editor eid eprint howpublished institution isbn issn journal key language month note number organization pages primaryClass publisher school SLACcitation series title translat...

    2010

  3. [3]

    merlin.mbs aipnum4-1.bst 2010-07-25 4.21a (PWD, AO, DPC) hacked

    FUNCTION id.bst "merlin.mbs aipnum4-1.bst 2010-07-25 4.21a (PWD, AO, DPC) hacked" ENTRY address archive archivePrefix author bookaddress booktitle chapter collaboration doi edition editor eid eprint howpublished institution isbn issn journal key language month note number organization pages primaryClass publisher school SLACcitation series title translati...

    2010

  4. [4]

    merlin.mbs apsrev4-1.bst 2010-07-25 4.21a (PWD, AO, DPC) hacked

    FUNCTION id.bst "merlin.mbs apsrev4-1.bst 2010-07-25 4.21a (PWD, AO, DPC) hacked" ENTRY address archive archivePrefix author bookaddress booktitle chapter collaboration doi edition editor eid eprint howpublished institution isbn issn journal key language month note number organization pages primaryClass publisher school SLACcitation series title translati...

    2010

  5. [5]

    merlin.mbs apsrmp4-1.bst 2010-07-25 4.21a (PWD, AO, DPC) hacked

    FUNCTION id.bst "merlin.mbs apsrmp4-1.bst 2010-07-25 4.21a (PWD, AO, DPC) hacked" ENTRY address archive archivePrefix author bookaddress booktitle chapter collaboration doi edition editor eid eprint howpublished institution isbn issn journal key language month note number organization pages primaryClass publisher school SLACcitation series title translati...

    2010

  6. [6]

    Structured denoising diffusion models in discrete state-spaces

    Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in neural information processing systems , 34:17981--17993, 2021

    2021

  7. [7]

    Reverse-time diffusion equation models

    Brian DO Anderson. Reverse-time diffusion equation models. Stochastic Processes and their Applications , 12(3):313--326, 1982

    work page 1982

  8. [8]

    Block diffusion: Interpolating between autoregressive and diffusion language models

    Marianne Arriola, Subham Sekhar Sahoo, Aaron Gokaslan, Zhihan Yang, Zhixuan Qi, Jiaqi Han, Justin T Chiu, and Volodymyr Kuleshov. Block diffusion: Interpolating between autoregressive and diffusion language models. In The Thirteenth International Conference on Learning Representations , 2025

    work page 2025

Show all 25 references
  1. [9]

    Diffusion models beat gans on image synthesis

    Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances in neural information processing systems , 34:8780--8794, 2021

    2021

  2. [10]

    Counter machines and counter languages

    Patrick C Fischer, Albert R Meyer, and Arnold L Rosenberg. Counter machines and counter languages. Mathematical systems theory , 2(3):265--283, 1968

    1968

  3. [11]

    Towards revealing the mystery behind chain of thought: a theoretical perspective

    Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: a theoretical perspective. Advances in Neural Information Processing Systems , 36:70757--70798, 2023

    2023

  4. [12]

    Diffuseq: Sequence to sequence text generation with diffusion models

    Shansan Gong, Mukai Li, Jiangtao Feng, Zhiyong Wu, and LingPeng Kong. Diffuseq: Sequence to sequence text generation with diffusion models. arXiv preprint arXiv:2210.08933 , 2022

    2022 arXiv

  5. [13]

    Threshold circuits of bounded depth

    Andr \'a s Hajnal, Wolfgang Maass, Pavel Pudl \'a k, Mario Szegedy, and Gy \"o rgy Tur \'a n. Threshold circuits of bounded depth. Journal of Computer and System Sciences , 46(2):129--154, 1993

    1993

  6. [14]

    Variational diffusion models

    Diederik Kingma, Tim Salimans, Ben Poole, and Jonathan Ho. Variational diffusion models. Advances in neural information processing systems , 34:21696--21707, 2021

    2021

  7. [15]

    Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang

    Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. In The Eleventh International Conference on Learning Representations , 2023

    2023

  8. [16]

    Chain of thought empowers transformers to solve inherently serial problems

    Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. arXiv preprint arXiv:2402.12875 , 2024

    2024 arXiv

  9. [17]

    Understanding diffusion models: A unified perspective

    Calvin Luo. Understanding diffusion models: A unified perspective. arXiv preprint arXiv:2208.11970 , 2022

    2022 arXiv

  10. [18]

    O (d/t) convergence theory for diffusion probabilistic models under minimal assumptions

    Gen Li and Yuling Yan. O (d/t) convergence theory for diffusion probabilistic models under minimal assumptions. arXiv preprint arXiv:2409.18959 , 2024

    2024 arXiv

  11. [19]

    Computation: Finite and Infinite Machines

    Marvin Minsky. Computation: Finite and Infinite Machines . Prentice-Hall, 1967

    1967

  12. [20]

    The illusion of state in state-space models

    William Merrill, Jackson Petty, and Ashish Sabharwal. The illusion of state in state-space models. arXiv preprint arXiv:2404.08819 , 2024

    2024 arXiv

  13. [21]

    The parallelism tradeoff: Limitations of log-precision transformers

    William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics , 11:531--545, 2023

    2023

  14. [22]

    Parallel computation with threshold functions

    Ian Parberry and Georg Schnitger. Parallel computation with threshold functions. Journal of Computer and System Sciences , 36(3):278--302, 1988

    1988

  15. [23]

    Scaling properties of diffusion models for perceptual tasks

    Rahul Ravishankar, Zeeshan Patel, Jathushan Rajasegaran, and Jitendra Malik. Scaling properties of diffusion models for perceptual tasks. arXiv preprint arXiv:2411.08034 , 2024

    2024 arXiv

  16. [24]

    Deep unsupervised learning using nonequilibrium thermodynamics

    Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International conference on machine learning , pages 2256--2265. pmlr, 2015

    2015

  17. [25]

    Spatial reasoning with denoising models

    Christopher Wewer, Bart Pogodzinski, Bernt Schiele, and Jan Eric Lenssen. Spatial reasoning with denoising models. arXiv preprint arXiv:2502.21075 , 2025

    2025 arXiv

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.