Language Models Need Inductive Biases to Count Inductively
Authors: Yingshan Chang
Yonatan Bisk
Venue: ICLR 2025 Poster (2025)
Keywords: Language Model Architecture
Inductive bias
Expressivity
Counting
Inductive Generalization
Primary area: foundation or frontier models, including LLMs

Abstract: Counting constitutes a core skill underlying a wide range of tasks, such as formal language recognition, multi-hop reasoning and simulating algorithms. Generaliz- ing counting inductively is central to task success on out-of-distribution (OOD) instances where testing inputs are longer than those seen in training. While there is a large body of literature reporting poor length generalization in language models, few papers have tried to distill the “reasoning” failure to the simplest case of count- ing failure. We aim to provide a broader picture on whether various language model architectures can a) learn to count, and b) generalize counting inductively. This work provides extensive empirical results on architectures ranging from RNNs, Transformers, State-Space Models and RWKV. We present carefully-designed task formats, auxiliary tasks and positional embeddings to avoid limitations in general- ization with OOD-position and OOD-vocabulary. We find that while traditional RNNs trivially achieve inductive counting, Transformers have to rely on positional embeddings (PEs) to count OOD. Further analyses on interpreting the learned solution reveal that different PEs encode different inductive biases that facilitate counting in different task formats. As counting is the basis for many arguments concerning the expressivity of Transformers, our finding calls for the community to reexamine the application scope of primitive functions defined in formal charac- terizations. Finally, modern RNNs also largely underperform traditional RNNs in generalizing counting inductively, hinting at the tradeoff modern RNNs struggle to balance between parallelized training and maintaining their recurrent nature.

Published as a conference paper at ICLR 2025
LANGUAGE MODELS NEED INDUCTIVE BIASES TO COUNT INDUCTIVELY
Yingshan Chang & Yonatan Bisk Camegii Mellon University (yi Jyingshac, ybisk (oisk) @cs. cmu. edu
ABSTRACT
Counting constitutes a core skill underlying a wide range of tasks, such as formal language recognition, multi-hop reasoning and simulating algorithms. Generaliz- ing counting inductively is central to task success on out-of- of-distribution (OOD) instances where testing inputs are longer than those seen training. While there is large body of literature reporting poor length generalization in language models, few papers have tried to distill the "reasoning" failure to the simplest case of count- ing failure. We aim to provide a broader picture whether various language model architectures can a) learn to count, and b) generalize counting inductively. This work provides extensive empirical results architectures ranging from RNNss Transformers, Srate-Space Models and RWKV. We present formats, auxiliary tasks and positional embeddings avoid limitations in general- ization with OOD-position and OOD-vocabulary. We find that while traditional RNNs trivially achieve inductive counting, Transformers have rely on positional embeddings (PEs) to count OOD. Further analyses on interpreting the learned solution reveal that different PEs encode different inductive biases that facilitate counting in different task formats. As counting is the basis for many arguments concerning the expressivity of Transformers, our finding calls for the community to reexamine the application scope of primitive functions defined in formal charac- terizations. Finally, modern RNNs also largely underperform traditional RNNs generalizing counting inductively, hinting at the tradeoff modern RNNs struggle balance between parallelized training and maintaining their recurrent nature.
task
INTRODUCTION
"Difficulty in generalizing to longer instances" is recurring theme in the discussion of Transformer limitations, regardless of the task domain (Dziri et al. 2023 Saparov et al. 2023 Zhang et al. 2023 Del' etang et al. 2022 Liu et al.) 2022 BBattaaishra et al. 2020). We find that, although the notion of length may vary across domains (e.g. sequence length, recursion depth, counter states for DSAs, stack sizes for PDAs), counting is always involved as a required component to successfully handle the task. In fact, counting might be leveraged by Transformers the need to implement recurrence. For example, [iu et al. (2022) indicates that Transformers may rely on internal representations of counts to model counter languages,
often than necessary it circumvents
remedy for its lack of recurrent mechanism, but failing immediately on instances with OOD counts. Further, Zhang et al. (2023) indicates that for recursive problem-solving, specialized attention heads count the recursion depth, dependent on which depth-specific solutions are learned. Therefore, counting is crucial for Transformers to perform variety of tasks, from formal language recognition to algorithmic reasoning. And generalizing to OOD counts is crucial for handling longer instances. However, it remains unclear whether Transformers can learn to count inductively.
On the other hand, RASP (Weiss et al. 2021). programming language designed to mimic Trans- former computations, treats counting as primitive function based on which more complex algorithms are built (e.g. sorting, reverse, Dyck). We question the generality of counting as primitive building block for Transformer computation. This paper conveys an important message that counting does not come effortlessly embeddings, input formats, and the amount of training have to be satisfied order for a Transformer to learn counting in-domain. Moreover, Transformers do not learn count inductively, e.g. when
might expect for primitive function. Nontrivial requirements positional

---

Published as a conference paper at ICLR 2025
the model knows increment (50) =51, it still cannot output the length of 51-symbol sequence as 51 if it has only been trained on up to 50-length sequences. Notably, in this work we do direct comparison with both modern and classical recurrent architectures to begin elucidating the source of this modern limitation, not shared by previous approaches.
We conduct extensive experiments training Transformers count inductively. We carefully design the input-output formats, auxiliary tasks and positional embeddings to overcome the OOD-position and OOD-vocabulary issues. However, we find negative evidence. Shallow IL 2L Transformers struggle to generalize inductively. Successful generalization is observed with 4L Transformers, but requiring different positional embeddings for different forms of counting. Expanding our comparison to recurrent architectures, we find that RNN and LSTM succeed at everything we have asked, whereas newer RNN architectures (e-g. State-Space Models and RWKV) have degraded performance. Our work opens up attractive challenges for augmenting Transformers with counter-equivalent mechanism, as well as hybridizing Transformer and RNN without breaking their inherent strengths.
2 BACKGROUND
The inductive counting principle: If a word in an ordered number word list refers to sets with cardinality n, then the next word refers sets with cardinality n. + 1 (Rips et al. 2006 Piantadosi et al. 2012).
2.1 DEFINITION OF COUNTING
We define counting the ability to map number word to the cardinality of set containing corresponding number of items. The crucial inductive step requires that, having learned the mapping of the first words to the first n cardinality values, one has infer that adding one more item results in cardinality value corresponding to the (n + 1)th word in the number word list. This definition of counting is extensively studied branch of cognitive science concerning how children learn to count (Davidson et al. 2012. Rousselle & Vossius 202T Sarnecka & Carey 2008 Spaepen et al.
2018). The cognitive science research informs that children learn count from to 5 independently in early ages, then drastically generalize to the entire natural number system by inductively inferring how the number words in one's native language map to cardinality values (Wynn) 1992 Margolis & &Luurence 2008). Further, the structure of the language (e.g. avoiding special cases change of bases) correspond to learning to count earlier in childhood (Rousselle & Vossius 2021).
Note how counting differs from knowing the ordered list of number words: word list constitutes an important prerequisite of counting, but establishing the mapping of numbers from the language context to the cardinal context is the core problem of interest. Also note that the complexity of number words may vary across languages. This would only affect the difficulty of learning the number word list, without changing the requirements for establishing the mapping and performing induction. Thus, the counting task studied in this paper is language-indeependen, and use arabic numerals, without loss of generality, for notational consistency. To avoid confusion between number words and cardinality values, in our writings we use arabic numerals with single quotation denote numbers in the language context (e.g. '3'), and use arabic numerals with vertical bars (e.g. 131) to denote numbers in the cardinal context. Numbers in the language context are treated in the same way as input/output tokens language model, whereas numbers in the cardinal context may only appear as internal states and its exact form may vary across individuals.
reciting the number
2.2 THE TRANSFORMER ARCHITECTURE
A Transformer takes a discrete sequence as input and outputs a discrete sequence. The input and output sequences share a vocabulary Σ. The embedding and unembedding layers project a one-hot vector with dim |Σز to the Transformer's 's hidden dim and back to [Σ|.
Between the embedding and unembedding layers are L layers of interleaved self-attention and MLP blocks, with LayerNorm and residual connections inserted at appropriate locations. For an intuitive understanding, self-attention layers communicate information across tokens, while MLP layers allow each token to update information across the feature dimension (i.e. hidden_ding _dmmm individually.
Code and data are released htttasssddtttt/////ss http::///ttaap/gghhss..////////a
1.M
2

---

Published as a conference paper at ICLR 2025
Importantly, parameters shared across tokens, and all input tokens perform the same operation in parallel rather than sequentially. Equation [
mathematically defines the self-attention function.
LttnQQ,,V)) Ei= f On
(I)
Ei eat k:
Since all input tokens perform the same operation in parallel, the Transformer does not intrinsically distinguish tokens based on positions. Thus, positional information is needed to break this symmetry.
Sinusoidal Positional Embedding (SinePE)) Vaswani et al. 2017) SinePE computes positional
embeddings based on sine waves, which is added to token embeddings at the input layer.
Absolute Positional Embedding (APE) et al., 2019) APE assigns learnable vectors to position ids I,.... P. which is added to token embeddings at the input layer.
Rotary Positional Embedding (RoPE) (Su et al. 2021) RoPE multiplies query and key vectors by an unlearnable rotation matrix, such that the relative rotation angle between two positions captures relative position. It requires a maximum sequence length to be predetermined.
Scaler Positional Embedding (SPE){Ya Yao et al. 2021 SPE sides aside one dimension from the Transformer's hidden_din _dmm and inserts positional information through a scaler value. Proposed by Yao 2 who found SPE's advantage over APE in modeling Dyck languages with bounded depth. al.
No Positional Embedding (NoPE) NoPE denotes the vanilla Transformer without positions. Haviv al. (2022) suggests that the causal mask could leak positional information, by potentially allowing each token to count the number of predecessors. However, this raises the same question of whether Transformers can count. Thus, experiments with NoPE will also inform how reliable Transformers figure out absolute positions solely from causal masks.
A model easily falls apart if it has never seen the embedding for position beyond the training length. To tackle the OOD-position issue Kiyono et al. (2021) proposes to augment the input position_ __dds (PIDs) with random shift (shifted PEs) so that you start numbering positions from random integer between and P. instead of always starting from 1. This ensures that all position embeddings will be trained. Ruoss al. (2023) proposes a more general augmentation (randomized PEs), where the PIDs for length=k sequence is the sorted list of k integers randomly drawn from [1, PJ. We empirically find that randomized PEs perform much worse than shifted PEs. Thus we adopt shifted PEs.
2.3 AXES OF SEQUENTIAL COMPUTATION IN DIFFERENT ARCHITECTURES
The induction step of counting can be trivially afforded by sequential modeling, where "adding one more item to the set" is operationalized the model consuming more input, and the increment on cardinality is operationalized as unrolling one more step along the sequential axis. Table [ summarizes the axes for sequential computation in Transformers well in five representative is important to highlight the contrast between architectures dominated
recurrent architectures. by parallel computation and architectures dominated by sequential computation. Our work reveals the implication of these differences on counting. In Transformers, due to the parallel processing of attention, in order for a token build on the computation results of its predecessors, has to proceed to the next layer. Thus, sequential computation occurs along the axis of Transformer layers. In RNNs, sequential computation realized through state transitions. SSMs share the concept of state transition with RNNs, but have varied implementations specific to individual models. For further information, Appendix A. reviews the design of recurrent architectures and Appendix discusses the trade-off between recurrence and parallelization.
Architectures
Repetitive components that realize sequential computation
Transformer RNN
Attention + MLP Blocks
Matrix Multiplication ʃ
LSTM
Matrix multiplication S Multiplicative gating
$4, Mamba
Matrix multiplication
Linear Attention (e.g. RWKV)
Moving avg. history with discounted weights
Table 1: Sequential computation enjoys the reuse of computation performed in previous steps and is realized along different axes in different architectures.
3

---

Published as a conference paper at ICLR 2025
Design
Examples
Training/IND Testing
OOD Testing
Inpus Ourput
Vanilla
Counta)) e
Counta) (ist, 100)
58
Vanilla
Input
Countra) [4,
Count'a) 103)
Succession
Output
96
Input
CountTa)
151, 103)
Helpar token
Ourput
48.40
Counthh) (1,
Imput
Countral c [I,
Countra) c 151, 100]
Output
Count e 100)
Helper token
Shifted
Input
Coffeelstart-Commmaaa (1.100]
shrftedstart Countcal 151,000]
shihodbaatt (b)
Output
20 22
66
Input
Output
12
Counti e 50g
Countaa (51. 1031
Shifted start
shifeedstant Council
shiftedstart CountCa) [5L,00
Input
45
66
Output
45 66
71
06 07
2001
Input Ourput
Modular (mod 10)
Coun 90g
Crumbol
Imput Output
Countia/) 10,
Countlay) c (00
Selective
CountSy e 10]
Countla,y) 10,
Countia,3 i... Countia,
Count(a,)+ +... Count
t: [51, 1009
Count C4,3
Countra,)
Selective
Input
Modular (mod 4)
Ourput
Count 89,
CountTa,)
Countraj Countia,)
Countaa)) Countta.)
Figure 1: Illustration of input-output formats. Every integer, as well as a, b, a1.... 410 are individual tokens. Row 1: Vanilla counting, where each token outputs the count of a's seen from the beginning of the sequence up to itself. Row 2: Vanilla counting augmented with input-output pairs that inform the order of number tokens. Row 3-4: b is the helper token, be with larger counts. the main token of interest, to bes seen with restricted counts during training and tested with OOD counts. Row 7-8: a1, 010 are distinct tokens, Each of them should maintain own counter.
3 GENERAL EXPERIMENTAL SETUP
3.1 DATA CREATION
When generating the data, there are two important hyperparameters at play: MAX_TRAII TEAIT_RRQLLLLE and MAX OOD_ SEDD_SEEEE. Note, MAX IND IND_INND_OOOOS DED_SEELENN MAX TRAIN SEQLEN. Please refer to the rightmost two columns of Figure [ for their exact values. Since loss is computed at every token, rather than only the last token, there is need to include shorter training sequences. In fact, all training sequences have identical lengths equal to MAX TRAIN SEQLEN, in order max out supervision on larger counts. Similarly, every testing sequence has length equals to MAX_ AND/OOD_SEQUL
Data creation for selective counting requires additional effort to balance the distribution. Figure T shows, each input sequence in selective counting can consist up to 10 unique tokens, 01...a10- If we sample aj..aa 10 at random, their counts, Count('a "), ... Count( (ount("ajn")) )) will heavily bias towards small values. It is desirable to balance the distribution so that each of Count( (aaj ...... Count( 'ajo") uniformly distirbuted over [0. 10] in training. Thus, during training data generation, we upweigh sequences where some tokens have larger counts, resulting in the distribution shown in Figure A7 The distribution of Count(' a, )) ..., Count( a ") in the OOD test set is skewed towards larger values because they longer while restrict each unique token to appear less than times.
4

---

Published as a conference paper at ICLR 2025
3.2 IMPLEMENTATION
We follow the standard GPT-2 implementation and train 1,2, 4-layer Transformers to count. Our models are restricted to be shallow because counting should not take much computation if truly serves as the primitive building block for other complex functions. Weiss et al. (202T) suggested that computing the length of sequence can be done within one layer. We generously increase the budget to four layers. The input-output formats are summarized in Figure and detailed in Section 4 Each number word is tokenized into an individual token, corresponding to whole-number tokenization in the LLM literature. We note alternative where numbers tokenized into digits. We opt not to use single-digit tokenization because previous studies show that when numbers are represented by multiple tokens, early Transformer layers serve to "detokenize" while late Transformer layers take the additional reponsibility to "re-tokenize" (Elhage et al. (022). This suggests that whole-numbers are the preferable processing units in Transformers, while single-digit tokenization adds extra complexity of mapping token spans and numbers back and forth. This work adopts whole-number tokenization to avoid conflating the complexity of counting with that introduced by tokenization.
3.3 CHECKPOINTING AND EVALUATION
We checkpoint and perform IND/OOD testing every 30K steps. The evaluation is accuracy averaged across the sequence dimension. The total length of training typically 312.5K or 625K steps. These stopping times are empirically chosen, by which the model has either experienced a long overfitting period with plateaued testing accuracy, or already saturated to perfect. For each model, we report performance on the best checkpoint over the entire course of training. We find different patterns in the training and testing curves across task variants and types of positional embeddings. While IND) testing scores usually increase monotonically, OOD testing scores may bump and drop if the model overfits. Due to the space limit, we only report the maximum performance along the curves as we believe the performance upperbound is of more interest in this study, and leave the examination of learning dynamics to future work. There is a possible connection between the bumps observed in some of counting tasks to the grokking (Nanda al.. rule out late grokking that would have happen after we stopped our training jobs, we already allow a long patience window within the training duration of 3 312.5K or 625K steps. Usually, no improvement was observed in the latter half of training. Moreover, every experiment has been repeated with five seeds, which further enlarges the search range for grokking it could ever happen. Unless otherwise noted, we report the best performance out of five seeds. Appendix [ reports the median performance out of five seeds which complement the main Transformer and RNN results in Table 2 and Table AT
2023) phenomena. While it is impossible to
4 COUNTING
Training model to count inductively requires us provide 1) An ordered number word list covering the full set of cardinality values, 2) Examples of mapping between number words and sets of objects for small cardinalities. Crucially, the full list of ordered number words should be taught without exposing the model to any set of objects with an out-of-distributin cardinality. Considering this, a vanilla approach would be to add the succession sequence, i.c. '1', '2', to the training data. However, this is largely ineffective, as shown in Table Top. This is because the model would easily master the succession sequence by modeling the bi-gram statistics, which brings no help to counting.
Top.
A more helpful approach is to teach counting with a helper token, which is seen up to the cardinality of M. The cardinality of the main object remains to be bounded by N in training. In fact, the helper token trivializes generalization. Intuitively, this task asks: "If you have learned to count bananas up to 100, but you have never seen as many as 100 apples, can you count apples up to 100?" (Figure [] rowl). Though generalization under this setting does not require induction, we view this task as useful sanity-check because it is undesirable to establish the counting ability tied to specific objects.
Next, we propose "shiftedstart". modification to the input-output format, to simultaneously achieve 1) full exposure of the vocabulary (as well as its ordering) and 2) bounded exposure of cardinalities. Given that, we can test generalization with the OOD cardinalities. Concretely, we insert a number word (k) at the initial position to shift the beginning of the output counting sequence from I to k+1, We illustrate this in Figure I row 3. Compared to the helper token setting, the shiftedstart setting
28 heads, 1,024 dim and 4,096 MI.P-dim. IRR=le4 with 3k steps of linear warmup. Batch size is 32.
5

