Worked examples — Long-context architectures

This page is the "drill ground" for Long-context architectures. The parent note gave us four families of tricks — sparse attention, linear attention, state-space models (SSMs), and memory-augmented lookup. Here we hit every case with numbers you can check by hand.

Before we start, one promise: every symbol below is either defined here or built in the parent note. If you see $O(n)$ and feel unsure, read it as "the cost grows in proportion to $n$, the number of tokens." Nothing more magical than that.

---

The scenario matrix

Every cell below is covered by at least one worked example. The Ex # column tells you where.

Cell class	Specific case	What it stresses	Ex #
Sparse — normal	window $w\ll n$, few global tokens	linear saving	Ex 1
Sparse — degenerate	window $w=n$ (window = whole sequence)	collapses back to $O(n^2)$	Ex 2
Sparse — limiting	$w=1$ (each token sees only itself)	information loss extreme	Ex 2
Linear — normal	precompute $S,Z$, one query	associativity payoff	Ex 3
Linear — zero input	a query whose feature map hits a zero denominator	division-by-zero guard	Ex 4
SSM — decay sign	eigenvalue $\lambda <0$ vs $\lambda >0$ vs $\lambda =0$	stable / blow-up / neutral	Ex 5
SSM — limiting	$\Delta \to 0$ (tiny step)	recurrence $\to$ identity	Ex 6
Memory — normal	local $w$ + top-$k$ retrieval	additive cost	Ex 7
Word problem	pick an architecture for a real budget	design decision	Ex 8
Exam twist	crossover length where two costs tie	solve for $n$	Ex 9

---

Ex 1 — Sparse attention, the normal case

Forecast: guess now — will the total be closer to $20\times 20=400$, or closer to $20\times 5=100$? Write down your guess.

1. Regular tokens. There are $n-g=18$ regular tokens, each doing $w=5$ comparisons. $18\times 5=90$ Why this step? Each regular token only looks inside its sliding window — that is the whole point of "local."

2. Global tokens. Each of the $g=2$ global tokens compares against all $n=20$ tokens. $2\times 20=40$ Why this step? Global tokens are the escape hatch that preserves document-level information the local windows would miss.

3. Total. $90+40=130$ Why this step? Total sparse cost is $O(nw+gn)$ — here $130$.

4. Full attention baseline. $20\times 20=400$

Verify: $130<400$, a $67.5\%$ reduction. Sanity check the formula $nw+gn=20\cdot 5+2\cdot 20=100+40=140$? No — careful: the parent formula double-counts if we let global tokens also be regular. We removed them ($18$ regular), so $130$ is the honest count. Units: comparisons. ✓

Figure s01 — reading the sparse mask. The grid is the full $20\times 20$ attention matrix: row $i$ is a query, column $j$ is a key, and a coloured cell means "query $i$ actually looks at key $j$." The burnt-orange diagonal band is the local window — notice it hugs the diagonal, exactly $w=5$ cells wide, because each token only reaches two neighbours on each side. The deep-teal cross (top two rows and left two columns) is the two global tokens: full rows and full columns because they see everyone and everyone sees them. The cream cells are the comparisons we skip — and that skipped area, roughly $400-130=270$ cells, is precisely the compute we saved. This is the picture behind the $130$ vs $400$ count above.

---

Ex 2 — Sparse attention, the two degenerate corners

Forecast: which of these two extremes gives you back plain Transformer attention?

1. Case (a): $w=20$. Cost $=n\cdot w=20\times 20=400$. Why this step? When the window equals the whole sequence, "local" attention is full attention — we bought nothing. Complexity is back to $O(n^2)$.

2. Case (b): $w=1$. Cost $=20\times 1=20$. Why this step? Each token sees only itself. This is the cheapest possible — but it is also the most information-starved: no token can mix with any neighbour. Useless as attention, but it exposes the lower bound.

Verify: Case (a) equals the $400$ full-attention count from Ex 1 exactly ✓. Case (b) equals $n$, the theoretical floor (you must at least look at yourself). Monotonic in $w$: as $w$ goes $1\to 20$, cost goes $20\to 400$. ✓

