# On the Expressive Power of Transformers

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 29 references that are in the map.
- First posted on arXiv 13 Aug 2026.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [On the Computational Power of Transformers and its Implications in Sequence Modeling](https://mlsanity.com/paper/2006.09286/) (2020)
- [A Logic for Expressing Log-Precision Transformers](https://mlsanity.com/paper/2210.02671/) (2022)
- [Auto-Regressive Next-Token Predictors are Universal Learners](https://mlsanity.com/paper/2309.06979/) (2023)
- [Tighter Bounds on the Expressivity of Transformer Encoders](https://mlsanity.com/paper/2301.10743/) (2023)
- [Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages](https://mlsanity.com/paper/2310.13897/) (2023)
- [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024)
- [Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descent](https://mlsanity.com/paper/2010.09697/) (2020)
- [Logical Languages Accepted by Transformer Encoders with Hard Attention](https://mlsanity.com/paper/2310.03817/) (2023)
- [Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers](https://mlsanity.com/paper/2502.02393/) (2025)
- [Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits](https://mlsanity.com/paper/2308.03212/) (2023)
- [Transformers in Uniform TC0](https://mlsanity.com/paper/2409.13629/) (2024)
- [A Survey of Neural Networks and Formal Languages](https://mlsanity.com/paper/2006.01338/) (2020)
- [Simulating Hard Attention Using Soft Attention](https://mlsanity.com/paper/2412.09925/) (2024)
- [Softmax Transformers are Turing-Complete](https://mlsanity.com/paper/2511.20038/) (2025)
- [The Transformer Cookbook](https://mlsanity.com/paper/2510.00368/) (2025)

## Abstract (arXiv)

Multi-layer transformers form the critical component of essentially all large language models (LLMs) in use today. Because of their ubiquity and computational capability, there is a rapidly growing body of work that aims to precisely calibrate the expressive power of transformers as language recognizers by comparing them against standard models of computation studied for decades by the theoretical computer science community. In this endeavor, circuit complexity has by and large emerged as the "correct" branch of computational complexity to analyze the expressive power of transformers; the reason is that parameterizing transformers by the various resources they use, such as attention and precision, leads to direct comparisons with different classes of circuits parameterized by resources such as type of gates, size, and depth. Here, we present an overview of selected results that delineate the expressive power of transformers using concepts and methods from circuit complexity.