mlsanityData to 7 Oct 2026

Lower bounds on transformers with infinite precision

arXiv 2412.20195 ↗First posted 28 Dec 2024cs.LG cs.AI stat.MLcited by 3

Not on the map. Why?

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.

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

Builds on

6 of 7 references.

References · 6

  1. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  2. 2023Representational Strengths and Limitations of Transformerscited by 132
  3. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
  4. 2024On Limitations of the Transformer Architecturecited by 63
  5. 2024Theoretical limitations of multi-layer Transformercited by 43
  6. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 1.

3 papers.

  1. 2025Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformerscited by 28
  2. 2025Fast attention mechanisms: a tale of parallelismcited by 2
  3. 2026Attention-based representations for multi-task computationcited by 1