# Exercises with solutions — Linear attention and fixed-size matrix memory **General instruction:** every answer must show data, transformation, result, one check, and one limitation. A bare number or copied definition is insufficient. > **Starting data:** 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. > > **Boundary to retain:** Fixed memory means neither perfect memory nor infinite context: capacity and interference remain bounded. ## Exercise 1 — Calculated trace — Matrix foundations Reproduce and annotate the chain `q·k=Σqᵢkᵢ`. For write k=[1,0], replace v=[2,3] with v=[2.4,3]. Recompute S and then read with q=[1,0]. **Deliverable:** a data → operation → result → interpretation table, plus two sentences about the changed value.
Worked solution 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. **Solved variant:** S becomes [[2.4,3],[0,0]] and qᵀS reads [2.4,3]. Only the first coordinate of the written value changes; selection through k and q is unchanged. 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. 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. The minimum check covers dimensions, sign, and order of magnitude. If the observed change contradicts the prediction, locate the first operation whose direction changes instead of fixing only the final line.
### Rubric Exercise 1 — /10 | Criterion | Points | |---|---:| | Explicit data and shapes | 2 | | Traceable calculation | 3 | | Prediction before variation | 2 | | Interpretation and check | 2 | | Named limitation | 1 | ## Exercise 2 — Diagnose a seductive explanation — Outer product A colleague claims: « Outer product proves the system will be accurate, fast, and stable in every context. » 1. Separate mechanism, assumption, observation, and conclusion. 2. Name two correct lesson elements and two unsupported extrapolations. 3. Propose a bounded experiment with controlled variable, metric, and stop threshold. 4. Rewrite the claim as one defensible sentence.
Reasoned solution 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ᵀ. 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. Fixed memory means neither perfect memory nor infinite context: capacity and interference remain bounded. The claim mixes a local relation with a global guarantee. A defensible version states only the observed mechanism, test conditions, and measured metric. Stop the test if shapes become invalid, the metric crosses the declared degradation threshold, or another variable changes.
### Rubric Exercise 2 — /10 2 points per element: separation, lesson grounding, extrapolations, protocol, and rewrite. ## Exercise 3 — Architecture decision and transfer — Fixed memory You must reproduce the 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.” under two conditions. Option A uses the full chain through “Fixed memory.” Option B is a transparent baseline that retains “Matrix foundations,” calculates the expected output directly, and does not use the compression or adjustment mechanism studied. Build a decision record containing: - the workload and dominant constraint; - each option’s mechanism, without slogans; - one quality, memory, or latency prediction; - one case where your preferred procedure loses; - an A/B protocol, metrics, and rollback threshold; - a bounded verdict: choose, defer, or reject.
Elements of a strong solution 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. 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. Established mechanisms; numerical simplifications are pedagogical. A strong answer does not make the newer mechanism the default winner. It retains a measurable baseline, sets thresholds before testing, and separates component cost from whole-system behavior. The verdict names what remains uncertain and the next evidence that could change it.
### Rubric Exercise 3 — /15 | Criterion | Points | |---|---:| | Framing and baseline | 3 | | Compared causal chains | 4 | | Protocol and metrics | 4 | | Rollback threshold | 2 | | Bounded verdict | 2 | ## Extension Repeat Exercise 3 after reversing the dominant constraint. If you optimized memory, impose a strict quality floor; if you optimized fidelity, halve the memory budget. Identify the first part of the verdict that changes and the evidence required. ## Review before submission Review the packet as if another group had to reproduce it without speaking to you. Are all starting values or assumptions present? Are shapes or roles stated before operations? Does the prediction truly precede the observation? Is the result translated into behavior rather than left as an isolated number? Did you test a boundary value and identify a stop condition? Does the procedure or architecture choice retain a measurable baseline and a rollback threshold set before the test? Finally, highlight one sentence that states what is established, one that remains a hypothesis, and one measurement that could change your verdict. If any element is missing, the work is not reproducible. ## Reference appendix for correction # 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. ## Sources and evidence boundary - Owner-supplied bilingual course packet, Chapter 8. - Katharopoulos et al., “Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention”, ICML (2020). - Course source packet supplied by the owner; named-product details remain source-reported until primary verification. > **Scope:** Established mechanisms; numerical simplifications are pedagogical. These references support the session frame; they do not turn a reported product choice into an independently verified result.