When Grokking Becomes Algebra: An Exactly Solvable Limit Case

Introduction

Grokking is often described as delayed generalization: a neural network first memorizes a training set, appears to make little progress, and only later discovers a rule that generalizes. Modular arithmetic has become one of the cleanest settings for studying this behavior, especially because model capacity strongly changes the outcome. Too little capacity can make memorization slow or impossible; enough capacity can make generalization appear much earlier.

This paper asks what happens at the far end of that spectrum. What if the architecture’s expressible function class is not merely small, but algebraically constrained to a fixed finite-dimensional object?

Core ideas

• A deliberately solvable architecture: The authors study two-layer networks with the holomorphic monomial activation σ(z)=z^k, trained on modular tasks represented through roots of unity. This makes the network’s behavior analyzable through discrete Fourier characters.
• Width does not remove the constraint: No matter how many hidden units are added, the network output remains inside a ((k+1))-dimensional subspace of characters of ((\mathbb{Z}_p)^2). This is only an (O(k/p^2)) slice of the full function space.
• Representability has a sharp algebraic test: A task is representable exactly when its discrete Fourier support lies on the diagonal (u+v=k \pmod p). For linear-phase targets, this reduces to the arithmetic condition (m+n=k).
• Failure is not just poor optimization: If the condition is not met, the model cannot fit the target even on the training set. The paper proves a positive lower bound on training loss that does not disappear with increased hidden width.
• Experiments become binary: Across 585 runs, the algebraic prediction matches the observed outcome with 99.8% accuracy. Instead of a memorization phase followed by grokking, runs split into immediate success or outright failure.

Why it matters

The result reframes grokking through the lens of representability. In standard stories, the key question is when a network transitions from memorization to rule learning. In this extreme model, that question dissolves: the target is either inside the architecture’s algebraic function class, or it is not.

The paper does not claim that ordinary neural networks always behave in such a binary way. Its bottleneck ablation instead connects this limit to more standard networks, tracing a path from representational failure, to memorization without generalization, and then to grokking with a shrinking gap as capacity increases.

That makes the model useful as a theoretical microscope. It separates delayed generalization caused by training dynamics from hard limits imposed by the architecture’s expressible function class. For researchers studying synthetic tasks, Fourier structure, and capacity-driven generalization, the paper offers a rare case where the boundary between learnable and unlearnable is algebraically exact.

Source: arXiv