# Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples

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

## Key facts

- Cited by 66 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2017.

## Built on by (most cited first, 30 of 66)

- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [Neuro-Symbolic Language Modeling with Automaton-augmented Retrieval](https://mlsanity.com/paper/2201.12431/) (2022)
- [Learning Transformer Programs](https://mlsanity.com/paper/2306.01128/) (2023)
- [Square One Bias in NLP: Towards a Multi-Dimensional Exploration of the Research Manifold](https://mlsanity.com/paper/2206.09755/) (2022)
- [Interpretability Illusions in the Generalization of Simplified Models](https://mlsanity.com/paper/2312.03656/) (2023)
- [Minimum Description Length Recurrent Neural Networks](https://mlsanity.com/paper/2111.00600/) (2021)
- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (2024)
- [SoK: Explainable Machine Learning for Computer Security Applications](https://mlsanity.com/paper/2208.10605/) (2022)
- [Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions](https://mlsanity.com/paper/2310.16076/) (2023)
- [BDD4BNN: A BDD-based Quantitative Analysis Framework for Binarized Neural Networks](https://mlsanity.com/paper/2103.07224/) (2021)
- [Extracting Finite Automata from RNNs Using State Merging](https://mlsanity.com/paper/2201.12451/) (2022)
- [Latent State Models of Training Dynamics](https://mlsanity.com/paper/2308.09543/) (2023)
- [Learning Useful Representations of Recurrent Neural Network Weight Matrices](https://mlsanity.com/paper/2403.11998/) (2024)
- [Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learning](https://mlsanity.com/paper/2107.04633/) (2021)
- [Learning Description Logic Ontologies. Five Approaches. Where Do They Stand?](https://mlsanity.com/paper/2104.01193/) (2021)
- [Learning Interpretable Temporal Properties from Positive Examples Only](https://mlsanity.com/paper/2209.02650/) (2022)
- [Extracting Weighted Finite Automata from Recurrent Neural Networks for Natural Languages](https://mlsanity.com/paper/2206.14621/) (2022)
- [On the Computational Complexity and Formal Hierarchy of Second Order Recurrent Neural Networks](https://mlsanity.com/paper/2309.14691/) (2023)
- [DeepDFA: Automata Learning through Neural Probabilistic Relaxations](https://mlsanity.com/paper/2408.08622/) (2024)
- [Linguistically inspired roadmap for building biologically reliable protein language models](https://mlsanity.com/paper/2207.00982/) (2022)
- [MLRegTest: A Benchmark for the Machine Learning of Regular Languages](https://mlsanity.com/paper/2304.07687/) (2023)
- [Weighted Automata Extraction and Explanation of Recurrent Neural Networks for Natural Language Tasks](https://mlsanity.com/paper/2306.14040/) (2023)
- [DeepSeer: Interactive RNN Explanation and Debugging via State Abstraction](https://mlsanity.com/paper/2303.01576/) (2023)
- [ReX: A Framework for Incorporating Temporal Information in Model-Agnostic Local Explanation Techniques](https://mlsanity.com/paper/2209.03798/) (2022)
- [Detecting Hidden Triggers: Mapping Non-Markov Reward Functions to Markov](https://mlsanity.com/paper/2401.11325/) (2024)
- [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)
- [On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach](https://mlsanity.com/paper/2510.04115/) (2025)
- [Extracting Weighted Automata for Approximate Minimization in Language Modelling](https://mlsanity.com/paper/2106.02965/) (2021)
- [Understanding Robust Generalization in Learning Regular Languages](https://mlsanity.com/paper/2202.09717/) (2022)

## Abstract (arXiv)

We present a novel algorithm that uses exact learning and abstraction to extract a deterministic finite automaton describing the state dynamics of a given trained RNN. We do this using Angluin's L* algorithm as a learner and the trained RNN as an oracle. Our technique efficiently extracts accurate automata from trained RNNs, even when the state vectors are large and require fine differentiation.