Glossary¶

Every technical term used in the explainer, in the order in which it is first defined. Each entry names the chapter that defines it; follow the chapter link for the full explanation. Terms are listed only once, at their first use.

Chapter 1 — Probability toolkit¶

Defined in Chapter 1.

experiment — any procedure whose result is not known in advance, such as rolling a die or drawing documents at random from a collection. (Ch. 1)
outcome — one possible result of an experiment. (Ch. 1)
sample space — the set of all possible outcomes of an experiment, written \(\Omega\). (Ch. 1)
event — a set of outcomes, i.e. a yes/no question about the result; it "happens" if the actual outcome lies in it. (Ch. 1)
disjoint events — events that cannot both happen (their intersection is empty). (Ch. 1)
probability — a rule \(\Pr\) giving every event a number, with \(\Pr(A)\ge0\), \(\Pr(\Omega)=1\), and probabilities of disjoint events adding up. (Ch. 1)
complement rule — \(\Pr(\text{not }A)=1-\Pr(A)\). (Ch. 1)
random variable — a number computed from the outcome of an experiment; a fixed recipe whose input is random. (Ch. 1)
indicator — the random variable \(\mathbf 1[A]\) that equals 1 if event \(A\) happens and 0 otherwise; its expectation is \(\Pr(A)\). (Ch. 1)
distribution — the list of values a random variable can take together with the probability of each. (Ch. 1)
identically distributed — having the same distribution (for example, the first and second roll of a die). (Ch. 1)
expectation — the probability-weighted average \(\mathbb E[X]=\sum_x x\,\Pr(X=x)\) of a random variable; also called the mean or expected value. (Ch. 1)
linearity of expectation — \(\mathbb E[aX+bY]=a\,\mathbb E[X]+b\,\mathbb E[Y]\), valid for any random variables, dependent or not. (Ch. 1)
variance — the expected squared distance of a random variable from its mean, \(\mathbb E[(X-\mathbb E[X])^2]\); measured in squared units. (Ch. 1)
standard deviation — the square root of the variance, in the same units as the variable; written \(\sigma\). (Ch. 1)
independence — events (or random variables) are independent if the probability of their joint occurrence is the product of the individual probabilities; it is a property of how they are drawn, not of their content. (Ch. 1)
covariance — \(\operatorname{Cov}(X,Y)=\mathbb E[(X-\mathbb E X)(Y-\mathbb E Y)]\); zero for independent variables, but zero covariance does not imply independence. (Ch. 1)
i.i.d. — independent and identically distributed: mutually independent draws that all have the same distribution. (Ch. 1)
conditional probability — \(\Pr(A\mid B)=\Pr(A\cap B)/\Pr(B)\), the probability of \(A\) once we know that \(B\) happened. (Ch. 1)
law of total probability — \(\Pr(A)=\sum_k \Pr(A\mid B_k)\Pr(B_k)\) for disjoint cases \(B_k\) covering everything; so a bound that holds in every case holds overall. (Ch. 1)
conditional expectation — \(\mathbb E[Y\mid X=x]\), the average of \(Y\) over outcomes with \(X=x\); \(\mathbb E[Y\mid X]\) is the resulting random function of \(X\). (Ch. 1)
tower rule — \(\mathbb E[\mathbb E[Y\mid X]]=\mathbb E[Y]\): averaging the group averages gives the overall average. (Ch. 1)
density — for a continuous random variable, the curve whose area over an interval gives the probability of that interval. (Ch. 1)
normal (Gaussian) distribution — the bell-shaped continuous distribution \(\mathcal N(\mu,\sigma^2)\) with mean \(\mu\) and variance \(\sigma^2\). (Ch. 1)
population — the collection of items we draw from (here a finite list; Chapter 15 widens it to a data-generating process). (Ch. 1)
sample mean — the average \(\bar X_n=\frac1n\sum_i X_i\) of \(n\) draws; for i.i.d. draws it has mean \(\mu\) and variance \(\sigma^2/n\). (Ch. 1)
sampling with replacement — drawing an item, putting it back, and drawing again; the draws are i.i.d. and repeats are possible. (Ch. 1)
sampling without replacement — drawing items without putting them back; each draw is uniform on its own, but the draws are dependent. (Ch. 1)
finite-population correction — the factor \((N-n)/(N-1)\) by which sampling without replacement shrinks the variance of the sample mean. (Ch. 1)
fixed vs random — the discipline of sorting every symbol in a probability statement into what depends on the experiment's outcome (random) and what was settled beforehand (fixed). (Ch. 1)
with probability at least 1 − δ — the statement fails for at most a fraction \(\delta\) of repetitions of the whole data collection; it is not a probability about one already-observed dataset. (Ch. 1)
failure probability — the number \(\delta\) in "with probability at least \(1-\delta\)" (the paper's code uses 0.05). (Ch. 1)
Markov's inequality — for \(X\ge0\) and \(a>0\), \(\Pr(X\ge a)\le\mathbb E[X]/a\). (Ch. 1)
Chebyshev's inequality — \(\Pr(|X-\mathbb E X|\ge t)\le\operatorname{Var}[X]/t^2\); for a sample mean of \(n\) i.i.d. draws, \(\le\sigma^2/(nt^2)\). (Ch. 1)
law of large numbers — the sample mean of i.i.d. draws gets arbitrarily close to the expectation with probability tending to 1 as the number of draws grows. (Ch. 1)

Chapter 2 — Learning from examples¶

Defined in Chapter 2.

memorization (memorize; parroting, regurgitating) — A hypothesis storing individual training examples so that it can reproduce them, instead of (or as well as) capturing a rule behind them; for language models, reproducing training text word for word is called parroting or regurgitating. (Ch. 2)
generalization (generalize) — Doing well on fresh examples from the same data-generating process, not merely on the training examples; measured by the expected risk. (Ch. 2)
training set (training data) — The list of \(m\) examples \(X_1,\dots,X_m\) that the learner uses to choose its hypothesis; assumed to be i.i.d. draws from the data-generating process. (Ch. 2)
model — A recipe for making predictions that leaves some numbers (its parameters) open; fixing all of them, and all hand-chosen settings, gives one hypothesis. (Ch. 2)
generalization bound — A statement "\(R(\hat h)\le\hat R(\hat h)+\varepsilon\) with probability at least \(1-\delta\)" over the random draw of the training set, where the gap term \(\varepsilon\) is computable without knowing the data-generating process and the inequality holds for the hypothesis that training actually chose. (Ch. 2)
vacuous / non-vacuous — In the standard sense a bound is vacuous if it is no better than a statement true without any data (e.g. "error ≤ 100 %"); the paper uses the stricter sense that a bound is vacuous unless it beats random guessing (\(\log_2 V\) bits per token, top-k error \(1-k/V\)). (Ch. 2)
data point (example) — One item the learner sees; in the toy problem an input–label pair \((z,y)\), in the paper a whole document. (Ch. 2)
dataset — A list of examples; the training set is the dataset used for training. (Ch. 2)
data-generating process — The random mechanism (a probability distribution over possible examples) that produces both the training examples and fresh examples; unknown to the learner. Chapter 15 makes it precise for documents. (Ch. 2)
fresh example — One more independent draw \(X\) from the data-generating process, independent of the training set; expected risk is the average loss on it. (Ch. 2)
parameter — One adjustable number in a model, set by training (GPT-2 small has about 124 million). (Ch. 2)
hypothesis — One fully specified prediction rule \(h\): a model with every parameter and every hand-chosen setting fixed. (Ch. 2)
hypothesis space — The set \(\mathcal H\) of all hypotheses a learner is allowed to end up with (e.g. 4 rules, or all \(2^{1000}\) lookup tables in the toy). (Ch. 2)
training — A procedure that takes the training set and returns one hypothesis \(\hat h\) from \(\mathcal H\); because the training set is random, \(\hat h\) is random too. (Ch. 2)
loss — A number \(R(h,X)\) scoring how badly hypothesis \(h\) did on one example \(X\) (lower is better); the paper calls it the "risk" of \(h\) on \(X\). (Ch. 2)
0-1 loss — The loss \(\mathbf 1[h(z)\ne y]\): 1 for a wrong prediction, 0 for a right one. (Ch. 2)
empirical risk (training error) — The average loss over the training set, \(\hat R(h)=\frac1m\sum_{j=1}^m R(h,X_j)\); with the 0-1 loss, the fraction of training examples gotten wrong. (Ch. 2)
expected risk (true error) — The average loss on a fresh example, \(R(h)=\mathbb E_X[R(h,X)]\), with \(h\) held fixed; unknown because the data-generating process is unknown. (Ch. 2)
test set — Fresh examples kept aside and never used for training; their average loss estimates \(R(h)\) for one finished hypothesis. (Ch. 2)
generalization gap — The difference \(R(h)-\hat R(h)\) between expected and empirical risk; it can be negative for a hypothesis fixed in advance. (Ch. 2)
overfitting — Training pushing the empirical risk down in a way that does not carry over to fresh examples, leaving a large generalization gap; a lookup-table memorizer is the extreme case. (Ch. 2)
deterministic vs stochastic predictor — A deterministic predictor is one fixed function (same input, same output; an LLM that outputs a fixed probability distribution counts); a stochastic predictor draws a hypothesis at random from a distribution over \(\mathcal H\), and PAC-Bayes bounds certify its average risk, whereas the paper's bounds certify one deterministically trained model. (Ch. 2)

Chapter 3 — Logarithms, bits and nats¶

Defined in Chapter 3.

logarithm — For a base b > 0 (b ≠ 1) and a positive number y, log_b y is the exponent you must put on b to get y: log_b y = x exactly when b^x = y. It is defined only for y > 0. (Ch. 3)
base-2 logarithm (log2) — The logarithm with base 2; log2 N is the number of fair yes/no answers (bits) needed, on average over long sequences, to name one of N equally likely things. Example: log2 50,257 = 15.617. (Ch. 3)
bit — A binary digit, 0 or 1; also the unit of information equal to the answer to one yes/no question whose two answers are equally likely. Amounts computed with log2 are in bits. (Ch. 3)
power (exponent) — b^n means b multiplied by itself n times (b is the base, n the exponent); extended to b^0 = 1, b^(−n) = 1/b^n and, for b > 0, to every real exponent, so that b^m · b^n = b^(m+n) always holds. (Ch. 3)
exponential function (e^x) and the number e — The function x ↦ e^x, where e = 2.718281828…; it is the one base whose graph has slope equal to its own height (d/dx e^x = e^x). It is always positive and strictly increasing. (Ch. 3)
natural logarithm (ln) — The logarithm with base e, the inverse of e^x. Amounts computed with ln are in nats; the paper's bound (Eq. 1) needs ln because it comes from solving an equation of the form e^(−x) = δ. (Ch. 3)
log rules — log(yz) = log y + log z (product), log(y/z) = log y − log z (quotient), log(y^r) = r log y (power), and log_b y = ln y / ln b (change of base); all follow from the fact that multiplying powers adds exponents. (Ch. 3)
ceiling — ⌈x⌉, the number x rounded up to the nearest whole number; e.g. ⌈15.617⌉ = 16. (Ch. 3)
bits to name one of N things — A fixed-length code (every item gets its own string of the same length) needs ⌈log2 N⌉ bits, because n bits give only 2^n different strings; GPT-2's 50,257 tokens need 16 bits. On average over long sequences, log2 N bits per item suffice. (Ch. 3)
nat — The "natural unit" of information: an amount computed with ln instead of log2. 1 nat = 1/ln 2 = 1.442695 bits. (Ch. 3)
nats↔bits conversion — The same amount of information is (amount in bits) × ln 2 nats, and (amount in nats) / ln 2 bits; 1 bit = 0.693147 nats. Never add a number in bits to a number in nats. (Ch. 3)
surprisal (information content) — The information in an event of probability p: −log2 p bits, or −ln p nats. A certain event has 0, a fair coin outcome 1 bit, and an impossible event (p = 0) has no finite surprisal. (Ch. 3)
byte — 8 bits. (Ch. 3)
kilobyte (KB) — Either 1,000 bytes (8,000 bits) or 1,024 bytes (8,192 bits; also called a kibibyte, KiB); the two differ by 2.4 %. This explainer follows Lotfi et al. (2022): 1 KB = 8192 bits; the 2024 paper does not define KB. (Ch. 3)
ln x ≤ x − 1 — For every x > 0, ln x ≤ x − 1, with equality only at x = 1 (the line x − 1 is the tangent of ln x at x = 1). Key step in Gibbs' inequality and in showing no yes/no strategy beats log2 N questions on average. (Ch. 3)
1 + x ≤ e^x — For every real x, 1 + x ≤ e^x, with equality only at x = 0; the same fact as ln x ≤ x − 1 after substituting x = e^t. (Ch. 3)

Chapter 8 — Linear-algebra toolkit¶

Defined in Chapter 8.

vector — An ordered list of numbers, such as (2, 1); the set of all real vectors with b entries is written ℝ^b. (Ch. 8)
dimension (of a vector) — How many numbers a vector holds; θ ∈ ℝ^D has dimension D. (Ch. 8)
scalar — A single number, as opposed to a vector or matrix; multiplying a vector by a scalar multiplies every entry. (Ch. 8)
matrix — A rectangular table of numbers; the entry in row i and column j of W is written W_ij. (Ch. 8)
shape — The size of a matrix written "rows × columns"; a matrix with a rows and b columns is a × b and lives in ℝ^(a×b). (Ch. 8)
matrix–vector product — For W of shape a × b and v of dimension b, the vector Wv whose i-th entry is the sum over j of W_ij v_j; it is a weighted sum of the columns of W and costs a·b multiplications. (Ch. 8)
linear (map) — A rule that respects sums and scaling, W(v + v′) = Wv + Wv′ and W(cv) = c·Wv; every matrix acts linearly, so it can only form weighted sums. (Ch. 8)
matrix–matrix product — For B of shape a × r and A of shape r × b, the a × b matrix BA with entries (BA)_ij = sum over k of B_ik A_kj; order matters (BA ≠ AB in general) and it costs a·r·b multiplications. (Ch. 8)
associativity — The rule (XY)Z = X(YZ) for matrix products of fitting shapes, which lets brackets be dropped. (Ch. 8)
transpose — The matrix Wᵀ obtained by turning the rows of W into columns, (Wᵀ)_ij = W_ji; transposing a product reverses the order, (XY)ᵀ = YᵀXᵀ. (Ch. 8)
identity matrix — The square matrix I with 1 on the diagonal and 0 elsewhere; multiplying by it changes nothing. (Ch. 8)
dot product — For two vectors of the same dimension, u·v = uᵀv = the sum of the products of matching entries. (Ch. 8)
norm (length) — The length of a vector, ‖v‖ = √(v·v), i.e. Pythagoras' theorem in any number of dimensions. (Ch. 8)
orthogonal (perpendicular) vectors — Two vectors whose dot product is 0. (Ch. 8)
unit vector — A vector of norm 1. (Ch. 8)
cosine of the angle — For nonzero u, v, the number (u·v)/(‖u‖‖v‖), which lies between −1 and 1 and defines the angle between them in any dimension. (Ch. 8)
Cauchy–Schwarz inequality — The fact |u·v| ≤ ‖u‖‖v‖ for any two vectors, which guarantees that the cosine of an angle lies between −1 and 1. (Ch. 8)
orthonormal columns — A matrix Q has orthonormal columns when every column is a unit vector and different columns are orthogonal; this is the same as QᵀQ = I. (Ch. 8)
PᵀP = I (isometric embedding) — If a D × d matrix P satisfies PᵀP = I, then ‖Pw‖ = ‖w‖ and dot products are kept, so P places ℝ^d inside ℝ^D without stretching or squashing; PPᵀ is still not the identity when d < D. (Ch. 8)
trace — The sum of the diagonal entries of a square matrix; trace(XY) = trace(YX). (Ch. 8)
linear combination — A sum c₁y₁ + … + c_k y_k of vectors multiplied by scalars. (Ch. 8)
column space (span) — The set of all linear combinations of a matrix's columns, i.e. all possible outputs Wv. (Ch. 8)
linear independence — Vectors are linearly independent when none is a linear combination of the others; equivalently, only the all-zero combination gives the zero vector. (Ch. 8)
rank — The largest number of linearly independent columns of a matrix: how many genuinely different output directions it has; rank(BA) ≤ min(rank B, rank A). (Ch. 8)
low-rank factorization — Writing W (a × b) as BA with B of shape a × r and A of shape r × b for small r; it stores r(a + b) numbers instead of ab and forces rank ≤ r. (Ch. 8)
upper triangular matrix — A square matrix whose entries below the diagonal are all 0. (Ch. 8)
QR decomposition — Writing a matrix G with independent columns as G = QT, with Q having orthonormal columns and T upper triangular with positive diagonal (textbooks call T "R"); the Q-factor does not depend on the overall scale of G. (Ch. 8)
Gram–Schmidt process — The algorithm that builds the QR decomposition column by column: remove from each column its parts along the earlier unit vectors, then rescale what is left to length 1. (Ch. 8)
block matrix — A matrix viewed as a grid of smaller matrices (blocks) cut out by horizontal and vertical lines. (Ch. 8)
Kronecker product — For M₁ (a₁ × b₁) and M₂ (a₂ × b₂), the (a₁a₂) × (b₁b₂) block matrix M₁ ⊗ M₂ whose block (i, j) is (M₁)_ij · M₂: a "tiled floor" of scaled copies of M₂. (Ch. 8)
mixed-product property — The rule (M₁ ⊗ M₂)(N₁ ⊗ N₂) = (M₁N₁) ⊗ (M₂N₂); with the transpose rule (M₁ ⊗ M₂)ᵀ = M₁ᵀ ⊗ M₂ᵀ it shows that Q₁ ⊗ Q₂ has orthonormal columns whenever Q₁ and Q₂ do. (Ch. 8)
vec (column stacking) — Turning a matrix into one long vector by stacking its columns, first column on top; unvec is the reverse. (Ch. 8)
vec trick — The identity (M₁ ⊗ M₂)·vec(X) = vec(M₂ X M₁ᵀ), which multiplies by a Kronecker product using only its two small factors, so the big matrix never has to be built or stored. (Ch. 8)
Gaussian random matrix — A matrix whose entries are independent normal random variables N(0, σ²) (σ² is the variance); the paper writes N(0,1)^(a×b) for an a × b matrix of standard-normal entries. (Ch. 8)
near-orthogonality (of random high-dimensional vectors) — Two independent random unit vectors in ℝ^D have a cosine with mean 0 and variance exactly 1/D, so in high dimension they are almost always nearly perpendicular; likewise a D × d Gaussian matrix with N(0, 1/D) entries has PᵀP ≈ I with errors of size about 1/√D. (Ch. 8)
central limit theorem — The result (stated, not proved, in this explainer) that a sum of many i.i.d. terms with finite variance, suitably centred and scaled, is approximately normally distributed. (Ch. 8)

Chapter 4 — Language models¶

Defined in Chapter 4.

language model — A model that gives a probability to every piece of text; in practice, for every prefix of text it gives a probability distribution over the next token. (Ch. 4)
large language model (LLM) — A language model with a very large number of parameters (GPT-2 small, the paper's main model, has 124 million), trained on a very large amount of text. (Ch. 4)
text — A sequence of characters. (Ch. 4)
character — One written symbol: a letter, digit, punctuation mark, space, or an invisible symbol such as "new line". Computers store characters as one or more bytes (UTF-8). (Ch. 4)
token — The unit a language model reads and predicts: a short piece of text such as a single byte, part of a word, a whole word (in GPT-2 usually with its leading space), or punctuation. (Ch. 4)
vocabulary (V) — The fixed, finite list of all tokens a model can use; its size is V. GPT-2's tokenizer has V = 50,257 (a value the paper never prints, erratum E36). (Ch. 4)
token id — The position number of a token in the vocabulary, a whole number from 0 to V − 1; the model sees only ids, never letters. (Ch. 4)
tokenizer — The fixed program that cuts text into tokens and replaces them by ids, and turns ids back into text; it is chosen before training and never changes. (Ch. 4)
end-of-text token (<|endoftext|>) — A special token (GPT-2 id 50,256) that marks where one document ends and the next begins; nanoGPT appends it after every OpenWebText document. (Ch. 4)
OpenWebText — The public collection of web pages on which the paper trains and evaluates; nanoGPT's training split has 8,009,762 documents and 9,035,582,198 GPT-2 tokens. (Ch. 4)
byte-pair encoding (BPE) — The method that builds a tokenizer's vocabulary: start from single bytes, then repeatedly merge the most frequent pair of neighbouring tokens into a new token. GPT-2 used 50,000 merges: 256 + 50,000 + 1 = 50,257 tokens. (Ch. 4)
chain rule of probability — For any distribution over sequences, p(x_1, …, x_L) = ∏i p(x_i | x<i): the probability of the whole is the product of each element's probability given all earlier ones. It assumes no independence. (Ch. 4)
autoregressive model — A model that predicts each element of a sequence from the elements before it; an autoregressive language model outputs a next-token distribution for every prefix and, when writing, feeds its own outputs back in. (Ch. 4)
next-token prediction — The training task of language models: at every position of real text the model gives a distribution for the next token and is scored by the probability (surprisal) of the token that actually came next. (Ch. 4)
logits — The real numbers, one per vocabulary token, that a network computes before softmax; a larger logit means a more favoured token. Only differences between logits matter. (Ch. 4)
softmax — The function turning logits z into probabilities, softmax(z)_v = e^(z_v) / Σ_u e^(z_u). Its outputs are positive and sum to 1, and adding a constant to all logits does not change them. (Ch. 4)
context window (L_ctx) — The largest number of previous tokens a model can use to predict the next one; 1,024 for the paper's GPT-2 models. (Ch. 4)
bigram model (n-gram model) — A language model whose context window is one token: it predicts the next token from the previous one only (an n-gram model uses the previous n − 1 tokens). The best bigram model for a text is obtained by counting pairs. (Ch. 4)
sampling (text generation) — Writing text by repeatedly drawing the next token at random from the model's distribution and appending it. (Ch. 4)
temperature (T) — A positive number by which the logits are divided before softmax when sampling; T < 1 sharpens the distribution, T > 1 flattens it. The paper samples its example texts at T = 0.8; its bounds use T = 1. (Ch. 4)
greedy decoding (argmax decoding) — Generating text by always choosing the single most probable next token; the T → 0 limit of sampling. It can loop and does not always find the most probable sequence. (Ch. 4)

Chapter 5 — Transformers and GPT-2¶

Defined in Chapter 5.

neural network — A function built by chaining many simple steps (layers), each with its own adjustable parameters; the output of one step is the input of the next. (Ch. 5)
layer — One step of a neural network; in a transformer the word also names one whole transformer block (the paper's "12 layers" counts blocks). (Ch. 5)
linear layer — A step u ↦ Wu + c with a weight matrix W (a × b) and a bias c (length a); it has ab + a parameters (ab without bias). (Ch. 5)
weight matrix — The matrix W of a linear layer; its entries are parameters. (Ch. 5)
bias — The vector c added at the end of a linear layer (or the shift of a LayerNorm); also parameters. (Ch. 5)
activation function — A non-linear function applied entry by entry between linear layers, so that the network is not just one big matrix. (Ch. 5)
GELU — The activation used by GPT-2: GELU(t) = t·Φ(t), where Φ(t) = Pr[Z ≤ t] for a standard normal Z; about 0 for very negative t, about t for large t. (Ch. 5)
embedding — A learned table with one vector per item; the token embedding W_E has one row of length d_model per vocabulary entry. (Ch. 5)
position embedding — A learned table with one row per position 1…L_ctx, added to the token's embedding so the network knows where each token sits. (Ch. 5)
padded vocabulary — nanoGPT's habit of enlarging the embedding table from 50,257 to 50,304 rows (a multiple of 64) for speed; the 47 extra rows are never the correct token. (Ch. 5)
residual stream — The vector of length d_model kept for every position and passed from block to block; each block adds its output to it instead of replacing it. (Ch. 5)
layer normalization (LayerNorm) — Rescaling one vector so its entries have average 0 and variance 1, followed by a learned gain and shift (2·d_model parameters). (Ch. 5)
self-attention — The step in which every position takes a weighted average of value vectors of positions in the same sequence, with weights from softmax of query·key scores divided by √d_head. (Ch. 5)
query, key, value — Three vectors computed from each position by the matrices W_Q, W_K, W_V: what the position looks for, what it offers, and the content it hands over. (Ch. 5)
attention weights — The softmax of one row of masked attention scores; non-negative and summing to 1. (Ch. 5)
causal mask — Setting the attention scores of later positions to −∞ so that each position can use only itself and earlier positions; it makes the transformer autoregressive. (Ch. 5)
attention head — One copy of the query–key–value machinery with its own matrices, working on d_head = d_model / n_head numbers (64 in GPT-2). (Ch. 5)
multi-head attention — Several heads run side by side; their outputs are stacked and multiplied by the output projection W_O. (Ch. 5)
output projection — The d_model × d_model matrix W_O that mixes the stacked head outputs before they are added to the residual stream. (Ch. 5)
MLP block — The per-position two-layer network of a transformer block: widen d_model → 4·d_model, apply GELU, narrow back to d_model. (Ch. 5)
transformer block — The repeated unit: residual add of multi-head attention (after LayerNorm), then residual add of the MLP (after LayerNorm). (Ch. 5)
transformer — A network made of an embedding, a stack of transformer blocks and an output layer. (Ch. 5)
linear head (unembedding) — The final matrix (V × d_model) that turns each final stream vector into V logits. (Ch. 5)
weight tying — Using the token-embedding matrix also as the linear head, so one table both encodes input tokens and scores output tokens and is counted once. (Ch. 5)
GPT-2 (small / medium / large) — OpenAI's 2019 family of transformer language models; small = 12 layers × 768, medium = 24 × 1,024, large = 36 × 1,280 (124M, 354M, 773M in nanoGPT's count). (Ch. 5)
nanoGPT — Andrej Karpathy's short public PyTorch re-implementation of GPT-2 training, which the paper follows; its parameter count uses the padded vocabulary, counts the tied head once and leaves out the position embedding. (Ch. 5)

Chapter 6 — Measuring a language model¶

Defined in Chapter 6.

log-loss — The charge a model pays on one token: the surprisal of the real token under the model, \(-\log_2 p_\theta(x_i \mid x_{<i})\) bits (or \(-\ln\) in nats). It is 0 for a certain prediction and has no upper limit. (Ch. 6)
likelihood — The probability a model gives to an observed document, \(p_\theta(X)=\prod_i p_\theta(x_i \mid x_{<i})\), viewed as a score of the model (higher is better). (Ch. 6)
log-likelihood — The logarithm of the likelihood; in bits with \(\log_2\), in nats with \(\ln\). (Ch. 6)
negative log-likelihood (NLL) — Minus the log-likelihood: the sum of a document's per-token log-losses, in bits or nats (nats = bits × ln 2). The paper also uses "NLL" as a name for BPD; its Table 2 "Validation NLL" is in nats per token. (Ch. 6)
bits per dimension (BPD), bits per token — A document's NLL in bits divided by its number of tokens, \(-\frac1L\sum_i\log_2 p_h(x_i \mid x_{<i})\); the paper's main loss. "Dimension" (from image modelling) means one token here. BPD × ln 2 = nats per token. (Ch. 6)
perplexity — \(2^{\mathrm{BPD}} = e^{\text{nats per token}}\), the inverse geometric mean of the probabilities given to the real tokens; "as unsure as a uniform choice among this many tokens". Not used by the paper. (Ch. 6)
cross-entropy — The expected log-loss of a model \(p\) when the real token is drawn from a distribution \(q\): \(H(q,p)=\sum_v q(v)\log_2\frac1{p(v)}\) bits. It is at least the entropy \(H(q)\) (Gibbs' inequality), with equality only for \(p=q\). (Ch. 6)
top-k prediction set — The \(k\) tokens to which the model gives the highest probabilities after a given prefix (its \(k\) favourite guesses). (Ch. 6)
top-k error — For one token, the 0-1 loss "the real token is not in the top-k set"; for a document, the fraction of its tokens with this loss. A bounded loss in \([0,1]\); top-1 error uses only the argmax. It ignores how much probability the real token got. (Ch. 6)
document-level average — Average each document's per-token loss over its own tokens, then average over documents with equal weight; the average the paper's bound uses. (Ch. 6)
token-level average — Pool all tokens of all documents and average them, so long documents weigh more; it differs from the document-level average by \(\mathrm{Cov}(L,\mathrm{BPD})/\bar L\). (Ch. 6)
random-guess baseline — The score of a predictor that learned nothing: the uniform predictor has BPD \(\log_2 V\) (15.617 for GPT-2's \(V=50{,}257\)), and a uniformly random ranking has expected top-k error \(1-k/V\). The paper calls a bound vacuous if it is not below these levels. (Ch. 6)
unbounded loss — A loss with no finite upper limit. The log-loss is one: \(-\log_2 p\to\infty\) as \(p\to0\), so a single token can dominate a document's BPD, and a probability rounded to 0 makes it infinite. Bounds such as Eq. (1) need a loss inside a known interval, which prediction smoothing provides. (Ch. 6)

Chapter 7 — Training neural networks¶

Defined in Chapter 7.

training objective — The function 𝓛(θ) that training minimizes, usually the empirical risk viewed as a function of the parameters θ. (Ch. 7)
derivative — The slope of a function of one number, f′(x) = lim (f(x+ε) − f(x))/ε; for small ε, f(x+ε) ≈ f(x) + f′(x)ε. (Ch. 7)
partial derivative — The derivative of a function of several numbers with respect to one of them while all others are held fixed, written ∂𝓛/∂θ_k. (Ch. 7)
gradient — The vector ∇𝓛(θ) of all partial derivatives; it points in the direction in which the loss rises fastest, and is zero at a lowest point. (Ch. 7)
gradient descent (GD) — Training by repeating θ ← θ − η∇𝓛(θ): compute the slope, step against it, repeat. (Ch. 7)
learning rate — The positive number η that scales each gradient-descent step; too small is slow, too large overshoots and can make the loss explode. (Ch. 7)
minibatch — A small random set of training examples whose average gradient is used in place of the full-data gradient; its size is the batch size (8 sequences in the paper). (Ch. 7)
stochastic gradient descent (SGD) — Gradient descent that uses a fresh random minibatch's gradient at every step; that gradient is right on average, with noise shrinking like 1/(batch size). (Ch. 7)
epoch — One full pass through the training set, e.g. 50 steps for 400 examples in minibatches of 8; the paper samples batches with replacement, so its pretraining has no clean epochs. (Ch. 7)
momentum — Stepping along a running (exponentially weighted) average of recent gradients instead of the latest one, which smooths out noise and zig-zags. (Ch. 7)
Adam — An optimizer that combines momentum with a per-parameter step size, dividing the bias-corrected average gradient by the square root of the average squared gradient, so each parameter moves by about the learning rate per step. (Ch. 7)
weight decay — Shrinking every trained parameter toward 0 by a factor (1 − ηλ) at each step; in subspace training it pulls w toward 0, i.e. θ toward θ₀. (Ch. 7)
AdamW — Adam with decoupled weight decay: the shrink factor is applied directly to the parameters rather than added to the gradient; the paper's optimizer (λ = 10⁻², ε = 10⁻⁶). (Ch. 7)
chain rule (calculus) — The rule that rates of change multiply along a chain of functions; for θ = f(w), ∂𝓛/∂w_i = Σ_k (∂𝓛/∂θ_k)(∂θ_k/∂w_i), i.e. ∇_w𝓛 = J_f(w)ᵀ∇_θ𝓛. (Ch. 7)
backpropagation — Computing the gradient of the loss with respect to every parameter by applying the chain rule from the loss backward through the layers, reusing intermediate results; it costs a small multiple of one loss evaluation. (Ch. 7)
finite-difference check — Estimating a partial derivative as (𝓛(θ + h e_k) − 𝓛(θ − h e_k))/(2h) for small h, used to test gradient code. (Ch. 7)
reparameterization — Writing the parameters as a function of other numbers, θ = f(w), and training w instead; for θ = θ₀ + Pw the gradient is ∇_w𝓛 = Pᵀ∇_θ𝓛, and only points of the form θ₀ + Pw can be reached. (Ch. 7)
Jacobian matrix — For a map θ = f(w), the matrix J_f(w) of all partial derivatives ∂θ_k/∂w_i; for θ = θ₀ + Pw it is P. (Ch. 7)
random initialization — Choosing a network's starting parameters θ₀ by drawing each one at random (typically from a normal distribution with small variance), which breaks the symmetry between units. (Ch. 7)
pseudo-random number generator (PRNG) — A deterministic algorithm whose outputs look random but are fully determined by its starting state; the algorithm itself is part of any "seed-only" description. (Ch. 7)
seed — The number that sets a pseudo-random generator's starting state; the same seed and generator reproduce the same numbers bit for bit, so 8 bytes can stand for millions of random numbers (Ch. 8 introduces it briefly). (Ch. 7)
flatten / unflatten — Writing all of a network's weight matrices and biases one after another into a single vector of length D, and cutting that vector back into pieces of the original shapes. (Ch. 7)
pretraining — Training a model from a random initialization on a large general dataset (for the paper, next-token prediction on OpenWebText). (Ch. 7)
fine-tuning — Continuing to train an already pretrained model on a smaller task-specific dataset, usually for fewer steps and with a small learning rate. (Ch. 7)
hyperparameter — Any setting chosen outside gradient descent (learning rate, batch size, number of steps, d, r, α, number of quantization levels…); only those needed to compute predictions must be paid for in the bound. (Ch. 7)
validation data — Examples held out from training and used to measure performance on unseen data and to compare hyperparameter settings; the paper's bound does not use them. (Ch. 7)
logistic regression — A model for yes/no labels that predicts Pr[label = 1] as σ(θ·x) = 1/(1 + e^(−θ·x)) and is trained on log-loss. (Ch. 7)

Chapter 9 — Hoeffding's inequality¶

Defined in Chapter 9.

tail probability — the probability that a random quantity lands far out on one side of its expected value, e.g. the chance that the empirical risk falls at least t below the expected risk. (Ch. 9)
concentration inequality — a theorem that puts an upper limit on a tail probability; it says an average of many random numbers stays close to its expected value, and how close. (Ch. 9)
Hoeffding's inequality — for independent random variables each confined to a fixed interval, the chance that their sum overshoots (or undershoots) its expected value by ε is at most exp(−2ε²/Σ(widths²)); for an average of m variables with width Δ, the chance of falling t below the mean is at most exp(−2mt²/Δ²). The two-sided version doubles the right side. (Ch. 9)
Bernoulli(p) variable — a random variable that equals 1 with probability p and 0 otherwise, like a coin with bias p; a fair coin is Bernoulli(0.5). (Ch. 9)
moment generating function (MGF) — the function λ ↦ E[e^{λY}] of a random variable Y; its derivatives at λ = 0 are the moments E[Y], E[Y²], …, and for independent variables the MGF of a sum is the product of the MGFs. (Ch. 9)
Chernoff method — a way to bound a tail probability Pr(Y ≥ c): exponentiate (Y ≥ c exactly when e^{λY} ≥ e^{λc} for λ > 0), apply Markov's inequality to get e^{−λc}E[e^{λY}], then choose the λ that makes this smallest. (Ch. 9)
convex function — a function whose graph lies on or below the straight segment (chord) joining any two of its points, i.e. a bowl-shaped curve such as e^x or x². (Ch. 9)
Jensen's inequality — for a convex function f and a random variable Y, f(E[Y]) ≤ E[f(Y)]: averaging first and then applying f gives a smaller number than applying f first and then averaging. (Ch. 9)
Hoeffding's lemma — if a random variable Z always lies in [a, b] and has expected value 0, then E[e^{λZ}] ≤ exp(λ²(b−a)²/8) for every real λ; it treats Z as if it had the largest variance possible on that interval. (Ch. 9)

Chapter 10 — The union bound¶

Defined in Chapter 10.

multiple comparisons — the problem that running many tests and reporting the one that "worked" makes a false discovery likely: 20 independent tests at a 5 % false-alarm rate give at least one false alarm with probability 0.6415. (Ch. 10)
Bonferroni correction — the standard repair for multiple comparisons: with N tests, demand a false-alarm rate of δ/N from each, so that the chance of any false alarm is at most δ (by the union bound). (Ch. 10)
data-dependent hypothesis — a hypothesis produced from the training set, ĥ = train(X₁, …, X_m); it is random because the training set is random, so Hoeffding's inequality for a fixed hypothesis does not apply to it directly. (Ch. 10)
selection bias — the systematic error that arises when the same data are used both to choose an item and to evaluate it; in learning, the trained hypothesis's empirical risk tends to underestimate its expected risk. (Ch. 10)
winner's curse — selection bias seen from the winner's side: the best-looking of many candidates is, on average, worse than it looks (e.g. the best of 1,000 coin-flip classifiers has mean training error 0.339 but true error 0.5). (Ch. 10)
empirical risk minimization — the training rule "return a hypothesis with the smallest empirical risk"; for it, E[R̂(ĥ)] ≤ min_h R(h) ≤ E[R(ĥ)]. (Ch. 10)
union bound — for any events E₁, E₂, … (no independence needed), Pr[at least one happens] ≤ Pr[E₁] + Pr[E₂] + …; exact for disjoint events, loose for overlapping ones. (Ch. 10)
bad event — for a fixed hypothesis h and margin t(h), the event E_h = {R(h) ≥ R̂(h) + t(h)} that its bound fails; it is an event about the random training set. (Ch. 10)
simultaneous (uniform) guarantee — a statement that, with probability at least 1 − δ, an inequality holds for every hypothesis in the class at once (one good event for all), so it also holds for whichever hypothesis training returns. (Ch. 10)
Occam bound — for a finite class fixed in advance and a loss in an interval of width Δ: with probability at least 1 − δ, R(h) < R̂(h) + Δ·√((ln|H| + ln(1/δ))/(2m)) for every h ∈ H; the uniform-prior special case of the paper's Eq. (1). (Ch. 10)
log of the hypothesis count — ln|H| (in nats), equal to log₂|H| · ln 2 where log₂|H| is the number of bits needed to name one hypothesis; the price of choosing in the Occam bound and the simplest complexity measure. (Ch. 10)
float32 — single-precision floating-point number: the standard 32-bit pattern a computer uses to store one real-valued parameter; a network with D float32 parameters is one of at most 2^(32D) bit patterns. (Ch. 10)

Chapter 11 — Priors and Eq. (1)¶

Defined in Chapter 11.

prior — a rule giving every hypothesis h a weight P(h) ≥ 0, with the weights adding up to at most 1, fixed before the training data are seen; it need not express a belief, it only shares out the failure budget δ. (Ch. 11)
price of a hypothesis (ln 1/P(h)) — the surprisal of h under the prior, in nats (log₂ 1/P(h) in bits); the amount Eq. (1) charges for having chosen h; with a uniform prior it equals ln|H|. (Ch. 11)
confidence parameter δ — the failure probability chosen in advance; a bound "with probability at least 1 − δ" fails in at most a fraction δ of repetitions of the data collection; 1 − δ is the confidence level (the paper's code uses δ = 0.05). (Ch. 11)
prior-weighted union bound — if each event E_h has Pr[E_h] ≤ P(h)δ and the P(h) add up to at most 1, then Pr[some E_h happens] ≤ δ; the union bound with unequal shares of δ fixed in advance. (Ch. 11)
Theorem A.1 — the paper's finite-hypothesis bound: for losses in an interval of width Δ, i.i.d. examples and a prior P fixed before the data, with probability at least 1 − δ, R(h) ≤ R̂(h) + Δ·√((ln 1/P(h) + ln 1/δ)/(2m)) for every h at once, hence for the trained ĥ. (Ch. 11)
Eq. (1) — the main-text statement of Theorem A.1 (identical to the appendix's Eq. 5); its "log" is the natural log. (Ch. 11)
complexity term — the second term of Eq. (1), Δ·√((ln 1/P(h) + ln 1/δ)/(2m)), in the units of the loss; it grows like the square root of the price and shrinks like 1/√m. (Ch. 11)
cheating prior — weights chosen after seeing the training data (e.g. weight 1 on the trained model); they may add up to 1 but break the proof, and the resulting "bound" can fail far more often than δ (93.57 % of runs in Ch. 11's toy). (Ch. 11)
structural risk minimization — the training rule "return the hypothesis with the smallest bound", trading training error against the hypothesis's price. (Ch. 11)
posterior — in PAC-Bayes, a probability distribution Q over hypotheses chosen after seeing the data; the predictor draws its hypothesis from Q. (Ch. 11)
Kullback–Leibler (KL) divergence — KL(Q‖P) = Σ_h Q(h) ln(Q(h)/P(h)) nats, a measure of how far Q is from P; for a point mass on h it equals ln 1/P(h). (Ch. 11)
finite-hypothesis bound vs PAC-Bayes — Eq. (1) certifies one deterministic hypothesis and charges ln 1/P(ĥ); a PAC-Bayes bound certifies the average risk of a hypothesis drawn from a posterior Q and charges KL(Q‖P); a point-mass posterior turns the second into (a slightly looser version of) the first. (Ch. 11)

Chapter 12 — Codes and the Kraft inequality¶

Defined in Chapter 12.

compressor — a fixed program that turns a file (here: a trained model) into a string of bits, together with a matching decompressor that turns those bits back into exactly the same file. (Ch. 12)
prefix-free code — a code in which no codeword is the beginning (prefix) of a different codeword, so a reader can tell where each codeword ends without separators. Also called an instantaneous or self-delimiting code. (Ch. 12)
Kraft inequality — for any prefix-free code, the sum over all codewords of 2^(−length) is at most 1; proved by noting that the events "fair coin flips begin with codeword s" are disjoint and have probability 2^(−length of s). (Ch. 12)
alphabet — a finite set of symbols from which strings are built; in this explainer usually the binary alphabet {0, 1}. (Ch. 12)
binary string — a finite sequence of 0s and 1s, such as 0110; the empty string (no symbols) also counts. (Ch. 12)
length of a string — the number of symbols in a string s, written |s|; there are exactly 2^ℓ binary strings of length ℓ. (Ch. 12)
concatenation — writing one string directly after another; the length of the result is the sum of the two lengths. (Ch. 12)
prefix — a string s is a prefix of t if t begins with s (t = s followed by something, possibly nothing). (Ch. 12)
code — a fixed rule that assigns each object of a set (letters, numbers, trained models) its own binary string, with different objects getting different strings. (Ch. 12)
codeword — the binary string that a code assigns to one particular object. (Ch. 12)
code length — the number of bits in an object's codeword, written ℓ(x). (Ch. 12)
uniquely decodable code — a code for which any sequence of codewords written back to back can be split into codewords in only one way. Every prefix-free code is uniquely decodable, but not every uniquely decodable code is prefix-free (e.g. {0, 01}). (Ch. 12)
instantaneous code — another name for a prefix-free code: the decoder can announce each object the moment its last bit arrives, without looking ahead. (Ch. 12)
self-delimiting — describes a codeword or message that marks its own end, so it can be followed directly by other data; a prefix-free code is self-delimiting. (Ch. 12)
Kraft sum — the quantity Σ 2^(−ℓ(x)) over all codewords of a code; the Kraft inequality says it is at most 1 for prefix-free (and, by McMillan, uniquely decodable) codes. (Ch. 12)
converse of the Kraft inequality — if whole numbers ℓ₁, ℓ₂, … satisfy Σ 2^(−ℓᵢ) ≤ 1, a prefix-free code with exactly these codeword lengths exists. (Ch. 12)
canonical code — the prefix-free code built from a sorted list of lengths by giving the i-th codeword the binary digits of the running total of earlier shares 2^(−ℓⱼ); it proves the converse of Kraft. (Ch. 12)
McMillan's theorem — every uniquely decodable code also satisfies the Kraft inequality, so dropping prefix-freeness never allows shorter codewords. (Ch. 12)
code → prior — turning a prefix-free code fixed before the data into a prior by setting P(h) = 2^(−ℓ(h)); then ln 1/P(h) = ℓ(h)·ln 2 nats, i.e. code length in bits equals surprisal under the prior. (Ch. 12)
sub-probability — non-negative weights that add up to at most 1 (rather than exactly 1); enough for a prior in the paper's bounds. (Ch. 12)
unary code — the prefix-free code that writes a whole number n ≥ 1 as n − 1 zeros followed by a 1 (n bits). (Ch. 12)
Elias gamma code — a prefix-free code for whole numbers n ≥ 1: write n in binary and put ⌊log₂ n⌋ zeros in front, for 2⌊log₂ n⌋ + 1 bits in total (e.g. 13 → 0001101). (Ch. 12)
Elias delta code — like Elias gamma, but the number of binary digits of n is itself sent in gamma code; about log₂ n + 2 log₂ log₂ n bits, shorter than gamma for large n. (Ch. 12)
length header — a self-delimiting code for a message's length (e.g. Elias gamma of C) placed in front of a C-bit message so the whole description becomes prefix-free whatever compressor produced it. (Ch. 12)
"+2 log C" term — the paper's cost for the length header: a C-bit compressed model is charged C + 2 log₂ C bits, i.e. C ln 2 + 2 ln C nats in the bound (§4.1; the exact Elias-gamma cost is 2⌊log₂ C⌋ + 1 bits). (Ch. 12)
Sardinas–Patterson test — an exact algorithm that decides whether a finite code is uniquely decodable by following the leftover ("dangling") bits when one codeword is a prefix of another. (Ch. 12)
length prior — a prior built as P(h) = Q(C(h))·2^(−C(h)) from weights Q on message lengths that sum to at most 1; with Q(c) = 1/c² (c ≥ 2) it gives exactly the paper's C ln 2 + 2 ln C. (Ch. 12)

Chapter 13 — Kolmogorov complexity¶

Defined in Chapter 13.

computer (machine) — a fixed procedure that reads an input string, follows instructions, and either halts with an output string or runs forever. (Ch. 13)
halt — for a computer, to stop running and leave an output; some programs never halt. (Ch. 13)
program — an input string p fed to a fixed computer U; we write U(p) = x if U, run on p, halts with output x. Its length |p| is measured in bits. (Ch. 13)
description — any program that makes a fixed computer print a given string x; a string has many descriptions, short and long. (Ch. 13)
description language — the choice of computer U, which fixes which strings are programs and what they print (e.g. Python 3). (Ch. 13)
universal computer — a computer that can imitate every other computer T when given a fixed interpreter string for T in front of T's program; every general-purpose programming language is universal in this sense. (Ch. 13)
interpreter — a fixed string i_T such that the universal computer, reading i_T followed by p, behaves exactly like computer T on p. (Ch. 13)
Kolmogorov complexity (plain) — the length in bits of the shortest program that prints x on a fixed universal computer that is told where the program ends; its weights 2^(−K) add up to infinity, so it cannot be turned into a prior. (Ch. 13)
prefix machine — a computer that reads its program bit by bit with no end marker and must decide by itself when to stop reading; the programs on which it halts form a prefix-free set. (Ch. 13)
prefix Kolmogorov complexity K(x) — the length in bits of the shortest self-delimiting program that prints x on a fixed universal prefix machine; the K of the paper and of this explainer. (Ch. 13)
conditional Kolmogorov complexity K(x | y) — the length of the shortest program that prints x when y is given to the computer for free; in the paper y is the architecture (and, per Lotfi et al. 2022, the random seeds and the decompression method). (Ch. 13)
invariance theorem — for any two universal prefix machines U and V there is a constant c such that |K_U(x) − K_V(x)| ≤ c for every string x; proved by putting an interpreter of one machine in front of the other's programs. (Ch. 13)
counting argument (incompressible strings) — fewer than 2^(n−c) programs are shorter than n − c bits, so fewer than a 2^(−c) fraction of n-bit strings can be described c or more bits shorter than themselves; most strings are incompressible. (Ch. 13)
incompressible string — a string whose shortest description is not much shorter than the string itself (K(x) close to its length); almost all long strings are like this. (Ch. 13)
incomputability of K — no program can take an arbitrary string and output its Kolmogorov complexity; proved with the Berry paradox (a short program searching for the first string of complexity ≥ n would itself describe it). (Ch. 13)
Berry paradox — "the smallest number not describable in fewer than twenty words", which has just been so described; with programs in place of words it becomes the proof that K is incomputable. (Ch. 13)
compressor as an upper bound on K — for any fixed, decodable compression scheme, K(x) ≤ compressed length + 2⌊log₂ (compressed length)⌋ + 1 + length of the decoder (bits); computable, but possibly very loose (e.g. 12,370× for a seeded Gaussian initialization in the Ch. 13 demo). (Ch. 13)
universal prior (Solomonoff prior) — the prior P(h) = 2^(−K(h|𝒜))/Z that halves a hypothesis's weight for every extra bit of its shortest description; it gives ln 1/P(h) ≤ K(h|𝒜)·ln 2 nats. (Ch. 13)
normalizer Z — the sum Σ 2^(−K(h)) over all hypotheses; Z ≤ 1 by the Kraft inequality because shortest self-delimiting programs form a prefix-free set, so dividing by Z can only increase each weight. (Ch. 13)
Occam's razor (quantified) — "prefer the simplest explanation" read as "prefer the shortest description": under the universal prior each extra bit of description halves the prior weight. (Ch. 13)
conditioning on the architecture — giving the decoder everything fixed before training (architecture, random seeds, decompression program, hyperparameter grid) for free, so only what training changed is paid for in bits; written K(h | 𝒜). (Ch. 13)
halting problem — the task of deciding, for every program and input, whether the program eventually halts; no program can do it (Turing), and computing K would require it. (Ch. 13)
universal distribution m(x) — Solomonoff's weighting of every program for x, m(x) = Σ 2^(−|p|) over programs p printing x; it is at least 2^(−K(x)) and, by the coding theorem, at most a constant factor more. (Ch. 13)

Chapter 14 — Compressed size as complexity¶

Defined in Chapter 14.

compressed size C(h) — the number of bits in the message that a compressor fixed before training (together with its decompressor, the architecture, the seeds and the hyperparameter grid) outputs for the hypothesis h; in the paper, the arithmetic-coded quantized subspace weights (best GPT-2 model: 16.5325 KB = 135,434 bits). (Ch. 14)
compression prior inequality — the paper's ln 1/P(h) ≤ K(h|𝒜) ln 2 ≤ C(h) ln 2 + 2 ln C(h) (§4.1); with the length prior P(h) = C^(−2)·2^(−C) it holds with equality: C ln 2 nats for the message plus 2 ln C nats for the length header. (Ch. 14)
hyperparameter bits — the log₂ N bits (ln N nats) paid to name which of N hyperparameter settings, listed before training, a model uses; equivalent to a union bound over the grid; the paper's App. E grid has 6·2·3·8·2 = 576 settings, i.e. 9.17 bits. (Ch. 14)
compression bound — Eq. (1) with the compression prior: with probability at least 1 − δ over the m documents, R(h) ≤ R̂(h) + Δ·√((C(h) ln 2 + 2 ln C(h) + ln N + ln 1/δ)/(2m)) for every hypothesis the decoder can produce, in particular the trained compressed model; it certifies the quantized, decoded model, not the network before compression. (Ch. 14)
finite-hypothesis-space Note — the paper's remark (App. A.1, p. 13) that real networks are finite programs with finitely many floating-point values, so finite-hypothesis bounds apply; and that the bound should be read through prior weights rather than by counting hypotheses, since the compression prior's price depends only on the length of the message actually sent. (Ch. 14)
complexity budget — the largest compressed size C for which a given empirical risk plus the complexity term stays below a target (e.g. log₂ V = 15.617 bits/token); 76.6–280.7 KB for the paper's setting with an assumed empirical risk of 10.5 bits/token. (Ch. 14)
bits-versus-nats audit — checking that every quantity under the square root of Eq. (1) is in nats; plugging bits in where nats belong inflates the complexity term by at most 1/√(ln 2) = 1.2011 (conservative, still valid), while converting twice shrinks it by √(ln 2) = 0.8326 (not valid). (Ch. 14)

Chapter 15 — Documents, not tokens¶

Defined in Chapter 15.

document (as the i.i.d. unit) — one unit of text in the corpus (in OpenWebText, one web page's tokens ending in the end-of-text token); the paper's example \(X_j\), whose loss is the document's bits per token (or fraction of top-k misses), so all within-document dependence is sealed inside one number. (Ch. 15)
population (of a bound) — the distribution the \(m\) examples are (assumed to be) i.i.d. draws from; \(R(h)\) averages over it, and the bound says nothing about any other distribution. For the document-level bound it is \(\mathcal D\), "a fresh document produced the way the corpus was produced". (Ch. 15)
document-level bound — Eq. (1) or Eq. (3) with whole documents as examples, \(m = 8{,}009{,}762\) for OpenWebText, population \(\mathcal D\); the bound of Tables 1–3. (Ch. 15)
context chunk (sequence) — a run of consecutive tokens whose length equals the context length (1,024), cut from the concatenated corpus without regard to document boundaries. (Ch. 15)
empirical distribution — the distribution of one item picked uniformly at random from a finite list (an item appearing \(r\) times out of \(M\) has probability \(r/M\)); its mean is the list average, and uniform draws with replacement are i.i.d. from it. (Ch. 15)
sequence-level bound — the bound with context chunks as examples (\(m = 8{,}823{,}811\)) and population the empirical distribution of the corpus's chunks (App. B, Table 4); since the model was trained on that corpus, it bounds training-corpus loss, not loss on new text. (Ch. 15)
effective sample size — the number of independent observations whose average would be exactly as variable as the average of the given dependent ones; for a chain with lag-k correlation \(\rho^k\) it is about \(L(1-\rho)/(1+\rho)\). (Ch. 15)
mutual information — \(I(U;W)=\sum p(a,b)\log_2\frac{p(a,b)}{p(a)p(b)}\) bits: how much one symbol tells about another on average; 0 exactly when they are independent. (Ch. 15)

Chapter 16 — Prediction smoothing¶

Defined in Chapter 16.

mixture distribution — for two distributions q₁, q₂ over the same outcomes and a weight α in [0, 1], the distribution (1 − α)q₁ + αq₂; it is again a probability distribution, and can be read as "with probability α draw from q₂, otherwise from q₁". (Ch. 16)
prediction smoothing — replacing a language model's next-token distribution, at every token and after training, by its mixture with the uniform distribution over the vocabulary: p_h(x_i | x_<i) = (1 − α) p_θ(x_i | x_<i) + α/V (Eq. 2); it puts a floor α/V under every predicted probability and so a ceiling log₂(V/α) on every token's log-loss. (Ch. 16)
smoothed model p_h — the language model produced by prediction smoothing from a base model p_θ and a mixing weight α; a genuine autoregressive model (one can sample from it or compress with it), and the object the paper's BPD bounds actually certify. (Ch. 16)
label smoothing — a training technique that mixes the one-hot training target with the uniform distribution; it changes the trained parameters but guarantees no floor on predicted probabilities. Contrast prediction smoothing, which mixes the outputs after training. (Ch. 16)
worst-case interval size Δ(α) — the width of the interval containing every possible per-token loss (and hence every document BPD) of a prediction-smoothed model: Δ(α) = log₂(1 + (1 − α)V/α) bits per token; 28.905 at α = 0.0001, 17.202 at α = 0.25, log₂(V + 1) = 15.617 at α = 0.5; it multiplies the complexity term of Eq. (1). (Ch. 16)
Theorem A.2 — the paper's statement (App. A.2, Eq. 7) that a prediction-smoothed model's BPD on any document lies in (log₂(V/α) − Δ, log₂(V/α)); proved from p_h ≥ α/V (upper end) and p_h ≤ (1 − α) + α/V = (α/V)(1 + (1 − α)V/α) (lower end), plus "an average of numbers in an interval stays in the interval"; open if 0 < p_θ < 1, closed otherwise (erratum E13). (Ch. 16)
α as a hypothesis parameter — treating the mixing weight as part of the hypothesis h = (θ, d, r, α), so that each value in a grid fixed in advance is a separate hypothesis with its own width Δ(α), paid for in the prior (log₂ 8 = 3 bits for the paper's 8 values); this makes choosing α after training legal. (Ch. 16)
smoothing premium — the extra loss smoothing can add to a token: at most log₂(1/(1 − α)) bits (0.152 at α = 0.1, 1 bit at α = 0.5); tokens the base model gave less than 1/V instead get cheaper. (Ch. 16)
smoothing trade-off — as α grows, Δ(α) shrinks (smaller complexity term) while the premium grows (larger empirical risk for well-predicted tokens); the bound is minimized at an intermediate α (0.25 for the paper's best model). (Ch. 16)
document-level mixture — mixing whole-document probabilities, (1 − α)p_θ(X) + αV^(−L), instead of each token's; it only helps documents whose average loss is worse than uniform guessing, which is why the paper found token-level smoothing more effective. (Ch. 16)

Chapter 17 — The subsampling bound¶

Defined in Chapter 17.

subsample — a list of n random positions σ(1), …, σ(n) in {1, …, m}, drawn after training with randomness independent of the training set; the documents at those positions are used to estimate the training loss cheaply (paper: n = 10,000, drawn with replacement). (Ch. 17)
subsampled empirical risk R̂̂(h) — the average loss of h over the subsampled documents, (1/n) Σᵢ R(h, X_σ(i)); an estimate of the empirical risk R̂(h), which itself estimates R(h). The paper's Eq. (3) prints it without the 1/n (erratum E03). (Ch. 17)
conditional (two-stage) probability statement — a guarantee proved by first holding the training set fixed and bounding a probability over the subsample alone, then averaging over the training set with the law of total probability / tower rule; used for the second term of Eq. (3). (Ch. 17)
δ-splitting — dividing the total failure probability δ among several bad events (here δ₁ = sδ for the training-set stage, δ₂ = (1−s)δ for the subsample stage) whose failures are combined by the union bound; any split with δ₁ + δ₂ = δ is valid. (Ch. 17)
subsampling bound (Eq. 3 / Eq. 8) — R(ĥ) ≤ R̂̂(ĥ) + Δ√((ln 1/P(ĥ) + ln 1/(sδ))/(2m)) + Δ√(ln(1/((1−s)δ))/(2n)), s = n/(n+m), holding with probability ≥ 1−δ over the training set and the subsample; for the paper's best model the extra cost is 0.2106 bits/token. (Ch. 17)
coverage simulation — repeating a random experiment many times and counting how often a bound's claim is false; a valid bound at level δ must fail in at most a fraction δ of runs, up to simulation noise. (Ch. 17)
proxy split s = n/(n+m) — the δ split that minimizes the single root √(ln(1/δ₁)/(2m) + ln(1/δ₂)/(2n)); not the minimizer of the actual two-root bound, but within ~0.00003 bits/token of it for the paper's models (erratum E06). (Ch. 17)
Hoeffding's sampling-without-replacement theorem (Hoeffding 1963, Theorem 4) — for any convex f, E f(sum of a without-replacement sample) ≤ E f(sum of a with-replacement sample) of the same size; it implies that Hoeffding's inequality holds unchanged for sampling without replacement. (Ch. 17)
coupling — building two random quantities on one shared random experiment so that they can be compared directly; used to prove Hoeffding's Theorem 4 (the without-replacement sum is the conditional average of the with-replacement sum). (Ch. 17)
selection-after-subsampling caveat — if N_sel candidates are compared on the same subsample and the best is reported, the second term must use ln(N_sel/((1−s)δ)) instead of ln(1/((1−s)δ)); the paper does not do this (erratum E07). (Ch. 17)

Chapter 18 — Random subspace training¶

Defined in Chapter 18.

random subspace (affine) — The set of all parameter vectors θ = θ₀ + Pw for w ∈ ℝ^d, with θ₀ and the D × d matrix P fixed before seeing data; it passes through the random initialization θ₀, not the origin, and training changes only w. (Ch. 18)
subspace dimension d — The number of free coordinates w in random-subspace training; the network still has all D parameters, but only d numbers are trained and must be described. (Ch. 18)
projection matrix P — The fixed D × d matrix that maps the short vector w into a change Pw of all D parameters; it is regenerated from a seed and never stored or formed explicitly. (Ch. 18)
intrinsic dimension — For a given task and network, the smallest subspace dimension d at which random-subspace training reaches a set fraction (Li et al. 2018: 90 %, written d_int90) of the performance of training all parameters. (Ch. 18)
stretch — For a nonzero w, the ratio ‖Pw‖/‖w‖: how far θ moves per unit step in w; it equals 1 in every direction exactly when PᵀP = I. (Ch. 18)
eigenvalue / eigenvector — For a square matrix S, a number λ and nonzero vector u with Su = λu; for S = PᵀP the smallest and largest eigenvalues are the smallest and largest squared stretches of P. (Ch. 18)
condition number — The ratio κ = λ_max/λ_min of the largest to the smallest eigenvalue of PᵀP; gradient descent on a quadratic shrinks its error by at best (κ − 1)/(κ + 1) per step, so κ = 1 is ideal. (Ch. 18)
approximately orthonormal — A matrix with PᵀP close to I; closeness is measured by the largest or RMS entry of PᵀP − I and, most relevantly for training, by the eigenvalue range of PᵀP. (Ch. 18)
Kronecker projector (§3 version) — P = (G₁ ⊗ G₂)/√D with G₁, G₂ independent standard-Gaussian √D × √d matrices; PᵀP ≈ I with errors shrinking only like D^(−1/4), and a stretch range of about [(1 − r)⁴, (1 + r)⁴] with r = (d/D)^(1/4). (Ch. 18)
QR-orthogonalized Kronecker projector (§5 version) — P = Q₁ ⊗ Q₂ with Q₁, Q₂ the orthonormal QR factors of Gaussian √D × √d matrices; PᵀP = I exactly, it is stored as two small factors (or a seed) and applied with the vec trick. (Ch. 18)
remainder block — In the authors' code, the dense Gaussian (D − D₀) × (d − d₀) block placed on the diagonal next to the Kronecker block when D or d is not a perfect square (D₀, d₀ the largest perfect squares not above D and d); it is only approximately orthonormal and can switch off directions of w. (Ch. 18)
pad-and-truncate — Handling non-square sizes by building an orthonormal Kronecker matrix for the next perfect squares and keeping the first D rows and d columns; dropping columns keeps PᵀP = I, dropping rows breaks it slightly. (Ch. 18)

Chapter 19 — LoRA¶

Defined in Chapter 19.

LoRA (low-rank adaptation) — Training a weight matrix \(W\) only through a low-rank correction, \(W=W_0+s\,BA\), with the starting matrix \(W_0\) kept fixed; proposed by Hu et al. (2021) for fine-tuning, used by the paper for pretraining from random weights. (Ch. 19)
frozen (base) weight — A parameter kept at its starting value during training; gradient descent never updates it. In LoRA, \(W_0\) is frozen. (Ch. 19)
LoRA factors — The two trainable thin matrices \(B\in\mathbb R^{a\times r}\) (initialized to zero) and \(A\in\mathbb R^{r\times b}\) (initialized randomly) whose product is the update; the paper calls them \(U\) and \(V\) (erratum E16). (Ch. 19)
LoRA rank — The inner dimension \(r\) of the factors, a hyperparameter; the update has rank at most \(r\). The paper uses \(r\in\{1,4\}\) for pretraining (4 for the larger models) and \(r=8\) for App. D fine-tuning. (Ch. 19)
LoRA scaling factor — The constant \(s=\alpha_{\text{LoRA}}/r\) multiplying \(BA\); the paper's "LoRA alpha" is \(\alpha_{\text{LoRA}}=32\), so \(s=32\) at \(r=1\) and \(8\) at \(r=4\). Under Adam it acts like a learning-rate multiplier for \(B\). (Ch. 19)
low-rank update — The change \(\Delta W=s\,BA\) that LoRA adds to a weight matrix; it costs \(r(a+b)\) numbers instead of \(ab\) (6,144 instead of 589,824 for a \(768\times768\) matrix at \(r=4\)). (Ch. 19)
outer product — The matrix \(uz^\top\) of a column vector \(u\) and a row vector \(z^\top\), with entries \(u_iz_j\); it has rank 1 when \(u,z\neq0\). \(BA\) is the sum of \(r\) outer products (column \(k\) of \(B\) times row \(k\) of \(A\)). (Ch. 19)
LoRA dropout — During training only, randomly zeroing entries (probability 0.1 in the paper) and rescaling the rest, on the low-rank branch's input per Hu et al.'s reference implementation (not verified here; the paper does not say where); off at evaluation. (Ch. 19)
stationary point — A point where the whole gradient is zero; gradient descent started there never moves. \(B=A=0\) is one for every loss (the trap behind erratum E10). (Ch. 19)
LoRA for pretraining — The paper's use of LoRA with a random (not pretrained) \(W_0\): LoRA on \(W_Q\), \(W_V\) of every layer and on the linear head, everything else left at its random initial value; 351,556 trainable numbers for GPT-2 small at \(r=4\) (with \(V=50{,}257\)). (Ch. 19)
bilinear map — A map of two arguments that is linear in each when the other is held fixed but not jointly, like \((B,A)\mapsto BA\); the reason LoRA is a nonlinear parameterization. (Ch. 19)
Frobenius norm — \(\lVert M\rVert_F\), the square root of the sum of the squared entries of a matrix (the ordinary norm of the matrix's flattened entries); equals \(\sqrt{\sum_i\sigma_i^2}\). (Ch. 19)
singular value decomposition (SVD), singular values — Writing any matrix as \(\sum_i\sigma_iu_iz_i^\top\) with orthonormal \(u_i\), orthonormal \(z_i\) and \(\sigma_1\ge\sigma_2\ge\dots\ge0\); the \(\sigma_i\) are the singular values and the rank is the number of nonzero ones. (Ch. 19)
Eckart–Young theorem — The best rank-\(\le r\) approximation of \(M\) in Frobenius norm keeps the \(r\) largest SVD terms; the squared error left is \(\sum_{i>r}\sigma_i^2\). (Ch. 19)

Chapter 20 — SubLoRA¶

Defined in Chapter 20.

SubLoRA — The paper's parameterization (§5, Eq. 4): LoRA on the query, value and head matrices, with all LoRA factors driven by a random subspace, θ = θ₀ + LoRA(φ₀ + Pw); only the d numbers in w are trained and stored. "Subspace-Enhanced Low-Rank Adaptation". (Ch. 20)
LoRA(·) operator (unflatten → product → flatten) — The map in Eq. (4) that cuts a vector of LoRA factors into the matrices B_k, A_k, forms each update s·B_kA_k, and writes these updates into the slots of their weight matrices in a full-length vector (zeros for frozen matrices and biases). (Ch. 20)
D_LoRA — The total number of LoRA factor entries; the row count of SubLoRA's projector P (351,556 for GPT-2 small at r = 4 with V = 50,257; 351,744 with nanoGPT's padded vocabulary), not the model's 123,689,472 parameters. (Ch. 20)
initial LoRA factors φ₀ — The fixed starting values of all LoRA factors (A random, B zero), regenerated from a seed; Eq. (4) omits them, but without them the gradient with respect to w is exactly zero at w = 0 (erratum E10). (Ch. 20)
nonlinear parameterization — A rule θ = f(w) that is not of the form θ₀ + Mw; in SubLoRA each weight update is a product of two factors that both depend on w, so θ is quadratic in w and the reachable set is a curved d-dimensional surface. (Ch. 20)
zero-gradient-at-origin caveat — With all LoRA factors starting at zero, every update is a quadratic form in w, so ∇_w L = 0 at w = 0 for every loss and training never moves; the gradient grows only linearly with the distance from the origin. (Ch. 20)
compression ladder — The chain of reductions for GPT-2 small: 123,689,472 parameters → 351,556 LoRA numbers (r = 4) → d subspace coordinates (5,000 … 200,000) → quantized and arithmetic-coded w (about 2.3–3.5 bits per coordinate in Fig. 2). (Ch. 20)
Pareto frontier — Among a set of runs scored on two "lower is better" axes (here empirical risk and complexity), the runs that no other run beats on both axes at once; the best bound (risk + complexity) always lies on it. (Ch. 20)
vacuous region (Fig. 1) — The shaded area of Figure 1 (left) above the diagonal risk + complexity = random-guess level (log₂ V = 15.617 bits/token for BPD; 1 − 1/V for top-1 error); a run inside it has a bound no better than uniform guessing. (Ch. 20)

Chapter 21 — Quantization¶

Defined in Chapter 21.

quantization — Replacing each of a list of real numbers by one value from a small fixed set of allowed values; the paper quantizes only the d subspace coordinates w, never GPT-2's D parameters. (Ch. 21)
quantization level — One of the L_q allowed values c_k a quantized number may take. (Ch. 21)
codebook c — The list c = (c_1, …, c_{L_q}) of quantization levels; it must be stored with the quantized vector (about 16 bits per level). (Ch. 21)
L_q (number of quantization levels) — How many levels the codebook has; 11 or 17 in the paper, which calls it C or L (erratum E16). (Ch. 21)
nearest-level assignment — q(i) = argmin_k |w_i − c_k|, the index of the level closest to w_i; the quantized coordinate is ŵ_i = c_{q(i)}. In 1-D the cells are intervals between midpoints of consecutive levels. (Ch. 21)
cluster / bin — The set S_k = {i : q(i) = k} of coordinates assigned to level k; its size n_k gives the empirical probability n_k/d used by arithmetic coding. (Ch. 21)
quantization error — e_i = w_i − ŵ_i; summarized by the mean squared error (1/d) Σ e_i², in units of w squared. (Ch. 21)
uniform vs learned levels — Uniform levels are evenly spaced; learned (non-uniform) levels are placed where the data are dense (k-means) and may be moved further by training. (Ch. 21)
k-means / Lloyd's algorithm — Choosing a codebook to make the total squared error Σ (w_i − c_{q(i)})² small by alternating "assign each point to its nearest level" and "move each level to the mean of its cluster"; neither step increases the error, it stops after finitely many rounds, but it can stop at a local optimum. (Ch. 21)
post-training quantization — Rounding the trained weights to the levels once, with no further training. (Ch. 21)
quantization-aware training (QAT) — Training with the quantizer in the loop: the forward pass uses ŵ, the backward pass uses the straight-through estimator for w and the exact codebook gradient for c; only the final ŵ is stored. (Ch. 21)
straight-through estimator (STE) — The deliberate substitution ∂ŵ_i/∂w_j := 1[i = j], i.e. ∂L/∂w_i := ∂L/∂ŵ_i, used because the true derivative of rounding is 0 almost everywhere; a heuristic with no convergence guarantee (Lotfi et al. 2022, Eq. 4). (Ch. 21)
codebook gradient — ∂L/∂c_k = Σ_{i: q(i)=k} ∂L/∂ŵ_i, the sum of the loss gradients over level k's cluster; an exact derivative almost everywhere, not an estimate. (Ch. 21)
bits per weight before entropy coding — ⌈log2 L_q⌉ bits per coordinate for a fixed-length code of the level index: 4 bits for 11 levels, 5 for 17. (Ch. 21)
entropy limit (of a quantized vector) — The best average cost per level index, H(p̂) = −Σ p̂_k log2 p̂_k bits with p̂_k = n_k/d; at most log2 L_q (3.4594 bits for 11 levels, 4.0875 for 17), less when usage is skewed (Chapter 22). (Ch. 21)

Chapter 22 — Entropy and arithmetic coding¶

Defined in Chapter 22.

symbol (of a message) — one element of a finite alphabet of L possibilities; for the paper's quantized weights, symbol k means "this weight equals the k-th quantization level". (Ch. 22)
message — a sequence x = (x₁, …, xₙ) of symbols that is to be coded as a whole. (Ch. 22)
i.i.d. source — a random message generator whose symbols are independent and each follow the same distribution p, so Pr[X = x] = p_{x₁}·…·p_{xₙ}. (Ch. 22)
entropy H(p) — the average surprisal of a distribution, H(p) = −Σ p_k log₂ p_k bits per symbol (terms with p_k = 0 count as 0); it lies between 0 (one certain symbol) and log₂ L (all L symbols equally likely), and adds up over independent symbols. (Ch. 22)
Gibbs' inequality — for a distribution p and weights q with Σ q_k ≤ 1, Σ p_k log₂(p_k/q_k) ≥ 0, with equality only if q = p; proved from ln x ≤ x − 1. Equivalently, cross-entropy is never below entropy. (Ch. 22)
relative entropy (KL divergence) — the quantity Σ p_k log₂(p_k/q_k) of Gibbs' inequality: the average number of extra bits paid for coding data from p with probabilities q. (Ch. 22)
expected code length — Σ_k p_k ℓ_k, the average number of bits per symbol of a code whose codeword for symbol k has ℓ_k bits. (Ch. 22)
Shannon source-coding bound — no prefix-free (or uniquely decodable) code has expected length below the entropy H(p); proved by Kraft (or McMillan) plus Gibbs. (Ch. 22)
Shannon code — the prefix-free code with lengths ⌈log₂(1/p_k)⌉; these lengths satisfy Kraft, and the expected length is below H(p) + 1. (Ch. 22)
symbol-by-symbol code — a code that gives each symbol its own codeword and writes the codewords one after another; it pays its rounding on every symbol and can waste up to about 1 bit per symbol on skewed distributions (0.7136 bits for probabilities 0.95/0.05). (Ch. 22)
Huffman code — a standard symbol-by-symbol prefix code built by repeatedly merging the two least likely symbols into one. (Ch. 22)
arithmetic coding — a code for a whole message: start with [0, 1), repeatedly keep the sub-interval of the next symbol (width proportional to its probability), and output the shortest bit string whose binary interval fits inside the final interval; length ≤ ⌈log₂(1/Πp)⌉ + 1 < Σ log₂(1/p_{xᵢ}) + 2 bits. (Ch. 22)
interval narrowing — the encoding step of arithmetic coding: low ← low + W·F_{xᵢ}, W ← W·p_{xᵢ}, so the final width W equals the probability of the message. (Ch. 22)
binary interval (of a bit string) — for b = b₁…b_k, the interval [0.b, 0.b + 2^−k) of all numbers whose binary expansion begins with b; a prefix's binary interval contains the longer string's. (Ch. 22)
arithmetic decoding — the reverse process: knowing the probabilities and the number of symbols, repeatedly find the sub-interval containing the received number and output its symbol. (Ch. 22)
static model — a coder whose symbol probabilities stay the same for every position of the message. (Ch. 22)
empirical probabilities — the fractions p̂_k = n_k/d of the d coded symbols that equal level k; with them the total surprisal of the message is exactly d·H(p̂), so arithmetic coding takes at most ⌈d·H(p̂)⌉ + 1 bits. (Ch. 22)
header cost (codebook and counts) — the bits a decoder needs besides the coded symbols: 16 bits per quantization level for a half-precision codebook and ⌈log₂ d⌉ bits per level for the counts (Lotfi et al. 2022); 352 bits for d = 50,000 and 11 levels; whether the paper counts them is erratum E18. (Ch. 22)
two-part code — a description that first sends the parameters of a code (here the counts) and then the data coded with them; it is a fixed, legal code because the rule is decided before the data. (Ch. 22)
Laplace adaptive coder — an arithmetic coder that codes each symbol with probabilities (count so far + 1)/(symbols so far + L), so no count header is needed; its length is exactly log₂ C(d+L−1, L−1) + log₂(d!/Π n_k!) bits. (Ch. 22)
finite-precision (integer) arithmetic coder — a practical arithmetic coder that keeps the interval as 32-bit integers and renormalizes (outputs settled leading bits and doubles the range); for d = 50,000 symbols it costs at most 3.36 bits more than the exact coder's d·H + 2. (Ch. 22)
renormalization — the step of an integer arithmetic coder that outputs (or defers) a bit and doubles the integer range whenever the range has narrowed to one half or the middle half. (Ch. 22)
language modeling is compression — arithmetic coding with a language model's next-token probabilities stores a text in fewer than its negative log-likelihood in bits plus 2; a better predictor is a better compressor. (Ch. 22)

Chapter 23 — The paper's story¶

Defined in Chapter 23.

shattering — a set of \(k\) inputs is shattered by a class of yes/no classifiers if every one of the \(2^k\) labellings of those inputs is produced by some classifier in the class. (Ch. 23)
VC dimension — the largest number of inputs that a class of classifiers can shatter; a class-wide measure of how many arbitrary labels it can fit, used by classical (Vapnik) generalization bounds. (Ch. 23)
growth function — the largest number of distinct labellings a class produces on any \(k\) inputs; bounded polynomially in \(k\) by the Sauer–Shelah lemma when the VC dimension is finite. (Ch. 23)
Rademacher variable — a random sign, \(+1\) or \(-1\) with probability \(\tfrac12\) each. (Ch. 23)
Rademacher complexity — the expected best correlation between a class's functions and random signs on a sample, \(\mathbb E_\varepsilon[\sup_f \frac1m\sum_j \varepsilon_j f(z_j)]\); it measures how well the class fits pure noise, and equals its maximum when the class can fit any labelling. (Ch. 23)
sub-Gaussian random variable — a variable whose moment generating function satisfies \(\mathbb E[e^{\lambda(X-\mu)}]\le e^{\lambda^2\sigma^2/2}\) for all \(\lambda\) (variance proxy \(\sigma^2\)), so its tails fall at least as fast as \(e^{-t^2/(2\sigma^2)}\); every variable in \([a,b]\) is sub-Gaussian with \(\sigma=(b-a)/2\). (Ch. 23)
Lipschitz constant — the largest factor \(K\) by which a function can stretch distances, \(\lVert f(u)-f(v)\rVert\le K\lVert u-v\rVert\); constants of stacked layers multiply. (Ch. 23)
hypothesis-dependent range Q(h) — a bound \(\sup_x R(h,x)\le Q(h)\) on the worst-case loss of one hypothesis (Haddouche et al., 2021); for an unsmoothed LLM it can grow exponentially with depth. (Ch. 23)
distillation — training a small "student" model to imitate the predictions of a large "teacher" model. (Ch. 23)
QLoRA — fine-tuning in which the pretrained model is stored in 4-bit precision and LoRA weights are trained by backpropagating through it. (Ch. 23)
SpQR — a compression method that keeps the few weights most damaged by rounding (outliers) in high precision and quantizes the rest. (Ch. 23)
GPTQ — post-training quantization that quantizes weights one at a time and adjusts the remaining weights to cancel the error, using approximate second-order (curvature) information. (Ch. 23)
tensor-train decomposition — storing a large array as a chain of small tensors whose product rebuilds it (used by TensorGPT for the embedding table). (Ch. 23)
Pareto dominance — point \(q\) dominates \(p\) if \(q\) is at least as good in every coordinate and strictly better in at least one. (Ch. 23)
iso-bound line — in a (complexity, training loss) plot, a line of slope −1 along which complexity + training loss, i.e. the bound, is constant. (Ch. 23)
vacuous region — in Figure 1 (left), the set of points whose bound (complexity + training loss) exceeds the random-guess level. (Ch. 23)
compression sweep — Figure 1 (right): models of increasing compressed size with their empirical risk, complexity and bound, showing that an intermediate size gives the best bound. (Ch. 23)

Chapter 24 — The pipeline¶

Defined in Chapter 24.

end-to-end pipeline — the complete sequence of steps from raw data to the reported number, each step feeding the next; in the paper: SubLoRA training → quantization-aware training → arithmetic coding (+ hyperparameter bits and length header) → smoothed loss on n = 10,000 subsampled documents → Eq. (3), repeated over a hyperparameter grid with the lowest bound reported. (Ch. 24)
grid search — choosing hyperparameters by trying every combination of a few listed values and keeping the best result. (Ch. 24)
hyperparameter grid — the list of hyperparameter combinations fixed before training; for GPT-2 small in App. E it has 6 (d) × 2 (r) × 3 (learning rate) × 8 (α) × 2 (L_q) = 576 points, costing log₂ 576 = 9.17 bits in the price. (Ch. 24)
pseudo-code — a program written for human readers, naming the steps with their inputs and outputs in a programming-like layout, not meant to be run as it stands. (Ch. 24)
Algorithm 1 — the paper's pseudo-code (App. C, p. 15) for one bound computation: TRAIN_SUBLORA, TRAIN_QUANTIZE, the smoothed subsampled empirical risk, GET_COMPRESSED_SIZE (arithmetic coding + hyperparameter bits + 2 log₂ header) and Eq. (3); it describes a single grid point, and its line 6 must convert bits to nats (errata E02, E52); further loose ends in errata E17 and E64. (Ch. 24)
forward pass — one run of the network on one input window of at most L_ctx tokens; a causal transformer returns a next-token distribution for every position of the window in a single forward pass. (Ch. 24)
sliding-window evaluation — scoring a document longer than the context by running forward passes on overlapping windows and keeping only the predictions not made before; any such rule fixed in advance defines a valid autoregressive model. (Ch. 24)
stride — the number of tokens by which a sliding window moves between forward passes; the authors' code uses 100, so one forward pass scores 100 new tokens. (Ch. 24)
Eq. (9) — the paper's rule for tokens beyond the context (App. E, p. 16): p(x_i | x_{:i−1}) = f(x_i | x_{i−L′:i−1}) with L′ = L − (i − L) mod 100; as printed it does not shift in chunks of 100 (erratum E15); the stride-100 rule of the code is L′ = L − 99 + ((i − L − 1) mod 100). (Ch. 24)

Chapter 25 — Results for GPT-2 small¶

Defined in Chapter 25.

certified accuracy — one minus an error bound: the accuracy that the bound guarantees with probability at least 1 − δ. For the paper's SubLoRA models (Table 1) it is 3.59 % (top-1), 22.10 % (top-10) and 41.66 % (top-100), versus 0.0020 %, 0.0199 % and 0.1990 % for uniform guessing. (Ch. 25)
capped table entry — a reported error bound of 100 % that stands for a computed bound of 100 % or more (e.g. LoRA's top-1 bound 1.0058 in Figure 1); the paper does not state the capping rule. (Ch. 25)
per-metric model selection — reporting, in each row of a results table, the best bound over all trained models for that metric; cells of the same column can therefore describe different models (in Table 1, SubLoRA's top-1 cell comes from a ≈3.9 KB model and its BPD cell from a 16.5 KB model). (Ch. 25)
complexity factor K(C) — the two complexity terms of Eq. (3) divided by the interval width Δ, a pure number that depends only on the compressed size C (and on m, n, δ): K(C) = √((C ln 2 + 2 ln C + ln 1/(sδ))/(2m)) + √(ln(1/((1−s)δ))/(2n)). A BPD bound is empirical risk + Δ(α)·K(C); a top-k bound is empirical top-k error + K(C). (Ch. 25)
implied compressed size — the compressed size obtained by solving K(C) = complexity/Δ for C from a published bound and empirical risk; a consistency check (not a guarantee) used to identify which model produced a table cell. (Ch. 25)
envelope (of a family of curves) — the curve formed by taking, at each x-value, the lowest value over several curves; Figure 2 (right) is an envelope over three models rather than one model's curve (erratum E41). (Ch. 25)
bound–validation gap — the bound minus the validation loss of the same model (Table 2: 1.59 bits per token for SubLoRA, 66.41 for the original model); not a generalization gap, since the two numbers may differ in model (smoothed or not) and in averaging. (Ch. 25)
joint confidence of a table — the probability that several separately certified cells all hold at once; by the union bound at least 1 − (number of cells)·δ, e.g. ≥ 0.80 for the four cells of one column at δ = 0.05. (Ch. 25)

Chapter 26 — Scale, structure, pretraining¶

Defined in Chapter 26.

monotone in model size — a sequence of values (e.g. bounds for models of increasing size) that only goes down, or only goes up, as size grows; one step in the wrong direction breaks it. Table 3's BPD bounds (12.12, 11.96, 11.95, 12.10, 12.01) are not monotone. (Ch. 26)
Spearman rank correlation (ρ) — the ordinary correlation of the ranks of two lists; with no ties, ρ = 1 − 6Σd²/(n(n²−1)), where d is the rank difference. +1 means same order, −1 reversed order, ≈ 0 no relation. (Ch. 26)
exact permutation p-value — the fraction of all n! assignments of fixed values to fixed labels whose statistic (here ρ) is at least as extreme as the observed one; a descriptive yardstick (the assignment is the only randomness). (Ch. 26)
run-to-run variation — how much a reported number changes when the same experiment is repeated with a different seed; the paper reports one run per setting, so it can only be estimated indirectly (e.g. the 124M shape appears as 12.12, 12.007 and 12.139 bits/token in different places). (Ch. 26)
standard error — the standard deviation of an average over repeated random samples; σ/√n for the mean of n independent draws with standard deviation σ, times (m−n)/(m−1) inside the square root when sampling without replacement from m items. (Ch. 26)
Popoviciu's inequality — a variable confined to an interval of width Δ has standard deviation at most Δ/2. (Ch. 26)
best-of-k effect — the drop in the best reported value that comes only from trying more settings; for N sorted values, E[min of k random ones] = Σᵢ v₍ᵢ₎ C(N−i, k−1)/C(N, k). (Ch. 26)
compressed dataset size — the length of a two-part code for the training set: C(h) bits for the model plus the bits for all training tokens coded with the model (≈ its total negative log₂-likelihood); Figure 3 (right), ≈ 8.5·10¹⁰ bits, of which the model is ≈ 10⁻⁶. (Ch. 26)
permuted-context training — training (and evaluating) on sequences whose tokens are randomly shuffled within each sequence, so the model sees its context as a bag of words (§7.2, Figure 4). (Ch. 26)
GLUE, QQP, CoLA — GLUE is a benchmark collection of language-understanding tasks; QQP (Quora Question Pairs) asks whether two questions are duplicates; CoLA (Corpus of Linguistic Acceptability) asks whether a sentence is grammatical. Used in App. D, Table 5. (Ch. 26)
majority-class baseline — the error of the classifier that always answers the most common class (CoLA 29.56 %, QQP 36.93 % on the training splits); the right "random guess" reference for an imbalanced two-class task. (Ch. 26)
truncated axis — a chart axis that does not start at zero, which makes differences look larger than they are (Figure 4's axes start at 9.806, 0.797 and 0.474). (Ch. 26)

Chapter 27 — The paper's own discussion¶

Defined in Chapter 27.

prompt — the text given to a language model before it starts generating; the model continues from it. (Ch. 27)
in-context learning — a model doing a new task from instructions or a few worked examples written into its prompt, with no change to its parameters; judged by a task-specific loss on the task's own questions, so the paper's next-token bound does not cover it (§8). (Ch. 27)
prompt tuning (soft prompt) — keeping every model weight frozen and training only a short list of extra input vectors placed in front of every input (Lester et al. 2021); mentioned without citation in §8 as a learning mode needing its own theory. (Ch. 27)
out-of-distribution generalization — performing well on data drawn from a different distribution than the training data (e.g. tabular data or images for a text model); the paper's document-level bound says nothing about it, since its population is the training-document distribution (§8 limitation 6). (Ch. 27)
token-level bound — a generalization bound that counts tokens, not documents, as its data points; §8 lists it as future work. If every token were an independent sample, OpenWebText's 1,128.07 tokens per document would shrink the m-term by √1,128 ≈ 33.6 (an unattainable upper limit, since tokens are dependent). (Ch. 27)
bias (societal) — a systematic, unfair tendency in a model's outputs, such as stereotypes picked up from training text; the Impact Statement notes bounds may not capture it. Unrelated to the bias vector of a linear layer (Ch. 5). (Ch. 27)
subgroup ceiling — the guarantee a bound on the average risk R gives for a group with population share f: R_G ≤ (R − (1 − f)ℓ_min)/f; for the paper's best model it is non-vacuous only for groups above 77.0 % of documents. (Ch. 27)
Azuma–Hoeffding inequality — Hoeffding's inequality for a sum of martingale differences (losses minus their expectation given the past), proved by applying Hoeffding's lemma conditionally one step at a time; it bounds the gap to context-conditional expected losses, not the risk on fresh documents. (Ch. 27)

Chapter 28 — Mini replication¶

Defined in Chapter 28.

mini replication — re-running a paper's whole pipeline at a much smaller scale (here: a laptop CPU, a 29-symbol alphabet, 100,000 short documents) to watch every step work and check it, not to reproduce the paper's numbers. (Ch. 28)
known generator (synthetic data) — a data-generating process written as a program, so that the exact probability of every document can be computed and unlimited fresh documents can be drawn. (Ch. 28)
fresh documents — new independent draws from the known generator that were used neither for training nor for computing the bound; they play the role of "the population". (Ch. 28)
true-risk estimate — the average loss of a fixed hypothesis on fresh documents, used as a stand-in for its expected risk \(R(h)\); it comes with a confidence half-width. (Ch. 28)
confidence half-width — the ± margin around an estimate; here either Hoeffding's (valid for any loss in an interval of width \(\Delta\)) or the central-limit (normal-approximation) margin \(1.96\,s/\sqrt N\), which is much narrower but only approximate. (Ch. 28)
central limit theorem (CLT) — the fact that the average of many i.i.d. values with finite variance is approximately normally distributed around the mean, with standard deviation \(\sigma/\sqrt N\). (Ch. 28)
generator's BPD (entropy reference) — the per-document average of \(-\log_2 \Pr[X]/L\) computed with the generator's own exact probabilities; the loss of a model that knows the generator perfectly. (Ch. 28)
certified model — the exact object a bound is about: here the quantized SubLoRA model with float16 codebook, smoothed with the chosen \(\alpha\) — not the unsmoothed or unquantized network. (Ch. 28)
price of the guarantee — the gap between a bound and the true risk of the same hypothesis (bound minus true risk); it is what one pays, in loss units, for a statement that holds with probability at least \(1-\delta\) without seeing fresh data. (Ch. 28)

Chapter 29 — Critique¶

Defined in Chapter 29.

theorem chain — the sequence of results that together give the paper's headline inequality (Eq. 3): Hoeffding's inequality per hypothesis, a prior-weighted union bound over a finite hypothesis space, prediction smoothing to bound the loss, and a second Hoeffding step for the subsample; it needs a prior fixed in advance, a bounded per-document loss, i.i.d. documents, an independent subsample, and a reported model that does not depend on the subsample. (Ch. 29)
validity gap — a place where a published number is not covered by the theorem exactly as stated, or is covered only under an assumption the procedure cannot guarantee (e.g. erratum E07: +0.0635 to +0.1614 bits/token on the best bound; the i.i.d. assumption on OpenWebText documents). (Ch. 29)
verdict (supported / partly supported / not supported) — this explainer's three-level judgement of an interpretive claim: the evidence covers the claim as worded; it covers only a narrower or weaker version; or it does not cover it or points the other way. (Ch. 29)
error bars — a range shown around a reported number that says how much it moves when the experiment is repeated (e.g. with different random seeds); the paper reports none for its scaling comparisons. (Ch. 29)
ranking by bounds — ordering models by their upper bounds; a smaller bound does not imply a smaller true risk or a smaller generalization gap, since an upper bound gives no lower limit on the other model's risk (in Ch. 28 the model with bound 9.48 has true risk 1.488, the one with bound 4.347 has 3.435). (Ch. 29)