📊 statistics

Algebraic Representability as the Limiting Regime of Grokking: An Exactly Solvable Model with Holomorphic Activations

This paper demonstrates that in two-layer neural networks with holomorphic monomial activations trained on modular arithmetic, the expressible function class collapses to a finite-dimensional algebraic variety, causing the network to exhibit a binary outcome of either instant generalisation or guaranteed training failure—thereby eliminating the grokking phenomenon entirely as the capacity-grokking relationship reaches its limiting regime.

Original authors: Chon-Fai Kam, Xavier Cadet, Miloud Bessafi, Frederic Cadet

Published 2026-07-16

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Chon-Fai Kam, Xavier Cadet, Miloud Bessafi, Frederic Cadet

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot to solve math puzzles. Usually, when we train these robots (called neural networks), we expect them to get better the more we practice. But sometimes, something weird happens: the robot memorizes the answers perfectly, gets a perfect score on its homework, but then fails miserably when you give it a new, similar problem. It sits there, stuck in a "memorization" mode, for thousands of steps. Then, suddenly, without any warning, it snaps into a new mode and starts solving the new problems correctly. This strange, delayed awakening is called grokking. It's like a student who crams for a test, forgets everything the next day, and then suddenly understands the concept a week later.

Scientists have been trying to figure out why this delay happens. They know that the size of the robot's brain (its "capacity") matters. If the brain is too small, it might never learn. If it's huge, it learns instantly. But what happens in the middle? Does the delay just get shorter as the brain gets bigger? Or is there a point where the robot's brain is so strangely built that it cannot learn the answer at all, no matter how long you wait? This paper dives into that question by building a very specific, mathematically perfect robot to see what happens when the rules of learning are pushed to their absolute limit.

The Robot with a One-Size-Fits-All Brain

The authors of this paper decided to stop guessing and start building. Instead of using a standard, messy robot brain, they built a special kind of network with a very strict rule: it can only think in a specific type of mathematical pattern called a "holomorphic monomial."

Think of this robot's brain like a locksmith with a very specific set of keys.

Standard Robots (Universal Approximators): Most AI models are like a locksmith with a giant toolbox. No matter what lock you give them, they can eventually pick it if they have enough time and enough tools. They might take a long time to figure out the right combination (memorization), and then suddenly get it (generalization), but they can always open the door.
This Paper's Robot: This robot only has one specific key shape. It can only open locks that match that exact shape. If you give it a lock that doesn't fit that shape, it doesn't just take a long time to open it; it cannot open it at all. It's not a matter of "not enough practice"; it's a matter of "wrong tool."

The researchers tested this robot on modular arithmetic tasks (basically, math problems where numbers wrap around, like a clock). They asked: If the robot's brain is so limited that it can't even represent the answer, does it still "grok"?

The Big Discovery: The "All-or-Nothing" Switch

The answer they found is surprisingly simple and binary. There is no middle ground, no slow delay, and no grokking.

The "Yes" Case: If the math problem the robot is asked to solve happens to match the specific shape of its key, the robot solves it instantly. It learns the training data and the new data at the exact same time. There is no waiting period. It's like handing the locksmith the exact key they were born to hold; the door swings open immediately.
The "No" Case: If the problem doesn't match the key's shape, the robot fails completely. It doesn't memorize the answers. It doesn't get stuck in a loop. It just stays at the level of random guessing forever. The training loss (a measure of how wrong it is) hits a hard floor and refuses to go lower, no matter how wide the robot's brain is or how long you train it.

The authors proved this mathematically. They showed that for this specific type of robot, the set of problems it can solve is a tiny, fixed slice of all possible problems. If your problem isn't in that slice, the robot is mathematically incapable of fitting the data. It's not an optimization problem; it's a structural impossibility.

The Experiment: 585 Trials of Truth

To prove this wasn't just a theory, the team ran 585 experiments. They tested the robot on 39 different math problems with 5 different "key shapes" (activation degrees).

The Result: The robot's behavior matched the math predictions with 99.8% accuracy.
The Pattern: The results formed a perfect "staircase." If the problem's numbers added up to the right total, the robot succeeded instantly. If not, it failed instantly.
The Missing Middle: In 585 runs, there were zero cases of "grokking" (the delayed success) and zero cases of "memorization without generalization" (getting the homework right but failing the test). The robot either won immediately or lost immediately.