---

Ex 3 — Linear attention, the normal payoff

This reworks the parent example so you can trust the machinery, then we extend it.

Forecast: the raw value list is $1,2,3,4$; will the answer land inside that range or outside?

1. Feature-map the keys. $\varphi (k_1)=[1,1,0],\varphi (k_2)=[1,0,1],\varphi (k_3)=[1,1,1],\varphi (k_4)=[1,0,0]$. Why this step? The whole linear-attention idea is to replace $e^{q\cdot k}$ with $\varphi (q{)}^T\varphi (k)$ so we can reorder the sum.

2. Precompute $S={\sum }_j\varphi (k_j)v_j$ (a 3-vector since $d_v=1$). $S=1[1,1,0]+2[1,0,1]+3[1,1,1]+4[1,0,0]=[10,4,5]$ Why this step? $S$ is the key–value summary, built once for all queries — this is where the $O(n)$ comes from.

3. Precompute $Z={\sum }_j\varphi (k_j)$. $Z=[4,2,2]$ Why this step? $Z$ is the normalizer — it plays the role the softmax denominator played.

4. Numerator and denominator for $q_1$, with $\varphi (q_1)=[1,1,0]$: $\text{num}=[1,1,0]\cdot [10,4,5]=14,\text{den}=[1,1,0]\cdot [4,2,2]=6$

5. Output. $14/6=2.\overline{3}$.

Verify: $2.33$ lies inside $[1,4]$ ✓ (a weighted average of values must). If we skipped normalization we'd report $14$, obviously outside the value range — the division by $Z$ is what keeps it honest. ✓

---

Ex 4 — Linear attention, the zero-denominator corner

Forecast: guess what happens to $\text{num}/\text{den}$.

1. Denominator. $\text{den}=[0,0,0]\cdot [4,2,2]=0$. Why this step? A zero denominator means "this query has no measurable similarity to anything" — division is undefined.

2. Numerator. $\text{num}=[0,0,0]\cdot S=0$. So we face $0/0$. Why this step? Both collapse together; the ratio is genuinely undefined, not infinite.

3. The engineering fix. Real implementations add a small $\epsilon$ (e.g. $10^{-6}$) to the denominator: $\text{output}=\frac{\text{num}}{\text{den}+\epsilon }=\frac{0}{0+10^{-6}}=0$ Why this step? A cleaner fix is to choose a feature map $\varphi$ whose components are always strictly positive, so the denominator can never truly hit zero. A common choice is $\varphi (x)=\text{elu}(x)+1$.

Verify: with $\epsilon =10^{-6}$, output $=0$, finite ✓. The parent note's $\varphi =[1,x_1,x_2]$ starts with a constant $1$, so its denominator $={\sum }_j(1+\dots )\ge n>0$ for real inputs — the constant-1 feature is itself a guard. ✓

---

Ex 5 — SSM, the sign of the eigenvalue (negative, positive, and zero)

First, a quick definition so nothing here is a mystery symbol.

Forecast: which sign gives a state that decays (safe), which explodes, and what happens exactly at zero?

1. Where $\bar{A}=e^{\Delta \lambda }$ even comes from. The equation $h^{\prime }=\lambda h$ has one exact solution: over any interval of length $\Delta$, the state multiplies by $e^{\Delta \lambda }$, i.e. $h(t+\Delta )=e^{\Delta \lambda }h(t)$. Why this step? We are not approximating here — $h^{\prime }=\lambda h$ is the classic "growth proportional to current amount" equation whose solution is an exponential. Advancing one token = advancing time by $\Delta$, so the exact per-token update is "multiply by $e^{\Delta \lambda }$." That is where $\bar{A}$ is born; every number below just plugs into it.

2. Case (a) $\lambda =-0.7$: $\bar{A}=e^{-0.7}\approx 0.4966$. $h_1=0.4966,h_2=0.2466,h_3=0.1225$ Why this step? Negative real part $\Rightarrow$ $|\bar{A}|<1$ $\Rightarrow$ old information fades — this is the stable, useful regime for long context.

