Chain-of-Thought Reasoning in Large Language Models: How Intermediate Rationales Expand Computational Expressivity and Transformer Capacity

Autoregressive large language models operate by predicting the next token in a sequence conditioned on preceding context. When presented with complex multi-step problems in mathematics, symbolic manipulation, algorithmic planning, or formal logic, standard standard models tasked with providing immediate answers often fail. This failure stems from a fundamental structural constraint: a model forced to output a final answer immediately must compress the entire multi-step derivation into a single forward pass through a fixed number of transformer layers.

Chain-of-thought (CoT) prompting alters this dynamic by allowing the model to generate a sequence of intermediate reasoning steps before emitting the final conclusion. While initially introduced as an empirical prompting technique, subsequent research in computational complexity theory has established that chain-of-thought generation fundamentally alters the expressive power of transformer architectures, converting fixed-depth parallel circuits into stateful sequential computing engines.

Computational circuit expansion in chain-of-thought reasoning

The Single-Pass Computation Bottleneck

In standard autoregressive language modeling, mapping an input prompt $x$ directly to an answer $y$ requires the neural network to execute all necessary logical deductions within a single forward pass. For a transformer with $L$ layers and hidden dimension $d_{\text{model}}$ , the total amount of computation allocated to generate the first token of the answer is fixed at $O(L \cdot d_{\text{model}}^2)$ operations per token.

For direct single-step answering, every intermediate variable and intermediate deductive state must be represented simultaneously within the activation vectors of the intermediate residual streams. If a task requires sequential steps where step $k$ depends strictly on the outcome of step $k-1$ , a fixed-depth network quickly encounters depth saturation. The network cannot perform more sequential operations than it has layers.

This computational bottleneck was demonstrated empirically by Nye et al. (2021) in work introducing scratchpads for neural networks. When standard sequence-to-sequence transformers were trained to predict the final output of multi-digit addition or multi-line Python program execution directly, accuracy collapsed rapidly as problem complexity scaled. However, when models were trained to emit line-by-line execution states onto an intermediate scratchpad before predicting the final return value, accuracy reached near-perfect levels across long input lengths.

Empirical Discovery: Few-Shot and Zero-Shot CoT

The formalization of chain-of-thought as a generalized prompting paradigm for foundation models occurred in 2022 through two parallel lines of investigation.

Few-Shot Exemplars

Wei et al. (2022) demonstrated that standard in-context learning could be restructured to elicit multi-step rationales. Rather than providing few-shot prompt exemplars in the standard format:

Q: Roger has 5 tennis balls. He buys 2 more cans of tennis balls. 
   Each can has 3 tennis balls. How many tennis balls does he have now?
A: The answer is 11.

Few-Shot Chain-of-Thought replaced the target outputs with structured deductive chains:

Q: Roger has 5 tennis balls. He buys 2 more cans of tennis balls. 
   Each can has 3 tennis balls. How many tennis balls does he have now?
A: Roger started with 5 balls. 2 cans of 3 tennis balls each is 6 tennis balls. 
   5 + 6 = 11. The answer is 11.

When evaluated on benchmarks such as GSM8K, SVAMP, and challenging Big-Bench tasks, standard prompting showed flat scaling curves on models below 100 billion parameters. Chain-of-thought prompting exhibited an emergent capability profile: as parameter scale crossed roughly 50 billion to 100 billion parameters, accuracy on multi-step reasoning benchmarks diverged sharply upward compared to standard prompt baselines.

Zero-Shot CoT

Following this, Kojima et al. (2022) showed that few-shot exemplar engineering was not strictly necessary to trigger intermediate generation in instruction-tuned models. By simply appending the prompt modifier:

"Let's think step by step."

to the input question, instruction-tuned models generated coherent multi-step rationales prior to outputting an answer. On MultiArith, zero-shot accuracy surged from 17.7% with standard prompting to 78.7% when using zero-shot chain-of-thought.

Theoretical Expressivity and Circuit Complexity

Beyond empirical gains, theoretical computer science has analyzed why intermediate tokens are necessary for transformers. This research uses circuit complexity to characterize the limits of fixed-depth attention architectures.

The TC0 Complexity Class Bound

Theoretical work by Merrill and Sabharwal (2023) established that fixed-depth autoregressive transformers using standard softmax or hard attention belong to the non-uniform circuit complexity class $\mathsf{TC}^0$ . The class $\mathsf{TC}^0$ consists of decision problems solvable by constant-depth, polynomial-size circuits composed of unbounded fan-in AND, OR, NOT, and majority threshold gates.

A fundamental result in computational complexity is that $\mathsf{TC}^0$ has strict mathematical limits:

$\mathsf{TC}^0$ circuits cannot compute basic sequential parity problems across arbitrary lengths without scaling circuit depth.
$\mathsf{TC}^0$ circuits cannot solve graph connectivity problems or determine reachability in arbitrary directed acyclic graphs.
$\mathsf{TC}^0$ circuits cannot evaluate arbitrary arithmetic formulas or simulate general finite-state automata across variable sequence lengths.

Consequently, when a transformer is asked to solve a problem requiring sequential graph traversal, modular arithmetic, or nested logic in a single decoding step, it is mathematically incapable of doing so across general input lengths. The model fails not because of insufficient parameter weights, but because its circuit depth is fixed at $L$ .

