# LSTM Networks Can Perform Dynamic Counting

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

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2019.

## Built on by (most cited first, 30 of 45)

- [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 Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [How Do Transformers Learn Topic Structure: Towards a Mechanistic Understanding](https://mlsanity.com/paper/2303.04245/) (2023)
- [Representing Numbers in NLP: a Survey and a Vision](https://mlsanity.com/paper/2103.13136/) (2021)
- [Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions](https://mlsanity.com/paper/2211.12316/) (2022)
- [When Models Manipulate Manifolds: The Geometry of a Counting Task](https://mlsanity.com/paper/2601.04480/) (2026)
- [Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biases](https://mlsanity.com/paper/2502.19249/) (2025)
- [Foundation Metrics for Evaluating Effectiveness of Healthcare Conversations Powered by Generative AI](https://mlsanity.com/paper/2309.12444/) (2023)
- [Counting Ability of Large Language Models and Impact of Tokenization](https://mlsanity.com/paper/2410.19730/) (2024)
- [Transformers are uninterpretable with myopic methods: a case study with bounded Dyck grammars](https://mlsanity.com/paper/2312.01429/) (2023)
- [Separations in the Representational Capabilities of Transformers and Recurrent Architectures](https://mlsanity.com/paper/2406.09347/) (2024)
- [Language Models Need Inductive Biases to Count Inductively](https://mlsanity.com/paper/2405.20131/) (2024)
- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (2024)
- [Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions](https://mlsanity.com/paper/2310.16076/) (2023)
- [What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languages](https://mlsanity.com/paper/2406.04289/) (2024)
- [Bridging the Empirical-Theoretical Gap in Neural Network Formal Language Learning Using Minimum Description Length](https://mlsanity.com/paper/2402.10013/) (2024)
- [Benchmarking Compositionality with Formal Languages](https://mlsanity.com/paper/2208.08195/) (2022)
- [Counting and Algorithmic Generalization with Transformers](https://mlsanity.com/paper/2310.08661/) (2023)
- [Can RNNs learn Recursive Nested Subject-Verb Agreements?](https://mlsanity.com/paper/2101.02258/) (2021)
- [Formal Language Theory Meets Modern NLP](https://mlsanity.com/paper/2102.10094/) (2021)
- [Tokenization Constraints in LLMs: A Study of Symbolic and Arithmetic Reasoning Limits](https://mlsanity.com/paper/2505.14178/) (2025)
- [Recognizing and Verifying Mathematical Equations using Multiplicative Differential Neural Units](https://mlsanity.com/paper/2104.02899/) (2021)
- [As Easy as 1, 2, 3: Behavioural Testing of NMT Systems for Numerical Translation](https://mlsanity.com/paper/2107.08357/) (2021)
- [Meta-Learning Neural Mechanisms rather than Bayesian Priors](https://mlsanity.com/paper/2503.16048/) (2025)
- [Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanations](https://mlsanity.com/paper/2112.09174/) (2021)
- [Exploring the Long-Term Generalization of Counting Behavior in RNNs](https://mlsanity.com/paper/2211.16429/) (2022)
- [Introducing Rhetorical Parallelism Detection: A New Task with Datasets, Metrics, and Baselines](https://mlsanity.com/paper/2312.00100/) (2023)
- [The Limitations of Limited Context for Constituency Parsing](https://mlsanity.com/paper/2106.01580/) (2021)
- [Implicit N-grams Induced by Recurrence](https://mlsanity.com/paper/2205.02724/) (2022)

## Abstract (arXiv)

In this paper, we systematically assess the ability of standard recurrent networks to perform dynamic counting and to encode hierarchical representations. All the neural models in our experiments are designed to be small-sized networks both to prevent them from memorizing the training sets and to visualize and interpret their behaviour at test time. Our results demonstrate that the Long Short-Term Memory (LSTM) networks can learn to recognize the well-balanced parenthesis language (Dyck-1) and the shuffles of multiple Dyck-1 languages, each defined over different parenthesis-pairs, by emulating simple real-time k-counter machines. To the best of our knowledge, this work is the first study to introduce the shuffle languages to analyze the computational power of neural networks. We also show that a single-layer LSTM with only one hidden unit is practically sufficient for recognizing the Dyck-1 language. However, none of our recurrent networks was able to yield a good performance on the Dyck-2 language learning task, which requires a model to have a stack-like mechanism for recognition.