# The Counting Power of Transformers

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 33 references that are in the map.
- First posted on arXiv 16 May 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [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)
- [Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages](https://mlsanity.com/paper/2310.13897/) (2023)
- [A Formal Framework for Understanding Length Generalization in Transformers](https://mlsanity.com/paper/2410.02140/) (2024)
- [Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers](https://mlsanity.com/paper/2404.04393/) (2024)
- [Logical Languages Accepted by Transformer Encoders with Hard Attention](https://mlsanity.com/paper/2310.03817/) (2023)
- [Simulating Hard Attention Using Soft Attention](https://mlsanity.com/paper/2412.09925/) (2024)
- [Text Similarity in Vector Space Models: A Comparative Study](https://mlsanity.com/paper/1810.00664/) (2018)
- [Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning](https://mlsanity.com/paper/2405.18548/) (2024)

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

- [Transformers are Inherently Succinct](https://mlsanity.com/paper/2510.19315/) (2025)
- [Length Generalization Bounds for Transformers](https://mlsanity.com/paper/2603.02238/) (2026)
- [Indexing: the Beginning and the End](https://mlsanity.com/paper/2607.22361/) (2026)
- [The Role of Logic and Automata in Understanding Transformers](https://mlsanity.com/paper/2509.24024/) (2025)
- [Synthesis and Verification of Transformer Programs (Technical Report)](https://mlsanity.com/paper/2602.16473/) (2026)
- [Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete](https://mlsanity.com/paper/2606.01532/) (2026)
- [Checking Leakage Witnesses versus Certifying Bounded Non-Leakage](https://mlsanity.com/paper/2609.32134/) (2026)
- [Repetition, Not Length: Isolating the Counting Failure in Neural Text-to-Speech](https://mlsanity.com/paper/2609.36974/) (2026)
- [Counting with Attention and LayerNorm: Norm Scaling and Representation Geometry](https://mlsanity.com/paper/2610.16653/) (2026)

## Abstract (arXiv)

Counting properties (e.g. determining whether certain tokens occur more than other tokens in a given input text) have played a significant role in the study of expressiveness of transformers. In this paper, we provide a formal framework for investigating the counting power of transformers. We argue that all existing results demonstrate transformers' expressivity only for (semi-)linear counting properties, i.e., which are expressible as a boolean combination of linear inequalities. Our main result is that transformers can express counting properties that are highly nonlinear. More precisely, we prove that transformers can capture all semialgebraic counting properties, i.e., expressible as a boolean combination of arbitrary multivariate polynomials (of any degree). Among others, these generalize the counting properties that can be captured by C-RASP softmax transformers, which capture only linear counting properties. To complement this result, we exhibit a natural subclass of (softmax) transformers that completely characterizes semialgebraic counting properties. Through connections with the Hilbert's tenth problem, this expressivity of transformers also yields a new undecidability result for analyzing an extremely simple transformer model -- surprisingly with neither positional encodings (i.e. NoPE-transformers) nor masking. We also experimentally validate trainability of such counting properties.