Research map / Architectures and efficiency / Attention and transformers
The Expressive Power of Transformers with Chain of Thought
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows theoretically that chain-of-thought decoding steps extend decoder-only transformer expressive power: log steps stay within L, linear steps recognize all regular languages (within context-sensitive), and polynomial steps yield exactly P, via a layer-norm hash construction.
Problem
Whether intermediate generation (chain of thought / scratchpad) fundamentally extends the computational power of decoder-only transformers, and how the number of decoding steps affects this power.
Approach
Characterizes transformer decoders with t(n) intermediate decoding steps against complexity classes, introducing a layer-norm hash for retrieval by numerical query-key matching and a projected/multi-pre-norm generalization that lets the construction simulate Turing machines step by step.
Key results
- Log-step decoder transformers are upper bounded by L (log-space), only slightly beyond TC^0.
- Linear decoding steps with projected pre-norm can simulate any automaton, so recognize all regular languages, and are upper bounded by context-sensitive languages (SPACE(n)).
- Polynomial decoding steps with strict causal saturated attention and projected pre-norm yield exactly the class P.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add a polynomial number of decoding steps | Decoder-only transformers with strict causal attention and projected pre-norm · Polynomial decoding steps | recognized language class | Helped |
| Add a linear number of decoding steps | Decoder-only transformers with projected pre-norm · Regular languages | recognized language class | Helped |
| Add a linear number of decoding steps | Decoder-only transformer · Linear decoding steps | recognized language class | Mixed |
| Add a logarithmic number of decoding steps | Decoder-only transformer · Logarithmic decoding steps | recognized language class | Helped |
| Add a logarithmic number of decoding steps | Decoder-only transformer · Directed graph connectivity | recognized language class | No clear effect |
| Add a quadratic number of decoding steps | Decoder-only transformer · Directed graph connectivity | decoding steps required | Helped |
Surprising findings
- Logarithmic decoding steps add little beyond TC^0 (upper bound only grows to L), and no concrete problem is identified where log steps help.
Limitations
- Expressive power only; lower bounds do not imply that transformers can learn to use intermediate steps.
- Lower bounds rely on saturated attention, strict causal masking, and projected pre-norm, which are non-standard assumptions.
- Upper and lower bounds are not tight; a strict separation between log and linear steps is not established.
Experimental setup
Builds on: Pre-norm transformers Turing machine simulation of transformers (Pérez et al.) saturated attention TC^0 upper bound for transformers
Closest papers by meaning
- Chain of Thought Empowers Transformers to Solve Inherently Serial Problems (ICLR 2024 · similarity 0.92)
- Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers (ICML 2025 · similarity 0.92)
- Exact Expressive Power of Transformers with Padding (NeurIPS 2025 · similarity 0.91)
- A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers (NeurIPS 2025 · similarity 0.90)
- Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning (ICLR 2025 · similarity 0.90)
- Transformers Provably Solve Parity Efficiently with Chain of Thought (ICLR 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.