O(n²) Attention Complexity: The Long-Context Cliff

Standard self-attention computes an (n × n) score matrix and a softmax over each row. Both time and memory scale as O(n²) in sequence length. For sequences up to a few thousand tokens this is cheap. Past 32K it gets expensive; past 128K it gets brutal; past 1M it's impractical without architectural changes.

Sequence length n	(n × n) entries	FP16 memory for one head
1K	1M	2 MB
8K	64M	128 MB
32K	1B	2 GB
128K	16B	32 GB
1M	1T	2 TB

For LLaMA-style models with 32+ heads and 80+ layers, multiply by ~2,560. A vanilla single-head attention at 1M tokens already needs 2 TB; full multi-head, multi-layer attention needs petabytes of intermediate storage — and that's before you've done the FFN. This is why models like LLaMA 4 Scout (10M context) and Gemini 2.5 Pro (1M context) are not running standard dense attention at full sequence length. They use efficient approximations (Flash Attention is exact but tiled in memory; sliding-window, sparse, and Mamba-hybrid alternatives are inexact).

Code

Memory cost calculator·python

def attention_memory_bytes(seq_len, n_heads=1, dtype_bytes=2):
    # Just the (n, n) score / weight matrix, per head
    return n_heads * seq_len * seq_len * dtype_bytes

for n in [1_024, 8_192, 32_768, 128_000, 1_000_000]:
    print(f"n={n:>9,}  per-head: {attention_memory_bytes(n)/1e9:>8.2f} GB"
          f"  Llama-3 32-head: {attention_memory_bytes(n, 32)/1e9:>9.2f} GB")

O(n²) Attention Complexity: The Long-Context Cliff

Code

External links

Exercise

Progress

Comments 0