Generalization

Definition

Generalization is how a model performs on data it was never trained on — and the reason a model can score 99% during training and 70% in production is that those two numbers measure different things. Training accuracy asks whether the model can reproduce answers it has already been shown. Generalization asks whether the rule it invented to cover everything else happens to be right. The difference between the two is the generalization gap, and it is the only quantity in machine learning that predicts whether a system is worth deploying.

Two facts about it are worth more than any list of techniques. First, generalization is never proven, only measured — and the measurement is a sample statistic with an error bar you can compute in one line. Second, the textbook explanation of why it happens — keep the model simple enough and it cannot memorize — is now known to be wrong for deep networks. A network with enough capacity to memorize its entire training set generalizes anyway, and one that has memorized pure noise is indistinguishable, by every classical complexity measure, from one that has learned something. That contradiction is not a footnote. It is the current state of the subject.

How It Works

Nothing in the training data tells you what to predict next

Start with the fact that makes generalization surprising rather than obvious. Suppose your inputs are 20-bit strings, so there are 2²⁰ = 1,048,576 of them, and you have labelled 10,000 with a yes or no. Your training data has pinned down 10,000 / 1,048,576 = 0.95% of the function's domain. The remaining 99.05% is free, and the number of distinct functions that agree perfectly with every one of your training labels is 2^(1,048,576 − 10,000) = 2^1,038,576.

For any particular unseen input, exactly half of those functions say yes and half say no. Averaged over them, any predictor you can write down scores exactly 50% — chance. This is the content of the no-free-lunch theorem (Wolpert, Neural Computation 1996): averaged uniformly over all target functions, every learning algorithm has the same expected error on data outside its training set. There is no algorithm that generalizes better than another in general.

So generalization is not something an algorithm does. It is a bet that the algorithm's built-in preference — its inductive bias — matches the world. A convolutional network bets that nearby pixels matter more than distant ones. A linear model bets on additivity. Gradient descent bets that among the many parameter settings fitting the data, the one it drifts to has small norm. When the bet is right you get 95% accuracy; when it is wrong you get 50%, and no amount of data fixes it, because the data was never the constraint.

The gap, on numbers

A fraud classifier scores 99.4% on its training rows and 96.1% on held-out rows: a generalization gap of 3.3 percentage points. Read that gap as an estimate of how much of the training score was specific to those particular rows rather than to the phenomenon.

But read the 96.1% against a baseline before celebrating it. If 3% of transactions are fraudulent, a model that predicts "never fraud" scores 97% — better than the trained one — and the whole system is worse than a constant. The gap tells you about memorization; only the comparison against a trivial baseline tells you whether anything was learned. Both checks are necessary and neither substitutes for the other. Whether the gap comes from too much capacity or too little is the territory of overfitting and underfitting, and the standard decomposition of error into bias, variance and noise is worked on numbers in ensemble methods.

Your test score is a measurement, and measurements have error bars

This is the most immediately useful arithmetic on this page and it is almost never applied. A test accuracy is the mean of n independent right/wrong outcomes, so its standard error is the binomial one:

SE = √(p(1 − p) / n), and the 95% interval is roughly ±1.96 × SE.

The consequences are immediate. A model reported at 80% on a 100-item eval could truly be anywhere from 72% to 88%. Two models a point apart on a 1,000-item benchmark are not distinguishable. And because the interval shrinks as 1/√n, halving it costs four times the labelling and quartering it costs sixteen times — which is why serious benchmarks are large and why a hand-built eval of 50 prompts cannot settle an argument.

One honest refinement: when two models are scored on the same items the comparison is paired, so the interval above is conservative. Only the items where the two disagree carry information, and McNemar's test on those discordant pairs is the right instrument. Related but distinct is the problem of estimating this number when you have too little data to spare a test set at all, which is what cross-validation exists for.

The classical story, and the two results that broke it

The classical account says test error follows a U: too little capacity and the model cannot fit the signal, too much and it fits the noise, so control capacity and you control generalization. That story survives in every introductory course. Two results show it cannot be the explanation for deep networks.

