# MLRegTest: A Benchmark for the Machine Learning of Regular Languages

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 66 references that are in the map.
- First posted on arXiv 16 Apr 2023.

## Builds on (most cited first, 9 of 9)

- [Deep Learning in Neural Networks: An Overview](https://mlsanity.com/paper/1404.7828/) (2014)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions](https://mlsanity.com/paper/2211.12316/) (2022)
- [A Logic for Expressing Log-Precision Transformers](https://mlsanity.com/paper/2210.02671/) (2022)
- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [How Can Self-Attention Networks Recognize Dyck-n Languages?](https://mlsanity.com/paper/2010.04303/) (2020)
- [Sensitivity as a Complexity Measure for Sequence Classification Tasks](https://mlsanity.com/paper/2104.10343/) (2021)
- [Evaluating the Ability of LSTMs to Learn Context-Free Grammars](https://mlsanity.com/paper/1811.02611/) (2018)
- [Connecting Weighted Automata, Tensor Networks and Recurrent Neural Networks through Spectral Learning](https://mlsanity.com/paper/2010.10029/) (2020)

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

- [In-Context Language Learning: Architectures and Algorithms](https://mlsanity.com/paper/2401.12973/) (2024)
- [Exposing Attention Glitches with Flip-Flop Language Modeling](https://mlsanity.com/paper/2306.00946/) (2023)
- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (2024)
- [State space models can express n-gram languages](https://mlsanity.com/paper/2306.17184/) (2023)
- [Probability Distributions Computed by Autoregressive Transformers](https://mlsanity.com/paper/2510.27118/) (2025)
- [Correct and Optimal: the Regular Expression Inference Challenge](https://mlsanity.com/paper/2308.07899/) (2023)
- [Causally Evaluating the Learnability of Formal Language Tasks](https://mlsanity.com/paper/2606.09822/) (2026)

## Abstract (arXiv)

Synthetic datasets constructed from formal languages allow fine-grained examination of the learning and generalization capabilities of machine learning systems for sequence classification. This article presents a new benchmark for machine learning systems on sequence classification called MLRegTest, which contains training, development, and test sets from 1,800 regular languages. Different kinds of formal languages represent different kinds of long-distance dependencies, and correctly identifying long-distance dependencies in sequences is a known challenge for ML systems to generalize successfully. MLRegTest organizes its languages according to their logical complexity (monadic second order, first order, propositional, or monomial expressions) and the kind of logical literals (string, tier-string, subsequence, or combinations thereof). The logical complexity and choice of literal provides a systematic way to understand different kinds of long-distance dependencies in regular languages, and therefore to understand the capacities of different ML systems to learn such long-distance dependencies. Finally, the performance of different neural networks (simple RNN, LSTM, GRU, transformer) on MLRegTest is examined. The main conclusion is that performance depends significantly on the kind of test set, the class of language, and the neural network architecture.