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.
One forward pass is weak, and provably so
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$.
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.
Serial steps buy computation, gradually
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 extra tokens are not, in the theory, meaningful reasoning: they are computation slots.
Merrill & Sabharwal (2024) give the graded version, and it is worth quoting the shape of it precisely because the intermediate cases are the interesting ones:
| CoT steps | Reachable class | Caveat |
|---|---|---|
| $T = O(\log n)$ | Only marginally beyond the no-CoT baseline. | — |
| $T = O(n)$ | Recognises all regular languages; upper-bounded by context-sensitive. | Requires a projected pre-norm architecture. |
| $T = \mathrm{poly}(n)$ | Exactly $\mathsf P$: as powerful as polynomial-time Turing machines. | Requires a generalised pre-norm architecture. |
The poly case is the first exact characterisation of a transformer variant by a standard complexity class. The caveats decide the result. These are theorems about particular normalisation variants, not about whatever architecture a lab happens to ship.
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, made rigorous
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) characterise which problems admit 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.
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.
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 paper explicitly distinguishes these from full sequence-state loops carrying $ndp$ bits, which are not covered. Recurrence buys depth. It does not, in the compressed regime, buy memory.
Reddi et al. (2025) establish the positive counterpart for depth specifically: $k$ layers looped $L$ times nearly matches $kL$ unlooped layers, so problems that are depth-bound rather than parameter-bound are exactly the ones loops help with.
On the empirical side, Zhu et al. (2025) prove a two-layer transformer with $D$ continuous steps solves directed graph reachability for diameter $D$ where the best known discrete construction needs $O(n^2)$ steps, and show the superposition that makes this work emerges from training rather than being built in. Gozeten et al. (2025) quantify the parallelism as tracking several discrete traces at once, with a constructive one-layer solution to subset-sum.
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 need to be 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$. Worth keeping 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.
- The filler-token toolkit (finite model theory, quantifier depth, $\mathsf{AC}^0$ separations) and the continuous-thought toolkit (circuit-depth iteration, superposition arguments) have no known reduction between them, despite describing the same phenomenon from two sides.
- No theory predicts the minimal number of steps a given task needs. The results are existential. The practical question of reasoning-token budgets is untouched by them.