Machine Learning from First Principles

Chapter 19 · Part IV: Deep Learning

Embeddings, Attention, and Transformers

After this chapter you will be able to

  • Represent discrete tokens as learned embedding vectors and explain why similar words end up close together.
  • Explain the limitations of recurrent networks that motivated attention.
  • Derive scaled dot-product attention as a soft dictionary lookup, including the $1/\sqrt{d_k}$ factor.
  • Implement causal masking and multi-head attention in matrix form.
  • Add position information with sinusoidal encodings and rotary embeddings (RoPE), and show that RoPE depends only on relative position.
  • Assemble a pre-norm Transformer block, count its parameters, and explain the KV cache used for fast generation.

The Transformer (Vaswani et al. 2017) is the architecture behind essentially every large language model and a growing share of vision, audio, and multimodal systems. It is built from pieces you already know: linear layers, a softmax, residual connections, and layer normalization. The one new idea is attention, a way for each element of a sequence to gather information from every other element, with weights computed from the data.

19.1Representing Words as Vectors

Text is a sequence of discrete symbols. We first split it into tokens (words or pieces of words; Section 24.2) drawn from a vocabulary of size $V$, typically tens of thousands to a few hundred thousand. A token with index $t$ could be represented as a one-hot vector $\mathbf e_t\in\R^V$, but one-hot vectors are huge and every pair of them is equally far apart: “cat” is as different from “kitten” as from “carburetor.”

An embedding maps each token to a dense vector in $\R^d$ ($d$ in the hundreds to thousands) by looking up a row of a learned matrix $\mathbf E\in\R^{V\times d}$:

$$\mathrm{embed}(t) = \mathbf E\T\mathbf e_t = \text{row $t$ of }\mathbf E .$$

Multiplying a one-hot vector by a matrix is just selecting a row, so the embedding layer is a linear layer implemented as a table lookup. Its rows are trained by backpropagation like any other weights.

Why similar words get similar vectors. The distributional hypothesis says that words appearing in similar contexts have similar meanings. If a model is trained to predict words from their neighbors, words that are interchangeable in context (“cat,” “dog,” “kitten”) receive similar gradients and drift toward similar vectors. Word2vec (Mikolov et al. 2013) showed that such embeddings capture surprisingly rich structure: directions in the space correspond to relationships, giving the famous approximate analogy $\mathrm{vec}(\text{king})-\mathrm{vec}(\text{man})+\mathrm{vec}(\text{woman})\approx\mathrm{vec}(\text{queen})$. Similarity between embeddings is measured with dot products or cosine similarity (Chapter 2).

Static versus contextual. A single vector per word cannot capture that “bank” means different things in “river bank” and “bank loan.” Transformers start from static token embeddings and then repeatedly update each token’s vector using its context, so that by the later layers every token has a contextual representation.

19.2Sequence Models Before Transformers

A recurrent neural network (RNN, Chapter 18) reads a sequence one token at a time and keeps a hidden state that summarizes everything so far:

$$\vh_t = \tanh(\mW\vh_{t-1}+\mathbf U\vx_t+\vb). \tag{19.1}$$

Training uses backpropagation through the unrolled sequence. RNNs, and their gated variants such as the LSTM, dominated language modeling and translation until about 2017, but they have two structural problems:

  1. Long-range dependencies. Information from token 1 must pass through every intermediate hidden state to reach token 500. Gradients flowing back through hundreds of steps are multiplied by hundreds of Jacobians and tend to vanish or explode, the same issue as in deep plain networks (Section 18.4). Gating mitigates it, but the hidden state remains a fixed-size bottleneck.
  2. Sequential computation. $\vh_t$ cannot be computed before $\vh_{t-1}$, so training cannot be parallelized across positions. Modern hardware wants large parallel matrix multiplications.

Attention was first added to RNNs so that a translation model could look back at all source words when producing each output word (Bahdanau et al. 2015). The Transformer’s insight was that attention alone, without recurrence, is enough.

