# Understanding Robust Generalization in Learning Regular Languages

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 37 references that are in the map.
- First posted on arXiv 20 Feb 2022.

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

- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [WILDS: A Benchmark of in-the-Wild Distribution Shifts](https://mlsanity.com/paper/2012.07421/) (2020)
- [Bridging Theory and Algorithm for Domain Adaptation](https://mlsanity.com/paper/1904.05801/) (2019)
- [Compositionality decomposed: how do neural networks generalise?](https://mlsanity.com/paper/1908.08351/) (2019)
- [COGS: A Compositional Generalization Challenge Based on Semantic Interpretation](https://mlsanity.com/paper/2010.05465/) (2020)
- [A survey on domain adaptation theory: learning bounds and theoretical guarantees](https://mlsanity.com/paper/2004.11829/) (2020)
- [A Benchmark for Systematic Generalization in Grounded Language Understanding](https://mlsanity.com/paper/2003.05161/) (2020)
- [Compositional generalization through meta sequence-to-sequence learning](https://mlsanity.com/paper/1906.05381/) (2019)
- [Compositional Generalization in Semantic Parsing: Pre-training vs. Specialized Architectures](https://mlsanity.com/paper/2007.08970/) (2020)
- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [Rearranging the Familiar: Testing Compositional Generalization in Recurrent Networks](https://mlsanity.com/paper/1807.07545/) (2018)
- [Recurrent Neural Networks as Weighted Language Recognizers](https://mlsanity.com/paper/1711.05408/) (2017)
- [CNNs found to jump around more skillfully than RNNs: Compositional generalization in seq2seq convolutional networks](https://mlsanity.com/paper/1905.08527/) (2019)
- [On Evaluating the Generalization of LSTM Models in Formal Languages](https://mlsanity.com/paper/1811.01001/) (2018)
- [A Survey of Neural Networks and Formal Languages](https://mlsanity.com/paper/2006.01338/) (2020)
- [*-CFQ: Analyzing the Scalability of Machine Learning on a Compositional Task](https://mlsanity.com/paper/2012.08266/) (2020)
- [Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning](https://mlsanity.com/paper/1807.01406/) (2018)
- [Representing Formal Languages: A Comparison Between Finite Automata and Recurrent Neural Networks](https://mlsanity.com/paper/1902.10297/) (2019)
- [Approximating probabilistic models as weighted finite automata](https://mlsanity.com/paper/1905.08701/) (2019)
- [PAC Learning Guarantees Under Covariate Shift](https://mlsanity.com/paper/1812.06393/) (2018)

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

- [What Makes Instruction Learning Hard? An Investigation and a New Challenge in a Synthetic Environment](https://mlsanity.com/paper/2204.09148/) (2022)
- [Is In-Context Learning Learning?](https://mlsanity.com/paper/2509.10414/) (2025)
- [On the Dynamics of Learning Time-Aware Behavior with Recurrent Neural Networks](https://mlsanity.com/paper/2306.07125/) (2023)

## Abstract (arXiv)

A key feature of human intelligence is the ability to generalize beyond the training distribution, for instance, parsing longer sentences than seen in the past. Currently, deep neural networks struggle to generalize robustly to such shifts in the data distribution. We study robust generalization in the context of using recurrent neural networks (RNNs) to learn regular languages. We hypothesize that standard end-to-end modeling strategies cannot generalize well to systematic distribution shifts and propose a compositional strategy to address this. We compare an end-to-end strategy that maps strings to labels with a compositional strategy that predicts the structure of the deterministic finite-state automaton (DFA) that accepts the regular language. We theoretically prove that the compositional strategy generalizes significantly better than the end-to-end strategy. In our experiments, we implement the compositional strategy via an auxiliary task where the goal is to predict the intermediate states visited by the DFA when parsing a string. Our empirical results support our hypothesis, showing that auxiliary tasks can enable robust generalization. Interestingly, the end-to-end RNN generalizes significantly better than the theoretical lower bound, suggesting that it is able to achieve at least some degree of robust generalization.