TL;DR
This paper shifts the study of "grokking" (delayed generalization) from the timing of the transition to the structure of the final solution. By modeling tasks as Latin Squares, the authors prove that while abelian group structures (like modular addition) mathematically guarantee generalization for all minimum-norm solutions, generalization is vanishingly rare in the broader space of random Latin squares.
What Problem Does This Paper Address?
Grokking is a counterintuitive phenomenon in deep learning where a model first perfectly memorizes its training data (remaining at chance accuracy on held-out data) and then, much later, suddenly generalizes.
While previous research has focused on the "why" and "when" of the delay, this paper asks a more fundamental question: What task structures make generalization even possible? Specifically, if we assume that training with weight decay eventually pushes a network toward a "minimum-norm" solution, does every such solution generalize, or just a lucky few?
The authors investigate this by looking at "pairwise input tasks"—problems where you take two inputs and produce one output. The classic example is modular addition ($x + y \pmod q$). They generalize this using Latin Squares: $q \times q$ tables where every symbol appears exactly once in every row and column (think of a completed Sudoku grid).
Methods
The authors use a mix of mathematical proofs and experiments with one-hidden-layer ReLU networks. Key components of their approach include:
- Minimum-Norm Endpoints: They define the "endpoint" of training as the set of all possible networks that achieve maximum margin on the training data with the smallest possible parameter norm.
- The Phase Profile: They classify tasks into three phases: all-good (every minimum-norm solution generalizes), no-good (none do), and mixed (some do, some don't).
- Relabelling Invariance: They prove that "structure" is independent of how a task is presented. If you shuffle the rows, columns, or labels of an addition table, the underlying task "orbit" remains the same.
- The Carrier Criterion: A theoretical lemma used to prove that a task is "all-good" if a "cheap" (low-norm) network exists that can represent the entire task grid with a comfortable margin.
Datasets
The study relies on synthetic datasets derived from Latin Squares:
- Modular Addition: The "cyclic prototype" for grokking.
- Relabelled Addition: Shuffled versions of the addition table that look like high-degree, dense polynomials (noise-like) but retain the same group structure.
- Random Latin Squares: Generated from random perfect matchings to serve as "unstructured" controls.
- Composite Order Tasks: Group tables of size $q=64$ (e.g., $C_2 \times C_{32}$) used to study how models recover partial information.
Key Insights and Ideas
- Structure Trumps Presentation: A surprising "aha moment" is that grokking is invariant to relabelling. Even if you encode modular addition such that it looks like a dense, complex polynomial, the network still groks it just as easily as the standard version. This suggests the network finds the underlying algebraic structure regardless of the "presentation" (see Figure 2).
- The Two Poles of Generalization: The authors identify two extremes in the space of Latin Squares. At one pole, Abelian Groups (like addition) are asymptotically "all-good"—generalization is mathematically guaranteed. At the opposite pole, Uniform Random Latin Squares are "unlearnable"—the probability of finding a generalizing solution vanishes as the problem size grows.
- Coarse-to-Fine Learning: On complex tasks of composite order, networks don't learn the whole label at once. They often learn "coarse factors" (e.g., whether the answer is even or odd) well before they can predict the exact label.
Key Results
- Theoretical Guarantee: The paper proves that for any sequence of finite abelian groups, the worst-case minimum-norm accuracy converges to 100% as the group size increases.
- The Rarity of Grokking: They prove that in the "ambient space" of all possible Latin squares, those that allow for generalization are extremely rare.
- Experimental Validation: Experiments at $q=97$ show that while relabelled addition reaches 100% accuracy, random-matching Latin squares stay below 0.14% accuracy (see Figure 1).
Limitations and Future Work
- Architecture Constraints: The theoretical proofs are currently limited to one-hidden-layer ReLU networks. While the authors discuss depth, a formal "depth-robust" proof remains a target for future work.
- Non-Abelian Groups: The "all-good" status of non-abelian groups (like dihedral groups) is suggested by experiments but not yet fully proven.
- The "Mixed" Phase: The authors acknowledge that the boundary between "mixed" and "no-good" tasks is still an open question. They haven't yet identified a specific family of tasks that consistently results in a "mixed" endpoint set.
Summary updated