1. Matrix foundations
The problem: You are about to manipulate memories made of vectors and matrices. A shape error — multiplying a length-3 vector by a 2×2 matrix — does not produce a wrong result: it produces nonsense. And with NumPy broadcasting, some wrong shapes still execute and silently corrupt everything downstream.
The idea: A vector is an ordered list of d numbers; a matrix organizes rows and columns (d_k × d_v). Dimensions dictate which multiplications are valid: here k(2) and v(2) build S(2×2), and a length-3 key [1;0;2] is rejected before any computation.
Why / at what price: The shape check costs one line and runs before the computation: it turns silent corruption into an immediate refusal. The price of skipping it: sessions 14 to 18 stack these objects — an early wrong shape becomes untraceable there.
Understanding check
Name the input, transformed state, output, and one required assumption. Then compare your chain with the explanation above.
2. Dot product
The problem: A memory needs addresses: which write should a query pair with? Eyeballing vectors gives no usable number, and without a quantified alignment measure every read would have to re-read everything.
The idea: The dot product compresses alignment into one number: q·k = Σqᵢkᵢ. Here q=[1,0] against k=[1,0] gives 1 (aligned); against k=[0,1] it gives 0 (orthogonal). That is the addressing mechanism: strong = relevant, zero = ignored.
q·k=Σqᵢkᵢ
Why / at what price: Why it works: the orthogonality zero isolates addresses — without it, every query would read every write. The price: alignment is continuous; two nearby keys (q·k = 0.9) partially share an address, and that sharing becomes the final beat’s interference.
Understanding check
Name the input, transformed state, output, and one required assumption. Then compare your chain with the explanation above.
3. Outer product
The problem: The dot product compares, but writes nothing. How do you file the value v=[2,3] “at the address” k=[1,0] inside a fixed-size structure — so that the right query finds it later?
The idea: The outer product k vᵀ builds a matrix: the row is selected by k, the content is carried by v. For k=[1,0] and v=[2,3]: k vᵀ = [[2,3],[0,0]] — the value is filed on row 1, row 2 stays blank. Writes accumulate: S ← S + k vᵀ.
S←S+k vᵀ
Why / at what price: An associative write in one O(1) operation, local to k’s direction: this is what makes fixed state possible. The price: the addition is blind — it never checks whether the address is already occupied. Writing twice on k=[1,0] adds the values instead of replacing them.
Understanding check
Name the input, transformed state, output, and one required assumption. Then compare your chain with the explanation above.
4. Reading state
The problem: The memory now holds several writes superposed in a single matrix. How does a query recover THE value that concerns it without scanning a list — since there is no list at all any more?
The idea: Reading is a multiplication: y = qᵀS. Query q=[1,0] selects row 1 and reads [2,3] exactly; q=[0,1] reads [5,1]. Nothing is scanned: one operation, however long the past.
y=qᵀS
Why / at what price: An O(1) read versus O(n) for the KV cache: the gain is structural. The price: y is always a combination of everything written, weighted by q·k. It is exact only when keys are orthogonal — the read cannot tell “stored value” from “blend”.
Understanding check
Name the input, transformed state, output, and one required assumption. Then compare your chain with the explanation above.
5. Fixed memory
The problem: A KV cache at 100,000 tokens blows up a service’s memory bill — and it grows again at the next token. Can you serve a long context with a memory whose size does not depend on length?
The idea: S measures d_k × d_v, full stop: 1,000 or 100,000 tokens written, the matrix keeps the same size. The cache’s O(n) growth becomes a constant — at the price of a superposed summary instead of an exact trace.
Why / at what price: The memory budget becomes predictable — exactly what gets billed in production. The price: information capacity is constant too; beyond roughly d_k distinct key directions, writes superpose. “Fixed size” also means “fixed capacity”, never infinite context.
Understanding check
Name the input, transformed state, output, and one required assumption. Then compare your chain with the explanation above.
6. Interference
The problem: Third write: k=[1,0] reused with v=[9,9]. The read q=[1,0] returns [11,12] — neither the old value nor the new one. Who overwrote what? Nobody: both writes coexist, merged. What do you do with a memory that can no longer discriminate?
The idea: Interference is arithmetic, not random: row 1 of S holds [2,3] + [9,9] = [11,12], and the read returns exactly that sum. Nearby keys write into shared directions; their values blend in proportion to alignment.
Why / at what price: Seeing it as a sum makes it predictable and measurable — a controlled recall test is enough to detect it. The price remains: without correction or forgetting, an additive memory drifts with length. That is exactly the problem session 14’s delta rule attacks.
Understanding check
Name the input, transformed state, output, and one required assumption. Then compare your chain with the explanation above.
Development from the course source
Chapter 8 — Linear attention and fixed-size matrix memory
8.0 Matrix foundations from zero
Goal: understand the small pieces of mathematics used from this chapter onward. A scalar is one number, such as 3. A vector is an ordered list, such as [2, 5]. A matrix is a rectangular grid of numbers. Its shape is written rows × columns.
Intuition: Think of a vector as one student’s report card and a matrix as the whole class register. Rows can represent students; columns can represent subjects.
Step by step
-
A = [[1, 2, 3], [4, 5, 6]] has 2 rows and 3 columns, so its shape is 2 × 3.
-
The transpose swaps rows and columns: transpose([2, 5]) turns a row into a column.
-
A dot product multiplies matching entries and adds them: [2, 3] · [4, 5] = 2×4 + 3×5 = 23.
-
An outer product makes a grid: column [2, 3] × row [4, 5] = [[8, 10], [12, 15]].
-
Matrix multiplication is repeated dot products. Shapes must connect: (2 × 3)(3 × 4) gives (2 × 4).
Worked example: x = [2, 1] and W = [[3, 0], [4, 5]]. Then xW = [2×3 + 1×4, 2×0 + 1×5] = [10, 5]. The matrix mixed the two input coordinates into two new coordinates.
Why it matters: These operations are the grammar of neural networks. We will always state what a matrix stores and check its shape.
Quick check: What is the shape of a grid with 4 rows and 7 columns? Answer: 4 × 7.
8.1 From a growing notebook to a fixed-size summary
Goal: see why ordinary attention becomes expensive. Exact causal attention keeps a key and value for every earlier token. During generation, the key-value cache therefore grows with the conversation.
Intuition: Exact attention is like keeping every receipt. Linear attention tries to maintain one running accounting table instead.
Step by step
-
Transform each key k with a feature map φ(k). A feature map simply changes coordinates before comparison.
-
Write the key-value association into a state matrix S using an outer product: S ← S + φ(k) vᵀ.
-
Read with a query q: output ≈ φ(q)ᵀS. A normalization term may also be used.
-
The dimensions of S depend on representation width, not on the number of tokens.
Worked example: start with S = [[0,0],[0,0]]. Let k = [1,0] and v = [3,4]. The outer product is [[3,4],[0,0]], so the new S is [[3,4],[0,0]]. Query q = [1,0] reads qᵀS = [3,4]. Query [0,1] reads [0,0].
Why it matters: The memory remains the same size even after many tokens. This can reduce memory growth and make recurrent decoding efficient.
Quick check: Does fixed-size memory mean unlimited perfect memory? Answer: No. Many associations must share the same limited grid.
8.2 Interference
Goal: understand the main weakness of simple additive memory. If two keys point in similar directions, their writes overlap inside S. A later query may retrieve a mixture.
Intuition: Imagine writing several answers in the same small square of a whiteboard. The ink overlaps.
Step by step
-
Write k₁ = [1,0], v₁ = [1,0].
-
Write k₂ = [1,1], v₂ = [0,1].
-
The state becomes [[1,1],[0,1]].
-
Reading with q = [1,0] returns [1,1], not the original [1,0]. The second write leaked into the first read.
Worked example: This toy example shows cross-talk. Real models use learned projections, gates, normalization and correction rules, but finite memory still creates trade-offs.
Why it matters: We need a write rule that can correct what a key currently remembers instead of only adding forever.
Quick check: Why can two memories interfere? Answer: Their key directions are not perfectly separate, so their matrix writes overlap.
Complete worked case
With zero S, k=[1,0] and v=[2,3], the write gives [[2,3],[0,0]]. Query q=[1,0] reads [2,3]. Trying to add a length-3 key [1,0,2] also reveals why shape checks are mandatory.
Reading method: write the data, state every object shape, perform one transformation, and interpret the result before continuing.