# Lower bounds on transformers with infinite precision

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 7 references that are in the map.
- First posted on arXiv 28 Dec 2024.

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

- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [On Limitations of the Transformer Architecture](https://mlsanity.com/paper/2402.08164/) (2024)
- [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024)
- [Separations in the Representational Capabilities of Transformers and Recurrent Architectures](https://mlsanity.com/paper/2406.09347/) (2024)

## Built on by (most cited first, 3 of 3)

- [Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers](https://mlsanity.com/paper/2502.02393/) (2025)
- [Fast attention mechanisms: a tale of parallelism](https://mlsanity.com/paper/2509.09001/) (2025)
- [Attention-based representations for multi-task computation](https://mlsanity.com/paper/2608.04243/) (2026)

## Abstract (arXiv)

In this note, we use the VC dimension technique to prove the first lower bound against one-layer softmax transformers with infinite precision. We do so for two tasks: function composition, considered by Peng, Narayanan, and Papadimitriou, and the SUM2 task, considered by Sanford, Hsu, and Telgarsky.