LLM & VLM courseBlog
2Track 1: Foundations · session 2 of 15

Math you need, part 1: vectors, dot products, matrices and softmax

Every number inside an LLM lives in a vector or a matrix, and almost every step is a dot product, a matrix multiplication or a softmax. This session builds these four tools slowly, with pictures you can move and numbers you can check by hand. At the end we use all four to compute one attention step on paper.

Time: 3 to 4 hours (reading 2 hours, exercises 1 to 2 hours)Level: BeginnerBefore this: Session 1 and high-school algebra

What you will learn

  • What a vector is, and how to read its length and direction
  • The dot product: what it measures, why it is the heart of attention, and why attention divides by the square root of the dimension
  • A matrix as a machine that transforms vectors, and how a linear layer works
  • Matrix multiplication: the shape rule, the cost in FLOPs, and the real numbers for an 8B model
  • Tensor shapes in PyTorch: (B, T, d), broadcasting and einsum
  • Softmax in depth: stability, the log-sum-exp trick, its gradient (the famous p − y), and the online softmax used by FlashAttention
  • One attention step computed fully by hand

Why this matters

Open any LLM and look at what it computes. You will find only a few kinds of operations, repeated billions of times: lists of numbers (vectors), tables of numbers (matrices), multiplications between them, and softmax.

In Session 1 we saw the path: tokens become vectors, vectors pass through blocks, the last vector becomes scores, and softmax turns scores into probabilities. Every arrow in that picture is one of the tools in this session:

  • The embedding lookup picks a row of a matrix.
  • Attention compares tokens with dot products, turns the results into weights with softmax, and mixes vectors with a weighted sum.
  • The MLP and all the projections are matrix multiplications. More than 95% of the compute of an LLM is matrix multiplication. [Likely]
  • The output layer is one more matrix multiplication followed by softmax.

Interviewers test these tools all the time, often in disguise: “What is the shape of \(QK^\top\)?”, “Why divide by \(\sqrt{d_k}\)?”, “What is the gradient of cross-entropy with respect to the logits?”, “How many FLOPs is this layer?”. By the end of this session you can answer all of them with numbers.

Vectors: lists of numbers that mean something

A vector is an ordered list of numbers. We write vectors in bold, and we say how many numbers they have:

\[ \mathbf{x} = (x_1, x_2, \dots, x_d) \in \R^{d} \tag{2.1} \]
Read the symbols
\(\mathbf{x}\)
the whole vector (bold letter)
\(x_i\)
its \(i\)-th number, also called its \(i\)-th component (normal letter)
\(d\)
the number of components, the dimension
\(\R^{d}\)
“the set of all lists of \(d\) real numbers”. The symbol \(\in\) means “is in”.

There are two ways to picture a vector, and you need both:

  • As an arrow from the origin to a point. With \(d = 2\) you can draw it on paper. Its direction and its length carry meaning.
  • As a list of features. Each position measures something. For example, a made-up 3-number vector for a word could be (how much about sport, how much about a person, how much about fruit).

Inside Llama 3 8B every token vector has \(d = 4096\) numbers. Nobody chose what each position means; training found useful features by itself. But the geometry is the same as in 2D: similar meanings point in similar directions.

Adding and scaling vectors

We add vectors component by component, and we scale (multiply by a number) every component:

\[ \mathbf{a} + \mathbf{b} = (a_1 + b_1,\ \dots,\ a_d + b_d), \qquad c\,\mathbf{a} = (c\,a_1,\ \dots,\ c\,a_d) \tag{2.2} \]

As arrows, adding means “walk along \(\mathbf{a}\), then along \(\mathbf{b}\)”. Scaling by 2 makes the arrow twice as long; scaling by \(-1\) turns it around. The residual stream from Session 1 is exactly this: each block adds its small vector to the running vector.

Length: the norm

The length of a vector is its norm, from Pythagoras:

\[ \lVert \mathbf{x} \rVert_2 = \sqrt{x_1^2 + x_2^2 + \dots + x_d^2} \tag{2.3} \]

For \(\mathbf{x} = (3, 4)\): \(\lVert \mathbf{x} \rVert = \sqrt{9 + 16} = 5\). A vector divided by its own length has length 1; we call it a unit vector, and this step is called normalizing. RMSNorm, used in every modern LLM, is a close cousin: it divides a vector by \(\sqrt{\text{mean of } x_i^2}\) (Session 22).

Figure 1. A vector playground. Drag the tips of \(\mathbf{a}\) (blue) and \(\mathbf{b}\) (orange), or focus a tip with Tab and use the arrow keys. The numbers below update with every move.
How to read Figure 1

The arc shows the angle \(\theta\) between the two arrows. Make the arrows point the same way: the dot product is large and positive and the cosine is close to 1. Make them perpendicular: both become 0. Point them in opposite directions: both become negative. Now keep the angle fixed and make \(\mathbf{a}\) longer: the dot product grows, but the cosine does not change. That is the whole difference between the dot product and the cosine similarity. The green segment is the projection: the part of \(\mathbf{a}\) that lies along \(\mathbf{b}\).

The dot product: how much do two vectors agree?

The dot product takes two vectors of the same size and returns one number. Multiply matching components and add everything up:

\[ \mathbf{a} \cdot \mathbf{b} = \sum_{i=1}^{d} a_i\, b_i = a_1 b_1 + a_2 b_2 + \dots + a_d b_d \tag{2.4} \]

The same number has a geometric meaning. With \(\theta\) the angle between the two arrows:

\[ \mathbf{a} \cdot \mathbf{b} = \lVert \mathbf{a} \rVert \, \lVert \mathbf{b} \rVert \cos\theta \tag{2.5} \]