The Comparison: The "Normal" Robot

To make sure this wasn't just a weird quirk of their special robot, they ran the same tests on a standard, "normal" robot (using a ReLU activation, which is the industry standard).

The Normal Robot: This robot could solve every problem. It memorized everything. But on the hard problems, it exhibited the classic grokking behavior: it memorized the training set, sat there for thousands of steps, and then suddenly generalized.
The Contrast: The problems that caused the special robot to fail completely were the exact same problems that caused the normal robot to grok. This proves that the "delay" in grokking isn't just about the problem being hard; it's about the robot's brain being almost big enough, but not quite. The special robot showed us what happens when the brain is too small to even start the race.

The "Bottleneck" Test: Bridging the Gap

The researchers wanted to see if there was a smooth path between "instant failure" and "instant success." They took a normal robot and squeezed its brain through a "bottleneck," making it narrower and narrower.

Wide Bottleneck: The robot groks (delayed success).
Medium Bottleneck: The robot memorizes but never generalizes (it gets stuck).
Tiny Bottleneck: The robot fails to memorize at all (instant failure).

This experiment connected the dots. It showed that the "instant failure" regime of the special robot is just the extreme end of the same spectrum where grokking happens. As you shrink a robot's capacity, the delay gets longer and longer, until finally, the delay becomes infinite because the robot can't even memorize the data in the first place.

What About Learning the Keys?

One might wonder: "What if the robot could learn its own keys?" The authors tested this by letting the robot learn its own input encoding (instead of being given the fixed "roots of unity" encoding).

The Result: The "staircase" of instant success and failure disappeared. The robot could now solve almost all the linear problems instantly.
The Exception: There was still one problem it couldn't solve: the multiplication task ( $a \times b$ ). Even with a learned brain, the robot's structure was too simple to capture the complexity of multiplication. This confirmed that the failure wasn't just about the specific math they used to feed the robot; it was a fundamental limit of the robot's architecture.

The Takeaway

This paper reveals a fundamental truth about AI training: Grokking is a race between memorization and generalization. But for that race to happen, the runner must first be able to tie their shoes.

If a neural network's brain is too small or too rigid to even represent the answer (to "tie its shoes"), the race never starts. There is no delay, no struggle, and no sudden awakening. There is just a hard stop. The question of "when will it grok?" dissolves into the simpler, more primitive question: "Can it represent the target at all?"

The authors have shown that when you push a network to its mathematical limits, the messy, confusing behavior of grokking vanishes, replaced by a clean, binary reality: either the math fits, and you win instantly; or it doesn't, and you lose instantly. It's a reminder that before we can talk about how AI learns, we have to make sure it's actually capable of learning what we're asking it to do.

Technical Summary: Algebraic Representability as the Limiting Regime of Grokking

Problem Statement
Recent literature on "grokking"—the phenomenon where neural networks trained on modular arithmetic tasks transition from memorization to generalization after a significant delay—has established that model capacity governs the timing of this transition. However, existing frameworks (e.g., Song and Ye 2026) assume the network is sufficiently large to eventually memorize the training data. This paper investigates the limiting regime where the network's expressible function class is so constrained that it cannot represent the target function at all, even in principle. The central question is: What happens to the memorization-generalization dynamic when the architecture's capacity is structurally insufficient to fit the training set, rather than merely slow to do so?

Methodology
The authors study a specific, exactly solvable architecture: a two-layer complex-valued neural network with a holomorphic monomial activation $\sigma(z) = z^k$ . The network is trained on modular arithmetic tasks $f: \mathbb{Z}_p \times \mathbb{Z}_p \to \mathbb{Z}_p$ (where $p$ is prime) using a roots-of-unity encoding, where inputs $(a, b)$ are mapped to $(\omega^a, \omega^b)$ with $\omega = e^{2\pi i/p}$ .

Key methodological choices include:

