PaperlayerView exact revision on arXiv

Source-linked AI summary

Chain of Thought Empowers Transformers to Solve Inherently Serial Problems

Zhiyuan Li, Hong Liu, Denny Zhou, Tengyu Ma

arXiv:2402.12875v4cs.LGcs.CCstat.ML

TL;DR

CoT’s mechanism for improving arithmetic and symbolic reasoning is unclear. The paper analyzes decoder-only transformer expressiveness using circuit complexity, showing that CoT supplies serial computation and empirically improves performance on inherently serial tasks.

  • Problem

    The paper asks why generating intermediate CoT steps improves LLM reasoning, especially when low-depth transformers otherwise lack sufficient serial computation.

  • Method

    The paper defines CoT transformer complexity classes and analyzes decoder-only transformers theoretically and empirically across four arithmetic problems.

  • Results

    CoT enables constant-depth, constant-precision transformers to express circuit-computable functions according to the available steps, while improving results on inherently serial tasks.

  • Takeaways & Limitations

    CoT gives low-depth transformers additional serial computation, making them more expressive on problems that require inherently serial computation.

  • Takeaways & Limitations

    The complexity class is non-uniform, allowing a different program for every input size.

Abstract

from arXiv · show

Instructing the model to generate a sequence of intermediate steps, a.k.a., a chain of thought (CoT), is a highly effective method to improve the accuracy of large language models (LLMs) on arithmetics and symbolic reasoning tasks. However, the mechanism behind CoT remains unclear. This work provides a theoretical understanding of the power of CoT for decoder-only transformers through the lens of expressiveness. Conceptually, CoT empowers the model with the ability to perform inherently serial computation, which is otherwise lacking in transformers, especially when depth is low. Given input length $n$, previous works have shown that constant-depth transformers with finite precision $\mathsf{poly}(n)$ embedding size can only solve problems in $\mathsf{TC}^0$ without CoT. We first show an even tighter expressiveness upper bound for constant-depth transformers with constant-bit precision, which can only solve problems in $\mathsf{AC}^0$, a proper subset of $ \mathsf{TC}^0$. However, with $T$ steps of CoT, constant-depth transformers using constant-bit precision and $O(\log n)$ embedding size can solve any problem solvable by boolean circuits of size $T$. Empirically, enabling CoT dramatically improves the accuracy for tasks that are hard for parallel computation, including the composition of permutation groups, iterated squaring, and circuit value problems, especially for low-depth transformers.

1 Introduction

The paper studies why chain-of-thought improves reasoning by analyzing transformer expressiveness through circuit complexity. It argues that CoT adds serial computation unavailable to low-depth vanilla transformers and supports this claim theoretically and empirically.

  • Theoretical motivation: Constant-precision, constant-depth transformers without CoT are bounded by AC0, a proper subset of TC0.The tighter bound accounts for rounding in iterative floating-point arithmetic.
  • Theoretical motivation: With T intermediate steps, transformers can solve problems requiring inherently serial computation, whereas vanilla transformers are limited by their fixed depth.CoT increases the possible number of serial computations from the fixed depth to T.
  • Theoretical results: A constant-precision transformer with logarithmic embedding dimension and T CoT steps can express any function computed by a circuit of size T.Polynomially many CoT steps therefore reach polynomial-size circuit computation, while linearly many steps cover all regular languages described in the introduction.
  • Theoretical results: Logarithmically many CoT steps do not extend transformer expressiveness beyond AC0.
  • Empirical evaluation: Experiments evaluate modular addition, permutation composition, iterated squaring, and circuit value problems with and without CoT.The latter three are described as requiring inherently serial computation, while modular addition is parallelizable.

2 Notations and Preliminaries

