A story in four parts. First, how attention works, with real numbers. Second, what it costs once the text gets long. Third, one tempting way out. Then back to the beginning: twelve years of fixes in launch order, each one solving a problem and creating the next.
A model reads text as tokens, roughly words. Each token is turned into a list of numbers, a vector, written x. Attention is how one token looks at the others and brings back what it needs. Below is the whole thing on five tokens with four numbers each, with real arithmetic at every step. Start at step 0 and work to the right. Click a word in any table to follow that word instead. The numbers are hand-made so that bank, which could mean money or a riverside, has a reason to look at river.
In the lab, 5 tokens made a 5 × 5 table. Now give the same mechanism a long document: 262,144 tokens, roughly 200,000 English words, a long novel. Follow the arithmetic for one real-sized model (32 layers, 32 heads of 128 numbers, 2 bytes per number).
Q is a list of N queries and Kᵀ a list of N keys, so Q·Kᵀ is an N × N table: one score for every pair.
N = 5 → 5 × 5 = 25 scores (the lab) N = 1,000 → 1,000 × 1,000 = 1,000,000 scores N = 262,144 → 262,144 × 262,144 = 68,719,476,736 scores (68.7 billion)
One score is stored in 2 bytes. A layer has 32 heads, each building its own N × N table.
68.7 billion scores × 2 bytes = 137 GB one head 137 GB × 32 heads = 4.40 TB one layer, one user one 80 GB GPU holds 80 GB → 4.40 TB is 55 GPUs’ worth
Honest limit: this is what a naive implementation would store. FlashAttention (2022, in the story below) computes the table in small pieces and never keeps it whole. But the 68.7 billion scores still have to be computed, per head, per layer.
When the model writes a reply, it keeps every earlier token’s key and value in every layer, so it does not recompute them for each new word.
one token = 2 (K and V) × 32 layers × 4,096 numbers × 2 bytes = 524 KB 262,144 tokens × 524 KB = 137 GB one user
Model weights are loaded once and shared. A cache belongs to one conversation, so it multiplies.
137 GB × 8 users = 1.10 TB
It was trained on texts of 4,096 tokens. At 262,144, only 4,096 ÷ 262,144 = 1.56% of the positions were ever seen in training.
Standard attention pays for length twice. The score work grows with N²: double the text, four times the work. The KV cache grows with N × users: double either, twice the memory. At 262,144 tokens, one user’s cache alone (137 GB) does not fit on an 80 GB GPU. Everything after this point is an attempt to shrink one of these bills.
Look at the order of the multiplication. Softmax wraps Q·Kᵀ, so the N × N table has to be built before V is touched. Remove softmax and matrix multiplication lets the brackets move.
Q · Kᵀ = [N × 128] · [128 × N] = [N × N]
Grows with N². Per user, the model keeps of KV cache, and it grows with every token.
Kᵀ · V = [128 × N] · [N × 128] = [128 × 128]
N has vanished from the shape. Per user, the model keeps a fixed of state (32 layers × 32 heads × 128 × 128 × 2 bytes), at 10 tokens or 10 million.
This idea is from 2020. It took a delta rule (2021), a way to train it in parallel (2024) and a forget gate (late 2024) before it could stand beside softmax, and even then only mixed with it. Meanwhile others attacked the same bills in completely different ways. Let’s start from the beginning.
Each entry answers the same questions: what was there before, what problem people hit, what fixed it, and what new problem the fix created. Ordered by first public release (arXiv v1 date, or the post date when there is no paper). Entries marked added were not on the class list. Highlight one concern to follow its thread.
The whole story on one chart. Each dot is one entry, placed by launch date and coloured by the cost it attacks; a ring marks a secondary concern. Read left to right: exact attention first, then decoding memory and position, then longer contexts, then recurrent state, sparsity and compression returning together. Click a dot to jump back to its entry.
None of these is good or bad in isolation. An architecture has a workload. The same mechanism can be right for a 2K chatbot and wrong for a 1M-token agent.
| Workload | Reasonable choice | Why |
|---|
Dates are where confident sentences go wrong. These are the places where the usual story, the class notes, or the assignment's list disagreed with the primary source.
Each date was checked against the source listed with it: the arXiv v1 submission date, the original post, or the release announcement. Numbers quoted from papers are the authors' own claims and were not reproduced here.