From Quadratic to Linear
Why attention got cheaper, and what it means for the chipmakers.
The square problem
Attention is the mechanism that lets a language model relate every word in its input to every other word. It’s powerful, and it has a cost problem built in: double the length of the input and the work roughly quadruples. That’s what O(n²), or quadratic, means.
For short prompts this barely matters. For long documents, codebases or hours of transcript, it dominates everything, and much of the cost isn’t the math itself but moving huge intermediate tables in and out of memory.
Same math, less traffic
FlashAttention, published in 2022, didn’t change what attention computes. It changed how: by working in small tiles that fit in a GPU’s fast on-chip memory, it avoided writing the giant intermediate table out to slower memory at all. The results are exact, not approximations.
A third version followed for Nvidia’s newer H100 chips, using their asynchronous hardware features and lower-precision math. Each generation is tuned more tightly to the specific silicon it runs on.
Changing the math itself
A different line of research asks whether every token really needs to look at every other token. State-space models such as Mamba, by Albert Gu and Tri Dao, process a sequence step by step while carrying forward a compact running state, so their cost grows linearly with length.
Whether these architectures replace attention, complement it in hybrid models, or stay niche is still an open question. But they’re already shaping research and product decisions.
Why chipmakers care
This is the hardware–software loop in miniature. Quadratic attention made memory bandwidth the bottleneck, which pushed chips toward high-bandwidth memory and larger on-chip caches. FlashAttention-style kernels then squeezed more out of those chips. If linear-time models win, the ideal chip shifts again, with less pressure on memory and a different balance of components.
What to watch
- Hybrid models that mix attention layers with state-space layers.
- Kernels written or tuned by AI systems, such as the FlashAttention speedups reported for AlphaEvolve.
- Long-context benchmarks that test whether cheaper methods actually keep quality at length.