This section defines the mathematical notation, problem and circuit-complexity terminology, and decoder-only transformer components used in the paper. It also specifies autoregressive CoT generation and several modeling assumptions.

  • Transformer and problem notation: A decoder-only transformer maps an input token sequence to next-token probabilities and selects the highest-probability token as its output.The paper denotes this selected-token function by TFθ.
  • Transformer and problem notation: CoT generation recursively appends the transformer’s selected next token to the current sequence for successive steps.The recursion is defined up to the model’s maximum input length.
  • Transformer architecture: The decoder-only architecture consists of token embedding, position encoding, an output layer, and a stack of decoder layers containing attention and feed-forward sublayers.The model depth L is the number of decoder layers.
  • Complexity notation: A problem maps a finite sequence of vocabulary tokens to an answer token; binary-answer problems are called decision problems or languages.
  • Complexity notation: SIZE[T(n)] contains problems solvable by Boolean circuits with O(T(n)) gates, while P/poly is the union of polynomial-size circuit classes.The preliminaries state that P is contained in P/poly.
  • Complexity notation: AC, TC, and NC describe circuit families by parallel depth, size, fan-in, and gate types, with NC^i ⊆ AC^i ⊆ TC^i ⊆ NC^(i+1).The paper also notes that finite-vocabulary inputs can be binary-encoded with only a constant-factor length increase.

3 Expressiveness Theory forTransformerswithChainofThought(CoT)

This section formalizes finite-precision transformer expressiveness and shows that chain-of-thought expands the serial computation available to constant-depth models. The results characterize both upper bounds without CoT and stronger expressiveness with CoT, including circuit-size and language-class consequences.

  • Finite Precision Modeling: Constant-precision arithmetic is modeled through floating-point representations, correct rounding, and rounded operations such as summation, inner products, matrix products, and softmax.Finite-precision summation is defined as a fixed-order chain of rounded binary additions.
  • CoT Expressiveness: The CoT class allows constant-depth transformers to autoregressively generate T intermediate tokens using specified embedding size and precision budgets.The class is non-uniform, permitting a different program for every input size.
  • Upper Bounds Without CoT: AC^0 is an upper bound for constant-depth transformers with constant bits of precision and exponent, while fixed-point log-precision models remain bounded by TC^0.The AC^0 result implies that sufficiently long inputs cannot support even modular counting such as parity under this setting.
  • Expressiveness With CoT: SIZE[T(n)] ⊆ CoT[T(n), log n, 1], and polynomially many CoT steps yield P/poly expressiveness.The construction uses each CoT step to simulate one target-circuit gate, storing gate metadata in Θ(log n) dimensions.
  • Expressiveness With CoT: Polynomial CoT steps strictly increase the expressiveness of constant-depth constant-precision transformers and, under TC^0 ⊊ P/poly, also strengthen log-precision transformers.Every regular language belongs to CoT[n, log n, 1].
  • Scope and Conventions: The oracle-circuit characterization uses a gate-count convention that differs from literature definitions based on the number of wires.This is a stated definitional scope boundary for the oracle results.
  • Embedding Size: For polynomially many CoT steps, polynomial embedding size does not improve expressiveness over logarithmic size, but for fixed T(n)=n^k it does.Theorem 3.9 states strict containments between logarithmic- and polynomial-width settings.

4 CoT Empirically Improves Expressiveness of Low-Depth Transformers on Inherently Serial Problems

The experiments test whether CoT improves decoder-only transformers on four arithmetic problems, especially the three predicted to require inherently serial computation. CoT substantially improves low-depth performance on permutation composition, iterated squaring, and circuit value problems.

  • Experimental design: The study compares base, CoT, and hint settings on modular addition, permutation composition, iterated squaring, and circuit value problems.The models are trained separately for each problem and sequence length using synthetic data.
  • Experimental design: Modular addition is parallelizable, whereas permutation composition, iterated squaring, and circuit value are treated as inherently serial under standard assumptions.The empirical design uses modular addition as the parallel-computation comparison problem.
  • Task construction: Iterated squaring computes f_r,p(n) ≡ (r2^n) mod p from a randomly generated sequence of squaring tokens.The vocabulary uses T = 1000, with prime p and 1 ≤ r, p ≤ T − 1.
  • Evaluation: For CoT evaluation, the study aims to assess answers after autoregressively generating the intermediate sequence rather than only evaluating the final step.Direct final-answer evaluation is considered too easy when CoT is supplied as input.
  • Findings: CoT outperforms hint and base settings on the problems hard for parallel computation, with especially large improvements at small depths.The reported pattern supports a substantial expressiveness gain for low-depth transformers on inherently serial problems.