19.3Attention as Soft Dictionary Lookup

Think of a Python dictionary: a query is compared with every key, and the value of the matching key is returned. Attention is a differentiable version of this. Given a query vector $\vq$ and $n$ key–value pairs $(\vk_j,\vv_j)$:

  1. Score each key by its similarity to the query: $s_j=\vq\T\vk_j$.
  2. Turn the scores into weights that are positive and sum to one: $\alpha_j=\softmax(\vs)_j$.
  3. Return the weighted average of the values: $\sum_j\alpha_j\vv_j$.

If one key matches much better than the rest, softmax puts almost all the weight on it and attention behaves like an exact lookup. If several keys match, it blends their values. Because every step is differentiable, the model can learn what the queries, keys, and values should be.

19.4Scaled Dot-Product Self-Attention

In self-attention, the queries, keys, and values all come from the same sequence. Stack the $n$ token vectors of a sequence as rows of $\mX\in\R^{n\times d}$, and compute three linear projections with learned matrices $\mW_Q,\mW_K\in\R^{d\times d_k}$ and $\mW_V\in\R^{d\times d_v}$:

$$\mQ=\mX\mW_Q,\qquad \mK=\mX\mW_K,\qquad \mV=\mX\mW_V .$$

Row $i$ of $\mQ$ is what token $i$ is looking for; row $j$ of $\mK$ is what token $j$ offers; row $j$ of $\mV$ is what token $j$ communicates if selected. All $n^2$ scores are the entries of $\mQ\mK\T$, and attention for every position at once is

$$\mathrm{Attention}(\mQ,\mK,\mV)=\softmax\!\Big(\frac{\mQ\mK\T}{\sqrt{d_k}}\Big)\mV \tag{19.2}$$

where the softmax is applied to each row. The $n\times n$ matrix $\mathbf A=\softmax(\mQ\mK\T/\sqrt{d_k})$ holds the attention weights: $A_{ij}$ is how much token $i$ attends to token $j$.

Why divide by $\sqrt{d_k}$? Suppose the entries of a query and a key are independent with mean 0 and variance 1. Their dot product $\vq\T\vk=\sum_{l=1}^{d_k}q_lk_l$ is a sum of $d_k$ independent terms, each with mean 0 and variance 1, so it has variance $d_k$. With $d_k=128$ the scores would have standard deviation about 11, the softmax would saturate (one weight near 1, the rest near 0), and its gradient would nearly vanish (recall the softmax Jacobian $\diag(\vp)-\vp\vp\T$, which is close to zero when $\vp$ is one-hot). Dividing by $\sqrt{d_k}$ restores unit variance.

Cost. Computing $\mQ\mK\T$ takes $O(n^2d_k)$ operations and the attention matrix takes $O(n^2)$ memory. This quadratic cost in sequence length is the main obstacle to very long contexts and motivates much of the efficiency research in Section 19.8.

19.5Causal Masking and Multi-Head Attention

Causal masking. A language model predicts each token from the ones before it, so position $i$ must not attend to positions $j>i$, which would let it see the answer. Before the softmax, add a mask $\mathbf M$ with $M_{ij}=0$ for $j\le i$ and $M_{ij}=-\infty$ for $j>i$:

$$\softmax\!\Big(\frac{\mQ\mK\T}{\sqrt{d_k}}+\mathbf M\Big)\mV . \tag{19.3}$$

$e^{-\infty}=0$, so masked positions get zero weight. Because of the mask, one forward pass over a training sequence of length $n$ produces $n$ next-token predictions at once, each using only its own past: training is fully parallel even though generation is sequential.

Multi-head attention. One attention pattern per layer is limiting: a token may need to look at its syntactic head, at the previous mention of an entity, and at the immediately preceding token, all at once. Multi-head attention runs $H$ attention operations in parallel, each with its own projections of size $d_k=d/H$, concatenates the results, and mixes them with an output matrix $\mW_O\in\R^{d\times d}$:

