Long-context architectures: Visual walkthrough

The parent note dropped one line that quietly does all the heavy lifting for long-context models — a way to make ordinary attention run in linear time. But that line is written in symbols we have not earned yet.

So this page builds it from absolute zero. We will not even show that formula until every letter in it has been drawn. By the end you will see why ordinary attention costs $O (n^{2})$ , and why one act of re-bracketing collapses it to $O (n)$ . No symbol is used before it is defined and pictured.

Step 0 — What are these letters even?

Think of a party. Every guest holds up a sign (a key) saying what they know. You walk in with a question (a query). You compare your question to every sign, decide who is worth listening to, and collect a weighted blend of what they actually say (their values). Attention is that "compare, weight, blend."

Figure s01 below is that party: the coral box on the left is your query, the mint boxes are the keys (signs), and the butter box on the right holds the values (facts). The lavender arrows are the comparisons — one per key.

The dot product $q_{i}^{T} k_{j}$ appears because it is the simplest number that grows when two vectors point the same way — it is our "how well does this sign match my question?" meter. Big dot product = strong match.

Step 1 — Draw the full attention table (the $O (n^{2})$ we want to kill)

WHY it hurts: the grid has $n$ rows and $n$ columns, so it has $n \times n = n^{2}$ cells. At $n = 100, 000$ tokens that is 10 billion cells — the exact wall the parent note describes. See why $O(n^2)$ is unaffordable.

PICTURE: Figure s02 draws that grid. Read the axes: keys run left-to-right, queries run bottom-to-top. The coral diagonal is "token compared with itself"; every lavender cell is a genuine dot product we must pay for. The whole point of this page is to never build this grid.

Step 2 — The softmax is the glue we must dissolve

Term by term: $e^{q_{i}^{T} k_{j}}$ exponentiates a match so a slightly-better key wins by a lot (it exaggerates differences). The denominator adds up the whole row so the weights become fractions.

WHY this is the villain: the exponential $e^{q_{i}^{T} k_{j}}$ locks $q_{i}$ and $k_{j}$ together inside one function. You cannot separate them, so you are forced to visit every $(i, j)$ pair. That coupling is the whole reason we are stuck at $n^{2}$ .

PICTURE: Figure s03 shows one row of the grid. Left (lavender bars): the raw scores. Right (mint bars): after softmax — the tallest raw score has been pushed up into a dominant weight while the rest shrink, and all bars now sum to 1. The coral note points at why: the exponential exaggerates the winner.

The output for token $i$ is the weighted blend of values: $out_{i} = \sum_{j} w_{ij} v_{j} .$

Step 3 — Replace the exponential with a product we CAN pull apart

This is a kernel trick: rewrite a similarity between two things as a dot product of transformed versions of each thing separately.

Definition Does such a

$ϕ$ actually exist? (the honest answer) Two levels of guarantee:

