Research map / Architectures and efficiency / Attention and transformers
A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
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 that highly uniform universal transformers with Θ(log n) looped depth can recognize regular languages and solve graph connectivity, giving depth-vs-context-length bounds and experiments confirming depth scales logarithmically with length for learning state tracking.
Problem
Fixed-depth transformers provably cannot express regular language recognition or graph connectivity over unbounded inputs (they lie outside TC^0); it is unclear how depth must grow with context length to express these problems, and how this compares to scaling width or chain-of-thought steps.
Approach
Construct fully uniform (parameter-shared, looped) transformers with residual connections and layer norm, where depth grows as Θ(log n); the key primitive is a uniform division/remainder gadget enabling a binary-tree monoid product for regular languages and a repeated-squaring reachability construction for graph connectivity.
Key results
- Theory: regular language recognition and graph connectivity are expressible by fully uniform (0,8,9) and (17,2,1) universal transformers with Θ(log n) depth, implying fixed depth d handles inputs up to length 2^{O(d)}.
- Empirically, effective context length fits d = 4.8 log2 n - 15.8 (r^2=0.93) for depth on A5, versus log-width fit n = 7.2 log2 w - 41.7 (r^2=0.98).
- Depth scaling of Θ(log n) is theoretically more efficient than width (superpolynomial needed) or chain-of-thought (superlogarithmic steps needed).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase depth while holding width at 512 | Transformer trained for A5 state tracking · A5 state tracking | effective context length at at least 95% validation accuracy: d = 4.8 log_2 n - 15.8; r^2 = 0.93 | Helped |
| Increase width while holding depth at 6 | Transformer trained for A5 state tracking · A5 state tracking | effective context length at at least 95% validation accuracy: n = 7.2 log_2 w - 41.7; r^2 = 0.98 | Helped |
| Scale depth logarithmically with input length | Universal transformer · Regular language recognition | recognition capability | Helped |
| Scale depth logarithmically with the number of vertices | Universal transformer · Graph connectivity | connectivity-solving capability | Helped |
| Scale width rather than depth to increase expressive power | Fixed-depth transformer · Reasoning problems outside TC^0 | expressive power | Hurt |
| Use O(log n) chain-of-thought steps instead of growing depth | Transformer · Regular language recognition and graph connectivity | expressive power | Hurt |
Surprising findings
- Width must grow exponentially in n (superpolynomially in the theoretical analysis) to express regular languages with fixed depth, contrasting with logarithmic depth growth.
Limitations
- Expressivity results do not address learnability, inductive biases, or learning dynamics of looped transformers.
- Experiments use non-looped transformers, not the weight-shared setting analyzed in theory.
- Log-depth and polylog-depth transformers cannot express P-complete problems unless NC = P.
Experimental setup
Datasets: A5 state tracking sequences (synthetic, ~100M)
Benchmarks: A5 state tracking
Metrics: effective context length n* (max token index with at least 9 r^2 of linear fit
Baselines: fixed-depth transformers width-scaled transformers chain-of-thought scaling
Builds on: universal transformers Liu et al. 2022 shortcut learning / log-depth construction Merrill and Sabharwal circuit complexity of transformers Barrington theorem
Closest papers by meaning
- Chain of Thought Empowers Transformers to Solve Inherently Serial Problems (ICLR 2024 · similarity 0.90)
- The Expressive Power of Transformers with Chain of Thought (ICLR 2024 · similarity 0.90)
- Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization (NeurIPS 2025 · similarity 0.89)
- Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers (NeurIPS 2025 · similarity 0.89)
- Understanding Transformer Reasoning Capabilities via Graph Algorithms (NeurIPS 2024 · similarity 0.88)
- Separations in the Representational Capabilities of Transformers and Recurrent Architectures (NeurIPS 2024 · similarity 0.88)
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.