The Counting Power of Transformers
Marco Sälzer, Chris Köcher, Alexander Kozachinskiy, Georg Zetzsche, Anthony Widjaja Lin · 2025
Read The Counting Power of Transformers by Marco Sälzer, Chris Köcher, Alexander Kozachinskiy, Georg Zetzsche, Anthony Widjaja Lin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-11199.txt.
Introduction
Marco Sälzer, Chris Köcher, Alexander Kozachinskiy, Georg Zetzsche, and Anthony Widjaja Lin wrote a theory paper in 2025 about what transformer models can count. Counting here means tasks like telling whether one kind of token shows up more often than another in a text. Past work had shown that transformers can handle simple, straight line forms of such tasks.
The authors set up a formal frame for the question and then prove a much stronger result. They show that transformers can express counting tasks built from curved rules of any degree, not just straight line ones. They also name a narrow class of models that matches this power exactly, link the result to a classic hard math problem, and test that such tasks can in fact be learned.
Catalog record
| CREATOR | Marco Sälzer, Chris Köcher, Alexander Kozachinskiy, Georg Zetzsche, Anthony Widjaja Lin |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-11199
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Counting Power of Transformers Marco Sälzer, Chris Köcher, Alexander Kozachinskiy, Georg Zetzsche, Anthony Widjaja Lin Abstract 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. 1 Introduction Transformers ( Vaswani et al., 2017 ) have emerged in recent years as a powerful model with a plethora of successful applications including (among others) natural language processing, computer vision, and speech recognition. Despite the success of transformers, the question of what transformers can express is still not well-understood and has in recent years featured in a rich body of research works (e.g. Strobl et al. (2024) ; Hahn (2020) ; Pérez et al. (2021) ; Hao et al. (2022) ). In particular, formal language theory provides a formal framework in understanding expressivity issues for sequential models like transformers and Recurrent Neural Networks (RNNs). One recurring theme when studying the expressibility of transformers is the counting power of transformers. Intuitively, counting amounts to asserting an arithmetic relationship between the numbers of occurrences of various tokens in a given text. Counting properties are essentially the class of properties for textual data under consideration in the well-known Vector Space Model (VSM) (cf. Salton et al. (1975) ; Wong et al. (1985) ; Shawe-Taylor and Cristianini (2004) ), or the similar Bag-of-Words (BoW) model ( Harris, 1954 ) , which are known from the information retrieval community to be surprisingly powerful in measuring text similarity (e.g. see Shahmirzadi et al. (2019) ; Shawe-Taylor and Cristianini (2004) ). A simple example of a counting property can be found in a sentiment analysis application 1 1 1 https://medium.com/data-science/sentiment-analysis-with-text-mining-13dd2b33de27 : the number of positive words exceeds the number of negative words in a text. In the formal language theory, such a counting property can be formalized as the following language \mathsf{MAJ}:=\{w\in\{a,b\}^{*}:|w|_{a}>|w|_{b}\}, (1) which is often referred to as majority . Here, |w|_{a} (resp. |w|_{b} ) refers to the number of occurrences of a (resp. b ) in the string w . For example, \mathtt{a}\mathtt{a}\mathtt{b}\in\mathsf{MAJ} but \mathtt{a}\mathtt{b}\mathtt{b}\notin\mathsf{MAJ} . Note that “tokens” in NLP are synonymous to “letters” in formal language theory. Another counting property that plays an important role in the theory of expressibility of transformers is parity language: \mathsf{PARITY}:=\{w\in\{a,b\}^{*}:a\text{ occurs an even number of times in }w\}. (2) Multiple theoretical and empirical results (e.g. Hahn and Rofin (2024) ; Chiang and Cholak (2022) ; Huang et al. (2025) ; Hahn (2020) ; Hao et al. (2022) ; Bhattamishra et al. (2020) ; Anil et al. (2022) ; Delétang et al. (2023) ) have shown that, while transformers can be efficiently trained for \mathsf{MAJ} , this is not the case for \mathsf{PARITY} . Several theoretical explanations have been offered, e.g., sensitivity by Hahn and Rofin (2024) and length generalization admitted by limit transformers by Huang et al. (2025) ). Thus far, existing results have touched only upon semilinear counting properties. For example, defining \mathsf{MAJ} requires only a linear inequality (i.e. |w|_{a}>|w|_{b} ). In fact, logical languages, which were devised by Barceló et al. (2024) ; Yang and Chiang (2024) ; Huang et al. (2025) epitomizing languages expressible by transformers, permit only linear expressions (e.g. |w|_{a}+|w|_{b}>2\cdot|w|_{c} ). However, polynomial expressions (cf. Shawe-Taylor and Cristianini (2004) ) are also used to express co-occurrence of terms/tokens in a text. For example, using a higher-degree monomial such as \#(\text{nvidia})\cdot\#(\text{intel})\cdot\#(\text{deal}), where \#(w) counts the number of occurrences of a word w in the text, one can emphasize the co-occurrence of “nvidia”, “intel” and “deal” in a text. This motivates the following question: Research Question . What counting properties are expressible on transformers? Can they express nonlinear counting properties? The main contribution of this paper is the following result. Theorem 1.1 . Transformers can capture all semialgebraic counting properties, i.e., those expressible as a boolean combination of inequalities between multivariate polynomials, where each variable counts the number of occurrences of a specific token in the text. This means that transformers can capture expressions involving higher-degree polynomials like 7\#(\text{nvidia})\cdot\#(\text{intel})\cdot\#(\text{deal})+2\#(\text{shares})-8\#(\text{war})>10 , or boolean combinations (i.e. unions/intersections) of similar polynomial expressions. Consequently, by the Weierstrass theorem it follows that the set of polynomials can also approximate any continuous function on the number of occurrences of tokens. We prove this theorem (using softmax transformers) — requiring the use of neither positional encodings nor positional masking — and experimentally validate this claim. Our next question concerns the expressivity of softmax transformers for capturing counting properties: which class of softmax transformers capture semialgebraic counting properties? To this end, we provide a surprising characterization involving average hard attention ( Hao et al., 2022 ; Pérez et al., 2021 ) , which was devised to “approximate” soft attention by attending to all positions with maximum attention score and forwarding their average. In particular, Average Hard Attention Transformers (AHATs) with only uniform layers (written AHAT[U]) — that is, where maximum attention score is achieved at every position — immediately form a subclass of SoftMax Attention Transformers (SMAT). In the sequel, we write \mathsf{NoPE\mathchar 45\relax AHAT} (resp. \mathsf{NoPE\mathchar 45\relax AHAT}[\mathsf{U}] ) to mean AHAT (resp. AHAT[U]) that do not use Positional Encodings (PEs) (also no positional masking). Theorem 1.2 . \mathsf{NoPE\mathchar 45\relax AHAT} and \mathsf{NoPE\mathchar 45\relax AHAT}[\mathsf{U}] capture precisely semialgebraic counting properties. In particular, as far as expressing counting properties, \mathsf{NoPE\mathchar 45\relax AHAT} is a subset of \mathsf{SMAT} . This is surprising, since it is still a major open problem whether AHAT are captured by SMAT ( Yang and Chiang, 2024 ; Hahn, 2020 ; Yang et al., 2024b ) for general (not necessarily counting) properties. A corollary of Theorem 1.1 , combined with Matiyasevich’s celebrated solution to the notorious Hilbert’s 10th Problem ( Matiyasevich, 1993 ) , is a kind of universality (i.e. Turing-completeness) of transformers. More precisely, any recursively enumerable counting property P\subseteq\Sigma^{*} can be represented in terms of a program that, given an input string w\in\Sigma^{*} , feeds each string wv (where v\in\Gamma^{*} , for some \Gamma\cap\Sigma=\emptyset ) into a transformer T and accepts if T accepts some wv . In this case, we say that P is a projection of the language accepted by T . In fact, we show that transformers T with only two attention layers are sufficient