{"id":"d90fb12a-f230-4600-821e-9c21b80d211f","arxiv_id":"2507.12469","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Perfect diffusion models with TC0 score networks are computationally limited to TC0, while unconstrained diffusion-like SDEs can be Turing-complete.","lead":"A theory paper argues that a diffusion language model whose score network is perfect and small (TC0) can only solve problems in a limited parallel complexity class, while a deliberately imperfect network can simulate any Turing machine. The result gives a complexity-theoretic explanation for why diffusion models struggle with sequential reasoning tasks.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem depends on an unverified distribution-free bound from [LY24]; under only E||x0||≤1, the DDPM step count may need to grow with n, breaking the TC0 conclusion.","rationale":"The reader's weakest assumption is exactly the importation of inequality (7) from [LY24] with a universal constant under only a bounded first moment, and I agree that this is the most load-bearing step. If the [LY24] bound is not distribution-free, the universal-T construction collapses because T can depend on properties of ρ0,n that vary with n. The proof's response—choosing T = cc'd^2 and noting that d does not grow with n—only works if the constant c in Eq. (7) is genuinely independent of the target distribution. The paper gives no derivation or statement of the cited theorem, so the conditional is the right verdict. A secondary but less severe gap is the derandomization step: the 'majority output' language is only justified if the correct token has probability greater than 1/2, whereas definition (6) gives only a margin over every incorrect token; for alphabets of size greater than 2 this would need a plurality argument with a union bound over prefixes. That issue is repairable, whereas a failure of the [LY24] bound would threaten the theorem itself. For these reasons I do not change the reader's CONDITIONAL verdict, but the concrete test above should be run before the theorem is accepted as stated.","tokens_in":9493,"tokens_out":18491,"duration_ms":189799,"concrete_test":"Obtain [LY24] (arXiv:2409.18959), locate the theorem cited for Eq. (7), and verify its hypotheses: does the bound hold for every distribution with only E||x0|| ≤ 1, or does it require a finite second-moment bound, a Lipschitz score, or a constant/step count depending on the target distribution? Then rerun the Section III argument with the family ρ_n = (1−1/n)δ_0 + (1/n)δ_n (after mollification so scores exist). If the number of DDPM steps T(n) needed to reach TV error ≤ ε/2 grows with n, the claim that T is independent of n is refuted and the proof needs a different argument. This check is analytical and can be done with the OU semigroup convergence rates.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Section III has two substantive steps: the [LY24] discretization bound (Eq. 7) and the derandomization into TC0. The first is load-bearing. The theorem assumes only E_{ρ0,n}||x0|| ≤ 1, but Eq. (7) is invoked as TV(ρ_DDPM,T, ρ_x̂,0) ≤ c d (log T)^3 / T with a universal constant c independent of n, d, and ρ0,n. That requires the [LY24] bound to be distribution-free under only a first-moment condition, which is not obviously true. The OU forward process forgets an initial distribution of variance R only after time O(log R), so a data distribution satisfying E||x0|| ≤ 1 but with E||x0||^2 growing with n (e.g., ρ_n = (1−1/n)δ_0 + (1/n)δ_n, mollified so scores exist) has scores that remain non-Gaussian for a duration growing with log n. If [LY24]'s constant c, or the required number of DDPM steps T, depends on the second moment or on a distribution-dependent constant, then the sentence 'The key is that T does not increase with n' fails: T must grow with n, the sampling circuit's depth grows with n, and the TC0 conclusion does not follow as stated. The paper neither states the exact hypotheses of [LY24] nor reproduces its theorem, so this dependency is unchecked.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":9874,"tokens_out":5592,"duration_ms":56975,"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":[{"comment":"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.","section":"Section III, Eq. (7)"},{"comment":"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.","section":"Section III, derandomization step"},{"comment":"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.","section":"Section IV, Turing-completeness construction"}],"minor_comments":[{"comment":"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.","section":"Section II.C"},{"comment":"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.","section":"Section III, Eq. (8)"},{"comment":"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.","section":"References"},{"comment":"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.","section":"Footnote 2"}],"recommendation":"major_revision","confidential_remarks":"The central idea is interesting and worth publishing if made rigorous, but the main theorem currently depends on an unverified external bound and on an unformalized conversion of a continuous stochastic process into a TC0 Boolean circuit. I am recommending major revision rather than rejection because the gaps are identifiable and potentially fixable within the manuscript's scope. The 'bad diffusion is Turing-complete' direction is largely definitional, since an unconstrained drift field can be programmed arbitrarily; the paper should be explicit about that limitation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper is worth reading, but the load-bearing theorem is not established as stated. The novel idea is a clean dichotomy: a diffusion model with exactly matching score functions is computationally shallow (TC0) when solving prefix language modeling, while abandoning the score-matching requirement entirely lets you build a Turing-complete SDE. That packaging is new and it connects to real empirical observations about diffusion language models failing on sequential tasks. Credit where due: the paper is clearly written and the author explicitly flags the approximate-score case as open (Section V.A), which is an honest limitation.\n\nThe soft spot is in Section III. Inequality (7) is imported from [LY24] without its hypotheses. The paper claims a universal constant c under only E||x0||≤1 and then sets T = cc'd^2, asserting 'T does not increase with n.' This is doing heavy lifting. [LY24] almost certainly needs at least a finite second moment, and even then the mixing time of the forward OU process depends on the distribution's tail. A simple example—(1−1/n)δ0 + (1/n)δ_n—has first moment 1 but second moment n, and the score is far from Gaussian for O(log n) time. So T would have to grow with n, making the sampling circuit depth non-constant, and the TC0 conclusion fails. The paper never clarifies whether d is constant in n; if d grows with the input length, T=O(d^2) is not constant either.\n\nThe derandomization step is also under-specified. Turning continuous SDE sampling with Gaussian noise into a boolean TC0 circuit requires discretizing randomness and showing a single non-uniform advice string works for exponentially many inputs. Hoeffding alone doesn't give that: with constant margin ε, the union bound fails. [HMP+93, Prop. 4.2] may do it, but the paper should state the proposition and verify the conditions.\n\nNone of this makes the paper worthless. The bad-side construction is a nice illustration of how unconstrained drift buys unlimited power, and the conjectures about approximate scores are reasonable. But as a formal result, the perfect-side theorem needs substantial repair. I'd send it to a serious referee because the question is important and the paper's thesis is original; the referee should ask for a correct, explicit discretization bound and a full derandomization argument.\n\nFor a reading group, it would spark a good debate about what 'perfect score' means and whether the TC0 framing is the right one. I wouldn't cite the theorem as proven, though I might cite the question as motivation.\n\nBest,","headline":"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.","tokens_in":10284,"tokens_out":5854,"would_cite":false,"duration_ms":53489,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Perfectly score-matched diffusion models compute only within TC0, while deliberately bad diffusion processes can simulate any Turing machine.","keywords":["diffusion models","TC0","circuit complexity","score matching","language modeling","Turing completeness","counter machines","computational complexity"],"falsifier":"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.","tokens_in":9249,"feed_emoji":"🧮","tokens_out":11963,"duration_ms":98220,"temperature":0.7,"pith_summary":"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.","feed_headline":"Perfect diffusion stays shallow; bad diffusion is Turing-complete","feed_subtitle":"A theorem pins exact-score diffusion to the constant-depth class TC0 unless the score is allowed to be arbitrary.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the universal total-variation bound $\\mathrm{TV} \\leq c d (\\log T)^3 / T$ under exact score matching, the inequality the TC0 proof hinges on.","marker":"[LY24]"},{"why":"Provides Proposition 4.2 used to derandomize the constant-probability sampler into a deterministic TC0 circuit family.","marker":"[HMP+93]"},{"why":"Establishes the exact reverse-time SDE that lets a perfect score function reproduce the initial distribution, the formal basis for 'exact score'.","marker":"[And82]"},{"why":"Shows counter machines with exponentially many steps decide languages decidable by bounded-tape Turing machines, used to size the pinball machine.","marker":"[FMR68]"},{"why":"Establishes that two-register counter machines simulate universal Turing machines, grounding the claim that the pinball construction is Turing-complete.","marker":"[Min67]"},{"why":"Gives the DDPM/SMLD equivalence that lets the convergence bound for DDPM be transferred to the SMLD framework used in the theorem.","marker":"[KSPH21]"}],"fun_headline_variants":["Perfect diffusion is shallow, bad diffusion is powerful","Exact score? TC0. Arbitrary score? Turing-complete","Diffusion dichotomy: exact scores stay shallow, loose scores go full Turing","Perfect score keeps diffusion in TC0; bad score unlocks Turing power","Score matching exact? Constant depth. Score arbitrary? Universal computation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Perfect diffusion is shallow, bad diffusion is powerful","Exact score? TC0. Arbitrary score? Turing-complete","Diffusion dichotomy: exact scores stay shallow, loose scores go full Turing","Perfect score keeps diffusion in TC0; bad score unlocks Turing power","Score matching exact? Constant depth. Score arbitrary? Universal computation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000211,"raw_usage":{"total_tokens":1393,"prompt_tokens":900,"completion_tokens":493,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":516,"completion_tokens_details":{"reasoning_tokens":405}},"tokens_in":516,"tokens_out":493,"duration_ms":4419,"temperature":1.0,"reasoning_tokens":405,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:42:44.501625+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}