Converting Sequential Forward Passes into Recurrent Memory

When an autoregressive transformer generates $T$ intermediate rationale tokens, each token generation step involves a full forward pass through all $L$ layers. The generated token is appended to the context sequence and stored in the key-value (KV) cache.

By generating $T$ tokens, the model performs $L \times T$ effective computational layers:

External State Storage: Intermediate calculations are written out as discrete tokens into the context buffer.
Recurrent State Transitions: In subsequent forward passes, self-attention mechanisms attend over earlier intermediate states stored in the KV cache, retrieving partial results and updating hypotheses.
Complexity Escalation: As shown by Feng et al. (2023), allowing an autoregressive transformer to emit polynomial-length reasoning chains expands its expressivity from $\mathsf{TC}^0$ to polynomial time ( $\mathsf{P}$ ) and logarithmic space ( $\mathsf{L}$ ). An autoregressive transformer generating intermediate chain-of-thought tokens is computationally equivalent to a bounded-space Turing machine.

Direct Answering:
Input [x] ──────> [ L Transformer Layers (TC0) ] ──────> Answer [y]

Chain-of-Thought Decoding:
Input [x] ──────> [ L Layers ] ──────> Token [t_1] (State 1)
                     │
                     ▼
[x, t_1]  ──────> [ L Layers ] ──────> Token [t_2] (State 2)
                     │
                     ▼
[x, t_1...t_T] ─> [ L Layers ] ──────> Answer [y] (Total Compute = L × T)

Algorithmic Variants and Enhancements

Standard linear text generation is one implementation of chain-of-thought. Several structured variations have been developed to address distinct operational failure points.

Program-Aided Language Models (PAL)

While language models excel at natural language problem decomposition, their internal attention heads frequently make calculation errors when executing exact arithmetic or iterating over long loops.

Gao et al. (2023) introduced Program-Aided Language Models (PAL), while Chen et al. developed Program-of-Thought (PoT). In these frameworks, the intermediate reasoning steps are generated as executable Python code rather than free-form natural language text. The model writes variable assignments, loop conditions, and mathematical equations, and then delegates the final evaluation to an external Python runtime environment. This decouples qualitative semantic decomposition from quantitative deterministic computation.

Self-Consistency Decoding

Standard chain-of-thought relies on greedy argmax decoding or a single stochastic temperature sample. If an early token in the rationale introduces a faulty premise, autoregressive conditioning can propagate that error through the remainder of the sequence.

Wang et al. (2022) introduced Self-Consistency decoding. Rather than generating a single reasoning path, the system samples $N$ distinct reasoning trajectories in parallel using a non-zero temperature (typically $T \in [0.5, 0.7]$ ). The final answer is determined by taking the marginal majority vote across all parsed answer strings, ignoring minor trajectory differences in intermediate steps. This approach consistently yields 5% to 15% absolute accuracy improvements over single-chain prompting.

Faithfulness and Reasoning Failure Modes

Despite its advantages, chain-of-thought prompting introduces subtle architectural vulnerabilities regarding faithfulness and error compounding.

Post-Hoc Rationalization and Sycophancy

A major question in mechanistic interpretability is whether the generated rationale reflects the true causal mechanism behind the model's prediction. Research by Turpin et al. (2023) and Lanham et al. (2023) demonstrated that chain-of-thought explanations can be unfaithful:

Biased Inputs: When prompts include subtle biasing cues (such as stating that a professor believes option A is correct, or formatting option A with arbitrary markers), the model's prediction skews heavily toward option A.
Rationalization: Instead of acknowledging the biasing context, the generated chain of thought constructs plausible-sounding, post-hoc technical arguments that lead directly to the biased answer.
Truncation Resilience: Lanham et al. showed that for many non-mathematical tasks, truncating or perturbing the intermediate tokens often fails to alter the final predicted answer, revealing that the model sometimes reaches the conclusion independently before generating the explanatory chain.

Autoregressive Error Snowballing

Because autoregressive decoding treats all generated tokens as verified context, an incorrect assumption made at token $t_k$ cannot be retracted within a standard left-to-right generation sequence without backtracking mechanisms. The model is forced to condition all subsequent tokens on an invalid state, leading to cascading errors where the model continues generating mathematically sophisticated but fundamentally incorrect arguments.

From Prompting to Native Reinforcement Learning

The evolution of chain-of-thought reasoning has shifted from manual prompt engineering to post-training optimization.

Early efforts like STaR (Self-Taught Reasoner) by Zelikman et al. (2022) bootstrapped reasoning data by generating rationales, filtering out those that produced incorrect answers, and fine-tuning the base model on successful rationale-answer pairs.

Modern frontier architectures, including OpenAI's o-series and DeepSeek-R1, incorporate chain-of-thought generation directly into large-scale reinforcement learning pipelines (such as Reinforcement Learning with Verifiable Rewards, or RLVR). In these models, the intermediate token stream functions as an internal hidden scratchpad where the policy is rewarded for exploring hypotheses, backtracking, verifying intermediate calculations, and spending test-time compute dynamically based on problem hardness.

What began as an empirical observation in prompt design has developed into a core principle of artificial intelligence architecture: complex reasoning is fundamentally a sequential compute process that cannot be compressed into a single forward pass.