Expressivity results
Stated carefully, because the complexity claims in this area are routinely garbled.
A single forward pass has a known upper bound, and serial token steps have a known effect on it. Both results are settled in outline. Whether a continuous step is worth more than a discrete one rests on one sharp theorem, and that theorem is conditional.
The bound on a single forward pass
Merrill & Sabharwal (2023) show that a log-precision transformer, poly-size, with log-space-computable feedforward blocks, can be simulated by constant-depth, logspace-uniform threshold circuits. In symbols, it sits inside uniform $\mathsf{TC}^0$.
logspace-uniform $\mathsf{TC}^0$
The problems decided by Boolean circuit families of constant depth and polynomial size, built from AND, OR, NOT and threshold gates, all with unbounded fan-in. A threshold gate fires when at least $k$ of its inputs are on, which is what lets these circuits count.
Uniform means the circuit for each input length can itself be built by an algorithm, here one restricted to logarithmic workspace. Without that condition a circuit family can smuggle in arbitrary precomputed advice, including uncomputable advice, and the bound stops describing anything a real machine does.
Constant depth is the part that bites. A transformer with a fixed number of layers is a constant-depth circuit, so whatever cannot be done in constant depth cannot be done in one forward pass, at any width.
The consequence is conditional: if $\mathsf L \neq \mathsf P$, no family of such transformers of polynomial size can solve certain $\mathsf P$-complete problems in a single pass. This is the parallelism tradeoff: fixed depth means a fixed-depth parallel circuit, and the property that makes transformers efficient to run is the same property that caps what one pass can do.
Scope of the bound
It is an asymptotic statement about families of circuits over arbitrarily growing inputs, within a polynomial-size regime. It is not a prohibition on a particular model solving a particular finite benchmark instance, and it does not say that growing the model never helps in practice. Arguments of the form “$\mathsf{TC}^0$, therefore this model cannot do arithmetic” do not follow.
Li, Liu, Zhou & Ma (2024) tighten this under a different precision assumption: with constant bit precision and constant depth and no chain of thought, expressivity is confined to $\mathsf{AC}^0$, a strict subset of $\mathsf{TC}^0$. The precision regime is not a technicality: it moves the answer by a complexity class, and papers in this area are often compared as though it does not.
$\mathsf{AC}^0$, and why PARITY sits outside it
$\mathsf{AC}^0$ is $\mathsf{TC}^0$ without the threshold gates: constant depth, polynomial size, unbounded fan-in AND, OR and NOT. It is strictly weaker, and PARITY, the question of whether an input has an odd number of ones, is the classical witness. Computing it requires counting, threshold gates count, and AND/OR gates at constant depth cannot.
This is why PARITY cannot witness a separation inside $\mathsf{AC}^0$. It is not in the class at either end.
Serial steps and circuit size
Chain of thought converts token count into a serial computation budget. Li et al. state it most directly: $T$ steps of chain of thought let a constant-depth, constant-precision transformer simulate Boolean circuits of size $O(T)$. The construction is non-uniform, so a separate $O(\log n)$-width transformer is built for each input length and target circuit, with the circuit description carried in learned absolute positional embeddings. That makes it a representability result rather than one model acquiring a general serial interpreter. The extra tokens are not, in the theory, meaningful reasoning: they are computation slots.
Merrill & Sabharwal (2024) give the graded version. The intermediate cases carry the content:
| CoT steps | Reachable class | Caveat |
|---|---|---|
| $T = O(\log n)$ | Only marginally beyond the no-CoT baseline. | Upper bound only, with no matching lower bound. |
| $T = O(n)$ | Recognises all regular languages. Upper-bounded by context-sensitive. | Projected pre-norm, strict causal saturated attention. |
| $T = \mathrm{poly}(n)$ | Exactly $\mathsf P$: as powerful as polynomial-time Turing machines. | Projected pre-norm, strict causal attention. Stated as an equality, the first for a transformer variant. |
The poly case is the first exact characterisation of a transformer variant by a standard complexity class. The caveats decide the result, and they are architectural rather than incidental. Both constructions assume projected pre-norm, a normalisation variant introduced to make them work, and saturated attention, in which every attention score is either zero or $1/v$. That is idealised averaging hard attention, not the softmax any deployed model uses.
Two corrections to how this result is often relayed. The tiers are not distinguished by normalisation: the headline theorems for both the linear and the polynomial case are stated for projected pre-norm, with multi-pre-norm appearing as a shared proof device that projected pre-norm can simulate. And the log tier is an upper bound only, $\mathsf{CoT}(O(\log n)) \subseteq \mathsf L$, with no matching lower bound.
Feng et al. (2023) give the applied complement, and their premise matters. Assuming $\mathsf{TC}^0 \neq \mathsf{NC}^1$, their Theorems 3.1 and 3.2 state that for any prime $p$, any fixed depth $L$ and any polynomial $Q$, there is a problem size at which no log-precision autoregressive transformer of depth $L$ and hidden dimension $d \leq Q(n)$ solves arithmetic-expression evaluation, or linear-equation solving, over the finite field $\mathbb{Z}_p$. Constant-size autoregressive transformers with chain of thought can do both, and can implement a general class of dynamic programming algorithms.
The scope is those two specified problem families over finite fields, not “basic arithmetic” in general. And the lower bound is supplied by circuit-complexity reasoning under an explicit conjecture: it is not an unconditional size-blowup result.
Contentless tokens
If the theory says intermediate tokens are computation slots, then slots with no content should work. London & Kanade (2025) prove this for pause tokens, and the statement needs its qualifiers to be true.
| Result | Statement | Regime |
|---|---|---|
| Thm 4.1 | Transformers with polynomially many pause tokens characterise exactly $\mathsf{AC}^0$. | Constant precision, $O(\log n)$ embedding width, polynomial padding. |
| Cor 4.2 | Strict separation: without pause tokens $\subsetneq$ with polynomial pause tokens. | Non-uniform, via a circuit-size hierarchy. |
| Thm 4.3 | The corresponding fixed-depth separation in the uniform setting. | Requires quasi-polynomial padding, not polynomial. |
| Thm 4.5 | With logarithmic precision, polynomial padding characterises $\mathsf{TC}^0$. | Log precision, polynomial padding. |
The uniform and non-uniform statements are different theorems with different padding requirements and should not be compressed into one line. What padding buys, in the authors' own framing, is parallel workspace at fixed layer depth: not additional serial computational depth. That distinction is the whole reason contentless tokens are not simply a free substitute for chain of thought.
PARITY is not the witness for this separation
Full-input PARITY lies outside $\mathsf{AC}^0$, so it cannot witness a strict containment within $\mathsf{AC}^0$. PARITY appears in the paper's Section 5 as a finite-size learning experiment on a 2-layer, 4-head GPT-2-style model, motivated by the logarithmic-precision regime, and it requires explicit intermediate supervision, threshold “hint” labels $t_j = \mathbb{I}[\sum_i x_i \geq j]$, because, as the authors note, gradient training of a shallow transformer “struggles to learn parity using only the loss on the final prediction.” That is an observation about learnability, not a proof of expressivity, and the two were conflated here.
Pfau, Merrill & Bowman (2024) give a sufficient condition for a filler-token benefit via the quantifier depth of a first-order formula describing the problem. Within the right quantifier-depth class, the intermediate tokens need carry no information about intermediate steps at all. It is a condition under which fillers suffice, not a characterisation of every problem they help. A problem of quantifier depth $k$ is expressible with $n^k$ filler tokens, and their two tasks, 3SUM and 2SUM-Transform, sit above depth two while remaining parallelisable.
Their own conclusion is more restrained than the result is usually taken to be. The experiments train a small transformer from scratch under dense supervision on synthetic tasks, and the authors judge that current language models are “unlikely to benefit from filler tokens,” while holding that this is not an in-principle limitation of the architecture. The paper is evidence about what transformers can be made to do, not about what deployed models are doing.
Quantifier depth
How deeply nested the quantifiers are in a first-order formula describing a problem: $\forall x\, \exists y\, P(x,y)$ has depth two. It is a measure of logical complexity independent of formula length, and it is the axis along which filler tokens are shown to help or not.
$\mathsf{TC}^k$, and why the separation is conditional
$\mathsf{TC}^k$ allows the same threshold circuits a depth of $O(\log^k n)$ rather than a constant, giving a hierarchy $\mathsf{TC}^0 \subseteq \mathsf{TC}^1 \subseteq \cdots$.
No containment in that hierarchy is known to be strict. A result of the form “continuous steps reach $\mathsf{TC}^k$ and discrete steps only $\mathsf{TC}^{k-1}$” therefore separates the two only if $\mathsf{TC}^{k-1} \subsetneq \mathsf{TC}^k$, which is believed and unproven. The theorem is real; the separation it implies inherits an open problem.
Continuous versus discrete steps
This is the question the field actually turns on, and there is one sharp theorem. Xu & Sato (2025) prove that iterating continuous latent thought to polylog depth reaches $\mathsf{TC}^k$, while discrete-token chain of thought at the same depth budget reaches only $\mathsf{TC}^{k-1}$.
The statement carries three qualifications.
- The separation is conditional. Theorem 3.15 gives $\mathsf{CoT} \subsetneq \mathsf{Loop}$ at $\log^k n$ iterations assuming $\mathsf{TC}^{k-1} \subsetneq \mathsf{TC}^k$. Deterministic decoding alone is not sufficient. A believed but unproven circuit-class separation is doing real work.
- The latent side is a characterisation. The CoT side is only an upper bound. Theorem 3.12 characterises the looped/continuous classes exactly at polylogarithmic iterations, polynomial width, and constant precision (or $\mathsf{TC}^k$ at logarithmic precision). Lemma 3.13 gives $\mathsf{CoT} \subseteq \mathsf{TC}^{k-1}$: an upper bound. Treating that containment as an exact characterisation overstates it.
- The stochastic comparison has its own premise. The counting and sampling advantage assumes $\mathsf{FPTAS} \subsetneq \mathsf{FPRAS}$ for self-reducible relations. It compares intermediate-token sampling against deterministic latent updates, and is not a general impossibility result for stochastic latent computation. Latent models may still sample their final output tokens.
These are asymptotic statements with explicit iteration budgets, width and precision conditions. They are not equal-FLOP or equal-parameter comparisons, and should not be cited as though a practitioner choosing between two 3B models were the setting. The same authors' earlier comparison lands in the same place: loops efficiently emulate parallel, DAG-structured deterministic computation, while sequential CoT suits self-reducible, compositionally sequential problems: complementary resources, not a ranking.
$\mathsf P$-complete under logspace reductions, and $\mathsf{DSPACE}(\mathrm{polylog}\,n)$
A problem is $\mathsf P$-complete under logspace reductions when it lies in $\mathsf P$ and every other problem in $\mathsf P$ can be transformed into it by an algorithm using only logarithmic workspace. These are the hardest polynomial-time problems, and the ones believed to resist parallelisation.
$\mathsf{DSPACE}(\mathrm{polylog}\,n)$ is what a deterministic machine can decide with polylogarithmic working memory. The assumption $\mathsf P \not\subseteq \mathsf{DSPACE}(\mathrm{polylog}\,n)$ says some polynomial-time problems genuinely need more memory than that, which is what makes a fixed-size recurrent state insufficient where a growing transcript is not.
Two results bound the enthusiasm. Zhang (2026) proves a memory-budget separation, under a standard complexity assumption (the paper's simulation runs in $O(sdp + \log n + \log T)$ space, with the separation resting on $\mathsf P \not\subseteq \mathsf{DSPACE}(\mathrm{polylog}\, n)$): a compressed-state looped transformer, carrying polylogarithmic persistent memory with a bounded iteration counter, cannot decide problems $\mathsf P$-complete under logspace reductions that polynomial-length chain of thought can. The bound is explicitly narrow. It does not cover full sequence-state loops carrying $ndp$ bits, loops with appended scratch positions, stochastic decoding, or any architecture whose persistent state grows with the context, and the author describes the accompanying experiments as finite-size probes of the state-budget effect rather than tests of the asymptotic theorem. Recurrence buys depth. It does not, in the compressed regime, buy memory.
Saunshi et al. (2025) report the positive counterpart for depth: on the reasoning tasks they study, $k$ layers looped $L$ times comes close to $kL$ unlooped layers, which suggests looping helps where a problem is bound by depth rather than by parameter count. The comparison is empirical on those tasks, not a general equivalence.
On the empirical side, Zhu et al. (2025) prove a two-layer transformer with $D$ continuous steps solves directed graph reachability for diameter $D$, for a fixed maximum input length and at width growing with the vocabulary. The best known constant-depth discrete-CoT construction needs $O(n^2)$ steps, and no lower bound is proved, so there is no separation. Trained two-layer models show the frontier in attention and embedding similarity, which is observational. Gozeten et al. (2025) quantify the parallelism as tracking several discrete traces at once. Their construction is a single block run for $n$ autoregressive steps at width $2^{n+1}+n+2$, holding every one of the $2^n$ signed partial sums, with $n+1$ position-specific experts and exact selection only in a hard-selection limit. It demonstrates representability through superposition rather than an efficient algorithm.
$\mathsf{FPTAS}$ and $\mathsf{FPRAS}$
Both are schemes that approximate a quantity to within any chosen relative error, in time polynomial in the input and in one over that error. The difference is randomness. An $\mathsf{FPTAS}$ is deterministic, while an $\mathsf{FPRAS}$ may use random bits and need only succeed with high probability.
$\mathsf{FPTAS} \subsetneq \mathsf{FPRAS}$ says randomisation genuinely helps for approximate counting. That is the assumption behind the claim that stochastic decoding gives discrete chains something deterministic latent iteration cannot match.
Expressivity versus learnability
Every result above is about what can be expressed. None is about what gradient descent will find. The empirical record is blunt about the difference: filler tokens need dense task-specific supervision before a model learns to use them, pause tokens give their large gains only when present in both pretraining and fine-tuning, and naive thinking tokens underperform real chain of thought outright. An expressivity theorem guarantees a construction exists in weight space. It says nothing about whether training reaches it, and in this literature it frequently does not.
Open theoretical questions
- No unconditional characterisation connects realistic finite-precision transformers under actual training dynamics to a complexity class. The sharp theorems assume particular pre-norm variants and precision regimes. Whether they survive the architectures shipped in practice is open.
- The $\mathsf{TC}^k$ versus $\mathsf{TC}^{k-1}$ separation is essentially the only theorem of its kind, and it is conditional on $\mathsf{TC}^{k-1} \subsetneq \mathsf{TC}^k$. Keep the two distinct: the latent-side characterisation is already quantified, whereas the strict separation inherits an unproved class separation. Whether realistic finite-precision continuous states retain the advantage is also open. Precision is known to be decisive in the discrete case.
- Is the separation about discreteness or about determinism? Stochastic decoding is what gives discrete CoT its counting and sampling power. Whether injecting noise into a continuous latent channel recovers it is unaddressed.
- Padding and looping are now analysed together, with threshold-circuit characterisations, in Merrill and Sabharwal (2025). What that does not yet reach is the superposition and parallel-trace line of argument, which remains separate from both. The filler-token toolkit (finite model theory, quantifier depth, $\mathsf{AC}^0$ separations) and the superposition arguments describe the same phenomenon from two sides with no known reduction between them.
- Minimal step counts are known only for particular tasks in a restricted model. Amiri et al. (2025) prove worst-case lower bounds on chain-of-thought length for unique-hard-attention transformers with a bounded number of layers and heads. Parity and Median need $\Omega(N)$ steps and reachability on a family of DAGs needs $\Omega(|E|\log|V|)$, each bound attained by a construction. A middle bit of a product of two $N$-bit numbers needs $\Omega(N)$, and the full product has a scratchpad of length $\Theta(N\log N)$. No theory yet predicts the budget a trained softmax model needs on a given instance of a natural-language task. The authors list other transformer models and average-case bounds as open.