An Algebraic View of the Expressivity of Recurrent Language Models
Franz Nowak, Reda Boumasmoud, Ryan Cotterell
Abstract
Recent progress in language model reasoning capabilities has revived a classic goal: characterizing which algorithms such systems can implement, or equivalently, which formal languages they can recognize. A growing research program studies RNNs, LSTMs, SSMs, and related architectures via reductions to finite-state automata and regular languages. Yet many results are not well-posed: they rely on implicit or incompatible semantic assumptions, invoking associativity and real-arithmetic techniques while also assuming floating-point arithmetic, which is finite and non-associative. Moreover, many proofs are highly architecture-specific and hard to transfer across closely related models. We address these issues with a unifying algebraic framework for a broad class of RNN language models, formally translating them to wreath products of transformation semigroups. By separating universal algebraic structure from contingent choices such as numerical semantics and wiring, the framework yields a disciplined workflow for rigorous expressivity analysis under realistic assumptions. We illustrate its value by rederiving and correcting representative expressivity claims from the literature under explicit deterministic finite-precision semantics.
BibTeX
@inproceedings{
nowak2026an,
title={An Algebraic View of the Expressivity of Recurrent Language Models},
author={Franz Nowak and Ryan Cotterell and Reda Boumasmoud},
booktitle={Forty-third International Conference on Machine Learning},
year={2026},
url={https://openreview.net/forum?id=7pbmZatDuD}
}