---

Published as a conference paper at ICLR 2025
NoPE
Sine
APE
RoPE
SPE
Task
IND
OOD
IND
OOD
IND
OOD
IND
00D
IND
OOD
Vanilla
2.0
0.0
100
0.0
100
0.0
2.0
100
+ Succession
2.0
0.0
100
0.0
100
0.0
2.0
0.0
100
0.0
100
100
100
76.4
100
80.6
100
100
92.9
Helper Token
100
100
100
71.7
100
69.3
100
100
100
99.8
100
4.1
99.7
0.0
100
13.6
100
7.4
100
4.1
Helper Token
100
100
100
100
100
81.34
100
78.7
100
18.3
+ Shifted Start
4
100
100
100
95.6
100
100
100
100
100
99.8
100
16.7
100
4.3
100
50.5
100
37.7
100
9.0
Shifted Start
100
25.0
100
78.7
100
27.8
100
92.5
100
57.8
100
46.1
100
48.6
100
51.9
100
98.86
100
83.8
11.8
11.8
100
100
100
71.2
11.8
11.8
100
8.2
Modular (mod10)
12.0
11.8
100
100
100
100
11.8
11.8
100
8.2
11.8
11.8
100
100
100
100
11.8
11.8
100
96.0
9.3
99.5
68.8
100
10.6
99.7
29.9
99.8
61.3
Selective
99.7
94.1
99.8
32.6
100
13.9
99.7
49.1
99.7
86.9
99.7
100
100
100
100
100
99.7
52.5
99.4
98.2
Selective
92.3
56.4
96.5
47.4
99.8
27.2
98.1 1
32.3
99.7
46.8
+ Modular (mod4)
4
97.4
91.8
100
98.2
99.9
97.3
98.5
39.8
98.2
54.6
Table 2: Top:
When the vocabulary corresponding OOD-cardinality is exposed via the succession sequence, models achieve perfect accuracy on reciting the Succession sequence, yet perform pooly on counting. This clearly show that augmenting training data with the ordered number word list offers no assistance to counting. Middle: We teach the model number words covering both IND and OOD counts, without exposing the model to OOD cardinalities. This is ensured via either an auxiliary task involving a Helper Token, or modifying the input-output format with Shifted Start. Bottom: Transformer counting for the Modular or Selective variants (or both). Positional embeddings augmented with random shift by default. We denote Layers, L, and In/Out-of distribution as IND/OOD. OOD accuracies are only calculated at extrapolation positions.
imposes a greater challenge since a cardinality above strictly absent from training data. Moreover, shifted starts discourages a model to exploit rigid mapping from input positions to outputs an undesirable solution that may inflate performance. Finally, we also experiment with a "Helper Token + Shifted Start" to enrich the evidence that our task design does not permit easily- hackale solutions.
Table Middle shows the counting performance of Transformers, with the training data augmented with helper token, shifted starts, both. A helper token indeed makes the task casier, evidenced by near-perfect OOD accuracy of all five positional embeddings. When the order of number words is only exposed by virtue of the shifted starts, only 4L RoPE Transformer is able to generalize. The poor results for 1L and 2L models suggest that counting in Transformers may require a non-trivial computation budget. This initial result already calls into question the validity of treating counting as a primitive operation in existing papers. Further, reasoning problems that treat counting as primitive operation would impose larger demands in order for inductive generalizations. Otherwise, instances with larger counter states should be explicitly demonstrated during training. Extrapolation to larger counter states do not trivially emerge as a result of mastering in-domain data. A more generous read is that current results relying on counting should only be interpreted as valid for in-domain settings not as general computational engines as papers often characterize them.
Modular Counting In the previous section, we found that Transformers largely failed to generalize inductively except for those equipped with RoPE. This calls for the next question: If it is too hard for Transformers to simulate "unbounded counters", can they simulate modular counters - only requiring finite counter states? Modular counting will not run into the OOD-vocabulary issue, so remedies we apply in the last section, including the helper token or shifted starts are no longer necessary. However, modular counting introduces additional complexity for modelling periodicity. We believe modular counting should be as powerful as "unbounded counting" because, for example, a stack of mod10 counters, coordinating appropriately, would give the entire natural number system.