5 Related Works

Related work characterizes transformer computation through low-complexity circuits, symbolic programs, and automata-like mechanisms. This paper differs by emphasizing multiple CoT steps for problems requiring serial computation and by studying constant-precision settings.

  • Prior perspectives: Prior studies connect self-attention with low-complexity circuits, declarative programs, Turing machines, and interpretable symbolic computations.These lines of work motivate analyzing transformer computation as an expressiveness question.
  • CoT and automata: Liu et al. study low-depth transformers for semi-automata, corresponding to one CoT step in the paper’s setting.The paper extends this perspective to more CoT steps and harder inherently serial problems.
  • CoT and automata: The paper’s contribution is to show that additional CoT steps can address problems beyond semi-automata, including the P-complete circuit value problem.This comparison is presented as a distinction from the closely related semi-automata setting.
  • Precision regimes: Most earlier transformer expressiveness work focuses on logarithmic precision, partly because it supports uniform attention over remaining tokens.The paper instead mainly studies constant precision with logarithmic embedding size.
  • Concurrent work: A concurrent work studies CoT expressiveness for specific P-complete problems, whereas this paper gives a construction for each problem in P/poly.The settings also differ in precision and embedding-size assumptions.

6 Conclusion

The paper studies CoT for decoder-only transformers through expressiveness and defines a complexity class parameterized by CoT length, depth, embedding size, and numerical precision. Its theory and experiments indicate that CoT expands expressiveness for inherently serial problems.

  • Conclusion: The paper defines CoT[T(n), d(n), s(n), e(n)] for problems solvable by constant-depth, constant-precision decoder-only transformers with specified CoT and numerical-resource bounds.The class tracks CoT steps, embedding size, exponent bits, and significand bits.
  • Conclusion: Increasing CoT length can drastically increase transformer expressiveness according to the paper’s theoretical analysis.The empirical evaluation covers four arithmetic problems.
  • Conclusion: For three inherently serial problems, the experiments find that transformers express the ground-truth function only when using CoT.The conclusion identifies these as the permutation composition, iterated squaring, and circuit value problems studied empirically.

A Additional Experimental Results

The appendix reports experimental settings and additional results across modular addition, permutation composition, iterated squaring, and circuit value problems. It also specifies the finite-precision transformer components used in these experiments.

  • Experimental Setup: The appendix evaluates base-setting performance on modular addition, permutation composition, iterated squaring, and circuit value problems using synthetic data.The experiments vary transformer depth and compare base, hint, and CoT settings in the broader evaluation.
  • Modular Addition: Modular addition is easy for transformers because attention can aggregate values and feedforward layers can compute the modulus.The observed high training accuracy is consistent with the use of float16, which behaves like log-precision for the sequence lengths studied.
  • Permutation Composition: Permutation composition is theoretically hard for shallow transformers when p ≥5 because it cannot be computed by TC0 unless TC0 = NC1.The experimental results are reported as matching this theoretical prediction.
  • Experimental Results: Base-setting accuracy is lower than hint-setting accuracy.The appendix states this comparison directly for the additional results.
  • Transformer Definition: The appendix defines finite-precision decoder-only transformers through token embeddings, position encodings, self-attention, feedforward layers, and output layers.The implementation uses causal self-attention with finite-precision arithmetic.

C Preliminary of Automata and Krohn-Rhodes Decomposition Theorem

