mlsanityData to 14 Oct 2026

Lower Bounds on the Expressivity of Recurrent Neural Language Models

arXiv 2405.19222 ↗First posted 29 May 2024cs.CLcited by 4

Not on the map. Why?

Abstract (arXiv)

The recent successes and spread of large neural language models (LMs) call for a thorough understanding of their computational ability. Describing their computational abilities through LMs' representational capacity is a lively area of research. However, investigation into the representational capacity of neural LMs has predominantly focused on their ability to recognize formal languages. For example, recurrent neural networks (RNNs) with Heaviside activations are tightly linked to regular languages, i.e., languages defined by finite-state automata (FSAs). Such results, however, fall short of describing the capabilities of RNN language models (LMs), which are definitionally distributions over strings. We take a fresh look at the representational capacity of RNN LMs by connecting them to probabilistic FSAs and demonstrate that RNN LMs with linearly bounded precision can express arbitrary regular LMs.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 25 of its 64 references that are in the map. First posted on arXiv 29 May 2024.

Builds on

25 of 64 references.

References · 25

  1. 2014Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translationcited by 4,057
  2. 2021Convex optimizationcited by 2,515
  3. 2014On the Properties of Neural Machine Translation: Encoder-Decoder Approachescited by 1,304
  4. 2020Exploiting Cloze Questions for Few Shot Text Classification and Natural Language Inferencecited by 938
  5. 2016Error bounds for approximations with deep ReLU networkscited by 574
  6. 2014On the Number of Linear Regions of Deep Neural Networkscited by 381
  7. 2016From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classificationcited by 341
  8. 2016On the Expressive Power of Deep Neural Networkscited by 306
  9. 2017Breaking the Softmax Bottleneck: A High-Rank RNN Language Modelcited by 152
  10. 2017On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learningcited by 142
  11. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  12. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
13 more
  1. 2023Text Classification via Large Language Modelscited by 106
  2. 2017Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activationscited by 104
  3. 2013How to Construct Deep Recurrent Neural Networkscited by 64
  4. 2020A Formal Hierarchy of RNN Architecturescited by 62
  5. 2020RNNs can generate bounded hierarchical languages with optimal memorycited by 59
  6. 2019Sequential Neural Networks as Automatacited by 54
  7. 2019On the Computational Power of RNNscited by 35
  8. 2022A Measure-Theoretic Characterization of Tight Language Modelscited by 33
  9. 2018Rational Recurrencescited by 18
  10. 2020A Survey of Neural Networks and Formal Languagescited by 17
  11. 2022Extracting Finite Automata from RNNs Using State Mergingcited by 17
  12. 2018Context-Free Transductions with Neural Stackscited by 14
  13. 2022FETA: A Benchmark for Few-Sample Task Transfer in Open-Domain Dialoguecited by 11

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 0; 2026: 2.

4 papers.

  1. 2024On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoningcited by 26
  2. 2024Autoregressive + Chain of Thought = Recurrent: Recurrence's Role in Language Models' Computability and a Revisit of Recurrent Transformercited by 16
  3. 2026An Algebraic View of the Expressivity of Recurrent Language Modelscited by 2
  4. 2026Provably Shorter Scratchpads in Hybrid DeltaNet-Attention Decoderscited by 0