Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets
A small network memorizes an arithmetic table, then learns the rule far later.
OpenAI researchers trained a two-layer transformer on the division table for the numbers modulo 97. Training accuracy reached about 100% within 1,000 steps. Validation accuracy stayed near chance until about 100,000 steps and reached 100% near step 1,000,000.
Explaining the paperGrokking: Generalization Beyond Overfitting on Small Algorithmic DatasetsThe paper reports the training curves and what affects them. Later papers worked out what the network computes, and the reason for the delay is still argued over.
Grokking is the name for a training run in which a neural network first memorizes its training examples and then, many steps later, starts answering unseen examples correctly, with no change to the data or the optimizer settings. Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin and Vedant Misra described it at an ICLR 2021 workshop, and their arXiv version is dated January 2022.1 The word comes from Robert Heinlein's novel Stranger in a Strange Land, where to grok something is to understand it completely.
A short vocabulary covers the rest of the page. A model overfits when it does well on the examples it was trained on and badly on examples it was not, which usually means it has stored those examples and found no rule that applies to new ones. Generalization is the opposite: correct answers on data held out from training, the validation set. An optimization step is one update of the weights from one batch of examples. Normal training practice is to stop once validation performance stops improving, on the assumption that an overfit network will not recover. The grokking experiments kept training anyway.
A few ideas explain the result: the dataset is an operation table with blank cells, the model is a very small transformer, the delay depends sharply on how much of the table is shown, weight decay shortens it, and the finished network computes something recognizable. The paper measures the first four. The last comes from later work and is marked that way.
The dataset: a table with holes
Every dataset in the paper is the table of a binary operation on a small set. Take division modulo the prime 97. The row is from 0 to 96, the column is from 1 to 96, and the cell holds such that . That gives equations. One of them is , because . A random fraction of cells goes to training and the rest to validation. With half of them, the network trains on 4,656 equations and is scored on the other 4,656.
The network sees symbols, not numbers. Each residue is a single token, the operator is a token, and the equals sign is a token, so the model gets the string <21> <÷> <7> <=> <3> with no decimal digits and no information about order or magnitude. Nothing tells the model that 22 follows 21. The only source of structure is which answer goes with which pair. The paper compares filling in the blanks to solving a Sudoku, and the table shares a Sudoku grid's property: the symbols could be renamed without changing the constraints.
? cells are held out. Switch between numbers, the renamed symbols the model effectively receives, and powers of 2 for multiplication and division. Drag the slider to change how much of the table the model is given, and click a cell to read its equation.In the numbers view of the division table, no pattern is obvious. Switch to powers of 2, which reorders rows and columns as (2 generates all twelve nonzero residues mod 13), and the same table becomes diagonal stripes. Every nonzero residue modulo a prime is a power of a fixed generator , called a primitive root. For 97 the smallest one is 5. Multiplying residues is then adding their exponents, and dividing is subtracting them:
So multiplication modulo 97 is addition modulo 96 with the symbols renamed. As a worked case: , , and in base 5, and indeed , matching . The paper uses this to predict that and should need about the same amount of data, and the paper's Figure 2 shows that they do, up to one small difference discussed under operations below.
The model and how it trains
The model is a decoder-only transformer with two layers, width 128 and four attention heads. A decoder-only transformer predicts each token from the tokens before it, and a causal mask stops any position from looking ahead. The released code feeds a seven-token sequence <eos> x op y = c <eos>, shifted by one position to form the inputs and targets, and takes the loss only on the part after the equals sign, as the paper says.
In tensor shapes: a batch of equations is a integer array. The input is the first six columns, the target the last six, the output is logits (239 is the code's vocabulary size), and only positions 4 and 5 count, those predicting the answer and the closing <eos>. The paper quotes about non-embedding parameters; counting the released architecture gives 424,832. A model that large has enough capacity to memorize all 9,312 equations many times over.
Training uses AdamW with learning rate , weight decay 1, , and a 10-step linear warmup, on minibatches of 512 equations (or half the training set if that is smaller). Half of the division table is 4,656 equations, so one pass through the training data takes about 9.1 steps. A million steps is about 110,000 passes. The official optimizer multiplies every weight by and then applies an Adam step, so with and each step shrinks every weight by 0.1%:
Here and are Adam's running averages of the gradient and the squared gradient, is a small constant, and the fraction is the gradient term. With no gradient term in (2) to offset the shrink, a weight falls to half its size in about 693 steps, because .
What grokking is: generalization long after overfitting
The figure below replays runs from our own replication of the paper's setup. The first run trains on 40% of the table modulo 97 with weight decay 1. Before playing it, look for two things: how early the teal curve (training accuracy) saturates, and how much later the amber curve (validation accuracy) moves.
In the x + y run, training accuracy reaches 99.4% by step 502, and validation accuracy first reaches 99% at step 3,297. In between, the network has already memorized its 3,764 training equations and keeps being trained. In the weight norm view, the norm of the weights falls from 134 at step 307 to 64 at step 3,297.
Chance level is low on this dataset. With 97 possible answers, guessing is right about of the time, so the validation curve starting near 1% means the network does no better than random guessing on held-out equations. The loss view has its own chance level:
The factor of one half comes from the released training step, which averages cross-entropy over the tokens after the equals sign, the answer and the closing <eos>. The end-of-sequence token is trivially predictable, so its loss is close to zero and the average over two tokens is half the loss on the answer. The dashed chance line in Figure 2 sits at 2.29 for that reason, and the paper's Figure 4 has a line near the same height.
The paper's own example is more extreme than our run. For its Figure 1, the authors trained on 50% of division modulo 97 with plain Adam, no weight decay, and a budget of steps, which the appendix says was chosen for emphasizing how late generalization can begin. Training accuracy is close to perfect before steps, there is "very little evidence of any generalization until steps", and validation accuracy reaches the same level close to steps. Validation loss rises for most of that time, from to about steps, before falling in a second descent. For a practitioner watching a loss curve, that run looks like a classic failure for a hundred thousand steps. Section 3.1 of the paper reports that these behaviours were typical for every operation at data fractions near the smallest one that could generalize within the budget, and that the training and validation curves track each other more closely at larger fractions.
Less data, much more optimization
The center panel of the paper's Figure 1 plots time to generalize against the amount of data. On the product in the symmetric group (the composition of permutations of five objects, 120 elements and 14,400 equations), the median number of steps to first reach 99% validation accuracy grows steeply as the training fraction shrinks. Near 25% to 30% of the data, removing one more percentage point raises that median by 40% to 50%. The rate compounds: five points of data means a factor of to , so the time doubles roughly every two percentage points. Training accuracy behaves differently: the steps to reach 99% on the training set stay in the range of to and generally fall as the training set shrinks, since less must be memorized.
The paper notes the practical reading of this: within the range where the network still generalizes, you can trade compute for data. Converged performance stays at 100% over a range of training sizes, and the cost shows up as optimization time. In ordinary supervised learning, less data means worse converged performance, so this is unusual behaviour. The authors suggest investigating whether the effect also occurs on other datasets.
In our division runs (Figure 3) the same shape appears. The 30% run first reaches 99% validation accuracy at step 14,443, on both seeds we tried at that fraction. The 40% run does so at step 7,197, the 50% run at 4,186 (5,281 on a second seed), and the 60% run at 2,254. The 20% and 25% runs did not reach 99% within the 20,000-step budget. Above 60% the time stops improving: 70% takes 2,631 steps and 80% takes 3,586. Steps to 99% training accuracy run the other way, from 301 at 20% of the data to 1,931 at 80%. These readings come from checkpoints spaced about 8% apart in steps, with one or two seeds per fraction, so they show the trend only. The paper's rate of 40% to 50% per point is a median over seven seeds on a different task.
Weight decay and other interventions
The paper's Figure 2 (left) compares nine training variants on , each scored by the best validation accuracy within steps: full-batch Adam, minibatch Adam, full-batch Adam with update noise, dropout, AdamW with weight decay 1, AdamW with decay towards the initial weights, a learning rate of , a learning rate of , and Gaussian weight noise. Weight decay gives the largest improvement, and the authors report that it more than halves the data needed compared with most other interventions. Training accuracy reaches 100% within to updates for all methods, so the differences are entirely in generalization.
Decay towards the initialization also works, but less well than decay towards the origin. The authors read this as evidence that a prior favoring near-zero weights explains part of the benefit of weight decay and not all of it. Noise in the optimizer, from minibatching or from Gaussian perturbation of the weights, also helps; the paper conjectures that noise pushes the optimizer towards flatter minima. Generalization happened only when the learning rate was tuned within about one order of magnitude.
With 40% of the division table, the run with weight decay 1 reaches 99% validation accuracy at step 7,197. Decay values of 0, 0.03, 0.1 and 0.3 all fit the training set by step 411 to 479 and are still at 8% validation accuracy or less at the last checkpoint, step 19,684. Weight decay 3 fails in the opposite way: training accuracy itself sits near 20% at that checkpoint, and at decay 10 it is 0% with the weight norm down to 17. A flat line over 20,000 steps does not show that the low-decay runs cannot grok, since the paper's no-decay run did not start rising until about steps. Choose the no-weight-decay run in Figure 2 and open the loss view to see what training does in the meantime: the weight norm grows from 179 to 399 and validation loss peaks at 12.3, more than five times the chance level of 2.29.
Weight decay is not required for grokking in the paper's runs, as the experiment behind its Figure 1 shows. It is, however, the intervention with the largest measured effect. The paper's Appendix A.5 adds a different kind of evidence: across networks trained on , the sharpness of the final minimum (Keskar et al.'s approximation) correlates with validation accuracy with a Spearman coefficient of (). Networks at flatter minima tended to have higher validation accuracy, and the authors present that as suggestive evidence and leave open whether flatness causes the generalization.
Which operations grok
Appendix A.1.1 of the paper lists twelve operations, and the paper's Figure 2 (right) plots, for each, the best validation accuracy within steps at each data fraction. The operations that are symmetric in their arguments, such as and , need less data than close relatives that are not, such as or . The authors offer a possible reason: a transformer can learn a symmetric function by ignoring its positional encoding, which would reduce the difficulty for symmetric operations. They call this partly architecture-dependent.
The cubic operation never generalized at any data fraction up to 95% within the budget. The models only memorized, and the authors state that to such a model the data is effectively random. An operation that switches rule depending on whether is odd ( if odd, otherwise) still generalizes, which shows that a network can find a rule even when it is not a clean group structure.
Appendix A.4 tests robustness to bad labels by replacing answers with answers from other equations in the training data, with up to 3,000. All runs reach 100% training accuracy with or without outliers, so the network memorizes the wrong labels too. Up to about 1,000 outliers the effect on generalization is small; larger shrinks the range of data fractions that generalize. The paper reads this as additional evidence that network capacity is well beyond what memorizing the labels requires.
The and comparison has a qualification: the prime-root renaming applies to nonzero residues, and the modulus changes. The appendix defines on 97 values including zero, while uses 97 values of and 96 of , so it includes a constant row at , where . The match in the paper's Figure 2 is therefore between closely related problems, not a perfect relabeling.
How the network adds: rotations on a circle
The paper's Figure 3 plots a t-SNE projection of the output layer of a trained network. t-SNE is a method that arranges high-dimensional points on a plane so that neighbors stay neighbors. Each point is one row of the output matrix, one vector for each candidate answer. For modular addition, the points form circles, with lines showing that adding 8 moves each element along the circle. For , they form clusters of permutations arranged as cosets of a subgroup. The paper does not explain what computation produces these shapes. Figure 5 measures the same object in our replication, without t-SNE, so distances on the plane are real projections of the weights.
The frequency is the discrete Fourier index: the pattern across the 97 answers. Frequencies and give the same pattern, so there are 48 distinct nonzero ones, and a frequency's power is its share of the variance. At the first checkpoint (step 20) the dots form a small blob and power is spread almost evenly over all 48 frequencies, about 2% each. By the final checkpoint (step 25,742) they lie on a ring, and the power bars on the right are concentrated on the seven frequencies {5, 8, 11, 22, 23, 37, 46}, which together carry about 86% of the variance of the centered output rows at that step, between 11% and 14% each. A memorizing network spreads its weight power across all 48 frequencies, and a generalizing one keeps only the frequencies the algorithm uses, as the next paragraphs describe.
Nanda, Chan, Lieberum, Smith and Steinhardt worked out the algorithm for modular addition in a one-layer transformer on and 30% of the data.2 They found the network represents a number as a point on a circle, as the cosine and sine of an angle with , for a handful of chosen . Modular addition is clock arithmetic on a clock with hours, and adding two numbers modulo is the same as adding their angles. Using the trig addition identities, the network produces and from the sines and cosines of the inputs:
Then each candidate answer gets a score from the output layer. The output weights implement and , and the logit combines them with the output of (4) and the matching sine: , which by the same identity is . Summing over frequencies gives:
In (5), is the strength the network gives frequency . Each cosine equals exactly 1 when and is smaller otherwise, because is prime and so is a multiple of only at the right answer. At a wrong answer the frequencies disagree: one cosine can be close to 1 while others fall far below it, so the sum separates the right answer, where every cosine is 1, from the best wrong one. Figure 6 shows the effect on a worked example.
The pair , has sum 17, since . Using only , the right answer scores exactly 1 and the best wrong answer scores 0.998, a margin of 0.002 that would not survive any noise. With two frequencies the margin is 0.01, with three it is 0.35, and with all seven it is 3.66. Reading the same formula as an implementation target: the embedding must store a cosine and sine pair per frequency, the layers must multiply those pairs, and the output weights must store the cosine and sine of each candidate.
Nanda et al. back this with four lines of evidence: the weights have the predicted periodic structure, the neuron-to-logit map is well approximated by the key frequencies, activations are localized by frequency, and ablating the key frequencies drops performance to chance while ablating the other 95% of frequencies slightly improves it. In their network the five key frequencies are {14, 35, 41, 42, 52}. They also split training into three phases. Memorization covers epochs 0 to 1.4k. In circuit formation (1.4k to 9.4k) the network gradually builds the generalizing mechanism while train and test loss stay flat. In cleanup (9.4k to 14k) the unused memorizing weights are removed and test loss drops abruptly. On this account, the sudden jump in test accuracy comes after the generalizing mechanism is already in place, when weight decay removes the memorized solution competing with it.
Why the delay
Neither the original paper nor the mechanistic account settles why the generalizing solution is found so late. The three accounts below are hypotheses, each supported by experiments in a particular setting.
Circuit efficiency. Varma, Shah, Kenton, Kramár and Kumar propose that training can use either a memorizing circuit or a generalizing circuit , both of which fit the training set.3 Weight decay favors a circuit that produces a given logit with less parameter norm, and they call this efficiency. The hypothesis is that is more efficient, and that it is learned more slowly. The memorizing circuit therefore fits the training set first, and the generalizing circuit eventually replaces it because it produces more logit per unit of weight. Efficiency also depends on training-set size: the memorizing circuit needs more weight for every extra example, the generalizing one does not. From this, Varma et al. predicted two new behaviours and confirmed them. A model that has already generalized, when trained further on a much smaller set, regresses from perfect to poor test accuracy (ungrokking), and at a critical set size delayed generalization reaches only partial accuracy (semi-grokking).
Weight-norm landscapes. Liu, Michaud and Tegmark observed that training and test losses, plotted against the norm of the weights, look like an L and a U respectively.4 Training loss is low over a wide range of norms, while test loss is low only in a band around a particular norm . A network starting at a large norm can fit the training data immediately and then needs a long, slow reduction in norm to reach the band. They used this picture to induce grokking on image, language and molecule tasks by scaling up the initial weights, and to eliminate grokking on algorithmic datasets.
Optimizer dynamics. Thilak, Littwin, Zhai, Saremi, Paiss and Susskind describe a slingshot mechanism in adaptive optimizers: late in training, the norm of the last-layer weights grows, the training loss spikes, and growth plateaus, in a repeating cycle.5 They report that without explicit regularization, the grokking in the original paper occurs almost exclusively at slingshot onset and is absent without it. Our replicated runs show loss spikes too, sometimes after generalization has already happened; we did not test whether they follow the last-layer norm pattern Thilak et al. describe. In the 50% division run of Figure 2, for example, the last checkpoint, at step 19,684, catches one, with training accuracy at 38% and validation accuracy at 23%, after both had been above 99%. Gromov shows that a two-layer multilayer perceptron with no regularization groks modular arithmetic under plain gradient descent with mean-squared error, so a specific optimizer pattern cannot be required for grokking in every setting.6
The original paper's own conjecture is that noise from SGD drives optimization towards flatter, simpler solutions that generalize better, consistent with the sharpness correlation above.
Implementation notes
The loop below follows the released code: logits has one row per position, and only the last two positions contribute to the loss.
# One training step of the replication (x / y mod 97, 50% train).
# batch: integer tokens, shape (B, 7):
# <eos> <x> <op> <y> <=> <c> <eos>
x, y = batch[:, :-1], batch[:, 1:] # inputs and shifted targets, shape (B, 6)
logits = model(x) # shape (B, 6, 239)
loss = cross_entropy(logits[:, 4:], y[:, 4:]) # only <c> and the final <eos>
loss.backward()
lr = 1e-3 * min(step / 10, 1) # 10-step linear warmup, then 1e-3
for p in params:
p *= 1 - lr * weight_decay # decoupled decay, applied to every weight
adam_step(params, lr, betas=(0.9, 0.98), eps=1e-8)
# weight_decay = 1 for most experiments; 0 for the paper's Figure 1 run.Three details of the released code affect a reproduction. The positional encoding in the released model is a fixed sinusoid, not a learned embedding. Weight decay is applied to every parameter, embeddings and LayerNorm weights included, by a direct multiplicative shrink before each Adam step. And the train/validation split comes from a shuffle with a fixed seed unless you change it.
Our replication used the architecture and optimizer settings above, on an Apple M4 Pro. A single run of 40,000 steps took about 7.4 minutes, and the 18-run sweep to 20,000 steps took about 37 minutes. The x + y run in Figure 2 generalized before step 3,300. Reproducing the paper's Figure 1 (Adam with no weight decay, a million steps) would take far longer; we did not repeat it.
Questions you might still have
Is grokking the same thing as double descent?
They are related, and the paper argues they differ. In double descent, as covered in the Deep Double Descent explainer, test error falls, rises near the point where the model can just fit the data, and falls again as capacity or training time grows. Grokking shows a second descent in validation loss far past the first time training loss becomes very small, tens of thousands of epochs in some runs, and the paper reports no non-monotonic behaviour in accuracy.
Does weight decay cause grokking?
No. The paper's most delayed example, Figure 1, used plain Adam with no weight decay and a budget of a million steps. Weight decay made generalization need less than half the data on S5 and made it happen much sooner. Nanda et al. saw no grokking without regularization in their one-layer setup, so whether explicit regularization is needed depends on the architecture and the training setup.
Does grokking happen on real data, or only on arithmetic?
The original paper studied only algorithmic datasets. Omnigrok (Liu, Michaud and Tegmark) induced delayed generalization on image, language and molecule tasks by increasing the size of the initial weights, so the effect is more general than arithmetic. It is much more pronounced on these small tables, which contain almost nothing except the rule to be found.
Can I tell mid-training that a run is about to grok?
Training loss and accuracy will not tell you, because they are already flat. Nanda et al. built progress measures from the Fourier structure of the logits for modular addition, which improve before test accuracy jumps. Those need a known target algorithm. On a task with an unknown solution there is no comparable signal.
Why does the network pick those particular frequencies?
The specific frequencies vary from run to run. Nanda et al. report {14, 35, 41, 42, 52} for their P = 113 mainline model, and our replication on P = 97 used {5, 8, 11, 22, 23, 37, 46}. Any nonzero frequency works in principle, since each one gives a cosine that peaks at the right answer. A few frequencies give a much larger margin over the runner-up than one, which is the reason a model keeps several.
What does 100% validation accuracy mean on 4,656 equations?
It means the model answers every held-out equation correctly at that step. Because the table is finite and the operation is exact, a model that has found the rule can be perfect on the held-out half. That is different from natural data, where label noise and ambiguity cap accuracy below 100%.
Footnotes & further reading
- Power, Burda, Edwards, Babuschkin & Misra, Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets (arXiv January 2022; ICLR 2021 MATH-AI workshop). Official code: github.com/openai/grok.
- Nanda, Chan, Lieberum, Smith & Steinhardt, Progress measures for grokking via mechanistic interpretability (ICLR 2023).
- Varma, Shah, Kenton, Kramár & Kumar, Explaining grokking through circuit efficiency (2023).
- Liu, Michaud & Tegmark, Omnigrok: Grokking Beyond Algorithmic Data (ICLR 2023), and Liu, Kitouni, Nolte, Michaud, Tegmark & Williams, Towards Understanding Grokking: An Effective Theory of Representation Learning (NeurIPS 2022).
- Thilak, Littwin, Zhai, Saremi, Paiss & Susskind, The Slingshot Mechanism: An Empirical Study of Adaptive Optimizers and the Grokking Phenomenon (2022).
- Gromov, Grokking modular arithmetic (2023). For the double-descent comparison see the Deep Double Descent explainer, and for a network's capacity to memorize random labels see the Rethinking Generalization explainer.
How could this explainer be improved? Found an error, or something unclear? I read every message.