So the dot product mixes two things: how long the vectors are, and how well they point the same way. If we only want the direction, we divide out the lengths. That is the cosine similarity:

\[ \cos\theta = \frac{\mathbf{a} \cdot \mathbf{b}}{\lVert \mathbf{a} \rVert \, \lVert \mathbf{b} \rVert} \in [-1, 1] \tag{2.6} \]
Angle\(\cos\theta\)Meaning
0°1same direction: very similar
90°0perpendicular: unrelated
180°\(-1\)opposite directions
Worked example: similar words point the same way

Use made-up features (sport, person, fruit): keeper \(= (0.9, 0.8, 0.1)\), goalkeeper \(= (0.95, 0.8, 0.0)\), banana \(= (0, 0, 0.95)\).

keeper · goalkeeper \(= 0.9 \cdot 0.95 + 0.8 \cdot 0.8 + 0.1 \cdot 0 = 1.495\). The lengths are \(1.208\) and \(1.242\), so the cosine is \(1.495 / (1.208 \times 1.242) = 0.996\): almost the same direction.

keeper · banana \(= 0 + 0 + 0.1 \cdot 0.95 = 0.095\), and the cosine is \(0.095 / (1.208 \times 0.95) = 0.083\): almost unrelated.

Projection: how much of \(\mathbf{a}\) lies along \(\mathbf{b}\)

Divide the dot product by the length of \(\mathbf{b}\) and you get the length of the “shadow” of \(\mathbf{a}\) on the line of \(\mathbf{b}\):

\[ \operatorname{proj}_{\mathbf{b}}(\mathbf{a}) = \frac{\mathbf{a} \cdot \mathbf{b}}{\lVert \mathbf{b} \rVert^2}\, \mathbf{b} \tag{2.7} \]

This is a useful way to read attention scores: a query “asks a question” in some direction, and each key’s dot product says how much it points that way.

Formulas (2.4), (2.5) and (2.7) are three views of the same number. Figure 2 computes them in order for one pair of vectors, line by line, and then turns \(\mathbf{a}\) around a full circle so you can watch the shadow grow, vanish and become negative.

