Sparse attention
The efficiency lineage · 2025
The idea
Section titled “The idea”The middle door of the taxonomy: fewer comparisons, same growing cache.
The story, animated
Section titled “The story, animated”The full grid, then the window that misses “animal”, then top-k that keeps the near-tie — and the cache that still grows.
Verdict
Section titled “Verdict”What it fixedAttend only to the top-k relevant tokens - compute ~ N x k.
What it still costsMemory still grows with N. The residual that motivates the linear branch.
Where it sits
Section titled “Where it sits”Worth having first: The memory wall
A window that drops the first tokens is the catastrophic case this page already showed. Sliding window with sinks keeps those first tokens on purpose — they stabilize softmax; they do not remember “animal”.