How a model reads the whole without weighing every word against every other. · Source

It weighs every word against every other. Most of that is wasted.

Attention's whole trick is that every word gets to look at every other word. Beautiful — and brutal. The bill grows as the square of the length: double the text, quadruple the work. Like wiring a town house-to-house: a separate line between every pair, a sky full of crossed cables — and almost none of them ever used. The grid is mostly empty. So why pay for all of it?

Most of that giant grid carries nothing.

\text{cells}=n^2,\quad \text{useful}\approx n\,k,\quad \frac{n\,k}{n^2}=\frac{k}{n}\to 0\ \ (k\ll n)

Look where a word's attention actually lands: a few near neighbors and a handful of far anchors. The rest of the row is near zero. Like the worn tracks across a green: of all the ways to cross, the crowd wears in only a few — the corners stay untrodden. Of n² possible links, real weight sits on a thin slice — and that slice, k⁄n, only shrinks as the text grows. So which pairs can we safely skip?

First escape: just look at your neighbors.

\text{Attn}(q_i)=\operatorname{softmax}\!\Big(\tfrac{q_i K_{i-w:i}^{\top}}{\sqrt d}\Big)V_{i-w:i}\ \ (\text{cost }O(nw)),\qquad \text{reach after }L\text{ layers}\approx L\,w

The simplest cut: let each word attend only to a window of nearby words — the last w, not all n. The cost drops from a square to a line. Like a stadium wave: each person watches only the two beside them, yet the wave still sweeps the whole arena. Stack a few layers and the reach spreads — after L of them, a word's view grows to about L·w.

But far-apart words still need to meet.

\text{cost}=O\!\big(n(w+g)\big),\quad g\ll n;\qquad \text{any pair connects in }\le 2\text{ hops via a global token}

Neighbors-only would snip every long thread. The fix: keep a few global anchors — tokens that see everyone and that everyone sees. Now any two distant words connect through an anchor in two short hops. Like a hub airport: small towns don't fly to every other town — route them through a couple of hubs and anywhere reaches anywhere. The grid stays nearly empty; the whole still talks.

The bolder escape: never build the grid at all.

\operatorname{Attn}(q_i)=\dfrac{\phi(q_i)^{\top}\sum_j \phi(k_j)\,v_j^{\top}}{\phi(q_i)^{\top}\sum_j \phi(k_j)}\,,\qquad (QK^{\top})V:\ O(n^2d)\ \to\ Q(K^{\top}V):\ O(nd^2)

Sparse attention still draws a thin grid. Linear attention refuses to draw one. Trade softmax's exponential for a plain feature map, and the order of the multiplication frees up: instead of queries-times-keys first, fold all the keys and values into one small running summary, then let each query read it. Like a river confluence: instead of every town piping to every spring, all the springs feed one river and each town just draws from that. Square becomes line.

But here's the honest catch.

\exp\!\big(q^{\top}k/\sqrt d\big)\;\approx\;\phi(q)^{\top}\phi(k)\quad\Rightarrow\quad o_{\text{lin}}\neq o_{\text{softmax}}\quad(\text{exact: }o=o_{\text{exact}})

None of this is free. Sparse attention bets that the pairs it dropped didn't matter; linear attention swaps softmax's sharp spotlight for a softer blur. Both return a slightly different answer than the full version — an approximation, not a match. Like eyeballing a flock: one sweep of the eye gives a fast, close count — but it's an estimate, not the head-by-head tally. The exponential's spike can't fit a small fixed map exactly; the exact speedups, by contrast, only move less memory and never change the answer.

The payoff: length stops being a wall.

O(n^2d)\ \longrightarrow\ \underbrace{O(nwd)}_{\text{sparse}}\ \text{or}\ \underbrace{O(nd^2)}_{\text{linear}},\qquad \frac{\text{cost}(2n)}{\text{cost}(n)}=2

Tally it up. The full bill grew as the square; now it grows as a line. Double the text and you double the work — not quadruple it. Like lamps along a road: add a mile, add a few more lamps — the cost rises one even step at a time, so the road can run to the horizon. That straight line is what finally makes very long context — whole books, hours of talk — affordable.

🌱 What could a mind safely ignore — and still understand?

You don't weigh every word of this sentence against every other. You lean on the few that matter and let the rest blur — and still you grasp the whole. Like a window at dawn: only the nearest ridge is sharp, the farther ranges dissolve into haze, and yet you take in the entire valley. Maybe the full grid was never the point. Maybe understanding was always mostly local — with a few long threads thrown across the dark.