The Counting Power of Transformers
Authors: Marco Sälzer
Chris Köcher
Alexander Kozachinskiy
Georg Zetzsche
Anthony Widjaja Lin
Venue: ICLR 2026 Poster (2026)
Keywords: FLaNN
expressiveness
attention
formal languages
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: Transformers can express highly nonlinear counting properties

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.

Published as a conference paper at ICLR 2026
THE COUNTING POWER OF TRANSFORMERS
Marco Sälzer
Chris Köcher MPI-SWS
RPTU Kaiserslautem-Landaa
Kaiserslautern, Germany
Kaiserslautern, Germany
marco. www.serertte.....cm......
ckoecher@mpi sws. org
Alexander Kozachinskiy
Georg Zetzsche
Centro Nacional de Inteligencia Artificial
MPI-SWS
Santiago, Chile
Kaiserslautern, Germany georgêmpi swws org
alexander www.iier....cc.nnskkkkk. kozachiinskyileeniia..
Anthony Widjaja Lin
MPI-SWS and RPTU Kaiserslautern-Lane Kaiserslautem, Germany
awl meiiimmmisssti -tmppissws.rr..
ABSTRACT
Counting properties (e.g. determining whether certain tokens occur more than other tokens given input text) have played a significant role in the study expressiveness of transformers. In this paper, we provide formal framework for investigating the counting power transformers. We argue that all cxisting results demonstrate transformers' expressivity only for (semi-)llnees counting properties, i.e., which are expressible as a boolean combination of linear inequalities. Our main result is that transformers nonlinear. More precisely, we prove that transformers can capture all semialgebraic counting properties, i.e., expressible a boolean combination of arbitrary multi- variate 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.
express counting properties that highly
To complement this result, exhibit natural subclass of (softmax) transformers that completely characterizes semialgebraic counting properties. Through connec- tions 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. (oPE-transformers) nor masking. We also experimentally validate trainability of such counting properties.
INTRODUCTION
Transformers (Vaswani et al., 2017) have emerged in recent years as powerful model with 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 well-understood and has recent years featured in 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 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 arithmetic relationship between the numbers occurrences of various tokens in 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- Shawe-Taylor & Cristianini (2004)), or the similar Bag-of Wordy (BoW) model (Harris, 1954), which known from the information retrieval community be

---

