# Rule Extrapolation in Language Models: A Study of Compositional Generalization on OOD Prompts

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 46 references that are in the map.
- First posted on arXiv 9 Sep 2024.

## Builds on (most cited first, 30 of 32)

- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Locating and Editing Factual Associations in GPT](https://mlsanity.com/paper/2202.05262/) (2022)
- [HuggingFace's Transformers: State-of-the-art Natural Language Processing](https://mlsanity.com/paper/1910.03771/) (2019)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [xLSTM: Extended Long Short-Term Memory](https://mlsanity.com/paper/2405.04517/) (2024)
- [Data Distributional Properties Drive Emergent In-Context Learning in Transformers](https://mlsanity.com/paper/2205.05055/) (2022)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Deep learning generalizes because the parameter-function map is biased towards simple functions](https://mlsanity.com/paper/1805.08522/) (2018)
- [Improving Dictionary Learning with Gated Sparse Autoencoders](https://mlsanity.com/paper/2404.16014/) (2024)
- [Investigating the Limitations of Transformers with Simple Arithmetic Tasks](https://mlsanity.com/paper/2102.13019/) (2021)
- [Sudden Drops in the Loss: Syntax Acquisition, Phase Transitions, and Simplicity Bias in MLMs](https://mlsanity.com/paper/2309.07311/) (2023)
- [Randomized Positional Encodings Boost Length Generalization of Transformers](https://mlsanity.com/paper/2305.16843/) (2023)
- [Tighter risk certificates for neural networks](https://mlsanity.com/paper/2007.12911/) (2020)
- [Same Pre-training Loss, Better Downstream: Implicit Bias Matters for Language Models](https://mlsanity.com/paper/2210.14199/) (2022)
- [Testing the General Deductive Reasoning Capacity of Large Language Models Using OOD Examples](https://mlsanity.com/paper/2305.15269/) (2023)
- [Does syntax need to grow on trees? Sources of hierarchical inductive bias in sequence-to-sequence networks](https://mlsanity.com/paper/2001.03632/) (2020)
- [The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning](https://mlsanity.com/paper/2304.05366/) (2023)
- [Visual Representation Learning Does Not Generalize Strongly Within the Same Domain](https://mlsanity.com/paper/2107.08221/) (2021)
- [Additive Decoders for Latent Variables Identification and Cartesian-Product Extrapolation](https://mlsanity.com/paper/2307.02598/) (2023)
- [Grokking of Hierarchical Structure in Vanilla Transformers](https://mlsanity.com/paper/2305.18741/) (2023)
- [Improving Transformer Models by Reordering their Sublayers](https://mlsanity.com/paper/1911.03864/) (2019)
- [Is SGD a Bayesian sampler? Well, almost](https://mlsanity.com/paper/2006.15191/) (2020)
- [Provably Learning Object-Centric Representations](https://mlsanity.com/paper/2305.14229/) (2023)
- [Provable Compositional Generalization for Object-Centric Learning](https://mlsanity.com/paper/2310.05327/) (2023)
- [Learning Universal Predictors](https://mlsanity.com/paper/2401.14953/) (2024)
- [Circuit Breaking: Removing Model Behaviors with Targeted Ablation](https://mlsanity.com/paper/2309.05973/) (2023)
- [Compositional Capabilities of Autoregressive Transformers: A Study on Synthetic, Interpretable Tasks](https://mlsanity.com/paper/2311.12997/) (2023)
- [On Provable Length and Compositional Generalization](https://mlsanity.com/paper/2402.04875/) (2024)
- [Position: Understanding LLMs Requires More Than Statistical Generalization](https://mlsanity.com/paper/2405.01964/) (2024)

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

- [From Isolation to Entanglement: When Do Interpretability Methods Identify and Disentangle Known Concepts?](https://mlsanity.com/paper/2512.15134/) (2025)
- [Out-of-distribution Tests Reveal Compositionality in Chess Transformers](https://mlsanity.com/paper/2510.20783/) (2025)

## Abstract (arXiv)

LLMs show remarkable emergent abilities, such as inferring concepts from presumably out-of-distribution prompts, known as in-context learning. Though this success is often attributed to the Transformer architecture, our systematic understanding is limited. In complex real-world data sets, even defining what is out-of-distribution is not obvious. To better understand the OOD behaviour of autoregressive LLMs, we focus on formal languages, which are defined by the intersection of rules. We define a new scenario of OOD compositional generalization, termed rule extrapolation. Rule extrapolation describes OOD scenarios, where the prompt violates at least one rule. We evaluate rule extrapolation in formal languages with varying complexity in linear and recurrent architectures, the Transformer, and state space models to understand the architectures' influence on rule extrapolation. We also lay the first stones of a normative theory of rule extrapolation, inspired by the Solomonoff prior in algorithmic information theory.