Networks fit random labels perfectly. In "Understanding deep learning requires rethinking generalization" (Zhang, Bengio, Hardt, Recht and Vinyals, ICLR 2017), a small Inception network with 1,649,402 parameters — 33 parameters for each of CIFAR-10's 50,000 training images — was trained twice. On the true labels it reached 100.0% training accuracy and 85.75% test accuracy. On labels replaced with uniform random classes it reached 100.0% training accuracy and 9.78% test accuracy: exactly chance on ten classes. Same architecture, same optimizer, same hyperparameters, same parameter count, no retuning. On ImageNet, Inception V3 fitted 95.20% top-1 on a million random labels drawn from 1,000 categories, and around 90% with dropout and weight decay left switched on.

Count what was memorized: 50,000 labels over 10 classes is 50,000 × log₂10 = 166,096 bits, about 20 KB of pure noise, stored in 1.65 million parameters — roughly 0.10 bits per parameter. The network had capacity to spare.

The point is narrower and sharper than the folklore version. It is not that networks memorize real data — on real labels the same network generalized to 85.75%. It is that any bound computed from the model class alone must be vacuous, because such bounds never look at the labels, and the labels are the only thing that differed between a run that generalized and a run that did not. The authors note that their result implies an empirical Rademacher complexity of ≈ 1 for these networks, which bounds the generalization error by a number greater than 1 and therefore says nothing. Nor does the paper say regularization is useless: switching on random cropping and weight decay moved that same network from 85.75% to 89.05%, a real 3.3-point gain. The claim is that explicit regularization is "neither necessary nor by itself sufficient" for generalization — a tuning knob, not the mechanism.

Test error descends twice. The U-curve says that past a certain size, more capacity must hurt. It does not. Belkin, Hsu, Ma and Mandal (PNAS 2019) fitted random-Fourier-feature models to 10,000 MNIST digits and found the classical U up to the interpolation threshold — the point where the number of features N equals the number of samples n = 10⁴ and the model can fit the training data exactly. There the test error peaks, and the model at that exact point, in their words, "has no predictive ability for classification". Add more features and error falls again, ending below the best value achieved anywhere in the classical regime. They named the shape double descent. Nakkiran et al. (ICLR 2020) reproduced it on ResNet-18s trained on CIFAR-10 with 15% label noise, and found two stranger variants: epoch-wise double descent, where training longer first hurts and then helps, and sample-wise non-monotonicity, where multiplying the training set by 4.5× (4k to 18k examples on a German-English translation task) made test performance worse for some model sizes. The ## Code Example below reproduces the whole shape, peak included, in twenty lines of NumPy.

The folklore reading — "bigger is always better, the old theory is dead" — is wrong in both halves. The peak is real, it is severe, and it sits exactly where a classically-sized model sits. And the second descent does not repeal the bias-variance decomposition; it shows that parameter count was never the right x-axis. That is why Nakkiran et al. replaced it with effective model complexity, defined as the largest training set the whole procedure — architecture, optimizer and training length together — can drive to near-zero error.

In-distribution and out-of-distribution

Every number above assumes the test set is drawn from the same distribution as the training set. That assumption is what a held-out split actually tests, and it is a much weaker claim than the one people take from a benchmark score. In-distribution generalization means the model handles new examples of the kind it has seen. Out-of-distribution generalization means it handles a new hospital, a new season, a new camera, or a user who phrases things differently — and a held-out split from the same pool cannot measure it, because every row in it came from the same pool. The robustness page covers what to do about that; the point here is that the two get reported with the same word and the same percentage sign, and only one of them was measured.

Real-World Applications

Rebuilding a benchmark from scratch, and watching every model drop. Recht, Roelofs, Schmidt and Shankar collected new test sets for CIFAR-10 and ImageNet by following the original collection protocols as closely as they could document them (ICML 2019). Across a broad range of models they measured accuracy drops of 3–15% on CIFAR-10 and 11–14% on ImageNet. The surprise was the diagnosis: the drops were not caused by years of researchers tuning against the public test set, but by the new images being slightly harder. Model rankings were largely preserved — the benchmark still ordered models correctly, it just overstated all of them. A benchmark can be a valid comparison and an invalid forecast at the same time.

