An Algebraic View of the Expressivity of Recurrent Language Models

2026-06-08 · Source: cs.CL updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences · Depth: Expert, extended

Summary

This paper presents a unified algebraic framework for analyzing the expressivity of recurrent neural language models (RNNs), resolving conflicting formal results regarding their computational power. It demonstrates that the underlying arithmetic model, including finite precision and evaluation order, fundamentally determines an RNN's capabilities. The framework reduces expressivity questions to algebraic statements, such as whether a network's syntactic monoid divides a specific wreath product. A case study on diagonal state-space models (SSMs) shows that the same architecture cannot implement even-modulus counters with floating-point recurrences but can realize every even-modulus counter under unsigned-integer quantization. This highlights how discretization impacts an architecture's formal language recognition.

Key takeaway

For machine learning engineers designing or evaluating recurrent neural networks, you must rigorously define the arithmetic semantics and evaluation order. Your choice of floating-point versus unsigned-integer quantization directly impacts the model's formal language recognition capabilities, potentially enabling or preventing tasks like modular counting. Consider the algebraic implications of your numerical implementation choices.

Key insights

Arithmetic semantics fundamentally determines recurrent neural network expressivity and recognized formal languages.

Principles

• Arithmetic semantics is part of the object being analyzed.
• RNN expressivity reduces to algebraic divisibility statements.
• Discretization alters algebraic structure, not just approximates.

Method

Develops an algebraic account of RNNs, formalizing arithmetic models and reducing expressivity to monoid division within wreath products.

In practice

• Diagonal SSMs recognize parity with unsigned-integer quantization.
• Krohn–Rhodes decomposition decides language recognition impossibility.

Topics

• Recurrent Neural Networks
• Formal Languages
• Algebraic Automata Theory
• Arithmetic Semantics
• Floating-Point Arithmetic
• Unsigned Integer Quantization
• State Space Models

Best for: Research Scientist, AI Scientist, Machine Learning Engineer

Related on AIssential

• The Evolution of Language Modeling — Recurrent Neural Networks process variable-length sequential data using feedback loops and shared weights.
• BRo-JEPA: Learning Modular Arithmetic in Latent Space — Latent world models can learn symbolic rules if their architecture aligns with the problem's inherent structure.
• Expressivity of congruence-based architectures for DNNs on positive-definite matrices — Semi-orthogonality in congruence layers limits DNN expressivity for SPD matrix classification due to spectral diversity loss.
• A "Lay" Introduction to "On the Complexity of Neural Computation in Superposition" — Neural networks achieve representational efficiency through superposition, with specific computational complexity bounds.
• Associative-State Universal Transformers: Sparse Retrieval Meets Structured Recurrence — Structured recurrent states can be parameter-efficient for language modeling but require explicit sparse retrieval for exact long-range recall.
• Improved state mixing in higher-order and block diagonal linear recurrent networks — Richer state mixing in LRNNs enhances expressivity and efficiency for long-sequence modeling.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.CL updates on arXiv.org.