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

• URL: http://arxiv.org/abs/2603.17019v1
• Date: Tue, 17 Mar 2026 18:02:28 GMT
• Title: Transformers Can Learn Rules They've Never Seen: Proof of Computation Beyond Interpolation
• Abstract summary: We test a strong-only hypothesis in two controlled settings.<n>In Experiment 1, we use a cellular automaton with a pure XOR transition rule.<n>In Experiment 2, we study symbolic operator chains over integers with one operator pair held out.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A central question in the LLM debate is whether transformers can infer rules absent from training, or whether apparent generalisation reduces to similarity-based interpolation over observed examples. We test a strong interpolation-only hypothesis in two controlled settings: one where interpolation is ruled out by construction and proof, and one where success requires emitting intermediate symbolic derivations rather than only final answers. In Experiment 1, we use a cellular automaton with a pure XOR transition rule and remove specific local input patterns from training; since XOR is linearly inseparable, each held-out pattern's nearest neighbours have the opposite label, so similarity-based predictors fail on the held-out region. Yet a two-layer transformer recovers the rule (best 100%; 47/60 converged runs), and circuit extraction identifies XOR computation. Performance depends on multi-step constraint propagation: without unrolling, accuracy matches output bias (63.1%), while soft unrolling reaches 96.7%. In Experiment 2, we study symbolic operator chains over integers with one operator pair held out; the model must emit intermediate steps and a final answer in a proof-like format. Across all 49 holdout pairs, the transformer exceeds every interpolation baseline (mean 41.8%, up to 78.6%; mean KRR 4.3%; KNN and MLP score 0% on every pair), while removing intermediate-step supervision degrades performance. Together with a construction showing 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, ruling out the strongest architectural form of interpolation-only accounts: that transformers cannot in principle discover and communicate unseen rules, while leaving open when such behaviour arises in large-scale language training.

Related papers

• Align, Unify, Suppress, Route: A Coherentist View of Transformer Computation [0.0]
  Coherentist Probabilistic Compositionalism grounds transformer computation in coherentist theories of interpretation.<n>Across 15 models from five architecture families, the suppression, unification, and routing weight-space signatures correlate with held-out activation-level role measures.<n>Explicit contradictions significantly shift a layerwise coherence proxy in 14 models; after removing shared residual covariance, the gap has the predicted direction in every model.
  arXiv  Detail & Related papers  (2026-08-22T16:29:20Z)
• Architecture-Dependent Causal Transfer of Activation States Across Large Language Models [51.56484100374058]
  Internal language activation states can be transferred causally between different large language models.<n>Injecting projected activations into a target model during generation produces a statistically significant, preregistered causal effect.<n>We conclude that end-to-end activation-state transfer between LLMs, as currently implemented, is architecture-dependent rather than universal.
  arXiv  Detail & Related papers  (2026-08-17T09:53:27Z)
• Grounding latent algorithm routing in transformer reasoning [2.3977651066739374]
  We study whether transformers can organize episode-level adaptation around different inductive-bias families.<n>We introduce ROUTEBENCH, a diagnostic benchmark whose regimes favor global shrinkage, sparsity, robustness, and locality.<n>Across dense decoder-only transformers trained from scratch at 44M-612M parameters, a 306M model closes 80.9 percent of the oracle-routing gap and achieves route F1 of 84.1.
  arXiv  Detail & Related papers  (2026-07-27T14:07:12Z)
• Cross-Trajectory Chimera Interventions Reveal Dissociable Roles of Weight Magnitude and Direction in Grokking [0.0]
  Single-trajectory interventions show necessity within one run, not portability across runs.<n>We introduce cross-trajectory interventions: given two runs from different seeds, we split each weight vector into a norm and a unit direction, recombine one run's norm with the other's direction, and continue training.
  arXiv  Detail & Related papers  (2026-07-07T12:12:43Z)
• Transformers Provably Learn to Internalize Chain-of-Thought [65.41010769606844]
  Implicit Chain-of-Thought (ICoT) trains models to internalize intermediate steps within their hidden states.<n>Log-ICoT removes thinking tokens one at a time, reducing the number of stages from linear in $k$ to logarithmic.<n>Experiments on multi-layer transformers confirm the theory and visualize how reasoning is progressively absorbed into deeper layers.
  arXiv  Detail & Related papers  (2026-05-27T15:17:06Z)