$$\mathrm{MHA}(\mX) = \big[\mathrm{head}_1;\dots;\mathrm{head}_H\big]\mW_O,\qquad \mathrm{head}_h=\mathrm{Attention}(\mX\mW_Q^h,\mX\mW_K^h,\mX\mW_V^h). \tag{19.4}$$

The total cost is about the same as one head of full width. Trained heads often specialize in recognizable patterns, though many are hard to interpret.

19.6Positional Information

Self-attention has no built-in notion of order. Permuting the rows of $\mX$ permutes the rows of the output in the same way (attention is permutation equivariant), so “dog bites man” and “man bites dog” would look alike. Position information must be injected.

Sinusoidal encodings. The original Transformer adds to each token embedding a fixed vector $\mathbf p_m$ for position $m$ whose coordinates are sines and cosines of geometrically spaced frequencies: $p_{m,2i}=\sin(m\,\omega_i)$ and $p_{m,2i+1}=\cos(m\,\omega_i)$ with $\omega_i=10000^{-2i/d}$. Learned position embeddings (one trainable vector per position) work similarly but cannot extend beyond the training length.

Rotary position embeddings (RoPE). Most modern language models use RoPE (Su et al. 2021), which encodes position by rotating queries and keys instead of adding to the input. Split the $d_k$ coordinates of a query into pairs and treat each pair as a point in the plane. At position $m$, rotate pair $i$ by angle $m\,\omega_i$:

$$\mathbf R(\phi)=\begin{pmatrix}\cos\phi&-\sin\phi\\ \sin\phi&\cos\phi\end{pmatrix},\qquad \tilde\vq_m^{(i)} = \mathbf R(m\omega_i)\,\vq_m^{(i)},\qquad \tilde\vk_n^{(i)} = \mathbf R(n\omega_i)\,\vk_n^{(i)} .$$

The key property is that the score depends only on the relative position $m-n$. Rotation matrices are orthogonal and compose by adding angles, so $\mathbf R(a)\T\mathbf R(b)=\mathbf R(b-a)$, and for each pair

$$\big(\tilde\vq_m^{(i)}\big)\T\tilde\vk_n^{(i)} = \vq_m^{(i)\top}\mathbf R(m\omega_i)\T\mathbf R(n\omega_i)\,\vk_n^{(i)} = \vq_m^{(i)\top}\mathbf R\big((n-m)\omega_i\big)\,\vk_n^{(i)} . \tag{19.5}$$

Shifting both positions by the same amount leaves every score unchanged. Low-frequency pairs (small $\omega_i$) rotate slowly and can represent long distances; high-frequency pairs distinguish nearby positions. Extending RoPE models to longer contexts than they were trained on is done by rescaling these frequencies.

19.7The Transformer Block

A Transformer is a stack of identical blocks. Each block has two sublayers, attention (for communication between positions) and a position-wise feed-forward network (for computation within each position), each wrapped in a residual connection with normalization. The pre-norm arrangement used by most modern models is

