An Algebraic View of the Expressivity of Recurrent Language Models

arXiv:2606.01765 · cs.FL, cs.CL, cs.LG · Submitted 2026-06-01 · Read on arXiv

cs.FL, cs.CL, cs.LG

Submitted: 2026-06-01

Updated: 2026-08-25

Comments: Accepted at the 43rd International Conference on Machine Learning (ICML 2026). 28 pages, 2 figures

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Core — 100× in this paper · explained in 2 episodes
• Quantization — 9× in this paper · explained in 13 episodes
• Abstraction — 6× in this paper · explained in 1 episode
• Transformer — 6× in this paper · explained in 2 episodes
• Adam — 1× in this paper · explained in 2 episodes
• Adaptation — 1× in this paper · explained in 1 episode
• Algebraic Invariants — 1× in this paper
• Chain-of-Thought Prompting — 1× in this paper · explained in 2 episodes
• Empirical Methods in Natural Language Processing — 1× in this paper

Sources

• iRNN: Integer-only Recurrent Neural Network
• GPT-4 Technical Report

Related papers

• Positive-Data Learning of Fixed-Observation Linear MCFGs from Working Binary Presentations