This section develops automata-theoretic tools centered on homomorphisms, cascade products, permutation-reset automata, and counter-free automata. Krohn-Rhodes decomposition reduces counter-free automata to reset-automaton cascades, connecting them to constant-depth circuits.

  • Automata: An automaton consists of a finite alphabet, finite state set, and transition function, with input sequences processed by recursively lifting transitions.Choosing an initial state and accepting states yields a recognized language; finite automata recognize exactly the regular languages.
  • Homomorphisms: An automaton homomorphism preserves transitions and transfers recognized languages through inverse images of accepting states.The supplied lemma formalizes this simulation relationship.
  • Krohn-Rhodes Decomposition: Krohn-Rhodes decomposition represents every automaton as a cascade of permutation-reset automata, with permutation groups linked to the original transformation semigroup.The resulting cascade together with its homomorphism is called a cascaded decomposition.
  • Counter-Free Automata: Counter-free automata are equivalent to automata whose transformation semigroups are group-free, or aperiodic.For counter-free automata, the Krohn-Rhodes cascade can use reset automata only.
  • Circuit Connection: A counter-free automaton can be simulated by an unbounded-fan-in circuit of size O(n^3) and constant depth.This establishes the circuit-complexity connection used by the paper.

D Proofs for Expressiveness Upper Bounds (Section 3.3)

The proofs establish upper bounds for finite-precision computation by analyzing rounded addition as an ordered automaton and by constructing a TC0 implementation for polynomial-precision fixed-point addition.

  • Constant Precision: For fixed exponent and significand sizes, rounded iterated addition over floating-point numbers has AC0 circuits.The proof uses the ordered-automaton characterization and the fact that ordered automata are counter-free.
  • Polynomial Precision: For s(n) = O(poly(n)) with zero exponent bits, rounded addition has TC0 circuits.The proof reduces fixed-point floating-point numbers to suitably rescaled binary integers and implements sorting and addition in TC0.
  • Ordered Automata: Rounded addition defines an ordered automaton because rounding preserves the usual numerical order.For x ≤ x′, the transition [x + y]e,s is no greater than [x′ + y]e,s.
  • Iterative Addition: Algorithm 5 computes rounded addition correctly for all inputs in F0,s(n).Its correctness is established by tracking overflow and partial sums across the iterative computation.
  • Circuit Implementation: Theorem 3.2 follows by implementing Algorithm 5 with a family of TC0 circuits.The construction uses the TC0 realizability of sorting and adding polynomial-bit binary integers.

E.1 Proof of Theorem 3.3

The proof of Theorem 3.3 constructs a two-layer decoder-only transformer that evaluates Boolean circuits gate by gate using CoT positions. Attention retrieves gate inputs, and a feedforward computation implements NOT and AND gates.

  • Circuit Simulation: A Boolean circuit with O(T(n)) gates is simulated using T(n) CoT steps.The construction assigns one autoregressive position to each non-input gate in topological order.
  • Embedding Construction: The transformer uses O(log n) embedding coordinates to encode gate indices and retrieve predecessor values.For polynomial T(n), the index width k(n) is O(log n).
  • Inductive Correctness: The output at each generated position equals the corresponding circuit gate value by induction.The final output layer reads the fourth embedding coordinate containing gi(x).
  • Attention Retrieval: Attention retrieves the value of a gate's first input and a second attention layer retrieves its second input.The key-query construction selects the positions indexed by a(i) and b(i).
  • Gate Computation: The feedforward layer computes NOT when c(i) = 0 and AND when c(i) = 1.It applies F(xa(i), xb(i), c(i)) using two ReLU terms on Boolean inputs.

E.2 Proof of Theorems 3.7 and 3.8

