Chain-of-Thought and Computational Expressivity in Transformers: Mathematical Foundations, Circuit Complexity Limits, and Sequential Reasoning Mechanics

Standard autoregressive Transformers generate text by computing token representations through a fixed stack of attention and feed-forward layers. When evaluated on complex reasoning, mathematical derivation, or multi-step algorithmic execution, standard models attempting to produce direct answers frequently fail. Introducing intermediate reasoning tokens through scratchpads and Chain-of-Thought (CoT) prompting eliminates these failure modes across diverse problem domains.

While early empirical evaluations framed Chain-of-Thought as semantic prompting guidance, theoretical investigations in circuit complexity reveal a more fundamental principle: direct generation in fixed-depth Transformers is fundamentally restricted in expressive power, whereas intermediate token generation fundamentally expands the computational complexity class of the architecture.

The Circuit Complexity of Fixed-Depth Transformers

In theoretical computer science, circuit complexity measures the computational resources required to evaluate functions using networks of logic gates. A standard autoregressive Transformer consists of a fixed number of layers $L$, a hidden dimension $d$, and attention heads operating with finite or logarithmic numerical precision.

When an autoregressive Transformer predicts an output token directly from an input of length $n$ without generating intermediate scratchpad tokens, the computation graph from inputs to the first output token has constant depth $O(L)$. Merrill and Sabharwal (2022, 2023) established the formal equivalence between constant-depth, log-precision Transformers and the circuit complexity class uniform $\text{TC}^0$:

• $\text{TC}^0$ Definition: The class of languages recognized by Boolean circuits of constant depth ($O(1)$) and polynomial size ($\text{poly}(n)$), constructed with unbounded fan-in AND, OR, NOT, and majority (threshold) gates.
• Attention as Soft Majority: Softmax self-attention with log-precision weights operates as a continuous, differentiable generalization of threshold and majority voting gates across token positions.
• Feed-Forward Blocks as Constant-Depth Mappings: Pointwise multi-layer perceptrons (MLPs) apply non-linear activations independently across positions, which evaluate within constant circuit depth.

Because the full forward pass across all $L$ layers executes in parallel across the sequence, a zero-step Transformer cannot perform more sequential computational steps than its architectural depth $L$.

Impossibility Results for Direct Prediction

Under the widely held complexity assumption that $\text{TC}^0 \subsetneq \text{NC}^1 \subseteq \text{P}$, constant-depth Transformers without intermediate tokens cannot solve computational problems requiring sequential state tracking or non-trivial depth:

1. Regular Language Recognition and Finite State Automata: Standard Transformers cannot simulate arbitrary deterministic finite automata (DFAs) or compute string parity across arbitrary input lengths $n$.
2. Graph Connectivity: Determining whether a path exists between two nodes ($s-t$ connectivity) in an arbitrary directed graph cannot be computed in uniform $\text{TC}^0$.
3. Context-Free Grammar Parsing: Checking membership for arbitrary context-free grammars (such as Dyck path validity or arithmetic expression evaluation) exceeds $\text{TC}^0$ capabilities.
4. Multi-Digit Arithmetic and Permutation Composition: Evaluating multi-step modular equations or sequential arithmetic chains cannot be solved in constant depth without expanding the hidden dimension super-polynomially.

When a fixed-depth model attempts to output the final answer to an $n$-step problem in a single forward pass, it must compress an inherently sequential computation into a shallow parallel circuit. If the required circuit depth grows with $n$, direct prediction is mathematically impossible for fixed $L$.

Autoregressive Generation as Dynamic Circuit Unrolling

Chain-of-Thought prompting and scratchpad mechanisms alter the computational model. Instead of predicting the answer $y$ immediately given input sequence $x = (x_1, \dots, x_n)$, the model generates a sequence of intermediate reasoning tokens $z = (z_1, z_2, \dots, z_T)$ before producing $y$:

$$P(y \mid x) = \sum_{z} \prod_{t=1}^{T} P(z_t \mid x, z_{<t}) \cdot P(y \mid x, z)$$

At each step $t$, the Transformer executes a single forward pass to compute token $z_t$. While each individual step remains a constant-depth $\text{TC}^0$ operation, conditioning token $z_{t+1}$ on the entire preceding sequence $(x, z_1, \dots, z_t)$ via causal attention unrolls an effective computation graph of depth proportional to $T \cdot L$.

Expressive Power Scaling by Reasoning Length

Recent theoretical work by Merrill & Sabharwal (2024), Feng et al. (2023), and Li et al. (2024) characterizes how the length of the intermediate chain $T(n)$ governs the expressive power of the model:

