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

Andy Gray

cs.LGMar 17, 2026

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

Authors: Andy Gray

Organizations: Kortical

Abstract

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.

Figures & tables

Figure 1: Experimental setup. A CA evolves from a random initial state (

t=0

). At each subsequent timestep, positions where hidden patterns occur (red) receive no supervision. Visible positions (green) provide training signal. Wrong hidden-pattern predictions at

t+1

cascade into errors at visible positions at

t+2

, providing indirect gradient signal.

Figure 2: Interpolation accuracy across five representation levels for Rule 150. Input space: provably 0% (Results 1 – 5 ). Neighbourhood embeddings: empirically 0%, with a fixed-position proof extension in Appendix A.1 . After transformer layers: 94–100%. The XOR function is constructed de novo by computation.

Representation Level	KNN	GP	RBF SVM	RF	Transformer
Input space (3-bit)	0	0	0	0	96.8
Nbhd. embedding (192-d)	0	0	0	0	96.8
Single-pos. embedding (64-d)	34–42	5–27	0	0	96.8
Single-pos. hidden (64-d)	0–100	0–100	0–100	94–100	96.8
Nbhd. hidden (192-d)	72–100	0–100	0–100	95–100	96.8

Table 1: Interpolation accuracy (%) across five representation levels for Rule 150. Results summarize the six transformer runs achieving

\geq

95% holdout accuracy.

Experiment	Mean	95% CI	Successes
Rule D $k$ =8 (soft)	96.7%	[94.1, 99.2]	10/10
Rule G $k$ =8 (soft)	99.5%	[99.2, 99.7]	10/10
Rule D $k$ =8 (hard/STE)	65.5%	[59.2, 71.9]	1/10
Rule 150 (soft, 220 ep.; initially failed patterns)	71.5%	[61.6, 81.4]	47/60
Rule 150 (soft, 50 ep.; all 8 patterns)	10.6%	[4.1, 17.1]	8/80
Rule D $k$ =8, no unrolling (1 step)	63.1%	[62.7, 63.5]	0/10

Table 2: Mean holdout accuracy across seeds (95% CI). Outcomes are bimodal; the mean reflects the fraction of seeds that succeed.

Figure 3: Causal substitution test for the symbolic benchmark. (a) Surgical input replacement: changing $(c,d)$ to values consistent with a different operator flips op 2 while preserving op 1 ; changing $(a,b)$ flips op 1 while preserving op 2 . (b) Systematic results over 200 base examples per target operator confirm a clean double dissociation.

Holdout	Full (familiar)	Full (opaque)	Label-only
ˆ \|	73.2 $\pm$ 2.0	73.0 $\pm$ 5.1	29.1 $\pm$ 0.8
&L	55.3 $\pm$ 3.9	65.9 $\pm$ 1.9	14.5 $\pm$ 2.5
R ˆ	28.2 $\pm$ 6.6	24.6 $\pm$ 7.0	6.1 $\pm$ 3.2
d\|	54.4 $\pm$ 17.7	56.3 $\pm$ 14.2	33.3 $\pm$ 9.8

Table 3: Symbolic benchmark: test-set holdout accuracy (%) averaged over 3 seeds, for the held-out operator pair named in each row (ˆ = XOR, | = OR, & = AND, d = NAND, L = LSHIFT, R = RSHIFT). Baselines: KNN = 0%, MLP (multilayer perceptron) = 0%, KRR = 0–18.2%, Oracle = 100%. Full details in Appendix F .

Appendix figures & tables21 assets

Supplementary material from the paper’s appendix.

Appendix

Model	$c_{0}$	$c_{L}$	$c_{C}$	$c_{R}$	$c_{LC}$	$c_{LR}$	$c_{CR}$	$c_{LCR}$
Seed 4444	$-5.89$	$11.82$	$7.13$	$11.63$	$-19.28$	$-23.60$	$-18.91$	$42.88$
Seed 456	$-6.50$	$12.59$	$8.26$	$12.91$	$-20.39$	$-25.27$	$-21.11$	$46.14$

Appendix

