Skip to content

Can we prove that a language model learned something?

A plain-language summary of Non-Vacuous Generalization Bounds for Large Language Models (Lotfi, Finzi, Kuang, Rudner, Goldblum and Wilson, ICML 2024, arXiv:2312.17173). No background needed.

The question

Large language models — programs like GPT-2 that write text one word-piece at a time — are trained on huge piles of web pages. They have hundreds of millions of adjustable numbers inside them. That is enough to store large parts of their training text word for word. So a fair worry is: do they only memorize and repeat, or do they learn patterns that also work on text they have never seen?

Testing on new text tells us how one model did on one test set. The paper wants something stronger: a mathematical guarantee, computed from the training data alone, of the form

"With 95 % confidence, this model's average error on new text is at most X."

Such a statement is called a generalization bound. A bound is vacuous when X is no better than random guessing — then it is true but useless. The paper reports that, for large language models, every bound before it was vacuous (we did not check this priority claim against the wider literature).

The main idea: simple explanations generalize

The paper's recipe has one central idea and a few repairs.

The central idea — Occam's razor with numbers. If a model can be written down in very few bits, it cannot have memorized much: a short description has no room to store the training text. The guarantee therefore gets a "price" that grows like the square root of (the model's description length ÷ the number of training documents). A model that is both accurate on its training data and tiny to describe gets a tight guarantee.

How that becomes mathematics, step by step:

  1. One fixed model. The average error over many independent examples is close to the true average error (Hoeffding's inequality — like a large opinion poll). → Chapter 9
  2. Many possible models. Training chooses the model after seeing the data, which can fool you (try enough lottery tickets and one wins). The fix is to pay for every model you could have chosen. → Chapter 10
  3. Pay less for simple models. Give each possible model a "prior weight" fixed in advance; short descriptions get large weights. The price you pay is then the model's description length in bits. → Chapters 11–14

The repairs needed for language models:

  1. Words in a text are not independent, so the guarantee is stated per document, and documents are treated as independent samples. → Chapter 15
  2. The usual error measure can be infinite (a model that gives the right word zero probability is infinitely wrong). The fix: blend the model's predictions with a little uniform guessing, which caps the worst case. → Chapter 16
  3. Checking the error on 8 million documents is expensive, so it is checked on a random sample of 10,000 and a small extra margin is added. → Chapter 17

Making a huge model tiny to describe

A normal GPT-2 has 124 million numbers — about 4 billion bits. That is far too long a description. The authors therefore train the model in a special form called SubLoRA: almost everything is fixed random noise that can be regenerated from a seed, and only a short list of up to 200,000 numbers is learned (Chapters 18–20). Those numbers are then rounded to a handful of allowed values and packed with a near-optimal compressor (Chapters 21–22). The best model ends up described in about 16.5 kilobytes.

What they found

  • Bits per token (how surprised the model is by each new word-piece; lower is better): the guarantee is 12.12 bits, while random guessing scores 15.62. Non-vacuous.
  • Next-token error (how often the single top guess is wrong): guaranteed to be at most 96.41 %, versus 99.998 % for random guessing. Non-vacuous, but it only certifies that at least 3.6 % of guesses are right.
  • The same recipe gives non-vacuous guarantees for architectures with up to 849 million numbers, and the authors argue that bigger models get slightly better guarantees.

Using values the paper does not print (recovered from the authors' code), we re-derived the headline 12.12 as 12.1222 from numbers read off the paper's own figures (Chapter 24).

What it does not show

  • The guaranteed model is the tiny compressed one, not GPT-2 as people use it. It is far weaker: on held-out text its surprise is 10.53 bits per token versus 4.35 for a normally trained GPT-2, and the text it writes is word salad (the paper's Table 7). The normally trained GPT-2's own guarantee is 70.76 bits — vacuous.
  • "Bigger is better" rests on differences of at most 0.17 bits per token, which go up and down with size, with no repeated runs; for the next-token error measures, bigger models are not consistently better.
  • The guarantee assumes the web documents are independent random draws from some fixed source — an assumption about the world, not something the procedure can guarantee.

The full assessment is in Chapter 29; the list of typos and inconsistencies we found in the paper is on the errata page.

How to read this site

  • Ten-minute path: this page → Chapter 23 (the paper's story) → Chapter 29 (critique).
  • Full path, no background assumed: read Parts I → V in order. The dependency map shows which chapters each one needs; the glossary lists every term in the order it is introduced.
  • Proof path, for readers who know probability: Chapters 9–17, opening every "Going deeper" block.
  • Hands-on path: every number comes from a script in explainer/code/; Chapter 28 runs the whole method end to end on a laptop and checks the guarantee against the truth.

Cite this explainer: Mukherjee, S. (2026), v1.0.0, Zenodo, doi:10.5281/zenodo.23838407. Source code and every script: GitHub.

How to read this explainer explains the two-layer format, the provenance tags (PAPER, MY EXPLANATION, MY ANALYSIS, [SOURCE]) and the notation.