Research map / Large language models / Language, safety and interpretability
Rule Extrapolation in Language Modeling: A Study of Compositional Generalization on OOD Prompts
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Evaluates rule extrapolation (completing OOD prompts that violate one of two intersected rules) across formal languages with linear, LSTM, Transformer, Mamba and xLSTM models, and proposes an uncomputable Solomonoff-inspired normative prior for OOD prompt completion.
Problem
Understanding how autoregressive language models behave on out-of-distribution prompts that have zero probability under the training distribution, specifically whether they extrapolate individual rules when a prompt violates one rule of a conjunction of rules.
Approach
Defines rule extrapolation as OOD compositional generalization on formal languages defined by the intersection of two rules, compares architectures (linear, LSTM, Transformer, Mamba, xLSTM) empirically, and proposes a non-parametric Solomonoff-style prior with prompt-conditioned completion as a normative theory.
Key results
- On L3 (a^nb^n), the Transformer extrapolated rule R1 to 66% OOD accuracy versus 38% for LSTM and 30% for Mamba.
- On the regular language L1, the LSTM achieved the best OOD R1 accuracy of 0.862 while the Transformer was below chance in-distribution (0.393).
- On L5 (a^nb^nc^n), the Transformer reached 0.980 OOD R1 accuracy, the best among the evaluated models.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LSTM instead of Transformer | Rule extrapolation models · L1 and L2 regular languages | OOD R1 accuracy | Helped |
| Use Transformer instead of LSTM | Rule extrapolation models · L3 context-free language | OOD R1 accuracy: 0.376 ± 0.209 -> 0.657 ± 0.162 | Helped |
| Use Transformer instead of LSTM | Rule extrapolation models · L4 Dyck language | OOD R1 accuracy: 0.543 ± 0.282 -> 0.980 ± 0.090 | Helped |
| Use Transformer instead of LSTM | Rule extrapolation models · L5 context-sensitive language | OOD R1 accuracy: 0.068 ± 0.036 -> 0.187 ± 0.085 | Helped |
| Use Transformer instead of LSTM | Rule extrapolation models · L6 context-sensitive Dyck | OOD R1 accuracy: 1.000 ± 0.000 vs 0.980 ± 0.045 | Mixed |
| Increase Transformer size by varying the number of layers and heads (ablation) | Transformer · Regular languages L1 and L2 | rule extrapolation accuracy | No clear effect |
Surprising findings
- Transformers performed below chance on in-distribution rule R1 for the regular language L1 despite similar test loss to LSTM and Mamba.
- Linear model achieved perfect R2 accuracy on some tasks only because it predicts EOS on test prompts.
Limitations
- Experiments limited to small synthetic formal languages far from natural language.
- Hyperparameter search and architecture variants (attention, positional encoding) not exhaustively explored.
- Normative Solomonoff-based prior is uncomputable and only informally connected to empirical results.
Experimental setup
Datasets: synthetic formal language samples for L1-L5
Benchmarks: rule extrapolation test prompts on L1-L6 formal languages
Metrics: test loss ID and OOD rule accuracy (R1/R2) chance level accuracy
Baselines: LSTM Transformer Mamba xLSTM Linear model human pilot study
Builds on: Solomonoff prior Mamba xLSTM Chomsky hierarchy
Closest papers by meaning
- Connecting the Dots: LLMs can Infer and Verbalize Latent Structure from Disparate Training Data (NeurIPS 2024 · similarity 0.86)
- Extrapolation by Association: Length Generalization Transfer In Transformers (NeurIPS 2025 · similarity 0.86)
- In-Context Learning Dynamics with Random Binary Sequences (ICLR 2024 · similarity 0.85)
- Quantifying Language Models' Sensitivity to Spurious Features in Prompt Design or: How I learned to start worrying about prompt formatting (ICLR 2024 · similarity 0.85)
- Task Generalization with Autoregressive Compositional Structure: Can Learning from $D$ Tasks Generalize to $D^T$ Tasks? (ICML 2025 · similarity 0.85)
- Reasoning Cache: Continual Improvement Over Long Horizons via Short-Horizon RL (ICML 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.