Grokking as Structural Inference: Transformers Need Bayesian Lottery Tickets

Grokking -- generalization long after training-set interpolation -- has been accelerated by structure-agnostic interventions (gradient filtering, weight-norm clamping, geometric penalties). Whether the delay specifically measures the time to form task-structured representations has remained observational. We test it causally by injecting representational priors of varying content into a one-layer transformer learning modular addition, via a supervised-contrastive loss whose positives encode (i) the task's true structure ($(a+b) \bmod p$), (ii) a coherent-but-wrong sibling ($(a-b) \bmod p$), or (iii) a random partition -- all with identical loss form, strength, class sizes, and geometry. Whether generalization occurs follows a clean gradation: true 22/30 runs, sibling (same periodic features, wrong combination) 14/15, random (only memorizable) 0/20 (Fisher $p=1.3\times10^{-7}$). A weight-norm-matched control replaying the norm trajectory onto plain cross-entropy generalizes 0/15, ruling out the norm as mediator. Probes show structure formation precedes and predicts generalization in all runs. Only the true structure also accelerates grokking (up to $2.75\times$), but this is dose-dependent and bimodal. We then confirm the mechanism by prediction: because the acceleration is gated by a weight-norm side-effect, clamping the norm during training yields a reliable, standalone accelerator with a median $8.6\times$ speedup (up to $22\times$ on the fastest seeds, under 1000 epochs), growing monotonically as the norm is held lower; the residual stalls also vanish, though significant only pooled over the two mitigations run at both strengths ($0/40$ vs $6/20$, $p=7.7\times10^{-4}$), not per method. The grokking delay is, causally, the time to form the right representational structure -- decided at the level of features, not labels.

This paper studies simple transformers trained on a high-order Markov chain, where the model must incorporate information from multiple past positions, each with different statistical importance. We show that transformers learn the task incrementally, with each stage corresponding to learning how to copy information from a subset of positions via a sparse attention pattern. Notably, the learning dynamics transition from a competitive phase, where all heads focus on the statistically most important positions, to a cooperative phase, where different heads specialize in different patterns. We model these dynamics with simplified differential equations and prove stage-wise convergence of the resulting system. Functionally, these stages correspond to a sequence of increasingly expressive misspecified models, with the full model class reached only at the end. Overall, we give a theoretical account of how structured attention patterns and head specialization emerge in stages without an explicit curriculum, with implications for generalization in sequential tasks.

Systematic generalization remains a significant challenge in deep learning. In particular, combinatorial generalization - generalizing to new configurations of known factors of variation - is effortless for humans but difficult for standard neural architectures that rely on statistical correlations rather than explicit structural representations. We introduce a new architectural component that embeds structured inductive bias into deep learning: an attention mechanism operating over tensor-product representations (TPRs). Through controlled experiments on compositional tasks, we show that this TPR-attention mechanism outperforms existing architectural components in combinatorial generalization. These results highlight the value of integrating explicit compositional structure into neural attention and point toward a promising path for models capable of systematic generalization.