# Extracting Finite Automata from RNNs Using State Merging

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 27 references that are in the map.
- First posted on arXiv 28 Jan 2022.

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

- [On the Properties of Neural Machine Translation: Encoder-Decoder Approaches](https://mlsanity.com/paper/1409.1259/) (2014)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Opening the Black Box of Deep Neural Networks via Information](https://mlsanity.com/paper/1703.00810/) (2017)
- [Visualizing and Understanding Recurrent Networks](https://mlsanity.com/paper/1506.02078/) (2015)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [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)
- [Sequential Neural Networks as Automata](https://mlsanity.com/paper/1906.01615/) (2019)
- [Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descent](https://mlsanity.com/paper/2010.09697/) (2020)
- [An Empirical Evaluation of Rule Extraction from Recurrent Neural Networks](https://mlsanity.com/paper/1709.10380/) (2017)
- [Extracting Weighted Automata for Approximate Minimization in Language Modelling](https://mlsanity.com/paper/2106.02965/) (2021)

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

- [Transformers Can Represent n-gram Language Models](https://mlsanity.com/paper/2404.14994/) (2024)
- [Grokking phase transitions in learning local rules with gradient descent](https://mlsanity.com/paper/2210.15435/) (2022)
- [On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning](https://mlsanity.com/paper/2406.14197/) (2024)
- [Interpretability Illusions in the Generalization of Simplified Models](https://mlsanity.com/paper/2312.03656/) (2023)
- [What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languages](https://mlsanity.com/paper/2406.04289/) (2024)
- [DeepDFA: Automata Learning through Neural Probabilistic Relaxations](https://mlsanity.com/paper/2408.08622/) (2024)
- [Recurrent Neural Language Models as Probabilistic Finite-state Automata](https://mlsanity.com/paper/2310.05161/) (2023)
- [LUNA: A Model-Based Universal Analysis Framework for Large Language Models](https://mlsanity.com/paper/2310.14211/) (2023)
- [Simulating Weighted Automata over Sequences and Trees with Transformers](https://mlsanity.com/paper/2403.09728/) (2024)
- [Lower Bounds on the Expressivity of Recurrent Neural Language Models](https://mlsanity.com/paper/2405.19222/) (2024)
- [Critical Thinking: Which Kinds of Complexity Govern Optimal Reasoning Length?](https://mlsanity.com/paper/2504.01935/) (2025)
- [On Efficiently Representing Regular Languages as RNNs](https://mlsanity.com/paper/2402.15814/) (2024)
- [RNN Generalization to Omega-Regular Languages](https://mlsanity.com/paper/2509.02491/) (2025)
- [Extracting Robust Register Automata from Neural Networks over Data Sequences](https://mlsanity.com/paper/2511.19100/) (2025)
- [On the Relationship Between RNN Hidden State Vectors and Semantic Ground Truth](https://mlsanity.com/paper/2306.16854/) (2023)
- [Learning Model Successors](https://mlsanity.com/paper/2502.00197/) (2025)
- [Algorithm Development in Neural Networks: Insights from the Streaming Parity Task](https://mlsanity.com/paper/2507.09897/) (2025)

## Abstract (arXiv)

One way to interpret the behavior of a blackbox recurrent neural network (RNN) is to extract from it a more interpretable discrete computational model, like a finite state machine, that captures its behavior. In this work, we propose a new method for extracting finite automata from RNNs inspired by the state merging paradigm from grammatical inference. We demonstrate the effectiveness of our method on the Tomita languages benchmark, where we find that it is able to extract faithful automata from RNNs trained on all languages in the benchmark. We find that extraction performance is aided by the number of data provided during the extraction process, as well as, curiously, whether the RNN model is trained for additional epochs after perfectly learning its target language. We use our method to analyze this phenomenon, finding that training beyond convergence is useful because it leads to compression of the internal state space of the RNN. This finding demonstrates how our method can be used for interpretability and analysis of trained RNN models.