mlsanityData to 14 Oct 2026

What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languages

arXiv 2406.04289 ↗First posted 6 Jun 2024cs.CLcited by 20

Not on the map. Why?

Abstract (arXiv)

What can large language models learn? By definition, language models (LM) are distributions over strings. Therefore, an intuitive way of addressing the above question is to formalize it as a matter of learnability of classes of distributions over strings. While prior work in this direction focused on assessing the theoretical limits, in contrast, we seek to understand the empirical learnability. Unlike prior empirical work, we evaluate neural LMs on their home turf-learning probabilistic languages-rather than as classifiers of formal languages. In particular, we investigate the learnability of regular LMs (RLMs) by RNN and Transformer LMs. We empirically test the learnability of RLMs as a function of various complexity parameters of the RLM and the hidden state size of the neural LM. We find that the RLM rank, which corresponds to the size of linear space spanned by the logits of its conditional distributions, and the expected length of sampled strings are strong and significant predictors of learnability for both RNNs and Transformers. Several other predictors also reach significance, but with differing patterns between RNNs and Transformers.

Key facts. Cited by 20 papers in the map (data through 14 Oct 2026). Builds on 31 of its 61 references that are in the map. First posted on arXiv 6 Jun 2024.

Builds on

31 of 61 references.

References · 31

  1. 2017Attention Is All You Needcited by 60,361
  2. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  3. 2017Decoupled Weight Decay Regularizationcited by 1,831
  4. 2021Probing Classifiers: Promises, Shortcomings, and Advancescited by 876
  5. 2020A Primer in BERTology: What we know about how BERT workscited by 815
  6. 2024OLMo: Accelerating the Science of Language Modelscited by 613
  7. 2019Linguistic Knowledge and Transferability of Contextual Representationscited by 383
  8. 2016Assessing the Ability of LSTMs to Learn Syntax-Sensitive Dependenciescited by 354
  9. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 294
  10. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
  11. 2022Neural Networks and the Chomsky Hierarchycited by 217
  12. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 193
19 more
  1. 2017Breaking the Softmax Bottleneck: A High-Rank RNN Language Modelcited by 152
  2. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  3. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  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. 2020How Can Self-Attention Networks Recognize Dyck-n Languages?cited by 51
  8. 2019LSTM Networks Can Perform Dynamic Countingcited by 45
  9. 2021Examining the Inductive Bias of Neural Language Models with Artificial Languagescited by 40
  10. 2019On the Computational Power of RNNscited by 35
  11. 2024Transformers Can Represent n-gram Language Modelscited by 32
  12. 2018Rational Recurrencescited by 18
  13. 2018On Evaluating the Generalization of LSTM Models in Formal Languagescited by 17
  14. 2022Extracting Finite Automata from RNNs Using State Mergingcited by 17
  15. 2018Context-Free Transductions with Neural Stackscited by 14
  16. 2020Efficient Computation of Expectations under Spanning Tree Distributionscited by 11
  17. 2023Transparency at the Source: Evaluating and Interpreting Language Models With Access to the True Distributioncited by 10
  18. 2024The Role of n-gram Smoothing in the Age of Neural Networkscited by 6
  19. 2023Evaluating Transformer's Ability to Learn Mildly Context-Sensitive Languagescited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 11; 2026: 6.

20 papers.

Sort:

By area:

  1. 2024Training Neural Networks as Recognizers of Formal Languagescited by 24
  2. 2025Can Language Models Learn Typologically Implausible Languages?cited by 23
  3. 2025Anything Goes? A Crosslinguistic Study of (Im)possible Language Learning in LMscited by 20
  4. 2025Learning curves theory for hierarchically compositional data with power-law distributed featurescited by 17
  5. 2024Can Transformers Learn n-gram Language Models?cited by 11
  6. 2025Better Estimation of the Kullback--Leibler Divergence Between Language Modelscited by 11
  7. 2024Training Bilingual LMs with Data Constraints in the Targeted Languagecited by 6
  8. 2026Learning State-Tracking from Code Using Linear RNNscited by 6
  9. 2025Scaling Laws and Representation Learning in Simple Hierarchical Languages: Transformers vs. Convolutional Architecturescited by 5
  10. 2025Which Word Orders Facilitate Length Generalization in LMs? An Investigation with GCG-Based Artificial Languagescited by 4
  11. 2026Context-Free Recognition with Transformerscited by 4
  12. 2025Is In-Context Learning Learning?cited by 2
8 more
  1. 2025Probability Distributions Computed by Autoregressive Transformerscited by 2
  2. 2026Hierarchical Latent Structures in Data Generation Process Unify Mechanistic Phenomena across Scalecited by 2
  3. 2025Randomly Sampled Language Reasoning Problems Elucidate Limitations of In-Context Learningcited by 1
  4. 2025From n-gram to Attention: How Model Architectures Learn and Propagate Bias in Language Modelingcited by 1
  5. 2025Rethinking Memorization Measures and their Implications in Large Language Modelscited by 1
  6. 2026Fine-tuning vs. In-context Learning in Large Language Models: A Formal Language Learning Perspectivecited by 1
  7. 2026What Kind of Language is Easy to Language-Model Under Curriculum Learning?cited by 0
  8. 2026Causally Evaluating the Learnability of Formal Language Taskscited by 0