Subquadratic Attention
Subquadratic attention refers to methods that make the computational cost of language models grow more slowly than quadratically when processing long texts. Instead of comparing every word with every other word, the number of comparisons is deliberately reduced.
Modern language programs like ChatGPT don’t read a text word by word in isolation. For each word, they check which other words in the text are important to it. This checking is called attention. In the classic method, every word is really compared with every other word. With 1,000 words, that’s a million comparisons; with 10,000 words, it’s already a hundred million. So the effort grows quadratically: twice as much text means four times as much computation. Subquadratic attention is the umbrella term for methods in which the effort grows more slowly than that.
Why long texts fail at the square
The amount of text a model can consider at once is called the context window. Users want to fit entire books, program code, or hours-long conversation histories into it. With the classic method, this quickly becomes unaffordable. A jump from 10,000 to 100,000 words doesn’t multiply the cost tenfold, but a hundredfold.
On top of that comes memory usage. The table of all word-to-word comparisons must sit in graphics memory, which is scarce on expensive compute cards. This is exactly where the hard limit arises in practice. Many models could in principle process longer texts, but fail due to the available memory.
Economically, this is one of the industry’s most important levers. Every request to a language model costs electricity and compute time. If companies halve the cost per long request, that determines the margin of entire products. That’s why a great deal of research funding goes into more efficient attention.
Shortcuts instead of all comparisons
An obvious approach is to simply leave out superfluous comparisons. This is called sparse attention. Each word then only looks at its nearest neighbors plus a few fixed anchor points in the text. It’s like reading: to understand a sentence, you rarely need page 300.
A second approach changes the order of computation. Mathematically, the formula can be rearranged so that the huge comparison table never fully arises. Instead, the model continuously condenses the text so far into a compact intermediate state. The effort then only grows linearly, i.e., proportional to the length of the text. This family is called linear attention and is closely related to so-called state space models.
A common misconception is that these methods are free. You trade accuracy for speed. If you cut comparisons, you risk the model missing a crucial reference at the beginning of the text. This should incidentally be distinguished from FlashAttention: this method still computes quadratically, but simply handles memory more cleverly.
Where the technology shows up in products
When a provider advertises a context window of one million characters, there’s almost always a hybrid form behind it. Typically, some layers of the model still compare fully, while other layers take shortcuts. Coding assistants that are supposed to read an entire project directory also depend on such tricks.
In tech industry news, you’ll usually encounter the term in two contexts. First, in connection with new model architectures with names like Mamba, which largely dispense with classic attention. Second, in connection with chips and data centers, where it’s about cost per unit of text processed.
For you as a user, the effect is invisible but noticeable. Answers to long documents arrive faster and are cheaper. At the same time, a critical look is worthwhile: models with a very large context window often lose details in the middle of long texts. This weakness is directly related to the shortcuts taken in attention.