---

Published as a conference paper at ICLR 2025
Table 2 row 5 shows that only APE and SinePE generalize well on modular counting. NoPE and RoPE failed catastrophically, not even fitting the training data. The failure of RoPE is particularly interesting because one would expect its formulation to inherently inform periodicity. Section [ provides explanation. Briefly, RoPE only modifies queries and keys, which does not help with symmetry breaking of a homogeneous input where all value vectors are identical in the first place. In this sense, RoPE behaves similarly to NoPE. Appendix proovides results showing that NoPE and RoPE must rely on an explicit beginoing-of-sequence token to achieve modular counting in-domain. SPE achieves perfect in-aoniin accuracy but breaks immediately once extrapolation is required.
Selective Counting We examine whether Transformers can selectively count predecessors satis- fying a condition. In the counting context, selective counting worth exploring because when an unbounded counter is approximated via modular counter stack, counters above the first level will have to perform selcctive-modular counting. More broadly, selectivity is important because obser- vations that carry useful information are sparse the same consideration that motivates Mamba's proposal of selective-scan (Gu & Dao 2023). In the general form of selective-counting, a predicate function pred can be learned such that each token outputs the number of predecessors 2; where pred(r, _3)) = True. This corresponds to the "selector_ __itth" primitive in RASP. Our experiments simply regard the identity indicator function as the selection condition. Learning predicate functions adds complexity along an axis orthogonal to inductive counting, which we leave for future research.
Note, we remove the requirement for generalizing OOD counts via induction on the mapping between vocabulary and cardinality, because this is the primary subject of discussion in Section | In this section, we focus on the additional challenge related selectivity. We generate the training data containing ten unique tokens such that the count of each unique token ranges from zero to ten. In the testing data, we also ensure that the counts do not exceed ten. However, our testing sequences are longer than the maximum training length. Thus, the summation of counts for all tokens, as well as the range of dependency in order to perform selection, are OOD.
Table 2 row 6 shows the results for selective counting. All PEs except for RoPE succeed given 4 layers. The observation that NoPE outperforms other PEs on selective counting is interesting. suggests that causal masking may indeed aid in symmetry breaking. And, in fact, our results indicate that PEs might unintentionally introduce exploitable shortcuts or inductive biases unfavorable to generalization. Finally, we perform experiments base (4 instead of 10), in order to prevent a substantial growth of sequence length, since a selective counting sequence contains 10 unique tokens interleaved together, unlike homogeneous sequence in previous counting tasks. Results are shown in Table row 6, which demonstrate clear message: only PEs SinePE and APE which generalizes on both modular counting and selective counting performs well on elletive-moduule selective-module modular counting. in contrast to its poor performance on modular counting. To explain this observation. NoPE's s limitation on modular counting stems from its inability to break the symmetry of homogeneous sequence. Such limitation no longer applies to coluulive-modular counting as the input becomes heterogeneous. Section 5 and Appendix D provide further evidence.
modular counting. We adopt smaller
counting. NoPE also achieves fairly good performance on
There are two major takeaways from our Transformer counting experiments: 1)
When counting is treated primitive towards more complicated reasoning, it is better to cover all possible counter states in-domain, as Transformers struggle to count inductively and rely on supervised encounter with each cardinality value. 2) Different PE schemas exhibit strength in different forms of counting. Put concisely, RoPE succeeds at unbounded counting with shifted starts; SinePE and APE generalize at both modular and selective counting; NoPE and SPE are only competitive selective counting. Our results motivate the integration of multiple PE schemas to take advantage of orthongonal strengths.
WHY DO EACH OF THE PE STRATEGIES BEHAVE DIFFERENTLY?
We proceed to find hidden factors that account for the observed performance differences among PE schemas. We proposes two generalizable mechanisms, for modular and selective counting, respectively. Each mechanism demands particular inductive biases. Each PE schema either supports or goes against certain inductive biases. The strengths and shortcomings of each PE schema revealed in our analysis consolidate our core argument that language models need inductive biases to count inductively. Our contributions are novel in two regards: 1) recognizing unique sets of inductive biases for modular and selective counting that are plausible for a Transformer to implement where parallel computation dominates, and 2) studying how these inductive biases are realized by PEs. We
7

---

Published as a conference paper at ICLR 2025
believe our findings will both inspire theoretical studies to quantify how much expressivity is added to Transformers by separate PE schemas, and advise downstream applications on the choice of PE based on the demand for inductive biases.
Modular Counting The mechanism that allows for perfect generalization to the OOD test set consists of two steps: First Token Recognition and Position-based Modular Subtraction. The first step, First Token Recognition, is necessary to address the additional complexity introduced by the position-shiff shifft technique (Section 2.2 The model must locate the first token in each input sequence in order to figure out the position-shift value. In the second step (Equation 2), each token attends to the first token and compute the difference in their PIDs modulo 10, which gives the desired output.
output = ((PIDrrst tok %10) - (PID carrruurtttttoo tole (10) %10
First Token Recognition demands the inductive bias for breaking symmetry. Since the input sequences in our modular counting task are homogeneous, the model must leverage PEs to distinguish among identical tokens. To test for how well each PE schema supports this inductive bias, we design a first token recognition task (dubbed first_ cos__tokhhule mokkhomogeneous) whose details are described in Appendix D We train 1L Transformers with five PE schemas and find that only APE, SinePE and SPE are able to fit the training data and generalize to unseen sequence lengths. NoPE and RoPE's inability to recognize the first token explains their failure in modular counting, as the position-shie -hiff technique renders any rigid mapping from PID the output useless.
Position-based Modular Subtraction requires the capability to cluster token representations based on their PID modulo 10. Both APE and SinePE support such constructions, as evidenced by the PCA plots of hidden states. Figure plots the first two principal components of intermediate states, color coded by PID modulo 10. Tight clusters indicate that the model produce close representations for tokens whose PIDs modulo 10 have the same value. Such clustering pattern is only observed for APE and SinePE, but not for SPE models. We believe that injecting positional information only through a single dimension limits an SPE Transformer's i ability to build richer features based on positions, which probably explains why SPE succeeds at first token recognition but fails at modular counting.
Selective Counting The generalizable mechanism suitable for the Transformer architecture again consists of two critical steps: First Token Recognition and Token-based Attention. This mechanism closely resembles the construction in Chiang & Cholak (2022) for recognizing PARITY, which crucially depends on 1) a beginning-of-sequueee that are either the BOS or identical to self. Though our task format does not include BOS, we argue that causal masking is sufficient for first token recognition, as long as the input sequence is largely heterogeneous. This verified through a variant of the first token recognition task (dubbed first_tok, heterogeneous), in which the input is shuffled sequence containing 10 unique tokens, each occurring a random number of times. We find that NoPE 1L causal Transformer able to generalize well on first_lok joookhheeroogeeosss Appendix D provides details about wtw.ooooeeerrrgeeooss and mechanistically describes how causal masking helps to accomplish it.
(BOS) symbol and 2) uniform attention over tokens
The first token, once recognized, can serve the role of BOS for subsequent layers. Following Chiang & Cholak (2022), subsequent layers should construct features that represent two quantities for cach token: I/n and k/n, where k is the desired output (i.c. the count of identity tokens or before the current token) and n is the total count of tokens up to the current token. Next, LayerNorm and MLP will learn the map (1/n, k/n)= - k. The key to construct representations for k/n is computing attention weights purely based on token identity, regardless of PIDs. Indeed, given the task format, positional information not needed solve selective counting. Therefore, one of the critical factors accounting for the different performance between PE schemas is whether the model can ignore PEs. NoPE Transformer effortlessly achieves this, thereby already generalizing well with 2L. SPE only minimally injects positional information through a single dimension, thus not imposing much difficulty when the PEs are supposed to be ignored. In that sense, SPE performs closer to NoPE, in accordance with our results in Table row 6. APE and SinePE only generalize well with 4L, due to two possible reasons: 1) It requires non-trivial effort for APE/SinePE Transformers to ignore PEs. 2) PEs are actually helpful for first token recognition, prerequisite subtask, thus complicating the picture. We additionally experiment with Selective Counting + BOS and the results corroborate our hypothesis. Explicitly feeding BOS lowers the complexity and removes the supervision signals which might be at odds with the need for disregarding PEs. Table shows that both APE and SinePE are able to emulate NoPE with II when BOS is included.
8

---

