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

arXiv: https://arxiv.org/abs/2406.04289 · HTML: https://mlsanity.com/paper/2406.04289/

## 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 (most cited first, 30 of 31)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Decoupled Weight Decay Regularization](https://mlsanity.com/paper/1711.05101/) (2017)
- [Probing Classifiers: Promises, Shortcomings, and Advances](https://mlsanity.com/paper/2102.12452/) (2021)
- [A Primer in BERTology: What we know about how BERT works](https://mlsanity.com/paper/2002.12327/) (2020)
- [OLMo: Accelerating the Science of Language Models](https://mlsanity.com/paper/2402.00838/) (2024)
- [Linguistic Knowledge and Transferability of Contextual Representations](https://mlsanity.com/paper/1903.08855/) (2019)
- [Assessing the Ability of LSTMs to Learn Syntax-Sensitive Dependencies](https://mlsanity.com/paper/1611.01368/) (2016)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Breaking the Softmax Bottleneck: A High-Rank RNN Language Model](https://mlsanity.com/paper/1711.03953/) (2017)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [A Formal Hierarchy of RNN Architectures](https://mlsanity.com/paper/2004.08500/) (2020)
- [RNNs can generate bounded hierarchical languages with optimal memory](https://mlsanity.com/paper/2010.07515/) (2020)
- [Sequential Neural Networks as Automata](https://mlsanity.com/paper/1906.01615/) (2019)
- [How Can Self-Attention Networks Recognize Dyck-n Languages?](https://mlsanity.com/paper/2010.04303/) (2020)
- [LSTM Networks Can Perform Dynamic Counting](https://mlsanity.com/paper/1906.03648/) (2019)
- [Examining the Inductive Bias of Neural Language Models with Artificial Languages](https://mlsanity.com/paper/2106.01044/) (2021)
- [On the Computational Power of RNNs](https://mlsanity.com/paper/1906.06349/) (2019)
- [Transformers Can Represent n-gram Language Models](https://mlsanity.com/paper/2404.14994/) (2024)
- [Rational Recurrences](https://mlsanity.com/paper/1808.09357/) (2018)
- [On Evaluating the Generalization of LSTM Models in Formal Languages](https://mlsanity.com/paper/1811.01001/) (2018)
- [Extracting Finite Automata from RNNs Using State Merging](https://mlsanity.com/paper/2201.12451/) (2022)
- [Context-Free Transductions with Neural Stacks](https://mlsanity.com/paper/1809.02836/) (2018)
- [Efficient Computation of Expectations under Spanning Tree Distributions](https://mlsanity.com/paper/2008.12988/) (2020)
- [Transparency at the Source: Evaluating and Interpreting Language Models With Access to the True Distribution](https://mlsanity.com/paper/2310.14840/) (2023)
- [The Role of n-gram Smoothing in the Age of Neural Networks](https://mlsanity.com/paper/2403.17240/) (2024)

## Built on by (most cited first, 20 of 20)

- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (2024)
- [Can Language Models Learn Typologically Implausible Languages?](https://mlsanity.com/paper/2502.12317/) (2025)
- [Anything Goes? A Crosslinguistic Study of (Im)possible Language Learning in LMs](https://mlsanity.com/paper/2502.18795/) (2025)
- [Learning curves theory for hierarchically compositional data with power-law distributed features](https://mlsanity.com/paper/2505.07067/) (2025)
- [Can Transformers Learn n-gram Language Models?](https://mlsanity.com/paper/2410.03001/) (2024)
- [Better Estimation of the Kullback--Leibler Divergence Between Language Models](https://mlsanity.com/paper/2504.10637/) (2025)
- [Training Bilingual LMs with Data Constraints in the Targeted Language](https://mlsanity.com/paper/2411.12986/) (2024)
- [Learning State-Tracking from Code Using Linear RNNs](https://mlsanity.com/paper/2602.14814/) (2026)
- [Scaling Laws and Representation Learning in Simple Hierarchical Languages: Transformers vs. Convolutional Architectures](https://mlsanity.com/paper/2505.07070/) (2025)
- [Which Word Orders Facilitate Length Generalization in LMs? An Investigation with GCG-Based Artificial Languages](https://mlsanity.com/paper/2510.12722/) (2025)
- [Context-Free Recognition with Transformers](https://mlsanity.com/paper/2601.01754/) (2026)
- [Is In-Context Learning Learning?](https://mlsanity.com/paper/2509.10414/) (2025)
- [Probability Distributions Computed by Autoregressive Transformers](https://mlsanity.com/paper/2510.27118/) (2025)
- [Hierarchical Latent Structures in Data Generation Process Unify Mechanistic Phenomena across Scale](https://mlsanity.com/paper/2603.06592/) (2026)
- [Randomly Sampled Language Reasoning Problems Elucidate Limitations of In-Context Learning](https://mlsanity.com/paper/2501.02825/) (2025)
- [From n-gram to Attention: How Model Architectures Learn and Propagate Bias in Language Modeling](https://mlsanity.com/paper/2505.12381/) (2025)
- [Rethinking Memorization Measures and their Implications in Large Language Models](https://mlsanity.com/paper/2507.14777/) (2025)
- [Fine-tuning vs. In-context Learning in Large Language Models: A Formal Language Learning Perspective](https://mlsanity.com/paper/2604.23267/) (2026)
- [What Kind of Language is Easy to Language-Model Under Curriculum Learning?](https://mlsanity.com/paper/2604.26844/) (2026)
- [Causally Evaluating the Learnability of Formal Language Tasks](https://mlsanity.com/paper/2606.09822/) (2026)

## 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.