Table 7

Layer Ablated	Seed 4444	Seed 456
Layer 0	20.5% (79.5% drop)	13.1% (86.9% drop)
Layer 1	0.0% (100% drop)	0.0% (100% drop)

Appendix

Table 8

Layer	Seed 4444	Seed 456
Embedding	1.2%	2.7%
After layer 0	0.0%	0.0%
After layer 1	100.0%	100.0%

Appendix

Table 9

Layer	Left	Centre	Right	XOR
Embedding	51.6%	100.0%	51.5%	51.6%
After layer 0	75.4%	100.0%	75.3%	56.8%
After layer 1	76.8%	99.2%	75.8%	98.4%

Appendix

Table 10

Patch Point	Seed 4444 Recovery	Seed 456 Recovery
Embedding	98.6%	98.6%
After layer 0	98.6%	100.0%
After layer 1	100.0%	100.0%

Appendix

Table 11

Method	Hidden Pattern [2]	Hidden Pattern [5]
Random Forest (500 trees)	0.2%	0.4%
Random Forest (100 trees)	8.4%	11.8%
KNN ( $k$ =1)	42.5%	42.1%
KNN ( $k$ =5)	36.2%	36.1%

Appendix

Table 12

Figure 4: Mean holdout accuracy vs. fraction of hidden patterns for Rule D and Rule G. Rule D shows a sharp cliff at

\sim

50% hidden; Rule G degrades gradually, tolerating 88% hidden. The frontier depends on intrinsic rule complexity.

$k$	Hidden %	Mean Accuracy	Successes
4	12%	99.4%	10/10
8	25%	96.7%	10/10
10	31%	99.6%	10/10
12	38%	99.6%	10/10
14	44%	99.8%	10/10
16	50%	55.3%	0/10

Appendix

Table 4: Rule D

k

-sweep (soft unrolling, 50 epochs, 10 seeds each).

$k$	Hidden %	Mean Accuracy	Successes
14	44%	99.3%	10/10
16	50%	99.2%	10/10
20	62%	99.2%	10/10
24	75%	97.1%	10/10
26	81%	81.3%	7/10
27	84%	95.7%	9/10

Appendix

Table 5: Rule G

k

-sweep (soft unrolling, 50 epochs, 10 seeds each).

Rule	Formula	Seeds	Mean Acc.	Successes
Rule D	$L_{1}\oplus((C\lor R_{1})\land(L_{2}\lor R_{2}))$	10	96.7%	10/10
Rule G	$(L_{1}\oplus(C\lor R_{1}))\lor(L_{2}\land R_{2})$	10	99.5%	10/10

Appendix

Table 6: Radius-2 rules (

k

=8 of 32 hidden). All use soft unrolling, 50 epochs.

	50 epochs			220 epochs
Pattern	Rule 150	Rule 30	Rule 106	Rule 150
0	0/10	1/10	10/10	3/10
1	0/10	5/10	10/10	10/10
2	4/10	6/10	0/10	—
3	0/10	10/10	8/10	10/10
4	0/10	0/10	9/10	10/10

Appendix

Table 7: Per-pattern holdout accuracy for radius-1 rules (

k

=1 of 8 hidden, 10 seeds each). Cells show seeds achieving

{\geq}70\%

holdout accuracy out of 10. Rule 150 (220 ep) excludes patterns 2 and 5, which partially succeeded at 50 epochs and were not re-run.

Pattern	3-NN vote	Successes	Best holdout
0	wrong	0/10	0.0%
1	wrong	2/10	100.0%
2	wrong	4/10	100.0%
3	correct	5/10	100.0%
4	wrong	0/10	36.2%
5	wrong	2/10	89.4%

Appendix

Table 8: Rule 30 with hard/STE unrolling (50 epochs, 10 seeds per pattern). Successes are seeds achieving

{\geq}70\%

holdout accuracy. The 3-NN column states whether a 3-nearest-neighbour majority vote over the other seven patterns predicts the held-out pattern’s label correctly; for the six patterns where it is wrong, recovery cannot be attributed to similarity-based interpolation.