Published as a conference paper at ICLR 2025
Nevertheless, RoPE does not benefit from BOS, indicating that its struggle may majorly come from the second subtask, Token-based Attention. Unlike APE, SinePE and SPE, where positions affect the input representations, RoPE directly use positions modify queries and keys. Such modifications encode a recency bias (Su et al., (021) - an unfavorable inductive bias in this case - which we believe is hard to be escaped by the rest of the network through learning. We hypothesize that the enforcement of recency bias leads to the difficulty of implementing pure token-based attention. One indicative piece of evidence is the variation of attention scores as the input PIDs varies, keeping the same input token ids (TIDs). Figure A6 visualizes the standard error of attention score (i.e. entries of QK") between each pair of TIDs, across all PID pairs they can take. For models trained on selective counting, attention scores in RoPE subject to the largest amount of variation influenced by PIDs, while attention scores in APE are the least sensitive to PIDs. There may be other explanations for why RoPE struggles more than other PE schemas at selective counting, which is left for future work. We hope the counting tasks proposed in this work provide a lens through which inductive biases enabled by PEs that are not otherwise encoded in self-attention can be studied in isolation. Future work may extend this work by exploring how those inductive biases carry over to broader arithmetic domains.
Shifted Start Counting For shifted start counting, we are unaware of generalizable solu- tion, which calls into question the seemingly successful generalization of RoPE 4L in Table 2 row 4. However, the ability for RoPE to generalize is fragile. Successful generalization when MAX_ TRAIN
= 100 does not imply success when the ratio between them is arbitrarily extreme. In fact, have easily challenged RoPE 4L failure by making MAX MAX_OOD_ WEDD_EEELENN four times larger than MAX_TRA SEELEEN,EEEN Table A8 sum- marizes the performance of RoPE 4L with different combinations of MAX_ TRAIITRRIIILLLLLIIIILAATIIIIITTS SEQLEN, MAX MAX_OOD SEQLEN, clearly demonstrating worsening trend as the ratio makes generalization harder. The fragility of RoPE, as well as the failure of other PE schemas indicate that the OOD- cardinality issue remains unsolved, which is the core obstacle to inductive counting in Transformers. Our work raises the importance of OOD-cardinality as harder barrier hindering generalization on in- ductive counting. OOD cord-candiny poses separate difficulty from OOD--position, OOD-vocabulary, or DOD-range-of-deeendee
TRAIN_SEQLER SEQLEN = 50, MAX_ LOLOOOODEURR
problems, and shall not be confused with these problems that the liter- ature on length generalization (Press et al. 2021 Kiyono et al. 2021 Ruoss et al. 2023 Kazemnejad
et al. 2024 Amil et al. 2022. Zhou et al.
2024 has been targeting at.
COUNTING IN OTHER LM ARCHITECTURES
As counting is a fundamentally recurrent task. it is natural to validate our conditions on recurrent architectures. Both the explicit modeling of hidden state transitions, and the sequential unrolling of computation along the input sequence dimension, naturally facilitate inductive counting. Note, there exists prior work hinting at counting in such architectures (Shi et al., [ [Suzgun et al.] 2201)). but not directly evaluated in a systematic comparison. We find that traditional recurrent architectures, RNN (Elman) 1990) and LSTM (Hochreiter & Schmidhuber, 1997), achieve perfect generalization with a single layer, except that RNN slightly falls short on selective counting (Table [AT). This highlights that recurrent bias is likely key for inductive counting, which is precisely what the Transformer lacks and must therefore rely on PEs as substitute.
The recent literature has seen a resurgence of modern RNN architectures (Gu & Dao 2023 Gu et al. 2021a Peng et al. 2023| 2024) claiming to enjoy the best of both worlds: parallelizable training, like Transtormers, and recurrent inference, like RNNs. It is important to investigate whether the recurrent formulation of these architectures affords inductive counting in the same way as traditional RNNs. To this end, we experiment with three modern RNNs S4 (Gu et al. 2021a), Mamba (aka S6) (Gu & Dao 2023) and RWKV-v6 (aka Finch)(Peng et al. 2024) that rival Transformers on large-scale LM benchmarks. The key observation is that modern RNNs generalize much worse than traditional RNNs on counting. We suspect the reason lies in less flexible state transitions, especially for Mamba and RWKV. The very design that enables parallel training through reformulating the model into the "convolutional mode" also limits the expressivity of state transitions. As illustrated in Table and Appendix | while traditional RNNs apply a nonlinearity to state transitions, modern RNNs only apply matrix multiplication or linear interpolation to history states, for the sake of easy contraction of multiple sequential updates into a single computation step. A potential limitation of this design is manifested through our counting tasks, opening up questions about what architectural elements imbue the necessary inductive biases for counting, and how these can be transferred to hy brid architectures. Appendix A provides implementation details and results for counting on other LM architectures.
9

---

Published as a conference paper at ICLR 2025
7 RELATED WORKS
Formal Theories on Transformer Expressivity Transformer expressivity can be formally analyzed
from the perspectives of functional libraries (Weiss et al., 2021:
Lindner et al. [2023] Zhou et al.
2023). boolean circuits (Cong et al., 1996 Yang & Chiang 2024,
Strobl et al. [024]] Merrill et al.
2022). or Automata Theory (Del etang et al. 2022) Yao al. 2021 Liu al. [022] Ebrahimi et al.
2020p. We expand the discussion on this large body of literature in Appendix [F] Formal studies have
established proofs for Transformers' inability to count in ungtt-gennralizzttoon regime (Hahn) 2020
Bhattamishra et al. (020) (usually in the context of modeling counter languages). However, the proofs involve assumptions such as 1) hard attention, i.c. hardmax instead of softmax, 2) infinite sequence length, 3) pure-atten attennttentoon architecture, i.c. without layernorm PEs, 4) infinite or log precision. It is unclear how certain assumptions in theoretical proof translate to real applications. Although we do not contribute new theoretical results, our work complements formal studies in important ways. First, we provide empirical evidence that echoes the theoretical proof', under a realistic setting. Second, theories on Transformer or self-attention seldomly treat different PEs separate cases. We argue that PEs in fact encode various inductive biases the worth detailed examination. Third, PE shift is another important realistic consideration which may affect expressivity but has been simplified away in theories. Overall, our work lays the ground where future theoretical discussions may branch out according to PE types, as well as inspiring practical design choices revolving around PEs.
Empirically assessing Transformer expressivity Abundant prior works have empirically studied the capacity of Transformer- based LMs. Categorizing by scale, these works include 1) testing Transformers with hand-constructed weights (Chiang & Cholak, 2022); 2) testing Transformers Ebrahimi et al.) [020)] /hhou et al.
trained from scratch (Del'etang et al. 2022 Abbe et
2023
McLeish et al.) 2024); and 3) testing pretrained LMs with finetuning (Anil et al. 2022) or
prompting (Zhou et al. (0022). Categorizing by task design, prior works usually adopt synthetic tasks
organized into hicrarchies, with notion of complexity informed by formal languages (Del Del'etangeeee et al.
2022 Zhou et al. 2023; Hao et al. 2022 Liu et al. 2022 Kazemnejad et al. 2024 Ebrahimi et al.
2020 Ruoss et al., (202) or boolean functions (Bhattamishra et al., 2022] Abbe et al., 2023). Our
work contributes to this body of empirical evidence. Our task design additionally draws inspiration from cognitive science (Rousselle & Vossius 2021; Sarnecka & Carey] 2008). Of particular note is that Zhou et al. (2023) also studied counting, which differs from ours by definition: the input includes a start and an end token, the output is an incremental expansion, e.g. 12 16 > 12 13 14 15 16. We believe that this can be handled by mastering the succession sequence plus a termination checking. Hence, their definition of counting involves neither numbers in the cardinality context nor induction.
We additionally review the literature on modern recurrent architectures in Appendix
H3
8 CONCLUSION
Building a growing body of work on formalizing the computation in Transformers, this work
investigates counting, which is believed to be primitive function enabling a Transformer to perform wide range of complex tasks, such as modeling counter languages (Bhattamishra et al., 2022
Hao et al. 2022; Ebrahimi et al. 2020), simulating algorithms (Anil et al. 2002 Zhong et al. 2024; Veličković et al. (022). and tracking the depth of reasoning chain (Saparov et al., [202)).
However, there is an important distinction between counting in-domain and counting infinitely, which understudied in the literature. While counting in-domain can be achieved with various approxi- mations, counting infinitely imposes a significant challenge concerning induction and extrapolation. We provide extensive empirical evidence showing that I) Counting is not a primitive function of Transformer computation as others have claimed, as it may require multiple layers to succeed at counting in-domain; 2) Different positional embeddings enable oft-of-domain generalization in different forms of counting. Our findings have implications for avoiding out-of-distrrbuti counter states in practical scenarios and the promise of integrating different positional embeddings. We also extend our investigation to recurrent architectures, including both traditional and modern models. We observe that while traditional RNNs easily generalize counting inductively, no single modern RNN generalizes on all six variants of our counting tasks, implying that inductive counting not only requires a recurrent formulation, but also demands expressive state dynamics. Thus, our investigation reveals a potential limitation where modern RNN architectures pay the cost for their lauded parallel training. motivating better solutions to combine the merits of Transformer and RNNs.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Emmanuel Abbe, Samy Bengio, Aryo Lotfi, and Kevin Rizk. Generalization on the unseen, logic reasoning and degree curriculum. In International Conference on Machine Learning, pp. 31-60.
PMLR, 2023.
Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur, Exploring length generalization in large language models. Advances in Neural Information Processing Systems, 35:38546-38556, 2022.
S. Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability of self-attention networks to recognize counter languages. ArXiv, abs/2009. 11264, 2020. URL htttt::////ppp setts: semant icscho
brg/CorpusTD:2220 856691
Satwik Bhattamishra, Arkil Patel, Varun Kanade, and Phil Blunsom. Simplicity bias in transformers and their ability to learn sparse boolean functions. arXiv preprint arXiv:2211.12316. 2022.
David Chiang and Peter Cholak. Overcoming a theoretical limitation of self-attention. arXiv preprint 1211 2022.
Jason Cong, John Peck, and Yuzheng Ding, Rasp: A general logic synthesis system for sram-based fpgas. In Proceedings of the 1996 ACM fourth international symposium on Field prograargge gate arnays, pp. 137-143, 1996.
Kathryn Davidson, Kortney Eng, and David Barner. Does learning to count involve a semantic induction? Cognition, 123(1):162-173, 2012.
Gr' egoire Del'etang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Marcus Hutter, Shane Legg, and Pedro A. Ortega. Neural networks and the chomsky hierarchy. ArXiv, abs/2207.020000 2022. URL http:://pppseeenniccccc..o.ooo httpaatticcccoaaa.oooooooooououe
255280065
Jacob Devlin, Ming-Was Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. North American Chapter of the Associa- tion for Computational Linguistics, 2019. URL https: / /appp.p../// semanticscholar org/
CorpusID:
Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jian, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D. Hwang, Soumya Sanyal, Sean Welleck, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi. Faith and fate: Limits of transformers on compositionality. ArXiv, abs/2305.11654 2023.
//ap:://app.. www.stttttccctoooooeeeee
oxq:/CorpusI: 258 2512963999111
Javid Ebrahimi, Dhruv Gelda, and Wei Zhang. How can self-attention networks recognize dyck-n languages? arXiv preprint arXiv:2010.04303, 2020.
Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Deep Ganguli, Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. A mathematical framework for transformer circuits. Transformer Circuits Thread, 2021. https:/transffrme--ciiooo wwtp:/ppp////a///eo/ott/t/
Zac Hatfield-Dodde
Nelson Elhage, Tristan Hume, Catherine Olsson, Neel Nanda, Tom Henighan, Scott Johnston, Sheer E[Showk, Nicholas Joseph, Nova DasSarma, Ben Mann, Danny Hernandez, Amanda Askell, Kamal Ndousse, Andy Jones, Dawn Drain, Anna Chen, Yuntao Bai, Deep Ganguli, Liane Lovitt, Zac HatfieldDDodds, Jackson Kermion, Tom Conerly, Shauna Kravec, Stanislav Fort, Saurav Kadavath, Josh Jacobson, Eli Tran-Johnson, Jared Kaplan, Jack Clark, Tom Brown, Sam McCandlish, Dario Amodei, and Christopher Olah. Softmax linear units. Transformer Circuits Thread, 2022. hutps//traassfrmee-cccciiss wuw.:icciiissuu//2222/////ddddd
Jeffrey L. Elman. Finding structure in time. Cognitive Science 14(2):179-21 1990. URL https 7/on 1 inel Sibrrr..... y.w. wi ley. com/ doi /wwp//b//////ooooo 12000.0000011111 670 (0115167770001111 402_

---

Published as a conference paper at ICLR 2025
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces, 2023.
Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. arXiv preprint arXiv:2111.00333 2021a.
Albert Gu, Isys Johnson, Karan Goel, Khaled Saab, Tri Dao, Atri Rudra, and Christopher Ré. Combining recurrent, convolutional, and continuous-ting models with linear state space layers. Advances in neural information processing systems, 34:572-585, 2021b.
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 1-156-171, 2020.
Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention trans- formers: Perspectives from circuit complexity. Transactions of the Association for Computational Linguistics, 10:800-810, 2022.
Adi Haviv, Oni Ram, Ofir Press, Peter Izsak, and Omer Levy. Transformer language models without positional encodings still learn positional information. ArXiv, abs/2203. 16634, 2022. URL
https://api semant cascoo ar. www.ohow....rroooooooooooooooooe ID:
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9()): 1735-1780, 1997.
Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy. The impact of positional encoding on length generalization in transformers. Advances in Neural Information Processing Systems, 36, 2024.
Shun Kiyono, Sosuke Kobayashi, Jun Suzuki, and Kentaro Inui. Shape: Shifted absolute po- sition embedding for transformers. ArXiv, 10s/2109,0564,, 2021. URL https::/aaa //api
David Lindner, J'anos Kram'ar ar, Matthew Rahtz, Tom McGrath, and Vladimir Mikulik. Tracr: Compiled transformers laboratory for interpretabilitty. ArXiv, abs/2301. 005062, 2023. URL
:255744933
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Trans-
formers learn shortcuts to automata. ArXiv, 1b572910..00449, 2022. URL https://api
semanticscholas wwt. ort 2229922222222222
Eric Margolis and Stephen Laurence. How to learn the natural numbers: Inductive inference and the acquisition of number concepts. Cognition, 106(2):924-939, 2008
Sean McLeish, Arpit Bansal, Alex Stein, Neel Jain, John Kirchenbauer, Brian R Bartoldson, Bhavya Kailkhura, Abhinav Bhatele, Jonas Geiping. Avi Schwarzschild, et al. Transformers can do arithmetic with the right embeddings. arXiv preprint 2rXiv:2405.17339, 2024.
William Merrill, Sequential neural networks as automata. arXiv preprint arXiv:1906.01611 2019.
William Merrill, Ashish Sabharwal, and Noah A Smith. Saturated transformers are constant-depth threshold circuits. Transactions of the Association for Computational Linguistics, 10:843-856, 2022.
William Merrill, Jackson Petty, and Ashish Sabharwal. The illusion of state state-space models. arXiv preprini 0rXiv:2404.08819, 2024.
Neel Nanda, Lawrence Chan, Tom Lieberum. Jess Smith, and Jacob Steinhardt. Progress measures for grokking via mechanistic interpretability. arXiv preprint arXiv:2301.05217, 2023.
Eric Nguyen, Michael Poli, Marjan Faizi, Armin Thomas, Michael Wornow, Callum Birch-Sykes, Stefano Massaroli, Aman Patel, Clayton Rabideau, Yoshua Bengio, et al. Hyenadna: Long-range genomic sequence modeling at single nucleotide resolution. Advances in neural information processing systems, 36, 2024.
12