Algorithm: dot product and projection
    Figure 2. The dot product as a projection, computed live. \(\mathbf{b} = (3, 1)\) is fixed (orange); \(\mathbf{a}\) (blue) starts at the chosen preset. Steps 1 to 7 run lines 1 to 7 of the algorithm. From step 8 on, line 8 turns \(\mathbf{a}\) by 15° per step and repeats the whole computation; the right panel plots every computed \(\mathbf{a} \cdot \mathbf{b}\) against the angle \(\theta\), and its dashed curve is formula (2.5), \(\lVert \mathbf{a} \rVert \lVert \mathbf{b} \rVert \cos\theta = 10\cos\theta\).
    How to read Figure 2

    Steps 2 and 3 show formula (2.4): the two thin bars on the axes are the matching components that get multiplied. For \(\mathbf{a} = (1, 3)\): \(1 \cdot 3 + 3 \cdot 1 = 6\). Step 4 gives \(\lVert \mathbf{b} \rVert = \sqrt{10} = 3.162\). Step 5 drops a dashed line from the tip of \(\mathbf{a}\) at a right angle onto the line of \(\mathbf{b}\); the green bar is the shadow, of signed length \(6 / 3.162 = 1.897\). Step 6 turns the shadow into the vector \(0.6\,\mathbf{b} = (1.8, 0.6)\), and step 7 gives \(\cos\theta = 0.6\), so \(\theta = 53.13°\). All three presets have \(\lVert \mathbf{a} \rVert = \sqrt{10}\), so \(\lVert \mathbf{a} \rVert \lVert \mathbf{b} \rVert = 10\) and the points on the right fall exactly on the dashed curve \(10\cos\theta\) of formula (2.5). The preset \((-1, 3)\) is perpendicular to \(\mathbf{b}\): dot product 0, no shadow. The preset \((-3, 1)\) gives \(-8\): the shadow points backwards.

    Why the dot product is the heart of attention

    In attention, every token makes a query vector \(\mathbf{q}\) (“what am I looking for?”) and a key vector \(\mathbf{k}\) (“what do I contain?”). The score between token \(i\) and token \(j\) is just \(\mathbf{q}_i \cdot \mathbf{k}_j\). A high score means “this token has what I am looking for”. The full story is in Session 17; here we only need one fact about how big these numbers get.

    Dot products grow with the dimension

    Take two random vectors whose components are independent, with mean 0 and variance 1. Each product \(a_i b_i\) also has mean 0 and variance 1. A sum of \(d\) independent terms has variance \(d\). So:

    \[ \operatorname{Var}(\mathbf{a} \cdot \mathbf{b}) = d, \qquad \operatorname{std}(\mathbf{a} \cdot \mathbf{b}) = \sqrt{d} \tag{2.8} \]

    With \(d = 128\) (a typical attention head), typical dot products are about \(\pm 11\). Softmax of numbers that far apart puts almost all weight on one token, and its gradients become tiny. Dividing by \(\sqrt{d}\) brings the spread back to about 1. That is exactly why attention uses \(\mathbf{q} \cdot \mathbf{k} / \sqrt{d_k}\). Figure 3 shows it with real random samples.

    Figure 3. Up to 2,000 pairs of random vectors (fewer for very large \(d\), so the page stays fast) with independent standard normal components. Left: the raw dot products. Right: the same values divided by \(\sqrt{d}\). The readout also shows what softmax does to 8 such scores.
    How to read Figure 3

    Move \(d\) from 1 to 4,096. The left histogram gets wider and wider: its standard deviation follows \(\sqrt{d}\). The right one stays the same width. The softmax line in the readout is the key point for attention: with raw scores and large \(d\), the biggest of 8 weights is close to 1 (one token takes everything). With scaled scores it stays moderate, so several tokens can share attention and gradients keep flowing.

    Matrices: machines that transform vectors

    A matrix is a table of numbers with \(m\) rows and \(n\) columns. We write \(W \in \R^{m \times n}\) and \(W_{ij}\) for the number in row \(i\), column \(j\). Multiplying a matrix by a vector gives a new vector:

    \[ \mathbf{y} = W \mathbf{x}, \qquad y_i = \sum_{j=1}^{n} W_{ij}\, x_j, \qquad W \in \R^{m \times n},\ \mathbf{x} \in \R^{n},\ \mathbf{y} \in \R^{m} \tag{2.9} \]

    Read this in two ways. Both are useful.

    • Row view: \(y_i\) is the dot product of row \(i\) of \(W\) with \(\mathbf{x}\). So a matrix is \(m\) “detectors”, and each one measures how much \(\mathbf{x}\) points in its direction.
    • Column view: \(\mathbf{y}\) is a mix of the columns of \(W\), with the numbers \(x_j\) as the mixing amounts. So the input decides how much of each column to use.

    A linear layer in a neural network is exactly this, plus a bias vector: \(\mathbf{y} = W\mathbf{x} + \mathbf{b}\). Its weights \(W\) and \(\mathbf{b}\) are learned. Note that PyTorch stores the weight of nn.Linear(n, m) with shape \((m, n)\) and computes \(\mathbf{x} W^\top\) for row vectors; the math is the same.

    In 2D you can see what a matrix does: it moves every point of the plane. It can rotate, stretch, shear, flip, or squash the plane onto a line. Try each preset in Figure 4.

    \(W =\)
    Figure 4. A 2×2 matrix acting on the plane. Grey: the original grid. Color: the grid after multiplying every point by \(W\). The first column of \(W\) is where the arrow \((1, 0)\) lands; the second column is where \((0, 1)\) lands.
    How to read Figure 4

    Change one number at a time and watch the two colored arrows: they are the columns of \(W\). The shaded square (area 1) becomes a parallelogram whose area is the determinant \(W_{11}W_{22} - W_{12}W_{21}\). “Squash” has determinant 0: the whole plane falls onto one line, and information is lost forever. Such a matrix has rank 1. Low-rank matrices come back in LoRA (session 57), where a big update is built from two thin matrices.

    Matrix multiplication

    Multiplying two matrices is many matrix-vector products at once. If \(A\) is \(m \times k\) and \(B\) is \(k \times n\), then \(C = AB\) is \(m \times n\), and each entry is one dot product: row \(i\) of \(A\) with column \(j\) of \(B\):

    \[ C_{ij} = \sum_{p=1}^{k} A_{ip}\, B_{pj}, \qquad (m \times k)\,(k \times n) \to (m \times n) \tag{2.10} \]

    The shape rule: the inner sizes must match (both \(k\)), and they disappear. The outer sizes remain. Check shapes before anything else; most bugs in model code are shape bugs.

    Worked example
    \[ \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 2 & -1 \end{pmatrix} = \begin{pmatrix} 1{+}0{+}6 & 0{+}2{-}3 \\ 4{+}0{+}12 & 0{+}5{-}6 \end{pmatrix} = \begin{pmatrix} 7 & -1 \\ 16 & -1 \end{pmatrix} \]

    Shapes: \((2 \times 3)(3 \times 2) \to (2 \times 2)\). Look at the first column of \(C\): it is \(A\) times the first column of \(B\). So a matrix product is just one matrix-vector product (2.9) per column of \(B\). Figure 5 runs both views of (2.9) and then Algorithm 1 (in the pseudo-code section) on this example.

    Algorithm
      Figure 5. Matrix-vector and matrix-matrix multiplication, one multiply-add at a time, with \(W = A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix}\) and \(B\) from the worked example. Blue: the entry of \(W\) or \(A\) in use. Orange: the entry of \(\mathbf{x}\) or \(B\) in use. Green: the output being written. The FLOP counter checks formula (2.11).
      How to read Figure 5

      Row view. Each output \(y_i\) is one dot product: with \(\mathbf{x} = (1, 0, 2)\), \(y_1 = 1 \cdot 1 + 2 \cdot 0 + 3 \cdot 2 = 7\) and \(y_2 = 4 + 0 + 12 = 16\). Column view. The same \(\mathbf{y}\) is built as \(1 \cdot (1, 4) + 0 \cdot (2, 5) + 2 \cdot (3, 6) = (7, 16)\): the input decides how much of each column to add. Both views do the same 6 multiply-adds, \(2 \cdot 2 \cdot 3 = 12\) FLOPs, in a different order. A B. The triple loop of Algorithm 1 writes the four cells of \(C\) with 12 multiply-adds, \(2mkn = 24\) FLOPs. The first column of \(C\) is \((7, 16)\), the \(\mathbf{y}\) of the row view; pick “x = column 2 of B” to get \((-1, -1)\), the second column. Click any cell of \(C\) to jump to the step that finishes it.

      The cost of a matrix multiplication

      Each of the \(m \cdot n\) output cells needs \(k\) multiplications and about \(k\) additions. So:

      \[ \text{FLOPs}(AB) \approx 2\, m\, k\, n \tag{2.11} \]

      A linear layer from \(n\) to \(m\) features applied to one token costs \(2mn\) FLOPs: two FLOPs per weight. That is where the “\(2N\) FLOPs per token” of Session 1 comes from.

      Real numbers: one MLP in Llama 3 8B

      Each MLP has three matrices of size \(4096 \times 14336\). Per token: \(3 \times 2 \times 4096 \times 14336 = 352{,}321{,}536\), about 352 million FLOPs per token per layer. With 32 layers that is about 11.3 GFLOPs per token for the MLPs alone, most of the \(2N \approx 16\) GFLOPs total.

      Transpose and batched multiplication

      The transpose \(A^\top\) swaps rows and columns: \((A^\top)_{ij} = A_{ji}\), and an \(m \times n\) matrix becomes \(n \times m\). One rule you will use often: \((AB)^\top = B^\top A^\top\).

      Put the \(T\) query vectors of a sentence as the rows of \(Q \in \R^{T \times d}\), and the keys as the rows of \(K \in \R^{T \times d}\). Then all query–key dot products come from one multiplication:

      \[ S = Q K^\top \in \R^{T \times T}, \qquad S_{ij} = \mathbf{q}_i \cdot \mathbf{k}_j \tag{2.12} \]

      GPUs are built to do such multiplications fast, so writing many dot products as one matrix multiplication is the main speed trick of deep learning. With a batch of \(B\) sentences and \(H\) heads, PyTorch does \(B \cdot H\) of these at once: shapes \((B, H, T, d) \times (B, H, d, T)\) \(\to (B, H, T, T)\).

      Tensors, shapes and PyTorch

      A tensor is the general name for an array with any number of axes: a vector has 1 axis, a matrix 2, and an LLM activation usually has 3: \((B, T, d)\) for batch, tokens and features. Here is how the shape changes inside one block (Llama 3 8B, \(B = 2\), \(T = 16\)):

      StepOperationShape
      Inputtoken vectors(2, 16, 4096)
      Queries\(X W_Q\), split into 32 heads of 128(2, 32, 16, 128)
      Scores\(Q K^\top / \sqrt{128}\)(2, 32, 16, 16)
      Weightssoftmax over the last axis(2, 32, 16, 16)
      Mixweights × \(V\), heads joined back(2, 16, 4096)
      MLP up\(\times W_1\)(2, 16, 14336)
      MLP down\(\times W_2\)(2, 16, 4096)

      Broadcasting

      When two tensors have different shapes, PyTorch can stretch the smaller one without copying. It compares shapes from the right. Two sizes are compatible if they are equal, or if one of them is 1 (that axis is repeated). A missing axis counts as size 1.

      Example: adding a mask

      Scores have shape \((B, H, T, T)\). A padding mask has shape \((B, T)\). Adding them directly fails, or worse, broadcasts the wrong way. Reshape the mask to \((B, 1, 1, T)\): now it is repeated over heads (\(H\)) and over query rows (\(T\)), and it masks the key axis, which is what we want.

      Einsum: write the math, get the code

      torch.einsum lets you write a product by naming the axes. Repeated letters that disappear from the output are summed:

      y = torch.einsum("btd,de->bte", x, W)          # linear layer: sum over d
      s = torch.einsum("bhqd,bhkd->bhqk", q, k)      # all attention scores, formula (2.12)
      o = torch.einsum("bhqk,bhkd->bhqd", a, v)      # weighted sum of values

      Softmax, in depth

      Session 1 introduced softmax. Here we go deeper, because softmax is everywhere: the output layer, every attention head, and the router of a mixture-of-experts layer (session 29).

      \[ \softmax(\mathbf{z})_i = p_i = \frac{e^{z_i}}{\sum_{j=1}^{n} e^{z_j}} \tag{2.13} \]

      Five properties, with short reasons

      1. Every \(p_i\) is positive and they sum to 1. Exponentials are positive, and we divide by their sum.
      2. Order is kept. \(e^z\) grows with \(z\), so a bigger score always gets a bigger probability.
      3. Adding the same number to all scores changes nothing. This is the key to stable code:
        \[ \frac{e^{z_i + c}}{\sum_j e^{z_j + c}} = \frac{e^{c}\, e^{z_i}}{e^{c} \sum_j e^{z_j}} = \frac{e^{z_i}}{\sum_j e^{z_j}} \tag{2.14} \]
      4. Only differences matter. A gap of \(\Delta\) between two scores means a ratio \(e^{\Delta}\) between their probabilities. With two classes, softmax becomes the sigmoid: \(p_1 = 1 / (1 + e^{-(z_1 - z_2)})\).
      5. Temperature scales all differences: \(\softmax(\mathbf{z}/\tau)\) is sharper for \(\tau \lt 1\) and flatter for \(\tau \gt 1\).

      Stable softmax and the log-sum-exp trick

      Computers overflow at about \(e^{89}\) in 32-bit float and much sooner in 16-bit. Scores like 1000 would give infinity. Property 3 saves us: subtract the largest score \(m = \max_j z_j\) first. Then the largest exponent is \(e^0 = 1\), and nothing overflows.

      We often need the log of the probability (for the loss). Computing \(\log(p_i)\) after softmax can give \(\log 0 = -\infty\) when \(p_i\) underflows. Instead we use the log-sum-exp function:

      \[ \operatorname{LSE}(\mathbf{z}) = \log \sum_j e^{z_j} = m + \log \sum_j e^{z_j - m}, \qquad \log p_i = z_i - \operatorname{LSE}(\mathbf{z}) \tag{2.15} \]

      For \(\mathbf{z} = (1000, 999, 998)\): \(m = 1000\), and

      \[ \operatorname{LSE} = 1000 + \log\left(1 + e^{-1} + e^{-2}\right) = 1000.408 \]

      No overflow anywhere. This is what torch.log_softmax and F.cross_entropy do inside.

      Figure 6 runs Algorithm 2 (in the pseudo-code section) on four scores, one line at a time, with a temperature \(\tau\) added in front: first \(u_j = z_j / \tau\), then the stable softmax of \(\mathbf{u}\). Next to it, a naive version computes \(e^{u_j}\) without the shift, in 32-bit float.

      Algorithm 2 with temperature
        Figure 6. Stable softmax, step by step, with live numbers. Each column of the table is one line of the algorithm; the cell being computed is outlined in blue and the maximum in orange. Move \(\tau\) at any moment: every number already computed is recomputed at once. The readout runs the naive formula \(e^{u_j} / \sum_k e^{u_k}\) in 32-bit float for comparison.
        How to read Figure 6

        With \(\mathbf{z} = (2, 1, 0.1, -1)\) and \(\tau = 1\): \(m = 2\), the shifted scores are \((0, -1, -1.9, -3)\), the exponentials \((1, 0.368, 0.150, 0.050)\), their sum \(s = 1.567\), and \(\mathbf{p} = (0.638, 0.235, 0.095, 0.032)\). The largest exponential is always exactly 1. Lower \(\tau\) to 0.5: the scores double, \(\mathbf{p} = (0.862, 0.117, 0.019, 0.002)\). Raise it to 5: \(\mathbf{p} = (0.328, 0.268, 0.224, 0.180)\), close to uniform. Now pick \((1000, 999, 998, 990)\): the stable path gives \(\mathbf{p} = (0.665, 0.245, 0.090, 0.00003)\) and \(\log p_1 = -0.408\), the LSE example above. The naive path overflows: \(e^{1000}\) is \(\infty\) in float32 (its limit is about \(e^{88.7}\)), and \(\infty / \infty\) is NaN. Even \(\tau = 5\) does not save it, because \(u_1 = 200\) still overflows.

        The gradient of softmax

        How does \(p_i\) change when we move score \(z_j\)? Using the quotient rule:

        \[ \frac{\partial p_i}{\partial z_j} = p_i\,(\delta_{ij} - p_j), \qquad \text{in matrix form } J = \operatorname{diag}(\mathbf{p}) - \mathbf{p}\mathbf{p}^\top \tag{2.16} \]

        Here \(\delta_{ij}\) is 1 when \(i = j\) and 0 otherwise. Raising your own score raises your probability (by \(p_i(1 - p_i)\)); raising another score lowers it (by \(p_i p_j\)). Every row of \(J\) sums to 0, because adding the same amount to all scores changes nothing (property 3).

        Softmax plus cross-entropy: the gradient is \(\mathbf{p} - \mathbf{y}\)

        This is one of the most asked derivations. Let the correct class be \(c\), and let \(\mathbf{y}\) be the one-hot vector (1 at \(c\), 0 elsewhere). The loss is

        \[ \mathcal{L} = -\log p_c = -z_c + \log \sum_j e^{z_j} \tag{2.17} \]

        Take the derivative with respect to \(z_i\). The first term gives \(-1\) if \(i = c\) and 0 otherwise, which is \(-y_i\). The second term gives \(e^{z_i} / \sum_j e^{z_j} = p_i\). So:

        \[ \frac{\partial \mathcal{L}}{\partial \mathbf{z}} = \mathbf{p} - \mathbf{y} \tag{2.18} \]

        Beautiful and simple: the gradient is “what the model said minus what it should have said”. The correct score is pushed up by \(1 - p_c\); every wrong score is pushed down by its own probability. A gradient step moves all scores at once, as Figure 7 shows.

        Worked example

        Scores \((2, 1, 0.1)\), correct class 1. Then \(\mathbf{p} = (0.659, 0.242, 0.099)\), the loss is \(0.417\), and the gradient is \((-0.341,\ 0.242,\ 0.099)\). One step with learning rate 1 gives scores \((2.341, 0.758, 0.001)\), new probabilities \((0.768, 0.158, 0.074)\), and a lower loss of \(0.264\).

        Figure 7. Gradient descent on the logits with softmax and cross-entropy. Columns: the score \(z_i\), the probability \(p_i\), and the gradient \(p_i - y_i\) (orange pushes the score down, blue pushes it up).
        How to read Figure 7

        Choose “cake” as the correct class: it starts with a tiny probability, so its gradient is close to \(-1\) and it rises fast. Press the step button several times: the loss drops quickly at first, then slowly, because \(\mathbf{p} - \mathbf{y}\) shrinks as the model becomes right. A very large learning rate overshoots. This is what happens to the output layer of an LLM during training, with 128,256 classes instead of 4.

        Online softmax: softmax in one pass, block by block

        To compute softmax over a very long row, we normally need two passes: one to find the maximum \(m\), and one to sum the exponentials. FlashAttention cannot afford to read the row twice. The trick is to keep a running maximum \(m\) and a running sum \(\ell\), and fix the old sum whenever the maximum grows:

        \[ m' = \max(m, m_{\text{new}}), \qquad \ell' = \ell \, e^{m - m'} + \ell_{\text{new}} \, e^{m_{\text{new}} - m'} \tag{2.19} \]

        where \(m_{\text{new}}\) and \(\ell_{\text{new}}\) are the maximum and the sum of \(e^{z - m_{\text{new}}}\) for the new block. The factor \(e^{m - m'}\) rescales the old sum to the new reference point. The result is exactly the same as the two-pass softmax. Step through it in Figure 8.

        Figure 8. Online softmax over 8 scores in two blocks of 4. Only one block is “in memory” at a time, yet the final maximum and sum equal the two-pass result.

        Putting it together: one attention step by hand

        Now we can compute a full attention step with all four tools. Three tokens, “keeper”, “ball”, “it”, each with a 2-number query, key and value (in a real model these come from multiplying token vectors by \(W_Q\), \(W_K\), \(W_V\)):

        \[ Q = \begin{pmatrix} 1 & 1 \\ 1 & 0 \\ 0 & 2 \end{pmatrix}, \quad K = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 0.2 & 0.6 \end{pmatrix}, \quad V = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 0.5 & 0.5 \end{pmatrix} \]

        The four steps are: scores \(S = QK^\top / \sqrt{2}\) (formula 2.12); a causal mask (each token sees only itself and earlier tokens); softmax on each row (formula 2.13); and the output \(O = AV\) (formula 2.10):

        \[ O = \softmax\!\left( \frac{QK^\top}{\sqrt{d}} + M \right) V \tag{2.20} \]
        Figure 9. Attention for three tokens, computed step by step with the exact numbers. The darker a weight cell, the more attention.

        Look at the last row: “it” puts weight 0.552 on “ball”, 0.314 on itself and only 0.134 on “keeper”. Its output \((0.291, 0.709)\) is mostly the value of “ball”. In words: the model has worked out what “it” refers to, using nothing but dot products, a softmax and a weighted sum. Track 2 builds the full mechanism around this one line.

        Where these tools are used

        ApplicationToolHow
        Semantic text searchCosine similarityRank documents by the cosine between query and document embeddings (session 150)
        Text-to-video retrievalDot product of unit vectorsA text embedding and each clip embedding live in one space; the best clips have the largest dot product (session 208)
        Video fingerprintingCosine plus a thresholdTwo frames are “the same content” if their copy-detection descriptors have cosine above a tuned threshold (session 209)
        Classification (sentiment, action type, shot type)Matrix multiplication + softmaxA linear layer maps a pooled vector to one score per class; softmax gives class probabilities; training uses the \(\mathbf{p} - \mathbf{y}\) gradient
        Attention in every LLM and VLMAll fourFormula (2.20)
        Mixture of expertsMatrix multiplication + softmaxA router scores each expert for each token; softmax picks the top experts

        Pseudo-code

        Algorithm 1: matrix multiplication, and its cost
        1. input: \(A \in \R^{m \times k}\), \(B \in \R^{k \times n}\)
        2. \(C \leftarrow\) zeros\((m, n)\)
        3. for \(i = 1\) to \(m\) do
        4. for \(j = 1\) to \(n\) do
        5. for \(p = 1\) to \(k\) do
        6. \(C_{ij} \leftarrow C_{ij} + A_{ip} B_{pj}\) // 1 multiply + 1 add
        7. return \(C\) // total about \(2mkn\) FLOPs, formula (2.11)
        Algorithm 2: stable softmax and log-softmax
        1. input: scores \(\mathbf{z} \in \R^{n}\)
        2. \(m \leftarrow \max_j z_j\) // formula (2.14): shifting changes nothing
        3. \(e_j \leftarrow \exp(z_j - m)\) for all \(j\) // largest value is exactly 1
        4. \(s \leftarrow \sum_j e_j\)
        5. \(p_j \leftarrow e_j / s\) // softmax
        6. \(\log p_j \leftarrow z_j - (m + \log s)\) // log-softmax via LSE, formula (2.15)
        Algorithm 3: online softmax (one pass over blocks)
        1. input: blocks of scores \(\mathbf{z}^{(1)}, \dots, \mathbf{z}^{(B)}\)
        2. \(m \leftarrow -\infty\), \(\ell \leftarrow 0\)
        3. for each block \(\mathbf{z}^{(b)}\) do
        4. \(m_b \leftarrow \max \mathbf{z}^{(b)}\), \(\ell_b \leftarrow \sum \exp(\mathbf{z}^{(b)} - m_b)\)
        5. \(m' \leftarrow \max(m, m_b)\)
        6. \(\ell \leftarrow \ell\, e^{m - m'} + \ell_b\, e^{m_b - m'}\) // formula (2.19)
        7. \(m \leftarrow m'\)
        8. return \(m\), \(\ell\) // then \(p_j = e^{z_j - m} / \ell\)
        Algorithm 4: one attention head
        1. input: \(Q, K, V \in \R^{T \times d}\), causal flag
        2. \(S \leftarrow Q K^\top / \sqrt{d}\) // (T, T) scores, formula (2.12)
        3. if causal then \(S_{ij} \leftarrow -\infty\) for all \(j \gt i\)
        4. \(A \leftarrow\) softmax of each row of \(S\) // Algorithm 2 per row
        5. return \(O = A V\) // (T, d), formula (2.20)

        The same ideas as a short PyTorch script you can run. Each block checks one claim from this session:

        import torch
        import torch.nn.functional as F
        torch.manual_seed(0)
        
        # 1) dot product and cosine, formulas (2.4) and (2.6)
        keeper, goalkeeper = torch.tensor([0.9, 0.8, 0.1]), torch.tensor([0.95, 0.8, 0.0])
        print(keeper @ goalkeeper, F.cosine_similarity(keeper, goalkeeper, dim=0))   # 1.495, 0.996
        
        # 2) shapes and FLOPs of a linear layer, formula (2.11)
        B, T, d, d_ff = 2, 16, 4096, 14336
        x = torch.randn(B, T, d)
        W = torch.randn(d, d_ff) / d ** 0.5
        y = x @ W                                        # (2, 16, 14336)
        print(y.shape, "FLOPs:", 2 * B * T * d * d_ff)
        
        # 3) softmax is shift-invariant; the naive version overflows
        z = torch.tensor([1000.0, 999.0, 998.0])
        print(torch.softmax(z, dim=0))                  # fine: subtracts the max inside
        print(torch.exp(z) / torch.exp(z).sum())        # nan: inf / inf
        print(torch.logsumexp(z, dim=0))                # 1000.408, formula (2.15)
        
        # 4) gradient of cross-entropy w.r.t. the logits is p - y, formula (2.18)
        z = torch.tensor([2.0, 1.0, 0.1], requires_grad=True)
        loss = F.cross_entropy(z[None], torch.tensor([0]))
        loss.backward()
        print(z.grad, torch.softmax(z, 0).detach() - torch.tensor([1.0, 0.0, 0.0]))
        
        # 5) random dot products have std close to sqrt(d), formula (2.8)
        for dd in [4, 64, 1024]:
            s = (torch.randn(10000, dd) * torch.randn(10000, dd)).sum(-1)
            print(dd, round(s.std().item(), 2), round(dd ** 0.5, 2))
        
        # 6) the attention example of Figure 9, formula (2.20)
        Q = torch.tensor([[1., 1.], [1., 0.], [0., 2.]])
        K = torch.tensor([[1., 0.], [0., 1.], [0.2, 0.6]])
        V = torch.tensor([[1., 0.], [0., 1.], [0.5, 0.5]])
        S = Q @ K.T / 2 ** 0.5
        S = S.masked_fill(torch.triu(torch.ones(3, 3, dtype=torch.bool), 1), float("-inf"))
        A = torch.softmax(S, dim=-1)
        print(A.round(decimals=4), (A @ V).round(decimals=4))   # last row: 0.1342 0.5522 0.3136 and 0.291 0.709

        Common mistakes

        • Softmax over the wrong axis. Attention weights must sum to 1 over the keys (the last axis of \((B, H, T, T)\)). Softmax over queries gives a model that trains, but badly. Always write dim=-1 on purpose and check that rows sum to 1.
        • Computing \(\log(\softmax(\mathbf{z}))\) in two steps. It can give \(-\infty\) and NaN gradients. Use log_softmax or cross_entropy on raw logits.
        • Applying softmax before F.cross_entropy. It already contains log-softmax. Applying softmax twice trains much worse and often goes unnoticed.
        • Silent broadcasting. Shapes \((B, T)\) and \((B, T, T)\) may broadcast in a way you did not mean. Add explicit axes with [:, None, None, :] and assert shapes.
        • Mixing up \(W\) and \(W^\top\). nn.Linear(in, out).weight has shape (out, in). When you copy weights between frameworks, check this first.
        • Dot product when you meant cosine. If embeddings are not normalized, long vectors win every search. Normalize, or use cosine explicitly.
        • Masking with a large negative number in 16-bit. \(-10^9\) overflows FP16 (its range ends at 65,504). Use float("-inf") or the dtype’s minimum, and make sure no row is fully masked, or softmax returns NaN.

        Interview questions

        What does a dot product measure? When is it zero?basic
        It measures length times alignment: \(\mathbf{a} \cdot \mathbf{b} = \lVert\mathbf{a}\rVert\lVert\mathbf{b}\rVert\cos\theta\). It is zero when the vectors are perpendicular (or one is zero), positive when they point the same way, negative when opposite. Cosine similarity removes the lengths and keeps only the direction.
        Why does attention divide by \(\sqrt{d_k}\)?core
        If query and key components are roughly independent with unit variance, \(\mathbf{q}\cdot\mathbf{k}\) has variance \(d_k\), so its spread grows like \(\sqrt{d_k}\). Large score differences push softmax toward one-hot, where its gradient (formula 2.16) is nearly zero, so learning stalls. Dividing by \(\sqrt{d_k}\) keeps the scores at unit scale at initialization. Some models add QK-norm or a learned scale for the same reason.
        How many FLOPs does an \((m \times k)(k \times n)\) multiplication take? And a linear layer per token?basic
        About \(2mkn\): \(mkn\) multiplies and about as many adds. A linear layer with \(n\) inputs and \(m\) outputs costs \(2mn\) per token, two FLOPs per weight. Example: one Llama 3 8B MLP (three \(4096 \times 14336\) matrices) costs about 352 MFLOPs per token per layer.
        Derive the gradient of softmax cross-entropy with respect to the logits.core
        \(\mathcal{L} = -z_c + \log\sum_j e^{z_j}\). The derivative of \(-z_c\) w.r.t. \(z_i\) is \(-y_i\); the derivative of the log-sum-exp is \(p_i\). So \(\partial\mathcal{L}/\partial\mathbf{z} = \mathbf{p} - \mathbf{y}\). It is bounded in \([-1, 1]\) per component, which is one reason this loss trains stably.
        Why subtract the maximum in softmax? What is log-sum-exp?basic
        Softmax is invariant to adding a constant (formula 2.14), so subtracting the max changes nothing mathematically but makes the largest exponent \(e^0 = 1\), avoiding overflow. Log-sum-exp computes \(\log\sum e^{z_j}\) as \(m + \log\sum e^{z_j - m}\), giving a stable log-softmax \(z_i - \operatorname{LSE}(\mathbf{z})\) without ever forming tiny probabilities.
        What is the Jacobian of softmax, and why is it singular?advanced
        \(J = \operatorname{diag}(\mathbf{p}) - \mathbf{p}\mathbf{p}^\top\), i.e. \(\partial p_i/\partial z_j = p_i(\delta_{ij} - p_j)\). It is symmetric and its rows sum to zero, so \(J\mathbf{1} = \mathbf{0}\): the all-ones direction is in its null space. This matches shift invariance: adding the same value to every logit does not change the output. When \(\mathbf{p}\) is nearly one-hot, every entry of \(J\) is near zero, which is the saturation problem.
        How does FlashAttention compute softmax without storing the full score matrix?advanced
        With online softmax: it processes keys in blocks, keeps a running max \(m\), running sum \(\ell\) and running output \(O\) per query row, and when a new block raises the max it rescales the old \(\ell\) and \(O\) by \(e^{m - m'}\) (formula 2.19). The final result is exact. The \(T \times T\) matrix is never written to HBM, which saves memory traffic, the real bottleneck.
        Shape and memory of the attention score tensor for B=1, H=32, T=8192 in FP16?core
        Shape \((1, 32, 8192, 8192)\): about 2.15 billion entries, times 2 bytes, about 4.3 GB per layer. With 32 layers that is far more than the weights. Standard attention writes and reads this tensor; FlashAttention computes it in tiles inside on-chip memory instead.
        Dot product or cosine similarity for retrieval?core
        Cosine compares only direction; the dot product also rewards length, so long vectors dominate. If embeddings are L2-normalized, they are identical, and you can use fast maximum-inner-product indexes. Some models deliberately keep length meaningful (for example as a confidence); then use the dot product they were trained with. Always match the similarity used in training.
        What is the rank of a matrix, and why does it matter for LoRA?core
        Rank is the number of independent directions the matrix can output. A \(d \times d\) matrix of rank \(r\) can be written as \(BA\) with \(B \in \R^{d\times r}\), \(A \in \R^{r\times d}\): \(2dr\) numbers instead of \(d^2\). LoRA assumes the fine-tuning update has low rank, so it learns \(B\) and \(A\) only. With \(d = 4096\) and \(r = 16\): 131k parameters instead of 16.8M per matrix.
        You add a padding mask of shape (B, T) to scores of shape (B, H, T, T). What goes wrong, and how do you fix it?core
        Broadcasting aligns from the right: (B, T) is treated as (1, 1, B, T), which is wrong (it fails, or silently mixes batch and query axes when B equals T). Reshape to (B, 1, 1, T) so the mask repeats over heads and queries and applies to the key axis. Assert shapes, and test with a batch where padding differs between examples.

        Exercises

        1. Compute \(\mathbf{a}\cdot\mathbf{b}\), \(\lVert\mathbf{a}\rVert\), \(\lVert\mathbf{b}\rVert\) and the cosine for \(\mathbf{a} = (3, 4)\), \(\mathbf{b} = (4, -3)\). What is the angle?
        2. What is the shape of \(XW\) for \(X \in \R^{2 \times 16 \times 4096}\) and \(W \in \R^{4096 \times 1024}\)? How many FLOPs?
        3. Compute \(\operatorname{LSE}(2, 2)\) and \(\softmax(2, 2)\) by hand.
        4. For \(\mathbf{z} = (0, 0, 0, 0)\) and correct class 2, what is \(\mathbf{p} - \mathbf{y}\)?
        5. In Figure 3, at \(d = 1024\), about how large are typical raw dot products? What does softmax do to 8 of them?
        6. Run online softmax by hand on the scores \((1, 3 \mid 2, 5)\) in two blocks. Check the final sum against the direct sum of \(e^{z - 5}\).
        Answerscheck
        1. \(12 - 12 = 0\); both lengths are 5; cosine 0; the angle is 90°. 2. \((2, 16, 1024)\); \(2 \times 32 \times 4096 \times 1024 \approx 268\) MFLOPs. 3. \(\operatorname{LSE} = 2 + \log 2 = 2.693\); softmax \(= (0.5, 0.5)\). 4. \(\mathbf{p} = (0.25, 0.25, 0.25, 0.25)\), so \(\mathbf{p} - \mathbf{y} = (0.25, -0.75, 0.25, 0.25)\). 5. Standard deviation \(\sqrt{1024} = 32\), so values like \(\pm 32\) or more; softmax gives nearly all weight to the largest score. 6. Block 1: \(m = 3\), \(\ell = e^{-2} + 1 = 1.135\). Block 2: \(m_b = 5\), \(\ell_b = e^{-3} + 1 = 1.050\). Merge: \(m' = 5\), \(\ell = 1.135\,e^{-2} + 1.050 = 1.203\). Direct: \(e^{-4} + e^{-2} + e^{-3} + 1 = 1.203\). Same.

        Key takeaways

        • A vector is an arrow and a list of features. The dot product (2.4–2.5) measures length times alignment; cosine (2.6) measures alignment only.
        • Random dot products grow like \(\sqrt{d}\) (2.8); this is why attention divides by \(\sqrt{d_k}\).
        • A matrix transforms vectors: rows are detectors, columns are ingredients. A linear layer is \(W\mathbf{x} + \mathbf{b}\).
        • \((m\times k)(k\times n) \to (m\times n)\) costs about \(2mkn\) FLOPs (2.11). \(QK^\top\) computes all attention scores at once (2.12).
        • Softmax is shift-invariant (2.14), computed stably with the max trick and log-sum-exp (2.15). With cross-entropy its gradient is \(\mathbf{p} - \mathbf{y}\) (2.18). Online softmax (2.19) makes FlashAttention possible.

        Key formulas

        \[ \mathbf{a}\cdot\mathbf{b} = \sum_i a_i b_i = \lVert\mathbf{a}\rVert\lVert\mathbf{b}\rVert\cos\theta, \quad \operatorname{FLOPs}(AB) \approx 2mkn, \quad \frac{\partial \mathcal{L}}{\partial \mathbf{z}} = \mathbf{p} - \mathbf{y}, \quad O = \softmax\!\left(\tfrac{QK^\top}{\sqrt{d}} + M\right)V \]

        References for this session

        1. Stanford (2025). CS336: Language Modeling from Scratch (course)
        2. Karpathy (2023). Neural Networks: Zero to Hero (video course)
        3. Vaswani et al. (2017). Attention Is All You Need
        4. Milakov & Gimelshein (2018). Online normalizer calculation for softmax
        5. Dao et al. (2022). FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness