# When Can Transformers Count to n?

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 35 references that are in the map.
- First posted on arXiv 21 Jul 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models](https://mlsanity.com/paper/2206.04615/) (2022)
- [In-context Learning and Induction Heads](https://mlsanity.com/paper/2209.11895/) (2022)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Same Task, More Tokens: the Impact of Input Length on the Reasoning Performance of Large Language Models](https://mlsanity.com/paper/2402.14848/) (2024)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [Transformers need glasses! Information over-squashing in language tasks](https://mlsanity.com/paper/2406.04267/) (2024)
- [Efficient Long-Text Understanding with Short-Text Models](https://mlsanity.com/paper/2208.00748/) (2022)
- [On Limitations of the Transformer Architecture](https://mlsanity.com/paper/2402.08164/) (2024)
- [Language Models Need Inductive Biases to Count Inductively](https://mlsanity.com/paper/2405.20131/) (2024)
- [How Many Neurons Does it Take to Approximate the Maximum?](https://mlsanity.com/paper/2307.09212/) (2023)
- [Contextual Counting: A Mechanistic Study of Transformers on a Quantitative Task](https://mlsanity.com/paper/2406.02585/) (2024)
- [Counting in Small Transformers: The Delicate Interplay between Attention and Feed-Forward Layers](https://mlsanity.com/paper/2407.11542/) (2024)
- [All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis](https://mlsanity.com/paper/1306.3284/) (2013)

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

- [Language Models Encode Numbers Using Digit Representations in Base 10](https://mlsanity.com/paper/2410.11781/) (2024)
- [Frontier LLMs Still Struggle with Simple Reasoning Tasks](https://mlsanity.com/paper/2507.07313/) (2025)
- [Large Language Model Reasoning Failures](https://mlsanity.com/paper/2602.06176/) (2026)
- [Position: The Future of Bayesian Prediction Is Prior-Fitted](https://mlsanity.com/paper/2505.23947/) (2025)
- [Depth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformers](https://mlsanity.com/paper/2503.01805/) (2025)
- [More Expressive Attention with Negative Weights](https://mlsanity.com/paper/2411.07176/) (2024)
- [Training Transformers for KV Cache Compressibility](https://mlsanity.com/paper/2605.05971/) (2026)
- [Composing Global Solutions to Reasoning Tasks via Algebraic Objects in Neural Nets](https://mlsanity.com/paper/2410.01779/) (2024)
- [Compositional Reasoning with Transformers, RNNs, and Chain of Thought](https://mlsanity.com/paper/2503.01544/) (2025)
- [Are You Human? An Adversarial Benchmark to Expose LLMs](https://mlsanity.com/paper/2410.09569/) (2024)
- [Sequential Enumeration in Large Language Models](https://mlsanity.com/paper/2512.04727/) (2025)
- [StringLLM: Understanding the String Processing Capability of Large Language Models](https://mlsanity.com/paper/2410.01208/) (2024)
- [A Minimum Description Length Approach to Regularization in Neural Networks](https://mlsanity.com/paper/2505.13398/) (2025)
- [Tracr-Injection: Distilling Algorithms into Pre-trained Language Models](https://mlsanity.com/paper/2505.10719/) (2025)
- [Vector Symbolic Algebras for the Abstraction and Reasoning Corpus](https://mlsanity.com/paper/2511.08747/) (2025)
- [Abacus: Self-Supervised Event Counting-Aligned Distributional Pretraining for Sequential User Modeling](https://mlsanity.com/paper/2512.16581/) (2025)
- [Every Bit Counts: A Theoretical Study of Precision-Expressivity Tradeoffs in Quantized Transformers](https://mlsanity.com/paper/2602.02707/) (2026)
- [ECG-LLM: Foundation Model for ECG-Based Cardiac Reasoning](https://mlsanity.com/paper/2607.16323/) (2026)
- [Semantic Content Determines Algorithmic Performance](https://mlsanity.com/paper/2601.21618/) (2026)
- [Artificial Effort](https://mlsanity.com/paper/2605.23920/) (2026)
- [Shape Over Intensity: Directional Topological Encoding for False Positive Reduction in Intracranial Aneurysm Detection](https://mlsanity.com/paper/2607.05317/) (2026)
- [List Counting Failures Are Not One Phenomenon](https://mlsanity.com/paper/2609.22230/) (2026)
- [Counting on Thinking: Tracing Evidence Integration in Language Models](https://mlsanity.com/paper/2609.32932/) (2026)
- [Counting with Attention and LayerNorm: Norm Scaling and Representation Geometry](https://mlsanity.com/paper/2610.16653/) (2026)

## Abstract (arXiv)

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 failure when scaling the vocabulary or context length. Furthermore, we show that state-of-the-art pretrained models suffer from similar failure cases. Our work reveals a critical blind spot absent from the current literature regarding the connection among these three parameters, proving that vocabulary size fundamentally dictates the difficulty of counting tasks.