![[2407.15160] When Can Transformers Count to n?](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2407.15160] When Can Transformers Count to n?
Summary
This paper investigates the limitations of transformer models in performing basic counting tasks, revealing a critical relationship between embedding dimension, vocabulary size, and task difficulty.
Why It Matters
Understanding the limitations of transformers in simple algorithmic tasks is crucial for improving their design and application in AI. This research highlights a significant phase transition that affects model performance, which could inform future developments in machine learning and natural language processing.
Key Takeaways
- Transformers can accurately count tokens when embedding dimension matches or exceeds vocabulary size.
- A phase transition occurs when vocabulary size exceeds embedding dimension, leading to performance drops.
- Empirical validation shows pretrained models also struggle with counting tasks under these conditions.
- The study reveals a critical blind spot in transformer capabilities regarding counting tasks.
- Understanding these limitations can guide future improvements in transformer architecture.
Computer Science > Computation and Language arXiv:2407.15160 (cs) [Submitted on 21 Jul 2024 (v1), last revised 25 Feb 2026 (this version, v3)] Title:When Can Transformers Count to n? Authors:Gilad Yehudai, Haim Kaplan, Guy Dar, Royi Rassin, Asma Ghandeharioun, Mor Geva, Amir Globerson View a PDF of the paper titled When Can Transformers Count to n?, by Gilad Yehudai and 6 other authors View PDF HTML (experimental) Abstract:Large language models based on the transformer architecture can solve highly complex tasks, yet their fundamental limitations on simple algorithmic problems remain poorly understood. In this work, we focus on basic counting tasks and investigate how the difficulty of these tasks scales with the transformer embedding dimension, the context length, and the vocabulary size. We reveal a sharp theoretical phase transition governed by the relationship between the embedding dimension and the vocabulary size. When the dimension is at least as large as the vocabulary, transformers can perfectly maintain token counts. However, when the vocabulary exceeds the embedding dimension, the interference between non-orthogonal token representations forces the network weights to scale polynomially. This renders the exact counting algorithm numerically unstable and practically unlearnable. We empirically validate this bottleneck by training transformers from scratch, demonstrating a strict performance drop at the theoretical threshold and catastrophic out of distribution fai...