• Sublinear CoT ($T(n) = o(n)$): If the model generates fewer than linear intermediate tokens, it remains largely bounded within shallow complexity classes, offering limited separation from $\text{TC}^0$.
• Linear CoT ($T(n) = O(n)$): Generating $O(n)$ scratchpad tokens allows the Transformer to maintain and update a dynamic internal state. A linear chain of thought enables constant-size Transformers to simulate any finite automaton, parse Dyck-k languages, solve linear equations over finite fields, and recognize languages in logarithmic space ($\text{L}$) and $\text{NC}^1$.
• Polynomial CoT ($T(n) = \text{poly}(n)$): With polynomially many intermediate tokens, a constant-depth Transformer can simulate any polynomial-size Boolean circuit or deterministic Turing machine operating in polynomial time. This unlocks exact solutions for $\text{P}$-complete problems, including Horn-clause satisfiability, Context-Free Language parsing (CYK algorithm), and general Dynamic Programming algorithms.
• Unbounded Scratchpads ($T(n) \to \infty$): When permitted an unbounded sequence length, autoregressive attention with a read-write scratchpad is Turing-complete (Perez et al., 2021).

Algorithmic Decomposition in Intermediate Tokens

The expansion in expressive power stems from how intermediate tokens decompose global, deep computations into local, shallow operations.

Carry Propagation in Multi-Digit Arithmetic

In multi-digit addition or multiplication, direct prediction requires computing carries across long dependencies. Carry propagation across $n$ digits requires logarithmic depth ($\text{NC}^1$), which exceeds $\text{TC}^0$ when precision is bounded.

When generating a step-by-step scratchpad:

1. Each intermediate token represents a single digit calculation and the local carry state for position $i$.
2. The model looks up the inputs at position $i$ and the previously emitted carry token from step $i-1$.
3. The local calculation $c_i = \lfloor (a_i + b_i + c_{i-1}) / 10 \rfloor$ is an $O(1)$ lookup easily computed within a single Transformer layer.

By emitting the intermediate carry $c_i$ explicitly, the model converts a global depth-$O(\log n)$ circuit into $n$ sequential depth-$O(1)$ operations.

Dynamic Programming Execution

Feng et al. (2023) demonstrated that autoregressive Transformers with CoT can systematically execute arbitrary Dynamic Programming (DP) algorithms. Consider the state transition:

$$S[i, j] = \min_{k} \left( S[i, k] + S[k, j] \right)$$

Computing the entire matrix $S$ simultaneously is intractable in constant depth. When guided to emit state entries $S[i, j]$ sequentially in topological order:

1. Previously computed entries $S[i, k]$ and $S[k, j]$ are stored in the key-value (KV) cache as previously generated tokens.
2. The attention mechanism retrieves the relevant values via positional index matching.
3. The feed-forward layer performs the addition and pairwise minimization across $k$.
4. The resulting value $S[i, j]$ is written to the output context, becoming accessible for subsequent state derivations.

Engineering Implications for Modern Reasoning Models

The theoretical equivalence between reasoning token count and effective circuit depth explains key architectural patterns in modern LLMs:

1. Test-Time Compute as Circuit Depth: Scaling parameter count increases circuit width and single-step representation capacity, but cannot substitute for circuit depth in inherently sequential tasks. Test-time compute (extended thinking sequences) directly controls the computational depth available to solve a query.
2. The Key-Value Cache as Working Memory: The autoregressive KV cache functions as an append-only, random-access working tape. Causal self-attention serves as the read head, allowing the model to inspect past computation steps without recomputing them.
3. Error Drift and Rollout Stability: Because each step $z_t$ depends on $z_{<t}$, an incorrect token corrupts downstream circuit inputs. Mitigating error compounding requires high single-step token accuracy or verification mechanisms such as Process Reward Models (PRMs) and search-guided rollouts.
4. Latent vs. Explicit Reasoning: Replacing explicit token generation with recurrent hidden states trades KV cache memory for circuit depth. However, discrete intermediate tokens benefit from exact categorical separation and cross-entropy supervised alignment.

Sources

• The Expressive Power of Transformers with Chain of Thought (Merrill & Sabharwal, ICLR 2024)
• Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective (Feng et al., NeurIPS 2023)
• Chain of Thought Empowers Transformers to Solve Inherently Sequential Problems (Li et al., ICLR 2024)
• The Parallelism Tradeoff: Limitations of Log-Precision Transformers (Merrill & Sabharwal, TACL 2022)
• Show Your Work: Scratchpads for Intermediate Computation with Language Models (Nye et al., 2021)
• Chain-of-Thought Prompting Elicits Reasoning in Large Language Models (Wei et al., NeurIPS 2022)
• Attention is Turing-Complete with a Scratchpad (Perez et al., 2021)