An Algebraic View of the Expressivity of Recurrent Language Models

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.

Neural language models are the AI systems behind tools like ChatGPT, trained to predict and produce text. They can answer questions and assist with work through multi-step problems, which raises a basic question: what can such systems do, and what lies beyond their reach? One way to make this concrete is to ask which patterns a model can reliably detect in a sequence of symbols, however long the sequence. The patterns a machine can track are a measure of how powerful it is. For one common type of model, which reads its input one piece at a time, like a sentence word by word, researchers have reached opposite conclusions: some find these models extraordinarily powerful, others sharply limited. The paper shows that the disagreement comes down to an overlooked detail: how the computer running the model handles numbers. Computers store and round numbers in different ways, and that choice quietly changes what the model can and cannot do. The paper develops a single, general way of analyzing these models that makes the role of this choice precise, turning a difficult question about neural networks into a clean question in algebra, the branch of mathematics concerned with abstract symmetry and structure. To illustrate, the paper examines one popular model design under two ways of handling numbers. When numbers are stored in the usual approximate way computers use for decimals, the model cannot keep a running count and report whether it is even. When the very same model stores numbers as exact whole numbers, it can. Same model, different number system, opposite outcome.