Scaled dot-product attention: the math and the shapes
The previous session gave the idea of attention: a query looks for matching keys and collects their values. This session writes it as one exact formula, softmax(QKᵀ/√d_k)V, follows the shape of every tensor through it, shows why the division by √d_k is needed, and counts what attention costs in compute and memory as the sequence gets longer.
What you will learn
- How the three projections Q = XW_Q, K = XW_K, V = XW_V are computed, and the shape of every tensor, with and without batch and heads
- The four steps of attention: scores QKᵀ, scaling by √d_k, softmax over the keys, weighted sum of the values, done by hand on a 3-token example
- Why √d_k: the variance of a dot product of random vectors grows like d_k, which saturates the softmax and kills its gradient
- The stable softmax trick and the backward pass of attention, checked against PyTorch autograd
- The cost: O(T²·d) compute and O(T²) memory for the score matrix, with real numbers for GPT-2 and Llama 3.1 8B
- Where the T² wall appears in practice (long documents, high-resolution images, video) and what FlashAttention changes and does not change
Why this matters
In session 16 we described attention in words: every token sends out a query (“what am I looking for?”), every token shows a key (“what do I contain?”), and each token collects the values of the tokens whose keys match its query best. This session turns those words into one line of math and follows every number through it.
That line is the most important formula of this course. It was written down in the transformer paper (Vaswani et al., 2017) and every LLM and VLM since then runs it, in every layer, for every token: [Certain]
It looks short, but it hides four separate steps, three design decisions and one big cost:
- Shapes. Which tensor is \(T \times d_k\), which is \(T \times T\), and along which axis the softmax runs. Getting an axis wrong gives no error message, just a model that does not learn.
- The division by \(\sqrt{d_k}\). Without it, large models train badly. The reason is a simple variance argument, and interviewers ask for it very often.
- Numerical safety. A softmax over raw scores overflows in 16-bit floats. Every real implementation subtracts the row maximum first.
- Cost. The score matrix \(QK^\top\) has \(T \times T\) entries. Double the context, and this part costs four times as much. This one fact explains FlashAttention, the KV cache, sliding windows and most of the work on long context and long video.
We will build formula (17.1) step by step, do it by hand on three tokens, derive the \(\sqrt{d_k}\), write the backward pass, and then count FLOPs and bytes for GPT-2 and Llama 3.1 8B.
The inputs: X and three projections
Attention works on a sequence of \(T\) vectors, one per token. After the embedding layer (session 11) and earlier transformer layers, we stack them as the rows of a matrix \(X\). Row \(t\) is the current vector of token \(t\) (its hidden state). Its length \(d\) is the model width (also written \(d_{\text{model}}\)).
From \(X\), attention makes three new matrices with three learned weight matrices. This is the first step of formula (17.1):
- Read the symbols
- \(X \in \R^{T \times d}\)
- the input: \(T\) tokens, each a row of \(d\) numbers
- \(W_Q, W_K \in \R^{d \times d_k}\)
- learned matrices that turn each token vector into a query and a key of length \(d_k\)
- \(W_V \in \R^{d \times d_v}\)
- learned matrix that turns each token vector into a value of length \(d_v\)
- \(Q, K \in \R^{T \times d_k}\)
- row \(i\) of \(Q\) is the query \(\mathbf{q}_i\) of token \(i\); row \(j\) of \(K\) is the key \(\mathbf{k}_j\) of token \(j\)
- \(V \in \R^{T \times d_v}\)
- row \(j\) is the value \(\mathbf{v}_j\): what token \(j\) gives to anyone who attends to it
- \(d_k, d_v\)
- the head size. Queries and keys must have the same length \(d_k\), because we take their dot product. \(d_v\) can be different, but in practice \(d_v = d_k\)
Each projection is applied to every row separately: \(\mathbf{q}_i = \mathbf{x}_i W_Q\). So the same token vector \(\mathbf{x}_i\) plays three roles through three different “lenses”. Why three different matrices and not one? Because “what I look for” and “what I contain” are different things. A pronoun looks for a noun, but it does not contain a noun. If \(W_Q = W_K\), the score of token \(i\) with itself, \(\mathbf{q}_i \cdot \mathbf{q}_i = \lVert \mathbf{q}_i \rVert^2\), would always be large and positive, and the score matrix would be symmetric: \(i\) would like \(j\) exactly as much as \(j\) likes \(i\). Separate matrices remove both limits.
In a real model, attention is split into \(H\) heads (session 19). Each head has its own small \(W_Q, W_K, W_V\) with \(d_k = d / H\). For Llama 3.1 8B: \(d = 4096\), \(H = 32\), so \(d_k = 128\) [Certain, from its config.json]. For the original transformer base model: \(d = 512\), \(H = 8\), \(d_k = 64\) [Certain]. In this session we study one head; everything is done \(H\) times in parallel.
Figure 1 shows every shape in the computation. Change \(T\), \(d\) and \(d_k\) and watch which matrices grow.
How to read Figure 1
Increase \(d\): only \(X\) and the three weight matrices grow; the score matrix does not change. Increase \(d_k\): \(Q\), \(K\), \(V\) and the output grow in one direction. Increase \(T\): almost everything grows in one direction, but the two grey \(T \times T\) squares grow in both directions. That square is the source of the \(T^2\) cost in the last part of this session. Notice also that the output has \(T\) rows, one per query: attention gives every token a new vector.
Step 1: scores are dot products
Next, each query is compared with each key. The comparison is the dot product (session 2): large when the two vectors point the same way, near zero when they are unrelated, negative when they point in opposite directions. All \(T \times T\) comparisons together are one matrix product:
- Read the symbols
- \(S_{ij}\)
- the score (also called logit): how much query \(i\) matches key \(j\). Row \(i\) belongs to one query; column \(j\) to one key.
- \(K^\top\)
- the transpose of \(K\), shape \(d_k \times T\). Shapes: \((T \times d_k)(d_k \times T) = T \times T\).
Why the dot product and not another similarity? Bahdanau et al. (2014) used additive attention, a small neural network \(\mathbf{w}^\top \tanh(W_1 \mathbf{q} + W_2 \mathbf{k})\) for each pair (session 7). The transformer paper chose the dot product because it is one big matrix multiplication, which GPUs do extremely fast [Certain]. The price is the scale problem we fix in step 2.
Step 2: divide by the square root of \(d_k\)
Before the softmax, every score is divided by \(\sqrt{d_k}\). To see why, ask: how big is a typical score at the start of training?
The variance of a dot product
Assume, as the transformer paper does, that the \(d_k\) components of \(\mathbf{q}\) and \(\mathbf{k}\) are independent random numbers with mean 0 and variance 1. This is roughly true at initialization, when weights are random and inputs are normalized. Each product \(q_l k_l\) has mean \(\E[q_l]\E[k_l] = 0\) and variance \(\E[q_l^2]\E[k_l^2] = 1 \cdot 1 = 1\). A sum of \(d_k\) independent terms has the sum of their variances:
So the typical size (standard deviation) of a raw score is \(\sqrt{d_k}\). With \(d_k = 64\) it is 8; with \(d_k = 128\) it is about 11.3. Dividing by \(\sqrt{d_k}\) brings it back to 1, for every head size. In a simulation with 10,000 random pairs (the code below), the measured standard deviations were 3.95, 7.98, 16.17 and 32.06 for \(d_k = 16, 64, 256, 1024\), against \(\sqrt{d_k} = 4, 8, 16, 32\).
Why large scores are bad: the softmax saturates
The softmax turns scores into weights: \(a_j = e^{z_j} / \sum_l e^{z_l}\). Only the differences between scores matter. If scores differ by 1 or 2, the weights are spread over several keys. If they differ by 20, \(e^{20} \approx 5 \times 10^8\), and the top key gets almost all the weight: the softmax becomes a hard “argmax”. We say it is saturated.
A saturated softmax is not only “too sharp”. It also stops learning, because its gradient goes to zero. The derivative of the softmax is
- Read the symbols
- \(\delta_{ij}\)
- 1 if \(i = j\), else 0
- \(J\)
- the Jacobian: the table of all \(\partial a_i / \partial z_j\). It tells the backward pass how a change in the scores changes the weights.
If \(\mathbf{a}\) is one-hot (one weight 1, the rest 0), every entry is 0: for \(i = j\) at the winner, \(1 \cdot (1 - 1) = 0\); everywhere else one of the factors is 0. No gradient flows back to \(Q\) and \(K\), so the model cannot learn which tokens to look at. For 4 keys, the Frobenius norm (the size) of \(J\) is 0.433 for the uniform weights \((0.25, 0.25, 0.25, 0.25)\) and only 0.041 for \((0.97, 0.01, 0.01, 0.01)\): ten times smaller.
Figure 2 runs this experiment in front of you. Eight random keys compete for one random query. Press Play: for each head size \(d_k = 2, 4, \dots, 1024\) the figure computes the eight dot products, scales them (or not), takes the softmax and measures its gradient, one line of the small program at a time. Untick the box to see what happens without the scale.
- draw \(\mathbf{q}, \mathbf{k}_1, \dots, \mathbf{k}_8\) with \(d_k\) entries from \(\mathcal{N}(0, 1)\)
- \(s_j \leftarrow \mathbf{q} \cdot \mathbf{k}_j\) // formula (17.3)
- \(z_j \leftarrow s_j / \sqrt{d_k}\) // formula (17.4), only if ticked
- \(\mathbf{a} \leftarrow \softmax(\mathbf{z})\) // formula (17.6)
- \(\lVert J \rVert \leftarrow \lVert \operatorname{diag}(\mathbf{a}) - \mathbf{a}\mathbf{a}^\top \rVert_F\) // formula (17.5)
- repeat for 400 queries; next \(d_k\)
How to read Figure 2
Press Play, or drag the slider to jump to one \(d_k\). With the scale on, the picture hardly changes as \(d_k\) grows: the dots stay within a few units of 0, score spread stays near 1, the largest weight stays near 0.36, and the gradient size stays near 0.37. With the scale off, watch step 2: the dots spread out like \(\sqrt{d_k}\) and soon leave the axis. Then the largest weight climbs toward 1 (one key takes everything), the entropy falls toward 0 (its maximum for 8 keys is \(\ln 8 = 2.079\)), and the gradient shrinks several times. That is the regime where attention stops learning. Real queries and keys are not random after training; the point is the starting state, from which learning must begin.
Simulate 4,000 random queries, each with 8 random keys (the same experiment as Figure 2, with PyTorch’s random numbers). Without the scale, the average largest weight is 0.52 for \(d_k = 4\), 0.87 for \(d_k = 64\), 0.92 for \(d_k = 128\) and 0.95 for \(d_k = 512\). The average size of the softmax Jacobian falls from 0.34 to 0.15, 0.11 and 0.06. With the scale, the average largest weight is 0.34 to 0.36 and the Jacobian size is 0.36 to 0.37 for every \(d_k\). At \(d_k = 128\) (Llama 3.1 8B), leaving out the scale makes the starting gradient through the softmax more than three times smaller.
Why the square root, and not \(d_k\)?
We want the scores to have variance 1, not some other size. Variance scales with the square of a factor: \(\operatorname{Var}(c\,s) = c^2 \operatorname{Var}(s)\). To turn variance \(d_k\) into 1, we need \(c^2 = 1/d_k\), so \(c = 1/\sqrt{d_k}\). Dividing by \(d_k\) would give variance \(1/d_k\): for \(d_k = 128\), scores with a spread of about 0.09, and an almost uniform softmax that cannot pick anything at the start. Both directions are bad; \(\sqrt{d_k}\) is the one that keeps the scale fixed.
Two refinements you may meet. You can read \(\sqrt{d_k}\) as a temperature: \(\softmax(\mathbf{z}/\tau)\) with \(\tau = \sqrt{d_k}\). And the \(1/\sqrt{d_k}\) argument holds at initialization, when \(\mathbf{q}\) and \(\mathbf{k}\) are uncorrelated. μP (Yang et al., 2022) argues that after training \(\mathbf{q}\) and \(\mathbf{k}\) become correlated, so the score grows like \(d_k\), and uses \(1/d_k\) instead to transfer hyper-parameters across widths [Likely]. Some large models also normalize \(\mathbf{q}\) and \(\mathbf{k}\) (“QK-norm”) because their scores kept growing during training and the softmax saturated anyway; ViT-22B is a well-known example [Likely].
Step 3: softmax over the keys
Now each row of scaled scores becomes a probability distribution:
- Read the symbols
- \(A \in \R^{T \times T}\)
- the attention matrix (attention weights, or attention probabilities)
- \(A_{ij}\)
- how much query \(i\) attends to key \(j\). Every entry is between 0 and 1.
- \(\sum_l\)
- the sum runs over the keys \(l\), with the query \(i\) fixed. So each row of \(A\) sums to 1. Columns do not.
The axis matters. In code, scores have shape (..., T_q, T_k) and the softmax is over the last axis, dim=-1. A softmax over dim=-2 runs without error but means “each key spreads itself over the queries”, which is a different and wrong model.
The stable softmax
Raw \(e^{z}\) overflows quickly: in FP16 the largest number is 65,504, so \(e^{z}\) is infinite once \(z \gt 11.09\); in FP32 once \(z \gt 88.7\). Then \(\infty / \infty\) gives NaN. The fix uses the fact that adding the same constant to every score of a row does not change the softmax:
After subtracting the row maximum \(m\), the largest exponent is \(e^0 = 1\) and nothing overflows. Every serious implementation does this. FlashAttention goes one step further and computes the maximum and the sum block by block (the “online softmax”), so it never needs the whole row at once (session 124).
Step 4: a weighted sum of the values
Finally, each query collects the values, weighted by its row of \(A\):
Because the weights in a row are non-negative and sum to 1, \(\mathbf{o}_i\) is an average of the value vectors (a convex combination). It always lies “between” the values. If one weight is 1, the output is a copy of one value; if all weights are \(1/T\), it is the plain mean. Shapes: \((T \times T)(T \times d_v) = T \times d_v\). In a real layer the outputs of all heads are joined and multiplied by an output matrix \(W_O \in \R^{d \times d}\) to get back to width \(d\) (session 19).
Putting steps 1 to 4 together gives exactly formula (17.1). Now do it by hand.
Take \(T = 3\), \(d = 4\), \(d_k = d_v = 2\), and
Projections. Each row of \(X\) picks and adds rows of \(W\). Token 1 is \((1,0,1,0)\), so \(\mathbf{q}_1 = (1,0) + (1,0) = (2, 0)\). In full: \(Q = \begin{pmatrix} 2&0 \\ 0&2 \\ 1&1 \end{pmatrix}\), \(K = \begin{pmatrix} 1&1 \\ 1&0 \\ 2&1 \end{pmatrix}\), \(V = \begin{pmatrix} 3&0 \\ 0&2 \\ 2&1 \end{pmatrix}\).
Scores. \(S_{13} = \mathbf{q}_1 \cdot \mathbf{k}_3 = 2 \cdot 2 + 0 \cdot 1 = 4\). All of them: rows \((2, 2, 4)\), \((2, 0, 2)\), \((2, 1, 3)\).
Scale. Divide by \(\sqrt{2} = 1.414\): row 1 becomes \((1.414, 1.414, 2.828)\).
Softmax, row 1. Subtract the maximum: \((-1.414, -1.414, 0)\). Exponentials: \((0.243, 0.243, 1)\), sum 1.486. Weights: \((0.164, 0.164, 0.673)\). Rows 2 and 3 give \((0.446, 0.108, 0.446)\) and \((0.284, 0.140, 0.576)\).
Output, row 1. \(\mathbf{o}_1 = 0.164\,(3, 0) + 0.164\,(0, 2) + 0.673\,(2, 1) = (1.836, 1.000)\). Rows 2 and 3: \((2.229, 0.663)\) and \((2.004, 0.856)\).
Without the scale, row 1 would be \(\softmax(2, 2, 4) = (0.107, 0.107, 0.787)\): already sharper, with only \(d_k = 2\).
Figure 3 runs the same example in the browser, one number at a time, in the order of Algorithm 1 below. Each matrix fills in as its entries are computed, the current line of the program is highlighted, and the panel next to it writes the formula with the live numbers. Switch the scale to “none” or “÷ d_k” to rerun the whole computation without \(\sqrt{d_k}\); click any filled cell to jump to the step that made it.
- \(Q \leftarrow X W_Q\); \(K \leftarrow X W_K\); \(V \leftarrow X W_V\) // (17.2), row by row
- for each \(i, j\): \(S_{ij} \leftarrow \mathbf{q}_i \cdot \mathbf{k}_j\) // (17.3)
- \(\tilde S \leftarrow c \cdot S\), \(c = 1/\sqrt{d_k}\) // (17.4)
- for each row \(i\): \(m_i \leftarrow \max_j \tilde S_{ij}\) // (17.7)
- \(P_{ij} \leftarrow \exp(\tilde S_{ij} - m_i)\)
- \(\ell_i \leftarrow \sum_j P_{ij}\); \(A_{ij} \leftarrow P_{ij} / \ell_i\) // (17.6)
- for each row \(i\): \(\mathbf{o}_i \leftarrow \sum_j A_{ij} \mathbf{v}_j\) // (17.8)
How to read Figure 3
Blue matrices are on the query side, orange on the key side, green on the value side. Outlined cells are the inputs of the current step; the cell that appears is its output. In the softmax steps the weight matrix first shows the unnormalized exponentials \(P_{ij}\) (dashed), then the weights after division by the row sum \(\ell_i\); the purple table keeps \(m_i\) and \(\ell_i\) for each row. In the output steps the value rows fade in proportion to their weight. Query 2 is a good test: keys 1 and 3 both score 2, so they get equal weight. Then switch the scale to “none”: row 1 becomes \((0.107, 0.107, 0.787)\) instead of \((0.164, 0.164, 0.673)\), already sharper with only \(d_k = 2\); “÷ d_k” goes the other way, \((0.212, 0.212, 0.576)\). The last step lists the largest weight and the softmax gradient size \(\lVert J \rVert\) of every row for the chosen scale.
Shapes with batch, heads and two sequences
Real code adds two leading axes: a batch of \(B\) sequences and \(H\) heads. Nothing in the math changes; the matrix products just run over the last two axes, for every \((b, h)\) pair at once.
| Tensor | Shape, one head | Shape in code | Llama 3.1 8B, one layer, \(T = 8192\) |
|---|---|---|---|
| Input \(X\) | \(T \times d\) | (B, T, d) | (B, 8192, 4096) |
| \(Q\) | \(T \times d_k\) | (B, H, T, d_k) | (B, 32, 8192, 128) |
| \(K\), \(V\) | \(T \times d_k\) | (B, H_kv, T, d_k) | (B, 8, 8192, 128), shared by groups of 4 query heads (GQA) |
| Scores \(S\), weights \(A\) | \(T \times T\) | (B, H, T, T) | (B, 32, 8192, 8192) |
| Output \(O\) | \(T \times d_v\) | (B, H, T, d_v), then (B, T, d) | (B, 8192, 4096) after joining heads |
Llama 3.1 8B uses grouped-query attention: 32 query heads but only 8 key and value heads [Certain, config.json]. Each key-value head serves 4 query heads; the math per query head is still formula (17.1) (session 26).
The queries and the keys do not have to come from the same sequence. If \(Q\) comes from \(T_q\) tokens and \(K, V\) from \(T_k\) other tokens (for example text queries attending to image patches), the shapes become
The output always has one row per query. When \(Q\), \(K\), \(V\) all come from the same \(X\), it is self-attention; otherwise it is cross-attention (session 20). During generation with a KV cache, \(T_q = 1\) (the new token) and \(T_k\) is the whole past, so the score matrix is a single row (session 80).
The algorithm, and a memory-saving version
- input: \(X \in \R^{T \times d}\), weights \(W_Q, W_K \in \R^{d \times d_k}\), \(W_V \in \R^{d \times d_v}\)
- \(Q \leftarrow X W_Q\); \(K \leftarrow X W_K\); \(V \leftarrow X W_V\) // formula (17.2), each \(T \times d_k\)
- \(S \leftarrow Q K^\top / \sqrt{d_k}\) // formulas (17.3), (17.4): \(T \times T\)
- for each row \(i\): \(m_i \leftarrow \max_j S_{ij}\); \(P_{ij} \leftarrow \exp(S_{ij} - m_i)\) // stable, formula (17.7)
- \(A_{ij} \leftarrow P_{ij} / \sum_l P_{il}\) // formula (17.6): each row sums to 1
- \(O \leftarrow A V\) // formula (17.8): \(T \times d_v\)
- return \(O\) (and keep \(A\) if a backward pass will follow)
Algorithm 1 builds the full \(T \times T\) matrix. But row \(i\) of the output only needs row \(i\) of \(A\). So we can process the queries in blocks of \(b\) rows and throw each block of scores away after use. The result is exactly the same, and peak memory for scores drops from \(T^2\) to \(b \cdot T\):
- input: \(Q, K \in \R^{T \times d_k}\), \(V \in \R^{T \times d_v}\), block size \(b\)
- for \(r = 0, b, 2b, \dots\) while \(r \lt T\):
- \(Q_r \leftarrow\) rows \(r\) to \(r + b - 1\) of \(Q\) // \(b \times d_k\)
- \(S_r \leftarrow Q_r K^\top / \sqrt{d_k}\) // only \(b \times T\) scores in memory
- \(A_r \leftarrow \softmax(S_r)\) row by row, with the max trick
- rows \(r\) to \(r + b - 1\) of \(O\) \(\leftarrow A_r V\); free \(S_r\) and \(A_r\)
- return \(O\)
The compute is unchanged: still \(T^2\) dot products. FlashAttention also splits the keys into blocks, using the online softmax so that one row never has to be complete, and it recomputes the blocks in the backward pass instead of storing \(A\). Memory then grows only like \(T\), and the result is still exact [Certain] (session 124).
The backward pass
Training needs gradients for \(Q\), \(K\) and \(V\). Let \(dO = \partial \mathcal{L}/\partial O\) be the gradient that arrives from the layer above (same shape as \(O\)), and write \(\tilde S = S / \sqrt{d_k}\) for the scaled scores. Apply the linear-layer rule (4.4) from session 4 to \(O = AV\), then the softmax Jacobian (17.5) row by row:
Three observations. First, \(dV\), \(dA\), \(dQ\) and \(dK\) are four more matrix products of the same size as the forward ones, so the backward pass costs about twice the forward pass, as for any layer. Second, the backward pass needs \(A\): either we store the \(T \times T\) matrix from the forward pass, or we recompute it (FlashAttention’s choice). Third, the factor \(A_{ij}\) in \(d\tilde S\) is where saturation hurts: if a row of \(A\) is one-hot, \(d\tilde S\) for that row is zero, and \(Q\) and \(K\) get no signal. The code below checks (17.10) against autograd.
In PyTorch
The code reproduces the worked example, writes batched multi-head attention from scratch and compares it with PyTorch’s fused F.scaled_dot_product_attention, measures the \(\sqrt{d_k}\) effect, and checks the backward formulas. It is deterministic (fixed seed) and runs on a CPU in about a second.
import math, torch import torch.nn.functional as F torch.manual_seed(0) # 1) the worked example of this session: T = 3 tokens, d = 4, d_k = d_v = 2 X = torch.tensor([[1., 0, 1, 0], [0, 1, 0, 1], [1, 1, 0, 0]]) WQ = torch.tensor([[1., 0], [0, 1], [1, 0], [0, 1]]) WK = torch.tensor([[1., 0], [1, 1], [0, 1], [0, -1]]) WV = torch.tensor([[2., 0], [0, 1], [1, 0], [0, 1]]) Q, K, V = X @ WQ, X @ WK, X @ WV # each (T, d_k) = (3, 2), formula (17.2) S = Q @ K.T / math.sqrt(Q.shape[-1]) # (T, T) scaled scores, (17.3) and (17.4) A = torch.softmax(S, dim=-1) # softmax over keys: each row sums to 1, (17.6) O = A @ V # (T, d_v), (17.8) print(A.round(decimals=4)); print(O.round(decimals=4)) # A rows: [0.1636 0.1636 0.6728] [0.4458 0.1084 0.4458] [0.2840 0.1400 0.5760] # O rows: [1.8364 1.0000] [2.2290 0.6626] [2.0039 0.8560] # 2) attention from scratch for any batch and heads: shapes (B, H, T, d_k) def sdpa(q, k, v): d_k = q.shape[-1] s = q @ k.transpose(-2, -1) / math.sqrt(d_k) # (B, H, T_q, T_k) s = s - s.amax(dim=-1, keepdim=True) # stable softmax, (17.7) a = s.exp(); a = a / a.sum(dim=-1, keepdim=True) return a @ v # (B, H, T_q, d_v) B, H, T, d_k = 2, 4, 16, 32 q, k, v = (torch.randn(B, H, T, d_k) for _ in range(3)) mine = sdpa(q, k, v) ref = F.scaled_dot_product_attention(q, k, v) # PyTorch's fused version print(mine.shape, (mine - ref).abs().max().item()) # (2, 4, 16, 32), about 5e-7 # 3) why sqrt(d_k): the spread of q.k grows like sqrt(d_k), formula (17.4) for d in [16, 64, 256, 1024]: qq, kk = torch.randn(10000, d), torch.randn(10000, d) dots = (qq * kk).sum(-1) print(d, round(dots.std().item(), 2), round(math.sqrt(d), 2)) # 3.95 7.98 16.17 32.06 # 4) without the scale, softmax saturates and its gradient vanishes s = torch.randn(8, 512) # 8 keys, d_k = 512 qk = (torch.randn(512) * s).sum(-1) # 8 raw scores, spread about 22 for name, z in [("raw", qk), ("scaled", qk / math.sqrt(512))]: z = z.clone().requires_grad_(True) a = torch.softmax(z, -1); a[0].backward() print(name, round(a.max().item(), 3), round(z.grad.norm().item(), 4)) # raw: largest weight 1.0, gradient 0.0 | scaled: largest weight 0.37, gradient 0.0257 # 5) the backward pass by hand, formula (17.10), matches autograd q = torch.randn(5, 8, requires_grad=True); k = torch.randn(7, 8, requires_grad=True) v = torch.randn(7, 3, requires_grad=True); dO = torch.randn(5, 3) A = torch.softmax(q @ k.T / math.sqrt(8), -1); (A @ v).backward(dO) with torch.no_grad(): dV = A.T @ dO dA = dO @ v.T dS = A * (dA - (dA * A).sum(-1, keepdim=True)) dQ = dS @ k / math.sqrt(8); dK = dS.T @ q / math.sqrt(8) print(max((x - y).abs().max().item() for x, y in [(dQ, q.grad), (dK, k.grad), (dV, v.grad)])) # about 3e-8
On a GPU, F.scaled_dot_product_attention picks a fused kernel (such as FlashAttention) when the inputs allow it, so it never builds the \(T \times T\) matrix. Use it in real code; write your own only to learn or to test.
The cost: T² compute and T² memory
Count the work for one head. \(QK^\top\) is \(T \times T\) dot products of length \(d_k\): \(T^2 d_k\) multiply-adds, which is \(2 T^2 d_k\) FLOPs (one multiply and one add each). \(AV\) costs \(2 T^2 d_v\). The softmax adds a few operations per score, small next to these. The score matrix itself holds \(T^2\) numbers:
For a whole layer with \(H\) heads and \(H d_k = d\), the attention core costs \(4 T^2 d\) FLOPs. Compare it with the four projections \(Q, K, V\) and the output \(W_O\): each is a \((T \times d)(d \times d)\) product, \(2 T d^2\) FLOPs, so \(8 T d^2\) in total for standard multi-head attention. The ratio is
So for short sequences (\(T \lt 2d\)) the projections dominate and attention looks cheap. For long sequences the \(T^2\) part wins and keeps growing: doubling \(T\) doubles the projection cost but quadruples the attention core. With grouped-query attention (smaller \(W_K, W_V\)), projections are cheaper and the crossover comes earlier: for Llama 3.1 8B the projections cost \(5 T d^2\), so the crossover is at \(T = 1.25\,d = 5{,}120\) tokens.
Per layer: \(d = 4096\), \(H = 32\) query heads [Certain, config.json]. Scores in BF16 take 2 bytes each.
At \(T = 1{,}024\): score memory \(32 \times 1024^2 \times 2\) bytes \(= 64\) MiB per layer, per sequence. Attention core \(4 \times 1024^2 \times 4096 = 1.7 \times 10^{10}\) FLOPs, only 1/8 of the MHA-style projection cost.
At \(T = 8{,}192\) (8 times longer): score memory \(32 \times 8192^2 \times 2 = 4\) GiB per layer, 64 times more. If a naive implementation stores \(A\) for the backward pass in all 32 layers, that is 128 GiB for one sequence, more than an 80 GB GPU. Attention core \(1.1 \times 10^{12}\) FLOPs per layer.
At \(T = 131{,}072\) (the model’s maximum context): one layer’s scores would need \(32 \times 131072^2 \times 2\) bytes \(= 1\) TiB. This is why long-context models cannot run attention naively, and why FlashAttention, which never stores the scores, is not optional.
Figure 4 lets you move \(T\) and compare two real models.
How to read Figure 4
Each step of the slider doubles \(T\). Watch the readout: projection FLOPs double, attention-core FLOPs and score memory grow 4 times. GPT-2 small (\(d = 768\), 12 heads, full multi-head attention) crosses at \(T = 2d = 1{,}536\), just above its 1,024-token context. Llama 3.1 8B (\(d = 4096\), GQA with 8 key-value heads) crosses at \(T = 5{,}120\). This chart counts only the attention block; the feed-forward network adds another cost that grows like \(T\) (session 25).
Memory is often the harder limit. FLOPs can be spread over time, but a tensor that does not fit does not run. That is why the first fix was to stop storing the score matrix (FlashAttention: exact, memory \(O(T)\), compute still \(O(T^2)\)), and why approaches that reduce the compute itself change the model: sliding windows, sparse patterns, linear attention, state-space models (session 27).
Where this is used
| Setting | What \(Q\), \(K\), \(V\) are | Typical \(T\), and what the \(T^2\) means |
|---|---|---|
| LLM pretraining (Llama, Qwen, GPT) | All from the same text tokens (self-attention, causal mask) | 4k to 8k tokens in most pretraining, longer in a final long-context stage [Likely]; fused kernels are required |
| LLM generation with a KV cache | \(Q\): the 1 new token; \(K, V\): all cached past tokens | \(T_q = 1\), so each step costs \(O(T_k\, d)\); the problem moves from compute to reading the cache from memory (session 80) |
| Vision Transformer on one image | Image patches (plus a class token) | ViT-B/16 at \(224 \times 224\): 196 patches + 1 = 197 tokens, 38,809 scores per head; cheap [Certain] |
| VLM reading an image and a question | Image tokens and text tokens in one sequence, or text queries over image keys (cross-attention) | High-resolution images give thousands of image tokens, so the \(T^2\) cost appears quickly (session 164) |
| Video classification and action recognition | Patches from many frames | 16 frames × 196 patches = 3,136 tokens: 9.8 million scores per head, 253 times more than one image. This is why video transformers such as ViViT also offer variants that factorize attention into space and time [Certain] |
| Video retrieval, key-moment detection, Video-RAG | A text query attends over frame or clip features (cross-attention, \(T_q \ll T_k\)) | \(T_q \times T_k\) scores (formula 17.9); the attention weights over time can be read as a rough “where in the video” signal [Likely] |
| Retrieval and fingerprinting encoders | Self-attention inside a text or video encoder that outputs one vector | Attention runs once per item at indexing time; at query time only vectors are compared |
Common mistakes
- Softmax over the wrong axis. Scores are
(..., T_q, T_k); the softmax goes over keys,dim=-1. A wrong axis gives no error and a model that trains poorly. - Forgetting the scale, or using the wrong \(d\). Divide by \(\sqrt{d_k}\), the head size (for example 128), not by \(\sqrt{d}\) of the whole model (4096) and not by \(d_k\).
- Transposing the wrong tensor. It is \(QK^\top\), with \(K\) transposed on its last two axes:
k.transpose(-2, -1). Usingk.Ton a 4-D tensor reverses all four axes. - Mixing up \(T\) and \(d_k\) when reshaping heads. Go from
(B, T, d)to(B, T, H, d_k)withview, thentranspose(1, 2)to(B, H, T, d_k). Callingview(B, H, T, d_k)directly runs but mixes tokens and heads. - A naive softmax in FP16. Scores above about 11 overflow. Subtract the row maximum (17.7), or use the fused function.
- Masking after the softmax. Setting weights to 0 after the softmax leaves rows that no longer sum to 1. Add \(-\infty\) (or a large negative number) to the scores before the softmax (Session 18).
- Thinking attention knows order. Without positions or masks it is permutation-equivariant: “dog bites man” and “man bites dog” give the same set of output vectors.
- Estimating memory with weights only. At long context, the \(B \cdot H \cdot T^2\) score tensor (if materialized) can be larger than the whole model.
Interview questions
Write scaled dot-product attention and give the shape of every tensor.basic
(B, H, T, d_k), scores (B, H, T, T), output (B, H, T, d_v), then heads are joined to (B, T, d) and multiplied by \(W_O\).Why do we divide by \(\sqrt{d_k}\)?core
Why \(\sqrt{d_k}\) and not \(d_k\)?core
What is the time and memory complexity of self-attention?core
Why subtract the maximum before the softmax? Does it change the result?basic
Why use separate \(W_Q\) and \(W_K\)? What happens if they are the same matrix?core
Dot-product vs additive attention?core
Is attention permutation-invariant or equivariant? Why does that matter?core
Derive the gradient of attention with respect to the scores.advanced
Llama 3.1 8B at 8k context: how much memory would naive attention scores take?advanced
During decoding with a KV cache, what are the shapes and the cost of one attention step?advanced
(B, H, 1, d_k). The cache holds \(K, V\) of shape (B, H_kv, T_k, d_k). Scores are (B, H, 1, T_k), a single row. Compute is \(O(T_k d)\) per token, but every step must read the whole cache from GPU memory, so decoding is limited by memory bandwidth, not FLOPs. That is why MQA and GQA (fewer K/V heads) speed up generation.Exercises
- In the worked example, compute row 2 of \(A\) and \(\mathbf{o}_2\) by hand. Check with Figure 3.
- \(Q\) has shape
(4, 16, 512, 64). What are \(B\), \(H\), \(T\), \(d_k\)? What is the shape of the scores, and by what number do you divide them? - Show that \(\softmax(\mathbf{z} + c\mathbf{1}) = \softmax(\mathbf{z})\) for any constant \(c\).
- Components of \(\mathbf{q}, \mathbf{k}\) have variance \(\sigma^2 = 4\) (not 1) and \(d_k = 64\). What is the standard deviation of \(\mathbf{q}\cdot\mathbf{k}\), and of the scaled score?
- For GPT-2 small (\(d = 768\), 12 heads, \(T = 1024\)), compute the attention-core FLOPs and the projection FLOPs per layer, and the score memory per layer in FP32.
- A video model attends jointly over 32 frames of 196 patches each. How many scores per head is that, compared with one frame?
- Explain why Algorithm 2 gives exactly the same output as Algorithm 1, and what it does not save.
Answerscheck
(4, 16, 512, 512), divided by \(\sqrt{64} = 8\). 3. \(e^{z_j + c} / \sum_l e^{z_l + c} = e^c e^{z_j} / (e^c \sum_l e^{z_l})\); the \(e^c\) cancels. 4. Each product \(q_l k_l\) has variance \(\sigma^2 \cdot \sigma^2 = 16\), so \(\operatorname{Var} = 64 \times 16 = 1024\) and the standard deviation is 32. Scaled by \(1/8\): standard deviation 4. The \(\sqrt{d_k}\) fixes the growth with \(d_k\), not the size of the inputs; that is the job of normalization layers (or QK-norm). 5. Attention core \(4 \times 1024^2 \times 768 = 3.22 \times 10^9\) FLOPs; projections \(8 \times 1024 \times 768^2 = 4.83 \times 10^9\) (ratio \(T/2d = 0.667\)). Score memory \(12 \times 1024^2 \times 4\) bytes \(= 48\) MiB (50.3 MB). 6. \(T = 32 \times 196 = 6{,}272\); \(6272^2 = 39{,}337{,}984\) scores per head, \(32^2 = 1{,}024\) times one frame’s \(196^2 = 38{,}416\). 7. Each output row \(\mathbf{o}_i\) depends only on \(\mathbf{q}_i\) and all of \(K, V\), so rows can be computed in any grouping. It saves memory (\(bT\) instead of \(T^2\) scores at a time) but not compute: all \(T^2\) dot products are still done.Key takeaways
- Attention is \(\softmax(QK^\top/\sqrt{d_k})V\) (17.1), with \(Q = XW_Q\), \(K = XW_K\), \(V = XW_V\) (17.2), each \(T \times d_k\) for one head.
- Four steps: dot-product scores \(T \times T\) (17.3), divide by \(\sqrt{d_k}\) (17.4), softmax over keys so each row sums to 1 (17.6), and a weighted average of the values (17.8).
- A dot product of random vectors has variance \(d_k\) (17.4). Without the scale, softmax saturates, its Jacobian (17.5) goes to zero, and \(Q\), \(K\) stop learning. \(\sqrt{d_k}\), not \(d_k\), restores variance 1.
- Subtract the row maximum before exponentiating (17.7). The backward pass (17.10) needs \(A\), stored or recomputed.
- Cost per layer: \(4T^2 d\) FLOPs and \(H T^2\) stored scores (17.11), against \(8Td^2\) for the projections (17.12). For Llama 3.1 8B at 8k tokens, naive scores take 4 GiB per layer; FlashAttention removes the memory, not the \(T^2\) compute.
Key formulas
References for this session
- Vaswani et al. (2017). Attention Is All You Need
- Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, chapter 7: Transformers and Pretraining
- Xiao & Zhu, NLP: Neural Networks and Large Language Models, chapter 6: Transformers
- Vaswani et al. (2017). Attention Is All You Need
- Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, chapter 7: Transformers and Pretraining
- Xiao & Zhu, NLP: Neural Networks and Large Language Models, chapter 6: Transformers
- Raschka, Build a Large Language Model (From Scratch), chapter 3: Coding attention mechanisms
- Bahdanau et al. (2014). Neural Machine Translation by Jointly Learning to Align and Translate
- Luong et al. (2015). Effective Approaches to Attention-based Neural Machine Translation
- Dao et al. (2022). FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness
- Milakov & Gimelshein (2018). Online normalizer calculation for softmax
- Yang et al. (2022). Tensor Programs V: Tuning Large Neural Networks via Zero-Shot Hyperparameter Transfer
- Dehghani et al. (2023). Scaling Vision Transformers to 22 Billion Parameters
- Dosovitskiy et al. (2020). An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
- Arnab et al. (2021). ViViT: A Video Vision Transformer
- Llama Team, Meta (2024). The Llama 3 Herd of Models