# An Algebraic View of the Expressivity of Recurrent Language Models

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 37 references that are in the map.
- First posted on arXiv 1 Jun 2026.

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

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inference](https://mlsanity.com/paper/1712.05877/) (2017)
- [Solving Quantitative Reasoning Problems with Language Models](https://mlsanity.com/paper/2206.14858/) (2022)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [I-BERT: Integer-only BERT Quantization](https://mlsanity.com/paper/2101.01321/) (2021)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues](https://mlsanity.com/paper/2411.12537/) (2024)
- [Sequential Neural Networks as Automata](https://mlsanity.com/paper/1906.01615/) (2019)
- [The Expressive Capacity of State Space Models: A Formal Language Perspective](https://mlsanity.com/paper/2405.17394/) (2024)
- [On the Computational Power of RNNs](https://mlsanity.com/paper/1906.06349/) (2019)
- [Recurrent Neural Networks as Weighted Language Recognizers](https://mlsanity.com/paper/1711.05408/) (2017)
- [NITI: Training Integer Neural Networks Using Integer-only Arithmetic](https://mlsanity.com/paper/2009.13108/) (2020)
- [Bridging Expressivity and Scalability with Adaptive Unitary SSMs](https://mlsanity.com/paper/2507.05238/) (2025)
- [Training Integer-Only Deep Recurrent Neural Networks](https://mlsanity.com/paper/2212.11791/) (2022)
- [Lower Bounds on the Expressivity of Recurrent Neural Language Models](https://mlsanity.com/paper/2405.19222/) (2024)
- [iRNN: Integer-only Recurrent Neural Network](https://mlsanity.com/paper/2109.09828/) (2021)
- [Monotonicity of Multi-Term Floating-Point Adders](https://mlsanity.com/paper/2304.01407/) (2023)

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

- [The Rank the Task Demands: A Causal Rank Law for Matrix Memories Trained on Group Composition](https://mlsanity.com/paper/2609.12259/) (2026)
- [A Compositional Theory of Causally Masked Transformers](https://mlsanity.com/paper/2607.26988/) (2026)

## Abstract (arXiv)

What formal languages can a recurrent neural language model recognize? Formal results in the literature conflict: some authors report Turing-completeness, while others show equivalence to regular languages. The reason for this discrepancy is that the underlying arithmetic model differs. The paper develops a unified algebraic account of the expressivity of recurrent neural networks, starting with a formal account of various arithmetic models. This account reduces expressivity to an algebraic question, e.g., whether a network's syntactic monoid divides a certain wreath product. As a case study, the paper revisits diagonal state-space models: the same architecture cannot implement an even-modulus counter once floating-point recurrences are enforced, yet realizes every even-modulus counter under unsigned-integer quantization.