Exercise 1: Why Doubling Context Length Quadruples Attention Cost — Possible Solution ==================================================================== WHAT llm1-4's OWN ATTENTION COMPUTATION ACTUALLY COMPUTES ------------------------------ Per this chapter, "Q @ K.T computes a similarity score between every pair of tokens." For a sequence of N tokens, this means computing one score for every possible pairing of a Query with a Key — and since every one of the N tokens has both a Query and a Key that must be compared against every other token's own Key, the total number of pairs to score is N multiplied by N, or N². WORKING THROUGH THE TABLE'S OWN NUMBERS ------------------------------ Per this chapter's own table, at N=1,000 tokens, the number of score pairs is 1,000 x 1,000 = 1,000,000. Doubling the sequence length to N=2,000 gives 2,000 x 2,000 = 4,000,000 — four times as many pairs, not two. At N=10,000 (ten times the original length), the count becomes 10,000 x 10,000 = 100,000,000 — one hundred times as many pairs, not ten. WHY DOUBLING LENGTH PRODUCES QUADRUPLED COST, NOT DOUBLED COST ------------------------------ Because the relationship is N², scaling N by some factor k scales the total score count by k². Doubling N means k=2, and k² = 4 — hence quadrupling, not doubling. This isn't a coincidence specific to the doubling case; it's the general behavior of any quadratic relationship: scaling the input by k always scales the output by k², which grows much faster than k itself once k is greater than 1. WHY THIS IS A REAL ARCHITECTURAL CONSTRAINT, NOT AN ARBITRARY LIMIT ------------------------------ Per this chapter's own finding-box, "this is why context windows historically grew slowly, and why any given amount of available compute and memory imposes a genuine, hard ceiling on sequence length." This cost isn't the result of a deliberate business or product decision to restrict context length — it falls directly out of the mathematical structure of scaled dot-product attention itself (llm1-4), specifically the fact that every token must be compared against every other token. No amount of clever engineering around this specific mechanism changes the underlying N² relationship for full, dense attention; it can only be reduced through fundamentally different attention mechanisms (this chapter's own brief mention of sparse/sliding-window approaches). WHY THIS EXPLAINS THE REAL, PRACTICAL COMPUTE/MEMORY CEILING ------------------------------ Since both the compute needed to calculate every score and the memory needed to store the resulting N x N matrix scale quadratically, there is a genuine, hard limit on how long a sequence can be processed given any fixed amount of available hardware — not a soft preference, but a mathematical consequence of the mechanism computing something for every single pair of tokens in the sequence. WHY THIS WORKS AS AN ANSWER ------------------------------ It walks through this chapter's own table to verify the N² relationship numerically, explains algebraically why scaling N by a factor k scales cost by k² (and specifically why doubling therefore quadruples), and connects this directly to why the resulting cost ceiling is a genuine structural property of self-attention rather than an arbitrary design choice.