---

Published as a conference paper at ICLR 2025
Bo Peng, Eric Alcaide, Quentin Anthony, Alon Albalak, Samuel Arcadinho, Huanqi Cao, Xin Cheng, Michael Chung, Matteo Grella, Kranthi Kiran GV, et al. Rwkv: Reinventing rns for the transformer arXiv preprint 2.XY::2005.1044: 2023.
Bo Peng, Daniel Goldstein, Quentin Anthony, Alon Albalak, Eric Alcaide, Stella Biderman, Eugene Cheah, Teddy Ferdinan, Haowen Hou, Przemys aw Kazienko, Kranthikiran, Jan Koco' n, Bartlomiej Koptyra, Satyapriya Krishna, Ronald McClelland, Niklas Muennighoff, Fares Obeid, Atsushi Saito, Guangyu Song. Haoqin Tu, Stanislaw Wo" zniak, Ruichong Zhang, Bingchen Zhao, Qihang Zhao, Peng Zhou, Jian Zhu, and Ruijie Zhu. Eagle and finch: Rwkv with matrix- valued states and dynamic recurrence. ArXiv, abs/2404.05892, 2024. URL https://api
semanticscho Owt//ooppsID:
Steven T Piantadosi, Joshua B Tenenbaum, and Noah D Goodman.
Bootstrapping in language of thought: A formal model of numerical concept learning. Cognition, 123(2):199-217, 2012.
Olir Press, Noah A. Smith, and Mike Lewis. Train short, test long: Attention with linear bi-
ases enables input length extrapolation. ArXiv, abs/2108. 12409, 2021. BRRLh:t::
semanticscholas wwtp:orggg/ooooeee ID: 2
Lance Rips, Jennifer Asmuth, and Amber Bloomfield. Giving the boot to the bootstrap: How not to learn the natural numbers. Cognition, 101(3):B51-660, 2006.
Laurence Rousselle and Line Vossius, Acquiring the cardinal knowledge of number words: A conceptual replication. Journal of Numerical Cognition, 7(3):41--433 2021.
Anian Ruoss, Gr' egoire Del' etang, Del'etang, Tim Genewein, Jordi Grau-Moya, R. Csordás, Mehdi Abbana Bemnani, Shane Legg, and Joel Veness. Randomized positional encodings boost length generaliza- tion of transformers. ArXiv, abs/2305. 16843, 2023. BtLhhttss://att semanticccooolll.....
Pec//oorpuTD:25581/
Abulhair Saparov, Richard Yuanzhe Pang, Vishakh Padmakumar, Nitish Joshi, Seyed Mehran Kazemi, Najoung Kim, and He He. Testing the general deductive reasoning capacity of large language models using ood examples. ArXiv, hiss22355.15699 2023. URL https
//api. semanticccholaar http://c.w.........oooo..ooaaaaa
Barbara W Sarnecka and Susan Carey, How counting represents number: What children must learn and when they learn it. Cognition, 108(3):662-61) 667-674, 2008.
Xing Shi, Kevin Knight, and Deniz Yuret. Why neural translations are the right length. In Jian Su, Kevin Duh, and Xavier Carreras (eds.), Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 2278-2282, Austin, Texas, November 2016. Association for Computational Linguistics. doi: 10.18653/v 1/D16- 1248. URL BRL/attps://ccaaatho.oo
org/DD6 1--D-1611155
Elizabet Spaepen, Elizabeth A Gunderson, Dominic Gibson, Susan Goldin-Meadow, and Susan C Levine. Meaning before order: Cardinal principle knowledge predicts improvement in understand- ing the successor principle and exact ordering. Cognition. 180:59-81, 2018.
Lena Strobl, Dana Angluin, David Chiang, Jonathan Rawski, and Ashish Sabharwal. Transformers as transducers. arXiv preprint arXiv:2404.0200 2024.
Jianlin Su, Yu Lu, Shengfeng Pan, Bo Wen, and Yunfeng Liu. Roformer: Enhanced trans- former with rotary position embedding. ArXiv, has/2104400986/ 2021. URL https://apt
semant cscholalllle lar wwwp///rr..oaoooooo Co:p//orrppuuiDip 2D:3010713333333
Mirac Suzgun, Yonatan Belinkov, Stuart Shieber, and Sebastian Gehrmann. LSTM networks can per- form dynamic counting. In Jason Eisner, Matthias Gallé, Jeffrey Heinz, Ariadna Quattoni, and Guil- laume Rabusseau (eds.), Proceedings of the Workshop Deep Learning and Formal Languages: Building Bridges, pp. 44-54, Florence, August 2019. Association for Computational Linguistics. doi: 10.18653/v 1/W 3905. URL URL https: https////aaaattoggg...o.ooo
/W1 3905
Matteo Tiezzi, Michele Casoni, Alessandro Betti, Tommaso Guidi, Marco Gori, and Stefano Melacci. On the resurgence recurrent models for long sequences: Survey and research opportunities in the transformer arXiv preprint arXiv:2402.08 132, 2024.
13

---

Published as a conference paper at ICLR 2025
Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In Neural Information Processing Systems, 2017. htttl::: //pp.aapp..aa// www.nttcscooola..cooooooo htt.://aaa..aaaaooooaaaaaa:::::1
Petar Veličkovié, Adrià Puigdomenech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, and Charles Blundell. The clrs algorithmic reasoning benchmark. In International Conference on Machine Learning, pp. 20884-22102. PMLR, 2022.
Jesse Vig and Yonatan Belinkov. Analyzing the structure of attention transformer language model. arXiv preprint wrXiv::906.042600 2019.
Zhongwei Wan, Xin Wang, Che Liu, Samiul Alam, Yu Zheng, Zhongnan Qu, Shen Yan, Yi Zhu, Quanlu Zhang, Mosharaf Chowdhury, et al. Efficient large language models: A survey. arXiv preprint 2rXiv:23/2.03863, 1, 2023.
Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers, ArXiv, wbwp//06.0068/.... 2021. URLpttps:: //ap:::///pp... semant icscholar: wwtp/ooggouuee 2 235221630
Karen Wynn. Children's acquisition of the number words and the counting system. Cognitive psychology, 24(2)220-251, 1992.
Andy Yang and David Chiang. Counting like transformers: Compiling temporal counting logic into softmax transformers. arXiv preprint arXiv:2404.04399 2024.
Shunyu Yao, Binghui Peng, Christos H. Papadimitriou, and Karthik Narasimhan. Self-attention net- works can process bounded hierarchical languages. In Annual Meeting of the Association for Com- putational Linguistics, 2021. URL pottpss//appe /api. semantiiiieee wesanticcchaarr org/CorpusID;
235166395
Shuangfei Zhai, Walter Talbott, Nitish Srivastava, Chen Huang, Hanlin Goh, Ruixiang Zhang, and Josh Susskind. An attention free transformer. ArXiv, 2021. httpttttt//aaxi...t abs/
21C5 2105. 14103
Shizhuo Zhang, Curt Tigges, Stella Biderman, Maxim Raginsky, and Talia Ringer. Can transformers learn to solve problems recursively? ArXiv, abs/2305. 14699, 2023. URL https://api
semanticschin ar. wtt.:/cch.......oooooooo.saaaaa.
Ziqian Zhong, Ziming Liu, Max Tegmark, and Jacob Andreas. The clock and the pizza: Two stories in mechanistic explanation of neural networks. Advances in Neural Information Processing Systems, 36, 2024.
Hattie Zhou, Azade Nova, Hugo Larochelle, Aaron Courville, Behnam Neyshabur, and Hanie Sedghi. Teaching algorithmic reasoning via in-context learning. arXiv preprint arXiv:22/ 1000220..006666 2022.
Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Josh Susskind, Samy Bengio, and Preetum Nakkiran. What algorithms can transformers Iearn? study in length generalization. ArXiv, abs/2310. 16028, 2023. URL httpt::tt//aapt otteess...pi.eeettcccoooooo....o org/CorpusiD 264439160
Yongchao Zhou, Uri Alon, Xinyun Chen, Xuezhi Wang, Rishabh Agarwal, and Denny Zhou. Trans- formers can achieve length generalization but not robustly. arXiv preprint arXiv:2402.09371, 2024.
14

---