Timesteps	Identifiability	Mean Unknowns	Mean Constraints	Mean Rank
1	0%	12.5	0.0	0.0
2	100%	12.5	31.4	12.5
3	100%	12.5	58.8	12.5
4	100%	12.5	101.2	12.5

Appendix

Table 19

Holdout	Seed	Full (familiar)	Full (opaque)	Label-only
ˆ \|	42	70.4	66.0	28.0
	123	74.0	78.2	29.6
	456	75.2	74.8	29.6
	Mean	73.2 $\pm$ 2.0	73.0 $\pm$ 5.1	29.1 $\pm$ 0.8
&L	42	50.8	67.6	13.0
	123	60.2	66.8	18.0

Appendix

Table 9: Test-set holdout accuracy (%) per seed across all conditions. Each cell reports accuracy on a held-out test set, evaluated at the best checkpoint (selected by peak eval-set performance).

Holdout	Transformer	KRR	Oracle	Learned Tables
ˆ \|	73.2	13.8	100	100
ˆ r	53.4	11.8	100	99.6
&L	55.3	0.2	100	99.2
d\|	54.4	3.2	100	99.8
R ˆ	28.2	7.2	100	99.8
\|&	12.3	0.4	100	100

Appendix

Table 10: Baseline holdout accuracy (%) for seven representative holdouts. All 49 pairs were evaluated: KNN and MLP achieve exactly 0% on every holdout; KRR ranges from 0% to 18.2% (mean 4.3%), highest when XOR is the first operator.

	Op 1 accuracy		Op 2 accuracy
Holdout	Pos 0 ( $a$ )	Pos 1 ( $b$ )	Pos 3 ( $d$ )	Pos 4 ( $u$ )
ˆ \|	63.9	61.7	83.8	56.5
&L	49.2	52.3	85.0	46.9
R ˆ	70.8	67.6	84.7	37.3
d\|	58.4	53.3	84.8	44.9

Appendix

Table 11: Encoder layer 1 probe accuracy (%) for operator identity by position.

Predicting	ˆ \|	&L	R ˆ	d\|
$e$ : attention to $c$	84.9%	57.2%	84.0%	91.2%
$f$ : attention to $c$	74.0%	62.3%	68.4%	77.6%
$f$ : attention to $u$	24.8%	34.9%	27.6%	19.6%

Appendix

Table 12: Cross-attention weights (layer 0 average across heads) on selected encoder positions.

Corrupted position	ˆ \|	&L	R ˆ	d\|
$a$ $\to$ op 1 changed	73.0%	68.0%	62.0%	73.7%
$b$ $\to$ op 1 changed	73.7%	73.3%	67.0%	73.7%
$c$ $\to$ op 2 changed	70.7%	69.7%	69.3%	70.0%
$d$ $\to$ op 2 changed	77.0%	78.7%	75.3%	78.3%
$u$ $\to$ op 1 changed	3.0%	1.0%	1.3%	1.0%
$u$ $\to$ op 2 changed	1.7%	0.7%	0.7%	1.0%

Appendix

Table 13: Input corruption: fraction of predictions changed when each encoder position is replaced with a random value.

Layer	Target	ˆ \|	&L	R ˆ	d\|
Embedding	op 2	6.6	4.6	2.4	10.4
After dec-0	op 2	97.5	87.2	82.0	89.6
After dec-1	op 2	100	100	99.9	100
Embedding	op 1	0.0	3.9	1.7	0.6
After dec-0	op 1	61.8	47.9	54.3	60.1
After dec-1	op 1	93.1	91.6	94.9	93.6

Appendix

Table 14: Logit lens: accuracy (%) when projecting intermediate decoder representations to output vocabulary at the positions predicting op 1 and op 2 .

Figure 5: Holdout accuracy across all 49 operator pairs (3 seeds each, dots show individual seeds). Dashed line: best interpolation baseline (KRR, 18.2%). Dark bars: four case-study holdouts from Table 3 .

