0003 — Matrix Multiplication: The Engine of Attention

Linear Algebra Pillar · ~25 minutes

🧩 Puzzle Piece: The attention formula is softmax(Q·Kᵀ/√dₖ)·V. The first operation — Q·Kᵀ — is a matrix multiplication that computes every pairwise dot product between every query and every key, all at once. This is the computational heart of the transformer, and this lesson teaches you exactly how it works.

You know dot products measure similarity between two vectors. You know matrices transform vectors. Now: what if you had a matrix of queries and a matrix of keys, and you wanted to compute the similarity between every possible pair — all in one operation? That's Q·Kᵀ. One matrix multiplication, every pairwise comparison, done.

Matrix × Matrix: The Rules

To multiply A (m×n) by B (n×p), the result C (m×p) has entry C_ij = dot product of row i of A with column j of B:

C_ij = Σₖ A_ik · B_kj

The inner dimensions must match: (m×n) × (n×p) → (m×p). This is why K must be transposed — so its dimension matches Q's.

Q·Kᵀ: The Similarity Matrix

In attention, we have:

Q: matrix of query vectors (seq_len × d_k) — "what am I looking for?" for each position
K: matrix of key vectors (seq_len × d_k) — "what do I contain?" for each position

Q·Kᵀ has dimensions (seq_len × d_k) × (d_k × seq_len) = (seq_len × seq_len). Every entry (i,j) is the dot product between query i and key j:

(Q·Kᵀ)_ij = q_i · k_j = similarity between position i's query and position j's key

That's it. One matrix multiplication computes the similarity between every word and every other word in the input. For a 2048-token context, that's 4,194,304 pairwise comparisons — in one operation.

This is why transformers scale. The number of pairwise comparisons grows as seq_len², but matrix multiplication on GPUs is incredibly optimized. The bottleneck isn't the computation — it's the quadratic memory. This is why "context length" is a big deal: doubling context length quadruples the attention matrix.

Composition of Transformations

Matrix multiplication also represents composition. If B transforms vector space U→V, and A transforms V→W, then A·B transforms U→W directly:

(A·B)·x = A·(B·x)

Apply B first, then A. The product A·B is a single matrix that does both. This is why stacking transformer layers works: each layer is a composition of transformations.

The entire transformer is one giant composition of matrix multiplications. Input → Embedding → (Attention → FFN → Norm)^N → Output. Every arrow is a matrix multiplication (or a composition of them). The model is, mathematically speaking, a very elaborate function built entirely from matrix operations.

After Q·Kᵀ: What Comes Next (Preview)

The full attention formula: softmax(Q·Kᵀ/√dₖ)·V

Operation	What It Does	Lesson
Q·Kᵀ	Compute all pairwise similarities (matrix mult)	0003 (this one)
/√dₖ	Scale to prevent vanishing gradients	0013
softmax(·)	Convert similarities to probabilities (rows sum to 1)	0012
·V	Weighted average of value vectors by attention probabilities	0013

Each piece has a mathematical reason for being there. None of it is arbitrary. By the end of this course, you'll understand all of them.

Check Your Understanding

Q1: Q has shape (100 × 64) and K has shape (100 × 64). What is the shape of Q·Kᵀ?

A. (64 × 64) B. (100 × 100) C. (100 × 64) D. (64 × 100)

Q2: Entry (3, 7) of Q·Kᵀ represents what?

A. The similarity between key 3 and query 7 B. The similarity between query 3 and key 7 C. The similarity between query 3 and value 7 D. The 7th component of query 3

Q3 (Challenge): If context length doubles from 1024 to 2048, how does the size of the Q·Kᵀ matrix change?

A. It doubles (2×) B. It quadruples (4×) C. It stays the same D. It increases by 8×

📺 Primary Source Watch: Matrix multiplication as composition — 3Blue1Brown (Essence of Linear Algebra, Ch. 4)

📖 Recommended Reading Strang, Linear Algebra and Its Applications — Section 1.4 (Matrix Multiplication) and 1.5 (Transposes)

The Q·Kᵀ pattern is the single most important matrix multiplication in modern AI. If the dimensions aren't clicking, ask me to walk through a concrete example with 3 tokens and 4-dimensional vectors. Seeing it with small numbers makes the pattern obvious.

← 0002: Matrices as Transformations Next: 0004 — Vector Spaces & Embeddings →