Published as a conference paper at ICLR 2025
A COUNTING IN OTHER LM ARCHITECTURES
A. OVERVIEW OF RNNS AND SSMS
recurrent architecture, at each step, maintains hidden state, updates the hidden state when consum- ing a new input, and produces an output based on both the current hidden state. We denote these three key operations, namely reception, transition and emission, by i + h, + h, and + o, respectively, A standard (Elman) RNN implements these three steps as matrix multiplication followed by nonlinear activation (o). An LSTM adopts additional parameters to compute multiplicative gates for these three steps, achieving more effective forgetting and memory.
h4 a (Whhh:-1 + Win bn)) =
+ bo)
State Space Models (SSM) also incorporate reception, transition and emission operations (Eq. 4 Moreover, there is feedthrough matrix Wi directly sending information from the input output, bypassing the hidden state Importantly. an SSM differs from standard RNN in omitting the nonlinearity in state transitions. This enables reparameterization of SSMs into convolutional form, presented in Equation
5
The kernelization trick is essential for parallelization during training.
h4 Whhhh-1 + Win
02 =
ho + Win
x k= ( ho Win ih, Who W hh W Wh: -.. Who W hh "W ih:
Linear Attention Zhai et al. (202), aims to substitute dot-product attention with sub-quadratic complexity. Linear attention initially suffered from severe performance drop, but was recently revitalized by the RWKV model family, introducing input-dependent parameters to boost performance. At the core of RWKV is the wkv operation where qi k, as attention, is replaced by a weighted sum of history states with discounted weights. A major innovation of RWKV-v6 versus previous RWKV models lies in ieput-dependent derivation of the decay factor w.
wky; Eiz (e (t-1--11, & vs) + gaths @ Ug
E e -- + eattii
The discounted moving average of history states can be rewritten in a recurrent form, thereby exhibiting a flavor of state transition.
let ag (e-11-1-0w+ Det o.), then a = = --- + t U
(7)
1=1
A.2 EXPERIMENTS AND RESULTS
Comparing performance between Transformers, RNNs and SSMs important because the dominance of sequential computation in RNNs or SSMs may encode inductive biases unavailable in Transformers and favorable for inductive counting. We use the same data and experiment settings described in 3 for RNNs and SSMs. We select the most performant hyperparameters for each individual architecture Results are shown in Table Al The key takeaway is that while Transformers need careful design decisions to count, the simple RNN is able do everything have asked, and the newer SSM architectures have degraded performance. We believe that the inferior performance of Mamba or RWKV is due their compromised expressivity in modeling state transitions in exchange for easy adaptation into the parallel training regime.
Section
B MEDIAN PERFORMANCE OUT OF FIVE RANDOM SEEDS
We sometimes observe high variances across random seeds, suggesting the difficulty for SGD A3 report the median performance for the same
to find generalizable solution. Table A2
Wi.. Wan. W ho and Win correspond to B, A. C and D. respectively, in the SSM community. *I (5e-5. 5, le- [4,3, 2)}, w_decay (0.0, 0.01, 0.001), dim 2 (9.7,10) dropout {0.0, 0.1), hatch=32
15

---

Published as a conference paper at ICLR 2025
RNN
LSTM
Mamba
RWKV-v6
Task
L
IND
OOD
IND
OOD
IND
OOD
IND
OOD
IND
OOD
100
100
100
15.5
100
100
Helper Token
2
100
100
100
100
100
100
100
12.1
100
100
4
100
100
100
100
100
100
100
76.5
100
100
1
100
100
100
100
100
100
100
1.5
100
3.2
Helper Token
2
100
100
100
100
100
100
100
5.1
100
0.0
+
Shifted Start
4
100
100
100
100
100
100
100
100
100
100
1
100
100
100
100
100
96.3
100
7.8
99.9
29.4
Shifted Start
2
100
100
100
100
99.9
100
30.8
4
100
100
100
100
100
100
100
97.5
100
93.8
100
100
100
100
100
98.3
91.8
11.5
100
8.2
Modular (mod10)
100
100
100
11.1
100
11.0
4
100
100
100
100
100
100
100
16.6
100
12.8
99.3
94.5
100
100
78.3
59.3
100
99.8
100
100
Selective
2
99.4
95.1
100
100
91.3
66.7
100
96.6
100
100
4
97.8
85.3
100
100
98.3
72.9
100
97.0
100
100
1 100
100
100
100
87.7
27.8
58.4
28.2
98.5
83.1
Selective
2 100
100
100
100
92.9
31.4
99.4
60.7
99.2
56.5
+ Modular (mod4)
100
37.8
100
100
Table Al:
Results for recurrent architectures (in-distribution, IND, and OOD). OOD accuracies are only calculated at extrapolation positions.
experiments presented Section 4 (Table 2 & ATI. There are large discrepancies between the best
and median results for Transformers with SinePE, APE, or SPE. Mamba and RWKV-v6 also exhibit such instability. As such, although certain architectural choices allows for generalizable solutions, learnability remains be matter of chance. We hope further study training dynamics find out why the likelihood of learning a generalizable solution varies across architectures.
NoPE
Sine
APE
RoPE
SPE
Task
IND
OOD
IND
OOD
IND
0OD
IND
OOD
IND
OOD
100
98.5
100
66.3
100
55.3
100
100
100
14.2
Helper Token
4
100
100
100
59.9
100
68.4
100
100
100
65.8
100
4.1
99.4
0.0
100
13.1
100
5.3
100
4.1
Helper Token
100
100
100
99.3
100
81.3
100
48.5
100
6.8
+ Shifted Start
100
99.7
100
84.3
100
100
100
100
100
84.5
100
15.3
99.8
2.7
100
40.6
100
37.4
99.6
8.7
Shifted Start
100
20.9
100
2.0
100
19.7
100
86.6
100
43.7
100
39.2
100
36.7
100
26.6
100
96.6
100
30.7
11.8
11.8
100
97.9
100
56.5
11.8
11.8
100
8.3
Modular (mod10)
11.8
11.8
100
11.8
100
11.8
11.8
100
100
100
99.9
11.8
11.8
100
10.2
95.4
9.2
95.8
51.0
100
10.6
99.7
26.4
99.7
57.1
Selective
2
99.7
94.1
99.3
16.3
100
13.5
99.7
48.9
99.7
81.2
4
99.7
100
100
99.8
100
99.9
99.7
47.6
99.7
95.4
Selective
92.2
55.1
98.7
37.9
99.7
27.2
98.1 1
32.1
99.6
46.1
Modular (mod4)
98.0
91.0
98.8
70.2
99.3
95.0
98.5
38.6
98.2
49,9
Table A2: Results for Transformers corresponding to Table switching from best to median performance out of 5 runs. Bold entries indicate >10 absolute gap between the median and best results.
16

---

Published as a conference paper at ICLR 2025
RNN
LSTM
Mamba
RWKV-v6
Task
L
IND
OOD
IND
OOD
IND
OOD
IND
0OD
IND
0OD
100
100
100
100
100
15.5
100
Helper Token
2
100
100
100
100
100
100
100
4.5
100
2.0
4
100
100
100
100
100
100
100
37.0
100
100
1
100
100
100
100
100
100
100
0.7
100
0,0
Helper Token
2
100
100
100
100
100
100
100
5.0
100
0.0
+
Shifted Start
4
100
100
100
100
100
100
100
100
100
44.2
1
100
100
100
100
100
95.9
100
5.2
99.9
25.0
Shifted Start
2
100
100
100
100
100
99.8
48.5
100
30.8
4
100
100
100
100
100
100
100
51.7
100
84.0
100
100
100
100
100
97.8
89.5
11.5
100
8.2
Modular (mod10)
100
100
100
100
100
100
11.1
100
4
100
100
100
100
100
100
100
11.0
100
9.3
1
98.6
92.5
100
100
72.9
53.0
100
99.3
99.9
98.6
Selective
2
99.3
93.7
100
100
91.3
66.7
100
94.8
100
99.9
4
97.3
81.9
100
100
98.2
67.2
100
96.7
100
97.7
1
100
100
100
100
86.1
27.3
58.1
27.4
98.5
83.1
Selective
2
100
100
100
100
91.0
31.4
99.1
55.0
99.2
56.5
+ Modular (mod4)
100
100
100
99.2
35.9
100
$7.9
100
55.1
Table A3: Results for recurrent architectures corresponding to Table A1
switching from best to median performance out of 5 runs. Bold entries indicate >10 absolute gap between the median and best results.
C IMPORTANCE OF BOS FOR NoPE AND ROPE
We observed grevious failures of NoPE and RoPE on Counting + Succession and Modular counting (Table 2 rows 1 & 5), where both IND and OOD performances were below chance-level. The inability to fit in-domain data took us by surprise. We perform further analysis and find that NoPE and RoPE crucially depend on the presence of a begin-of-sequence (bos) token in order to fit the in-domain data. Concretely, we insert <bos>, token distinct from the remaining vocabulary, at the beginning of each training sequence. Loss computation at the output side of <bos>> skipped. After such adjustment, NoPF and RoPF are able to achieve perfect IND accuracy on both Counting + Succession and Modular counting. Notably, <bos> also improves RoPE-OOD performance on modular counting well beyond the chance level. A question immediately arises: why other tasks were accomplished initially? To account for the IND success of NoPE and RoPE in other tasks studied in Section 4 we believe that the first token in shifted start sequence may have concurrently played the role of <bos> For selective counting, the task nature may remove the dependence on bos.
The special role of bos has been discussed in the literature. Chiang & Cholak 2022 manually constructed Transformer weights for recognizing two regular languages, where bos plays key roles in multiple steps of their construction. [Elhage et al. (2021) pointed out phenomenon called "resting", where an attention head predominantly attends to a meaningless token by default (i.e. resting position) if there is no token matches what it looks for. The bos token and punctuation tokens are common examples of resting positions in a pretrained Transformer. Similarly, VVig & Belinkov (2019) discovered that 57% of attention was directed the first token in pretrained GPT-2. These works provide clues for why bos is critical for NoPE and RoPE in certain counting tasks. A detailed answer left for future work. Another intriguing question why other PEs performed well without bos. One possibility is that different PEs tend to direct the Transformer towards different solutions, among which some relies on bos while others do not, implying a diverse algorithmic phase space (Zhong et al. 2024) in Transformers. Future work is needed to 1) characterize Transformers' algorithmic phase space, and 2) analyze how PEs constrain the "navigation" through such a space.
'For the Helper Token task, we reused the data generation process for shifted start sequences, simply fixing the shift to be O. We realized later that this inadvertently offered the opportunity for the shifted start token to <hos> Helper Token task in the way as in the Shifted Start task.
17

---

Published as a conference paper at ICLR 2025
w/o bos
w/ bos
NoPE
RoPE
NoPE
RoPE
Task
L
IND
00D
IND
0OD
IND
OOD
IND
0OD
Vanilla
1
2.0
0.0
2.0
0.0
100
0.0
100
0.0
Successson
2
2.0
0.0
2.0
0.0
100
0.0
100
0.0
4
2.0
0.0
2.0
0.0
100
0.0
100
0.0
1
11.8
11.8
11.8
11.8
100
10.1
100
27.8
Modular (mod 10)
2
12.0
11.8
11.8
11.8
100
8.6
100
40.3
4
11.8
11.8
11.8
11.8
100
8.6
100
41.6
Table A4: Grevious in-domain failures of NoPE and RoPE can be addressed by the bos token, though their OOD performance benefits less from bos. This finding calls for future work investigate how bos affects NoPE and RoPF, and why other PEs/tasks are not affected.
D MODULAR COUNTING ANALYSIS
This section complements Section We describe the additional experiments and analysis performed upon in-depth investigation of what influential factors account for the empirical observations on Modular Counting. The mechanism permitting generalization longer sequences consists of two steps: First Token Recognition and Dasition-based Modular Subtraction. These two steps demand a model break symmetry and build representations indicative of PID% 10, respectively. Figure A] and Figure A4 show that the model's inner workings highly align with our mechanism.
APE
SinePE
Value vectors
Attention output
heads
bou/d
6.00
heac
100-
Rindal Corgreene
2/21.
1/2L
8:30
1
6.000
Mexibel Compower)
00.
6.0
02
03
het
Prodec Comeeee
to.
0.-
2/41.
2/41.
-01
60
24
3.5
05
PVin Companeril
Fredbol Component2
Figure A1: The first token's 's intermediate representations stand out w.r. the first and second principal components. And this precedes the attention layer exhibiting an attention pattern concentrating on the first tok.
NoPE
Sine
APE
RoPE
SPE
Model Configs
IND
OOD
IND
OOD
IND
OOD
IND
OOD
IND
OOD
IL, 1h. 32d
0
0
100
100
100
100
0
100
100
II, 1h, 4d
0
100
100
100
100
0
0
100
100
Table A5: Results of IL Transformers trained on the first tak__oo_oooae homogeneous task. We report the accuracy of only the first token's prediction, because model would easily learn to predict the majority label 'F', which would already allows for a fairly high average accuracy.
First, we design a first tok homogeneous task to examine how well each PE schema supports the inductive bias for breaking the symmetry of homogeneous sequence. The input-output format is
18

---

Published as a conference paper at ICLR 2025
Output
T
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
Causal Transformer
Input
Position embedding (PE)
shift
Token embedding (TE)
Figure A2: Input-output format of the first tok__ooo_o homogeneous task, designed for the purpose of examining which types of PE can be leveraged by Transformers distinguish among identical tokens.
layer outpor
queries
layer MLP intemmaiate
layert
nici
Preddod Contee Cosppnan
APE:
-100
Pririipal Component.
-10
10
Panccpa Comporott
SteePE
-10
Princiall Covponent
APK www.curGergpeeet..........
600
10
precpe Component
200
SPS
-50
-397
Nin.pol Compunenn)
Micipal Comporent
205
203
000
Figure A3: PCA of intermediate states for 2L APE/SincPE/SPE Transformers trained on modular counting. This differentiates SPE from APE/SinePE in the ability to count modularly, although all three PEs accomplish fist token recognition.
illustrated in Figure A2 Each token is supposed predict binary label indicating whether it is the first token the input sequence. We construct training/IND sequences of length 50 and OOD sequences of length 128. Following the experimental setup Section we adopt the position-shin augmentation, 2) run each training job up to 312.5K or 625K steps (depending on when the model exhibits strong signs saturation or plateauing). 3) select the best checkpoint over the entire training course for each training job, and 4) report the best result out of five seeds. The metric is accuracy, for which we only evaluate on the first token's prediction. This is because a model would easily learn to predict the majority label 'F', which would already allows for a fairly high average accuracy, indeed observed that all models have perfectly learned to predict 'F' on non-firt first tokens, so the performance difference is only manifested via the first token's 's prediction. Table A5 presents the results: Transformers equipped with SinePE, APE or SPE can recognize the first token among homogeneous sequence, while NoPE and RoPE cannot. It is worth explaining that RoPE fails
19