The proofs establish correspondences between bounded-size threshold circuits and constant-depth transformers with chain-of-thought steps. The construction uses autoregressive intermediate tokens to realize sequential circuit computations while maintaining logarithmic precision or polynomial embedding resources, as specified.

  • The construction recursively maps each intermediate token to a constant-depth threshold circuit depending on earlier inputs and generated tokens.Topological ordering supplies the autoregressive sequence, while the transformer simulates the corresponding circuits in parallel across positions.
  • Theorem 3.7 proves that threshold-circuit computations with T(n) gates can be represented by CoT transformers using T(n) intermediate steps.The proof establishes both containment directions through circuit simulation and sequential generation of intermediate tokens.
  • The transformer construction uses constant depth, CoT length T(n), polynomial embedding width, and precision sufficient to simulate polynomial-size MAJORITY gates.The stated embedding width is O(poly(n)), with precision s(n)=⌈log2 S(n)⌉ in the construction.
  • Attention and feedforward layers organize prior tokens and simulate circuit layers, while the output layer converts the final intermediate computation into the answer.The proof assigns distinct roles to attention, ReLU feedforward layers, positional representations, and output coordinates.
  • With zero intermediate steps, the construction yields the equivalence TC0 = T[poly(n)] = CoT[1, poly(n)] = SIZETC0(1).Thus the zero-step case recovers the constant-depth threshold-circuit class represented by the transformer model.

E.3 Proof of Theorem 3.9

Theorem 3.9 separates CoT transformers with logarithmic embedding size from those with polynomial embedding size by relating them to distinct circuit-size classes. The separation relies on AC0’s strict containment in polynomial-size standard circuits.

  • For every k, CoT[n^k, log(n)] is strictly contained in CoT[n^k, poly(n)].The proof combines circuit-size upper bounds with the strict separation AC0 ⊊ SIZE[n^k].
  • The separation proof embeds AC0 computations into CoT transformers with polynomial resources, then uses circuit-size bounds to exclude the logarithmic-embedding class.This establishes the strict inclusion for every polynomial CoT length exponent k.
  • Unlimited-fanin AND and OR gates are simulated by two-layer ReLU networks with constant precision and constant hidden dimension.The construction uses additional constant inputs and a ReLU difference identity to implement Boolean gates.
  • The counting argument constructs an AC0 language outside every fixed polynomial-size standard-circuit class SIZE(Cn^k).There are at least 2^(n^(k+1)) candidate CNFs, exceeding the number of circuits of size at most Cn^k for sufficiently large n.

F Discussion on Variants in Transformer Architecture

The paper argues that its expressiveness results remain valid for common LayerNorm variants and constantly many attention heads. It restricts the main presentation to one attention head because arbitrary head counts may change expressiveness.

  • Adding LayerNorm does not affect the stated upper bounds, and the main results extend to both Post LayerNorm and Pre LayerNorm architectures.The extension uses representations whose coordinates occur as paired −1 and 1 values, making LayerNorm act as the identity.
  • The constructions can be modified for LayerNorm by replacing each original coordinate with a four-coordinate ±1 representation.The outgoing layer averages the expanded representation to recover the original values.
  • Constantly many attention heads preserve the main results because k heads can be simulated by k single-head attention layers.The paper therefore presents the simpler one-head formulation.
  • Allowing an arbitrary number of heads while fixing total embedding size may make constant-depth transformers strictly more expressive, and this case is left for future work.This is the paper’s explicit architecture-scope boundary.

G Discussion on Non-uniformity

The discussion distinguishes non-uniform transformer families from uniform computation models and explains how uniformity could be imposed through parameter generation. It also identifies length generalization as a boundary for non-uniform GPT-style models.

  • Non-uniform models may use a different program or transformer for each input length, whereas uniform models require cross-length circuits or parameters to be algorithmically related.The distinction parallels the difference between arbitrary circuit families and circuits generated under resource-bounded assumptions.
  • Uniform CoT transformers can be defined by requiring their parameters to be generated by a Turing machine from the input length.A T-step Turing-machine computation can be simulated by uniform Boolean circuits of size O(T^2).
  • The practicality of one transformer per input length is unclear because current practice does not scale to arbitrary lengths and GPT architectures use trainable absolute position encodings.The position encoding makes additional trainable parameters necessary for longer input lengths in the architecture considered.
  • Length generalization is required for complexity-class tasks over arbitrary lengths but may be impossible for non-uniform GPT models with unseen trainable absolute positions.The paper contrasts this requirement with natural-language tasks, which can rely more heavily on memorization.
Loading 2402.12875v4…