How to read this explainer¶
This site explains one research paper — Lotfi, Finzi, Kuang, Rudner, Goldblum and Wilson, Non-Vacuous Generalization Bounds for Large Language Models (ICML 2024, arXiv:2312.17173v3) — from first principles. You do not need any background. If you already know the background, the chapter list and the dependency map show where to jump in.
Reading order. Chapters are numbered by topic, but the sidebar lists them in an order where every chapter comes after the chapters it needs. The one difference: Chapter 8 (linear algebra) needs nothing earlier and is listed right after Chapter 3, because Chapters 5 and 7 use it.
Two layers in every chapter¶
The main text is written in plain language. Sentences are short and each paragraph carries one idea. When a formula appears, every symbol is explained in words right next to it.
The "Going deeper" blocks are collapsed by default. They hold the full mathematics: definitions, step-by-step derivations and complete proofs of every tool the paper uses (Markov's, Chebyshev's and Hoeffding's inequalities, the union bound, the Kraft inequality, Theorem A.1, Theorem A.2, the subsampling bound, and more). Click a block to open it.
Going deeper: what a block looks like
This is a "Going deeper" block. Inside, nothing is skipped: each equation is derived from the previous one, and every probability statement says what is random and what is fixed.
Every chapter follows the same order:
- The problem this chapter solves — why the paper needs the idea.
- Intuition — an everyday analogy, and an explicit note on where the analogy breaks.
- Precise definition — the exact statement.
- Worked example with real numbers — every number is printed by a script you can run.
- Going deeper — proofs and derivations.
- Common misconceptions.
- Self-test — three questions with hidden answers.
- Code for this chapter — the script, its output, and how to run it.
Where each statement comes from¶
We never blur what the paper says with what we add. Paragraphs carry a coloured tag:
- PAPER §4.1, p. 4 — the paper states this (section and page given). We paraphrase; we do not copy.
- MY EXPLANATION — our addition: intuition, derivation steps, worked examples, analysis.
- MY ANALYSIS — our own critical conclusion (for example, a gap in an argument).
- SOURCE: … — a supporting source other than the paper: Lotfi et al. (2022), Hu et al. (2021, LoRA), nanoGPT, the authors' public code, or dataset statistics.
A heading may set a default tag for its whole section; any paragraph that switches source carries its own tag.
Problems in the paper¶
When the paper contains a typo, an ambiguity or an inconsistency, we do not silently fix it. We show what it says, then the corrected reading, inside a yellow "Paper erratum" box, and we log it with a number (E01, E02, …) on the errata page.
Values the paper does not state¶
Some numbers needed to reproduce the paper are never printed in it. We recovered them elsewhere and label them [SOURCE] every time they matter:
| Quantity | Value | Where it comes from |
|---|---|---|
| confidence parameter \(\delta\) | 0.05 | authors' public code; Lotfi et al. (2022) |
| number of training documents \(m\) | 8,009,762 | nanoGPT's OpenWebText split; authors' code |
| number of 1,024-token training sequences | 8,823,811 | authors' code |
| vocabulary size \(V\) | 50,257 | GPT-2 tokenizer |
| 1 KB | 8,192 bits | Lotfi et al. (2022); confirmed by reproducing Table 1 |
| OpenWebText training tokens | 9,035,582,198 | nanoGPT prepare.py |
Using these values, we reproduce the paper's headline bound (12.12 bits per token, Table 1) as 12.1222 from numbers read off the paper's own figures — see Chapter 24 and Chapter 25.
Notation used everywhere¶
| Symbol | Meaning | Units / type |
|---|---|---|
| \(h\), \(\hat h\) | a hypothesis (one fully specified model, incl. hyperparameters); the one returned by training | — |
| \(\mathcal H\) | hypothesis space: the set of all allowed \(h\) | finite set |
| \(X_j\) | the \(j\)-th training document (random) | sequence of tokens |
| \(m\), \(n\) | number of training documents; size of the random subsample | counts |
| \(\sigma(i)\) | index of the \(i\)-th subsampled document | random index |
| \(R(h,X)\) | loss of \(h\) on one document \(X\) | bits per token, or a fraction |
| \(\hat R(h)\), \(\hat{\hat R}(h)\) | average loss over the \(m\) training documents; over the \(n\) subsampled ones | as the loss |
| \(R(h)\) | expected loss on a fresh document | as the loss |
| \(\Delta\) | width of the interval that contains the loss | as the loss |
| \(\delta\) | failure probability (0.05 means 95 % confidence) | probability |
| \(\Pr[\cdot]\) | probability of an event | probability |
| \(P(h)\) | prior weight of \(h\), fixed before seeing data | probability |
| \(C(h)\), \(K(h)\) | compressed size of \(h\); Kolmogorov complexity of \(h\) | bits |
| \(\ln\), \(\log_2\) | natural logarithm; base-2 logarithm (the paper often writes just "log") | — |
| \(V\) | vocabulary size (50,257) | count |
| \(x_i\), \(x_{<i}\) | the \(i\)-th token; all tokens before it | token ids |
| \(L\), \(L_{\text{ctx}}\) | number of tokens in a document; context length (1,024) | counts |
| \(p_\theta\), \(p_h\) | the model's token probabilities; the smoothed version | probability |
| \(\alpha\), \(\alpha_{\text{LoRA}}\) | smoothing weight; LoRA's scaling constant (32) | — |
| \(\theta\in\mathbb R^D\), \(\theta_0\) | all model parameters as one long vector; their random initialization | real numbers |
| \(w\in\mathbb R^d\), \(P\in\mathbb R^{D\times d}\) | the trained low-dimensional vector; the fixed random projection | — |
| \(B\), \(A\), \(r\) | LoRA factors (\(\Delta W = BA\)) and their rank (the paper writes \(U\), \(V\)) | — |
| \(c_1,\dots,c_{L_q}\) | quantization levels (\(L_q\) = 11 or 17) | real numbers |
| \(H(p)\) | entropy of a distribution \(p\) | bits |
Units matter throughout: losses for "bits per dimension" (BPD) are in bits per token; the complexity term of the bound is computed in nats (natural-log units), because it comes from an exponential; 1 bit = ln 2 ≈ 0.693 nats.
Running the code¶
Every number in the text is printed by a Python script in explainer/code/. From the project folder:
python -m venv .venv
.venv/Scripts/python -m pip install numpy scipy matplotlib pymupdf torch mkdocs-material
.venv/Scripts/python explainer/code/run_all.py
run_all.py runs every demo and checks (with assertions) that the reproduced paper numbers agree with the paper to
its stated rounding. The All code demos page lists each script and what it reproduces.