Language models need inductive biases to count inductively
Open accessAbstract
Counting is a fundamental example of generalization, whether viewed through the mathematical lens of Peano's axioms defining the natural numbers or the cognitive science literature for children learning to count. The argument holds for both cases that learning to count means learning to count infinitely. While few papers have tried to distill transformer "reasoning" to the simplest case of counting, investigating length generalization does occur throughout the literature. In the "train short, test long" paradigm of NLP, length refers to the training sentence length. In formal language recognition, length refers to the input sequence length, or the maximum stack size induced by a pushdown automata. In general problem solving, length refers to the number of hops in a deductive reasoning chain or the recursion depth. For all cases, counting is central to task success. And crucially, generalizing counting inductively is central to success on OOD instances. This work provides extensive empirical results on training language models to count. We experiment with 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 generalization with OOD-position and OOD-vocabulary. We find that while traditional RNNs trivially achieve inductive counting, Transformers have to rely on positional embeddings to count out-of-domain. 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 characterizations. Finally, modern RNNs also largely underperform traditional RNNs in generalizing counting inductively. We discuss how design choices that enable parallelized training of modern RNNs cause them to lose merits of a recurrent nature.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Counting is described as a notable fundamental challenge for LLMs, including reasoning models.
“Despite its simplicity, counting poses a notable fundamental challenge for LLMs”
From Large Language Model Reasoning Failures (2026) · cites this paper as Chang & Bisk, 2024
The Conclusion says counting infinitely poses a significant challenge for induction and extrapolation, and the Abstract reports that Transformers need positional embeddings to count out of domain. This supports a challenge for the language-model architectures studied, but not an unqualified claim about counting for LLMs generally; the paper also does not establish the added characterization about reasoning models. (LLM, conf=0.84)
Experimental — accuracy not yet measuredWebb et al. (2024) argue that solving the permuted task requires counting letter indices, which LLMs cannot do effectively without tools like a Python interpreter.
“In response, Webb et al. (2024) argue that solving the permuted task requires counting letter indices, which LLMs cannot do effectively without tools like a Python interpreter (see Chang & Bisk 2024).”
From Anthropocentric Bias in Language Model Evaluation (2026) · cites this paper as Chang & Bisk 2024
The Introduction says Transformers do not learn to count inductively, which supports the general point that counting can be difficult for them. But Chang and Bisk do not address Webb et al.’s permuted task, counting letter indices, or the need for a Python interpreter; those specifics are not established by this source. (LLM, conf=0.81)
Experimental — accuracy not yet measuredCounting poses a fundamental challenge for LLMs, including reasoning-specialized models.
“Despite its simplicity, counting poses a notable fundamental challenge for LLMs (Xu & Ma, 2024; Chang & Bisk, 2024; Zhang & He, 2024; Fu et al., 2024; Conde et al., 2025; Yehudai et al., 2024), even the reasoning ones (Malek et al., 2025)”
From Large Language Model Reasoning Failures (2026) · cites this paper as Chang & Bisk, 2024
Counting failures originate primarily from architectural and representational limits, including tokenization, positional encoding, and training data composition, rather than from superficial prompting or task framing.
“much work suggest that they originate primarily from architectural and representational limits, including tokenization (Zhang et al., 2024f; Shin & Kaneko, 2024), positional encoding (Chang & Bisk, 2024), and training data composition (Allen-Zhu & Li, 2024), rather than from superficial prompting or task framing on the application-level.”
From Large Language Model Reasoning Failures (2026) · cites this paper as Chang & Bisk, 2024
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., & Polosukhin, I. (2017) · arXiv · doi:10.48550/arxiv.1706.03762 · Cited by 120,404 · cited 1× · see citing works
“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.”
BackgroundHochreiter, S., & Schmidhuber, J. (1997) · Neural Computation · doi:10.1162/neco.1997.9.8.1735 · Cited by 102,318 · cited 3× · see citing works
“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.”
BackgroundBERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
Devlin, J., Chang, M.-W., Lee, K., & Toutanova, K. (2019) · Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers) · doi:10.18653/v1/n19-1423 · Cited by 48,293 · cited 2× · see citing works
“This is in contrast to APE/SinePE/SPE in which case it is possible to ignore the influence of PEs through learning.”
BackgroundElman, J. L. (1990) · Cognitive Science · doi:10.1207/s15516709cog1402_1 · Cited by 11,212 · cited 1× · see citing works
“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 A1).”
BackgroundRoFormer: Enhanced transformer with rotary position embedding
Su, J., Ahmed, M., Lu, Y., Pan, S., Bo, W., & Liu, Y. (2024) · Neurocomputing · doi:10.1016/j.neucom.2023.127063 · Cited by 1,957 · cited 2× · see citing works
“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.”
MethodResultRoFormer: Enhanced Transformer with Rotary Position Embedding
Su, J., Lu, Y., Pan, S., Murtadha, A., Wen, B., & Liu, Y. (2021) · arXiv · doi:10.48550/arxiv.2104.09864 · Cited by 1,952 · see citing works
Children's acquisition of the number words and the counting system
Wynn, K. (1992) · Cognitive Psychology · doi:10.1016/0010-0285(92)90008-p · Cited by 1,072 · cited 1× · see citing works
“…science research informs that children learn to count from 1 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 & Laurence, 2008).”
BackgroundEfficiently Modeling Long Sequences with Structured State Spaces
Gu, A., Goel, K., & Ré, C. (2021) · arXiv · doi:10.48550/arxiv.2111.00396 · Cited by 805 · cited 3× · see citing works
“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 Transformers, and recurrent inference, like RNNs.”
BackgroundMethodHow counting represents number: what children must learn and when they learn it.
Sarnecka, B., & Carey, S. (2008) · Cognition · doi:10.1016/j.cognition.2008.05.007 · Cited by 477 · cited 2× · see citing works
“This definition of counting is extensively studied in a branch of cognitive science concerning how children learn to count (Davidson et al., 2012; Rousselle & Vossius, 2021; Sarnecka & Carey, 2008; Spaepen et al., 2018).”
BackgroundMethodRWKV: Reinventing RNNs for the Transformer Era
Peng, B., Alcaide, E., Anthony, Q., Albalak, A., Arcadinho, S., Biderman, S., Cao, H., Cheng, X., Chung, M., Derczynski, L., et al. (2023) · Findings of the Association for Computational Linguistics: EMNLP 2023 · doi:10.18653/v1/2023.findings-emnlp.936 · Cited by 390 · cited 2× · see citing works
“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 Transformers, and recurrent inference, like RNNs.”
BackgroundCombining Recurrent, Convolutional, and Continuous-time Models with Linear State-Space LayersPreprint
Gu, A., Johnson, I., Goel, K., Saab, K. K., Dao, T., Atri Rudra, B., & Ré, C. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.13985 · Cited by 311 · cited 1× · see citing works
“…achieving the best of both worlds, previous works have focused on either proposing attention-ish mechanisms with subquadratic time complexity (Zhai et al., 2021; Peng et al., 2023; 2024), or modernizing RNN to permit parallelized training (Gu et al., 2021b; Gu & Dao, 2023; Nguyen et al., 2024).”
BackgroundAnalyzing the Structure of Attention in a Transformer Language Model
Vig, J., & Belinkov, Y. (2019) · Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP · doi:10.18653/v1/w19-4808 · Cited by 301 · cited 1× · see citing works
“We believe that injecting positional information only through a single dimension limits an SPE Transformer’s ability to build richer features based on positions, which probably explains why SPE succeeds at first token recognition but fails at modular counting.”
BackgroundNeural Networks and the Chomsky HierarchyPreprint
Del'etang, G., Ruoss, A., Grau-Moya, J., et al. (2022) · International Conference on Learning Representations · doi:10.48550/arxiv.2207.02098 · Cited by 270 · cited 4× · see citing 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., 2024; Merrill et al., 2022), or Automata Th…”
BackgroundMethodInfluentialTransformer Language Models without Positional Encodings Still Learn Positional Information
Haviv, A., Ram, O., Press, O., Izsak, P., & Levy, O. (2022) · Conference on Empirical Methods in Natural Language Processing · doi:10.48550/arxiv.2203.16634 · Cited by 210 · cited 1×
“This ensures that all position embeddings will be trained.”
BackgroundDoes learning to count involve a semantic induction?
Davidson, K., Eng, K., & Barner, D. (2012) · Cognition · doi:10.1016/j.cognition.2011.12.013 · Cited by 169 · cited 1× · see citing works
“This definition of counting is extensively studied in a branch of cognitive science concerning how children learn to count (Davidson et al., 2012; Rousselle & Vossius, 2021; Sarnecka & Carey, 2008; Spaepen et al., 2018).”
BackgroundHyenaDNA: Long-Range Genomic Sequence Modeling at Single Nucleotide Resolution
Nguyen, E., Poli, M., Faizi, M., Thomas, A., Birch-Sykes, C., Wornow, M., Patel, A., Rabideau, C., Massaroli, S., Bengio, Y., et al. (2023) · arXiv · doi:10.48550/arxiv.2306.15794 · Cited by 168 · cited 1× · see citing works
“…achieving the best of both worlds, previous works have focused on either proposing attention-ish mechanisms with subquadratic time complexity (Zhai et al., 2021; Peng et al., 2023; 2024), or modernizing RNN to permit parallelized training (Gu et al., 2021b; Gu & Dao, 2023; Nguyen et al., 2024).”
BackgroundTheoretical Limitations of Self-Attention in Neural Sequence Models
Hahn, M. (2020) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00306 · Cited by 165 · cited 3× · see citing works
“We expand the discussion on this large body of literature in Appendix F. Formal studies have established proofs for Transformers’ inability to count in a length-generalization regime (Hahn, 2020; Bhattamishra et al., 2020) (usually in the context of modeling counter languages).”
BackgroundTrain Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation
Press, O., Smith, N. A., & Lewis, M. (2021) · arXiv · doi:10.48550/arxiv.2108.12409 · Cited by 161 · see citing works
Testing the General Deductive Reasoning Capacity of Large Language Models Using OOD ExamplesPreprint
Saparov, A., Pang, R. Y., Padmakumar, V., et al. (2023) · Neural Information Processing Systems · doi:10.48550/arxiv.2305.15269 · Cited by 147 · cited 2× · see citing works
““Difficulty in generalizing to longer instances” is a 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; Bhattamishra et al., 2020).”
BackgroundOvercoming a Theoretical Limitation of Self-AttentionPreprint
Chiang, D., & Cholak, P. A. (2022) · Annual Meeting of the Association for Computational Linguistics · doi:10.48550/arxiv.2202.12172 · Cited by 144 · see citing works
Faith and Fate: Limits of Transformers on Compositionality
Dziri, N., Lu, X., Sclar, M., Li, X. (., Jiang, L., Lin, B. Y., Welleck, S., West, P., Bhagavatula, C., Bras, R. L., et al. (2023) · Advances in Neural Information Processing Systems 36 · doi:10.52202/075280-3081 · Cited by 124 · cited 1× · see citing works
““Difficulty in generalizing to longer instances” is a 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; Bhattamishra et al., 2020).”
BackgroundFaith and Fate: Limits of Transformers on Compositionality
Dziri, N., Lu, X., Sclar, M., Li, X. L., Jiang, L., Lin, B. Y., West, P., Bhagavatula, C., Bras, R. L., Hwang, J. D., et al. (2023) · arXiv · Cited by 124 · see citing works
RASP: A General Logic Synthesis System for SRAM-Based FPGAs
Cong, J., Peck, J., & Ding, Y. (1996) · Fourth International ACM Symposium on Field-Programmable Gate Arrays · doi:10.1145/228370.228390 · Cited by 111 · cited 2×
“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.”
BackgroundTransformers Can Do Arithmetic with the Right EmbeddingsPreprint
McLeish, S., Bansal, A., Stein, A., et al. (2024) · Neural Information Processing Systems · doi:10.48550/arxiv.2405.17399 · Cited by 95 · cited 1× · see citing works
“Finally, we also experiment with a “Helper Token + Shifted Start" to enrich the evidence that our task design does not permit easily-hackable solutions.”
MethodFunctional Interpolation for Relative Positions Improves Long Context TransformersPreprint
Li, S., You, C., Guruganesh, G., et al. (2024) · International Conference on Learning Representations · doi:10.48550/arxiv.2310.04418 · Cited by 89 · see citing works
Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean FunctionsPreprint
Bhattamishra, S., Patel, A., Kanade, V., et al. (2022) · Annual Meeting of the Association for Computational Linguistics · doi:10.48550/arxiv.2211.12316 · Cited by 84 · cited 2× · see citing works
“…which is believed to be a primitive function enabling a Transformer to perform a 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., 2022; Zhong et al., 2024; Veliˇckovi´c et…”
BackgroundWhy Neural Translations are the Right Length
Shi, X., Knight, K. K., & Yüret, D. (2016) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/d16-1248 · Cited by 67 · cited 1× · see citing works
“Note, there exists prior work hinting at counting in such architectures (Shi et al., 2016; Suzgun et al., 2019), but not directly evaluated in a systematic comparison.”
BackgroundSHAPE: Shifted Absolute Position Embedding for Transformers
Kiyono, S., Kobayashi, S., Suzuki, J., & Inui, K. (2021) · Conference on Empirical Methods in Natural Language Processing · doi:10.18653/v1/2021.emnlp-main.266 · Cited by 61 · cited 1× · see citing works
“To tackle the OOD-position issue Kiyono et al. (2021) proposes to augment the input position_ids (PIDs) with a random shift (shifted PEs) so that you start numbering positions from a random integer between 1 and P , instead of always starting from 1.”
BackgroundSpaepen, E., Gunderson, E. A., Gibson, D. J., et al. (2018) · Cognition · doi:10.1016/j.cognition.2018.06.012 · Cited by 58 · cited 1×
“This definition of counting is extensively studied in a branch of cognitive science concerning how children learn to count (Davidson et al., 2012; Rousselle & Vossius, 2021; Sarnecka & Carey, 2008; Spaepen et al., 2018).”
BackgroundZhai, S., Talbott, W., Srivastava, N., Huang, C., Goh, H., Zhang, R., & Susskind, J. (2021) · arXiv · doi:10.48550/arxiv.2105.14103 · Cited by 57 · cited 3× · see citing works
“The generalizable mechanism suitable for the Transformer architecture again consists of two critical steps: First Token Recognition and Token-based Attention .”
BackgroundInfluentialThe Impact of Positional Encoding on Length Generalization in Transformers
Kazemnejad, A., Padhi, I., Ramamurthy, K. N., Das, P., & Reddy, S. (2023) · arXiv · doi:10.48550/arxiv.2305.19466 · Cited by 54 · cited 1×
“…into hierarchies, with a notion of complexity informed by formal languages (Del’etang 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., 2023) or boolean functions (Bhattamishra et al., 2022; Abbe et al., 2023).”
BackgroundSequential Neural Networks as Automata
Merrill, W. (2019) · Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges · doi:10.18653/v1/w19-3901 · Cited by 54 · cited 1× · see citing works
“Extending the expressivity analysis for Transformers to these new RNN architectures (Merrill, 2019; Merrill et al., 2024)”
MethodProgress measures for grokking via mechanistic interpretability
Nanda, N., Chan, L., Lieberum, T., Smith, J., & Steinhardt, J. (2023) · arXiv · doi:10.48550/arxiv.2301.05217 · Cited by 51 · cited 1× · see citing works
“There is a possible connection between the bumps observed in some of our counting tasks to the grokking (Nanda et al., 2023) phenomena.”
BackgroundLSTM Networks Can Perform Dynamic Counting
Süzgün, M., Belinkov, Y., Shieber, S. M., & Gehrmann, S. (2019) · Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges · doi:10.18653/v1/w19-3905 · Cited by 50 · cited 1× · see citing works
“Note, there exists prior work hinting at counting in such architectures (Shi et al., 2016; Suzgun et al., 2019), but not directly evaluated in a systematic comparison.”
BackgroundExploring Length Generalization in Large Language Models
Anil, C., Wu, Y., Andreassen, A., Lewkowycz, A., Misra, V., Ramasesh, V., Slone, A., Gur-Ari, G., Dyer, E., & Neyshabur, B. (2022) · arXiv · doi:10.48550/arxiv.2207.04901 · Cited by 44 · cited 2× · see citing works
“It (Anil et al., 2022) or prompting (Zhou et al., 2022).”
BackgroundEfficient Large Language Models: A SurveyPreprint
Wan, Z., Wang, X., Che, L., Alam, S., Zheng, Y., Liu, J., Qu, Z., Yan, S., Zhu, Y., Zhang, Q., et al. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2312.03863 · Cited by 41 · cited 1× · see citing works
“We refer the reader to Tiezzi et al. (2024); Wan et al. (2023) for surveys on this emergent area.”
BackgroundOvercoming a Theoretical Limitation of Self-Attention
Chiang, D., & Cholak, P. (2022) · Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/2022.acl-long.527 · Cited by 39 · cited 4× · see citing works
“This mechanism closely resembles the construction in Chiang & Cholak (2022) for recognizing PARITY, which crucially depends on 1) a beginning-of-sequence (BOS) symbol and 2) uniform attention over tokens that are either the BOS or identical to self.”
BackgroundMethodInfluentialHow to learn the natural numbers: inductive inference and the acquisition of number concepts.
Margolis, E., & Laurence, S. (2008) · Cognition · doi:10.1016/j.cognition.2007.03.003 · Cited by 37 · cited 1×
“…science research informs that children learn to count from 1 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 & Laurence, 2008).”
BackgroundFormal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity
Hao, Y., Angluin, D., & Frank, R. (2022) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00490 · Cited by 27 · cited 2× · see citing works
“…a primitive function enabling a Transformer to perform a 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., 2022; Zhong et al., 2024; Veliˇckovi´c et al., 2022), and tracking the…”
BackgroundSaturated Transformers are Constant-Depth Threshold Circuits
Merrill, W., Sabharwal, A., & Smith, N. A. (2022) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00493 · Cited by 25 · cited 2× · see citing works
“…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., 2024; Merrill et al., 2022), or Automata Theory (Del’etang et al., 2022; Yao et al., 2021; Liu et al., 2022; Ebrahimi et al., 2020).”
BackgroundTeaching Algorithmic Reasoning via In-context LearningPreprint
Zhou, H., Nova, A., Larochelle, H., Courville, A. C., Neyshabur, B., & Sedghi, H. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2211.09066 · Cited by 24 · cited 1× · see citing works
“It (Anil et al., 2022) or prompting (Zhou et al., 2022).”
Self-Attention Networks Can Process Bounded Hierarchical Languages
Yao, S., Peng, B., Papadimitriou, C. H., & Narasimhan, K. (2021) · Annual Meeting of the Association for Computational Linguistics · doi:10.18653/v1/2021.acl-long.292 · Cited by 24 · cited 2× · see citing works
“…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., 2024; Merrill et al., 2022), or Automata Theory (Del’etang et al., 2022; Yao et al., 2021; Liu et al., 2022; Ebrahimi et al., 2020).”
BackgroundTiezzi, M., Casoni, M., Betti, A., et al. (2024) · arXiv.org · doi:10.48550/arxiv.2402.08132 · Cited by 23 · cited 1× · see citing works
“We refer the reader to Tiezzi et al. (2024); Wan et al. (2023) for surveys on this emergent area.”
BackgroundCan Transformers Learn to Solve Problems Recursively?Preprint
Zhang, S., Tigges, C., Biderman, S., et al. (2023) · arXiv.org · doi:10.48550/arxiv.2305.14699 · Cited by 22 · cited 2× · see citing works
““Difficulty in generalizing to longer instances” is a 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; Bhattamishra et al., 2020).”
BackgroundWeiss, G., Goldberg, Y., & Yahav, E. (2021) · arXiv · doi:10.48550/arxiv.2106.06981 · Cited by 18 · cited 8× · see citing works
“This corresponds to the “selector_width" primitive in RASP.”
BackgroundMethodInfluentialRWKV: Reinventing RNNs for the Transformer Era
Peng, B., Alcaide, E., Anthony, Q., Albalak, A., Arcadinho, S., Biderman, S., Cao, H., Cheng, X., Chung, M., Grella, M., et al. (2023) · arXiv · doi:10.48550/arxiv.2305.13048 · Cited by 17 · see citing works
The clock and the pizza: Two stories in mechanistic explanation of neural networks
Zhong, Z., Liu, Z., Tegmark, M., & Andreas, J. (2023) · arXiv · doi:10.48550/arxiv.2306.17844 · Cited by 14 · cited 1× · see citing works
“…perform a 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., 2022; Zhong et al., 2024; Veliˇckovi´c et al., 2022), and tracking the depth of reasoning chain (Saparov et al., 2023).”
BackgroundTransformers Learn Shortcuts to AutomataPreprint
Liu, B., Ash, J. T., Goel, S., et al. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2210.10749 · Cited by 13 · cited 6× · see citing works
“Transformers can be analyzed through Automata Theory (Liu et al., 2022; Del’etang et al., 2022).”
BackgroundMethodInfluentialEagle and Finch: RWKV with Matrix-Valued States and Dynamic Recurrence
Peng, B., Goldstein, D., Anthony, Q., Albalak, A., Alcaide, E., Biderman, S., Cheah, E., Du, X., Ferdinan, T., Hou, H., et al. (2024) · arXiv · doi:10.48550/arxiv.2404.05892 · Cited by 13 · see citing works
How Can Self-Attention Networks Recognize Dyck-n Languages?
Ebrahimi, J., Gelda, D., & Zhang, W. (2020) · Findings of the Association for Computational Linguistics: EMNLP (Findings of EMNLP) · doi:10.18653/v1/2020.findings-emnlp.384 · Cited by 13 · cited 4× · see citing works
“…enabling a Transformer to perform a 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., 2022; Zhong et al., 2024; Veliˇckovi´c et al., 2022), and tracking the depth of reasoning…”
BackgroundInfluentialOn the Ability of Self-Attention Networks to Recognize Counter Languages
Bhattamishra, S., Ahuja, K., & Goyal, N. (2020) · Conference on Empirical Methods in Natural Language Processing · doi:10.48550/arxiv.2009.11264 · Cited by 11 · cited 3×
“We expand the discussion on this large body of literature in Appendix F. Formal studies have established proofs for Transformers’ inability to count in a length-generalization regime (Hahn, 2020; Bhattamishra et al., 2020) (usually in the context of modeling counter languages).”
BackgroundWhat Algorithms can Transformers Learn? A Study in Length Generalization
Zhou, H., Bradley, A., Littwin, E., Razin, N., Saremi, O., Susskind, J., Bengio, S., & Nakkiran, P. (2023) · arXiv · doi:10.48550/arxiv.2310.16028 · Cited by 10 · cited 4× · see citing works
“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.”
BackgroundInfluentialThe CLRS Algorithmic Reasoning BenchmarkPreprint
Veličković, P., Badia, A. P., Budden, D. M., et al. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2205.15659 · Cited by 9 · cited 1× · see citing works
“…perform a 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., 2022; Zhong et al., 2024; Veliˇckovi´c et al., 2022), and tracking the depth of reasoning chain (Saparov et al., 2023).”
BackgroundTransformers as TransducersPreprint
Strobl, L., Angluin, D., Chiang, D., et al. (2024) · Transactions of the Association for Computational Linguistics · doi:10.48550/arxiv.2404.02040 · Cited by 9 · cited 2× · see citing works
“…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., 2024; Merrill et al., 2022), or Automata Theory (Del’etang et al., 2022; Yao et al., 2021; Liu et al., 2022; Ebrahimi et al., 2020).”
BackgroundAcquiring the cardinal knowledge of number words: A conceptual replication
Rousselle, L., & Vossius, L. (2021) · Journal of Numerical Cognition · doi:10.5964/jnc.7029 · Cited by 9 · cited 3×
“This definition of counting is extensively studied in a branch of cognitive science concerning how children learn to count (Davidson et al., 2012; Rousselle & Vossius, 2021; Sarnecka & Carey, 2008; Spaepen et al., 2018).”
BackgroundMethodTracr: Compiled Transformers as a Laboratory for Interpretability
Lindner, D., Kramár, J., Farquhar, S., Rahtz, M., McGrath, T., & Mikulik, V. (2023) · arXiv · doi:10.48550/arxiv.2301.05062 · Cited by 8 · cited 3× · see citing works
“…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., 2024; Merrill et al., 2022), or…”
BackgroundMethodTransformers Can Achieve Length Generalization But Not RobustlyPreprint
Zhou, Y., Alon, U., Chen, X., et al. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2402.09371 · Cited by 6 · see citing works
The Illusion of State in State-Space Models
Merrill, W., Petty, J., & Sabharwal, A. (2024) · arXiv · doi:10.48550/arxiv.2404.08819 · Cited by 5 · cited 1× · see citing works
“Extending the expressivity analysis for Transformers to these new RNN architectures (Merrill, 2019; Merrill et al., 2024)”
MethodGeneralization on the Unseen, Logic Reasoning and Degree Curriculum
Abbe, E., Bengio, S., Lotfi, A., & Rizk, K. (2023) · arXiv · doi:10.48550/arxiv.2301.13105 · Cited by 4 · cited 1×
“…into hierarchies, with a notion of complexity informed by formal languages (Del’etang 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., 2023) or boolean functions (Bhattamishra et al., 2022; Abbe et al., 2023).”
BackgroundRandomized Positional Encodings Boost Length Generalization of Transformers
Ruoss, A., Delétang, G., Genewein, T., Grau-Moya, J., Csordás, R., Bennani, M., Legg, S., & Veness, J. (2023) · arXiv · doi:10.48550/arxiv.2305.16843 · Cited by 1 · cited 1× · see citing works
“…into hierarchies, with a notion of complexity informed by formal languages (Del’etang 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., 2023) or boolean functions (Bhattamishra et al., 2022; Abbe et al., 2023).”
BackgroundCounting Like Transformers: Compiling Temporal Counting Logic Into Softmax TransformersPreprint
Yang, A., & Chiang, D. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2404.04393 · cited 2×
“…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., 2024; Merrill et al., 2022), or Automata Theory (Del’etang et al., 2022; Yao et al., 2021; Liu et al., 2022;…”
BackgroundHow Can Self-Attention Networks Recognize Dyck-n Languages?Preprint
Ebrahimi, J., Gelda, D., & Zhang, W. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2010.04303
SHAPE: Shifted Absolute Position Embedding for TransformersPreprint
Kiyono, S., Kobayashi, S., Suzuki, J., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2109.05644
Flagged first, then by citations
Cited by
Sorted by citations
When Models Manipulate Manifolds: The Geometry of a Counting Task
Gurnee, W., Ameisen, E., Kauvar, I., et al. (2026) · arXiv.org · doi:10.48550/arxiv.2601.04480 · Cited by 49
“Others have also studied, even going back to LSTMs, the existence of mechanisms in language models for controlling the length of output responses [66, 49], as well as performed more theoretical analyses of the space of counting algorithms [69, 8].”
Why Prompt Design Matters and Works: A Complexity Analysis of Prompt Search Space in LLMs
Zhang, X., Cao, J., Wei, J.-Q., et al. (2025) · Annual Meeting of the Association for Computational Linguistics · doi:10.18653/v1/2025.acl-long.1562 · Cited by 39
“The recursive reasoning problem arises when CoT instructions incorporate subtasks that LLMs struggle to solve without CoT prompting, such as counting operations (Chang and Bisk, 2024).”
When Can Transformers Count to n?
Yehudai, G., Kaplan, H., Dar, G., et al. (2024) · arXiv.org · doi:10.48550/arxiv.2407.15160 · Cited by 29
“Zhang et al. [2024] study the effect of tokenization for counting tasks, while Chang and Bisk [2024], Chiang and Cholak [2022] provide empirical evidence of an inductive bias toward the success of models in counting inductively.”
A Survey on Compositional Learning of AI Models: Theoretical and Experimetnal Practices
Sinha, S., Premsri, T., & Kordjamshidi, P. (2024) · Trans. Mach. Learn. Res. · doi:10.48550/arxiv.2406.08787 · Cited by 25
“Other works (Ruoss et al., 2023; Kazemnejad et al., 2023; Chang & Bisk, 2024) also investigate the effect of different positional encodings on the performance of Transformers for specifically length generalization.”
Tokenization Constraints in LLMs: A Study of Symbolic and Arithmetic Reasoning Limits
Zhang, X., Cao, J., Wei, J.-Q., et al. (2025) · arXiv.org · doi:10.48550/arxiv.2505.14178 · Cited by 16
“As established in complexity theory (Zhang et al., 2024; Li et al., 2024a; Chang and Bisk, 2024), this places answer-only Transformers in the class TC 0 —constant-depth circuits with polynomial size and threshold gates—incapable of performing even simple arithmetic functions such as parity,…”
InfluentialAgentic World Modeling for 6G: Near-Real-Time Generative State-Space Reasoning
Rezazadeh, F., Chergui, H., Debbah, M., et al. (2025) · arXiv.org · doi:10.48550/arxiv.2511.02748 · Cited by 7
“…when LLMs are used as the primary modeling primitive for control, several limitations emerge: (i) token-centric training and weak inductive bias [8] for stochastic dynamics make it difficult to learn calibrated physical behavior from KPIs; (ii) exposure bias [9], [10] and off-policy…”
Anthropocentric Bias in Language Model Evaluation
Millière, R., & Rathkopf, C. (2026) · Computational Linguistics · doi:10.1162/coli.a.582 · Cited by 6 · see citing works
Prompt-Based One-Shot Exact Length-Controlled Generation with LLMs
Xie, J., & Lee, H.-Y. (2025) · arXiv.org · doi:10.48550/arxiv.2508.13805 · Cited by 6
“Combining character-level tokenization with CoT pushes letter-counting accuracy from under 10% to 90–98% (Zhang, Cao, and You 2024; Chang and Bisk 2024).”
On the "Induction Bias" in Sequence Models
Ebrahimi, M., Defferrard, M., Panchal, S., et al. (2026) · arXiv.org · doi:10.48550/arxiv.2602.18333 · Cited by 5
“The inability to length-generalize in state tracking tasks has been shown to hold also for most existing state-space models (SSM) (Sarrof et al., 2024; Merrill et al., 2024).”
Frydenlund, A. (2025) · Annual Meeting of the Association for Computational Linguistics · doi:10.48550/arxiv.2503.10542 · Cited by 4
“Liu et al. (2023) demonstrated that automata on sequenced of length T can be simulated with trans-formers of log( T ) -depth via algorithmic ‘shortcuts’ and that these are not robust to OOD data (so being true shortcuts in the above sense).”
InfluentialUnderstanding Hallucinations in Large Visual and Language Models
Ho, Z. Y., Liang, S., & Tao, D. (2026) · ACM Computing Surveys · doi:10.1145/3811409 · Cited by 3 · see citing works
“Finally, hallucinations are strongly shaped by how well test-time inputs align with the structural biases induced by pretraining.”
Yuan, P.-W., Tan, C.-Y., Feng, S., et al. (2025) · Annual Meeting of the Association for Computational Linguistics · doi:10.48550/arxiv.2502.13544 · Cited by 3
“…remains a challenge for LLMs due to limitations in their architecture, such as position encoding (Butcher et al., 2024; Kazemnejad et al., 2024; Chang and Bisk, 2024) and decoding mechanisms(Huang et al., 2025 While effective in certain scenarios, these methods suffer from limited…”
Large Language Model Reasoning Failures
Song, P., Han, P., & Goodman, N. (2026) · arXiv · doi:10.48550/arxiv.2602.06176 · Cited by 3 · see citing works
A Vision for Multisensory Intelligence: Sensing, Science, and Synergy
Liang, P. (2026) · arXiv.org · doi:10.48550/arxiv.2601.04563 · Cited by 2
“However, existing models still lack inductive biases and positional awareness inherent in older recurrent architectures [52], often requiring far more data to generalize to longer, more compositional tasks.”
Sequential Enumeration in Large Language Models
Hou, K., Zorzi, M., & Testolin, A. (2025) · International Conference on Pattern Recognition · doi:10.48550/arxiv.2512.04727 · Cited by 2
“Some authors have proposed that these issues could be due to the non-recurrent nature of transformers [5], while others argue that layer normalization and scaling of the attention weights are the two main operations that make it impossible for standard transformers to learn counting in a…”
Causality ≠ Decodability, and Vice Versa: Lessons from Interpreting Counting ViTs
Huang, L., & Chang, Y. (2025) · arXiv.org · doi:10.48550/arxiv.2510.09794 · Cited by 2
“In this work, we investigate the relationship between decodability and causality in a vision transformer fine-tuned for object counting [3, 11, 12].”
Self-citationReview of Hallucination Understanding in Large Language and Vision ModelsPreprint
Ho, Z.-H., Liang, S., & Tao, D. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2510.00034
“Chang and Bisk [31] argued that transformers require explicit architectural inductive biases to generalise counting beyond seen examples.”
Reproducing Recurrent Transformers: The CoTFormer
Kavuncu, A., Vullo, B., & Berni, A. (2026) · arXiv.org · doi:10.48550/arxiv.2607.19405 · Cited by 1
Improved state mixing in higher-order and block diagonal linear recurrent networks
Dubinin, I., Orvieto, A., & Effenberger, F. (2026) · arXiv.org · doi:10.48550/arxiv.2602.12021 · Cited by 1
Is In-Context Learning Learning?
de Wynter, A. (2025) · arXiv.org · doi:10.48550/arxiv.2509.10414 · Cited by 1
“…Strobl et al., 2024a) Proposed explanations to this related model size to sensitivity to semantics (Shivagunde et al., 2024; Long et al., 2024) and inductive/selection biases Zhao et al. (2025); Chang & Bisk (2025) although this sensitivity disappeared when the exemplars included instructions.”
How do autoregressive transformers solve full addition?
Wang, P.-X., Chen, Y., Yu, M., et al. (2025) · Conference on Empirical Methods in Natural Language Processing · doi:10.18653/v1/2025.emnlp-main.643 · Cited by 1
“Even simpler tasks, such as counting (Chang and Bisk, 2024) and PARITY (Hahn and Rofin, 2024), are empirically difficult for transformers to generalize.”
List Counting Failures Are Not One Phenomenon
Hou, I. A., Mankarious, S., Zirikly, A., et al. (2026) · doi:10.48550/arxiv.2609.22230
“Theory and small-model work characterize when transformers can implement counting and related algorithms (Hahn, 2020; Yehudai et al., 2024; Behrens et al., 2025; Golkar et al., 2024; Chang and Bisk, 2025).”
When Does Reward Teach State? A Hidden-Automaton Instrument and the Group-Language Boundary
Allchin, J. (2026) · arXiv.org · doi:10.48550/arxiv.2607.11953
“…whereas attention-only encoders ( AC 0 -bounded under hard attention) need positional tricks and tend not to length-generalize (Strobl et al., 2024; Chang & Bisk, 2024; X. Huang et al., 2025); this Chomsky-hierarchy view of architecture-vs-task is mapped at scale by Delétang et al. (2023) and for…”
The FIL Hypothesis: Inductive Biases Help with Kernel Engineering
Rozanov, N., Dutta, S., Nakov, P., et al. (2026) · arXiv.org · doi:10.48550/arxiv.2606.30442
“Additionally, studies demonstrate that language models require explicit inductive biases to perform certain reasoning tasks like recursive counting, challenging the notion that scale alone suffices [11].”
Inductive Generalization for Robotic Manipulation
Macaluso, A., Zhang, H.-C., Masilamony, I., et al. (2026) · arXiv.org · doi:10.48550/arxiv.2606.20999
“Puzzles revealed by saturation regime evaluations have sparked discussions on understanding and injecting inductive biases into the model architecture [19, 28, 29, 30], and on exploring alternative architecture families [31, 32].”
Self-citationBeyond Accuracy: Diagnosing Algebraic Reasoning Failures in LLMs Across Nine Complexity Dimensions
Patil, P. V., Kumar, D., Sinha, Y., et al. (2026) · arXiv.org · doi:10.48550/arxiv.2604.06799
“This is because counting failure is rooted in tokenisation rather than tree structure or memory capacity (Zhang et al., 2024; Chang & Bisk, 2024).”
InfluentialDo Transformers Have the Ability for Periodicity Generalization?
Liu, H., Li, G., Dong, Y., et al. (2026) · arXiv.org · doi:10.48550/arxiv.2601.22690
“Other works (Nam et al., 2022; Ouellette et al., 2023; de Luca et al., 2024; Huang et al., 2025; Altabaa et al., 2025; Hu et al., 2025; Chang & Bisk, 2025) investigate OOD generalization on logic and reasoning tasks, finding that standard Transform-ers can fit the training distribution but often…”
Semantic Content Determines Algorithmic Performance
R'ios-Garc'ia, M., Alampara, N., & Jablonka, K. (2026) · arXiv.org · doi:10.48550/arxiv.2601.21618
“Given the foundational nature of counting, several works have evaluated LLMs’ counting-related abilities across diverse settings and benchmarks (Xu & Ma, 2025; Chang & Bisk, 2025; Fu et al., 2024; Srivastava et al., 2023b).”
Chang, Y., & Bisk, Y. (2025) · doi:10.48550/arxiv.2502.00197
“[26] reveals that the failure to generalize to greater cardinality persists whenever the neural network architecture cannot express the desired inductive bias.”
Self-citation
- Authors
- Chang, Y., & Bisk, Y.
- Affiliations
- Carnegie Mellon University (US)
- ORCID
- Bisk, Yonatan
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2024
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2405.20131
- OpenAlex
- W4399253050
- Cited by
- 0
- References
- 60
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- arXiv (Cornell University) (submittedVersion, cc-by)
- arXiv (Cornell University) (cc-by)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
- Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Domain Adaptation and Few-Shot Learning
- Keywords
- length generalization, out-of-domain generalization, inductive bias, positional encoding, transformer models, recurrent neural networks, state-space model, RWKV, formal language recognition
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
