# The Parallelism Tradeoff: Limitations of Log-Precision Transformers

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

## Key facts

- Cited by 193 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 30 references that are in the map.
- First posted on arXiv 2 Jul 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [On the Turing Completeness of Modern Neural Network Architectures](https://mlsanity.com/paper/1901.03429/) (2019)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descent](https://mlsanity.com/paper/2010.09697/) (2020)
- [On the Linguistic Capacity of Real-Time Counter Automata](https://mlsanity.com/paper/2004.06866/) (2020)
- [What Makes Instruction Learning Hard? An Investigation and a New Challenge in a Synthetic Environment](https://mlsanity.com/paper/2204.09148/) (2022)

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

- [Large Language Models](https://mlsanity.com/paper/2307.05782/) (2023)
- [Self Forcing: Bridging the Train-Test Gap in Autoregressive Video Diffusion](https://mlsanity.com/paper/2506.08009/) (2025)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [How Language Model Hallucinations Can Snowball](https://mlsanity.com/paper/2305.13534/) (2023)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [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)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Kimi Linear: An Expressive, Efficient Attention Architecture](https://mlsanity.com/paper/2510.26692/) (2025)
- [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)
- [Hierarchical Reasoning Model](https://mlsanity.com/paper/2506.21734/) (2025)
- [The pitfalls of next-token prediction](https://mlsanity.com/paper/2403.06963/) (2024)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [TiRex: Zero-Shot Forecasting Across Long and Short Horizons with Enhanced In-Context Learning](https://mlsanity.com/paper/2505.23719/) (2025)
- [Evaluating the World Model Implicit in a Generative Model](https://mlsanity.com/paper/2406.03689/) (2024)
- [Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues](https://mlsanity.com/paper/2411.12537/) (2024)
- [In-Context Language Learning: Architectures and Algorithms](https://mlsanity.com/paper/2401.12973/) (2024)
- [Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought](https://mlsanity.com/paper/2505.12514/) (2025)
- [DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products](https://mlsanity.com/paper/2502.10297/) (2025)
- [Why are Sensitive Functions Hard for Transformers?](https://mlsanity.com/paper/2402.09963/) (2024)
- [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)
- [RNNs are not Transformers (Yet): The Key Bottleneck on In-context Retrieval](https://mlsanity.com/paper/2402.18510/) (2024)
- [On Limitations of the Transformer Architecture](https://mlsanity.com/paper/2402.08164/) (2024)
- [On the Emergence of Position Bias in Transformers](https://mlsanity.com/paper/2502.01951/) (2025)
- [Training Strategies for Efficient Embodied Reasoning](https://mlsanity.com/paper/2505.08243/) (2025)
- [A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers](https://mlsanity.com/paper/2503.03961/) (2025)
- [The Expressive Power of Transformers with Chain of Thought](https://mlsanity.com/paper/2310.07923/) (2023)

## Abstract (arXiv)

Despite their omnipresence in modern NLP, characterizing the computational power of transformer neural nets remains an interesting open question. We prove that transformers whose arithmetic precision is logarithmic in the number of input tokens (and whose feedforward nets are computable using space linear in their input) can be simulated by constant-depth logspace-uniform threshold circuits. This provides insight on the power of transformers using known results in complexity theory. For example, if mathsf L neq mathsf P (i.e., not all poly-time problems can be solved using logarithmic space), then transformers cannot even accurately solve linear equalities or check membership in an arbitrary context-free grammar with empty productions. Our result intuitively emerges from the transformer architecture's high parallelizability. We thus speculatively introduce the idea of a fundamental parallelism tradeoff: any model architecture as parallelizable as the transformer will obey limitations similar to it. Since parallelism is key to training models at massive scale, this suggests a potential inherent weakness of the scaling paradigm.