# Training Neural Networks as Recognizers of Formal Languages

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 38 of its 63 references that are in the map.
- First posted on arXiv 11 Nov 2024.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

## Builds on (most cited first, 30 of 38)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Learning Deep Transformer Models for Machine Translation](https://mlsanity.com/paper/1906.01787/) (2019)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Transformers without Tears: Improving the Normalization of Self-Attention](https://mlsanity.com/paper/1910.05895/) (2019)
- [Inductive Biases and Variable Creation in Self-Attention Mechanisms](https://mlsanity.com/paper/2110.10090/) (2021)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [Randomized Positional Encodings Boost Length Generalization of Transformers](https://mlsanity.com/paper/2305.16843/) (2023)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021)
- [In-Context Language Learning: Architectures and Algorithms](https://mlsanity.com/paper/2401.12973/) (2024)
- [On the Computational Power of Transformers and its Implications in Sequence Modeling](https://mlsanity.com/paper/2006.09286/) (2020)
- [Why are Sensitive Functions Hard for Transformers?](https://mlsanity.com/paper/2402.09963/) (2024)
- [Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions](https://mlsanity.com/paper/2211.12316/) (2022)
- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [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)
- [Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages](https://mlsanity.com/paper/2310.13897/) (2023)
- [LSTM Networks Can Perform Dynamic Counting](https://mlsanity.com/paper/1906.03648/) (2019)
- [A Measure-Theoretic Characterization of Tight Language Models](https://mlsanity.com/paper/2212.10502/) (2022)
- [Memory-Augmented Recurrent Neural Networks Can Learn Generalized Dyck Languages](https://mlsanity.com/paper/1911.03329/) (2019)
- [Transformers are uninterpretable with myopic methods: a case study with bounded Dyck grammars](https://mlsanity.com/paper/2312.01429/) (2023)
- [Separations in the Representational Capabilities of Transformers and Recurrent Architectures](https://mlsanity.com/paper/2406.09347/) (2024)
- [Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits](https://mlsanity.com/paper/2308.03212/) (2023)

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

- [Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biases](https://mlsanity.com/paper/2502.19249/) (2025)
- [Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers](https://mlsanity.com/paper/2502.02393/) (2025)
- [Characterizing the Expressivity of Fixed-Precision Transformer Language Models](https://mlsanity.com/paper/2505.23623/) (2025)
- [Information Locality as an Inductive Bias for Neural Language Models](https://mlsanity.com/paper/2506.05136/) (2025)
- [Learning State-Tracking from Code Using Linear RNNs](https://mlsanity.com/paper/2602.14814/) (2026)
- [Rethinking Addressing in Language Models via Contexualized Equivariant Positional Encoding](https://mlsanity.com/paper/2501.00712/) (2025)
- [Context-Free Recognition with Transformers](https://mlsanity.com/paper/2601.01754/) (2026)
- [Characterizing the Expressivity of Local Attention in Transformers](https://mlsanity.com/paper/2605.00768/) (2026)
- [PBEBench: A Multi-Step Programming by Examples Reasoning Benchmark inspired by Historical Linguistics](https://mlsanity.com/paper/2505.23126/) (2025)
- [A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networks](https://mlsanity.com/paper/2505.24110/) (2025)
- [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)
- [Randomly Sampled Language Reasoning Problems Elucidate Limitations of In-Context Learning](https://mlsanity.com/paper/2501.02825/) (2025)
- [RNN Generalization to Omega-Regular Languages](https://mlsanity.com/paper/2509.02491/) (2025)
- [Symbolic Feedforward Networks for Probabilistic Finite Automata: Exact Simulation and Learnability](https://mlsanity.com/paper/2509.10034/) (2025)
- [Bearing Syntactic Fruit with Stack-Augmented Neural Networks](https://mlsanity.com/paper/2511.03547/) (2025)
- [Length Generalization with Log-Depth Recurrent Units](https://mlsanity.com/paper/2605.26035/) (2026)
- [Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't](https://mlsanity.com/paper/2605.30523/) (2026)
- [Understanding the Parameter Space Geometry of Transformers Encoding Boolean Functions](https://mlsanity.com/paper/2606.08768/) (2026)
- [Prompting Robot Teams with Natural Language](https://mlsanity.com/paper/2509.24575/) (2025)
- [Evaluating the Formal Reasoning Capabilities of Large Language Models through Chomsky Hierarchy](https://mlsanity.com/paper/2604.02709/) (2026)
- [Causally Evaluating the Learnability of Formal Language Tasks](https://mlsanity.com/paper/2606.09822/) (2026)
- [Length Generalization for Transformers via Compression](https://mlsanity.com/paper/2609.08851/) (2026)
- [Training Dynamics of Transformers on Unbounded Inputs: Attention Learning Can Lag Output Layer Learning](https://mlsanity.com/paper/2610.20337/) (2026)

## Abstract (arXiv)

Characterizing the computational power of neural network architectures in terms of formal language theory remains a crucial line of research, as it describes lower and upper bounds on the reasoning capabilities of modern AI. However, when empirically testing these bounds, existing work often leaves a discrepancy between experiments and the formal claims they are meant to support. The problem is that formal language theory pertains specifically to recognizers: machines that receive a string as input and classify whether it belongs to a language. On the other hand, it is common instead to evaluate language models on proxy tasks, e.g., language modeling or sequence-to-sequence transduction, that are similar in only an informal sense to the underlying theory. We correct this mismatch by training and evaluating neural networks directly as binary classifiers of strings, using a general method that can be applied to a wide variety of languages. As part of this, we extend an algorithm recently proposed by Snaebjarnarson et al. (2025) for efficient length-controlled sampling of strings from regular languages. We provide results on a variety of languages across the Chomsky hierarchy for three neural architectures: a simple RNN, an LSTM, and a causally-masked transformer. We find that the RNN and LSTM often outperform the transformer, and that auxiliary training objectives such as language modeling can help, although no single objective uniformly improves performance across languages and architectures. Our contributions will facilitate theoretically sound empirical testing of language recognition claims in future work. We have released our datasets as a benchmark called FLaRe (Formal Language Recognition), along with our code.