• When Rule Violations Are Rare: Chimera Training for Logical Anomaly Detection [56.362776482614976]
  We study anomaly detection in a setting where constraints are given as logical rules over learned visual concepts.<n>We propose a neural rule evaluator that compiles each constraint into a directed acyclic graph and learns feature-aware subtree gates.<n>Across CLEVRER, OpenImages, and VidOR, the resulting evaluator improves rule-level anomaly AUROC over independent-events and same-image semantic-training baselines.
  arXiv  Detail & Related papers  (2026-05-25T02:52:36Z)
• Correction and Corruption: A Two-Rate View of Error Flow in LLM Protocols [51.56484100374058]
  We propose a paired-outcome measurement interface for auditing a single protocol step on exact-match tasks.<n>For each instance, the interface records a baseline correctness bit and a post-step correctness bit.<n>These rates predict accuracy changes and define a reusable empirical interface testable across seeds, mixtures, and pipelines.
  arXiv  Detail & Related papers  (2026-04-20T13:25:40Z)
• Empirical Falsification of Pairwise-Only Explanations for an Engineered Parity Benchmark on a 133-Qubit Superconducting Processor [0.0]
  We report a compact hardware experiment designed to distinguish pairwise-only explanations from irreducible triplet-order predictive structure.<n>A1b protocol implements a parity-structured binary label on a 133-qubit IBM superconducting processor.
  arXiv  Detail & Related papers  (2026-03-20T22:24:41Z)
• Transformers Don't In-Context Learn Least Squares Regression [5.648229654902264]
  In-context learning (ICL) has emerged as a powerful capability of large pretrained transformers.<n>We study how transformers implement learning at inference time.<n>We highlight the role of the pretraining corpus in shaping ICL behaviour.
  arXiv  Detail & Related papers  (2025-07-13T01:09:26Z)
• How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Bias [48.9399496805422]
  We focus on two representative tasks in the category of regular language recognition, known as even pairs' and parity check'<n>Our goal is to explore how a one-layer transformer, consisting of an attention layer followed by a linear layer, learns to solve these tasks.
  arXiv  Detail & Related papers  (2025-05-02T00:07:35Z)
• Transformers Provably Solve Parity Efficiently with Chain of Thought [40.78854925996]
  This work provides the first theoretical analysis of training transformers to solve complex problems.<n>We consider training a one-layer transformer to solve the fundamental $k$-parity problem.
  arXiv  Detail & Related papers  (2024-10-11T08:55:17Z)
• Unveiling Induction Heads: Provable Training Dynamics and Feature Learning in Transformers [54.20763128054692]
  We study how a two-attention-layer transformer is trained to perform ICL on $n$-gram Markov chain data. We prove that the gradient flow with respect to a cross-entropy ICL loss converges to a limiting model.
  arXiv  Detail & Related papers  (2024-09-09T18:10:26Z)
• Transformers as Support Vector Machines [54.642793677472724]
  We establish a formal equivalence between the optimization geometry of self-attention and a hard-margin SVM problem. We characterize the implicit bias of 1-layer transformers optimized with gradient descent. We believe these findings inspire the interpretation of transformers as a hierarchy of SVMs that separates and selects optimal tokens.
  arXiv  Detail & Related papers  (2023-08-31T17:57:50Z)
• Predicting Out-of-Domain Generalization with Neighborhood Invariance [59.05399533508682]
  We propose a measure of a classifier's output invariance in a local transformation neighborhood. Our measure is simple to calculate, does not depend on the test point's true label, and can be applied even in out-of-domain (OOD) settings. In experiments on benchmarks in image classification, sentiment analysis, and natural language inference, we demonstrate a strong and robust correlation between our measure and actual OOD generalization.
  arXiv  Detail & Related papers  (2022-07-05T14:55:16Z)
• The Parallelism Tradeoff: Limitations of Log-Precision Transformers [29.716269397142973]
  We prove that transformers whose arithmetic precision is logarithmic in the number of input tokens can be simulated by constant-depth logspace-uniform threshold circuits. This provides insight on the power of transformers using known results in complexity theory.
  arXiv  Detail & Related papers  (2022-07-02T03:49:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.