What Limits Context Windows: Attention Complexity, Memory, and Cost

It's tempting to assume a '1 million token context window' costs roughly 8x what a 128k window costs, since 1M is about 8x bigger than 128k. The real cost is far worse than that, and understanding why requires looking at what self-attention (the mechanism inside every Transformer, covered at a high level in this curriculum's neural-networks material) actually computes.

Self-attention lets every token 'look at' every other token to decide how much to weigh it when building its own representation. For a sequence of n tokens, this means computing an attention score between EVERY pair of tokens — that's n multiplied by n, or n-squared, pairs. Double the sequence length, and you don't double the work — you quadruple it: 2n tokens means (2n)^2 = 4n^2 pairs, four times as many as before. This O(n^2) (order n-squared) scaling is the single biggest structural reason context windows can't just be made arbitrarily large by throwing more compute at the problem — the cost curve gets steeper and steeper as n grows, not just proportionally bigger.

Memory is the second constraint, and it's closely related to the KV cache from this curriculum's llm-optimization topic: every token's attention keys and values need to be stored so future tokens can attend to them, and that storage also grows with sequence length. A model processing a 1-million-token context needs to hold a correspondingly enormous KV cache in GPU memory for the ENTIRE generation — this is why extremely long contexts are often memory-bound (limited by how much fits in VRAM) well before they're compute-bound.

Inference cost combines both problems into what you actually pay: processing a long prompt (the 'prefill' phase, computing attention across the whole input at once) takes meaningfully longer and costs meaningfully more as the input grows, due to the O(n^2) attention cost above, and providers typically price API calls partly by token count specifically because longer inputs are genuinely more expensive to serve, not just as a convenient billing unit.

This is exactly why 'just increase the context window' isn't a free upgrade a lab can ship overnight — every genuine long-context capability increase requires engineering work to manage this quadratic cost curve, which is precisely what the next two subtopics' techniques (better positional encodings, sparse/sliding-window attention) are built to address.

# Demonstrating the O(n^2) attention cost directly: doubling sequence
# length QUADRUPLES the number of attention score pairs computed.

def attention_pair_count(seq_len: int) -> int:
    """Every token attends to every other token: n * n pairs."""
    return seq_len * seq_len

def kv_cache_size_mb(seq_len: int, num_layers: int = 32, num_kv_heads: int = 8,
                     head_dim: int = 128, bytes_per_val: int = 2) -> float:
    """KV cache memory (from llm-optimization) also grows with seq_len."""
    total_bytes = 2 * num_layers * num_kv_heads * head_dim * seq_len * bytes_per_val
    return total_bytes / 1e6

print(f"{'seq_len':>10} {'attn_pairs':>15} {'pairs_vs_prev':>15} {'kv_cache_mb':>12}")
prev_pairs = None
for seq_len in [1_000, 2_000, 4_000, 8_000, 128_000, 1_000_000]:
    pairs = attention_pair_count(seq_len)
    ratio = f"{pairs / prev_pairs:.1f}x" if prev_pairs else "--"
    kv_mb = kv_cache_size_mb(seq_len)
    print(f"{seq_len:>10,} {pairs:>15,} {ratio:>15} {kv_mb:>10.1f} MB")
    prev_pairs = pairs
# Notice: each 2x increase in seq_len produces roughly a 4x increase
# in attention pairs -- the quadratic cost the subtopic describes