# Transformers Can Learn Rules They've Never Seen: Proof of Computation Beyond Interpolation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 22 references that are in the map.
- First posted on arXiv 17 Mar 2026.

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

- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Progress measures for grokking via mechanistic interpretability](https://mlsanity.com/paper/2301.05217/) (2023)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models](https://mlsanity.com/paper/2410.05229/) (2024)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Trained Transformers Learn Linear Models In-Context](https://mlsanity.com/paper/2306.09927/) (2023)
- [Reasoning or Reciting? Exploring the Capabilities and Limitations of Language Models Through Counterfactual Tasks](https://mlsanity.com/paper/2307.02477/) (2023)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Transformer Dissection: A Unified Understanding of Transformer's Attention via the Lens of Kernel](https://mlsanity.com/paper/1908.11775/) (2019)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Embers of Autoregression: Understanding Large Language Models Through the Problem They are Trained to Solve](https://mlsanity.com/paper/2309.13638/) (2023)
- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [Cellular automata as convolutional neural networks](https://mlsanity.com/paper/1809.02942/) (2018)
- [Everything, Everywhere, All at Once: Is Mechanistic Interpretability Identifiable?](https://mlsanity.com/paper/2502.20914/) (2025)
- [Initialization is Critical to Whether Transformers Fit Composite Functions by Reasoning or Memorizing](https://mlsanity.com/paper/2405.05409/) (2024)
- [Reconstructing cellular automata rules from observations at nonconsecutive times](https://mlsanity.com/paper/2012.02179/) (2020)
- [Learning with Boolean threshold functions](https://mlsanity.com/paper/2602.17493/) (2026)

## Abstract (arXiv)

A central question in the debate over large language models is whether transformers can learn rules they have never seen, or whether they can only interpolate: predict new cases from their similarity to training examples. We test this in a controlled setting where interpolation provably fails, so success can only come from computation beyond interpolation. We train small transformers to predict the rollout of a cellular automaton whose update rule is pure XOR, and remove one entry of the rule's truth table from all direct supervision. The missing entry's output is never shown to the model; its only trace is indirect, as wrong values corrupt visible predictions at later timesteps. Because XOR parity flips whenever one input bit is changed, every one-bit neighbour of the missing entry carries the opposite label, and we prove that similarity-based predictors, including nearest-neighbour, kernel, and Gaussian-process methods, are forced to the wrong answer. A two-layer transformer can nevertheless recover the missing entry, and circuit extraction confirms it computes XOR exactly. Ablations show the recovery depends on gradient signal propagating through multi-step prediction, and a second, structurally unrelated benchmark on symbolic operator chains exhibits the same capacity under ordinary autoregressive training. Together with a constructive proof that a standard transformer block can implement exact local Boolean rules, these results provide an existence proof that transformers can learn rule structure not directly observed in training and express it explicitly. This rules out the strongest architectural form of the interpolation-only account, the claim that transformers cannot in principle discover and communicate unseen rules, while leaving open when such behaviour arises in large-scale language training.