3. Case (b) $\lambda =+0.7$: $\bar{A}=e^{0.7}\approx 2.0138$. $h_1=2.0138,h_2=4.0552,h_3=8.1662$ Why this step? Positive real part $\Rightarrow$ $|\bar{A}|>1$ $\Rightarrow$ state blows up. This is why S4 constrains eigenvalues to have negative real part.

4. Case (c) $\lambda =0$ (the boundary): $\bar{A}=e^0=1$. $h_1=1,h_2=1,h_3=1$ Why this step? This is the razor's edge — neutral stability. The state neither fades nor grows; it holds its value forever (a perfect infinite memory). In principle attractive, but fragile: any tiny numerical or learned nudge of $\lambda$ off zero tips you into decay ($<0$) or blow-up ($>0$). Real S4 keeps eigenvalues strictly in the left half-plane precisely to stay on the safe side of this edge.

Verify: (a) ratio between successive terms $=e^{-0.7}=0.4966$ constant, magnitudes shrinking ✓; (b) ratio $=e^{0.7}=2.0138$ constant, magnitudes growing ✓; (c) every $h_k=1$, ratio $=1$ exactly ✓.

Figure s02 — three fates of a state. The horizontal axis is the token step $k$; the vertical axis is the state's magnitude $h_k$. The burnt-orange curve ($\lambda =-0.7$) bends down toward the baseline — that curve is memory forgetting gracefully, the regime we want. The plum curve ($\lambda =+0.7$) rockets upward off the top of any fixed axis — numerical death, and the reason we forbid positive eigenvalues. The deep-teal flat line ($\lambda =0$) sits perfectly level at $h_k=1$ — the neutral boundary from step 4, holding its value forever. Seeing all three at once is the whole stability argument in one glance: the sign of $\lambda$ chooses which curve your model rides.

---

Ex 6 — SSM, the tiny-step limiting case

Forecast: as we sample time more and more finely, does the state change more or less per step?

1. Evaluate $\bar{A}$ at $\Delta =0.001$. $\bar{A}=e^{-0.0007}\approx 0.99930$. Why this step? Small $\Delta$ means each token advances time only a sliver, so $\bar{A}$ sits just under $1$.

2. One step barely moves $h$: $h_1=0.99930h_0\approx h_0$. Why this step? In the limit $\Delta \to 0$, $\bar{A}\to e^0=1$, the identity — the state is essentially frozen between steps. Continuous time is recovered.

3. Contrast $\Delta =1$: $\bar{A}=e^{-0.7}\approx 0.4966$, a big jump per step (from Ex 5).

Verify: ${\lim }_{\Delta \to 0}{e}^{\Delta \lambda }=1$ for any finite $\lambda$ ✓; at $\Delta =0.001$, $\bar{A}=0.99930$ is within $0.001$ of $1$ ✓. The step size $\Delta$ is the knob converting continuous dynamics to discrete tokens. ✓

---

Ex 7 — Memory-augmented, the additive-cost case

Forecast: will the attended count be nearer $576$ or nearer $50,000$?

1. Local. $512$ recent tokens. Why this step? Nearby context (grammar, immediate topic) is best served by a dense local window.

2. Retrieved. $k=64$ from memory. Why this step? Far-away-but-relevant facts come through selective retrieval, not brute force.

3. Total attended. $512+64=576$. Why this step? Cost is additive: $O(nw)+O(n\log M)$, not multiplicative.

4. ANN lookup cost per query $\approx {\log }_{2}M={\log }_{2}10,000\approx 13.29$. Why this step? FAISS-style indices scale like $O(\log M)$, so even a huge memory bank is cheap to query.

Verify: $576\ll 50,000$ (a $98.85\%$ reduction) ✓. ${\log }_{2}10000\approx 13.29$ ✓ — searching 10k items costs about the work of 13 comparisons, not 10,000. Units: tokens attended, comparisons for search. ✓

---

Ex 8 — Word problem, the design decision

Forecast: guess the order of magnitude in gigabytes for full attention.

