mlsanityData to 7 Oct 2026

An Algebraic View of the Expressivity of Recurrent Language Models

arXiv 2606.01765 ↗First posted 1 Jun 2026cs.FL cs.CL cs.LGcited by 2

Not on the map. Why?

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.

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

Builds on

23 of 37 references.

References · 23

  1. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  2. 2021Evaluating Large Language Models Trained on Codecited by 8,053
  3. 2023Mamba: Linear-Time Sequence Modeling with Selective State Spacescited by 4,616
  4. 2017Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inferencecited by 1,548
  5. 2022Solving Quantitative Reasoning Problems with Language Modelscited by 1,359
  6. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  7. 2021I-BERT: Integer-only BERT Quantizationcited by 250
  8. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  9. 2024The Illusion of State in State-Space Modelscited by 181
  10. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  11. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  12. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 110
11 more
  1. 2024Unlocking State-Tracking in Linear RNNs Through Negative Eigenvaluescited by 97
  2. 2019Sequential Neural Networks as Automatacited by 54
  3. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 45
  4. 2019On the Computational Power of RNNscited by 35
  5. 2017Recurrent Neural Networks as Weighted Language Recognizerscited by 30
  6. 2020NITI: Training Integer Neural Networks Using Integer-only Arithmeticcited by 18
  7. 2025Bridging Expressivity and Scalability with Adaptive Unitary SSMscited by 8
  8. 2022Training Integer-Only Deep Recurrent Neural Networkscited by 5
  9. 2024Lower Bounds on the Expressivity of Recurrent Neural Language Modelscited by 4
  10. 2021iRNN: Integer-only Recurrent Neural Networkcited by 3
  11. 2023Monotonicity of Multi-Term Floating-Point Adderscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026The Rank the Task Demands: A Causal Rank Law for Matrix Memories Trained on Group Compositioncited by 1
  2. 2026A Compositional Theory of Causally Masked Transformerscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Why Depth Matters in Parallelizable Sequence Models: A Lie Algebraic View
  2. 2023Algebraic Dynamical Systems in Machine Learning
  3. 2024Autoregressive + Chain of Thought = Recurrent: Recurrence's Role in Language Models' Computability and a Revisit of Recurrent Transformer
  4. 2025Transformers are Inherently Succinct
  5. 2024Training Neural Networks as Recognizers of Formal Languages
  6. 2022Limitations of Language Models in Arithmetic and Symbolic Induction
  7. 2024Unraveling Arithmetic in Large Language Models: The Role of Algebraic Structures
  8. 2026Probing Structural Mathematical Reasoning in Language Models with Algebraic Trapdoors