Figure 6: Training dynamics for Rule D (left) and Rule 150 pattern 3 (right). Each line is one seed (10 per panel). Holdout accuracy (blue) emerges rapidly once supervised accuracy (orange) exceeds

\sim

85%. For pure XOR (Rule 150), holdout stays near 0% until this threshold; Rule D, which has internal structure permitting partial interpolation, can rise earlier. Rule 150 (

k

=1, radius 1) requires more epochs and fewer seeds converge, consistent with sparser constraints producing weaker indirect signal.

Transformer

Transformers are neural architectures that use attention to model relationships among sequence elements in language, vision, and scientific data.

See all 535 papers

Jul 13, 2026

From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP

A theoretical understanding of Transformers is crucial to better understand the capacities and limitations of large language models (LLMs). There is much work analyzing the expressivity of attention-based models. By proposing handcrafted weights or using computational complexity arguments, a large amount of past theoretical works have sought to characterize which tasks are and which are not in the hypothesis class of Transformer models. However, little work investigates the learnability of such solutions. In this work, we make progress towards this goal. Inspired by recent loss landscape analysis work, we propose preliminary sample complexity bounds for learning C-RASP constructions with Transformers.

Michael Rizvi-Martel, Satwik Bhattamishra, Guillaume Rabusseau +1

Mila & Universit´e de Montr´eal · University of Oxford · Saarland University

Transformer Sample Complexity

Ask PDF

May 29, 2026

Fixed Universal Transformers

We introduce universal transformers: fixed transformers that can simulate any transformer in a given class via a suitable input embedding. Analogous to a universal Turing machine, the input embedding encodes a description of the target model while all internal parameters remain fixed. We provide explicit sparse constructions achieving universality when the embedding dimension is sufficiently large, and further show that universality is generic: randomly initialized transformers are universal almost surely, which aligns with recent empirical results of Zhong and Andreas (2024). We empirically validate our theory on the algorithmic tasks of parenthesis balancing and multi-hop reasoning. Our results suggest that much of a transformer's expressive power may reside in its input representation rather than its learned weights.

Jingwen Liu, Alexandr Andoni, Daniel Hsu

Columbia University New York, NY

Transformer Expressivity Transformer

Ask PDF

Oct 12, 2026

One-Layer Transformers Provably Learn In-Context K-Nearest Neighbor Prediction with Chain-of-Thought

Chain-of-Thought (CoT) enables transformers to solve complex reasoning tasks by generating intermediate reasoning steps. Despite strong empirical success, the mechanisms by which such reasoning abilities emerge during training remain poorly understood, particularly from a theoretical perspective. In this work, we study this question in a stylized yet fully analyzable setting: in-context

\mathrm{K}

-nearest-neighbor (

\mathrm{K}

-NN) prediction with a one-layer transformer. Earlier work has demonstrated that one-layer transformers can be trained to perform

1

-NN without CoT (Li et al., 2024a) by having the softmax attention attend to the nearest neighbor in context. However, this result on

1

-NN cannot be extended to

\mathrm{K}

-NN for

K>1

, as softmax attention is much less naturally suited to attending to the 2nd through

K

-th nearest neighbors. We first give a rigorous negative result showing that this limitation already appears on a well-separated class of binary classification tasks for odd

K>1

. We then give an explicit construction of a one-layer transformer, and show that it can solve

\mathrm{K}

-NN via CoT reasoning. We further prove that, under a stylized training setup, gradient descent can recover this construction, thereby showing that transformers can acquire the capability to solve

\mathrm{K}

-NN through training. In addition, we show that the resulting trained model applies to a broader test class than that assumed in the training analysis. Our results shed light on how CoT expands the ability of transformers to learn and solve tasks that are otherwise hard to solve.

Lyumin Wu, Yuan Cao

School of Computing & Data Science, The University of Hong Kong

Transformer In-Context Learning Neural Algorithmic Reasoning CoT Reasoning k-Nearest Neighbors

Ask PDF

Abstract

Transformer

Explore similar work

From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP

Fixed Universal Transformers

One-Layer Transformers Provably Learn In-Context K-Nearest Neighbor Prediction with Chain-of-Thought