A pneumonia detector that had learned which hospital took the X-ray. Zech et al. (PLOS Medicine 2018) trained computer vision models on 158,323 chest radiographs from three institutions. A model trained at Mount Sinai scored AUC 0.802 internally and 0.717 at the NIH; a jointly-trained model scored 0.931 internally and 0.815 on Indiana data. Internal beat external in 3 of 5 natural comparisons. The mechanism was identified precisely: pneumonia prevalence was 34.2% at Mount Sinai and 1.2% at the NIH, a network could identify the source hospital from the image alone with 99.95% accuracy, and hospital identity by itself predicted pneumonia at AUC 0.861 on the pooled data — higher than the NIH-trained detector's own internal AUC of 0.750. The model found the shortcut because the shortcut generalized perfectly within the distribution and not at all outside it.

Commissioning a benchmark that cannot have leaked. Because LLMs train on scraped text, a public benchmark may already be in the training data, and a model that has memorized it reports a generalization gap of nearly zero while having generalized nothing. Scale AI tested this by commissioning GSM1k: 1,250 new grade-school maths problems written by human annotators and matched to GSM8k on human solve rate, solution length and answer magnitude (Zhang et al. 2024). Accuracy drops on the fresh set reached 13 percentage points, concentrated in the Phi and Mistral families, while Gemini, GPT and Claude models showed little to none. A model's probability of generating a GSM8k problem verbatim correlated with its drop (Spearman's r² = 0.32) — memorization leaving fingerprints.

That study is also the cleanest worked example of the error bar above. Phi-3-mini-4k-instruct scored 78.2% on GSM8k (1,319 problems) and 68.4% on GSM1k (1,250 problems), a gap of 9.8 points. Is that noise? SE = √(0.782 × 0.218 / 1319 + 0.684 × 0.316 / 1250) = 0.0174, so the gap is 9.8 / 1.74 = 5.6 standard errors — the z-score the paper itself reports. A 1-point gap on the same two test sets would have scored z = 0.58 and meant nothing at all.

Key Concepts

• Generalization gap: training score minus held-out score. It measures memorization of the specific training rows, not fitness for deployment — a model can have a gap of zero and still be useless, and a well-calibrated model on shifting data can have a small gap and a large real error.
• Inductive bias: the preference that picks one of the 2^1,038,576 consistent functions. Architecture, optimizer and regularizer are all ways of expressing it, and it is the only reason generalization is possible at all.
• Interpolation threshold: the capacity at which a model can exactly fit its training data. Test error peaks there, which is precisely why "just big enough to fit the data" is the worst possible size to choose.
• Covariate shift, label shift, concept drift: the three ways a held-out estimate silently stops being valid — the inputs move, the outcome frequencies move, or the relationship between them moves. Only the third makes your existing annotations wrong.
• Shortcut learning: a feature that predicts the label inside the dataset and not outside it — the hospital tag, the watermark, the sentence length. It produces a small generalization gap and a catastrophic deployment failure, which is the combination no held-out split can catch.

Challenges

The measured gap is a lower bound on the real one. Every effect on this page pushes the same way. A contaminated benchmark understates the gap because the test items were in training. A test set reused for a hundred experiments understates it because your model-selection decisions have fitted it. A test set drawn from the same pool as training understates it because the shift you will actually face is not represented in the pool. The number you report is the most optimistic estimate consistent with your evidence, and deployment error is systematically worse than it.

Test sets are consumed by use, though not as fast as expected. Every hyperparameter choice made by looking at held-out performance leaks a little information from the test set into the model, which is why feature selection done outside the validation loop produces impressive scores on pure noise. The honest surprise from the ImageNetV2 work is that a decade of community reuse of the ImageNet test set apparently did not produce the drop; harder images did. Adaptive overfitting is real, and it is not the largest problem — which is worth knowing before spending a year on it.

No usable bound exists for the models people actually deploy. Classical uniform-convergence bounds — VC dimension, Rademacher complexity, uniform stability — are all computed from the model class or the algorithm, and Zhang et al.'s random-label result rules out every one of them for deep networks, since none can distinguish the run that generalized from the run that did not. Tighter specialised bounds exist for small problems, but nothing in the literature replaces the practical procedure: hold out data, measure, and attach the binomial interval. Generalization in deep learning remains an empirical fact rather than a derived one.