1. Full-attention score memory. $n^2=(10^6{)}^2=10^{12}$ floats. At 2 bytes each: $2\times 10^{12}$ bytes $=2000$ GB. Why this step? This is per layer, per head — clearly impossible on any single device.

2. SSM memory. A fixed state of dimension $s=256$ plus a kernel of a few thousand entries — call it $\sim 20,000$ floats. To compare fairly we must use the same 2 bytes/float assumption we used for full attention: $20,000\times 2=40,000$ bytes $=40$ kB. Why this step? The state is a fixed-size summary of all history; it does not grow with $n$. Stating the byte-per-float assumption explicitly is what makes the two numbers directly comparable — mixing float widths would make the ratio meaningless.

3. Ratio (in floats, so the byte assumption cancels). $\frac{10^{12}}{20,000}=5\times 10^7$. Why this step? Since both counts use 2 bytes/float, the bytes cancel and we can compare raw float counts. SSM is about $50$ million times lighter on this axis — decisive for a memory-bound device.

4. The recommendation. Choose an SSM backbone (Ex 5's stable state) as the workhorse, optionally bolted to a small local-attention window (Ex 2's $w\ll n$) for sharp nearby detail. Pure full attention is ruled out by step 1's $2000$ GB. Reserve memory-augmented retrieval (Ex 7) only if the task needs verbatim recall of far-back facts, since it adds an index to maintain. Why this step? This maps the abstract cost numbers onto a concrete build: fixed memory $\Rightarrow$ favour the fixed-size state, accept its lossy compression, and buy back local precision cheaply with a small window.

Decision: SSM (+ small local attention) for a fixed-memory, million-token device; accept that the fixed state may lose some fine detail an attention layer would keep.

Verify: $10^{12}$ floats $\times 2$ B $=2\times 10^{12}$ B $=2000$ GB ✓ (since $10^9$ B $=1$ GB). SSM $20,000$ floats $\times 2$ B $=40,000$ B $=40$ kB ✓. Float-count ratio $10^{12}/2\times 10^4=5\times 10^7$ ✓.

---

Ex 9 — Exam twist, the crossover length

Forecast: guess whether the crossover is around a hundred, five hundred, or a thousand tokens.

1. Set equal. $nw=n^2$. Why this step? The crossover is exactly where switching architectures stops helping — the break-even point an exam loves to ask for.

2. Solve. Divide both sides by $n$ (valid for $n>0$): $w=n\Rightarrow n=512$. Why this step? Below $n=512$ the window already covers everything, so sparse = full anyway.

3. Interpret the regions.

   • $n<512$: since $w=512>n$, we get $nw>n^2$, so full is cheaper (the window is oversized and wasteful).
   • $n>512$: $n^2>nw$, so sparse is cheaper — and the gap widens fast.

Verify: at $n=512$: $nw=512\cdot 512=262144$ and $n^2=512^2=262144$, equal ✓. At $n=1000$: $nw=512000<n^2=10^6$, sparse cheaper ✓. At $n=100$: $nw=51200>n^2=10000$, full cheaper ✓.

This connects directly to computational complexity: the crossover is where the $O(n^2)$ curve overtakes the $O(nw)$ line.

---

Recall Self-test

Ex 1 total comparisons for $n=20,w=5,g=2$ ::: $130$ When window $w=n$, sparse attention collapses to complexity ::: $O(n^2)$ (identical to full) Linear-attention output for $q_1$ in Ex 3 ::: $14/6\approx 2.33$ The guard against a zero denominator in linear attention ::: add small $\epsilon$ / use strictly-positive feature maps like elu(x)+1 Sign of eigenvalue $\lambda$ that keeps the SSM state stable ::: negative (so $|e^{\Delta \lambda }|<1$) What happens at $\lambda =0$ for an SSM state ::: neutral — $\bar{A}=1$, state holds its value forever (fragile boundary) Crossover length where $nw$ meets $n^2$ with $w=512$ ::: $n=512$

See also the parent's kernel-approximation view via kernel methods, the retrieval angle in RAG, and the compression view in the information bottleneck.