# Weighted Automata Extraction from Recurrent Neural Networks via Regression on State Spaces

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Apr 2019.

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

- [Formally Explaining Neural Networks within Reactive Systems](https://mlsanity.com/paper/2308.00143/) (2023)
- [Verifying Generalization in Deep Learning](https://mlsanity.com/paper/2302.05745/) (2023)
- [Extracting Weighted Finite Automata from Recurrent Neural Networks for Natural Languages](https://mlsanity.com/paper/2206.14621/) (2022)
- [On the Tractability of SHAP Explanations under Markovian Distributions](https://mlsanity.com/paper/2405.02936/) (2024)
- [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)
- [Simulating Weighted Automata over Sequences and Trees with Transformers](https://mlsanity.com/paper/2403.09728/) (2024)
- [Extracting Weighted Automata for Approximate Minimization in Language Modelling](https://mlsanity.com/paper/2106.02965/) (2021)
- [Verifying the Generalization of Deep Learning to Out-of-Distribution Domains](https://mlsanity.com/paper/2406.02024/) (2024)
- [Extracting Rules from Neural Networks with Partial Interpretations](https://mlsanity.com/paper/2204.00360/) (2022)
- [When are Local Queries Useful for Robust Learning?](https://mlsanity.com/paper/2210.06089/) (2022)
- [Automata Extraction from Transformers](https://mlsanity.com/paper/2406.05564/) (2024)
- [An L^* Algorithm for Deterministic Weighted Regular Languages](https://mlsanity.com/paper/2411.06228/) (2024)
- [Extracting Robust Register Automata from Neural Networks over Data Sequences](https://mlsanity.com/paper/2511.19100/) (2025)
- [Warm Starting State-Space Models with Automata Learning](https://mlsanity.com/paper/2603.05694/) (2026)
- [A Passive Online Technique for Learning Hybrid Automata from Input/Output Traces](https://mlsanity.com/paper/2101.07053/) (2021)
- [DeepCover: Advancing RNN Test Coverage and Online Error Prediction using State Machine Extraction](https://mlsanity.com/paper/2402.06966/) (2024)
- [PDFA Distillation via String Probability Queries](https://mlsanity.com/paper/2406.18328/) (2024)
- [Learning Weighted Finite Automata over the Max-Plus Semiring and its Termination](https://mlsanity.com/paper/2407.09775/) (2024)
- [Synthesis and Verification of Transformer Programs (Technical Report)](https://mlsanity.com/paper/2602.16473/) (2026)
- [From Transformers to Weighted Automata: Towards the Verification of Large Language Models](https://mlsanity.com/paper/2610.04569/) (2026)

## Abstract (arXiv)

We present a method to extract a weighted finite automaton (WFA) from a recurrent neural network (RNN). Our algorithm is based on the WFA learning algorithm by Balle and Mohri, which is in turn an extension of Angluin's classic lstar algorithm. Our technical novelty is in the use of regression methods for the so-called equivalence queries, thus exploiting the internal state space of an RNN to prioritize counterexample candidates. This way we achieve a quantitative/weighted extension of the recent work by Weiss, Goldberg and Yahav that extracts DFAs. We experimentally evaluate the accuracy, expressivity and efficiency of the extracted WFAs.