Fixing generalization and diagnosing it are different jobs. The gap tells you that something is wrong, not what. More data augmentation helps a model that has memorized and does nothing for one that has found a shortcut. A regularizer helps with variance and cannot touch a distribution shift. Collecting more data from the same biased pool improves your estimate of the wrong quantity. Choosing among them requires knowing which failure you have, and the single gap number cannot tell you.

Future Trends

Held-out benchmarks by construction. GSM1k is the template: commission fresh items, keep them private, and report the drop against the public version as the contamination measure. Rolling benchmarks that retire and replace items on a schedule apply the same idea continuously. It is a change in what a benchmark is — from a fixed public artefact to a renewable one — forced by the fact that a public test set stops measuring generalization the moment it is scraped.

Contamination detection as standard practice. Canary strings embedded in benchmark files, n-gram overlap scans between eval sets and training corpora, and the verbatim-generation probe used in the GSM1k analysis are becoming things a model card is expected to report. None is conclusive against a closed training set, but together they turn "was this contaminated?" from an unanswerable question into an estimate with an error bar.

Predicting generalization before training. Scaling laws forecast held-out loss from parameter count, data size and compute — empirical curve-fitting rather than a bound, but accurate enough to allocate budgets, which is more than classical theory ever delivered. Nakkiran et al.'s effective model complexity points the same way, measuring capacity by what a full training procedure can actually fit rather than by counting parameters. Both replace "is this model class too rich?" with "what does this procedure do on this data?", and that is where the useful answers have been coming from.

Code Example

Two things worth computing rather than describing: the confidence interval around a reported score, and the double-descent curve itself.

import math

def interval(p, n, z=1.96):
    """95% binomial interval for an accuracy p measured on n examples."""
    se = math.sqrt(p * (1 - p) / n)
    return se, z * se

for n in (100, 1_000, 1_250, 5_000, 14_042):
    se, half = interval(0.80, n)
    print(f"n={n:>6}  accuracy 80.0%  +/- {half * 100:.2f} pp  (se {se:.4f})")

# Is a reported gap real? Two-proportion z-test, Phi-3-mini on GSM8k vs GSM1k.
p1, n1 = 0.782, 1_319      # GSM8k test set
p2, n2 = 0.684, 1_250      # GSM1k, commissioned to be uncontaminated
se = math.sqrt(p1 * (1 - p1) / n1 + p2 * (1 - p2) / n2)
print(f"\ngap {p1 - p2:.3f}  se {se:.4f}  z {(p1 - p2) / se:.2f}")
print(f"a 1-point gap would score z {0.01 / se:.2f}")

The first block prints ±7.84, ±2.48, ±2.22, ±1.11 and ±0.66 percentage points: sixteen times the labelling to reduce the uncertainty fourfold. The second prints z = 5.64 for the observed gap and z = 0.58 for a hypothetical one-point gap, so the first is evidence and the second is weather.

Now the peak. Fit random features to 100 training points by minimum-norm least squares — the solution lstsq returns when the system is underdetermined — and sweep the number of features straight through the interpolation threshold at p = n = 100:

import math
import numpy as np

rng = np.random.default_rng(0)
n, d, noise = 100, 20, 0.5
beta = rng.standard_normal(d)

def test_error(p, trials=40):
    errs = []
    for _ in range(trials):
        W = rng.standard_normal((d, p)) / math.sqrt(d)
        Xtr = rng.standard_normal((n, d))
        ytr = Xtr @ beta + noise * rng.standard_normal(n)
        Xte = rng.standard_normal((2_000, d))
        yte = Xte @ beta
        w, *_ = np.linalg.lstsq(np.tanh(Xtr @ W), ytr, rcond=None)
        errs.append(float(np.mean((np.tanh(Xte @ W) @ w - yte) ** 2)))
    return float(np.median(errs))

for p in (10, 25, 50, 80, 100, 120, 200, 1_000, 3_000):
    print(f"features={p:>5}  test MSE={test_error(p):>9.3f}")

Every model from 100 features rightward fits the training data exactly, so training error is identically zero across that whole range — and test error varies within it by a factor of 151.073 / 0.305 = 495. That is the entire argument of this page in one table: fitting the training data perfectly tells you almost nothing about what the model will do next, and the thing that decides it is not capacity.