---

Published as a conference paper at ICLR 2025
APE
SinePE
QLINO
keys 1014
keys head'
leyi hear
kxys
Hgs wu.14
lega Heacs
tepi hewr
kays
2/2L
OMTO
Searls
heall3
2/4L
3/4L
hon
leps
leys
4/4L
hore
Peys
Figure A4: Heads that concentrate their attention on the first_tok are prevelant beyond the first layer. Note that first tok heads do not unanimously attend the to the first_tok. Instead, they are selective for position indices with specific mod-10 10 values. Encoding such fourier features allows multiple first_tok heads to collaboratively attend to the first token and may help subsequent layers in performing modular arithmetic.
because it only modifies queries and keys, leaving the values identical for a homogeneous sequence. No matter how the attention weights vary, the attention output (i.e. weighted sum of identical value vectors) would still be identical throughout the sequence.
Second, to investigate whether a model builds representations indicative of PID% 10, we visualize principal components of intermediate states for 2L APE/SinePE/SPE Transformers trained on modular counting. The fact that APE/SinePE models construct 10 dinstinct groups of representation whereas SPE models do not, differentiates SPE from APE/SinePE in the ability to count modularly, although all three PEs accomplish fist token recognition.
Concretely, we feed an input sequence of 128 "a" tokens with PIDs 0-127 and record representations the 1st layer's output, the 2nd layer's queries and the 2nd layer's MLP intermediate states. In Figure A3 we plot the first two principal components for 128 tokens, color coded by PID% 10, e.g. tokens whose PIDs belong to 1, 11, 21, 31 ... are assigned the same color. To implement a generalizable solution for modular counting, tokens with the same value of PID% 10 should have close representations. From the plot we see that the APE/SinePE representations form clean clusters based on PID modulo 10, while the SPE representations do not.
20

---

Published as a conference paper at ICLR 2025
w/ Causal Masking
w/o Causal Masking
Model Configs
IND
OOD
IND
OOD
NoPE IL. 1h,
100
100
4.0
0.0
Table A6: Results of 1L Transformers trained on the first firstttokk heterogeneous task. We report the accuracy of only the first token's 's prediction, because model would easily learn to predict the majority label ',,, which would already allows for fairly high average accuracy. PEs are not implemented in order to demonstrate that Transformers can simply leverage causal masking to accomplish this task.
E SELECTIVE COUNTING ANALYSIS
This section complements Section We describe the additional experiments and analysis performed upon in-depth investigation of what influential factors account for the empirical observations on Selective Counting. Section 5 proposes two factors demanded by mechanism that permits general- ization: First Token Recognition and Token-based Attention. Unlike modular counting, where the inputs are homogeneous, selective counting designed to have heterogeneous inputs containing 10 unique tokens. First Token Recognition on heterogeneous inputs can achieved purely with causal masking. PEs may aid First Token Recognition, but at the meantime introduce intricacies interfering with Token-based Attention, as Token-based Attention ideally requires for the assignment of attention weights irrespective of positional information.
Ourput
Causal Transformer
Input
Token embedding (TE)
Figure AS: Input-output format of the first tok heterogeneous task, designed demonstrate that causal Transformer can recognize the first token in a heterogeneous input sequence without the need for PEs.
First, we design a first tok_ heterogeneous task demonstrate that causal masking enables First Token Recognition on heterogeneous inputs. The input-output format is illustrated in Figure A5 differs from first_too tac_tooohoont Jomogeneous in that I) each input sequence contains a random number of 10 different tokens, and 2) the removal of PEs. We construct training/IND sequences of length 50 and OOD sequences of length 128, randomly selecting the number of occurrences for each token and randomly shuffling the sequence. The experimental setup and evlauation metric identical to forst_tol mook_hooogeeeuus Table (66ppresent the results: With causal masking, a NoPE Transformer can accomplish the task with few as head and four hidden dimensions. This is no longer achievable without causal masking, emphasizing the critical role played by causal masking in first tok heterogeneouss In fact, we are able to understand the inner workings of a causal Transformer on foffrrt_fooo heterogeneous. Thanks to causal masking, the first tok will have nothing to attend other than itself. Non-firs first tokens will merge features from predecessors during attention. MLP layers will learn to distinguish between representations resulted from merges representations that have not been merged.
Second, we argue that PEs complicate the picture, because PFs might be initially involved in First Token Recognition, but should better ignored in order for Token-bused Attention. This explains why NoPE 2L generalizes well in selective counting, whereas APE/SincPE/SPE only achieves generalization with 4L (Table 2 row 6). SPE's performance is second to NoPE in a sense that suffers less from the complication introduced by PEs only single dim is affected by PIDs in SPE.
The complication caused by PEs further evidenced through comparing performance with vs. without BOS. Concretely, repeat our selective counting experiments except for the explicit inclusion of beginning-on offee-------eeceee (BOS) token. With BOS, PEs need not to be actively engaged in First Token Recognition. Hence, APE and SinePE will receive cleaner supervision signals encouraging them to
21

---

Published as a conference paper at ICLR 2025
NoPE
Sine
APE
RoPE
SPE
Task
IND
OOD
IND
0OD
IND
0OD
IND
00D
IND
OOD
Selective
9.3
100
68.8
100
10.6
100
29.9
100
61.3
Selective + bos
100
99.5
100
98.3
100
99.4
100
68.2
100
98.3
Selective
100
94.1
100
32.6
100
13.9
100
49.1
100
86.9
Selective + bos
2
100
99.9
100
100
100
95.8
100
40.9
100
99,9
Table A7: Selective Counting requires subtask of first token recognition. Such a requirement can be removed by explicitly providing a BOS. With BOS, NoPE and SPE Transformers can learn generalizable solution using one layer less than what would be required without BOS. Moreover, the once noticeable performance gap between APE/SinePE and NoPE disappears with BOS.
ignore PEs. As expected, the performance gap between NoPE/SPE and APE/SinePE vanishes when BOS is explictly included - they generalize equally well on selective counting with either IL or 2L (Table A7).
Lastly, we explain why RoPE is inferior other PE schemas in both Selective and Selective+BOS. We hypothesize that the enforcement of recency bias in RoPE makes it hard to escape the influence of positions when computing attention weights. This is in contrast to APE/SinePE/SPEE in which case it is possible to ignore the influence of PEs through learning. To measure the amount of sensitivity to PEs in the computation of attention weights, for each pair of (TIDsouree: source: TID targett). ) compute the std of 4sourca across all sourcss PID target) ) pairs that the source and target tokens can possibly take. VigureAA6 visualizes vissuaiizs such variation in attention weights for 11. APE/SinePE/SPE//oPPP Transformers trained the Selective+BOS task, color coded according to the std value interval. Darker cells suggest larger std values, implying greater amounts of variation in attention scores caused by PEs. Attention scores an APE model are the least affected by varying PIDs, which is conducive to saseen Attention. On the other hand, a RoPE model exhibits the greatest sensitivity PEs when computing attention weights, suggesting that it insufficiently learns to disregard PEs as required by the task. Such a shortcoming of RoPE prevents it from generalizing on selective counting.
SPE
RoPE
C-6.05
0.05-0.2
0.2-0.5
1-2
255
Figure A6: Variation in attention scores influenced by PEs. First, we take the best performing 1L checkpoints trained the Selective Counting + BOS task and compute attention scores (pre-softmax gkT)) between all pairs of tokens. Then we compute the std of attention scores across all possible assignments of PIDs. Hence, the value of each cell in each of the panels visualized here equals to the std of GaoureakTarger values across all PID pairs that the source and target tokens can take (i.e. PID souree PIDrarget following the causal rule).
22

---

