An Algebraic View of the Expressivity of Recurrent Language Models
Provides a rigorous algebraic account to clarify expressivity results for recurrent neural language models, addressing a foundational confusion in the field.
The paper resolves conflicting claims about the expressivity of recurrent language models by developing a unified algebraic framework, showing that expressivity depends on the underlying arithmetic model—e.g., diagonal state-space models can implement even-modulus counters under unsigned-integer quantization but not with floating-point recurrences.
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.