Why does self-attention scale quadratically with sequence length, and how do long-context models cope?

Standard self-attention compares every token with every other token: for a sequence of n tokens it computes an n-by-n attention matrix, so both compute and (naive) memory scale as O(n^2). Doubling context roughly quadruples attention cost, which is why long contexts are expensive. Coping strategies fall into a few families. Exact but memory-efficient kernels like FlashAttention avoid materializing the full matrix, reducing memory to O(n) and speeding things via tiling, without changing the math. Approximate/sparse attention (Longformer, BigBird, sliding-window as in Mistral) restricts each token to a local or structured subset of others, giving near-linear cost. Linear-attention and state-space models (Mamba) replace softmax attention with recurrences that scale linearly. Retrieval and context compression sidestep the issue by feeding only relevant chunks. RoPE scaling/interpolation extends usable length. The KV cache also grows linearly with n, compounding long-context memory pressure.