# Rational Recurrences

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Aug 2018.

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

- [Parallelizing Linear Transformers with the Delta Rule over Sequence Length](https://mlsanity.com/paper/2406.06484/) (2024)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [Neuro-Symbolic Language Modeling with Automaton-augmented Retrieval](https://mlsanity.com/paper/2201.12431/) (2022)
- [ABC: Attention with Bounded-memory Control](https://mlsanity.com/paper/2110.02488/) (2021)
- [Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits](https://mlsanity.com/paper/2308.03212/) (2023)
- [Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions](https://mlsanity.com/paper/2310.16076/) (2023)
- [What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languages](https://mlsanity.com/paper/2406.04289/) (2024)
- [A Call for Clarity in Beam Search: How It Works and When It Stops](https://mlsanity.com/paper/2204.05424/) (2022)
- [Formal Language Theory Meets Modern NLP](https://mlsanity.com/paper/2102.10094/) (2021)
- [Why Are Linear RNNs More Parallelizable?](https://mlsanity.com/paper/2603.03612/) (2026)
- [The Surprising Computational Power of Nondeterministic Stack RNNs](https://mlsanity.com/paper/2210.01343/) (2022)
- [Recurrent Neural Language Models as Probabilistic Finite-state Automata](https://mlsanity.com/paper/2310.05161/) (2023)
- [Lower Bounds on the Expressivity of Recurrent Neural Language Models](https://mlsanity.com/paper/2405.19222/) (2024)
- [Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcs](https://mlsanity.com/paper/2301.06862/) (2023)
- [Interpretable Predictive Models for Healthcare via Rational Logistic Regression](https://mlsanity.com/paper/2411.03224/) (2024)
- [Aligning Brain Activity with Advanced Transformer Models: Exploring the Role of Punctuation in Semantic Processing](https://mlsanity.com/paper/2501.06278/) (2025)
- [Learning Transductions and Alignments with RNN Seq2seq Models](https://mlsanity.com/paper/2303.06841/) (2023)

## Abstract (arXiv)

Despite the tremendous empirical success of neural models in natural language processing, many of them lack the strong intuitions that accompany classical machine learning approaches. Recently, connections have been shown between convolutional neural networks (CNNs) and weighted finite state automata (WFSAs), leading to new interpretations and insights. In this work, we show that some recurrent neural networks also share this connection to WFSAs. We characterize this connection formally, defining rational recurrences to be recurrent hidden state update functions that can be written as the Forward calculation of a finite set of WFSAs. We show that several recent neural models use rational recurrences. Our analysis provides a fresh view of these models and facilitates devising new neural architectures that draw inspiration from WFSAs. We present one such model, which performs better than two recent baselines on language modeling and text classification. Our results demonstrate that transferring intuitions from classical models like WFSAs can be an effective approach to designing and understanding neural models.