Exact-in-the-limit (Random Features). There is a classic construction — random Fourier / "positive random features" — where $ϕ (x)$ is built from $m$ random projections of $x$ . It satisfies $E [ϕ (q)^{T} ϕ (k)] = e^{q^{T} k}$ exactly on average, and the approximation error shrinks like $O (1/ m)$ as you add features. So bigger $d_{ϕ}$ ⇒ tighter fit. (This is the Performer's FAVOR+ scheme.)
Cheap-and-good-enough. In practice people also use a plain positive map like $ϕ (x) = elu (x) + 1$ . It does not reproduce $e^{q^{T} k}$ ; it just gives some positive separable similarity that trains well. This is the Linear Transformer choice.

Takeaway: $ϕ$ is not magic — either it provably approximates the exponential with controllable error, or it is a deliberately simpler positive kernel. Both keep the property we actually need: separability.

WHY exactly $ϕ$ and not something else? Because we want to break the $q$ – $k$ marriage. The exponential glues them; a dot product of two separate maps $ϕ (q)^{T} ϕ (k)$ lets each side be computed alone first. Separation is the entire game.

PICTURE: Figure s04 shows the swap. The coral box is the glued exponential (q and k trapped together). The mint and butter boxes are $ϕ (q)$ and $ϕ (k)$ built in isolation, later dotted — the lavender caption calls out "separable!".

Now rewrite the whole attention with $ϕ$ in place of $exp$ : $out_{i} = \frac{\sum _{j} ( ϕ ( q _{i} ) ^{T} ϕ ( k _{j} ) ) v _{j}}{\sum _{j} ϕ ( q _{i} ) ^{T} ϕ ( k _{j} )} .$ Every symbol here is defined: $ϕ (q_{i}), ϕ (k_{j})$ are transformed column vectors, $v_{j}$ is the value column, the sums run over all keys $j$ .

Step 4 — The magic re-bracketing (associativity)

Watch the parentheses move (recall from the convention box that $ϕ (k_{j}) v_{j}^{T}$ is an outer product — a column times a row makes a matrix):

\;=\; \phi(q_i)^T \underbrace{\Big(\sum_j \phi(k_j)\, v_j^T\Big)}_{\text{call this }S}$$ > [!formula] The two precomputed summaries > $$S \;=\; \sum_j \underbrace{\phi(k_j)}_{d_\phi\text{-column}}\, \underbrace{v_j^T}_{d_v\text{-row}} > \quad(\text{a }d_\phi\times d_v\text{ table}), \qquad > Z \;=\; \sum_j \phi(k_j)\quad(\text{a }d_\phi\text{-column})$$ > $d_v$ is the length of a value vector; each term $\phi(k_j)v_j^T$ is the outer product from the convention box. **WHY this is legal:** multiplication by a constant distributes over a sum — the same rule that lets you compute $a\cdot b + a\cdot c = a(b+c)$. Here the "constant" (w.r.t. $j$) is $\phi(q_i)$. **WHY it wins:** $S$ and $Z$ are built **once**, scanning the keys a single time. They are the party's *entire crowd compressed into one summary card*. After that, each query just reads the card. **PICTURE:** **Figure s05** shows the parentheses sliding: the equation on top, then the mint "key-value card" $S$ and the butter "count card" $Z$, with a coral note that both are built once. ![[deepdives/dd-ai-ml-6.1.10-d2-s05.png]] --- ## Step 5 — Count the cost and watch $n^2$ vanish > [!intuition] WHAT > Final formula, fully separated: > $$\boxed{\;\text{out}_i \;=\; \frac{\phi(q_i)^T\, S}{\phi(q_i)^T\, Z}\;}$$ Cost audit, term by term — **and this time we count the feature maps too**: 1. Compute $\phi(k_j)$ for all keys and $\phi(q_i)$ for all queries: $n$ tokens each, cost of one $\phi$ call is $O(c_\phi)$ (for elu it is $O(d_\phi)$; for random features $O(d\, d_\phi)$). Total $O(n\, c_\phi)$. 2. Build $S$: touch each key once, adding a $d_\phi\times d_v$ outer product → $O(n\, d_\phi d_v)$. 3. Build $Z$: touch each key once → $O(n\, d_\phi)$. 4. Each query reads $S,Z$ → $O(d_\phi d_v)$, **with no $n$ in it**. Across $n$ queries: $O(n\, d_\phi d_v)$. **Total: $O\big(n\,(c_\phi + d_\phi d_v)\big)$ — still linear in $n$**, because every one of those costs is a fixed per-token amount multiplied by $n$. The $n^2$ grid of Step 1 is gone; we never form it. **PICTURE:** **Figure s06** plots work against $n$: the coral $O(n^2)$ curve rockets up, the mint linear curve stays low. The arrow marks where full attention "explodes". ![[deepdives/dd-ai-ml-6.1.10-d2-s06.png]] > [!example] The parent note's numbers, verified > Tokens $=4$, $\phi(x)=[1,x_1,x_2]^T$ so $d_\phi=3$, scalar values ($d_v=1$). > Keys $\phi$: $[1,1,0]^T,[1,0,1]^T,[1,1,1]^T,[1,0,0]^T$; values $1,2,3,4$. > $$S = 1[1,1,0]^T+2[1,0,1]^T+3[1,1,1]^T+4[1,0,0]^T = [10,4,5]^T$$ > $$Z = [1,1,0]^T+[1,0,1]^T+[1,1,1]^T+[1,0,0]^T = [4,2,2]^T$$ > Query $q_1=[1,0]^T\Rightarrow \phi(q_1)=[1,1,0]^T$: > $$\text{num}=[1,1,0]\,[10,4,5]^T=14,\quad \text{den}=[1,1,0]\,[4,2,2]^T=6,\quad \text{out}_1=\tfrac{14}{6}\approx 2.33$$ --- ## Step 6 — The degenerate cases (never leave the reader stranded) Every derivation must survive its edge inputs. Here are the ones that bite. **Figure s07** collects all four as labelled cards. **Case A — the denominator hits zero.** If $\phi(q_i)^T Z = 0$, the blend is undefined (dividing by nobody). This is why real linear attention forces $\phi(x)>0$ elementwise (e.g. $\phi(x)=\text{elu}(x)+1$): with all-positive features and non-empty keys, $Z$ has positive entries and the denominator can't vanish. **Case B — one token ($n=1$).** Then $S=\phi(k_1)v_1^T$ and $Z=\phi(k_1)$, so $$\text{out}_1=\frac{\phi(q_1)^T\phi(k_1)\,v_1}{\phi(q_1)^T\phi(k_1)}=v_1.$$ A lone token attends only to itself — exactly what full attention gives. The two methods agree in the limit. ✓ **Case C — causal / left-to-right generation.** Token $i$ may only see keys $j\le i$. Then $S$ and $Z$ become **running sums**: $S_i=S_{i-1}+\phi(k_i)v_i^T$. This is precisely a [[Recurrent Neural Networks|recurrent]] hidden state carried forward — linear attention *is* an RNN in disguise, and it inherits the RNN worry that a fixed-size $S$ can only remember so much (an [[Information Bottleneck|information bottleneck]]). **Case D — the approximation is imperfect.** $\phi(q)^T\phi(k)$ only *approximates* $e^{q^T k}$ (with error $O(1/\sqrt{m})$ for $m$ random features, or no guarantee at all for the cheap elu map). Sharp, spiky attention (one key dominating hugely) is what exponentials do best and low-dimensional $\phi$ does worst. That is the quality price for the speed — and why [[Retrieval-Augmented Generation|retrieval]] or sparse hybrids are sometimes bolted on. ![[deepdives/dd-ai-ml-6.1.10-d2-s07.png]] --- ## The one-picture summary **Figure s08** compresses the whole derivation: keys+values on the left get scanned **once** into the cards $S,Z$ (butter); a query (coral) arrives and reads those cards through the boxed formula (lavender) in constant time — total cost linear in $n$, no $n\times n$ grid ever built. ![[deepdives/dd-ai-ml-6.1.10-d2-s08.png]] > [!recall]- Feynman retelling — say it to a 12-year-old > Imagine 100,000 people in a hall, each holding a sign (key) and knowing a fact (value). The slow way: for every question you ask, you walk past all 100,000 signs — that's a question × people grid, and it explodes. > > The clever way: first walk the hall **once** and mash everyone's sign-and-fact into a single summary card $S$ (and a "how many total" card $Z$). Now when anyone asks a question, they just glance at the two cards — no more walking the hall. The trick that makes this legal is that the exponential match-meter is replaced by a *separable* meter $\phi(q)^T\phi(k)$, so each person's contribution can be baked into the card **before** any question arrives. Cost goes from "questions × people" to "people, once, plus questions, once" = linear. The catch: a single card can't hold every nuance, so razor-sharp focus and very long memories can blur. > [!mnemonic] Remember it as > **"Bake the crowd into a card."** Separate ($\phi$), then re-bracket, then read the card in constant time. Quick self-checks: Why does full attention cost $O(n^2)$? ::: Because the exponential glues each query to each key, forcing an $n\times n$ score grid. What single algebra rule collapses it to $O(n)$? ::: Associativity — pulling $\phi(q_i)$ out of the sum over $j$ so $S,Z$ are built once. What are $S$ and $Z$? ::: $S=\sum_j\phi(k_j)v_j^T$ (key–value summary) and $Z=\sum_j\phi(k_j)$ (normalizer), both independent of any query. Why must $\phi$ output positive values? ::: So the denominator $\phi(q)^TZ$ can never be zero and weights stay a valid blend. Does a $\phi$ with $\phi(q)^T\phi(k)\approx e^{q^Tk}$ really exist? ::: Yes — random-feature maps satisfy it in expectation with error $O(1/\sqrt{m})$; cheaper maps like elu+1 just give a positive separable kernel. What does linear attention become under a causal mask? ::: A recurrence — running sums for $S,Z$, i.e. an RNN-style fixed-size state.

Step 0 — What are these letters even?

Step 1 — Draw the full attention table (the O(n2) we want to kill)

Step 2 — The softmax is the glue we must dissolve

Step 3 — Replace the exponential with a product we CAN pull apart

Step 4 — The magic re-bracketing (associativity)

Step 1 — Draw the full attention table (the $O (n^{2})$ we want to kill)