Published as a conference paper at ICLR 2026
surprisingly powerful in measuring text similarity (e.g. Shahmirzadi al. (2019): Shawe-Taylor & Cristianini (2004)). A simple example of a counting property can be found in sentiment analysis application': the number of positive words exceeds the number of negative words in text. In the formal language theory, such a counting property can be formalized as the following language
MAJ := fw fa, b)": |wla >
|u|bb>
(I)
which is often referred to majority. Here, |w/a (resp. (w/b)) refers to the number of occurrences of a (resp. b) in the string W. For example, aab E MAJ but abb & MAJ. Note that "tokens" in NLP synonymous "letters" in formal language theory. Another counting property that plays an important role in the theory of expressibility of transformers is parity language:
PARITY == {w {a, b}* a occurs an even number of times in w)
(2)
Multiple theoretical and empirical results (c.g. Hahn & Rofin (2024); Chiang & 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 not the case for PARITY. Several theoretical explanations have been offered, e.g.. sensitivity by Hahn & Rofin (2024) and length generalization admitted by limit transformers by Huang et al. (2025)).
be efficiently trained for MAJ, this is
Thus far, existing results have touched only upon semilinear counting properties. For example, defining MAJ requires only a línear inequality (i.e. [w/ lol)). In fact, logical languages, which were devised by Barceló et al. (2024); Yang & Chiang (2024); Huang et al. (2025) epitomizing languages expressible by transformers, permit only linear expressions (e.g. |w/a + |w|p
(wle). However, polynomial expressions (ef. Shawe-Taylee & Cristianini (2004)) are also used to express co-occurrence of terms/tokens in text. For example, using a higher-degree monomial such as
# #(nvidia) # #(ineel) #(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" 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, ie., 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# (nvidia) # (intel)) # (deal)= + 2# (shares) - (war) > 10, or boolean combinations (i.e. umions/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 sofimax transformers capture semialgebraic counting properties? To this end, we provide 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 achieved at every position - immediately form a subclass of SoftMax Attention Transformers (SMAT). In the sequel, we write NoPE-AHAT (resp. NoPE-AHAT [U) to mean AHAT (resp. AHAT(U]) that do not use Positional Encodings (PEs) (also no positional masking).
Theorem 1.2. NoPE-AHAT and NoPE-AHAT[[] capture precisely semialgebraic counting proper- ties. In particular, as far as expressing counting properties, NoPE-AHAT is subset SMAT.
This is surprising, since it is still a major open problem whether AHAT are captured by SMAT (Yang & Chiang, 2024; Hahn, 2020; Yang et al., 2024b) for general (not necessarily counting) properties.
httpps:/ /tt////md/iii/ um, com datta aci ence/ sent ment-ana lysi witttttt wwwthhhtettttttteee www.-teextt-nn--ee 1nn--nnn3n--1133333222777
3dd2b33de27
2

---

Published as a conference paper at ICLR 2026
Theorem B.2
Theorem 1.2
AHAT
NoPE-AHAT NoPE-AHAT[U] SemiAlg
NoPE-AHATI< 1 QFPA
AHAT[U]
SMAT
Figure 1: Visualization of our results.
A corollary of Theorem 1.1, combined with Matiyasevieh's celebrated solution the notorious Hilbert's 10th Problem (Matiyasevich, 1993), is a kind of universality (i.c. (uring-oomlletnnsss) of transformers. More precisely, any recursively enumerable counting property P C Σ' can be represented in terms of a program that, given an input string w E Σ", feeds each string wy (where E [", for some I UnΣ = ()) into transformer T and accepts if T accepts some we. 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 and necessary to achieve this result:
Theorem 1.3. Every recursively enumerable counting property is a projection of language recog- nized by a NoPE-AHAT(U), and thus by an SMAT. Here, two attention layers in NoPE-AHAT[U] and SMAT are sufficient.
Similarly, our results yield undecidability result for analyzing an extremely simple transformer model Surprisiury with neither positional encodings nor masking:
Theorem 1.4. Given a NoPE-AHAT[U] or SMAT (with just two attention layers), it is undecidable whether its language is empty.
Recent results (ef. (Sälzer et al., 2025)) require a substantially more complex architecture to achieve such undecidability result, ie., with powerful positional encoding and average hard attention.
Finally, how do general transformers compare with other machine learning models as far as capturing counting properties? To this end, let us discuss two models. First is the class of polynomial separators that can be generated by mapping to a higher dimension and look for a linear separator in this higher dimension. This is standard technique in classical machine learning literature, where one can apply techniques like Support Vector Machines (SVM) (c.g. using polynomial kernel) in the Vector Space Model (VSM) (Salton et al. (1975); Wong et al. (1985); also see Chapter 10 of Shawe-Tay -aylor & Cristianini (2004)). Our result shows that transformers generalize such counting properties: not only polynomial counting properties can be captured, but also boolean combinations thereof. Second is the model called C-RASP (Huang et al., 2025), which is simple declarative language that formalizes the so-called RASP-L conjecture (Zhou al., 2024) capturing "efficiently learnable" properties on transformers. In particular, C-RASP allows only linear counting terms. We prove that C-RASP can capture only linear counting properties. Since our experiments supporting Theorem 1. reveals that counting properties like La := {w ba, /wo & > |w]a)) are also efficiently learnable for k > it follows that C-RASP is only partial characterization of efficiently learnable properties.
Organization. We recall transformer models and define our framework for studying counting properties in Section 2. We then show how to capture semialgebraic counting properties using transformers in Section 3. Section 4, we provide natural subclass of softmax transformers that completely characterizes semialgebraic counting properties. In Section 5, we show applications of our semialgebraic results for a better understanding of expressiveness of transformers, e.g., universal- ity/undecidability and comparison to work on C-RASP transformers. We report experimental results in Section 6 and conclude in Section 7. Some details have been relegated into the Appendix.
2 FRAMEWORK: TRANSFORMERS AND COUNTING PROPERTIES
Formal language theory primer We assume some basic understanding of formal language theory (at the level of standard undergraduate textbook by Sipser (2013)) and will only fix some notation.
For an alphabet Σ- = {ai...., } J. A language is a set of strings over Σ. We write Σ' (resp. Σ+) to mean the set of all strings (resp. all nonempty strings) over Σ. We write |i| to denote the length of
3

---

Published as a conference paper at ICLR 2026
For each a E Σ, write |w/a to mean the number of occurrences of a in A language K Σ* is a projection of a language L S Σ- if there is subalphabet I S Σ such that K is obtained from L by deleting all occurrences of letters in I' from words in L. For class C of languages, by Proj(C), denote the class of projections of languages in C.
We will touch upon regular languages and recursively enumerable languages (see Sipser (2013) for details). In summary, regular languages are languages that can be described by regular expressions. Recursively enumerable languages are those that are recognized by (possibly nonterminating) Turing machines. The class of such languages is denoted RE. In particular, a machine model is said to be it can capture all recursively enumerable languages.
For an alphabet Σ = {ai..... am J. we define the Parikh image (a.k.a. Parikh map) as the function :: Σ- + N",, where V/r (w) := wl,,, is the number of a, is in w. Intuitively, Parikh image of a word w provides the letter counts in w, e.g., over Σ = {a. b), we have T (abaaa)
(3. 1). The Parikh
map can also be extended to a language L; that is, / (L) = { (W()): :w E L} C N For example, if L {a"b"a" n 2 0} is a language over Σ (a. b}. we have (L) {2n, n) : n 2 20.
2.1 TRANSFORMERS
We now recall the formal definition of transformers. Loosely speaking, a transformer is composition of finitely many attention layers, each converting a sequence a of IR -vectors into another sequence of of R -vectors, for some d and k. To turn a transformer T into language recognizer, to embed any letter in the finite alphabet Σ as a R veetor, where d is smaller than the dimension of the first attention layer. For example, Σ. {a, b. <), and the one-hot embeddings of a, b, a (respectively) (1, 0, 0). (0, 1, 0). and (0, 0, 1). Finally, to determine acceptance, we simply run 7 on the embeddings of the input string w into sequence of vectors (possibly expanded with positional information) and check if the last vector u satisfies that the dot product v.t is greater than 0 (for some pre-defined vector of weights). particular, w is accepted by T iff v.t > 0.
have
Example. Suppose we are given the input string abac. Additionally, suppose we use the positional embedding p: n + 1/n. Then, checking whether T accepts w amounts to running T on the sequence σ:
(1,0,0,
U2, v3, U4. Determining whether T After running I on the resulting sequence is of the form U1, U2 accepts w amounts to checking whether t.u, > O. For example, 11 12 U3. U2 could be:
(1, 1, 1),2, 3. 1, 10, (1, 8, (1)) 0, 1,414)
which will be accepted, whenever t (1, 0, 0,
Next we formalize the definition of transformers by defining how each attention layer functions.
ReLU networks. We first define ReLU networks, which used inside an attention layer. A ReLU node v is a function Qm + Q, where E N is referred to as the input dimension, and is detined as u(2 Tm) max(0, b + Σx=1 wix;), where w; E Q are the weights, and b Q is the bias. [In practice, GeLU and SwiGLU are also used instead of ReLU, which we do not consider in this paper.] A ReLU layer l a tuple of ReLU nodes (01. (01..... Un), all having the same input dimensionality, computing a function R"" + R", where n E N is referred to as the output dimension. Finally, ReLU network A is a tuple of ReLU layers (E1,...,44 44), such that the input dimension of fi+1 is equal to the output dimension of f. It computes a function QTa + Q"* given by N Tm,) = (x( (...... (ZI...., Im,) ...).
Attention layers Each attention layer involves weight normalizer wt R - K" which turns any d-sequence of weights into amother such d-sequence. Two widely used weight normalizers are:
1. The softmax normalizer softmax. That is, given sequence 2...... Cn R, define softmax(o) := Vi..... yn. where yı Ej-r""
2. The averaging hard attention normalizer aha. We define aha(r) = y1...., . Yn. where if = max(o),
L| 0
91 =
or else.
4

---

Published as a conference paper at ICLR 2026
where P consists of positions in such that 2; is maximum in That is, aha behaves like softmax but maps all non maximum weights to O, and all maximum weights to 1/ PI.
One can also allow temperature scaling 0 to softmax, i.e., softmax, (o) -....... ................................ Un and set e"t/T This is not so relevant in our paper since our proof works for any r > 0.
y/ Ej=r""//r
An attention layer is a function A: (R+)) + (IP"), given by affine maps Q. K: E2 + R. V: F. + R (query, key, and value matrices) and a ReLU neural net W: Quttk + Q Given an input sequence x (.1,...,, Fn) ) E (Qrl), the output sequence y = (y),... ...,...... yn) E (Q is computed as follows. First, one computes the sequences of key, query, and value vectors: k; Kæ;, qi = Qz,, v; = Va,, for each i = I,..... n, then we define yi = N Nx az), with a; Σ w(j)us, where = wt(((k;, 4 )=)))
We say that À is softmax (resp. aha) layer if wt. = softmax (resp. aha). We say that it is uniform-aha layer if it is an aha layer such that Kx: = Qz = 0 for all æ, i.e. (Kx, Qy) = 0 for all and y. Note that a uniform-ahe is both an aha layer and softmax layer since noting that
softmax(51,.............. ..., 8n) softmax, (si...., sn) aha(s), ................................ sn) [1/n,... 1/n1],
Sn. which can be guaranteed for uniform aha layers. This holds for all > 0. Remark. Some papers (e.g. Yang et al. (2024a); Huang et al. (2025); Yang & Chiang (2024)) apply strict future masking, which means that attention is only applied to positions up to the current position i. Our work does not apply masking.
whenever 51
Defining transformers. To define transformer and its language, first extend the finite alphabet
E with an end marker $ & Σ. That is, r == Σ u {S}. A transformer with é layers over a finite alphabet E is then function T: Σ+
{0.1). 1). given by: (i) the "input embedding" function
6: T Qud, (ii) the positional encoding p: I22 RRd and (iii) a sequence of layers λ (I241 )* + (I ..... Xe: (I + (Rd++1)* Given an input word w a1 On 2n, the output T(w) is computed as follows. First, we set æ1 (,,, ..... In ((an) +p n), In+11 = (($) + p(n + 1, n). Then we compute (y1..... Mo+1) \e(ee1(
(#1....., 1n+ ... ..)))))))))))))))))). and we set T(w) = 1 if and only if y, [1] > 0, and T(w) = O otherwise. The language L(T) accepted by T is defined as (w E E.: T(w) = 1}. We say that has no positional encoding (NoPE) if the positional encoding is constant function.
Remark. Several studies (e.g., Merrill & Sabharwal (2023b); Sälzer et al. (2025); Li & Cotterell (2025)) consider the capabilities of transformers in the context of restricted precision, such as assuming computations are carried out under the assumption of finite representation sizes. We do not focus these aspects, but note that it is easy see that our key results, such as Proposition 3.1, also apply under so-called log-precision assumptions (cf. Merrill & Sabharwal (2023b); also see Merrill & Sabharwal (2023a)) for rational numbers. This means that the binary representation size of number p/q E Q grows logarithmically with the length of the input.
A Sofimax Attention Transformer is transformer using only softmax layers whereas AHA Transformer is a transformer using only aha layers. By SMAT we denote the class of all languages accepted by softmax attention transformers and by AHAT we denote the class of all languages accepted by AHA transformers. To all classes we of transformer languages we append "[U]" to denote languages of transformers with only uniform layers, e.g. AHAT[U]. We prepend "NoPE" to denote only languages of transformers with no positional encoding, e.g. NoPE-AHAT[U), Note that all transformer models we are considering in this paper have only one attention head.
2.2 COUNTING PROPERTIES
We now define framework for studying the counting ability of transformers. Intuitively, our framework focuses on "counting properties". As we shall see below, we can build many interesting formal languages with the help of purely counting properties.
Given a permutation ग. {l....,,.] n + (L...., n) and a string w = w1 ... Wn of length n, the string (w)) = (x(1) (x(n)) is obtained by permuting the letters in w according to n. Definition 2.1. A counting property over the alphabet Σ is permutation-closed language L, i.c., for each Σ², it is the case that T. iff i (w) E T. for each permutation over (1,-..; [[....[w/]]
5

---

Published as a conference paper at ICLR 2026
Examples of counting properties MAJ and PARITY (see (1), (2)). We often identify counting property I. with its set (w) C NIEI of letter counts (i.e. Parikh image). By Pl, we denote the class of counting properties over Σ. Counting properties are also called permutation-invaatie or "proportion-invarian"" languages, e.g., see Pérez et al. (2021); Barceló al. (2024).
Why counting properties? Certainly, many languages of interests have both "counting com-- ponent" and an "order component". Take, for example, the language L1 = (a"b"e" 2 0). Our framework focuses purely counting properties for two reasons. Firstly, it abstracts away non-counting components that cannot be captured by the model. Secondly, many formal languages L of interests can be constructed by taking intersection of a counting property P and an order (and
language L'. For example, L1 above can be written as P n L', where P (w E Σ" [// w/ | and L' = c". Finally, multiple key languages in the literature on the expressivity of transformers are in fact counting properties (e.g. MAJ and PARITY).
3 CAPTURING SEMIALGEBRAIC COUNTING PROPERTIES
A subset S C N is semi-algebraic if it is Boolean combination of sets of the form S, fo N" p(x) > 0} for some polynomial E Z [[ Xm]. language L C Σ is semi-algebraic there is semi-algebraic set S S N and Σ = {a1.... ..... am ) such that L {w {ai..... 3m) }
(w) E S}. Let SemiAlg denote the class of semi-algebrate languages. An example is
SQRT {w E {a, b}" |w|a /ull/V23.
since Iw/a- < / if and only if 2/w < /w|2. Likewise, extending the coefficients of our polynomials to rational numbers does increase the expressiveness of semialgebraic sets, e.g.. 3 3ry+tz² > 8z - can be rewritten as +zy+ > 24r 9. Note that for every p E Z[X1..... Xm the set {ar E Nm p(x) = 0} is semi-algebraic, because p(x)- 0 if and only if -p(x)² + +1>00 0. Thus, every solution set to polynomial equations is also semi-algebraic.
We show Theorem 1.1. Since AHAT[U] S SMAT, it sufices to construct AHAT[U]. We will even construct a NoPE-AHAT[U). The key ingredient is:
Proposition 3.1. For every polynomial p E Z[X,,... Xmm, the language Lp>0 fw {a)..... am }" pp (w:) > 0} belongs to NoPE NOPE-AHAT[U], Thus, Lp5o is in SMAT.
Let us see why Proposition 3.1 implies SemiAlg C NoPE-AHAT[UJ, First, the complement of each language Lp>0 can be obtained, because p(x) > is violated if and only if -(x)))+)++ NoPE-AHAT is closed under union and intersection (we prove a stronger fact in Appendix A.2). We can thus accept Boolean combinations of languages of the form Iyp00. and hence SemiAlg.
Moreover,
To show Proposition 3.1, we will use polynomials that are homogeneous, meaning all monomials have the same degree. Note that given an arbitrary polynomial p E Z ..... X,m of degree d, we can consider the polynomial q E Z[Xo has the property that p(r1..... .,, xm) > 0 and only if q(1 21, Tm) > O. Therefore, from now on, assume that have a homogeneous polynomial q Z ................................ X,,. and want construct an AHAT(U] for the language K, = {w E fai..... am q (11 x) > for æ = (w)).
X...] with q = -xpp( X1
Xm Xo which is homogeneous.
X
To simplify notation, denote the end marker by ag. Thus, the input will be string (ao..... ) that contains ag exactly once, at the end. Since |w/a, AHAT[U] only has to check that (150...-,, > O, where x; |ucla.- The input encoding is the map {ao.... am) + 2T with + e,, where e, E Q is the i-th unit vector.
is satisfied automatically.
Overall idea Roughly speaking, we implement multiplication via averaging as follows. For each letter a, we have gadget that can multiply an existing entry y E [0, 1] (in each vector) by n+1 (recall that n is the overall word length). This is done by first multiplying the existing entries either (i) by 1 if the current letter is a or (ii) by 0 if the current letter is not a, This is achieved using {0. 1}. we have v ReLU(u (1 (1))).. After this, we average over the entire input in this component. Since we make sure that all the entries we multiplied with or 1 had the same value y E [o. 1), taking the average will result in the value u.a,
ReLU layer, by observing that for E [Ó, 1] and
n+1
Repeating this for monomial Z4,"" Ligs arrive at the value Zg "g Since our homogenization
(x+1)²*

---

Published as a conference paper at ICLR 2026
step ensured that all our monomials have the same degree d. adding up the entries corresponding to the monomials will yield p(P(w)) Finally, the latter quantity is positive if and only if p( (w)) >
[m+1y=
Step I: Compute frequencies Our AHAT[U] first uses an attention layer to compute m + new components, where i-th component holds n+I where n + 1 is the length of the imput (including the end marker). This is easily done by attending to all positions and computing the averages of the first m + 1 components. To simplify notation, we will index vectors starting with index O.
Step II: Multiplication gadgets Second, we have a sequence of gadgets (each consisting of one ReLU layer and one attention layer) that perform the multiplication. Each gadget introduces new component, and does not change the existing components. Between gadget executions, the following additional invariants are upheld: (i) Overall, a gadget does not change existing components: it introduces one new component. (ii) The components {O..... m) are called the initial components. (iii) All other components are uniform, i.c. they are the same across all positions. (iv) The uniform components carry values in [0, 1]. Thus, we will call components O..... m the initial components; and we call components > m the uniform components.
Our gadgets do the following. Suppose we have already produced additional components. For each initial component E [0, m] and uniform component j E [m + 1, m + 1 1+ E], gadget omult(E, i. j). which introduces a new component, will carry the value 20.8 where M/ is the value in component, of all vectors. Recall that we use z; to denote the number of a, occurrences in the input for i [0, ml.
We implement the gadget omult i, using some ReLU layers and an attention layer. Suppose that before, we have the vector up E Qm in position p. First, using ReLU layers, we introduce new This can be achieved since up [i] is in {0, 13 ReRUR [up
ReLUUlayess,
component that in position p has the value uplil u Up
(i)) Indeed, if up = 1, then this evaluates to Up if up = 0, then we get ReI.U up -1 - 1,-1)==1) = 0. We then use uniform attention compute the average of this new up [i] [pp ccomponent across all vectors. Since there n + 1 vectors, exactly 2; of them have up [ 1, and also up[s] Vy. we get the desired #;*1, n+1
and u, [0, 1]: Notice that up [i] upli]
[i]:
Step III: Computing the polynomial We now use our gudgets to compute the value of the polyno- mial. For each monomial of q. say X,, ...... we use dl gadgets to compute T;, -,, ... /n +1y. The frequency computation in the beginning yields / + 1), and then we use gadgets to compute Fú /ig/ (n + 1)2, Fi, TigTis / (n + 1) etc. until Fú, ... /ii./ (n + 1)d. Finally, we use a ReLUU layer to multiply each monomial with rational coefficient, and compute the sum of all the monomials. Thus, we have computed q( ... hmm/(t + 1)d. We accept if and only if g. /m) + 1)a > O.
Note that this is the case if and only if q(=u, 2m) > O.
This completes Proposition 3.1 and thus SemiAlg S NoPE-AHAT(UJ. We remark that the embedding dimension and the number of layers of our transformer in Proposition 3.1 depends the degree d and the number M of monomials in p. We require at most (d) layers, each layer increasing the degree detailed that polynomials of degree d are
of the computed monomials by one. In the appendix, accepted by NoPE-AHAT [U] using at most d attention layers (see Proposition A. The embedding dimension is (d.M) because we store the value of each monomial in a separate dimension.
4 CHARACTERIZING SEMI-ALGEBRAN COUNTING PROPERTIES
We have shown that NoPE-AHAT[U] C SMAT can capture semi-algebraic counting properties. We now prove that the subclass NoPE-AHAT[U] precisely characterizes SemiAlg. Proposition 4.1. NoPE-AHAT C SemiAlg.
Proof. Suppose that Σ = (ai...., am) is our alphabet, ag the end marker, and x; E N the number of occurrences of a; in the input. We say that position p is an a,-position if the input holds a; at position p. Notice that an AHAT without positional encoding cannot distinguish vectors that come from the same input letter. This means, in any layer, any two -pposiiio will hold the same vector. Thus, the vector sequence on layer is described by rational vectors ug,0.-.., Ue.m, where ug. is the vector at all the a.-positions on layer f. Moreover, for each i, the set of positions maximizing an attention score also either contains all poppoiiiinss, or none of them. Therefore, the AHAT has attention layers, there are at most (22m+1jm+t) = 2mm+ possible ways to choose the positions of maximal score: On each attention layer, and for each E [0, m),, we select subset of the m +
7

---

Published as a conference paper at ICLR 2026
letters. For each ReLU node and each i, there two ways its expression ReLU(e) can be evaluated: as 0 or as U. Thus, if there are r ReLU nodes, then there are 2" ways to evaluate all those nodes.
For each of these 2r+(m+))&a choices, we construct a conjunction of polynomial inequalities that verify that (i) this choice actually maximized scores, (ii) the resulting vector at the right-most position in the last layer satisfies the accepting condition. This is easy to do by building, for each layer l and each i, expressions in 21. I' for the vectors ugt. assuming our choice above. These expressions have the form p(a (Z))) F'm (averaging can introduce denominators). Here, once we have expressions for ug,s, we can use them build expressions for U4+1, by following the definition of AHAT. Checking (i) and (ii) is then also easy. because inequalities involving quotients p(z1,.... Zm) /mm /q(//)/....... Tm) can be turned into polynomial inequalities by multiplying with common denominators, Finally, we take a disjunction over all (m+++) conjunctions.
Our characterization of NoPE-AHAT (i.e. Proposition 4.1) implies an interesting inexpressibility result regarding PARITY (see (2):
Inexpressibility of PARITY.
Corollary 4.2. PARITY does not belong to NoPE-AHAT.
PARITY known to be accepted by AHAT (Barceló et al., 2024) and by SMAT (Chiang & Cholak, 2022) (with PE). Inexpressibility of PARITY in eength-generalizable subclass of SMAT and AHAT (with struet future masking and positional encodings) is known (Huang et al., 2025). Similarly, PARITY is not expressible by SMAT with strict future masking (Hahn, 2020). Corollary 4.2 comple- ments these results and is an easy corollary of Proposition 4.1 (see Appendix A.3).
5 APPLICATIONS
5.1 UNIVERSALITY AND UNDECIDABILITY OF TRANSFORMERS
Let us discuss why universalitylundeccibbiiii (i.e. Theorems 1.3 and 1.4) follow from Theorem 1.2. First, by the well-known theorem "MRDP" theorem (Matiyasevich, 1993) due to Matiyasevich, Robinson, Davis, and Putnam, every language in RE n Pl is a projection of language of the form Lp = {w E fai..... am }" p( (w)) = 0). where E Z[X Xmm] is a polynomial. Since Lp belongs to NoPE-AHAT UU. we thus obtain Theorem 1.3. Furthermore, since translation from polynomials to NoPE-AHAT [J] (and thus SMAT) is effective, this also implies Theorem 1,4: By the MRDP theorem (which is also effective), is undecidable whether given polynomial E _[X Xm. has a solution. Using our translations, we can turn such a into NoPE-AHAT (or SMAT) that is non-empty if and only if p has solution.
Using only two layers In fact, in Theorems 1.3 and 1.4, we even claim that two layers suffice for universality and undecidability. Let us sketch this here. First, our construction above yields a NoPE-AHAT of at most e layers, provided that the polynomials in the semialgebraic set all have degree S f (see Appendix A). In particular, we show that for each É, NoPE-AHAT[E, U] is closed rely the well-known fact that
under union and intersection (see Appendix A.2). Furthermore, the set of solutions of a polynomial equation p- = O can always be written as the projection of the set of solutions of system of quadratic equations. Since by stronger version of Theorem 1.2, intersections of solution sets of quadratic equations only require a NoPÊ-AHAT with < 2 layers, this yields the stronger versions of Theorems 1.3 and 1.4. See Appendix B for details (where we also show that with just one layer, Theorems 1.3 and 1.4 do not hold).
5.2 COMPARISON WITH C-RASP AND LTL WITH COUNTING
C-RASP (Huang et al., 2025; Yang & Chiang, 2024) is a simple programming language that can be converted into softmax transformers. In particular, it is subset of the so-called LTL with Counting (Yang Chiang, 2024; Barceló et al., 2024). For example, {w E ba, |w/o = (wla} can be written as the following formula in LTL with Counting: #a = #b. In particular, only linear expressions can be constructed in such formulas. We show in the appendix that LTL with Counting (and therefore C-RASP) only capture (semi)linear counting properties, i.e., boolean combinations of linear inequalities (and modulo arithmetics). so not languages like Lę := {w E {a. b) w &
a 2 [w/a)-
8

---

Published as a conference paper at ICLR 2026
Val. Perf.
Test Perf.
Gen. Perf.
10"
k
Val. Perf.
Test Perf.
Gen. Perf.
10
0.015
0.016/0.99
0.301/0.95
Loss
2
0.024
0.033/0.99
0.324/0.94
3
0.023
0.021/0.99
0.299/0.96
10-2
4
0.019
0.020/0.99
0.099/0.97
5 0.020
0.024/0.99
0.107/0.96
10-3
Performance of softmax transformer classifiers for L3 (k 1 5). Validation Performance (Val. Perf.): BCEWithLogitsLoss on validation data. Test Performance (Test Perf.): BCEWithL CCEEiitLLoggitl.ooo LosissLoss and Accuracy (separated by on data. Generalization Performance (Gen. Perf.): BogEWWttLogiis...om Loss and Accuracy (separated by /) on generalization test set. The y-axis uses logarithmic scale to accommodate the different orders of magnitude in the results.
Figure 2:
Proposition 5.1. LTL with Counting can define only (semi)linear counting properties.
EXPERIMENTS
In this section, experimentally complement main result (ef. Theorem 1.1) that transformers can capture solutions of polynomial equations of higher degree. particular, our results suggest that softmax transformers should be able to learn languages encoding solutions of polynomial equations.
We test our hypothesis on extensions of MAJ with polynomial inequalities. That is, we define the language La is defined by La {w (a, b3+ |w/b ([w[a)*). representing the of solutions for the simple equation y 2 xx
Do softmax transformer classifiers perform well on language L Additionally, can we observe tendencies of length- geiggh--eneealization!
In other words, the task of the transformer a binary classification such that ((w) accepts E L and it does not if w & Lk-
train softmax encoders without positional encoding and otherwise line with the vanilla model, introduced by Vaswani et al. (2017), as binary classifiers using components offered by Pytorch's h 10" data points sampled from L3 for 1..... 5 of
nn Module based on a balanced dataset conduct single epoch and choosed the best model words up length 500 In all experiments, conducting early stopping based on the binary-cross entropy loss combined with softmax, the typical metric for models outputring probability for binary classification, offered in numerical stable version by Pytorch's 's nn Module in form of BCEWithLoge seiggtssssssss on validation dataset sampled from the same distribution and of the same size as the training dataset. To partially explore the hyperparameter space, we conduct grid search over number of layers to 5, number of heads per layer or In all experiments, we fixed the input features 32, the feedforward dimension to 64, the dropout rate to 0.3, and optimized using the Adam optimizer with learning rate of 10-4 and weight decay of 0.01 as, again, offered by Pytorch's 's opt package.
Figure presents the outcome of our experiments. The table on the left-hand side demonstrates the best observed performance on the validation dataset (first column), balanced test dataset derived from the same distribution the training and validation data (second column). This specifically implics that this dataset also only includes words of length up to 500. The final column represents another balanced test dataset encompassing words from length 501 to 1000, used potentially unveil some length generalization performance. The plot on the right visualizes the same results.
Generally, observe very high performance with accuracy of > 0.99 on the in-distribution test dataset. Additionally, while the performance on the test dataset with longer words decreases, remains relatively high, with accuracy of 0.94 in all instances. Especially, it is to be assumed

---

Published as a conference paper at ICLR 2026
that with more extensive experimental setup, this gap in performance will decrease. Therefore, infer that our trained encoders perform well and that length generalization is supported, indicating that the model can capture the semanties of Lx- In Appendix D we report additional results, showing strong performance, with a decrease in performance on longer inputs.
7 CONCLUDING REMARKS
Related Work. Lots of work have been done in recent years on the expressiveness of transformers for general (not necessarily counting) properties (cf. see (Strobl et al., 2024)). Counting properties ee... the languages PARITY and MAJ have frequently featured in transformers expressivity research, which highlight their importance. Various theoretical transformer models have been used in the literature employing different assumptions on the attention mechanisms (hardmax attention vs. softmax attention), positional encodings, etc. For example, large proportion of results use hardmax attention, which is not used by practical transformers (which instead use softmax attention). In addition, some works (e.g. Pérez et al. (2021); Barceló et al. (2024)) employ extremely complex positional encodings with no restrictions. That said, several recent works have adopted more practical models. In particular, the works of Yang & Chiang (2024); Huang et al. (2025); Yang et al. (2024b; 2025) employ softmax attention transformers and simple classes of positional encodings (causal masking, local, etc.). Our results also employ a similar model (AHAT[U) and SMAT); in fact, we proved that semialgebraic counting properties can be captured by transformers without any positional encodings. Yang et al. (2025) gave a restriction of softmax attention transformers with bounded finite precision outside the attention computation, which characterizes C-RASP. Our experimental results seem to suggest this transformer model only lower-bounds the expressivity of real-world transformers, which can capture counting properties beyond C-RASP.
Concerning verification of transformers, we mention the works by Yang et al. (2024a) and Bergsträßer et al. (2026), showing that reasoning about Unique-Hard Attention Transformers (UHAT) are de- cidable with complexity EXPSPACE-comple captured by softmax transformers with bounded finite precision (Li & Cotterell, 2025). We also mention the recent work (Yang et al., 2026), showing that verifying C-RASP is undecidable.
UHAT is known to overapproximate what can be
Potential Applications in NLP. By Weierstrass theorem, polynomials can approximate any con- tinuous function of the number of occurrences of tokens. This suggests that transformers can solve practical NLP tasks that require computation of nonlinear statistics in the word frequencies.
Counting properties are tightly connected Vector Space Model (VSM) (Salton et al., 1975; Wong et al., 1985; Shahmirzadi et al., 2019) that has applications in text classification and similarity analysis, where the standard method has been to employ Support Vector Machines (SVM), together with kernel analysis (e.g. using polynomial kernels). Our results imply that transformers are expressive enough to perform such tasks. In VSM, a document D a vector Up indexed by "terms" that may occur in D. That is, uD [8] is count on the number of occurrences of in D. To compare similarity between two documents D, D', we may consider the Euclidean distance between up and up', which requires polynomial. Also, there are often challenges including "related terms" (e.g. husband, wife, and spouse). which are missed when we only use the aforementioned metric. Thus, a similarity measure is often learned (see Section 10.2.2 in (Shawe-Taylee & Cristianini, 2004), where VSM is used in combination with polynomial kernels). Our results show that transformers can solve such a task. A related task is the problem of determining proximity to a human written text, as dictated by Zipf (1935) stating that the frequency of the k-th most frequent word is proportional to 1/k in a natural language. As above, we may compare using Euclidean distance a document D with predetermined Vipf-vector. This results in a polynomial, and our results show this can be captured by transformers.
Future Work. We mention several open problems. Firstly, can softmax attention transformers with causal masking capture counting properties beyond semialgebraic sets? Secondly, our work has identified gap in the formalization the RASP-L conjecture by Huang et al. (2025). That is, transformers can capture and efficiently learn semialgebraic counting properties, which are beyond the language C-RASP. It is open whether the extension of C-RASP with inequalities over nonlinear polynomials still be captured by softmax transformers.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
We thank David Chiang, Michael Hahn, Andy Yang, and anonymous reviews for their feedback.
Marco Sälzer, Chris Köcher, Georg Zetzsche, and Anthony Lin are funded by the European Union (ERC, LASD, 101089343 and FINABIS, 101077902). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
Alexander Kozachinskiy is funded by the National Center for Artificial Intelligence CENIA (FB210017, Basal ANID, and ANID Fondecyt Iniciación grant 11250060).
REFERENCES
Cem Anil. Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay V. Ra- masesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Explor- ing length generalization in large language models. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances Neural In- Neural Information Process- ing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 December 2022, 2022. URL http:/ http://appersssseeee oc cappappr_pp...epeppppppppeeeeeep files/ palles/paper/22/// 222220aa2h/ 33755e4SSBe23338777ccaaaaaa2122
formation Processing Systems 35: Annual Conference
html.
Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, and Vladimir V. Podolskii. Logical languages accepted by transformer encoders with hard attention. In ICLR. OpenReview.net, 2024.
Pascal Bergsträßer, Ryan Cotterell, and Anthony Widjaja Lin. Transformers are inherently succinet. In The Fourteenth International Conference Learning Representations, 2026. URL https: / //openreviee ew net/ / forum? d= 92UUPIQ.
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, pp. 7096-71 16. Association for Computational Linguistics, 2020. doi: 1111665/V1//2200.MLL.PMM. 576. URL https: /doi org/10. 13653/v1/20/
emnlp mm....ain.........
David Chiang and Peter Cholak. Overcoming theoretical limitation of self-attention. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2022, Dublin, Ireland, May 22-27, 2022. pp. 7654-7664. Association for Computational Linguisties, 2022. doi:
URL https: h http://o.ioooooo .erliorgg110 18653/v1/200
a acl-long. 527.
Dmitry Chistikov. An introduction to the theory of linear integer arithmetic (invited paper). In Siddharth Barman and Slawomir Lasota (eds.), 44th IARCS Anmual Conference on Foundations
of Software Technology and Theoretical Computer Science, FSTTCS 2024, December 16-18, 2024, Gandhinagar, Gujarat, India, volume 323 of LIPlcs, pp. 1:1-1:36. Schloss Dagstuhl Leibniz-Zentrun für Informatik, 2024. doi: D0.220//IPCC..FSTTTS..00
Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Mareus Hutter, Shane Legg, Joel Veness, and Pedro A. Ortega. Neural networks and the chomsky hierarchy. In The Eleventh International Conference Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL https::/cpperewe
net / forum?irudddoo dww.mmidddwiixxeeeee...
Christoph Haase. A survival guide to presburger arithmetic. ACM SIGLOG News, 5(3):67-82, 2018.
doi: (445//242293332225509
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Trans. Assoc. Comput. Linguistics, 8:156-171, 2020. doi: 10.1162/TACL) A\ 00306. URL https://doi. org/10. /2//acll aaa_aaaalla__a_ee____ ___00306.
11

---

Published as a conference paper at ICLR 2026
Michael Hahn and Mark Rofin. Why are sensitive functions hard for transformers? In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2024, Bangkok, Thailand, August I 1-16, 2024, pp. 14973-15008. Association for Computational I Linguistics, 2024. URL htw.s::pp... http:///oo..or//////// 18633665lv
doi:
acl-long: 800.
Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention transformers: Perspectives from circuit complexity. Trans. Assoc. Comput. Linguistics, 10:800- 810, 2022. doi: 10.1 10.1162/TACLLAAA0000 00490.
00490.
Zellig Harris.
Distributional structure. Word, 10(2-3)146-162, 1954. doi: 10.1007/
010-9994--99---5 978- 94- 94-009-8466-7_1
URL https://link... wwr.ngiee.prrii.........e. com/ htt.::/r....oo/capate//0./.... chapter/10.1007.
Xinting Huang, Andy Yang, Satwik Bhattamishra, Yash Raj Sarrof, Andreas Krebs, Hattie Zhou, Preetum Nakkiran, and Michael Hahn. A formal framework for understanding length generalization in transformers. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025. URL https: /otppree///peeevieeeeee net / Eorum? 04 049N0V51uu.
Jiaoda Li and Ryan Cotterell. Characterizing the expressivity of tixed-precisie transformer language models. In The Thirty-ninth Anmual Conference on Neural Information Processing Systems, 2025. URL https::/// wwwpoeevvvseeeeeeeeeee evview .nt// forum? i d= WWWA
Yuri V. Matiyasevich. Hilbert's 's Tenth Problem. MIT Press, Cambridge, Massachusetts, 1993.
William Merrill and Ashish Sabharwal. A logic for expressing log-precision transformers. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems 36: Annual Conference Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023a. URL http:/tp:/ 24485877ccbbff 7 01118877777776665555550000223
nips ec wwtppppe_ffllss////eeecppscsssee wpwpsr/appeeeeeeeeeee / 22002//aaall html.
William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Trans. Assoc. Comput. Linguisticss 11:531-545, 2023b. doi: 10.1162/TACLLAI
_0056.. URL https: http://...........1.....//.///// ______2___666..
00062.
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing-complete. J. Mach. Learn. html.
Res., 22:75:1-75:35, 2021. URL ottp
Gerard Salton, Anita Wong, and Chung-Shu Yang. A vector space model for automatic indexing. Commun. ACM, 18(11)6113622, 1975. doi: 10.1145/3612119:311220 URL https://doi.
org/10. hxg/10.1100 100.1115533122 //1.//662219..122...
Marco Sälzer, Eric Alsmann, and Martin Lange. Transformer encoder satisfiability: Complex- ity and impact formal reasoning. In The Thirteenth International Conference on Learn- ing Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025. URL https: wpwnrevieneeeeeeeeeeeeeeeeeeeeee net/ wwt.:neeenttee/ee worum?id--vo33pdcl
Omid Shahmirzadi, Adam Lugowski, and Kenneth Younge. Text similarity in vector space models: comparative study. In M. Arif Wani, Taghi M. Khoshgoftaar, Dingding Wang, Huanjing Wang, and Naeem Seliya (eds.), 18th IEEE International Conference Machine Learning And Applications, ICMLA 2019, Boca Raton, FL, USA, December 16-19, 2019, pp. 659-666. IEEE, 2019. doi: 10.1109/CML 2019 20001 URL htwph:ttp//ccmm /tt::////ooo//// org 10 110 /ICMIA 2019. 00120.
John Shawe- Taylor and Nello Cristianini. Kernel Methods for Pattern Analysis. Cambridge University Press, illustrated edition edition, 2004. ISBN 0521813972. URL /ttp::////. wwww amazon. com/ Kernel - Modt Pattern- Aaarnnnnnallsiss.aaaa SSwwwehww---ee-
Michael Sipser. Introduction to the Theory of Computation. Course Technology, Boston, MA, third edition, 2013. ISBN 113318779X.
12

---

Published as a conference paper at ICLR 2026
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal languages can transformers express? A survey. Trans. Assoc. Comput. Linguistics, 12:543-561, 2024. doi: 10.1162/TACLI AI 00663. URL https:://// http://ooooooooo///////// 1t//g/100. wtt.:.1112ttat..
a 00663.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5998-6008 2017. URL https: /ttttps:/pprceee http://pooceeeeeeeeeeeeeecc neurips cc/ wtcppappr/2013 /hash/ Abstract html.
S. K. Michael Wong, Wojciech Ziarko, and P. C. N. Wong. Generalized vector space model in information retrieval. In Jean Tague (ed.), Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, Montréal, Québec, Canada, June 5-7, 1985, pp. 18-25, ACM, 1985. doi: 10.11455253495.55550 URL https: //doi.org 10. 1145 253495 253506.
Andy Yang and David Chiang. Counting like transformers: Compiling temporal counting logic into softmax transformers. CoRR, abs/2404.04393, 2024.
Andy Yang, David Chiang, and Dana Angluin. Masked hard-attention transformers recognize exactly the star-free languages. In A. Globerson, L. Mackey, D. Bel- grave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang (eds.), Advances in Neural In- formation Processing Systems, volume 37, pp- 10202-10235. Curran Associates, Inc., 2024a. URL https: http::://ppoceeeinng. neurips cc/paper_fileeeeeeeeeeeeeeeeeeee ppppp/202/////////////////////2/ f Paper- Conference, .df..
Andy Yang. Lena Strobl, David Chiang, and Dana Angluin. Simulating hard attention using soft attention. CoRR, abs/2412.09925,, 2024b, doi: 10.48550ARXIV:2412.00999 //doi.org/11.
URL https:
Andy Yang, Michaël Cadilhac, and David Chiang. Knee-deep in c-RASP: A transformer depth hierarchy. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. URL https: opwnrevieww.e..ee////e/.e net forummid=:Puuuiiiii yxyfw.
Andy Yang, Pascal Bergsträßer, Georg Zetzsche, David Chiang, and Anthony Lin. Length general- ization bounds for transformers, 2026. Under submission (preprint: https: weoooo. org/ records/ / 18800000).
Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Joshua M. Susskind, Samy Bengio, and Preetum Nakkiran. What algorithms can transformers learn? A study in length generalization. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. URL https: wpwpreveee.eeeeee////pp.. n forum? fimmm?dd=Ass HnHMHXX
George Kingsley Zipf. The Psychobiology of Language: An Introduction to Dynamic Philology. Houghton Mifflin, Boston, MA, 1935.
A TRANSLATING SEMIALGEBRAIC SETS TO NoPE-AHAT
A. FINE-GRAINED ANALYSIS OF POLYNOMIAL DEGREE VS. DEPTII
In this subsection, we show the inclusion SemiAlg C NoPE-AHAT(U) In fact, we show a stronger
statement (Proposition A.1), which requires some notation. By SemiAlg < E] we denote the restriction
of the class SemiAlg to the semi-algebraic languages L C Σ* such that the underlying semi-algebraic set S C Nm is Boolean combination of sets Sp where p E 2 2[x,,..., Xm) polynomials of degrec < f. In particular, we have SemiAlg[< 1] = QFPA. Our construction for SemiAlg S NOPE-AHAA[U] actually shows the following:
Proposition A.I. For each e > 0 we have SemiAlg < A NoPE-AHAT UJ.
13

---

Published as a conference paper at ICLR 2026
For showing Proposition A. need some more technical definitions. Let T be AHAT with input embedding :: Σ + Qii and layers d (Q"4)* + (Q"")" de: (Q"))) + (Q":11)*. We define the function fr: E Q as follows: for word 01 .......0. an E ΣT, if X ....
)e(u(a)).-.. ((an)) = ( yn), then fr(w)= = (n In other words, we have fr(w) > 0 iff T(w)= 1.
Proposition A.2. For every polynomial p E Z X of degree e, the language L,20 = {w {ai..... am) }" (w)) > 0} belongs to NoPE-AHAT U.
To show Proposition 3.1, we will use polynomials that are homogeneous, meaning all monomials have the same degree. Note that given an arbitrary polynomial p E _[X ......... Xm] of degree l, we can consider the polynomial E _[Xo:.... Xm] with q == xxpp X1 Xm ). which is homogeneous. No
No
Im > O. Therefore, from now on, we assume that we have a homogeneous polynomial g X ................................ Xm) and want construct an AHAT for the language K₂ = fw E fai..... am. }" g(1 x) > 0 for x (w))).
It has the property that p(r,,,... Fm) > O if and only if,
To simplify notation, we denote the end marker $ by ag. Thus, the imput will be a string e {ao...., Jm J that contains ag exactly once, at the end. Since ww)
is satisfied automatically, our AHAT only has to check that ( ,....,, .mmm > O, where 2; |w/a.. The input encoding the map {ay.... am | + Q" with + ej. where E Q"" is the i-th unit vector.
In first lemma we show that each monomial of q can be computed by a NoPE-AHAT with l uniform attention layers.
Lemma A.3. For every monomial Z[Xo, Xi,..., Xm] of degree E, there is NoPE-AHATT with uniform attention layers such that
r(V(w))
fr(w)=
|wlt
for each word w E E". In particular, we have fr(w8) > O if and only if (f:() > 0.
Proof. We use the word embedding ;: Σ + Quet1 with c(a;) = e; for each i E [0, m].
Step I: Compute frequencies Our AHAT first uses an attention layer to compute m + new components, where i-th component holds di RtFT. where n + 1 is the length of the input (including the end marker). This is easily done by attending to all positions and computing the averages of the first m components. To simplify notation, we will index vectors starting with index O.
Step I: Multiplication gadgets Second, we have a sequence of gadgets (each consisting of one uniform attention layer and one ReL.U layer). Each gadget introduces new component, and does not change the existing components. Between gadget executions, the following additional invariants are upheld: (i) Overall, gadget does not change existing components: it introduces one new component. (ii) The components {O...., m are called the initial components. (iii) All other components are uniform, i.e. they are the same across all positions. (iv) The uniform components carry values in [0. 1]. Thus, we will call components O..... m the initial components; and we call components >> m the uniform components.
Our gadgets do the following. Suppose we have already produced k additional components. For each initial component E [0, m) and uniform component j E Jm + 1,m + 1 k), gadget omult(k, i, j). which introduces new component, will carry the value 2e:81 ntI where Yj is the value in component, I, to denote the number of a, occurrences in the input for i [0, m].
of all vectors. Recall that
We implement the gadget omult(k; (s, i, j) using some ReLU layers and an attention layer. Suppose that before, we have the vector Up E Qm in position p. First. using ReLU layers, we introduce new
component that in position p has the value [ ut,,)] []] This can be achieved since up [i] is in {0. 1) and up[s] [0, 1]: Notice that up [0] upp
ReLU(u, - - (i)). Indeed, if up = 1) = O. We then use uniform attention to compute the average this new u, [i] ut Li] coompnentt across all vectors. Since there
then this evaluates to un if up [] = O, then we get ReLU(u,,
[i];
+ 1 vectors, exactly 2; of them have u. i 1, and also up j] Mý. we get the desired scy; p+1
14

---

Published as a conference paper at ICLR 2026
91
dg
Mi
N2
(
Figure 3: Visualization of the proof of Lemma A.4.
Step III: Computing the monomial We now use our gadgets to compute the value of the monomial. Let (Xo,, .m, = X1, ...Xi.. We use É - gadgets to compute Iı, "..Ii,/ + 1) The frequency computation in the beginning yields x,, / (n + 1), and then we use gadgets to compute Ty Liz/ / + 1)², Iq Big (n (n= 1)S, etc. until Ti, x,,/ / 1)º. Finally, we use ReLU layer to multiply Ti Ti, (n + 1) with a. Thus, we have computed r(zo, tmm 1
A.2 COMBINING NoPE-AHAT(U) WITHOUT ADDITIONAL LAYERS
The following lemma states that two NoPE-AHAT with only uniform attention layers can be paral- lelized resulting in a NoPE-AHAT with the number of uniform layers. Their outputs can also be combined via ReLU neural network. In particular, NoPE-AHAT(S f, UJ is closed under union and intersection.
Lemma A.A. Let T2 be two NoPE-AHAT with É uniform attention layers and let N be ReLU neural network computing a function N: 02 - Q. Then there is a NoPE-AHAT Ty with & uniform attention layers computing fIx (w8) N (fr, (w8), fr, (w8)).
Proof. The idea of Ty is, that concatenates the components from Ti with those of T2 and keeps the sets of components always disjoint. By uniformity we are able to apply the attention layers of Ti and T2 in parallel. In the last attention layer can simply apply N to the first components of Ti and T2.
By 4: E Quh.s we denote the word embedding of T, From this we construct new word embedding :: Σ +th, with ((as) = (Li(a)), (2())) for each j E ml].
Now, let AR.I: Qude. - Qde+s.s be the kth layer of T; for S k. S f. By K,, Qi, Vi, and M; we denote the parameters of A Since A uniform, the key and query maps K, and Q2 are constantly mapping zero. We now construct uniform layer Ag: Qde,+ + Qde+1,1 1ode+1,--d+11- dd composed of AR, and A the key and query maps K and Q still map to zero. If V((x)) A, + b; then we define the new value map by
A 0
b1 b
(A131
bi
Vi (Vi(aa)) (V((x2))
V
32
A2
32
A222 ba)
By this definition obtain that the attention vectors aj in A are the concatenation of the attention vectors aj and aj2 in AR.1 resp. AR.2- Similarly, we build the composition Ni and N₁2 resulting in FFN computing (ates,
Finally, in the last layer, we add the FFN A that takes the first components of the output of Ma az,)) and simulates N on these two numbers.
Recall that from polynomial p Z[X,, Xml we constructed homogeneous polynomial q E Z[X,,X, X,...,,,... such that p(x) > 0 and only if q(1, x) > 0 holds for all vectors QTh Let r, rk 2(X,, X1,..., X.m be the monomials in q. Since g is homogeneous, all
15

---

Published as a conference paper at ICLR 2026
monomials have the same degree f. Lemma A.3 yields NoPE-AHATs T T3 that are computing the monomials ry. Each of these AHATs has exactly & uniform attention layers. Finally, we can apply Lemma A.4 to construct NoPE-AHAT T with uniform layers computing fr (w8) = v(((w)))
1w8/
(since addition is an affine map). Then T accepts iff q(V(w))) In other words, T accepts the language Tp20
|w8f > iff of (V(()) 0 Of ((V(w))
A.3 INEXPRESSIBILITY OF PARITY
Proof of Corollary 4.2. By Theorem 1.2, it suffices to show that PARITY is not semi-algebraic. Suppose it is. Then there is a disjunction of conjunctions of polynomial inequalities that characterizes PARITY. The polynomials are over Z[X, Y), where X is the variable for a's and Y is the variable for b's. By plugging in Y = 0, we conclude that the set of even numbers is semi-algebraic. Hence, there is a disjunction V==1/ (X) > of conjunctions that satisfied exactly for the even numbers. This implies that for some i, there are infinitely many even numbers such that A==1 (k) > 0. Therefore, for every j E ml,, the leading coefficient of Pi, must be
positive. But then, AT (k) > 0 must hold for all sufficiently large k not just the ones, contradiction.
B PARAMETRIC ANALYSIS
In this section, study how the expressive power of NoPE-AHAT(UJ and SMAT depends on the number of attention layers. In particular, we show that Theorems 1.3 and 1.4 hold already in the case of two layers. The main insight of this proof is that the number of layers needed to express semialgebraic set depends on the degrees of the involved polynomials (see Proposition A.1): Note that our sketch of NoPE-AHAT for Lę>0 in Section directly yields NoPE-AHAT with E layers, where e is the degree of p. For Proposition A.1, one then has to show that Boolean combinations of such sets can be expressed without growing the number of attention layers. See Appendix for details.
Capturing RE with two layers From Proposition 1. we can now deduce the wwo-attention-lyee version of Theorems 1.3 and 1.4. The first ingredient is the following version of the MRDP theorem on Diophantine sets (Matiyasevich, 1993):
Theorem B.1. Ler Σ = (ai...., ..m...,,.... ). A language L C E' belongs to RE PI if and only if there is k N and a polynomial p E Z(X1,... Xm+k] such that L Tai........ (K), where
K = fw {a )m [ 0}.
In other words, every language in RE n Pl is projection of a language of the form Lp fw e (ai...., am }- p( (w)) 0}. where p E Z[X]..... Xm] is a polynomial. Thus, it suffices to place Tup in NoPE-AATPA 2, UJ). First observe that in Theorem 1 1.2, we use one attention layer for each multiplication, so this avenue is closed if we want stay within two attention layers. Instead, we use that for every polynomial
X,), there are quadratic (i.e. degree 9r E Z[X [[XX.......... ]] for some r, k 2 0 such that for æ Nm we
E Z
< 2) polynomials have p(æ) 0 if and only if there is some E N with qi (æ, y) = O...., (x, 0,....9r(24. y) 0: Just introduce a fresh variable for each multiplication in p and use the qi to assign these fresh variables. Since the language K := {w E fai..... am+*)
Xm+4]
()(V(w)) belongs to SemiAlg < 2] (since the qi have degree < 2) and I.p, is projection of K, this means T.p belongs to Proj (reemiAlg 2)). By Proposition A. Proj(SemiApp
91 (V (w))
2)) C PooP-AAAT (< 2, U)).
NoPE AHAT with single layer The fact that two layers suffice for universality among counting properties raises the question of whether this even possible with a single attention layer. We show here that this is not the case:
Theorem B.2. NoPE-AHAT(S 1| = NoPE-AHAT(S 1, QFPA.
This means, with a single attention layer, NoPE-AHAT can recognize precisely those counting properties expressible using quantifier-free Presburger formulas. Since satisfiability of Presburger
16

---

Published as a conference paper at ICLR 2026
arithmetic is well-known to be decidable (Haase, 2018; Chistikov, 2024), this implies that universality and undecidability of NoPE-AHAT (as we have shown for two attention layers), do not hold with just attention layer. However, leave open whether SMAT with one attention layer have decidable emptiness problem.
Before going into details, let sketch the proof of Theorem B.2. For the inclusion NoPE-AHAT Il I QFPA, we proceed similarly to Proposition 4.1, while observing that the inequalities we have to verify are all linear inequalities: This is because single attention layer averages only once. Conversely, for the inclusion QFPA C NoPE-AHAT|S 1, U] follows easily from Proposition A.1.
Proof of Theorem B.2. We begin by proving that NoPE-AHAT|< 1] S QFPA. Let be an AHAT
with input embedding :: Σ {8) - Q" a single AHA layer utilising affine maps Q, K E Quaxd V E Qixd, given matrices, and the ReLU network N Qu+tk - Q Our goal is to construct
quantifier-free PA formula yor with variables z, for E {1...., | such that L ([ = {w E
Σ'
T accepts w8}. J. In the following, we assume Σ = {a1,-.... am and denote Σ U (S} by E'.
First, we observe that for all words w E E,, the output of T given wS is computed by
1
N (())
168 aa Ve(as,)
W Rij +
where I' = fa........ Oin J S E' is exactly the subset of symbols ai, occurring in w$ that maximise (Qi(ar,): ), (S)). We construct for such that it mirrors exactly this computational structure. We have for V Vigg' frr where V ranges over those subsets I where (Qu(ai,). ) K (()) is maximal for precisely the ai r. The subformula for is defined follows. For now, we assume that $ & I and introduce some auxiliary formulas. Throughout the following construction steps, we assume that atomic formulas are normalised the form c + Cn S b.
Given the ReLU network Nf, it is straightforward to construct quantifier-free PA formula & such that [ exactly includes those Ti...., leth E Nd+k satisfying . (z
where (.)) denotes the first output dimension of N. The key idea here is that the computation of a single ReLU node o2, Fdttk) = y. with weights e; and bias b of N, is described by the quantifier-free PA formula: (cıæ) - Ca4 + < O/00 y) V (cTæ) + +2+ &.Ed+ A 2 + +.... + Ca+ &. + y). Then, by nesting this construction iteratively from the last layer to the first layer of N,, and finally replacing = y with 0 in the atomic formulas related to the first output dimension of N, we achieve the construction of w This nesting and replacement also ensures that yVV includes only the variables ,,...., Zddkk-
+
Let r C such that r {am..... 4i, }. Consider the ReLU network N, the value matrix V, and the embedding We construct a quantifier-free PA formula N.V such that [ N. exactly includes those (Ii No satisfying (((nnngN(((())))))))))))) z., +2, Σj= Ve(as,)) )), > 0. To do so, we adjust the formula s/ as described in the following. To account for the fixed input <(8), we replace each occurrence of œ1 to in vp by the respective entry of z(S). Furthermore, to handle the specific form of the input #ig toi ΣE= Di Vi(ai,). ). first replace each occurrence of rd+1 with E {1,...,k) in the already modified vo by:
(vI1)(a;)) +... + viau(as, Ja)x;, +...+ (vii((a;,) + vrai(ai, )a) where Uty are the respective entries of V. Lastly, we replace each atomic constraint C1 +...+ Ci 5 in the adjusted formula with (c1 b)z,, + +.... (ch- - b)r,, I 0 to adjust for the factor present in the input.
Now, we define frr as N.V. If E I, we adjust V. slightly. Assuming $ ai, E F. we replace the variable xi, with the constant in yp N.V. Given this construction, it is clear that V (-(([=r])= = {w E E T accepts wS}, as for mimics the computation of T for all possible attention situations I.
V.
For the inclusion QFPA S NoPE-AHATI<, UJ, we observe that QFPA C SemiAlg(s 1), and thus the inclusion follows from Proposition A.
17

---

Published as a conference paper at ICLR 2026
C COUNTING PROPERTIES EXPRESSIBLE BY OTHER MODELS
C.I SEMILINEAR COUNTING PROPERTIES
counting property P S N' is said to be semilinear if can be defined as a boolean combination of inequalities over linear arithmetic expressions (over variables ....... Zd and integer constants) and modulo arithmetic expressions of the form 2, = (mod b), where a, b E N are fixed constants. In particular, semilinear counting properties cannot define semialgebraic counting properties involving polynomials of degrees 2 or above.
It is also convenient to use quantifiers when defining semilinear sets. In particular, they do not increase the expressive power since they can eliminated. This results in the logic called Presburger arithmetic (PA), which refers to the first-order theory of the structure (N; +, 0, <); see Haase (2018); Chistikov (2024).
C.2 PERMUTATIIO LANGUAGES OF LTL WITH COUNTING
[Count has the following syntax:
Φ == a t t Φ Φ V Φ X ØU
1 :: l #
1++
where E E and & E Z. Next we define the semantics of LTL(Count). For any word w a1a2....0 E D with a1 a1,02........ .2...., Og E 2, for each 1 S i < l, and each formula ø E LTL[Count] we write w, i -= o if the formula è is satisfied in at position i. Formally, this relation is defined inductively as follows:
w. i + (for Σ) iff a.
w. i == - iff w. i / d.
i = o V ve iff w. i F á or w v
w, = X i and w, w o. w. i o U & iff there is i S S & with w.j - vb and for all S k < j we have w, = o.
w, - t1 to iff [t,](w, i) < [w,] i) where the semantics [t] Σ- N + Z of
a term t is defined as follows: [k] (w, i) = k, [t + t,l i) = [t [w, i) + [t]] i).
[k. #ol k. |1 S < w. F Φ11, and [k- #ol k. Kis S < e w,j =
Our main result on LTL[Count] is the following: Theorem C.I. Every ceomuutationinvariiin language definable in LTL[Count] has a semilinear Parikh image.
Before we can prove Theorem C.I, we need a few more definitions. For an alphabet Σ write Ee for the set E U {s). (d-dimensional) Parikh automaton is tuple X = (Q, Σ, i, A, (Co)gE)) where Q is finite set of states, Σ. is the input alphabet, e Q is initial state, A C Q Eg x Nd Q is a finite transition relation, and Cg S N' are semilinear target sets. A word w E D" is accepted by 2 if there are a1 02 .... Og E Σg. states such that (i) qu and Vn with 1; 0, + x,, and (iii) E Cy. The accepted language L of 21 is the set of all words accepted by 21 is a well-known fact that for each Parikh automaton A the accepted language L( has a semilinear Parikh image. Observe that O-dimensional Parikh automata are essentially NFA and, hence, accept exactly the regular languages.
....... E Q. and vectors Vo UI...., U2 E Nd (ii) for each 0 S < l there is a transition (4i, ag 3i gi+1) )) E A
A Parikh transducer is Parikh automaton with input alphabet Σ, x T where E and I are two alphabets. The accepted language L( C Σ' x I" of a Parikh transducer can also be seen as a map: if (v, w) L(2l) then we can see the input and w the output of the transducer. Formally, for an input language L C Σ" a Parikh transducer computes the output (L) = [w E I' Ee E L: (v, w) E L. If L is accepted by Parikh automaton then Ta (L) is also accepted by Parikh automaton. To see this, we can take the synchronized product of the Parikh automaton B accepting I and 2 (i.e., B reads the same letter from the input as 2 in its first component). Accordingly,
18

---

Published as a conference paper at ICLR 2026
cascading of Parikh transducers is also possible, i.e., if 21 and B are Parikh transducers over Σg x Te and r. x Ilg, we can also construct a Parikh transducer e over De x IIg computing Te = Tay Tx.
With the definition of Parikh automata and Parikh transducers we now able to prove Theorem C.I.
Proof. Let & E LTL[Count] be formula such that the described language L(Ø) is permutation invariant. We will prove by induction on the structure of & that the Parikh image of L(ő) (or actually bounded subset of L(ő)) is semilinear. Here, a language L S Σ" is bounded if there letters 01, ag....,, O2 E Σ with L S aja; ... a So, let 01. 0g...., ag E Σ be distinct letters with E {ai, "n Then ((ø) N aajz- ..... dz is clearly bounded and has the same Parikh image as T(()).
For each subformula 1 of construct a Parikh transducer that labels each position satisfying v. In the base case, we decorate each letter a by b E {0, 1 where bli] = 1 iff a; a. Note that this transducer handles all atomic formulas a Σ at once. For 1 Xi V X2 we add the decoration b E {0, I} to each letter where b = 1 iff one of the decorations corresponding to X1 and X2 is 1. There are similar transducers (which do not introduce counters) for the cases & = ~ v = X X. and a = X1 U X2. Note that applying these transducers to bounded language always yields another bounded language.
Now, consider a counting subformula, i.e. 3 = 1i=1k #x Eiz Ky #X S k. Observe that the set of positions satisfying á is convex in the set of positions satisfying any X This is true since we consider only bounded input language. Hence, we can split the input word into three (possibly empty) intervals: (i) the positions at the beginning of the input that do not satisfy v (ii) the positions where all positions satisfying a Xi also satisfy v), and (iii) the positions at the end of the input that do not satisfy a/. We describe in the following a Parikh transducer with 3 Ea many counters- one for each of these three intervals and each formula Xi. The transducer guesses the three intervals (note that this is non-deterministic). counts positions satisfying a Xi accordingly, decorates only the positions in the second interval labeled with Xi with (and everything else with a 0), and validates in the end our choice of the intervals (via appropriate semilinear target sets ensuring that the equation in is not satisfied in the first and third interval and is satisfied in the second interval). Clearly, this all can be done in one (non-deterministic) Parikh transducer.
Finally, we have a cascade of (Parikh) transducers decorating each position in a bounded input word with a Boolean value indicating whether & holds in that position. If we use ajaz ... az as input language for our transducers (note that this language is regular) and intersect the output with all words decorated with a in the first position, we obtain a Parikh automaton accepting exactly the language [(Ø) ajaz ... an Since Parikh automata accept only languages with semilinear Parikh image, we infer that (.))) Majaz ..0, and, hence, T.()) have a semilinear Parikh image.
n
D FURTHER EXPERIMENTAL VALIDATION
In this section, we report additional experiments addressing a similar research question as posed in Section 6, namely, do softmax transformers perform well on formal languages with inherent non-linear counting properties? Therefore, we consider the language
T4. = {a "" "ammn"nmnii [m, n E N21)
for selected values of i and j. Clearly, recognising this language requires non-linear counting capabilities. Moreover, contrast to L& (see Section 6), this language poses greater challenge in learning tasks due to its structure (all b's follow all a's followed by all c's) and larger alphabet size.
The experimental setup is identical to that presented in Section 6. The results are presented in Figure 4 for five distinct combinations of i and j. Similar to our previous experiments, the table on the left shows the highest observed performance on the validation dataset (first column) and the best performance validation data (second column). This indicates that this dataset also contains only words of length up to 500. The final column represents another balanced test dataset of words from length 501 to 1000, utilised to potentially reveal length generalisation performance. The plot on the right visualises the results reported in the table.
a balanced test dataset derived from the same distribution the training and
19

---

Published as a conference paper at ICLR 2026
Val. Perf.
Test Perf.
Gen. Perf.
Val. Perf.
Test Perf.
Gen. Perf.
100
1,3
0.016
0.02/0.99
0.03/0.99
10-1
3,2
0.002
0.003/0.99
0.60/0.93
3,3
0.001
0.002/0.99
2.26/0.85
10-2
4,2
0.001
0.001/0.99
0.26/0.96
5,1
0.004
0.004/0.99
0.03/0.99
10-3
Figure 4: Performance of softmax transformer classifiers for Ls, (for selected set of and combinations). Validation Performance (Val. Perf.): BCEWithLLogissoos on validation data. Test Performance (Test Perf.): BCEWithLogitsLoss and Accuracy (separated by /) test data. Generalization Performance (Gen. Perf.): BCEWithl logitsl oos Loss and Accuracy (separated by /) on generalization test set. The y-axis uses logarithmic scale to accommodate the different orders of magnitude in the results.
We again observe very high performance of our trained softmax transformers the in-distribution test dataset (second column), which shares the same distribution as our training dataset. The performance generally remains high the generalisation test (third column) well. We witnessed slight decrease compared to the results on the in-distribution test in the case of L3,3 (accuracy of 0.85). A general decrease performance on longer inputs expected and also witnessed other studies (cf. Huang et al. (2025)), but also indicates that focused studies are essential to reveal rigorous insights into the relationship between the expressibility of polynomial counting properties we established and their practical learnability.
20


Reviews:
[{"review_id": "Yf1xZImhqm", "reviewer": "Reviewer_sqAV", "summary": "This paper formally studies the counting power of transformers, i.e., which counting properties of the input can transformer models represent. The authors substantially expand on prior understanding, showing that the answer goes well-beyond previously studied (Boolean combinations of) linear properties, to (Boolean combinations of) polynomial properties of the number of occurrences of various tokens in the input. Along the way, they also define and motivate counting properties, and provide a small empirical confirmation of the findings. Towards the end, they make connections to universality and undecidability of certain classes of transformers.", "questions": "Please see the comments above about the (implicit) assumptions on the datatype and precision, and on intuitions. Clarity on any of these fronts would be great to have!", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "* Well-motivated and nicely written paper. While technically strong, its pitch and claims will also be accessible to broader audience not deep into theoretical research.\n\n* I liked the structure of the paper and how it (quickly) conveys the findings and uses many examples to explain concepts.\n\n* That the studied transformer model uses simple (or no) position encodings and the standard softmax attention (either directly or through AHAT[U] which is a special case of softmax) is a positive, especially compared to some efforts that have relied to unrealistically complex position embeddings and other design choices in their analysis.\n\n* The main result about transformers being able to capture counting properties well beyond (combinations of) linear properties is a strong technical advance. Having an empirical support for it is a plus.\n\n* The connections to undecidability are intriguing, though I must say the corresponding sections can use some more clarity of exposition.", "weaknesses": "* While it's valuable to have an **empirical validation**, I felt that section 6 is not as well described and discussed as the rest of the paper. E.g., even the metrics mentioned in the caption of Fig 1 need clarification.\n\n* There are some places where it would be valuable to state which **design decisions / assumptions / choices** play an important role. E.g., it seems to me that Prop 4.1 (that whatever NoPE-AHAT can compute is expressible semi-algebraically) relies on the assumption of ReLU as the non-linearity; I suspect it will also work with any polynomial non-linearity, but not with sigmoid, inverse-tangent, or other choices that have been used in practice. (And this is fine, I just think it's better if the authors can call it out.)\n\n* The paper can also use a clearer treatment of the **datatype** assumed for the transformer model. Section 2.1 starts with *real* vectors, which clearly isn't realistic, at least for arbitrary precision. Later, the ReLU paragraph switches to *rationals*, leaving some lack of clarity. The choice of datatype -- and importantly the *precision* (how many bits are allocated, and whether they depend on the input length $n$ -- is an important consideration in transformer expressivity results, but seems to be lacking here. E.g., when, in the proof of Prop 3.1 (that semi-algebraic counts can be expressed by NoPE-AHAT[U]) the transformer is computing $u_p[j] \\in [0,1]$, this is presumably expressed as a rational where the numerator (and denominator) can grow very quickly. Their size should be bounded in terms of $\\ell$ and $n$, though. It would be helpful to get some clarity on this front.\n\n* Some of the proof ideas can use a short discussion of the **intuition**. E.g., in the proof of Prop 3.1, we are multiplying two integers (represented as rationals). A priori, it's unclear how a transformer might be able to do so! The key observation, I believe, is that one of the items being multiplied, namely $x_i$, is always a *count* of letters in the input word, and thus distributed across the input as captured by $u_p[i]$ being 0 or 1 at various positions $p$. Thus, one can get around the usual difficulty of multiplication by instead multiplying $y_i$ with a 0 or a 1 at each position, ensuring that there are exactly $x_i$ positions with a 1, and then using attention to aggregate. Is this the right intuition? In any case, adding some intuition would help.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "z8JaezWILK", "reviewer": "Reviewer_XAw7", "summary": "This paper investigates the counting power of Transformers.\nWhile prior work on Transformer expressiveness has shown that Transformers possess semilinear counting properties, this paper demonstrates that Transformers can express all semialgebraic counting properties.\nIt also shows that Average Hard Attention Transformers (AHAT) without positional encodings (PEs), as well as their subset AHAT[U] that uses only uniform layers, precisely capture semialgebraic counting properties.", "questions": "- Are there practical situations where nonlinear counting is required for tasks usually solved with Transformers?\n- Is it possible to define a new class of language, e.g., LTL with nonlinear counting?\n- I could not understand the paragraph beginning at Line 355.  \n  Regarding the arbitrary choices among the $2^{r+(m+1)^2a}$ options representable by AHAT, why is it “easy to do” to construct the polynomial expression of $u\\_{\\ell, i}$?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Understanding the expressive power of Transformers is an important research topic.  \n  This paper presents new results on counting capabilities that were not clarified in previous work.\n- The paper is concise and readable.\n- The theoretical results are supported by experiments.\n- Although I had some questions, the theoretical part appears mostly correct.", "weaknesses": "- It is unclear how practical it is to apply Transformers to nonlinear counting problems as discussed in this paper.  \n  For sequences such as text, which Transformers typically handle, input order is important, and tasks are generally not permutation-invariant.  \n  Therefore, studying permutation-invariant input properties may have limited practical relevance.  \n  As the authors discuss in the paragraph beginning at Line 263, combining counting properties with other characteristics is interesting.  \n  However, it is not clear whether nonlinear counting is necessary in such cases.  \n  In fact, the use case shown at Line 264 can be realized with linear counting.\n\n- The proof of the main result, Proposition 3.1, seems somewhat trivial.  \n  The idea in Step I, computing the frequency via a Transformer layer, has already appeared in prior work such as Yang & Chiang (2024).  \n  Step II, which performs multiplication, also appears straightforward.\n\n\n## Minor comments\n\n- Line 22: properties.. => properties.\n- Line 161: (a.k.a. Parikh map => missing ')'\n- Line 180: I think the fourth vector should be (0,0,1, 1/4) if we use the one-hot embeddings.\n- Line 190: (x_1, \\ldots, x_n) => (x_1, \\ldots, x_m)? \n- Line 205: duplicated ':='.\n- Line 213: x_j \\tau => x_j / \\tau\n- Line 227: duplicated ','.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QxkOwmutuc", "reviewer": "Reviewer_2cZ9", "summary": "The paper provides a theoretical analysis on transformers’ ability to perform counting operations. It is shown that transformers can capture all semialgebraic properties, meaning they can evaluate polynomials where variables are characterized by symbol counts (for instance, accepting strings s.t (#a)^2 + (#b)^3 > 0). The proof mainly consists of demonstrating that average-hard attention transformers (AHATs) with no positional embeddings exactly characterize semialgebraic sets. As a direct corollary, they are able to show that AHATs with no PEs cannot recognize Parity. Furthermore, by connecting this result with the MRDP theorem (which states that there is no algorithm that determines whether some given Diophantine has a solution), they provide an undecidability result for transformers: it is undecidable to determine whether their language is empty or not.", "questions": "N/A", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The perspective on semialgebraic sets rather than semilinear sets is novel and generalizes prior results on the counting power of transformers\n2. The corollary on inexpressibility of Parity is interesting and accompanies a rich body of work tackling this question\nNovel tools to me such as semialgebraic sets and Parikh images were introduced well enough for me to understand the technical parts of the paper\n3. Introduction is well written and puts in perspective previous work on semilinear counting with transformers", "weaknesses": "1. Importantly, this paper disregards the impact of precision. In the finite-precision regime (which describes transformers used in practice), it is impossible to store counts from uniform attention for any input string. Recently, the expressive power of fixed-precision transformers (SMATs and AHATs) has already been characterized by a subclass of regular languages [Li and Cotterell, 2025] (and therefore can not perform counts across all possible strings), undermining the relevance of the paper’s main claim on counting. I would recommend at least mentioning this inherent limitation.\n2. The experiments consist of training transformers on a single type of polynomial (comparing (#b) and (#a)^k) rather than a more diverse set of polynomials with different coefficients of different degrees. Experiments on polynomials with a larger alphabet, different coefficients with different degrees would consolidate the claims of the paper. Even better, training on randomly sampled polynomials would be a great contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RtqzZw2r4f", "reviewer": "Reviewer_EZ5n", "summary": "This paper theoretically investigates the capabilities of encoder-only Transformers to recognize formal languages. Specifically, it focuses on languages characterized by polynomial inequalities based on occurrence counts. The authors leverage this analysis to present a related undecidability result for Transformers. The theoretical findings are empirically validated on the language class $L_k = \\{ w\\in \\{a,b\\}^+: |w|_b \\leq |w|_a^k \\}$.", "questions": "1. Could the authors elaborate on the size requirements (e.g., depth, width) for the Transformers needed to express the counting properties discussed in Theorem 1.1 and other results? Specifically, how does the required model size scale with the parameters of the formal language (e.g., the degree of the polynomial)?\n\n2. The current experiments are focused on $L_k$. Are there other language classes the authors considered that would serve as interesting and challenging testbeds for this theory?\n\n3. To help bridge the gap between this theory and practice, could the authors speculate on any practical NLP tasks (e.g., in semantic parsing, logical reasoning, or program synthesis) where these specific polynomial counting abilities might be relevant?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper's primary contribution is extending prior work on the counting abilities of Transformers. By generalizing the analysis from linear functions of occurrence counts to polynomial functions, the work advances our theoretical understanding of Transformer capabilities in this domain.", "weaknesses": "1. Given the theoretical nature of the paper and the numerous formal language concepts, the presentation would be significantly clarified by adding a Venn diagram. This could visually situate the language classes considered in this work relative to each other and to prior art, making the precise scope of the contribution more apparent.\n\n2. The analysis is confined to encoder-only Transformers. While this is a valid methodological choice, the paper would have broader impact if it discussed the implications of these findings or extended them to autoregressive models, which are prevalent in modern applications.\n\n3. Theorem 1.1 establishes the expressiveness of Transformers for semialgebraic counting properties. However, this claim would be much stronger with a corresponding analysis of the required model size (e.g., depth, width, or number of heads) as a function of the complexity of the counting problem. For instance, do the required Transformers scale polynomially or exponentially with the degree of the polynomial inequalities?\n\n4. The empirical validation of this paper is limited to the single language class $L_k$. The paper's value could be enhanced by either broadening the experimental scope to other complex formal languages or by discussing the potential implications of these counting properties for more conventional NLP tasks, even at a high level.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Zayq0bDB8c", "reviewer": "Reviewer_Fyg9", "summary": "This work analyzes the ability of Transformer based models to performing higher order forms of counting (e.g. counting if the product of three variables is larger than some threshold). The authors analyze the counting abilities of Transformers under various assumptions about the self-attention layer and analyze how the counting abilities of models with different self-attention assumptions relate to one another in terms of expressivity.\n\nThe main theoretical result of the paper shows that softmax attention transformers can express any counting property which can be expressed as a boolean combination of multivariate polynomial inequalities. For AHAT, the authors provide an exact characterization showing that the set of counting languages accepted by AHAT is equivalent to the set of semi-algebraic languages.\n\nThe authors complement this with empirical results showing that models can easily learn to perform classification on the set of languages of the form $|w|_b \\leq |w|_a^k$ for k from 1 to 5.\n\nI think the claims made by the paper are very interesting and meaningfully advance the field of Transformer expressivity. Most of my feedback is minor details which I think could help improve the exposition of the theoretical results However, I quite like this paper and thus have given it an 8.", "questions": "**General Questions**\n\n- Do we know if, in terms of counting, there are languages in SMAT but **not** in SemiAlg?\n- Could the authors give somewhere a more formal/rigorous definition of the sets AHAT, AHAT[U] and SMAT in the context of semi-algebraic language recognition? No formal definition of these sets are given, but many of the main results hinge on inclusions between these and SemiAlg.\n- Could you give a more precise theorem statement for Thm 1.1? Which class of Transformers are concerned by this?\n- You do not use multi-head attention in your definition of the Transformer. Is there a reason for this?\n- I would like for asymptotics (in terms of number of layers/width/number of heads) to be clearly stated either in or around the definition of the theorems. Currently, the only place where number of layers is referred to is in the paragraph discussing the reduction to two layers argument. I found this to be late in the text to introduce these.\n\n**Minor Comments/Clarification Questions**\n\n- For the proof of Prop 3.1\"(each consisting of one uniform layer and several ReLU layers)\" How many RELU layers? At least state big O.\n- The argument for PARITY in the appendix should be introduced in a proof environment with an associated Proposition/Lemma/Theorem.\n- What is $d$ line~ 633?\n- What are PI and RE languages ~line 382?\n- The titles for the columns/lines in Figure 1 could have clearer names.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The main claims are interesting and novel. Showing that softmax attention transformers can recognize semi-algebraic counting languages and giving characterization of the subclass meaningfully advances our theoretical understanding of Transformer counting power\n- Paper is well written. Motivation of the theoretical problem considered is given. In the sections exposing the framework and the theoretical results, examples are given which is nice. \n- At a high level, the theoretical approach taken is clean and convincing. The authors also show an interesting inexpressibility result for PARITY as well as undecidability/universality Theorems (1.3 and 1.4). The argument for two layer networks is also appealing.", "weaknesses": "* The main weakness of the paper for me is the exposition. I feel many things could be made clearer or more rigorous in the proofs/in the formalization of the problem. There are many occurrences of variables which are  referred to in text or in equations without properly being defined. I think this hinders the readability of the paper.\n* I also think the experiments are quite limited. It would be interested to see evaluation on languages that are not of the form of $L_k$.  I also wish the authors would have tested on languages with different vocabulary sizes to see how this affects performance. However, the theoretical contribution is, in my opinion, strong enough that this is not a major shortcoming to the paper's contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)