Chapter 41: Scaled Dot-Product Attention Mathematics

Chapter 41: Scaled Dot-Product Attention Mathematics

AI Reading

Quick summary of this article

Preparing the AI summary…

AI Mathematics Masterclass — Chapter 41 of 48

Attention is a soft dictionary lookup: a query is compared against every key, the comparison scores are normalised into weights, and the output is the weighted average of the values. This chapter derives each step, shows why the scaling factor is √d and not something else, and explains the causal mask as an additive −∞ before the softmax.

1. Technical Audit & Core Learning Objectives

Component Common Tutorial Deficiency Engineering Standard Applied Here
Formula Quoted without derivation. Built step by step and verified numerically.
The √d factor Called “for stability” and left there. Variance of the dot product computed as d.
Masking Shown as a triangle, never as arithmetic. Implemented as an additive −∞ and checked.
Cost Only n² mentioned. Memory and bandwidth distinguished from FLOPs.

Core learning objectives. After this chapter you should be able to:

  1. Write the attention formula and explain each factor.
  2. Derive why the dot product grows like √d.
  3. Explain what happens to softmax gradients when the scaling is removed.
  4. Implement causal masking as additive −∞.
  5. Verify row-stochasticity of the attention matrix.
  6. State the time and memory complexity of attention.

2. The Four Steps

Input tokens projected to Q, K and V, scored, softmaxed, and combined into an output
Figure 41.1: Query asks, keys advertise, values answer.
Q = X W_Q      (n, d_k)
K = X W_K      (n, d_k)
V = X W_V      (n, d_v)

S = Q K^T / sqrt(d_k)        (n, n)   scores
A = softmax(S, dim=-1)       (n, n)   weights, rows sum to 1
O = A V                      (n, d_v) output

Row i of A says how much of each value token i copies.
Row i of O is therefore a convex combination of the values.
import numpy as np

rng = np.random.default_rng(0)

def attention(X, Wq, Wk, Wv, mask=None):
    Q, K, V = X @ Wq, X @ Wk, X @ Wv
    S = Q @ K.T / np.sqrt(Q.shape[1])
    if mask is not None:
        S = S + mask
    S = S - S.max(axis=-1, keepdims=True)
    A = np.exp(S)
    A = A / A.sum(axis=-1, keepdims=True)
    return A, A @ V

n, d, dk = 5, 6, 4
X = rng.normal(size=(n, d))
Wq, Wk, Wv = rng.normal(size=(d, dk)), rng.normal(size=(d, dk)), rng.normal(size=(d, dk))

A, O = attention(X, Wq, Wk, Wv)
print("A shape", A.shape, " O shape", O.shape)
print("row sums:", np.round(A.sum(axis=1), 12))
print("\nA[0]:", np.round(A[0], 4))
print("O[0] is a convex combination of V rows:", np.isclose(O[0].sum(), (A[0] @ (X @ Wv)).sum()))

V = X @ Wv
manual = sum(A[0, j] * V[j] for j in range(n))
print("matches the weighted sum by hand:", np.allclose(manual, O[0]))

Every row of the output is a convex combination of value rows — no value can be extrapolated beyond, only blended. That is why attention is called a lookup and not a transformation.

3. Why Divide by √d

Softmax response curves showing the unscaled version saturating far earlier than the scaled one
Figure 41.2: Scaling keeps the softmax out of its saturated region.
Let q and k have independent entries with mean 0 and variance 1.
Then q . k = sum of d terms, each with variance 1.

Var(q . k) = d      sd(q . k) = sqrt(d)

So the logits spread like sqrt(d). Divide by sqrt(d) and the
spread is O(1) again, independent of width.

Without it, d = 64 gives logits with sd 8. Softmax over values
that far apart is effectively one-hot, and its Jacobian is
essentially zero — attention stops learning.
import numpy as np

rng = np.random.default_rng(1)

print(f"{'d':>5}{'sd(q.k)':>12}{'sd(q.k/sqrt(d))':>20}")
for d in (4, 16, 64, 256):
    dots = []
    for _ in range(4000):
        q, k = rng.normal(size=d), rng.normal(size=d)
        dots.append(q @ k)
    dots = np.array(dots)
    print(f"{d:5d}{dots.std():12.3f}{dots.std()/np.sqrt(d):20.3f}")

# the effect on softmax sharpness
def softmax(z):
    e = np.exp(z - z.max()); return e / e.sum()

d = 64
q, K = rng.normal(size=d), rng.normal(size=(8, d))
raw = softmax(K @ q)
scaled = softmax(K @ q / np.sqrt(d))
print("\nunscaled max weight:", f"{raw.max():.6f}", " entropy:", f"{-(raw*np.log(raw)).sum():.4f}")
print("scaled   max weight:", f"{scaled.max():.6f}", " entropy:", f"{-(scaled*np.log(scaled)).sum():.4f}")

The unscaled softmax collapses onto a single key. That is not merely a numerical worry — a one-hot distribution has a near-zero Jacobian, so the gradient with respect to the queries and keys disappears along with the useful signal.

