# Advancing Regular Language Reasoning in Linear Recurrent Neural Networks

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 22 references that are in the map.
- First posted on arXiv 14 Sep 2023.

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

- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [RWKV: Reinventing RNNs for the Transformer Era](https://mlsanity.com/paper/2305.13048/) (2023)
- [Simplified State Space Layers for Sequence Modeling](https://mlsanity.com/paper/2208.04933/) (2022)
- [Hungry Hungry Hippos: Towards Language Modeling with State Space Models](https://mlsanity.com/paper/2212.14052/) (2022)
- [Resurrecting Recurrent Neural Networks for Long Sequences](https://mlsanity.com/paper/2303.06349/) (2023)
- [Hyena Hierarchy: Towards Larger Convolutional Language Models](https://mlsanity.com/paper/2302.10866/) (2023)
- [Diagonal State Spaces are as Effective as Structured State Spaces](https://mlsanity.com/paper/2203.14343/) (2022)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Liquid Structural State-Space Models](https://mlsanity.com/paper/2209.12951/) (2022)
- [Parallelizing Linear Recurrent Neural Nets Over Sequence Length](https://mlsanity.com/paper/1709.04057/) (2017)
- [How to Train Your HiPPO: State Space Models with Generalized Orthogonal Basis Projections](https://mlsanity.com/paper/2206.12037/) (2022)

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

- [Gated Delta Networks: Improving Mamba2 with Delta Rule](https://mlsanity.com/paper/2412.06464/) (2024)
- [Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues](https://mlsanity.com/paper/2411.12537/) (2024)
- [DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products](https://mlsanity.com/paper/2502.10297/) (2025)
- [Structured Linear CDEs: Maximally Expressive and Parallel-in-Time Sequence Models](https://mlsanity.com/paper/2505.17761/) (2025)
- [Structured Sparse Transition Matrices to Enable State Tracking in State-Space Models](https://mlsanity.com/paper/2509.22284/) (2025)
- [Learning State-Tracking from Code Using Linear RNNs](https://mlsanity.com/paper/2602.14814/) (2026)
- [Revisiting Bi-Linear State Transitions in Recurrent Neural Networks](https://mlsanity.com/paper/2505.21749/) (2025)
- [On the "Induction Bias" in Sequence Models](https://mlsanity.com/paper/2602.18333/) (2026)
- [Length Generalization with Log-Depth Recurrent Units](https://mlsanity.com/paper/2605.26035/) (2026)
- [Chess-World-Model: A 10M-Game Benchmark for Exact State Tracking from Chess Move Sequences](https://mlsanity.com/paper/2605.30100/) (2026)
- [Improved state mixing in higher-order and block diagonal linear recurrent networks](https://mlsanity.com/paper/2602.12021/) (2026)
- [Flash PD-SSM: Memory-Optimized Structured Sparse State-Space Models](https://mlsanity.com/paper/2605.19150/) (2026)
- [Universal Time Series Generation with Neural Controlled Differential Equations](https://mlsanity.com/paper/2605.28507/) (2026)

## Abstract (arXiv)

In recent studies, linear recurrent neural networks (LRNNs) have achieved Transformer-level performance in natural language and long-range modeling, while offering rapid parallel training and constant inference cost. With the resurgence of interest in LRNNs, we study whether they can learn the hidden rules in training sequences, such as the grammatical structures of regular language. We theoretically analyze some existing LRNNs and discover their limitations in modeling regular language. Motivated by this analysis, we propose a new LRNN equipped with a block-diagonal and input-dependent transition matrix. Experiments suggest that the proposed model is the only LRNN capable of performing length extrapolation on regular language tasks such as Sum, Even Pair, and Modular Arithmetic. The code is released at urlhttps://github.com/tinghanf/RegluarLRNN.