Part III · Deep learning | word embeddings, encoder–decoder models, attention as soft lookup, self-attention and multi-head attention, positional encodings, the transformer block, BERT and GPT, a tiny GPT trained from scratch, byte-pair encoding, decoding strategies, pre-training and in-context learning, scaling laws, retrieval and retrieval-augmented generation | reading: Prince, Understanding Deep Learning, ch. 12 (and notebooks 12.1–12.4); Jurafsky & Martin, Speech and Language Processing (3rd ed. draft), ch. 6, 9–11 and 14; Vaswani et al. (2017)
Lecture 11 ended with the two weaknesses of recurrent networks: they process a sequence one step at a time, and they must squeeze the whole past through a fixed-size state. Attention removes both. To compute the representation of one position, it compares that position with every other position, turns the similarities into weights with a softmax, and takes a weighted average: a soft, learned dictionary lookup that runs for all positions in parallel. A transformer stacks attention with the MLPs, residual connections and layer normalisation of Lectures 10 and 11. Trained to predict the next token on enough text, it becomes a large language model. This lecture builds every part from scratch: word vectors, attention, a small GPT trained on Shakespeare on a laptop-sized computer, the byte-pair tokeniser, the decoding rules that turn probabilities into text, and a small retrieval system of the kind that grounds language models in documents.
By the end of this lecture you should be able to explain word embeddings and their link to co-occurrence statistics; define scaled dot-product attention and multi-head self-attention, prove their basic properties (kernel smoothing, permutation equivariance, the \(\sqrt d\) scaling) and count their cost; describe positional encodings and the transformer block; distinguish encoder-only, decoder-only and encoder–decoder models and their training objectives; implement byte-pair encoding; compare greedy, beam, temperature, top-k and nucleus decoding; explain pre-training, fine-tuning, in-context learning and scaling laws; and build and evaluate lexical, dense and hybrid retrieval, and write retrieval-augmented generation as a mixture model.
A network needs numbers. The simplest encoding of a word from a vocabulary of size \(V\) is a one-hot vector: all zeros except a one in that word's position. One-hot vectors are all equally far apart, so "king" is no more similar to "queen" than to "turnip". An embedding maps each word to a dense vector of a few hundred numbers, \(e_w=E^\top\mathbf 1_w\) (a row of a learned matrix \(E\)), so that similar words get similar vectors. Where does the similarity come from? From the distributional hypothesis: "you shall know a word by the company it keeps" (Firth, 1957). Words that appear in similar contexts have similar meanings.
Skip-gram with negative sampling (word2vec; Mikolov et al., 2013) learns word vectors \(e_w\) and context vectors \(c_u\) so that \(\sigma(e_w^\top c_u)\) is high for word–context pairs seen in text and low for random pairs.
At its optimum (with unconstrained vectors),
$$e_w^\top c_u=\mathrm{PMI}(w,u)-\log k,$$where
$$\mathrm{PMI}(w,u)=\log\frac{P(w,u)}{P(w)P(u)}$$and \(k\) is the number of negative samples.
So word2vec implicitly factorises a matrix of pointwise mutual information (Levy and Goldberg, 2014).
That suggests a transparent recipe: count co-occurrences, convert them to positive PMI, and take a truncated SVD (Lecture 2), exactly the factorisation word2vec approximates.
About 1.1 million characters from Shakespeare's plays (Karpathy, 2015), as in Lecture 11. We use the first 90% for training and the last 10% for validation throughout this lecture.
import numpy as np, re, collections # Word vectors from co-occurrence counts: positive PMI + truncated SVD (Levy & Goldberg, 2014), on Shakespeare text = open('data/tinyshakespeare.txt').read() words = re.findall(r"[a-z']+", text.lower()) counts = collections.Counter(words) vocab = [w for w, c in counts.most_common() if c >= 10]; ix = {w: i for i, w in enumerate(vocab)}; V = len(vocab) seq = np.array([ix.get(w, -1) for w in words]) C = np.zeros((V, V)) for off in [1, 2, 3, 4]: # symmetric window of 4 words a, b = seq[:-off], seq[off:]; ok = (a >= 0) & (b >= 0) np.add.at(C, (a[ok], b[ok]), 1); np.add.at(C, (b[ok], a[ok]), 1) total = C.sum(); pw = C.sum(1) / total; pc = (C.sum(0) / total) ** 0.75; pc /= pc.sum() with np.errstate(divide='ignore'): PMI = np.log(C / total) - np.log(pw[:, None]) - np.log(pc[None, :]) PPMI = np.maximum(PMI, 0) # positive pointwise mutual information U, S, _ = np.linalg.svd(PPMI, full_matrices=False) E = U[:, :100] * np.sqrt(S[:100]); E /= np.linalg.norm(E, axis=1, keepdims=True) # 100-dimensional unit vectors print(f'{len(words):,} words, {V:,} with at least 10 occurrences; embedding dimension 100') def nearest(w, k=6): sims = E @ E[ix[w]]; return [vocab[j] for j in np.argsort(-sims)[1:k + 1]] for w in ['king', 'love', 'death', 'night', 'sword', 'father']: print(f'{w:8s} -> ' + ', '.join(nearest(w))) def analogy(a, b, c): # a is to b as c is to ? v = E[ix[b]] - E[ix[a]] + E[ix[c]]; sims = E @ v for w in (a, b, c): sims[ix[w]] = -np.inf return vocab[int(np.argmax(sims))] for a, b, c in [('man', 'woman', 'king'), ('he', 'she', 'his'), ('father', 'son', 'mother')]: print(f'{a} : {b} :: {c} : {analogy(a, b, c)}')
204,062 words, 1,893 with at least 10 occurrences; embedding dimension 100 king -> richard, edward, iv, vi, henry, warwick love -> heart's, hate, thy, true, tell, dear death -> life, day, die, poor, bed, even night -> morrow, good, day, lie, morning, to sword -> knife, lay, put, equal, him, treason father -> son, prince, princely, brother, child, heir man : woman :: king : vi he : she :: his : her father : son :: mother : daughter
From 200,000 words of plays, with no labels, the nearest neighbours already make sense: kings are near other kings' names (Richard, Edward, Henry), "father" is near "son", "brother", "heir", "death" near "life" and "die". The vector arithmetic of analogies works for pronouns and family relations (he : she :: his : her; father : son :: mother : daughter) but "man : woman :: king : ?" returns "vi", because in Shakespeare's histories "king" sits next to "Henry VI" far more often than next to any queen. Embeddings learn the statistics of their corpus, biases included, a point Lecture 13 develops.
Translation maps a sequence to a sequence of different length. The encoder–decoder (sequence-to-sequence) model of Sutskever, Vinyals and Le (2014) and Cho et al. (2014) used one LSTM, the encoder, to read the source sentence into its final hidden state, and a second, the decoder, to generate the translation word by word from that state. It worked, but it degraded on long sentences, for the reason Lecture 11 ended with: the whole sentence must pass through one fixed-size vector, a bottleneck. Bahdanau, Cho and Bengio (2015) let the decoder, at every output step, look back at all the encoder's hidden states and take a weighted average of them, with weights computed from how relevant each source word is to the word being produced. That weighted average is attention.
A Python dictionary maps a query to the value whose key matches it exactly. Attention is a soft version: compare the query with every key, turn the similarities into weights that sum to one, and return the weighted average of the values.
Given queries \(Q\in\mathbb R^{n\times d_k}\), keys \(K\in\mathbb R^{m\times d_k}\) and values \(V\in\mathbb R^{m\times d_v}\),
$$\operatorname{Attention}(Q,K,V)=\operatorname{softmax}\Big(\frac{QK^\top}{\sqrt{d_k}}\Big)V,$$with the softmax applied to each row: row \(i\) of the output is \(\sum_ja_{ij}v_j\) with
$$a_{ij}\propto\exp(q_i^\top k_j/\sqrt{d_k}).$$In self-attention the queries, keys and values all come from the same sequence \(X\in\mathbb R^{n\times d}\) through learned matrices:
$$Q=XW_Q,\quad K=XW_K,\quad V=XW_V.$$Each position asks a question (its query), every position advertises what it contains (its key), and each position receives a mixture of the others' contents (their values).
Attention is older than it looks. It is the Nadaraya–Watson kernel smoother (Nadaraya, 1964; Watson, 1964) with learned similarities.
The Nadaraya–Watson estimator
$$\hat f(x)=\sum_j\frac{K_h(x-x_j)}{\sum_lK_h(x-x_l)}y_j$$with the Gaussian kernel \(K_h(u)=e^{-u^2/(2h^2)}\) is attention with query \(x\), keys \(x_j\), values \(y_j\) and score \(-(x-x_j)^2/(2h^2)\).
When all keys have the same norm, this score equals \(x\,x_j/h^2\) up to terms that do not depend on \(j\), which the softmax ignores: dot-product attention with scale \(1/h^2\).
The weights \(K_h(x-x_j)/\sum_lK_h(x-x_l)\) are exactly
$$\operatorname{softmax}_j\big(-(x-x_j)^2/(2h^2)\big).$$Expanding,
$$-(x-x_j)^2/(2h^2)=-x^2/(2h^2)+x\,x_j/h^2-x_j^2/(2h^2).$$The first term is the same for every \(j\) and cancels in the softmax; if \(x_j^2\) is the same for all \(j\), so does the last. What remains is \(x\,x_j/h^2\). \(\square\)
# Attention as kernel smoothing: Nadaraya-Watson regression on the crash-helmet data (Lectures 1 and 7) import pandas as pd mc = pd.read_csv('data/mcycle.csv'); t_, a_ = mc['times'].to_numpy(), mc['accel'].to_numpy() def nw_attention(t_query, t_keys, values, bandwidth): scores = -(t_query[:, None] - t_keys[None, :]) ** 2 / (2 * bandwidth ** 2) # query-key similarity return softmax(scores) @ values # weighted average of values from sklearn.model_selection import KFold folds = list(KFold(5, shuffle=True, random_state=0).split(t_)) print('bandwidth (ms) 5-fold CV RMSE of the attention-weighted average') for h in [0.5, 1, 2, 4, 8]: err = np.sqrt(np.mean(np.concatenate([(nw_attention(t_[b], t_[a], a_[a], h) - a_[b]) ** 2 for a, b in folds]))) print(f'{h:14g} {err:10.2f}')
bandwidth (ms) 5-fold CV RMSE of the attention-weighted average
0.5 27.04
1 24.91
2 26.06
4 31.41
8 39.98
With a bandwidth of 1 ms, the attention-weighted average of nearby measurements predicts head acceleration with cross-validated RMSE 24.9 g, close to the 23.4 of Lecture 7's kernel ridge regression. A transformer's attention differs in two ways: the similarity is learned (through \(W_Q\) and \(W_K\)) rather than fixed, and it is computed between all pairs of positions of the input itself.
# Scaled dot-product self-attention, in numpy, on a five-token "sentence" rng = np.random.default_rng(0) tokens = ['the', 'cat', 'sat', 'on', 'it'] n, d_model, d_k = len(tokens), 16, 8 X = rng.normal(size=(n, d_model)) # one embedding per token (random here) Wq, Wk, Wv = (rng.normal(0, 1 / np.sqrt(d_model), (d_model, d_k)) for _ in range(3)) def softmax(Z): Z = Z - Z.max(-1, keepdims=True); E_ = np.exp(Z); return E_ / E_.sum(-1, keepdims=True) def self_attention(X): Q, K, Vv = X @ Wq, X @ Wk, X @ Wv A = softmax(Q @ K.T / np.sqrt(d_k)) # n x n attention weights, rows sum to 1 return A @ Vv, A out, A = self_attention(X) print('attention weights (row = query token, column = key token):') print(' ' + ''.join(f'{t:>7s}' for t in tokens)) for t, row in zip(tokens, A): print(f'{t:>7s} ' + ''.join(f'{a:7.3f}' for a in row)) P = np.eye(n)[[2, 0, 4, 1, 3]] # reorder the tokens out_p, _ = self_attention(P @ X) print('permutation equivariance: max |attn(PX) - P attn(X)| =', np.abs(out_p - P @ out).max()) # Why divide by sqrt(d_k): dot products of random vectors have variance d_k for dk in [8, 64, 512]: q, k = rng.normal(size=(10000, dk)), rng.normal(size=(10000, dk)) s = (q * k).sum(1) w_raw = softmax(rng.normal(size=(1000, 16, dk)) @ rng.normal(size=(dk,))) # 16 keys, unscaled scores print(f'd_k = {dk:3d}: variance of q.k = {s.var():7.1f}; largest attention weight without scaling, median over 1000 queries: {np.median(w_raw.max(1)):.3f}')
attention weights (row = query token, column = key token):
the cat sat on it
the 0.113 0.290 0.044 0.285 0.268
cat 0.050 0.211 0.230 0.032 0.476
sat 0.181 0.033 0.609 0.150 0.028
on 0.107 0.266 0.071 0.101 0.455
it 0.084 0.023 0.654 0.231 0.008
permutation equivariance: max |attn(PX) - P attn(X)| = 4.440892098500626e-16
d_k = 8: variance of q.k = 8.1; largest attention weight without scaling, median over 1000 queries: 0.585
d_k = 64: variance of q.k = 63.9; largest attention weight without scaling, median over 1000 queries: 0.928
d_k = 512: variance of q.k = 507.9; largest attention weight without scaling, median over 1000 queries: 1.000
(a) Self-attention without positional information is permutation-equivariant: reordering the tokens reorders the outputs in the same way,
$$\operatorname{SA}(PX)=P\operatorname{SA}(X).$$(b) If the entries of \(q,k\in\mathbb R^{d_k}\) are independent with mean 0 and variance 1, then
$$\operatorname{Var}(q^\top k)=d_k;$$dividing by \(\sqrt{d_k}\) keeps the scores at variance 1 whatever the dimension.
(a) \(Q,K,V\) become \(PQ,PK,PV\), so the score matrix becomes \(PQK^\top P^\top\); the row-wise softmax commutes with permuting rows and columns, giving
$$P\operatorname{softmax}(QK^\top/\sqrt{d_k})P^\top,$$and multiplying by \(PV\) gives \(P\operatorname{softmax}(\cdot)V\), using \(P^\top P=I\).
(b) \(q^\top k=\sum_iq_ik_i\) is a sum of \(d_k\) independent terms with mean 0 and variance \(\mathbb E[q_i^2]\mathbb E[k_i^2]=1\). \(\square\)
Part (a) is Proposition 9.1 again: self-attention is a graph neural network on the complete graph, with learned, data-dependent edge weights. It also means a transformer knows nothing about word order unless we tell it (Section 4). Part (b) matters because unscaled scores grow with \(d_k\), and a softmax of large numbers is nearly one-hot: in the code, with \(d_k=512\) and no scaling, the largest of 16 weights is 1.000 for the median query, so attention collapses to a hard lookup whose gradient is almost zero.
In a transformer with \(d_k=64\), by what number are the raw query–key dot products divided before the softmax?
Multi-head attention runs \(H\) attention operations ("heads") in parallel, each with its own projections into a space of dimension \(d/H\), and concatenates the results:
$$\operatorname{MHA}(X)=\big[\operatorname{head}_1,\dots,\operatorname{head}_H\big]W_O,\qquad\operatorname{head}_h=\operatorname{Attention}\big(XW_Q^{(h)},XW_K^{(h)},XW_V^{(h)}\big).$$The cost is about the same as one full-width head, but each head can attend to something different: one to the previous token, one to the subject of the sentence, one to matching brackets.
To give the model word order, add a positional encoding \(p_t\in\mathbb R^d\) to the embedding of the token at position \(t\). Vaswani et al. (2017) used fixed sinusoids,
$$p_{t,2i}=\sin\big(t/10000^{2i/d}\big),\qquad p_{t,2i+1}=\cos\big(t/10000^{2i/d}\big),$$a set of clocks running at geometrically spaced speeds, so that every position gets a distinct pattern and the encoding of position \(t+\Delta\) is a fixed linear function (a rotation of each sine–cosine pair) of the encoding of \(t\). GPT-2 instead learned one vector per position (as our tiny GPT does), and most current models use rotary embeddings (RoPE; Su et al., 2021), which rotate queries and keys by position-dependent angles so that their dot product depends only on the offset between positions.
A (pre-norm) transformer block maps a sequence of vectors \(X\in\mathbb R^{n\times d}\) to another of the same shape, in two residual steps (Lecture 11):
$$X\leftarrow X+\operatorname{MHA}\big(\operatorname{LN}(X)\big),\qquad X\leftarrow X+\operatorname{MLP}\big(\operatorname{LN}(X)\big),$$where LN is layer normalisation and the MLP, applied to each position separately, is \(\mathrm{GELU}(xW_1)W_2\) with a hidden width of about \(4d\) (Lecture 10a). The first step moves information between positions; the second computes at each position.
A transformer is an embedding layer, positional encodings, a stack of \(L\) blocks, a final layer norm and an output layer.
In a decoder (causal) transformer, position \(i\) may attend only to positions \(j\le i\): the scores for \(j>i\) are set to \(-\infty\) before the softmax (a causal mask).
The original transformer (Vaswani et al., 2017) put the layer norm after each residual addition ("post-norm"); almost all current models put it first, as above, because, as Lecture 11 showed, normalising the branch input keeps the residual stream's growth under control and makes deep stacks train reliably without warm-up tricks (Xiong et al., 2020).
For a sequence of \(n\) tokens of width \(d\), one block costs about \(12nd^2\) multiplications for the projections and MLP (\(4nd^2\) for \(Q,K,V\) and the output projection, \(8nd^2\) for the MLP) and \(2n^2d\) for the attention scores and weighted sums, and it must store \(n^2\) attention weights per head.
It has about \(12d^2\) parameters.
Projections: four \(d\times d\) matrices applied to \(n\) vectors, \(4nd^2\).
MLP: \(d\times4d\) and \(4d\times d\), \(8nd^2\).
Scores \(QK^\top\): \(n^2d\) in total across heads (each head \(n^2d/H\)); weighted sum \(AV\): another \(n^2d\).
Parameters: \(4d^2+8d^2=12d^2\), ignoring biases and layer norms. \(\square\)
Attention's cost is quadratic in the sequence length. The attention term overtakes the rest once \(2n^2d>12nd^2\), that is, once \(n>6d\); for long contexts (a book, an hour of audio) the \(n^2\) term dominates, which is why long-context models use tricks such as FlashAttention (Dao et al., 2022), which computes exact attention without ever storing the \(n\times n\) matrix, and why Lecture 11's linear-time state-space models are attractive.
A transformer processes 4,096 tokens with width \(d=1{,}024\). Then it processes 16,384 tokens. By what factor does the attention-score computation (\(\propto n^2d\)) grow?
Three families of transformer differ in their masks and their training objective. Encoder-only models such as BERT (Devlin et al., 2019) attend in both directions and are trained by masked language modelling: hide 15% of the tokens and predict them from both sides. They produce representations for classification, tagging and search. Decoder-only models such as GPT (Radford et al., 2018, 2019; Brown et al., 2020) use the causal mask and are trained to predict the next token,
$$\mathcal L=-\frac1n\sum_{t=1}^n\log p_\theta(x_t\mid x_1,\dots,x_{t-1}),$$the cross-entropy of Lectures 4 and 5 at every position at once, which by the chain rule of probability is the log-likelihood of the whole text. They generate. Encoder–decoder models such as T5 (Raffel et al., 2020) keep the original translation design, with a bidirectional encoder and a causal decoder that also attends to the encoder ("cross-attention"). Today's large language models are almost all decoder-only. Here is one, small enough to train in about twenty minutes on two CPU cores: 4 blocks, 4 heads, width 128, a context of 128 characters.
# A tiny GPT (decoder-only transformer) trained on characters of Shakespeare, in JAX import jax, jax.numpy as jnp, time chars = sorted(set(text)); stoi = {c: i for i, c in enumerate(chars)}; Vc = len(chars) ids = np.array([stoi[c] for c in text], np.int32); split = int(0.9 * len(ids)) T, d, n_layer, n_head = 128, 128, 4, 4 # context length, width, blocks, heads def init_gpt(key): ks = iter(jax.random.split(key, 4 + 6 * n_layer)); nrm = lambda shape, s: jax.random.normal(next(ks), shape) * s p = {'tok': nrm((Vc, d), 0.02), 'pos': nrm((T, d), 0.02), 'lnf': (jnp.ones(d), jnp.zeros(d)), 'blocks': []} for _ in range(n_layer): p['blocks'].append({'ln1': (jnp.ones(d), jnp.zeros(d)), 'qkv': nrm((d, 3 * d), 0.02), 'proj': nrm((d, d), 0.02 / np.sqrt(2 * n_layer)), 'ln2': (jnp.ones(d), jnp.zeros(d)), 'fc': nrm((d, 4 * d), 0.02), 'fc2': nrm((4 * d, d), 0.02 / np.sqrt(2 * n_layer))}) return p def layer_norm(x, gb): m, v = x.mean(-1, keepdims=True), x.var(-1, keepdims=True); return (x - m) / jnp.sqrt(v + 1e-5) * gb[0] + gb[1] def attention(b, x, return_weights=False): B, n, _ = x.shape; hd = d // n_head q, k, v = jnp.split(layer_norm(x, b['ln1']) @ b['qkv'], 3, axis=-1) q, k, v = (z.reshape(B, n, n_head, hd).transpose(0, 2, 1, 3) for z in (q, k, v)) # (B, heads, n, hd) scores = q @ k.transpose(0, 1, 3, 2) / np.sqrt(hd) mask = jnp.tril(jnp.ones((n, n), bool)) # causal: no peeking ahead w = jax.nn.softmax(jnp.where(mask, scores, -1e9), axis=-1) out = (w @ v).transpose(0, 2, 1, 3).reshape(B, n, d) @ b['proj'] return (out, w) if return_weights else out def gpt(p, idx): # idx: (B, n) character ids -> logits (B, n, Vc) x = p['tok'][idx] + p['pos'][:idx.shape[1]] for b in p['blocks']: x = x + attention(b, x) # communicate between positions x = x + jax.nn.gelu(layer_norm(x, b['ln2']) @ b['fc']) @ b['fc2'] # compute at each position return layer_norm(x, p['lnf']) @ p['tok'].T # output layer shares the token embedding def lm_loss(p, xb, yb): return -jnp.mean(jnp.take_along_axis(jax.nn.log_softmax(gpt(p, xb)), yb[..., None], -1)) def get_batch(lo, hi, n, seed): s = np.random.default_rng(seed).integers(lo, hi - T - 1, n) return np.stack([ids[i:i + T] for i in s]), np.stack([ids[i + 1:i + T + 1] for i in s]) steps, lr_max, warm = 3000, 1e-3, 200 @jax.jit def train_step(p, m, v, t, xb, yb): l, g = jax.value_and_grad(lm_loss)(p, xb, yb) lr = lr_max * jnp.minimum(1.0, t / warm) * 0.5 * (1 + jnp.cos(jnp.pi * t / steps)) # warm-up + cosine (Lecture 10b) m = jax.tree_util.tree_map(lambda a, b: 0.9 * a + 0.1 * b, m, g) v = jax.tree_util.tree_map(lambda a, b: 0.99 * a + 0.01 * b * b, v, g) p = jax.tree_util.tree_map(lambda q, a, b: q - lr * ((a / (1 - 0.9 ** t)) / (jnp.sqrt(b / (1 - 0.99 ** t)) + 1e-8) + 0.01 * q), p, m, v) # AdamW return p, m, v, l gpt_p = init_gpt(jax.random.PRNGKey(0)) print(f'{sum(x.size for x in jax.tree_util.tree_leaves(gpt_p)):,} parameters') m = jax.tree_util.tree_map(jnp.zeros_like, gpt_p); v = jax.tree_util.tree_map(jnp.zeros_like, gpt_p) Xv, Yv = get_batch(split, len(ids), 64, 123); val_loss = jax.jit(lm_loss); t0 = time.time() for t in range(1, steps + 1): xb, yb = get_batch(0, split, 32, t); gpt_p, m, v, l = train_step(gpt_p, m, v, t, xb, yb) if t in [1, 250, 1000, 3000]: print(f'step {t:5d}: train loss {float(l):.3f}, validation loss {float(val_loss(gpt_p, Xv, Yv)):.3f} nats/char ({time.time() - t0:.0f} s)') # Baseline: a bigram model (next character given the previous one), from counts B2 = np.ones((Vc, Vc)); np.add.at(B2, (ids[:split - 1], ids[1:split]), 1); B2 /= B2.sum(1, keepdims=True) print(f'bigram counts baseline: validation loss {-np.mean(np.log(B2[Xv.ravel(), Yv.ravel()])):.3f} nats/char') np.savez('gpt_params.npz', *[np.asarray(x) for x in jax.tree_util.tree_leaves(gpt_p)]) gpt_logits = jax.jit(gpt) def generate(p, prompt, n, pick, seed=0): r = np.random.default_rng(seed); s = [stoi[c] for c in prompt] for _ in range(n): ctx = s[-T:]; L = len(ctx) # pad to a fixed length: the causal mask makes padding harmless logits = np.asarray(gpt_logits(p, np.array(ctx + [0] * (T - L))[None])[0, L - 1], np.float64); s.append(pick(logits, r)) return ''.join(chars[i] for i in s) sample_t1 = lambda lg, r: r.choice(Vc, p=np.exp(lg - lg.max()) / np.exp(lg - lg.max()).sum()) print(generate(gpt_p, 'ROMEO:\n', 300, sample_t1))
813,440 parameters step 1: train loss 4.215, validation loss 4.192 nats/char (2 s) step 250: train loss 2.365, validation loss 2.416 nats/char (96 s) step 1000: train loss 1.709, validation loss 1.865 nats/char (371 s) step 3000: train loss 1.377, validation loss 1.598 nats/char (1116 s) bigram counts baseline: validation loss 2.515 nats/char ROMEO: O Gaunt, wick thou hast ofth steal forth! For do them hath accept, what'st kits their pressolvountly, To mercy an three her either or first old Is thing show the lquenchant from upon the violencin duty party more sent visit time, That newfuld, they shaull scorn shall f thee: thy-- here shall for wit
The model has 813,440 parameters. Before training it guesses uniformly (4.19 nats per character, against \(\ln65=4.17\)). After 250 steps it has learned roughly what a bigram table knows (2.42, against 2.52 for a model that predicts each character from counts of what follows the previous one); after 3,000 steps, about nineteen minutes, it reaches 1.60 nats per character on held-out text. Lecture 11's character-level LSTM, trained on the same 90/10 split with the same number of steps, reached 1.62 in five minutes. At this tiny scale and budget the transformer is barely better and four times slower per step on a CPU, so this is not where its advantage lies. It lies in parallelism along the sequence, which a GPU exploits and our two CPU cores barely can, and in scaling: transformers keep improving as data and parameters grow by orders of magnitude (Section 9), where Kaplan et al. (2020) found LSTMs falling behind transformers, above all in using long contexts. The sample has the same strengths and weaknesses as the LSTM's: the format of a play, plausible names ("O Gaunt"), mostly real words and no sense.
The maps show the division of labour typical of small transformers. In the first layer attention is diffuse, mixing information from many earlier characters. In layers 2 and 3 most heads put about 30% of their weight on the current character and about 30% on the one just before it: these are previous-token heads, which let later layers know which character came before. Others track words: when the most recent space is at least two characters back, layer 2, head 1 still puts on average 31% of its weight on it (against about 7% for weight spread evenly over the earlier characters), a marker of where the current word began (choose a query in the middle of a word to see it). What we did not find is a clear induction head: for each character that has occurred earlier in the line, we measured the weight a head puts on the character that followed the earlier occurrence, and no head puts more than 9% there on average. This model and this short line may be too small to show one; the second project at the end of the lecture looks for induction heads systematically.
How far is our tiny GPT from a real one? GPT-2 small (Radford et al., 2019) has the same architecture with 12 blocks, 12 heads, width 768 and a context of 1,024 tokens: 124 million parameters, trained on 40 GB of web pages. It cannot have been trained for Shakespeare, but the web contains Shakespeare, so it may have seen this very text. We score the same validation text, in nats per character so that the two models' different vocabularies do not matter, and then look for heads with a recognisable job.
# Pre-trained GPT-2 small (124M parameters, trained on 40 GB of web text): how far is it from our tiny GPT, and what do its heads do? import torch, time from transformers import GPT2LMHeadModel, GPT2TokenizerFast gtok = GPT2TokenizerFast.from_pretrained('openai-community/gpt2') gpt2 = GPT2LMHeadModel.from_pretrained('openai-community/gpt2', attn_implementation='eager').eval() val = open('data/tinyshakespeare.txt').read(); val = val[int(0.9 * len(val)):] # the same validation text as the tiny GPT (last 10%) vid = gtok(val).input_ids; nll, n, t0 = 0.0, 0, time.time() with torch.no_grad(): for s in range(0, len(vid) - 1, 512): # windows of 1,024 tokens, scoring the second half of each (512 tokens of context) lo = max(0, s - 512); x = torch.tensor([vid[lo:s + 512 + 1]]) lp = torch.log_softmax(gpt2(x[:, :-1]).logits[0], -1); tgt = x[0, 1:] k = s - lo; nll -= lp[k:].gather(-1, tgt[k:, None]).sum().item(); n += len(tgt) - k print(f"GPT-2 on the validation text: {len(vid):,} tokens for {len(val):,} characters; " f"{nll / len(val):.3f} nats per character ({nll / n:.2f} per token; {time.time() - t0:.0f} s)") print("tiny GPT (above): 1.598 nats per character; bigram counts: 2.515") for prompt in ["ROMEO:\n", val[:400] + "\n\nROMEO:\n"]: # a bare prompt, then the same after 400 characters of the play torch.manual_seed(0); ids = gtok(prompt, return_tensors='pt').input_ids out = gpt2.generate(ids, max_new_tokens=40, do_sample=True, top_p=0.9, pad_token_id=50256) print(f"GPT-2, {len(prompt)}-character prompt ending 'ROMEO:', nucleus sampling (p = 0.9):\n " + gtok.decode(out[0, ids.shape[1]:]).strip().replace('\n', '\n ')) # Heads with a job: previous-token heads and induction heads (Olsson et al., 2022), found by feeding random tokens repeated twice g = torch.Generator().manual_seed(0); R = torch.randint(1000, 20000, (8, 40), generator=g); X = torch.cat([R, R], 1) with torch.no_grad(): att = torch.stack(gpt2(X, output_attentions=True).attentions) # layers x batch x heads x 80 x 80 t = torch.arange(41, 80) prev = att[..., t, t - 1].mean((1, 3)); ind = att[..., t, t - 39].mean((1, 3)) # attention to the previous token; to the token after the earlier copy top = lambda S: ', '.join(f'{i // 12}.{i % 12} ({S.flatten()[i]:.2f})' for i in torch.argsort(S.flatten(), descending=True)[:4].tolist()) print(f"previous-token heads (layer.head, mean attention to the previous token): {top(prev)}") print(f"induction heads (mean attention to the token after the earlier occurrence): {top(ind)}") with torch.no_grad(): lp2 = torch.log_softmax(gpt2(X).logits, -1) loss1 = -lp2[:, :39].gather(-1, X[:, 1:40, None]).mean().item(); loss2 = -lp2[:, 40:79].gather(-1, X[:, 41:80, None]).mean().item() print(f"loss on the random tokens: {loss1:.2f} nats on the first copy, {loss2:.2f} on the repeat (in-context copying)")
GPT-2 on the validation text: 36,059 tokens for 111,540 characters; 1.258 nats per character (3.89 per token; 378 s) tiny GPT (above): 1.598 nats per character; bigram counts: 2.515 GPT-2, 7-character prompt ending 'ROMEO:', nucleus sampling (p = 0.9): I wanted to make something that is as close to the old EZMEGO as possible, so I started to build a nice EZMEGO in a very rough way. I GPT-2, 409-character prompt ending 'ROMEO:', nucleus sampling (p = 0.9): I see your pride, your Amanence, my heart, your Flesh-blood, my heart, my Flesh-blood, my heart, my previous-token heads (layer.head, mean attention to the previous token): 4.11 (0.99), 6.8 (0.67), 3.7 (0.53), 2.2 (0.49) induction heads (mean attention to the token after the earlier occurrence): 5.5 (0.94), 6.9 (0.91), 7.10 (0.91), 5.1 (0.90) loss on the random tokens: 12.59 nats on the first copy, 0.25 on the repeat (in-context copying)
GPT-2 predicts the held-out Shakespeare at 1.258 nats per character, against 1.60 for our model: per character it is 79% as surprised. Its 36,059 BPE tokens cover the 111,540 characters at about 3.1 characters each, so each token is scored at 3.89 nats. The bare prompt "ROMEO:" does not tell it which part of the web it is in, and it writes modern prose about a design project. Given 400 characters of the play first, it switches, with no change to its weights, to short lines in a vaguely Elizabethan register ("I see your pride, your / ... my heart, your"), though it soon repeats itself, even with nucleus sampling on. This is in-context learning (Section 9) at a small scale. Part of the gap in nats per character is that advantage: GPT-2 conditions on 512 to 1,023 earlier tokens (fewer only in the first window), about 1,500 to 3,000 characters, where our model sees 128.
The heads have recognisable jobs. On a sequence of random tokens repeated twice, head 4.11 (layer 4, head 11, counting from 0) puts 0.99 of its weight on the previous token, almost all of it: a previous-token head. Heads 5.5, 6.9, 7.10 and 5.1 put 0.90–0.94 of their weight on the token that followed the current token's earlier occurrence. These are the induction heads of Olsson et al. (2022): a previous-token head in an earlier layer writes "the token before me was A" into each position, and the induction head, looking for positions whose previous token matches the current one, finds where A occurred before and copies what came next. The effect on the predictions is dramatic: GPT-2's loss on the random tokens falls from 12.59 nats on the first copy, worse than uniform guessing over its 50,257 tokens (10.8 nats), to 0.25 on the repeat. Our tiny GPT showed no clear induction head; this model has several, in its middle layers, which is where Olsson et al. find them in models of this size. The widget shows them at work on real sentences.
Dzmitry Bahdanau, Kyunghyun Cho and Yoshua Bengio introduced attention for translation in 2014 (published 2015), as a way for the decoder to "align" with the relevant source words. In 2017 eight Google researchers (Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Łukasz Kaiser and Illia Polosukhin) dropped the recurrence entirely in "Attention is all you need", and the transformer trained faster and translated better. In 2018 OpenAI's GPT and Google's BERT showed that a transformer pre-trained on unlabelled text could be fine-tuned for almost any language task; GPT-2 (2019) generated fluent paragraphs, and GPT-3 (2020, 175 billion parameters) performed new tasks from a few examples in its prompt. Instruction tuning and reinforcement learning from human feedback (Lecture 22) turned such models into assistants, and OpenAI's ChatGPT (November 2022) reached a hundred million users within about two months.
Our tiny GPT reads characters. Large models read tokens, chunks of text chosen by a tokeniser. Characters make sequences long (and attention is quadratic in length); whole words make the vocabulary huge and leave every misspelling, rare name and new word "unknown". Subword tokenisers sit in between: common words become single tokens, rare words split into familiar pieces. The most widely used is byte-pair encoding, adapted from a 1994 compression algorithm by Sennrich, Haddow and Birch (2016).
Start with a vocabulary of single characters (or bytes) and the training text split into words.
Repeat \(M\) times: count every pair of adjacent symbols across the corpus, and merge the most frequent pair into a new symbol, recording the merge.
To tokenise new text, split it into words and apply the recorded merges in the order they were learned. The final vocabulary has (number of characters) \(+M\) symbols.
# Byte-pair encoding from scratch (Sennrich, Haddow & Birch, 2016), trained on the first 90% of Shakespeare n_tr = int(0.9 * len(text)); train_text, val_text = text[:n_tr], text[n_tr:] def pre_split(s): # GPT-2 style: words keep their leading space return re.findall(r" ?[A-Za-z']+| ?[0-9]+| ?[^\sA-Za-z0-9']+|\s+", s) def learn_bpe(s, n_merges): freq = collections.Counter(pre_split(s)) words_ = [list(w) for w in freq]; cnt = list(freq.values()) # each distinct word as a list of symbols pairs, where = collections.Counter(), collections.defaultdict(set) # pair counts, and which words contain each pair for k, w in enumerate(words_): for a, b in zip(w, w[1:]): pairs[a, b] += cnt[k]; where[a, b].add(k) merges = [] for _ in range(n_merges): (a, b), c = pairs.most_common(1)[0] if c < 2: break merges.append((a, b)) for k in list(where[a, b]): # only the words that contain the pair change w = words_[k] for x, y in zip(w, w[1:]): pairs[x, y] -= cnt[k] out, i = [], 0 while i < len(w): if i < len(w) - 1 and w[i] == a and w[i + 1] == b: out.append(a + b); i += 2 else: out.append(w[i]); i += 1 words_[k] = out for x, y in zip(out, out[1:]): pairs[x, y] += cnt[k]; where[x, y].add(k) del pairs[a, b] return merges def encode(s, merges): rank = {m: r for r, m in enumerate(merges)}; out = [] for w in pre_split(s): sym = list(w) while len(sym) > 1: cand = [(rank.get((sym[i], sym[i + 1]), 10**9), i) for i in range(len(sym) - 1)] r, i = min(cand) if r == 10**9: break sym[i:i + 2] = [sym[i] + sym[i + 1]] out += sym return out merges = learn_bpe(train_text, 2000) print('first 12 merges:', ' '.join(repr(a + b) for a, b in merges[:12])) print('merges 990-1000:', ' '.join(repr(a + b) for a, b in merges[990:1000])) sample_line = "To be, or not to be, that is the question" print('BPE-1000 tokens of a famous line:', encode(sample_line, merges[:1000])) import json, sys sys.path.insert(0, 'data'); import gpt2_encoder enc = gpt2_encoder.Encoder(json.load(open('data/encoder.json')), [tuple(l.split()) for l in open('data/vocab.bpe', encoding='utf-8').read().split('\n')[1:-1]]) print('GPT-2 tokens of the same line:', [enc.decoder[t].replace('Ġ', ' ') for t in enc.encode(sample_line)]) n_words = len(re.findall(r"[A-Za-z']+", val_text)) print(f'\nvalidation text: {len(val_text):,} characters, {n_words:,} words') for name, toks in [('characters', len(val_text))] + [(f'our BPE, {k} merges', len(encode(val_text, merges[:k]))) for k in [100, 500, 1000, 2000]] + \ [('GPT-2 (50,000 merges, trained on web text)', len(enc.encode(val_text)))]: print(f'{name:44s} {toks:8,d} tokens {toks / n_words:5.2f} per word')
first 12 merges: ' t' 'he' ' a' 'ou' ' s' ' m' 'in' ' w' 're' 'ha' ' the' 'nd' merges 990-1000: 'ail' " 'tw" 'erer' 'ary' ' nat' 'cle' 'iet' 'Will' 'ORD' ' none' BPE-1000 tokens of a famous line: ['To', ' be', ',', ' or', ' not', ' to', ' be', ',', ' that', ' is', ' the', ' qu', 'est', 'ion'] GPT-2 tokens of the same line: ['To', ' be', ',', ' or', ' not', ' to', ' be', ',', ' that', ' is', ' the', ' question'] validation text: 111,540 characters, 20,316 words characters 111,540 tokens 5.49 per word our BPE, 100 merges 68,841 tokens 3.39 per word our BPE, 500 merges 51,913 tokens 2.56 per word our BPE, 1000 merges 46,332 tokens 2.28 per word our BPE, 2000 merges 41,688 tokens 2.05 per word GPT-2 (50,000 merges, trained on web text) 36,059 tokens 1.77 per word
The first merges learned from Shakespeare are " t", "he", " a", "ou", and by the eleventh merge " the" is a single token. After 1,000 merges, "To be, or not to be, that is the question" is tokenised almost exactly as GPT-2 does, except that "question" is still split into " qu", "est", "ion". On the held-out tenth of Shakespeare, characters cost 5.5 tokens per word; our BPE with 2,000 merges costs 2.05; GPT-2's tokeniser, with 50,000 merges learned from web text, costs 1.77, despite never having been trained on Shakespeare specifically. Tokenisation has visible consequences: models struggle to count the letters in a word they see as two tokens, numbers split into arbitrary pieces, and languages under-represented in the tokeniser's training text need more tokens per word, so they cost more and fit less into the context (Petrov et al., 2023).
Why do language models use subword tokens rather than whole words?
A language model does not write text; it gives a probability distribution over the next token. Turning a sequence of such distributions into text is a separate decision, called decoding, and it changes the output as much as the model does. Two natural goals pull in opposite directions. We might want the most probable continuation, or we might want a continuation that looks like a typical sample of human text, and these are not the same thing: the single most probable sentence is usually short, bland and repetitive, while each human sentence is individually improbable.
Let \(z\in\mathbb R^V\) be the logits for the next token and \(p=\operatorname{softmax}(z)\).
A model's first token is A with probability 0.6 or B with probability 0.4. After A, five tokens are equally likely (0.2 each); after B, the token X has probability 0.9. Which two-token sequence is most probable, and what does greedy decoding choose?
Greedy takes A (0.6), then any of the five continuations, for a sequence probability of \(0.6\times0.2=0.12\). But \(P(\text{B X})=0.4\times0.9=0.36\), three times larger. Beam search with width 2 keeps both A and B after the first step and finds B X. Even beam search is not exact: with any fixed width, a sequence whose prefix falls out of the beam is lost.
Let \(p^{(T)}_i\propto e^{z_i/T}\). As \(T\to0^+\), \(p^{(T)}\) concentrates on the largest logit (greedy decoding, when it is unique); at \(T=1\) it is the model's distribution; as \(T\to\infty\) it tends to the uniform distribution.
The entropy \(H(p^{(T)})\) is non-decreasing in \(T\), and strictly increasing unless all logits are equal.
Write \(\beta=1/T\) and \(p_i=e^{\beta z_i}/Z(\beta)\). For \(i\) not a maximiser,
$$p_i/p_{i^*}=e^{\beta(z_i-z_{i^*})}\to0$$as \(\beta\to\infty\), and every ratio tends to 1 as \(\beta\to0\), which gives the limits.
For the entropy, \(\log p_i=\beta z_i-\log Z\), so
$$H=-\sum_ip_i\log p_i=\log Z-\beta\,\mathbb E_p[z].$$Since \(\frac{d}{d\beta}\log Z=\mathbb E_p[z]\) and \(\frac{d}{d\beta}\mathbb E_p[z]=\operatorname{Var}_p(z)\) (the standard identities for the log-partition function of an exponential family),
$$\frac{dH}{d\beta}=\mathbb E_p[z]-\mathbb E_p[z]-\beta\operatorname{Var}_p(z)=-\beta\operatorname{Var}_p(z)\le0.$$So the entropy decreases in \(\beta\) and increases in \(T=1/\beta\), strictly whenever the logits are not all equal (then \(\operatorname{Var}_p(z)>0\), since every \(p_i>0\)). \(\square\)
# Decoding the tiny GPT: greedy, beam search, temperature, top-k and nucleus (top-p) sampling words_all = set(re.findall(r"[a-z']+", text[:split].lower())) def log_softmax(lg): lg = lg - lg.max(); return lg - np.log(np.exp(lg).sum()) def sampler(temp=1.0, top_k=None, top_p=None): def pick(lg, r): lp = log_softmax(lg / temp); p = np.exp(lp) if top_k is not None: p[np.argsort(-p)[top_k:]] = 0 if top_p is not None: order = np.argsort(-p); keep = np.cumsum(p[order]) - p[order] < top_p # smallest set with mass >= top_p mask = np.zeros_like(p, bool); mask[order[keep]] = True; p[~mask] = 0 return r.choice(len(p), p=p / p.sum()) return pick greedy = lambda lg, r: int(np.argmax(lg)) def beam_search(p, prompt, n, width=5): beams = [([stoi[c] for c in prompt], 0.0)] for _ in range(n): ctxs = [b[0][-T:] for b in beams]; L = [len(c) for c in ctxs] batch = np.array([c + [0] * (T - len(c)) for c in ctxs]) lg = np.asarray(gpt_logits(p, batch), np.float64) cand = [] for (seq, s), row, l in zip(beams, lg, L): lp = log_softmax(row[l - 1]) for j in np.argsort(-lp)[:width]: cand.append((seq + [int(j)], s + lp[j])) beams = sorted(cand, key=lambda c: -c[1])[:width] return ''.join(chars[i] for i in beams[0][0]) def logprob_per_char(p, s, n_prompt): # the model's own log-probability of what was generated idx = [stoi[c] for c in s]; tot = 0.0 for start in range(n_prompt, len(idx), T // 2): lo = max(0, start - T // 2); ctx = idx[lo:start + T // 2][:T] lg = np.asarray(gpt_logits(p, np.array(ctx + [0] * (T - len(ctx)))[None])[0], np.float64) for k in range(start - lo, min(len(ctx), start - lo + T // 2)): if lo + k >= n_prompt and k >= 1: tot += log_softmax(lg[k - 1])[ctx[k]] return tot / (len(idx) - n_prompt) def repetition(s, n=10): # share of 10-character strings that occurred earlier grams = [s[i:i + n] for i in range(len(s) - n)]; seen = set(); rep = 0 for g_ in grams: rep += g_ in seen; seen.add(g_) return rep / max(1, len(grams)) prompt = 'KING HENRY:\nWhat says the ' outs = {'greedy': generate(gpt_p, prompt, 400, greedy), 'beam search, width 5': beam_search(gpt_p, prompt, 400)} for name, kw in [('temperature 0.5', dict(temp=0.5)), ('temperature 1.0 (pure sampling)', dict(temp=1.0)), ('temperature 1.5', dict(temp=1.5)), ('top-k, k = 5', dict(top_k=5)), ('top-p (nucleus), p = 0.9', dict(top_p=0.9))]: outs[name] = generate(gpt_p, prompt, 400, sampler(**kw), seed=7) print('method log-prob/char repeated 10-grams real words') for name, s in outs.items(): gen = s[len(prompt):]; ws = re.findall(r"[a-z']+", gen.lower()) print(f'{name:32s} {logprob_per_char(gpt_p, s, len(prompt)):13.3f} {repetition(gen):17.1%} {np.mean([w in words_all for w in ws]):10.1%}') for name in ['greedy', 'beam search, width 5', 'temperature 1.5', 'top-p (nucleus), p = 0.9']: print(f'\n--- {name} ---\n' + outs[name][len(prompt) - 15:len(prompt) + 220])
method log-prob/char repeated 10-grams real words greedy -0.903 82.8% 98.9% beam search, width 5 -0.690 40.3% 98.7% temperature 0.5 -1.022 0.0% 94.7% temperature 1.0 (pure sampling) -1.443 0.3% 87.8% temperature 1.5 -2.160 0.0% 54.3% top-k, k = 5 -1.192 0.0% 95.4% top-p (nucleus), p = 0.9 -1.183 0.0% 93.7% --- greedy --- What says the stand the stand of the state, And the state of the state of the state, And the state of the state of the state of the state The state of the stand of the state of the state That the state of the stand of the state of the --- beam search, width 5 --- What says the common of the counsel of the counsel That he hath been the common of the world. KING RICHARD III: What is thou art thou hast thou art their hands, And thou hast thou art the world, and that they That thoughtst thou hast --- temperature 1.5 --- What says the must tRone bear.nd,at laKing ble Do fAuldomers miserage thy mother'dn, as I: what? Third Consor, Adx; gracious: a rodes To't be hurl,--whitherini-ffreships he duteous, sirda'd, rawly wad dear nevals to be Wough and to s --- top-p (nucleus), p = 0.9 --- What says the not grave in my worthaped it. DUKE OF AUMERLE: My life thy mind forth, that what may me. ROMEO: A will her, speak, and speak me without my life; I will not dangerous honour his brought Again the full of any aim pretth;
The table makes the trade-off concrete. Greedy decoding produces almost only real words (98.9%) and gets stuck at once: "the state of the state of the state", with 83% of its 10-character strings repeats of earlier ones. Beam search finds text with a higher probability under the model (−0.69 nats per character against −0.90 for greedy) and still loops ("thou hast thou art thou hast"). Pure sampling at \(T=1\) never repeats itself but produces made-up words (only 88% real), and at \(T=1.5\) it collapses into gibberish (54%). Temperature 0.5, top-\(k\) and nucleus sampling sit in between: no repetition and 94–95% real words. Note the log-probabilities. Real Shakespeare scores −1.60 nats per character under this model (the validation loss), far below greedy's −0.90 and beam's −0.69. Human text is not the most probable text; it is typical text, and decoding methods that aim for maximal probability produce something no person writes (Holtzman et al., 2020). Large language models are usually sampled at a temperature between about 0.5 and 1 with nucleus sampling, and greedy decoding is used where there is a single right answer.
A model has two possible next tokens with logits 2 and 0. At temperature 1 the first has probability \(e^2/(e^2+1)=0.881\). What is its probability at temperature 0.5? (Three decimal places.)
The transformer's success rests less on the architecture than on a training recipe. Pre-train a large model on a large amount of unlabelled text with next-token prediction (or masked-token prediction), which needs no human labels at all. Then adapt it: fine-tune all the weights on a smaller labelled dataset, or only a low-rank update \(W+BA\) with \(B\in\mathbb R^{d\times r}\), \(A\in\mathbb R^{r\times d}\), \(r\ll d\) (LoRA, Hu et al., 2022; the low-rank approximation of Lecture 2), or not change the weights at all. GPT-3 (Brown et al., 2020) showed that a large enough model can perform a new task from a description and a few examples in its prompt:
English: sea otter French: loutre de mer English: cheese French: fromage English: peppermint French:
This is in-context learning: the "training examples" are part of the input, and the "learning" happens in the forward pass. How can a fixed network learn? Part of the answer is mechanistic. Olsson et al. (2022) found induction heads in transformers of all sizes: a pair of attention heads in successive layers, the first of which copies information about each token's predecessor into its position, so that the second can look for earlier occurrences of the current token and copy the token that followed them ("…A B … A → B"). Induction heads appear abruptly during training, at the same moment that the model's ability to use long contexts improves, and they implement the simplest form of learning from the context: continuing a pattern. The project at the end of this lecture looks for them in our tiny GPT.
Xie, Raghunathan, Liang and Ma (2022) offered a statistical explanation. Suppose pre-training documents are generated by first drawing a latent "concept" \(\theta\) (a topic, a format, a task) and then text given \(\theta\). A model that predicts the next token optimally must compute the posterior predictive
$$p(x_{t+1}\mid x_{1:t})=\int p(x_{t+1}\mid x_{1:t},\theta)\,p(\theta\mid x_{1:t})\,d\theta,$$so it must implicitly infer \(\theta\) from the prompt. A few examples in the prompt concentrate the posterior on the concept that generated them, and the model then behaves as if it had learned the task. The same idea, run deliberately, gives prior-fitted networks: TabPFN (Hollmann et al., 2023, 2025; Lecture 8) is a transformer pre-trained on millions of synthetic tabular datasets drawn from a prior over data-generating processes. Given a real training set in its context, it outputs an approximation to the Bayesian posterior predictive in a single forward pass, and on small tables it is competitive with tuned gradient boosting.
The third ingredient is scale. Kaplan et al. (2020) found that the test loss of language models falls as a power law in the number of parameters \(N\), the amount of data \(D\) and the compute \(C\), over seven orders of magnitude, provided none of the three is the bottleneck: for example \(L(N)\approx(N_c/N)^{\alpha_N}\) with \(\alpha_N\approx0.076\). Training costs about \(C\approx6ND\) floating-point operations (2 per parameter per token for the forward pass, 4 for the backward pass). Hoffmann et al. (2022) refitted these laws and found that for a fixed compute budget, parameters and tokens should grow in equal proportion, roughly 20 training tokens per parameter; their 70-billion-parameter Chinchilla, trained on 1.4 trillion tokens, beat the 280-billion-parameter Gopher trained with the same compute on fewer tokens. Scaling laws are empirical, not theorems, and they predict the loss, not which abilities appear at which loss; apparent sudden "emergent" abilities often become smooth when measured with a continuous metric instead of exact-match accuracy (Schaeffer, Miranda and Koyejo, 2023).
Using \(C\approx6ND\), how much compute did Chinchilla's training take (70 billion parameters, 1.4 trillion tokens)? Give the answer in units of \(10^{23}\) floating-point operations.
A language model's knowledge is frozen at training time and stored diffusely in its weights, so it cannot cite sources, does not know about recent or private documents, and, asked about something it does not know, often produces a fluent, confident and wrong answer (a "hallucination"). Retrieval-augmented generation (RAG) fixes part of this by searching a document collection for passages relevant to the question and putting them in the model's context. How well it works depends mostly on the search. There are two families of retriever.
BM25 (Robertson and Zaragoza, 2009) scores a document \(d\) for a query \(q\) by the words they share:
$$\operatorname{BM25}(q,d)=\sum_{w\in q}\operatorname{idf}(w)\,\frac{f(w,d)\,(k_1+1)}{f(w,d)+k_1\big(1-b+b\,|d|/\overline{|d|}\big)},$$where \(f(w,d)\) counts \(w\) in \(d\),
$$\operatorname{idf}(w)=\log\big(1+\frac{N-n_w+0.5}{n_w+0.5}\big)$$is large for words in few of the \(N\) documents, and \(k_1\approx1.5\), \(b\approx0.75\) make the score saturate in repeated words and discount long documents.
A dense retriever maps queries and documents to vectors with an encoder \(E\) and scores them by
$$s(q,d)=E(q)^\top E(d).$$It is trained on pairs of a query and a relevant passage \(d^+\) by the contrastive InfoNCE loss
$$\mathcal L=-\log\frac{e^{s(q,d^+)/\tau}}{e^{s(q,d^+)/\tau}+\sum_{j}e^{s(q,d_j^-)/\tau}},$$the cross-entropy of picking the relevant passage out of a batch that also contains irrelevant ones \(d_j^-\) (Karpukhin et al., 2020).
Reciprocal rank fusion combines rankings by \(\sum_r1/(60+\operatorname{rank}_r(d))\) (Cormack, Clarke and Büttcher, 2009).
Dense retrieval can match a question to a passage that uses different words for the same thing; BM25 cannot, but it never misses an exact name, number or rare term, and it needs no training. To compare them we need a corpus and questions with known answers, and we have one: the eleven lectures of this course so far, split into 890 paragraphs, with 32 questions written to be answered by a known section and phrased, as students would, mostly without the section's technical terms ("maximise the gap between two classes" for the SVM section). We try two dense retrievers: the simplest one there is, latent semantic analysis, a 256-dimensional truncated SVD of the tf-idf matrix (Deerwester et al., 1990; Lecture 16); and a pretrained neural sentence encoder, all-MiniLM-L6-v2, a 22-million-parameter transformer distilled from a larger one (Wang et al., 2020) and then trained contrastively, as in Definition 12.6, on about a billion pairs of related sentences (Reimers and Gurevych, 2019).
# A mini search engine over this course's own lecture notes: BM25 (lexical), LSA and a neural sentence encoder (dense), and hybrids import html as htmllib, glob, os files = sorted(glob.glob('corpus/ML-L*.html')) # the published notes of Lectures 1-10 chunks = [] # (lecture, section, text) for f in files: lec = re.search(r'ML-L(\d+[ab]?)', f).group(1) page = open(f).read(); page = page[page.find('<h2 id="s1"'):] for sec in re.split(r'(?=<h2 id="s\d+")', page): m = re.match(r'<h2 id="(s\d+)"', sec) if not m: continue for par in re.findall(r'<p[^>]*>(.*?)</p>', sec, re.S): t = htmllib.unescape(re.sub(r'<[^>]+>', ' ', par)); t = re.sub(r'\\\(|\\\)|\s+', ' ', t).strip() if len(t) > 120: chunks.append((lec, m.group(1), t)) print(f'{len(files)} lectures, {len(chunks):,} paragraphs') tok = lambda s: re.findall(r'[a-z0-9]+', s.lower()) STOP = set('the a an of to and in is are be for on that this it with as by or we its at from which can each one not their our has have'.split()) docs = [[w for w in tok(c[2]) if w not in STOP] for c in chunks] df = collections.Counter(w for d_ in docs for w in set(d_)); N = len(docs); avgdl = np.mean([len(d_) for d_ in docs]) def bm25(query, k1=1.5, b=0.75): q = [w for w in tok(query) if w not in STOP]; scores = np.zeros(N) for i, d_ in enumerate(docs): tf = collections.Counter(d_); dl = len(d_) for w in q: if w in tf: idf = np.log(1 + (N - df[w] + 0.5) / (df[w] + 0.5)) scores[i] += idf * tf[w] * (k1 + 1) / (tf[w] + k1 * (1 - b + b * dl / avgdl)) return scores from sklearn.feature_extraction.text import TfidfVectorizer from sklearn.decomposition import TruncatedSVD tfidf = TfidfVectorizer(stop_words='english', sublinear_tf=True, min_df=2) D = tfidf.fit_transform([c[2] for c in chunks]); svd = TruncatedSVD(256, random_state=0).fit(D) Z = svd.transform(D); Z /= np.linalg.norm(Z, axis=1, keepdims=True) + 1e-12 def dense(query): z = svd.transform(tfidf.transform([query]))[0]; return Z @ (z / (np.linalg.norm(z) + 1e-12)) from sentence_transformers import SentenceTransformer # all-MiniLM-L6-v2: a 22M-parameter encoder trained contrastively on 1B sentence pairs st = SentenceTransformer('sentence-transformers/all-MiniLM-L6-v2', device='cpu'); st.max_seq_length = 256 E = st.encode([c[2] for c in chunks], batch_size=64, normalize_embeddings=True) def neural(query): return E @ st.encode([query], normalize_embeddings=True)[0] def fuse(f1, f2, k=60): # reciprocal rank fusion of two rankings def h(query): r1 = np.argsort(np.argsort(-f1(query))); r2 = np.argsort(np.argsort(-f2(query))) return 1 / (k + 1 + r1) + 1 / (k + 1 + r2) # ranks counted from 1 return h queries = [("how do I pick a decision threshold when missing a disease is worse than a false alarm", '05', 's1'), ("why is squared error minimised by the mean but absolute error by the median", '05', 's2'), ("probability forecasts that reward honesty", '05', 's5'), ("how many training examples are enough for a finite set of classifiers", '06', 's3'), ("a network that memorises random labels", '06', 's1'), ("largest set of points that a class can label in every possible way", '06', 's5'), ("test error falls again after the interpolation threshold", '06', 's8'), ("maximise the gap between two classes", '07', 's1'), ("replace inner products with a similarity function", '07', 's4'), ("Bayesian version of kernel ridge regression with error bars", '07', 's7'), ("why a single decision tree is unstable", '08', 's3'), ("fit each new tree to the errors of the current model", '08', 's6'), ("explain one prediction by sharing credit fairly among the features", '08', 's9'), ("which customers benefit from a treatment, using forests", '08', 's10'), ("split a friendship network into two groups with an eigenvector", '09', 's4'), ("classify thousands of points from a handful of labels on a graph", '09', 's5'), ("rank web pages by a random surfer", '09', 's6'), ("why message passing networks cannot count triangles", '09', 's8'), ("a ReLU network is a piecewise linear function", '10a', 's1'), ("can one hidden layer approximate any continuous function", '10a', 's5'), ("chain rule applied backwards through a network", '10b', 's2'), ("choosing the scale of random initial weights so signals do not vanish", '10b', 's3'), ("keep dropout on at test time to estimate uncertainty", '10b', 's6'), ("decoupled weight decay in Adam", '10b', 's4'), ("least squares as an orthogonal projection", '03', 's2'), ("penalties that shrink coefficients or set some to zero", '03', 's5'), ("why regression coefficients are not causal effects", '03', 's7'), ("closest point on a line to a vector", '02', 's2'), ("every matrix is a rotation, a stretch and a rotation", '02', 's5'), ("classify a point by the labels of its nearest neighbours", '01', 's3'), ("best possible classifier if we knew the true distribution", '01', 's6'), ("weighting by the propensity score to estimate causal effects", '04', 's7')] def evaluate(score_fn): rr, hits5 = [], [] for q, lec, sec in queries: order = np.argsort(-score_fn(q)) rel = [i for i, j in enumerate(order[:100]) if chunks[j][0] == lec and chunks[j][1] == sec] rr.append(1 / (rel[0] + 1) if rel else 0.0); hits5.append(bool(rel) and rel[0] < 5) return np.mean(hits5), np.mean(rr) print(f'{len(queries)} questions, each with one correct lecture section') print('method answer section in top 5 mean reciprocal rank') for name, fn in [('BM25 (word matching)', bm25), ('LSA, 256 dimensions (dense)', dense), ('MiniLM sentence encoder (dense)', neural), ('hybrid: BM25 + LSA', fuse(bm25, dense)), ('hybrid: BM25 + MiniLM', fuse(bm25, neural))]: h5, mrr = evaluate(fn); print(f'{name:35s} {h5:24.1%} {mrr:20.3f}')
11 lectures, 890 paragraphs 32 questions, each with one correct lecture section method answer section in top 5 mean reciprocal rank BM25 (word matching) 93.8% 0.700 LSA, 256 dimensions (dense) 87.5% 0.691 MiniLM sentence encoder (dense) 87.5% 0.696 hybrid: BM25 + LSA 90.6% 0.674 hybrid: BM25 + MiniLM 90.6% 0.748
BM25 puts a paragraph from the right section in its top five for 30 of the 32 questions (93.8%); LSA and the neural encoder each manage 28 (87.5%). The pretrained encoder does not beat word matching on its own, and it is barely better than LSA, which was fitted to these very notes. But fused with BM25 it gives the best mean reciprocal rank of all (0.748, against 0.700 for BM25 and 0.674 for BM25 with LSA), presumably because the neural encoder's mistakes overlap less with BM25's than LSA's do (the code does not measure this). Even though the questions were written to avoid the sections' vocabulary, enough content words survive ("decision tree", "random labels", "propensity score") for BM25 to do well. This matches the large benchmarks: on the BEIR collection (Thakur et al., 2021), BM25 beat many neural retrievers outside the domain they were trained on, and hybrids of lexical and dense retrieval are now standard in production RAG systems. Use the widget to see where each method fails.
Once passages are retrieved, how should the model combine them? Lewis et al. (2020) treated the retrieved passage as a latent variable.
Let a retriever give \(p_\eta(z\mid x)\) over passages \(z\) (a softmax of retrieval scores over the top \(K\)) and a generator give \(p_\theta(y\mid x,z)\). The RAG model is the mixture
$$p(y\mid x)=\sum_{z}p_\eta(z\mid x)\,p_\theta(y\mid x,z),$$and the gradient of its log-likelihood is the posterior-weighted average of the component gradients:
$$\nabla\log p(y\mid x)=\sum_z p(z\mid x,y)\,\nabla\big[\log p_\eta(z\mid x)+\log p_\theta(y\mid x,z)\big],\qquad p(z\mid x,y)=\frac{p_\eta(z\mid x)\,p_\theta(y\mid x,z)}{p(y\mid x)}.$$So the retriever is trained, without any labels saying which passage is relevant, to give more weight to the passages that helped the generator produce the right answer.
and \(\nabla f=f\,\nabla\log f\) for any positive \(f\), so this equals
$$\sum_z\frac{p_\eta(z\mid x)p_\theta(y\mid x,z)}{p(y\mid x)}\nabla\log\big[p_\eta(z\mid x)p_\theta(y\mid x,z)\big],$$which is the claim by Bayes' rule.
It is the same identity that underlies the EM algorithm for mixture models (Lecture 17a): the posterior over the latent component weights each component's contribution. \(\square\)
Within five years of 2017 the transformer became the default architecture well beyond text. Vision transformers cut images into patches and treat them as tokens (Dosovitskiy et al., 2021); Whisper transcribes speech with an encoder–decoder transformer; AlphaFold 2 predicts protein structures with attention over residue pairs (Jumper et al., 2021), work recognised with the 2024 Nobel Prize in Chemistry; code assistants, chatbots and search engines are built on decoder-only language models with retrieval; and transformers trained on weather reanalysis data produce medium-range forecasts competitive with numerical weather prediction at a fraction of the cost. What these share is the recipe of this lecture: tokenise the data, let every token attend to every other, pre-train at scale, and adapt.
A quantum computer protects its information with an error-correcting code: many physical qubits encode one logical qubit, and repeated "syndrome" measurements reveal where errors have probably occurred. A decoder must infer from the stream of syndromes which correction to apply, fast and accurately, and real hardware has correlated, leaky, drifting noise that the standard decoders' simple noise models miss. AlphaQubit (Bausch et al., 2024) is a recurrent transformer decoder: at each round it updates a per-stabiliser state with the new syndromes, using attention between stabilisers and convolutions over their layout. Pre-trained on simulated data and fine-tuned on a limited budget of experimental data from Google's Sycamore processor, it made fewer errors on surface codes of distance 3 and 5 than the best tensor-network and correlated-matching decoders. Speed remains the open problem: a decoder for superconducting qubits must keep up with a new round of syndromes every microsecond.
Next: Lecture 13 turns these tools to text as data: sentiment, bias, and what the embeddings of a language model reveal about the text it was trained on.
By permutation equivariance (Proposition 12.3), permuting the inputs permutes the outputs, so the set of output vectors is unchanged; any pooled summary (a mean, a max) is identical. With a causal mask, the first position attends only to itself, the second to two tokens, and so on: the output at position \(i\) depends on which tokens precede it, so order matters. Decoder-only models without explicit positional encodings do in fact learn positional information this way (Haviv et al., 2022).
Token embeddings \(65\cdot128=8{,}320\); positions \(128\cdot128=16{,}384\); final layer norm 256. Per block: \(Q,K,V\) \(128\cdot384=49{,}152\); output projection \(16{,}384\); MLP \(2\cdot128\cdot512=131{,}072\); two layer norms 512; total 197,120. Four blocks give 788,480 and the model 813,440, as printed. The blocks' weight matrices account for \(12Ld^2=786{,}432\) of these: at this size the embeddings are only 3% of the model; in a model with a 50,000-token vocabulary and small width they can be the majority.
\(a_i=e^{s_i}/\sum_ke^{s_k}\), so \(\partial a_i/\partial s_j=a_i\delta_{ij}-a_ia_j\). If \(a_1\approx1\) and the rest \(\approx0\), every entry \(a_i(\delta_{ij}-a_j)\) is near 0: the Jacobian vanishes, and the query and key weights stop learning. Without scaling, scores have variance \(d\) and the softmax saturates (the code box: median largest weight 1.000 at \(d=512\)); dividing by \(\sqrt d\) keeps the variance at 1.
Words: l o w, ␣ l o w e r, ␣ l o w e s t. Pair counts: (l,o) 3, (o,w) 3, (␣,l) 2, (w,e) 2, others 1. Merge 1: l+o → lo (first of the tied pairs). Now (lo,w) 3: merge 2: lo+w → low. Then (␣,low) 2 and (low,e) 2 tie; (␣,low) occurs first: merge 3: ␣+low → ␣low. "slower" (no leading space) becomes s low e r: four tokens, the familiar piece "low" reused.
Each extra token multiplies the probability by a factor below 1, so \(\log p\) is a sum of negative terms that grows more negative with length: a sequence that ends early wins even if every one of its tokens is less likely. Normalising by length compares the average log-probability per token instead (Wu et al., 2016, used \(\log p/\mathrm{lp}\) with \(\mathrm{lp}=((5+|y|)/6)^{\alpha}\)).
\(p(y\mid x)=0.07+0.24=0.31\); \(p(z_1\mid x,y)=0.07/0.31=0.226\), \(p(z_2\mid x,y)=0.774\). The retriever's gradient pushes \(\log p_\eta(z\mid x)\) towards the posterior, increasing the weight of \(z_2\), the passage that actually helped.
Each project uses this lecture's methods and public data, and has a clear result.
Data. Tiny Shakespeare: A. Karpathy, github.com/karpathy/char-rnn (2015). GPT-2 tokeniser files (encoder.json, vocab.bpe) and encoder.py: OpenAI, github.com/openai/gpt-2 (Modified MIT licence). Motorcycle crash-helmet data (mcycle): B. W. Silverman, JRSS B 47, 1–52 (1985), as distributed with R's MASS package. Retrieval corpus: Lectures 1–10b of this course. Pretrained models from the Hugging Face Hub: GPT-2 small (openai-community/gpt2, MIT licence) and all-MiniLM-L6-v2 (sentence-transformers/all-MiniLM-L6-v2, Apache 2.0).
numbers in the text not printed by a code box are computed in verify_L12.py, widget data in figs_L12.py; code-box outputs are pasted from actual runs (numpy and JAX on two CPU cores)