4. Causal Masking

A lower-triangular mask matrix with minus infinity above the diagonal
Figure 41.3: The mask is added before the softmax, so blocked positions get exactly zero weight.
mask[i, j] = 0        if j <= i      (allowed)
mask[i, j] = -inf     if j >  i      (blocked)

S = Q K^T / sqrt(d) + mask
exp(-inf) = 0, so blocked positions contribute nothing at all.

Two practical details:
 1. Add the mask BEFORE the max-subtraction, or -inf interactions
    with the row max can produce NaN.
 2. Use a large negative constant only if your framework cannot
    represent -inf; exactly zero weight is what you want.
import numpy as np

def causal_attention(X, Wq, Wk, Wv):
    n = X.shape[0]
    Q, K, V = X @ Wq, X @ Wk, X @ Wv
    S = Q @ K.T / np.sqrt(Q.shape[1])
    mask = np.triu(np.full((n, n), -np.inf), k=1)
    S = S + mask
    if not np.all(np.isfinite(S.max(axis=1))):
        raise ValueError("a row is fully masked")
    S = S - S.max(axis=1, keepdims=True)
    A = np.exp(S); A /= A.sum(axis=1, keepdims=True)
    return A, A @ V

rng = np.random.default_rng(2)
n, d = 6, 4
X = rng.normal(size=(n, d))
Wq, Wk, Wv = rng.normal(size=(d, d)), rng.normal(size=(d, d)), rng.normal(size=(d, d))

A, O = causal_attention(X, Wq, Wk, Wv)
np.set_printoptions(precision=3, suppress=True)
print(A)
print("\nupper triangle is exactly zero:", np.all(A[np.triu_indices(n, 1)] == 0.0))
print("row sums:", A.sum(axis=1))

If a row were fully masked, its softmax denominator would be zero and the result NaN. That is why a causal mask always keeps the diagonal — every token is allowed to attend to itself.

5. Reading the Attention Matrix

A heatmap of attention weights with some rows diffuse and others sharply peaked
Figure 41.4: Every row spends exactly one unit of attention; peaked rows have locked on.
A diffuse row  -> the model averages many tokens
A peaked row   -> the model has selected specific tokens

Entropy of a row is a direct measure of this:

  H_i = -sum_j A[i,j] log A[i,j]

uniform row -> H = log n   (maximum uncertainty)
one-hot row -> H = 0       (complete certainty)
import numpy as np

def row_entropy(A):
    A = np.asarray(A)
    return -(A * np.log(np.where(A > 0, A, 1))).sum(axis=1)

uniform = np.full((1, 8), 1 / 8)
onehot = np.zeros((1, 8)); onehot[0, 3] = 1.0
mixed = np.array([[0.5, 0.2, 0.1, 0.1, 0.05, 0.05, 0.0, 0.0]])

print("uniform entropy:", round(float(row_entropy(uniform)[0]), 4), "= log 8 =", round(np.log(8), 4))
print("one-hot entropy:", round(float(row_entropy(onehot)[0]), 6))
print("mixed   entropy:", round(float(row_entropy(mixed)[0]), 4))

# entropy is maximised by the uniform distribution
rng = np.random.default_rng(0)
samples = []
for _ in range(500):
    z = rng.normal(size=8)
    row = np.exp(z) / np.exp(z).sum()
    samples.append(row_entropy(row[None, :])[0])
print("\nmax entropy over 500 random rows:", round(max(samples), 4), "<= log 8 =", round(np.log(8), 4))
print("bound holds:", max(samples) <= np.log(8) + 1e-12)

Row entropy is the most useful single diagnostic on a trained model: near-uniform rows everywhere usually mean the attention is not doing anything and the model is relying on the residual path instead.

6. Cost and the FlashAttention Correction

Vectors at different angles on a circle illustrating that the dot product rewards alignment
Figure 41.5: The dot product rewards both alignment and magnitude.
Time:   O(n^2 d)  for QK^T and for AV
Memory: O(n^2)    for the score matrix, per head, per layer

The n^2 memory term is the one that actually hurts: an 8k
sequence with 32 heads and 32 layers means 8k^2 * 32 * 32
floats, which is far beyond any single accelerator.

FlashAttention does not change the O(n^2) arithmetic. It
fuses the operations and tiles them so the n^2 matrix is never
materialised in high-bandwidth memory. The FLOP count is
identical; the memory traffic is not.
import numpy as np

for n in (1024, 4096, 16384, 131072):
    per_head = n * n * 4          # float32
    total = per_head * 32 * 32    # 32 heads, 32 layers
    print(f"n={n:7d}  one head {per_head/1e6:10.1f} MB   full stack {total/1e9:10.2f} GB")

print()
print("This is why attention kernels are tiled:")
print("the score matrix is streamed, not stored.")

At 128k tokens the hypothetical full-stack score tensor is about 70 terabytes. No algorithm can materialise that, which is precisely why tiled and recomputed attention became standard rather than optional.