$$\begin{aligned}\mX' &= \mX + \mathrm{MHA}\big(\mathrm{Norm}(\mX)\big), \\ \mX'' &= \mX' + \mathrm{FFN}\big(\mathrm{Norm}(\mX')\big),\end{aligned} \tag{19.6}$$

where Norm is LayerNorm or RMSNorm (Chapter 16) and the FFN is a two-layer MLP applied to each position separately, $\mathrm{FFN}(\vx)=\mW_2\,\phi(\mW_1\vx)$, with hidden width about $4d$ and $\phi$ a GELU or a gated variant (SwiGLU). Putting the normalization inside the residual branch (pre-norm) rather than after the addition (post-norm, as in the original paper) keeps an unobstructed identity path through the whole stack and makes deep Transformers much easier to train (Xiong et al. 2020).

Reading the block. The residual stream $\mX$ is a running representation of every token. Attention lets each token read from others and write the result back into its stream; the FFN transforms each token’s stream on its own and is where much of a model’s stored knowledge appears to live. Stacking $L$ blocks lets information hop between positions and be refined many times.

Parameter count. Ignoring biases and norms, attention has four $d\times d$ matrices ($\mW_Q,\mW_K,\mW_V,\mW_O$, summed over heads) and the FFN has two matrices of size $d\times4d$, so one block has about $4d^2+8d^2=12d^2$ parameters. A model with $L$ layers has about $12Ld^2$ parameters plus $Vd$ for the embeddings. For $d=4096$ and $L=32$, that is about $6.4$ billion parameters in the blocks.

Three families. Encoder-only Transformers (such as BERT; (Devlin et al. 2019)) use unmasked attention and are trained to fill in masked tokens; they produce contextual representations for classification and retrieval. Decoder-only Transformers use causal masking and are trained to predict the next token; all GPT-style large language models are of this type. Encoder–decoder Transformers (the original design) encode an input sequence with one stack and generate an output with a second stack that also attends to the encoder’s outputs (cross-attention); they remain common for translation and speech recognition.

Output layer. A decoder-only model ends with a final normalization and a linear map from $\R^d$ to $\R^V$ (often sharing weights with the embedding matrix), followed by a softmax over the vocabulary: exactly the multiclass logistic regression of Section 6.4, applied to the final representation of each position.

19.8Efficient Inference: The KV Cache

To generate text, a decoder-only model predicts one token, appends it, and runs again. Naively, step $t$ recomputes attention over all $t$ previous tokens from scratch. But with causal masking, the keys and values of earlier positions never change when new tokens are appended. The KV cache stores them: each new step computes the query, key, and value only for the newest token, appends its key and value to the cache, and attends over the cached keys and values. This reduces each step from processing $t$ tokens to processing one.

The cache has a cost: for each layer and each previous token it stores a key and a value vector, so its size is $2\times L\times n\times d$ numbers per sequence (for a 32-layer model with $d=4096$, half a megabyte per token in 16-bit precision). Memory, not arithmetic, often limits how many users a model can serve and how long their contexts can be. Several architectural choices reduce it:

  • Grouped-query attention (GQA) shares each key/value head among a group of query heads, shrinking the cache by the group size.
  • Latent attention compresses keys and values into a smaller latent vector that is cached and expanded when needed.
  • Sliding-window attention lets most layers attend only to the most recent $w$ tokens, with a few global layers interleaved; cache size per local layer is then bounded by $w$.

Independently, kernels such as FlashAttention (Dao et al. 2022) compute exact attention without ever writing the full $n\times n$ matrix to slow memory, by processing it in tiles; this makes training on long sequences much faster without changing the math.

19.9Vision Transformers

Nothing in the Transformer is specific to text: it maps a set of vectors with positions to a set of vectors. The Vision Transformer (ViT) (Dosovitskiy et al. 2021) applies it to images with minimal change. Cut an $H\times W\times C$ image into $N=HW/P^2$ non-overlapping patches of $P\times P$ pixels (a $224\times224$ image with $P=16$ gives $14\times14=196$ patches), flatten each into a vector $\vx_p^{(i)}\in\R^{P^2C}$, and map it linearly to the model dimension $d$. Prepend a learned classification token and add learned position embeddings:

$$\mathbf Z_0=\big[\,\vx_{\text{cls}};\ \vx_p^{(1)}\mathbf E;\ \dots;\ \vx_p^{(N)}\mathbf E\,\big]+\mathbf E_{\text{pos}},\qquad \mathbf E\in\R^{P^2C\times d},\ \mathbf E_{\text{pos}}\in\R^{(N+1)\times d}. \tag{19.7}$$

The patch embedding is exactly a convolution with kernel size and stride $P$ (Chapter 17). The sequence then passes through a standard Transformer encoder (Section 19.7) without a causal mask, since every patch may attend to every other, and a linear head on the final classification token (or on the average of all tokens) predicts the class.

Inductive bias and data. Apart from cutting the image into patches, a ViT knows nothing about images: no locality, no translation equivariance; it must learn from data that nearby patches are related. Trained on ImageNet’s 1.3 million images alone, the original ViT was worse than a comparable ResNet; pretrained on 14 to 300 million images, it was better, and it kept improving with scale where CNNs saturated. Strong augmentation, regularization, and distillation later made ViTs competitive on ImageNet alone (Touvron et al. 2021), and hierarchical variants with local windowed attention, such as the Swin Transformer (Liu et al. 2021), produce multi-scale feature maps for detection and segmentation (Chapter 21).

Cost. Attention costs $O(N^2)$ in the number of patches, so the patch size trades resolution for compute: halving $P$ quadruples $N$ and multiplies the attention cost by about 16. ViTs are now the standard backbone for self-supervised vision models (Chapter 26), CLIP-style and multimodal models (Chapter 23), and image generators (Chapter 25), because they process image patches with the same machinery that processes text tokens.

19.10Implementation

Causal multi-head self-attention in NumPy, a direct transcription of Equation (19.2):

import numpy as np

def softmax(Z, axis=-1):
    Z = Z - Z.max(axis=axis, keepdims=True)
    E = np.exp(Z)
    return E / E.sum(axis=axis, keepdims=True)

def causal_mha(X, Wq, Wk, Wv, Wo, n_heads):
    n, d = X.shape
    dk = d // n_heads
    # project, then split the last dimension into heads: (heads, n, dk)
    split = lambda M: M.reshape(n, n_heads, dk).transpose(1, 0, 2)
    Q, K, V = split(X @ Wq), split(X @ Wk), split(X @ Wv)
    scores = Q @ K.transpose(0, 2, 1) / np.sqrt(dk)          # (heads, n, n)
    mask = np.triu(np.ones((n, n), dtype=bool), k=1)         # j > i
    scores = np.where(mask, -np.inf, scores)
    A = softmax(scores, axis=-1)                              # attention weights
    heads = A @ V                                             # (heads, n, dk)
    concat = heads.transpose(1, 0, 2).reshape(n, d)
    return concat @ Wo, A

rng = np.random.default_rng(0)
n, d, H = 6, 16, 4
X = rng.normal(size=(n, d))
W = [rng.normal(0, d**-0.5, (d, d)) for _ in range(4)]
out, A = causal_mha(X, *W, n_heads=H)
print(out.shape, np.allclose(A.sum(-1), 1), np.allclose(np.triu(A[0], 1), 0))

And a complete pre-norm Transformer block in PyTorch; Project 6 stacks such blocks into a small GPT and trains it.

import torch, torch.nn as nn, torch.nn.functional as F

class Block(nn.Module):
    def __init__(self, d, n_heads, dropout=0.0):
        super().__init__()
        self.n_heads = n_heads
        self.norm1, self.norm2 = nn.LayerNorm(d), nn.LayerNorm(d)
        self.qkv, self.proj = nn.Linear(d, 3 * d, bias=False), nn.Linear(d, d, bias=False)
        self.ffn = nn.Sequential(nn.Linear(d, 4 * d), nn.GELU(), nn.Linear(4 * d, d))
        self.drop = nn.Dropout(dropout)

    def forward(self, x):                                  # x: (batch, n, d)
        B, n, d = x.shape
        q, k, v = self.qkv(self.norm1(x)).split(d, dim=-1)
        q, k, v = (t.view(B, n, self.n_heads, d // self.n_heads).transpose(1, 2)
                   for t in (q, k, v))                     # (B, heads, n, dk)
        a = F.scaled_dot_product_attention(q, k, v, is_causal=True)
        x = x + self.drop(self.proj(a.transpose(1, 2).reshape(B, n, d)))
        return x + self.drop(self.ffn(self.norm2(x)))

19.11Where the Field Is Heading

As of late 2026, the decoder-only Transformer with pre-normalization, RoPE, and a gated feed-forward layer remains the backbone of nearly all frontier language models. Most activity is in making it cheaper at long context and large scale: grouped-query or latent attention to shrink the KV cache; hybrids that interleave sliding-window or other sparse attention layers with a few full-attention layers; and mixture-of-experts feed-forward layers that activate only a fraction of the parameters per token (Chapter 24). A separate line of work replaces some or all attention layers with recurrent state-space or linear-attention layers whose cost grows linearly with sequence length (Gu and Dao 2023); hybrids of such layers with attention are an active research area. Outside language, the same blocks process image patches, audio frames, and video, and the diffusion models of Chapter 25 increasingly use Transformer backbones too.

19.12Summary

  • Embeddings map tokens to learned dense vectors; words used in similar contexts end up close together.
  • RNNs process sequences step by step, which limits parallelism and long-range gradient flow.
  • Attention is a differentiable dictionary lookup: $\softmax(\mQ\mK\T/\sqrt{d_k})\mV$. The scale keeps score variance near 1 so the softmax does not saturate.
  • A causal mask enables parallel next-token training; multiple heads attend to different patterns.
  • Attention ignores order without positional information; RoPE rotates queries and keys so scores depend only on relative position.
  • A pre-norm block is $\mX+\mathrm{MHA}(\mathrm{Norm}(\mX))$ then $+\mathrm{FFN}(\mathrm{Norm}(\cdot))$, with about $12d^2$ parameters.
  • The KV cache makes generation incremental; GQA, latent attention, and sliding windows shrink it.
  • Vision Transformers embed $P\times P$ image patches as tokens with learned positions and run a standard encoder; they need more data than CNNs but scale better.

19.13Exercises

  1. MathShow that self-attention without positional information is permutation equivariant: if $\mathbf P$ is a permutation matrix, $\mathrm{Attention}(\mathbf P\mX\mW_Q,\mathbf P\mX\mW_K,\mathbf P\mX\mW_V)=\mathbf P\,\mathrm{Attention}(\mX\mW_Q,\mX\mW_K,\mX\mW_V)$.
  2. MathLet $\vq,\vk\in\R^{d_k}$ have independent entries with mean 0 and variance 1. Show that $\Var(\vq\T\vk)=d_k$.
  3. MathShow that $\mathbf R(a)\T\mathbf R(b)=\mathbf R(b-a)$ for 2D rotation matrices, and complete the RoPE relative-position argument.
  4. MathCount the parameters of a Transformer block exactly, including biases and two LayerNorms, for $d=768$ and FFN width $3072$. Compare with $12d^2$.
  5. MathEstimate the KV-cache size in gigabytes for a model with $L=80$ layers, 8 key/value heads of dimension 128 (grouped-query attention), a context of 128,000 tokens, and 16-bit numbers. How large would it be with 64 key/value heads?
  6. CodingCheck the NumPy attention against torch.nn.functional.scaled_dot_product_attention on random inputs (convert the arrays with torch.from_numpy). They should agree to about $10^{-6}$ in single precision.
  7. CodingImplement a KV cache for the NumPy attention: write a function that, given cached $\mK,\mV$ for $t$ tokens and a new token, returns the new output and the updated cache. Verify that generating token by token gives the same outputs as one full causal pass.
  8. MathFor a $224\times224\times3$ image, compute the number of tokens, the size of each flattened patch, and the number of parameters of the patch embedding $\mathbf E$ for $P=32,16,8$ and $d=768$. By what factor does the attention cost per layer change between $P=16$ and $P=8$?
Machine Learning from First Principles · Edition 2.0 · Companion site to the PDF book.