Published as a conference paper at ICLR 2025
F ADDITIONAL RELATED WORKS
F.1 FORMALLY CHARACTERIZING TRANSFORMER EXPRESSIVITY
p021 introduces functional library of Transformer capabilities, based on the Python programming language. It lays an important foundation for follow-up works to expand on. For example, Tracr (Lindner al., 2023) proposes a compiler that allows for automatic crafting of Transformer weights from a RASP script. This facilitates the comparison of solutions learned through SGD versus "canonical" ones human would create. Zhou et al. (2023) updates the RASP library by adding more realistic assumptions the numerical bounds, well as how the position indexes can contribute to the computation graph.
RASP (Weiss et
Others characterize Transformer computations from the perspective of boolean circuits (Cong et al. 1996; Yang & Chiang 2024, Strobl et al. 2024 Merrill et al.) 2022), where primitives are atomic boolean operations. This is distinct from RASP, Tracr and our work, as we deal with functional prim- itives, but may contribute complementary insights. Also note that there lacks empirical validations accompanying this line of research, opening the room for future work to bridge this gap.
Transformers can be analyzed through Automata Theory (Liu et al. 2022 Del' etang et al. 2022) This branch has not reached agreement where the hard boundary for Transformer's capacity lies. For example, while (Hahn) 2020) proves the hard limits of self-attention on modeling Dyck, (Yao ct al. 2021; Ebrahimi al. 2020) demonstrated empirical success. We believe that nuances regarding the task format, architectural modifications and the definition of generalization vary across studies. It invites significant future contributions either remove this complication or unify these nuances.
F.2 RECOGNIZING THE PARITY LANGUAGE
There is strong connection between work and previous works PARITY counter languages. Hahn (2020) suggested that Transformers have theoretical difficulty in expressing PARITY, while Chiang & Cholak (2022) demonstrated that such limitation be overcome via condtconst weights Regarding this topic, it is important to distinguish between two notions of difficulty: difficulty fit in-domain data difficulty to
In the context of theoretical discussions, the difficulty of PARITY for transformers often means the inability to fit the training data when the training sequence length approaches infinity, i.c. Transformers cannot express PARITY for arbitrarily long sequences. Such limitation is empirically corroborated for pure-attention Transformers. Bhattamishra et al. (2020) argued for the necessity of PEs in recognizing PARITY, while admitting that PEs learned in-domain cannot be used for sequences of higher lengths. Our results similarly suggest that PEs enable Transformers to fit the training data where NoPE fails to learn. However, "difficulty" in the context of this paper mainly refers to generalization beyond the training SEQLEN range. The PE shift trick used our experiments presents one step towards better generalization performance. But we demonstrate that PE shift only lifts one barrier towards generalization (OOD- position), leaving the other barriers (OOD-cardinality, OOD-range-of-depenne
unsolved.
F.3 RECURRENCE WITH ATTENTION
Many studies attempt to promote new architectures that address the fundamental tradeoff between efficient training and efficient inference. Transformers achieve the former thanks to the parallel attention mechanism, while an RNN features the latter with linear time complexity and constant history memory. Towards achieving the best of both worlds, previous works have focused on either
proposing attention-ish mechanisms with subquadratic time complexity (Zhai et al. 202 Peng et al. 2023 2024), or modernizing RNN to permit parallelized training (Gu al. 202 Gu & Dao 2023
Nguyen et al. 2024). We refer the reader to Tiezzi et al. (2024); Wan et al. (202) for surveys on this emergent area. Extending the expressivity analysis for Transformers to these new RNN architectures
(Merrill 2019: Merrill et al. 2024) would be a fruitful direction.
23

---

Published as a conference paper at ICLR 2025
G ADDITIONAL FIGURES AND TABLES
Training Data
IND Testing Data
0OD Testing Data
0.10
0.10
0.3
Frequency
Frequency
Frequency
0.2
2.05
0.05
0.00
0.0
8 10
2
5
10
Count(a;) in the input sequencce
Count in the input sequence
Count(a;) in the imput sequence
Figure A7:
Distribution of the number of occurrences for token 'aj" in Selective Counting. In the OOD test set, Count('as au ") is skewed towards larger values because OOD sequences are longer while restrict each token appear less than ten times avoid OOD-cardinllity Tokens "ag..-010" have similar distributions.
MAX TRAIN SEQLEN MAX OOD SEQLEN
25 550
50
100
25
100
50
200
25 200
Task
IND
OOD
OOD
OOD
IND
OOD
IND
OOD
Shifted Start
84.3
100
98.9
100
30.9
100
22.1
100
Table A8: Performance of RoPE 4L Transformers on Shifted Start Counting with varied combinations of MAX TRAIN SEQLEN and MAX OOD SEQLEN. The MAX PID hyperparameter is also adjusted in proportion to MAX OOD SEQLEN. Generalization deteriorates as the ratio between MAX_OOD SEQLEN and MAX TRAIN TRAIN_SEQLEN becomes greater. MAX_OODSSEQLEEN
24


Reviews:
[{"review_id": "uVbdg7K77f", "reviewer": "Reviewer_jHk7", "summary": "This paper studies the ability of language models to learn counting inductively. Specifically, whether they can generalize counting beyond their training data. The experiments train Transformers with various positional embedding strategies (APE, SinePE, RoPE, SPE, NoPE). The core finding is that Transformers require specific positional embedding configurations to count effectively, while traditional RNNs handle counting tasks more naturally. The experiments reveal that different positional embedding approaches have distinct strengths: RoPE excels at unbounded counting with shifted starts, SinePE and APE perform well on both modular and selective counting, while NoPE and SPE are effective only for selective counting. These findings demonstrate that different architectural choices and embedding strategies significantly impact a model's ability to learn counting inductively, with implications for how counting capabilities should be implemented in language models.\n\nGenerally, this paper was very well written and easy to read. I would say that the biggest weakness is in the introduction and framing of the paper, where the formatting is unclear and the strong experimental results don't come through. If you can improve the first couple pages, this should be an excellent paper.", "questions": "I would really love to see you take this analysis into the interpretability setting. With controlled datasets like this, tools like activation patching a distributed alignment search could be used to localize counting states within network representations, and then you could get a mechanistic analysis of how this ability develops!", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The generalization splits and counting tasks seem reasonable to me, clearly thought out well. The different performance across all of the kinds of positional encodings is very interesting, and I love the contrast between modular counting and typical unbounded state counting.\n\nIt's really interesting to focus on the positional embeddings as the design choice that might build in an inductive bias towards being able to count. It seems like core cognitive skills are implicitly built into different architectures, and perhaps papers like this one will lead to something exciting and new!", "weaknesses": "The abstract is very wordy and spends too much time explaining why counting is important. I would shorten the first half of the abstract to two or three sentences.\n\nThe quote at the beginning of the introduction, I’m not sure who the quote is being attributed to.\n\nI am surprised you didn’t cite the bootstrapping counting paper by Steve Piantadosi, Josh Tenebaum, and Noah Goodman. This seems like an important citation, as this paper makes good on Carey’s earlier ideas in a computational framework.\n\nThe formatting for the inductive counting principle makes it unclear where this principle is coming from. Is it from an earlier work, or is it just a general idea that you are making precise here? The reference to ordered lists of words makes the definition seem a bit idiosyncratic, but maybe I’m wrong about this!", "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": "yZAaqf0Udp", "reviewer": "Reviewer_oPHk", "summary": "This work emphasizes the limitations in language models for counting tasks. The authors examine various architectures, including RNNs, Transformers, and modern state-space models with a suite of experiments. They find that while traditional RNNs can easily count inductively, Transformers struggle without additional design considerations, and modern state-space models face degraded performance.", "questions": "How can the conclusions of this paper generalize to real-world tasks, such as math, code, and so on?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This work focuses on a specific problem, the counting task, for the language models. The authors conduct many experiments to investigate the ability to count systematically. \n2. This paper not only focuses on the standard transformer architectures but also investigates many popular modern architectures.", "weaknesses": "1. **Lack of Insights:** Although this work conducts many experiments to support their findings, it offers limited insights into the reasons behind the poor performance of Transformers and modern RNNs. I encourage the authors to provide more intuition or explanations for the observed empirical phenomena.\n\n2. **Lack of Generality:** This paper focuses on the counting task, which I acknowledge is an important task. However, it remains unclear how performance on this task influences real-world applications. The conclusions are specific to counting tasks and may not generalize well to real-world scenarios.\n\n3. **Lack of Novelty:** While the paper addresses an important aspect of language model performance, it does not introduce significantly new concepts or methodologies. Similar studies[1] have already explored the limitations of Transformers in various tasks. This work just conducts some experiments in different architectures and does not offer sufficient contributions.\n\n[1] When Can Transformers Count to n?", "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": "iby59bcZER", "reviewer": "Reviewer_RT8E", "summary": "The authors study the effect that the choice of position encoding in transformers has on their length generalization for counting. Specifically, they train transformers (<= 4 layers) on various counting problems, and evaluate their OOD performance. The counting problems require transformers to output a token representing the number of occurrences of certain input tokens. The variants of counting include shifted start, where the first input token is an offset to the counts transformers should output, modular arithmetic, and selective, where multiple classes of tokens are present in the input, and the counts of each class are to be tracked independently. Overall they find differences between the five position embeddings studied (NoPE, Sine, APE, ROPE and SPE), and conduct deeper analyses in the appendices to explain some of the more surprising findings.", "questions": "- Do you think that expressing numbers in bases (in the sense of base 10) is a source of inductive bias that can help length generalization? Would your results differ significantly? \n- Can you draw high level lessons from this? How would the findings here help improve the design of position embeddings?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Comprehensive empirical evaluation of the 5 position embeddings.\n- Analysis is reasonably thorough. e.g. I like the finding that RoPE fails to do modular counting, but not if there is a BOS token.", "weaknesses": "Counting setting far removed from practical language models.\n\n\nIssues with overclaiming in the interpretation and discussion of results. Specifically:\n- \"poor results for 1L and 2L models suggest that counting in Transformers may require a non-trivial computation budget\". I do not think the results are strong enough to support this claim. Firstly, 4 layers are still only a small fraction of most practical language models (e.g. even llama 8B has 32 layers), so \"non-trivial\" is some what of a stretch. Secondly, this studies the \"inductive bias\", i.e. the outcome of the particular training dynamics on this toy problem; it's entirely possible that some other synthetic set up, or even pretrained language models, can be more efficient. Claims like this is better substantiated with interpretability on pretrained language models, or an expressivity argument\n- \"Our results motivate the integration of multiple PE schemas to take advantage of orthongonal strengths.\" At no point do you study the setting of integrating several PEs. In fact, your results seem to suggest the opposite: that sometimes having PE with more degrees of freedom can do worse than having fewer (e.g. how NoPE can do better at some tasks)", "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": "Up6tLiPRJr", "reviewer": "Reviewer_FunV", "summary": "This paper questions the common belief that counting is a basic, easy-to-learn skill of transformer-based language models. It provides a detailed study of what it means for a language model to learn to count and the conditions that affect its ability to do so. The authors set up different counting tasks of varying levels of difficulty to test when and how transformers can learn to count. They compare different types of transformer models (mainly those with different positional encodings) and include comparisons to classic and modern RNNs. Results show that counting isn’t a natural skill for transformer and modern RNN models, especially when they need to generalize to counts they haven’t seen in training—a key requirement for inductive counting.", "questions": "I don’t have any further questions. The paper does a thorough job of explaining its goals and findings.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is well-written, organized, and easy to follow. The authors back up their claims with strong evidence and well-designed experiments, and they clearly explain the purpose and outcomes of each experiment. In particular, I like that:\n- The paper questions a basic assumption and shows that counting isn’t necessarily something language models can be expected to master but instead something they have to learn under specific conditions. I find this to be an important and illuminating insight.\n- By testing various transformers with different positional encodings and comparing them to RNNs, the paper provides a broad picture of how different architectures handle counting.\n- The finding that counting isn’t a built-in skill could shape future work in language model design and applications, as it highlights the need to consider how well a model can generalize basic counting tasks.", "weaknesses": "I couldn't find any major weaknesses in the paper. The one small issue I ran into was with the term “number word,” which wasn’t immediately clear. Adding an example early on—like explaining that you use decimal numbers as “number words”—could help readers follow this part more easily.", "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)