7. Worked Examples

7.1 Self versus cross attention

Self attention:  Q, K, V all from the same tensor
Cross attention: Q from the decoder, K and V from the encoder

7.2 Shapes

(n, d_k) @ (d_k, n) -> (n, n)
(n, n) @ (n, d_v)   -> (n, d_v)
d_k controls the score scale, d_v controls the output width.

7.3 Why softmax over the last axis

Softmax over the wrong axis normalises across queries instead of
across keys, which destroys the row-stochastic property.

7.4 Attention is not explainability

A large weight means a value was copied, not that a decision
was caused. Attention maps are a useful signal, not a proof.

7.5 Padding masks

Combine a padding mask with the causal mask by adding the two
matrices of 0 and -inf. They compose because addition is
the same as logical AND on the allowed set.

8. Verify It in Python

import numpy as np

rng = np.random.default_rng(0)

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

# --- 1. dot-product variance grows like d ---------------------
for d in (4, 64):
    dots = np.array([rng.normal(size=d) @ rng.normal(size=d) for _ in range(3000)])
    assert abs(dots.std() - np.sqrt(d)) < 0.15 * np.sqrt(d)
print("sd(q.k) tracks sqrt(d) for d=4 and d=64")

# --- 2. scaling keeps the spread bounded ----------------------
spreads = []
for d in (4, 16, 64, 256):
    dots = np.array([rng.normal(size=d) @ rng.normal(size=d) for _ in range(2000)])
    spreads.append(dots.std() / np.sqrt(d))
assert max(spreads) - min(spreads) < 0.15
print("scaled spread is flat in d:", [round(s, 3) for s in spreads])

# --- 3. attention rows are stochastic ------------------------
n, d, dk = 7, 5, 4
X = rng.normal(size=(n, d))
Wq, Wk, Wv = rng.normal(size=(d, dk)), rng.normal(size=(d, dk)), rng.normal(size=(d, dk))
Q, K, V = X @ Wq, X @ Wk, X @ Wv
A = softmax(Q @ K.T / np.sqrt(dk))
assert np.allclose(A.sum(axis=1), 1.0)
assert np.all(A >= 0)
print("attention rows sum to 1 and are non-negative")

# --- 4. output is a convex combination ------------------------
O = A @ V
for i in range(n):
    assert np.allclose(O[i], sum(A[i, j] * V[j] for j in range(n)))
assert O.min() >= V.min() - 1e-12 and O.max() <= V.max() + 1e-12
print("each output row lies inside the range of the value rows")

# --- 5. causal mask zeroes the strict upper triangle ----------
mask = np.triu(np.full((n, n), -np.inf), k=1)
Ac = softmax(Q @ K.T / np.sqrt(dk) + mask)
assert np.all(Ac[np.triu_indices(n, 1)] == 0.0)
assert np.allclose(Ac.sum(axis=1), 1.0)
assert np.all(np.diag(Ac) > 0)
print("causal mask: upper triangle exactly 0, diagonal positive")

# --- 6. a fully masked row really does produce NaN ------------
bad = np.full((1, 3), -np.inf)          # every key blocked
sub = bad - bad.max(axis=1, keepdims=True)   # -inf - (-inf) = nan
assert np.all(np.isnan(sub))
print("a fully masked row yields NaN after max-subtraction — as warned")

# --- 7. row entropy bounds -----------------------------------
def row_entropy(Arow):
    p = Arow[Arow > 0]
    return float(-(p * np.log(p)).sum())

assert np.isclose(row_entropy(np.full(8, 1/8)), np.log(8))
assert row_entropy(np.eye(8)[3]) == 0.0
assert row_entropy(A[0]) <= np.log(n) + 1e-12
print("entropy: uniform = log n, one-hot = 0")

# --- 8. softmax is shift invariant ---------------------------
S = Q @ K.T / np.sqrt(dk)
assert np.allclose(softmax(S), softmax(S + 100.0))
print("softmax shift invariance holds (mask-safe)")

# --- 9. cost arithmetic --------------------------------------
for n_tokens in (8192, 16384):
    bytes_needed = n_tokens ** 2 * 4 * 32 * 32
    print(f"n={n_tokens}: full-stack score tensor = {bytes_needed/1e12:.2f} TB")
assert 16384 ** 2 * 4 * 32 * 32 > 1e12
print("all assertions passed")

9. Practice Questions

  1. Write the attention formula and name each matrix.
  2. Show that Var(q·k) = d for unit-variance inputs.
  3. Why does removing the √d scaling damage the gradient?
  4. Why must a causal mask keep the diagonal unmasked?
  5. Implement a mask as additive −∞ and explain why it works.
  6. Compute the entropy of a uniform attention row over 16 keys.
  7. Distinguish self attention from cross attention.
  8. What happens if you softmax over the wrong axis?
  9. State the time and memory complexity of attention.
  10. Explain what FlashAttention changes and what it does not.

Leave a Reply

Your email address will not be published. Required fields are marked *