An Algebraic View of the Expressivity of Recurrent Language Models

• URL: http://arxiv.org/abs/2606.01765v2
• Date: Fri, 05 Jun 2026 15:53:13 GMT
• Title: An Algebraic View of the Expressivity of Recurrent Language Models
• Abstract summary: The paper develops a unified algebraic account of the expressivity of recurrent neural networks.<n>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.
• Score: 50.88598486616582
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Does My Embedding Reflect That $A = B$? Evaluating Mathematical Equivalence in Embedding Models [4.464113977291748]
  A single statement can take very different forms depending on what subfield it is framed in.<n>Current embedding models tend to group statements by the terminology used to make them instead of the underlying math.<n>We propose a contrastive approach to learning embeddings of mathematical text that focuses on aligning informal statements with different formalizations.
  arXiv  Detail & Related papers  (2026-06-22T21:37:58Z)
• Implicit Models: Expressive Power Scales with Test-Time Compute [17.808479563949074]
  Implicit models, an emerging model class, compute outputs by iterating a single parameter block to a fixed point.<n>We study this gap through a nonparametric analysis of expressive power.<n>We prove that for a broad class of implicit models, this process lets the model's expressive power scale with test-time compute.
  arXiv  Detail & Related papers  (2025-10-04T02:49:22Z)
• The Origins of Representation Manifolds in Large Language Models [52.68554895844062]
  We show that cosine similarity in representation space may encode the intrinsic geometry of a feature through shortest, on-manifold paths.<n>The critical assumptions and predictions of the theory are validated on text embeddings and token activations of large language models.
  arXiv  Detail & Related papers  (2025-05-23T13:31:22Z)
• Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
  We train and evaluate neural networks directly as binary classifiers of strings.<n>We provide results on a variety of languages across the Chomsky hierarchy for three neural architectures.<n>Our contributions will facilitate theoretically sound empirical testing of language recognition claims in future work.
  arXiv  Detail & Related papers  (2024-11-11T16:33:25Z)
• Lexinvariant Language Models [84.2829117441298]
  Token embeddings, a mapping from discrete lexical symbols to continuous vectors, are at the heart of any language model (LM) We study textitlexinvariantlanguage models that are invariant to lexical symbols and therefore do not need fixed token embeddings in practice. We show that a lexinvariant LM can attain perplexity comparable to that of a standard language model, given a sufficiently long context.
  arXiv  Detail & Related papers  (2023-05-24T19:10:46Z)
• Learning Algebraic Recombination for Compositional Generalization [71.78771157219428]
  We propose LeAR, an end-to-end neural model to learn algebraic recombination for compositional generalization. Key insight is to model the semantic parsing task as a homomorphism between a latent syntactic algebra and a semantic algebra. Experiments on two realistic and comprehensive compositional generalization demonstrate the effectiveness of our model.
  arXiv  Detail & Related papers  (2021-07-14T07:23:46Z)
• Do Neural Models Learn Systematicity of Monotonicity Inference in Natural Language? [41.649440404203595]
  We introduce a method for evaluating whether neural models can learn systematicity of monotonicity inference in natural language. We consider four aspects of monotonicity inferences and test whether the models can systematically interpret lexical and logical phenomena on different training/test splits.
  arXiv  Detail & Related papers  (2020-04-30T14:48:39Z)
• On the Linguistic Capacity of Real-Time Counter Automata [1.8072051868187933]
  We study the abilities of real-time counter machines as formal grammars. We show that counter languages are closed under complement, union, intersection, and many other common set operations. This work makes general contributions to the theory of formal languages that are of potential interest for understanding recurrent neural networks.
  arXiv  Detail & Related papers  (2020-04-15T03:37:47Z)
• Consistency of a Recurrent Language Model With Respect to Incomplete Decoding [67.54760086239514]
  We study the issue of receiving infinite-length sequences from a recurrent language model. We propose two remedies which address inconsistency: consistent variants of top-k and nucleus sampling, and a self-terminating recurrent language model.
  arXiv  Detail & Related papers  (2020-02-06T19:56:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.