Long-Context Efficiency

The KV-cache math page showed the cache grows linearly with sequence length. Now push the sequence length to 128K, 200K, a million tokens — the regime where “long context” stops being a feature and becomes the dominant cost. Two scaling laws fight you at once, and this page is the toolbox for both.

The two costs of length

  Full attention over n tokens:
    compute  ∝ n²   (every token attends to every prior token)
    KV cache ∝ n    (store K,V for every token, kept for all of decode)

• Compute, O(n²). A prefill of n tokens computes an n×n attention matrix per layer. Double the context, quadruple the prefill attention work. (FlashAttention cuts the memory of that matrix but not the FLOPs.)
• Memory, O(n). Every token’s keys and values stay resident for the entire decode, because token t+1 attends back to all of them.

Worked example — KV growth. Take a 70B-class model: 80 layers, ~8 KV heads × 128 dims, FP16. Per token:

per-token KV ≈ 2 (K,V) × 80 layers × (8×128) × 2 bytes ≈ 0.33 MB

Context	KV cache
4K tokens	~1.3 GB
32K tokens	~10 GB
128K tokens	~42 GB

At 128K the KV cache alone (~42 GB) rivals a quantized copy of the weights — and that is per concurrent request. Ten users at 128K and you have blown past an 80 GB GPU on cache alone. Length is a memory bill, paid per user, every step.

Lever 1 — attend to less (compute)

If most tokens only really need recent context, stop computing full attention.

• Sliding-window / local attention. Each token attends to the last w tokens, not all n. Compute drops from O(n²) to O(n·w); the KV cache you must keep shrinks to w. Mistral popularized this. The trade: information older than the window can only propagate indirectly, layer by layer.
• StreamingLLM (attention sinks). Pure sliding windows break when the oldest tokens are evicted — models dump “excess” attention onto the first few tokens, and losing them wrecks fluency. StreamingLLM keeps a handful of sink tokens (the first few) plus a recent window. With sinks + window you can stream essentially unbounded text at fixed memory.

  Full:    [#######################] every pair
  Window:  [........■■■■■■■■]  last w only
  Stream:  [##.......■■■■■■■■]  few sinks + recent window
            ^^ sinks            ^^ window

Lever 2 — keep fewer tokens (memory)

Even with full attention you can compress what you store.

• KV eviction — H2O (Heavy-Hitter Oracle). Empirically a small set of “heavy hitter” tokens receive most of the attention mass. H2O keeps those plus recent tokens and evicts the rest from the cache, holding KV memory roughly constant as context grows. Trade: an approximation — occasionally an evicted token mattered.
• KV quantization. Store K and V in INT8 or INT4 instead of FP16 — 2–4× less cache memory for a small accuracy cost, the same idea as weight quantization applied to the cache.
• GQA / MQA. Multi-Query and Grouped-Query Attention share K/V heads across many query heads. With 8 KV heads instead of 64, the KV cache shrinks ~8×. This is now standard in large models precisely because it attacks the O(n) term directly — it is why the worked example used 8 KV heads, not 64.

Lever 3 — spread the sequence (scale out)

When one device cannot hold the cache at all:

• Ring attention. Shard the sequence across devices; each holds a slice of K/V, and the attention computation passes blocks around a ring so every query eventually sees every key. This makes million-token context possible by pooling memory across GPUs. The cost is communication on every step — you trade interconnect bandwidth for capacity you could not otherwise afford.

Exactness is a knob, not a default

Sliding windows, H2O, and KV quantization are approximations — they bet that distant or low-attention tokens don’t matter much. For summarization that’s usually safe; for tasks that need a fact buried 100K tokens back (“needle in a haystack”), an evicted token is a wrong answer. GQA and ring attention are exact; the rest trade accuracy for memory. Know which kind you’re deploying.

Stacking the levers

These compose. A production long-context stack might use GQA (exact, ~8× cache cut) + KV-INT8 (2× cut) + sliding-window attention for the bulk of layers — together turning a 42 GB cache into single-digit GB, per request. The dollar effect is multiplicative.

It actually happened — “Lost in the Middle” (2023)

Approximating long context assumes the model uses all of it evenly — but it doesn’t, even with full attention. In Lost in the Middle: How Language Models Use Long Contexts (Liu et al., 2023), researchers planted a relevant fact at different positions inside a long input and measured retrieval. Performance traced a U-shape: models reliably used information at the very start or the very end of the context and were markedly worse when the needed fact sat in the middle. The implication for everything on this page is sharp — context you pay full memory and compute for is not uniformly useful, so eviction and windowing schemes that protect recent and early tokens are partly working with the model’s own bias, while a fact buried mid-context may be half-lost before you ever evict it. Long context is a quality problem, not only a memory bill.

The cost lens

Long context is the clearest case of the throughline: every extra token is more compute (O(n²) attention) and more memory (O(n) cache), and the memory is paid per concurrent user, on every decode step. The whole toolbox above is one question answered many ways — how do we serve length without paying linearly (or quadratically) for it?

The architect’s lens

Long context is two scaling laws fighting you — the toolbox is how you buy it back:

• Why does it exist? Because attention is O(n²) compute and the KV cache is O(n) memory, and at 128K tokens the cache (~42 GB) rivals a quantized copy of the weights — per concurrent request.
• What problem does it solve? Serving length without paying linearly (or quadratically) for it: GQA/MQA cut the cache ~8× (exact), KV-INT8 ~2×, sliding-window/H2O cap memory as context grows, and ring attention pools memory across GPUs for million-token context.
• What are the trade-offs? Most memory levers are approximations — sliding windows, H2O eviction, and KV quantization bet that distant or low-attention tokens don’t matter, which is safe for summarization but wrong for a needle buried 100K tokens back.
• When should I avoid it? Avoid the lossy levers (eviction/windowing) on retrieval-style tasks that need an exact fact from deep in the context; prefer the exact ones (GQA, ring attention) there.
• What breaks if I remove it? Full attention plus a full-precision KV cache: a handful of 128K sessions blow past an 80 GB GPU on cache alone, leaving no room for weights or other users.

Check your understanding

1. State the two asymptotic costs of context length and which resource each one bills.
2. In the worked example, why does a 128K-token KV cache (~42 GB) make multi-tenant serving so hard?
3. What problem does StreamingLLM’s “attention sink” fix that a plain sliding window has?
4. How do GQA/MQA reduce KV-cache size, and why is that lever “exact” while H2O is not?
5. When is ring attention the right tool, and what does it cost?

Show answers

1. Compute is O(n²) (the attention matrix), billing the GPU’s compute units during prefill; KV-cache memory is O(n), billing VRAM for the whole decode.
2. The ~42 GB cache is per request; a handful of concurrent 128K sessions exceeds an 80 GB GPU on cache alone, leaving no room for weights or more users.
3. When old tokens are evicted from a sliding window, models lose the first tokens they dump excess attention onto, wrecking fluency; keeping a few “sink” tokens plus the recent window restores it and allows unbounded streaming at fixed memory.
4. They share K/V heads across many query heads (e.g. 8 KV heads instead of 64), shrinking the cache ~8×. It’s exact because every query still attends to real keys/values — no token is dropped — whereas H2O evicts tokens and may drop one that mattered.
5. When the KV cache (huge context) cannot fit on one device; you shard the sequence across GPUs to pool memory, paying interconnect communication on every step in exchange for capacity you couldn’t otherwise have.