Long context is not one problem but two, and they scale differently. Attention compute grows as O(N^2) in the sequence length N — every token looks at every other token — while the KV cache that makes decoding fast grows as O(N), one key/value slot per token per layer. Both walls are real, and they bite in different places: the quadratic term dominates the prefill of a long prompt, while the linear cache dominates the memory budget of a long-running or highly concurrent decode. Almost every ‘long-context’ technique you will read about is an attack on one of these two costs — or, in the case of position extension, on a third problem (the model going incoherent past its training length) that is easy to confuse with the first two. This piece lays out the taxonomy: what each family actually changes, the complexity math that justifies it, and the accuracy you pay for the asymptotics. We close with a worked cost comparison at N = 128K tokens so the numbers are concrete rather than folkloric.
The two costs, stated precisely
Fix notation. A decoder layer with model dimension d processes a sequence X: [N, d]. Self-attention forms scores S = QK^T where Q, K: [N, d], so S: [N, N], then softmax(S / √d) · V with V: [N, d]. The two matmuls (QK^T and AV) each cost ~2N^2 d FLOPs, so attention compute is O(N^2 d) per layer — quadratic in N.
The second cost is memory, and it appears at decode time. To generate token N+1 without recomputing the whole prefix, you cache the keys and values of every prior token. That KV cache holds 2 × N × L × d numbers (K and V, across L layers), so it is O(N) in length. It does not vanish between steps; it grows by one slot per generated token and must be re-read from memory on every step. So the sequence-length bill has two lines with different slopes: a quadratic compute line and a linear memory line. A strategy that flattens one may leave the other untouched, which is exactly why you have to know which cost you are fighting before you pick a fix.
Where each cost actually hurts: prefill vs decode
The two costs dominate in different phases. Prefill ingests the whole prompt in parallel; it is compute-bound, and its dominant term is the O(N^2 d) attention over all N positions at once. A 128K-token prompt does not cost twice a 64K prompt — it costs four times, because the quadratic. Decode generates one token at a time; each step does only O(N d) attention (one query against N cached keys) but must stream the entire O(N) KV cache and the model weights from memory, so it is memory-bandwidth-bound.
This split explains the taxonomy’s shape. Techniques that shrink the quadratic (sparse, linear, low-rank attention) primarily help prefill and very-long-sequence throughput. Techniques that shrink the cache (quantization, GQA, eviction) primarily help decode memory and concurrency — how many long conversations fit on a GPU at once. FlashAttention sits apart: it keeps attention exact and still O(N^2) in compute, but tiles the computation so it never materializes the [N, N] matrix, cutting attention memory from O(N^2) to O(N). It is the free lunch everything else is measured against.
A map of the five families
Before the details, the whole landscape on one page. There are five families, and it helps to tag each with the cost it attacks and whether it is exact or approximate.
| Family | Attacks | Compute | Exact? |
|---|---|---|---|
| Position extension (PI, NTK, YaRN) | coherence past L_train | O(N^2) unchanged | exact |
| Sparse / local attention | O(N^2) compute | O(N·w) | approximate |
| Linear / low-rank attention | compute and cache | O(N·d^2) or O(N·k) | approximate |
| KV compression / eviction | O(N) cache | O(N^2), smaller cache | approximate |
| Retrieval (RAG, RETRO) | both, by shrinking N | O((k·c)^2) | approximate |
Two things jump out. First, position extension does not reduce any cost — it is on the list because it is a prerequisite for long context, not a saving, and confusing it with the compute fixes is a common error. Second, only linear attention attacks both the quadratic compute and the linear cache at once, by replacing the growing cache with a fixed-size recurrent state — which is also why it pays the steepest accuracy price. The rest of this article is these five rows, one at a time, with the math.
Family 1: position extension (why long context breaks first)
Before you can be cheap at long N you have to be coherent at long N, and a model trained to length L_train usually is not. The reason is positional encoding. RoPE (rotary embeddings) encodes position m by rotating each query/key feature pair by an angle m · θ_i, with frequencies θ_i = base^(-2i/d). At inference beyond L_train, the low-frequency dimensions see rotation angles the model never observed in training, and attention degenerates — perplexity explodes even though nothing about compute or memory changed.
The fixes rescale position so the angles stay in-distribution. Position Interpolation divides all position indices by L_target / L_train, squeezing a longer sequence into the trained angular range (linear, cheap, needs light fine-tuning). NTK-aware scaling instead changes the base, interpolating high frequencies less and low frequencies more, so local resolution is preserved. YaRN combines NTK-by-parts (per-frequency-band treatment) with an attention-temperature correction and reaches long context with very little fine-tuning. Crucially, all of these leave the O(N^2) compute and O(N) cache exactly where they were — they buy accuracy at length, not efficiency.
Family 2: sparse and local attention — the sliding window
The first genuine compute saving: stop attending to everything. In sliding-window attention each query attends only to the w nearest preceding keys, not all N. The score matrix becomes a band of width w, so compute drops from O(N^2 d) to O(N · w · d) — linear in N for fixed w. Mistral 7B, for instance, uses w = 4096.
The subtlety is receptive field. A single windowed layer only sees w tokens back, but stacking L such layers propagates information: a token can indirectly reach roughly L · w tokens away, the way stacked convolutions grow their field. So a 32-layer model with a 4K window has an effective reach of ~128K — enough for locality-dominated text, but only indirectly, through intermediate layers. The accuracy cost is precisely there: any single query cannot directly retrieve a fact 100K tokens back in one hop, and multi-hop propagation is lossy. Sliding windows shine on generation and long documents where relevant context is mostly recent, and struggle on tasks that need exact long-range lookup unless another mechanism carries the global signal.
Family 2, continued: dilation and global tokens
Two refinements widen a window’s reach without paying for full attention. Dilated attention attends to every r-th key instead of every key — a strided window — so a fixed budget of w connections spans a range of w · r, the way dilated convolutions enlarge the field. It keeps compute at O(N · w) while covering more ground, at the price of a coarser, gappier view of the middle distance.
Global tokens address the ‘can’t reach far in one hop’ problem directly. A handful of designated tokens attend to all positions and are attended by all positions, forming a shared bus. Longformer combines a sliding window with a few task-specific global tokens (e.g. the [CLS] token); BigBird adds random connections on top of window + global, and proves this sparse pattern is a universal approximator of full attention while staying O(N). With g global tokens the extra cost is O(N · g), so total compute is O(N · (w + g)) — still linear. The trade-off is that you must choose the pattern in advance; whatever long-range edge your task needs but the fixed pattern omits is simply invisible to the model.
Family 3: linear attention and the kernel trick
Sparse attention keeps softmax but drops connections. Linear attention keeps all connections but drops softmax, and the payoff is an associativity trick. Ordinary attention computes softmax(QK^T) V, forcing the [N, N] matrix. Replace the softmax similarity with a kernel feature map φ(·) so that sim(q, k) ≈ φ(q) · φ(k). Then attention is φ(Q) (φ(K)^T V), and matrix multiplication is associative:
full: softmax(Q K^T) V -> [N,N] then [N,N]x[N,d] = O(N^2 d)
linear: phi(Q) ( phi(K)^T V ) -> [d,d] state, then [N,d]x[d,d] = O(N d^2)
compute phi(K)^T V once -> a d x d summary S of the whole past
each output row = phi(q_i) S (no growing N x N matrix)The consequences are large. Compute falls to O(N d^2) — linear in N. And because the ‘past’ is now the fixed d × d state S, decoding becomes a recurrence with O(d^2) memory that does not grow with N — the KV cache disappears. Performer chooses φ as random features that provably approximate the softmax kernel; the Linear Transformer uses a simple elu+1 feature map and exposes the RNN view explicitly.
Family 3, continued: low-rank projection and the accuracy price
A close cousin attacks the same [N, N] matrix by assuming it is approximately low-rank. Linformer projects the keys and values along the sequence axis from length N down to a small constant k (via learned [N, k] projections), so scores are [N, k] and compute is O(N · k · d) — linear in N. It is simple and fast, but the fixed k caps how much distinct information the sequence axis can carry.
Now the bill. Softmax attention is sharp and selective: it can put almost all weight on a single token — the exact behavior needle-in-a-haystack retrieval and in-context learning rely on. Linear and low-rank approximations smear that: a fixed d × d or rank-k summary literally cannot store N arbitrary tokens losslessly once N exceeds its capacity, so precise recall of an old, specific token degrades. This is why, despite the beautiful asymptotics, pure linear attention has not displaced softmax at the frontier — it looks competitive on average language-modeling perplexity but underperforms on retrieval-heavy and long-range-exact tasks. The practical answer today is hybrids: interleave a few full-attention layers among many linear ones so the model keeps some exact recall while paying mostly linear cost.
Family 4: shrinking the KV cache without touching compute
Suppose you keep exact softmax attention — FlashAttention already makes compute memory-cheap — but the O(N) KV cache is what pins your batch size. Attack the cache directly. The cheapest lever is architectural sharing: Multi-Query and Grouped-Query Attention let many query heads share one K/V head, dividing the cache by the group factor (often 4–8×) with negligible quality loss — now standard in modern models. Orthogonally, KV quantization stores keys and values in int8 or int4 instead of fp16, a 2–4× reduction for a small precision cost.
These are lossless-ish and stack with everything. But they only rescale the O(N) line — the cache still grows without bound as the conversation runs. To bound it you need to stop keeping every token, which means eviction: deciding which past keys/values to throw away. That is a genuine approximation with a genuine failure mode — an evicted token is gone, and if a later query needed it, the model cannot recover it. The next section covers the two eviction policies that work in practice and the surprising trick that keeps them from collapsing.
Family 4, continued: eviction — H2O and StreamingLLM
Eviction turns the unbounded cache into a fixed budget of k slots. The question is which k tokens to keep. H2O (Heavy-Hitter Oracle) observes that attention mass is highly concentrated: a small set of ‘heavy hitter’ tokens accumulate most of the attention across steps. So H2O keeps the recent window plus the running heavy hitters and evicts the rest, holding the cache at O(k) while retaining most of the quality — because it keeps exactly the tokens the model actually attends to.
StreamingLLM targets endless generation and exposes a striking detail. Naively keeping only a sliding window of recent tokens makes perplexity explode once the earliest tokens fall out. The fix: always retain the first few tokens — the ‘attention sinks’ — alongside the recent window. Those initial tokens absorb surplus attention probability (softmax must sum to one, and it dumps the remainder somewhere); dropping them destabilizes every later softmax. With a handful of sink tokens plus a window of size w, StreamingLLM streams indefinitely at O(w) cache and stable perplexity. Both methods share the same caveat as sliding windows: information outside the retained set is unrecoverable, so exact recall of a long-evicted fact is not guaranteed.
Family 5: retrieval — don’t put it in the context at all
The last family reframes the problem. If the corpus is a million tokens, the cheapest way to avoid O(N^2) over a million tokens is to not attend over a million tokens. Retrieval keeps the documents in an external index (typically vector embeddings in a database) and, per query, pulls the top-k relevant chunks of size c into a short context. Attention then runs over ~k · c tokens, so compute is O((k c)^2) with k c « N, and there is no KV cache for the unread bulk — the corpus lives on disk, not in GPU memory. Retrieval itself is sub-linear (approximate nearest neighbor).
Two flavors exist. RAG retrieves text and prepends it to the prompt — model-agnostic, simple, ubiquitous. RETRO and kNN-LM push retrieval inside the model, fetching neighbor chunks and attending to them via a dedicated cross-attention, which lets a small model match a much larger one on knowledge. The trade-off is that retrieval quality caps everything: if the retriever misses the relevant chunk, the model never sees it, and no amount of reasoning recovers it. You also lose true global reasoning — the model sees fragments, not the whole document — and you inherit chunking-boundary and embedding-drift headaches. In exchange you scale to effectively unbounded corpora sub-quadratically.
A worked cost comparison at N = 128K
Numbers make the taxonomy concrete. Take a 7B-class model: d = 4096, L = 32 layers, fp16, and a single sequence of N = 128K = 131,072 tokens. Start with the full-attention baseline for the two costs.
KV cache (full) = 2 * N * L * d * 2 bytes
= 2 * 131072 * 32 * 4096 * 2
~ 64 GB <-- for ONE 128K sequence, before GQA
Attn compute (prefill, per layer) ~ 4 * N^2 * d FLOPs
= 4 * (1.31e5)^2 * 4096 ~ 2.8e14 per layer
x 32 layers ~ 9.0e15 FLOPs (~9 PFLOP)Sixty-four gigabytes of cache for one conversation is why concurrency collapses at long context, and nine petaFLOPs of attention is why the prompt is slow to ingest. Note also the crossover: attention’s ~4N^2 d overtakes the FFN’s ~16 N d^2 once N > 4d ≈ 16K tokens — below that the FFN dominates FLOPs, above it attention does, which is why the quadratic only becomes the villain in the long-context regime. Now see what each family does to these two numbers.
Reading the comparison table
Applying each family to the same N = 128K case, holding w = 4096, k = 8 retrieved chunks of c = 512:
| Strategy | Prefill compute | KV cache | vs full |
|---|---|---|---|
| Full + FlashAttention | O(N^2) ~9 PFLOP | ~64 GB | baseline (exact) |
| GQA (8 groups) + int8 | O(N^2) ~9 PFLOP | ~4 GB | 16× less cache |
| Sliding window w=4K | O(N·w) ~0.28 PFLOP | ~2 GB | ~32× less compute |
| StreamingLLM (sinks+w) | O(N·w) | ~2 GB (bounded) | streams forever |
| Linear attention | O(N·d) linear | O(d^2) tiny, fixed | no cache growth |
| RAG (k·c=4K ctx) | O((kc)^2) ~9 TFLOP | ~2 GB in-ctx | corpus stays on disk |
The pattern is clear. Sharing and quantization (GQA, int8) cut the cache ~16× while leaving compute and accuracy essentially intact — always do these. Sliding windows and streaming cut compute ~32× and bound the cache, at the cost of direct long-range recall. Linear attention removes cache growth entirely but pays in retrieval accuracy. Retrieval makes the raw N almost irrelevant — a 4K working context regardless of a corpus of millions — but its answer quality is only as good as its retriever. No row is free of trade; the ‘right’ one is dictated by whether your task needs exact global recall or merely local coherence.
Composing the strategies (they are not exclusive)
In practice these families stack, because they attack different costs and different problems. A modern long-context stack typically layers: YaRN or PI so the model stays coherent past its training length (coherence); FlashAttention so exact attention never materializes the [N, N] matrix (compute memory); GQA plus KV quantization so the cache is small enough for real batch sizes (decode memory); and, when the sequence is truly enormous or endless, sliding windows with attention sinks for streaming or retrieval when the corpus dwarfs any feasible window.
The mental model for composing them is the exact/approximate split. Position extension and FlashAttention are exact — they change coherence and memory layout without approximating attention, so use them freely and first. Everything else — sparse, linear, eviction, retrieval — trades accuracy for asymptotics, so reach for them only once the exact tools run out, and reach for the one whose accuracy loss your task can absorb. A code-completion model tolerates a sliding window; a legal-document QA system that must cite an exact clause 90K tokens back cannot, and wants exact attention plus retrieval instead. Match the approximation to the task, not to the benchmark leaderboard.
Pitfalls and what actually breaks
A few traps recur. First, ‘supports 128K’ is not ‘uses 128K’: even exact-attention models exhibit lost-in-the-middle, recalling facts at the start and end of a long context far better than the middle, so a longer window is not automatically more useful. Second, length extension without fine-tuning degrades — PI and YaRN need at least light adaptation, and naive extrapolation past L_train is often worse than truncating. Third, sparse patterns silently drop the one token that mattered: a fixed window or dilation is invisible to whatever long-range edge it omits, and you will not see the failure unless you test long-range recall specifically.
Fourth, linear-attention benchmarks mislead: strong average perplexity coexists with poor needle-in-a-haystack and in-context-learning scores, so evaluate on retrieval tasks, not just LM loss. Fifth, KV eviction fights any task that rereads early context — H2O and StreamingLLM assume recency and heavy-hitter locality, which breaks when a late query must revisit an evicted passage. Sixth, retrieval’s ceiling is its recall: chunking boundaries, embedding drift, and a single missed chunk cap the whole system. The unifying lesson: every sub-quadratic method makes an assumption about where the relevant information lives, and it fails exactly when that assumption does. Know your task’s access pattern before you pick your strategy.