Algebraic Tractability: The choice of $\sigma(z) = z^k$ ensures the network output is a polynomial of degree $k$ . On the roots-of-unity encoding, this restricts the network's output to a specific subspace of characters of the group $(\mathbb{Z}_p)^2$ .
Fourier Analysis: The authors utilize harmonic analysis on finite abelian groups to characterize the "expressible class" $\mathcal{F}_k$ . They prove that regardless of the hidden width $H$ , the network output is confined to a $(k+1)$ -dimensional subspace spanned by characters with frequency labels $(\ell, k-\ell)$ for $0 \le \ell \le k$ .
Theoretical Bounds: The paper derives a lower bound on the training loss for non-representable targets, proving that the loss remains strictly positive and independent of hidden width.
Experimental Validation: The theory is tested across 585 experimental runs involving 39 tasks (35 linear-phase, 4 nonlinear-phase) and 5 activation degrees ( $k=2$ to $6$).
Comparative Ablations: The study includes a ReLU baseline (universal approximator) and a "bottleneck" ablation on ReLU networks to trace the transition from representational failure to grokking.

Key Contributions

Exact Algebraic Characterization of Representability:
The paper provides a complete characterization of which modular tasks lie within the expressible class $\mathcal{F}_k$ .
- Linear-phase targets ( $f(a,b) = ma + nb \mod p$ ): A task is representable if and only if $m + n = k$ (assuming $m+n \le k$ ). If this condition is not met, the target is orthogonal to the entire expressible subspace.
- Nonlinear-phase targets (e.g., $ab$, $a^2+b^2$ ): These tasks have Fourier support that extends beyond the diagonal $u+v \equiv k \pmod p$ . The paper proves these are unrepresentable for any finite $k < p$ .
- Encoding Independence: Through Proposition 1, the authors show that even with learned embeddings, the representability of a task is constrained by the rank of the target matrix. Specifically, the task $ab$ (which corresponds to a full-rank DFT matrix) remains unrepresentable for any $k < p-1$ , regardless of the input encoding.
The "No Memorization" Regime:
The paper proves that for non-representable targets, the network cannot memorize the training set. Because the output is algebraically confined to a subspace that does not contain the target, the training loss is bounded below by a positive constant (the spectral gap). Consequently, there is no "memorization" phase, no "grokking" delay, and no gradual improvement; the network simply fails to fit the data, remaining at chance-level accuracy.
Empirical Validation of Binary Outcomes:
Across 585 runs, the algebraic prediction matched the observed outcome with 99.8% accuracy. The results were strictly binary:
- Representable tasks: Learned almost instantly (Instant Generalization, or INST) with no gap between training and test accuracy.
- Non-representable tasks: Complete failure (FAIL) with training accuracy stuck at chance levels.
- There were zero instances of grokking or memorization-without-generalization for the holomorphic network.
Connecting to the Capacity Spectrum:
The paper bridges the gap between the "algebraic extreme" (holomorphic networks) and standard universal approximators (ReLU networks).
- ReLU Baseline: Standard ReLU networks memorize all tasks and exhibit grokking on difficult nonlinear tasks, with delays scaling with task complexity.
- Bottleneck Ablation: By compressing a ReLU network via a linear bottleneck, the authors trace a continuous path from FAIL (when the bottleneck is too narrow to fit the data) to MEM (memorization without generalization) to GROK (with a shrinking gap as capacity increases). This demonstrates that the "FAIL" regime observed in the holomorphic model is the structural limit of the capacity-grokking spectrum.

Significance and Claims
The paper argues that the question of "when a network will grok" is a secondary question that presupposes the primary condition of representability.

Limiting Regime: The holomorphic network represents the limiting case where the expressible class collapses to a fixed algebraic object. In this regime, the competition between memorization and generalization speeds (the mechanism of grokking) never begins because the memorization phase is structurally impossible.
Structural vs. Optimization Constraints: The results distinguish between optimization difficulties (which cause grokking delays in standard networks) and representational impossibility (which causes immediate failure in constrained networks).
Universality of the Obstruction: The failure of the task $ab$ is shown to be an intrinsic property of the architecture's rank constraints, not an artifact of the fixed roots-of-unity encoding.

The authors conclude that their work defines a regime where the dynamics of grokking dissolve into a binary question of representability. While the specific algebraic results apply to this holomorphic setting, the bottleneck experiments suggest that the three-regime structure (Failure $\to$ Memorization $\to$ Grokking) is a general feature of the capacity spectrum, with the holomorphic model providing a rigorous, analytically solvable boundary condition for the "Failure" end of that spectrum.