# Language Models Need Inductive Biases to Count Inductively

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 60 references that are in the map.
- First posted on arXiv 30 May 2024.

## Builds on (most cited first, 30 of 46)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation](https://mlsanity.com/paper/2108.12409/) (2021)
- [Progress measures for grokking via mechanistic interpretability](https://mlsanity.com/paper/2301.05217/) (2023)
- [RWKV: Reinventing RNNs for the Transformer Era](https://mlsanity.com/paper/2305.13048/) (2023)
- [Combining Recurrent, Convolutional, and Continuous-time Models with Linear State-Space Layers](https://mlsanity.com/paper/2110.13985/) (2021)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [The Impact of Positional Encoding on Length Generalization in Transformers](https://mlsanity.com/paper/2305.19466/) (2023)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Analyzing the Structure of Attention in a Transformer Language Model](https://mlsanity.com/paper/1906.04284/) (2019)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [HyenaDNA: Long-Range Genomic Sequence Modeling at Single Nucleotide Resolution](https://mlsanity.com/paper/2306.15794/) (2023)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [Efficient Large Language Models: A Survey](https://mlsanity.com/paper/2312.03863/) (2023)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [Eagle and Finch: RWKV with Matrix-Valued States and Dynamic Recurrence](https://mlsanity.com/paper/2404.05892/) (2024)
- [The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networks](https://mlsanity.com/paper/2306.17844/) (2023)
- [Transformer Language Models without Positional Encodings Still Learn Positional Information](https://mlsanity.com/paper/2203.16634/) (2022)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [Randomized Positional Encodings Boost Length Generalization of Transformers](https://mlsanity.com/paper/2305.16843/) (2023)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [An Attention Free Transformer](https://mlsanity.com/paper/2105.14103/) (2021)
- [Teaching Algorithmic Reasoning via In-context Learning](https://mlsanity.com/paper/2211.09066/) (2022)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021)

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

- [When Models Manipulate Manifolds: The Geometry of a Counting Task](https://mlsanity.com/paper/2601.04480/) (2026)
- [Why Prompt Design Matters and Works: A Complexity Analysis of Prompt Search Space in LLMs](https://mlsanity.com/paper/2503.10084/) (2025)
- [When Can Transformers Count to n?](https://mlsanity.com/paper/2407.15160/) (2024)
- [Large Language Model Reasoning Failures](https://mlsanity.com/paper/2602.06176/) (2026)
- [A Survey on Compositional Learning of AI Models: Theoretical and Experimental Practices](https://mlsanity.com/paper/2406.08787/) (2024)
- [Tokenization Constraints in LLMs: A Study of Symbolic and Arithmetic Reasoning Limits](https://mlsanity.com/paper/2505.14178/) (2025)
- [Prompt-Based One-Shot Exact Length-Controlled Generation with LLMs](https://mlsanity.com/paper/2508.13805/) (2025)
- [Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More](https://mlsanity.com/paper/2503.10542/) (2025)
- [Sequential Enumeration in Large Language Models](https://mlsanity.com/paper/2512.04727/) (2025)
- [From Sub-Ability Diagnosis to Human-Aligned Generation: Bridging the Gap for Text Length Control via MARKERGEN](https://mlsanity.com/paper/2502.13544/) (2025)
- [Is In-Context Learning Learning?](https://mlsanity.com/paper/2509.10414/) (2025)
- [Review of Hallucination Understanding in Large Language and Vision Models](https://mlsanity.com/paper/2510.00034/) (2025)
- [Causality neq Decodability, and Vice Versa: Lessons from Interpreting Counting ViTs](https://mlsanity.com/paper/2510.09794/) (2025)
- [On the "Induction Bias" in Sequence Models](https://mlsanity.com/paper/2602.18333/) (2026)
- [Reproducing Recurrent Transformers: The CoTFormer](https://mlsanity.com/paper/2607.19405/) (2026)
- [Learning Model Successors](https://mlsanity.com/paper/2502.00197/) (2025)
- [A Vision for Multisensory Intelligence: Sensing, Science, and Synergy](https://mlsanity.com/paper/2601.04563/) (2026)
- [Semantic Content Determines Algorithmic Performance](https://mlsanity.com/paper/2601.21618/) (2026)
- [Do Transformers Have the Ability for Periodicity Generalization?](https://mlsanity.com/paper/2601.22690/) (2026)
- [Improved state mixing in higher-order and block diagonal linear recurrent networks](https://mlsanity.com/paper/2602.12021/) (2026)
- [Beyond Accuracy: Diagnosing Algebraic Reasoning Failures in LLMs Across Nine Complexity Dimensions](https://mlsanity.com/paper/2604.06799/) (2026)
- [Inductive Generalization for Robotic Manipulation](https://mlsanity.com/paper/2606.20999/) (2026)
- [The FIL Hypothesis: Inductive Biases Help with Kernel Engineering](https://mlsanity.com/paper/2606.30442/) (2026)
- [When Does Reward Teach State? A Hidden-Automaton Instrument and a Group-Language Warning Signal](https://mlsanity.com/paper/2607.11953/) (2026)
- [List Counting Failures Are Not One Phenomenon](https://mlsanity.com/paper/2609.22230/) (2026)

## Abstract (arXiv)

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.