Grokking as Structural Inference: Transformers Need Bayesian Lottery Tickets

• URL: http://arxiv.org/abs/2605.15787v1
• Date: Fri, 15 May 2026 09:46:36 GMT
• Title: Grokking as Structural Inference: Transformers Need Bayesian Lottery Tickets
• Abstract summary: We study why a Transformer that has memorized its training set wait thousands of steps before it generalizes.<n>We prove that this explaining-away delay can be bypassed by a KL-based structural intervention.<n>Experiments on algorithmic sequence tasks isolate structure from capacity and show that this Bayesian ticket matches or outperforms lottery-ticket transfer.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Why does a Transformer that has memorized its training set wait thousands of steps before it generalizes? Existing accounts locate this delay in norm minimization, feature emergence, or the late discovery of sparse subnetworks. These explanations capture important parts of the transition, but ignore a constraint unique to attention-based models: if attention discards an informative token, no bounded downstream computation can recover it. We formalize attention as an implicit Bayesian posterior over the task dependency graph and prove that generalization requires two separable conditions: a familiar Goldilocks bound on MLP capacity, coinciding with norm-based theories of grokking, and a novel Bayesian structural condition requiring attention to place sufficient mass on every informative token. This decoupling explains delayed generalization as delayed structural inference. Early in training, the MLP memorizes through unaligned features, drives the cross-entropy loss near zero, and thereby starves attention of structural gradient. Weight decay must then erode memorization before the missing graph becomes learnable, yielding the known inverse-weight-decay delay, which we derive as a structural waiting time. We then prove that this explaining-away delay can be bypassed by a KL-based structural intervention, yielding an inverse-intervention-strength scaling law for the grokking time. Experiments on algorithmic sequence tasks isolate structure from capacity and show that this Bayesian ticket matches or outperforms lottery-ticket transfer.

Related papers

• Stabilizing Extrapolation in Looped Transformers via Learned Stochastic Stopping [56.14767235650558]
  Looped Transformers, which repeatedly apply a shared transformer block, are an architecturally natural fit for variable-length computation tasks.<n>We trace this variance to the spurious correlation in simple algorithmic tasks between sequence length and number of loops.<n>Our work suggests that "when to stop" should be treated as a training design choice, not merely an inference-time-allocation rule.
  arXiv  Detail & Related papers  (2026-06-29T08:58:09Z)
• Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers [50.98108117044413]
  We show that the choice of a graph-to-token map is a fundamental component of transformer expressivity.<n>We examine three tokenizations that serve as building blocks for many existing graph tokenizations: spectral, random-walk, and adjacency tokenizations.
  arXiv  Detail & Related papers  (2026-05-21T13:32:20Z)
• Norm-Hierarchy Transitions in Representation Learning: When and Why Neural Networks Abandon Shortcuts [0.0]
  We introduce the Norm-Hierarchy Transition (NHT) framework, which explains delayed representation learning.<n>We derive a tight bound showing that the transition delay grows logarithmically with the ratio between shortcut and structured norms.
  arXiv  Detail & Related papers  (2026-03-07T20:07:16Z)
• The Geometric Inductive Bias of Grokking: Bypassing Phase Transitions via Architectural Topology [0.0]
  We study grokking - delayed generalization in Transformers trained on cyclic modular addition (Zp)<n>We identify two independent structural factors in standard Transformers: representational magnitude and data-dependent attention routing.
  arXiv  Detail & Related papers  (2026-03-05T14:41:01Z)
• Recurrence-Complete Frame-based Action Models [0.06768558752130312]
  "Attention Is All You Need" famously claims RNN cells are not needed in conjunction with attention.<n>We conjecture a critical time t beyond which non-recurrence-complete models fail to aggregate inputs correctly.<n>To address this, we introduce a recurrence-complete architecture and train it on GitHub-derived action sequences.
  arXiv  Detail & Related papers  (2025-10-08T09:50:41Z)
• Understanding Transformers for Time Series: Rank Structure, Flow-of-ranks, and Compressibility [90.894232610821]
  We analyze Transformers through the lens of rank structure.<n>We show that time-series embeddings exhibit sharply decaying singular value spectra.<n>We prove that the associated $Q/K/V$ projections admit accurate low-rank approximations.
  arXiv  Detail & Related papers  (2025-10-02T23:56:17Z)
• Provable In-Context Learning of Nonlinear Regression with Transformers [66.99048542127768]
  In-context learning (ICL) is the ability to perform unseen tasks using task specific prompts without updating parameters.<n>Recent research has actively explored the training dynamics behind ICL, with much of the focus on relatively simple tasks.<n>This paper investigates more complex nonlinear regression tasks, aiming to uncover how transformers acquire in-context learning capabilities.
  arXiv  Detail & Related papers  (2025-07-28T00:09:28Z)
• Beyond Progress Measures: Theoretical Insights into the Mechanism of Grokking [50.465604300990904]
  Grokking refers to the abrupt improvement in test accuracy after extended overfitting.<n>In this work, we investigate the grokking mechanism underlying the Transformer in the task of prime number operations.
  arXiv  Detail & Related papers  (2025-04-04T04:42:38Z)
• Curse of Attention: A Kernel-Based Perspective for Why Transformers Fail to Generalize on Time Series Forecasting and Beyond [17.002793355495136]
  We propose the first theoretical explanation of the inefficiency of transformers on TSF tasks.<n>We attribute the mechanism behind it to bf Asymmetric Learning in training attention networks.
  arXiv  Detail & Related papers  (2024-12-08T20:29:06Z)
• How Transformers Learn Causal Structure with Gradient Descent [44.31729147722701]
  Self-attention allows transformers to encode causal structure. We introduce an in-context learning task that requires learning latent causal structure. We show that transformers trained on our in-context learning task are able to recover a wide variety of causal structures.
  arXiv  Detail & Related papers  (2024-02-22T17:47:03Z)
• Bridging Lottery Ticket and Grokking: Understanding Grokking from Inner Structure of Networks [27.020990219204343]
  We investigate the influence of internal network structures on grokking.<n>We show that utilizing lottery tickets during the generalizing phase (termed grokked tickets) significantly reduces delayed generalization.<n>We find that grokked tickets exhibit periodic weight patterns, beneficial graph properties, and undergo rapid structural changes.
  arXiv  Detail & Related papers  (2023-10-30T11:58:44Z)
• CARD: Channel Aligned Robust Blend Transformer for Time Series Forecasting [50.23240107430597]
  We design a special Transformer, i.e., Channel Aligned Robust Blend Transformer (CARD for short), that addresses key shortcomings of CI type Transformer in time series forecasting. First, CARD introduces a channel-aligned attention structure that allows it to capture both temporal correlations among signals. Second, in order to efficiently utilize the multi-scale knowledge, we design a token blend module to generate tokens with different resolutions. Third, we introduce a robust loss function for time series forecasting to alleviate the potential overfitting issue.
  arXiv  Detail & Related papers  (2023-05-20T05:16:31Z)

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.