warming up your workspace

How a million-token context window works, when attention is quadratic

The context window is the marquee spec of 2026's language models: a million tokens, sometimes more, enough to drop an entire codebase, a legal case file, or a small library of books into a single prompt. This should be impossible. The transformer's attention mechanism, the thing that lets a model relate each word to every other word, has a cost that grows as the square of the input length. Double the context and you quadruple the work; a million tokens of naive attention would need a trillion operations per layer. So either the labs repealed a law of computer science, or they changed the attention. They changed the attention. Build both versions and see how.

The one idea

Standard self-attention compares every token to every other token. For n tokens that is an n by n grid of comparison scores, which is why the cost is n squared. That grid is the wall. The way through is to notice that most tokens do not need to attend to all the others. A word usually cares most about its neighbors and a few far-off anchors, not every one of a million tokens equally. So you compute only the scores that matter, a window of nearby tokens, plus a handful of global ones, and skip the rest of the grid. That turns n squared into roughly n times a small constant, which is linear, and linear is what makes a million tokens affordable.

Build the wall

Full attention is one matrix multiply that forms the whole n by n score grid:

import numpy as np

def full_attention(X):
    d = X.shape[-1]
    scores = X @ X.T / np.sqrt(d)             # (n, n) grid -- the quadratic cost
    return softmax(scores) @ X, scores.size

Now build the linear alternative. Sliding-window attention lets each token attend only to the w tokens just before it, so the number of scores is about n times w instead of n squared:

def windowed_attention(X, w=64):
    n, d = X.shape
    out = np.zeros_like(X); computed = 0
    for i in range(n):
        lo, hi = max(0, i - w), i + 1          # only the last w neighbors
        s = X[i] @ X[lo:hi].T / np.sqrt(d)
        out[i] = softmax(s) @ X[lo:hi]
        computed += (hi - lo)
    return out, computed

Proof: watch the two costs diverge

Count the attention scores each approach computes as the sequence grows:

 seq len    full scores   windowed(w=64)    ratio
     256         65,536           14,560       5x
    1024      1,048,576           64,480      16x
    4096     16,777,216          264,160      64x
   16384    268,435,456        1,062,880     253x

Full attention's score count quadruples every time the length doubles: 65 thousand, one million, 16 million, 268 million. The windowed version merely doubles. By 16 thousand tokens the gap is already 253x, and it keeps widening. Extrapolate to the headline number:

at n=1,000,000: full needs 1,000,000,000,000 scores; windowed needs ~64,000,000
that is 15,625x more work for full attention

A trillion versus 64 million. That factor of fifteen thousand is the difference between "impossible" and "shipping". The million-token window is not a bigger machine brute-forcing the quadratic cost; it is a smarter attention pattern that refuses to pay it.

Three details that matter:

  • Pure windowing loses long-range links, a token cannot see something a million positions back if it only looks at its 64 neighbors. Real long-context models fix this by mixing window attention with a few global tokens that everyone can see, and by alternating local and sparse-global layers, so information still travels the full length in a few hops.
  • The window is a quality-cost dial. A wider window captures more but costs more; the art is choosing patterns that keep the information the task needs while dropping the scores it does not.
  • Separately, models cache the intermediate results for tokens already processed so each new token is cheap to add, an orthogonal optimization that makes generating into a long context fast, on top of making reading it affordable.

Where this shows up

Every long-context model, Gemini's million-token window, the open long-context Llama and MiniMax lines, is built on some blend of these ideas: sliding windows, sparse global attention, and hardware-aware kernels like FlashAttention that compute exact attention without ever storing the full n by n grid. The research on efficient attention, Longformer, BigBird, and their descendants, is the reason the context window stopped being a hard ceiling and became a spec that keeps climbing.

If you want to build attention itself, then the sparse and windowed variants, and the transformer they live inside, that is the path the nlp track on IWTLP constructs from scratch.

Sources