# A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers

arXiv: https://arxiv.org/abs/2503.03961 · HTML: https://mlsanity.com/paper/2503.03961/

## Key facts

- Cited by 53 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 40 references that are in the map.
- First posted on arXiv 5 Mar 2025.

## Builds on (most cited first, 22 of 22)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Mixed Precision Training](https://mlsanity.com/paper/1710.03740/) (2017)
- [On Layer Normalization in the Transformer Architecture](https://mlsanity.com/paper/2002.04745/) (2020)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Scaling up Test-Time Compute with Latent Reasoning: A Recurrent Depth Approach](https://mlsanity.com/paper/2502.05171/) (2025)
- [The Impact of Positional Encoding on Length Generalization in Transformers](https://mlsanity.com/paper/2305.19466/) (2023)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [Reasoning with Latent Thoughts: On the Power of Looped Transformers](https://mlsanity.com/paper/2502.17416/) (2025)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Let's Think Dot by Dot: Hidden Computation in Transformer Language Models](https://mlsanity.com/paper/2404.15758/) (2024)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [Looped Transformers are Better at Learning Learning Algorithms](https://mlsanity.com/paper/2311.12424/) (2023)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [A Logic for Expressing Log-Precision Transformers](https://mlsanity.com/paper/2210.02671/) (2022)
- [Understanding Transformer Reasoning Capabilities via Graph Algorithms](https://mlsanity.com/paper/2405.18512/) (2024)
- [Tighter Bounds on the Expressivity of Transformer Encoders](https://mlsanity.com/paper/2301.10743/) (2023)
- [The Impact of Depth on Compositional Generalization in Transformer Language Models](https://mlsanity.com/paper/2310.19956/) (2023)
- [Transformers as Transducers](https://mlsanity.com/paper/2404.02040/) (2024)

## Built on by (most cited first, 30 of 53)

- [Scaling Latent Reasoning via Looped Language Models](https://mlsanity.com/paper/2510.25741/) (2025)
- [A Survey on Latent Reasoning](https://mlsanity.com/paper/2507.06203/) (2025)
- [Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought](https://mlsanity.com/paper/2505.12514/) (2025)
- [Teaching Pretrained Language Models to Think Deeper with Retrofitted Recurrence](https://mlsanity.com/paper/2511.07384/) (2025)
- [Coevolutionary Continuous Discrete Diffusion: Make Your Diffusion Language Model a Latent Reasoner](https://mlsanity.com/paper/2510.03206/) (2025)
- [Exact Expressive Power of Transformers with Padding](https://mlsanity.com/paper/2505.18948/) (2025)
- [Constant Bit-size Transformers Are Turing Complete](https://mlsanity.com/paper/2506.12027/) (2025)
- [Theory of Scaling Laws for In-Context Regression: Depth, Width, Context and Time](https://mlsanity.com/paper/2510.01098/) (2025)
- [A Formal Comparison Between Chain of Thought and Latent Thought](https://mlsanity.com/paper/2509.25239/) (2025)
- [Training-Free Looped Transformers](https://mlsanity.com/paper/2605.23872/) (2026)
- [Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization](https://mlsanity.com/paper/2511.07378/) (2025)
- [Pangu Ultra: Pushing the Limits of Dense Large Language Models on Ascend NPUs](https://mlsanity.com/paper/2504.07866/) (2025)
- [The Serial Scaling Hypothesis](https://mlsanity.com/paper/2507.12549/) (2025)
- [Solve the Loop: Attractor Models for Language and Reasoning](https://mlsanity.com/paper/2605.12466/) (2026)
- [To CoT or To Loop? A Formal Comparison Between Chain-of-Thought and Looped Transformers](https://mlsanity.com/paper/2505.19245/) (2025)
- [Residual Context Diffusion Language Models](https://mlsanity.com/paper/2601.22954/) (2026)
- [Too Long, Didn't Model: Decomposing LLM Long-Context Understanding With Novels](https://mlsanity.com/paper/2505.14925/) (2025)
- [Chain-of-Experts: Unlocking the Communication Power of Mixture-of-Experts Models](https://mlsanity.com/paper/2506.18945/) (2025)
- [Sequences of Logits Reveal the Low Rank Structure of Language Models](https://mlsanity.com/paper/2510.24966/) (2025)
- [Prioritize the Process, Not Just the Outcome: Rewarding Latent Thought Trajectories Improves Reasoning in Looped Language Models](https://mlsanity.com/paper/2602.10520/) (2026)
- [Why Are Linear RNNs More Parallelizable?](https://mlsanity.com/paper/2603.03612/) (2026)
- [On the Reasoning Abilities of Masked Diffusion Language Models](https://mlsanity.com/paper/2510.13117/) (2025)
- [Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers](https://mlsanity.com/paper/2509.22445/) (2025)
- [The Transformer Cookbook](https://mlsanity.com/paper/2510.00368/) (2025)
- [When Does Recurrence Become an Algorithm? Convergence Selection in Weight-Tied Looped Transformers](https://mlsanity.com/paper/2607.20594/) (2026)
- [Learning to Ponder: Adaptive Reasoning in Latent Space](https://mlsanity.com/paper/2509.24238/) (2025)
- [The End of Transformers? On Challenging Attention and the Rise of Sub-Quadratic Architectures](https://mlsanity.com/paper/2510.05364/) (2025)
- [Efficient Turing Machine Simulation with Transformers](https://mlsanity.com/paper/2512.00003/) (2025)
- [Context-Free Recognition with Transformers](https://mlsanity.com/paper/2601.01754/) (2026)
- [Sparse Growing Transformer: Training-Time Sparse Depth Allocation via Progressive Attention Looping](https://mlsanity.com/paper/2603.23998/) (2026)

## Abstract (arXiv)

Recent theoretical results show transformers cannot express sequential reasoning problems over long inputs, intuitively because their computational depth is bounded. However, prior work treats the depth as a constant, leaving it unclear to what degree bounded depth may suffice for solving problems over short inputs, or how increasing the transformer's depth affects its expressive power. We address these questions by analyzing transformers whose depth can grow minimally with context length n. We show even highly uniform transformers with depth Theta(log n) can express two important problems: recognizing regular languages, which captures state tracking abilities and was known to be expressible only by an unconventional, non-uniform model of transformers, and graph connectivity, which underlies multi-step reasoning. Notably, both of these problems cannot be expressed by fixed-depth transformers under standard complexity conjectures, demonstrating the expressivity benefit of growing depth. Moreover, our theory quantitatively predicts how depth must grow with input length to express these problems, showing that depth scaling is more efficient than scaling width or chain-of-thought steps. Empirically, our detailed experiments designed to bridge the expressivity vs. learnability gap reveal that our theoretical depth requirements for regular language recognition closely match the practical depth requirements for successfully training transformers. Thus, our results clarify how depth affects a transformer's reasoning capabilities, and provide practical guidance for effective depth selection for sequential reasoning.