Concept dependency map¶
Two pictures of how the ideas depend on each other.
The paper's argument as a chain¶
Each box is one step of the argument. Read top to bottom: every step removes one obstacle between "a model did well on its training data" and "the model provably does well on new data". The tag on the right names the chapter that explains the step.
MY EXPLANATION In one paragraph: Hoeffding's inequality says one fixed model's training loss is close to its true loss. Training picks a model after looking at the data, so we must cover every model at once; the union bound does this at a price that grows with the number of models. A prior lets us pay less for simple models. The Kraft inequality turns code lengths into a legal prior, and the Kolmogorov/Solomonoff idea says "simple = short description". So the price becomes the model's compressed size in bits. To apply the bound to language models we need independent samples (whole documents, not tokens), a bounded loss (prediction smoothing) and an affordable training-loss estimate (subsampling). Finally, the model must actually be tiny when compressed: SubLoRA keeps only a few tens of thousands of numbers, and quantization plus arithmetic coding squeeze those into about 16.5 KB.
Chapter prerequisites¶
An arrow from chapter A to chapter B means "read A before B". Columns are ordered by the length of the longest prerequisite chain, so any left-to-right reading order works. Colours mark the five parts of the explainer.
| Chapter | Needs |
|---|---|
| 1 Probability, 3 Logs/bits, 8 Linear algebra | nothing |
| 2 Learning | 1 |
| 4 Language models | 1, 3 |
| 5 Transformers | 4, 8 |
| 6 LM metrics | 2, 3, 4 |
| 7 Training NNs | 2, 8 |
| 9 Hoeffding | 1, 3 |
| 10 Union bound | 2, 9 |
| 11 Prior / Eq. (1) | 3, 10 |
| 12 Kraft | 1, 3 |
| 13 Kolmogorov | 12 |
| 14 Compressed size | 11, 12, 13 |
| 15 Documents i.i.d. | 1, 4, 6, 11 |
| 16 Smoothing | 6, 11, 14 |
| 17 Subsampling | 9, 11, 15, 16 |
| 18 Subspace | 7, 8 |
| 19 LoRA | 5, 7, 8 |
| 20 SubLoRA | 18, 19 |
| 21 Quantization | 7, 20 |
| 22 Arithmetic coding | 3, 12 |
| 23 Paper §1–3 | 14–17, 20, 22 |
| 24 Algorithm 1 | 14, 16, 17, 20–22 |
| 25 Tables 1, 2, 4 | 6, 23, 24 |
| 26 Table 3, Figs 3–4 | 5, 25 |
| 27 Discussion | 26 |
| 28 Mini replication | 24 |
| 29 Critique | 25–28 |
The figures are produced by explainer/code/build_depmap.py.