# Memorize or generalize? Searching for a compositional RNN in a haystack

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

## Key facts

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

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

- [The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformers](https://mlsanity.com/paper/2108.12284/) (2021)
- [State-of-the-art generalisation research in NLP: A taxonomy and review](https://mlsanity.com/paper/2210.03050/) (2022)
- [Making Transformers Solve Compositional Tasks](https://mlsanity.com/paper/2108.04378/) (2021)
- [The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic Generalization](https://mlsanity.com/paper/2110.07732/) (2021)
- [Transformers in Time-series Analysis: A Tutorial](https://mlsanity.com/paper/2205.01138/) (2022)
- [On the proper role of linguistically-oriented deep net analysis in linguistic theorizing](https://mlsanity.com/paper/2106.08694/) (2021)
- [Pointer Value Retrieval: A new benchmark for understanding the limits of neural network generalization](https://mlsanity.com/paper/2107.12580/) (2021)
- [Compositional Capabilities of Autoregressive Transformers: A Study on Synthetic, Interpretable Tasks](https://mlsanity.com/paper/2311.12997/) (2023)
- [Inducing Transformer's Compositional Generalization Ability via Auxiliary Sequence Prediction Tasks](https://mlsanity.com/paper/2109.15256/) (2021)
- [Dissecting Chain-of-Thought: Compositionality through In-Context Filtering and Learning](https://mlsanity.com/paper/2305.18869/) (2023)
- [Improving Compositional Generalization in Classification Tasks via Structure Annotations](https://mlsanity.com/paper/2106.10434/) (2021)
- [Compositional Attention: Disentangling Search and Retrieval](https://mlsanity.com/paper/2110.09419/) (2021)
- [LogicInference: A New Dataset for Teaching Logical Inference to seq2seq Models](https://mlsanity.com/paper/2203.15099/) (2022)
- [CTL++: Evaluating Generalization on Never-Seen Compositional Patterns of Known Functions, and Compatibility of Neural Representations](https://mlsanity.com/paper/2210.06350/) (2022)
- [The Validity of Evaluation Results: Assessing Concurrence Across Compositionality Benchmarks](https://mlsanity.com/paper/2310.17514/) (2023)
- [Induced Natural Language Rationales and Interleaved Markup Tokens Enable Extrapolation in Large Language Models](https://mlsanity.com/paper/2208.11445/) (2022)
- [Monotonic Location Attention for Length Generalization](https://mlsanity.com/paper/2305.20019/) (2023)
- [Benchmarking GPT-4 on Algorithmic Problems: A Systematic Evaluation of Prompting Strategies](https://mlsanity.com/paper/2402.17396/) (2024)
- [Mutual Exclusivity Training and Primitive Augmentation to Induce Compositionality](https://mlsanity.com/paper/2211.15578/) (2022)
- [On the Interplay Between Fine-tuning and Composition in Transformers](https://mlsanity.com/paper/2105.14668/) (2021)
- [Iterative Decoding for Compositional Generalization in Transformers](https://mlsanity.com/paper/2110.04169/) (2021)
- [Visual Referential Games Further the Emergence of Disentangled Representations](https://mlsanity.com/paper/2304.14511/) (2023)
- [Does Entity Abstraction Help Generative Transformers Reason?](https://mlsanity.com/paper/2201.01787/) (2022)
- [Overcoming classic challenges for artificial neural networks by providing incentives and practice](https://mlsanity.com/paper/2410.10596/) (2024)
- [How Do Neural Sequence Models Generalize? Local and Global Context Cues for Out-of-Distribution Prediction](https://mlsanity.com/paper/2111.03108/) (2021)
- [Meta-Referential Games to Learn Compositional Learning Behaviours](https://mlsanity.com/paper/2207.08012/) (2022)
- [A Neural Rewriting System to Solve Algorithmic Problems](https://mlsanity.com/paper/2402.17407/) (2024)
- [Compositional learning of functions in humans and machines](https://mlsanity.com/paper/2403.12201/) (2024)
- [Attention-based Iterative Decomposition for Tensor Product Representation](https://mlsanity.com/paper/2406.01012/) (2024)
- [IWISDM: Assessing instruction following in multimodal models at scale](https://mlsanity.com/paper/2406.14343/) (2024)

## Abstract (arXiv)

Neural networks are very powerful learning systems, but they do not readily generalize from one task to the other. This is partly due to the fact that they do not learn in a compositional way, that is, by discovering skills that are shared by different tasks, and recombining them to solve new problems. In this paper, we explore the compositional generalization capabilities of recurrent neural networks (RNNs). We first propose the lookup table composition domain as a simple setup to test compositional behaviour and show that it is theoretically possible for a standard RNN to learn to behave compositionally in this domain when trained with standard gradient descent and provided with additional supervision. We then remove this additional supervision and perform a search over a large number of model initializations to investigate the proportion of RNNs that can still converge to a compositional solution. We discover that a small but non-negligible proportion of RNNs do reach partial compositional solutions even without special architectural constraints. This suggests that a combination of gradient descent and evolutionary strategies directly favouring the minority models that developed more compositional approaches might suffice to lead standard RNNs towards compositional solutions.