# Theoretical Conditions and Empirical Failure of Bracket Counting on Long Sequences with Linear Recurrent Networks

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 18 references that are in the map.
- First posted on arXiv 7 Apr 2023.

## Builds on (most cited first, 10 of 10)

- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [Compositional Generalization via Neural-Symbolic Stack Machines](https://mlsanity.com/paper/2008.06662/) (2020)
- [Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets](https://mlsanity.com/paper/1503.01007/) (2015)
- [A Formal Hierarchy of RNN Architectures](https://mlsanity.com/paper/2004.08500/) (2020)
- [Learning to Transduce with Unbounded Memory](https://mlsanity.com/paper/1506.02516/) (2015)
- [Sequential Neural Networks as Automata](https://mlsanity.com/paper/1906.01615/) (2019)
- [LSTM Networks Can Perform Dynamic Counting](https://mlsanity.com/paper/1906.03648/) (2019)
- [Memory-Augmented Recurrent Neural Networks Can Learn Generalized Dyck Languages](https://mlsanity.com/paper/1911.03329/) (2019)
- [On the Linguistic Capacity of Real-Time Counter Automata](https://mlsanity.com/paper/2004.06866/) (2020)
- [Exploring the Long-Term Generalization of Counting Behavior in RNNs](https://mlsanity.com/paper/2211.16429/) (2022)

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

- [Which Word Orders Facilitate Length Generalization in LMs? An Investigation with GCG-Based Artificial Languages](https://mlsanity.com/paper/2510.12722/) (2025)
- [Benchmarking Neural Network Generalization for Grammar Induction](https://mlsanity.com/paper/2308.08253/) (2023)
- [What Kind of Language is Easy to Language-Model Under Curriculum Learning?](https://mlsanity.com/paper/2604.26844/) (2026)

## Abstract (arXiv)

Previous work has established that RNNs with an unbounded activation function have the capacity to count exactly. However, it has also been shown that RNNs are challenging to train effectively and generally do not learn exact counting behaviour. In this paper, we focus on this problem by studying the simplest possible RNN, a linear single-cell network. We conduct a theoretical analysis of linear RNNs and identify conditions for the models to exhibit exact counting behaviour. We provide a formal proof that these conditions are necessary and sufficient. We also conduct an empirical analysis using tasks involving a Dyck-1-like Balanced Bracket language under two different settings. We observe that linear RNNs generally do not meet the necessary and sufficient conditions for counting behaviour when trained with the standard approach. We investigate how varying the length of training sequences and utilising different target classes impacts model behaviour during training and the ability of linear RNN models to effectively approximate the indicator conditions.