From all-to-all to a local window

Standard causal attention lets query position i attend to every key position j ≤ i. The score matrix QK^T is therefore a full lower triangle: N queries times up to N keys. Sliding-window attention keeps causality but adds a floor: position i may attend only to positions in the window [i − w + 1,  i] — itself and the w − 1 tokens immediately before it. Anything older than w steps is masked out.

Concretely, the attention mask becomes a band of width w along the diagonal instead of a solid triangle. A token far along the sequence sees a fixed-size sliver of recent context, never the whole history. This is exactly the pattern Mistral 7B ships with (w = 4096). We’ll use the convention that the window includes the current token, so the effective look-back is w − 1; the off-by-one washes out of every formula below, so we write reach as ≈ w and move on.

Advertisement

The complexity math: O(N·w) instead of O(N^2)

Full attention forms an N × N score matrix and does a weighted sum over N values per query. Counting the query-key dot products (each of dimension d) and the value aggregation, the work is Θ(N^2 · d) in compute and, if materialized naively, Θ(N^2) in memory for the scores.

full:     each query attends to  ≤ N keys  →  Σ_i i  ≈  N^2/2  pairs
window:   each query attends to  ≤ w keys  →  Σ_i min(i,w)  ≈  N·w  pairs

compute:  O(N^2 · d)   →   O(N · w · d)
scores:   O(N^2)        →   O(N · w)

The key move is that w is a constant, not a function of N. Once the sequence is longer than the window, adding more tokens grows the cost linearly — each new token does a bounded O(w) amount of attention work rather than O(N). So prefilling a long prompt scales as O(N·w) overall. For N ≫ w the saving is a factor of N / w: at N = 32K and w = 4K that is an 8× cut in attention compute, and the gap only widens as context grows.

Advertisement

The rolling-buffer KV cache

The second win is about memory during decoding, which is a different quantity from the compute above. In full attention the KV cache stores the key and value vectors of every past token, so it grows without bound: O(N) entries per layer, and for long chats the cache, not the weights, dominates memory.

Under a window of w, token i can never be attended to again after position i + w — it has fallen out of every future window. So there is no reason to keep it. A rolling (ring) buffer of exactly w slots suffices: token i is written to slot i mod w, overwriting token i − w, which is now invisible to everyone.

cache_k[i % w] = k_i      # overwrite token i-w, no longer in any window
cache_v[i % w] = v_i
# cache size is fixed at w, independent of sequence length N

The cache footprint is now O(w) per layer — constant in N. A million-token conversation uses the same KV memory as a w-token one. That is what makes indefinitely long or streaming generation feasible on modest hardware.

Why depth buys reach: the receptive-field derivation

A single windowed layer is myopic — it sees w tokens. The magic is that stacking layers compounds reach, exactly like the receptive field of a stacked convolution. Consider what information can reach token i’s hidden state layer by layer.

layer 1:  h(i) mixes tokens  [i-(w-1), i]              reach ≈ 1·w
layer 2:  h(i) attends h(i-(w-1)), which already
          carried info from  i-2(w-1)            reach ≈ 2·w
   ...
layer L:  reach ≈ L·(w-1)  ≈  L·w  tokens back

The argument is inductive. After layer 1, h(i) encodes the window [i−(w−1), i]. At layer 2, h(i) attends to h(i−(w−1)), but that neighbor already summarized tokens back to i−2(w−1). Each windowed layer extends the transitive reach by another w−1 tokens, so after L layers the effective receptive field is ≈ L·w. Information doesn’t leap the window in one hop; it flows through overlapping windows, one layer at a time, like a signal down a chain.

A worked example: Mistral-style numbers

Take Mistral 7B’s configuration: window w = 4096 and L = 32 layers. The theoretical receptive field is L · w = 32 × 4096 = 131,072 tokens — about 128K. So even though no single layer looks past 4K tokens, the top of the stack can, in principle, be influenced by something 128K tokens back.

window            w   = 4096
layers            L   = 32
receptive field   L·w = 131,072 tokens  (~128K)

at N = 32,768 tokens:
  full  attn pairs  ≈ N^2/2   ≈ 5.4 × 10^8
  window attn pairs ≈ N·w    ≈ 1.3 × 10^8   (~4× fewer here)
  KV cache (per layer):  32,768  →  4,096   (8× smaller)

Two cautions on reading these numbers. The receptive field is a maximum reach, not a guarantee that information actually survives 32 hops — signal can attenuate along the chain. And the compute ratio grows with N: at N = 32K the sequence is only 8 windows long, so the gap is a few×; push N to 256K and the same window yields a ~30× compute saving while the cache stays pinned at 4K.

Sliding window vs full attention: what you trade

Full attention’s advantage is exactness: any token can directly, in a single layer, pull from any other, so a fact stated at token 5 is one hop from a query at token 50,000. Sliding-window attention gives that up. Long-range dependencies must travel through the layer stack, which costs depth and risks attenuation, and any single layer is blind beyond its band.

What you get in return is the linear-in-N compute and constant KV cache above — the two properties that make long context affordable. The empirical bet, borne out by Mistral and similar models, is that most useful dependencies are either local or reachable within L·w through depth, so the quadratic exactness is largely wasted spend. Full attention stays the right default only when sequences are short (below w the window mask is a no-op) or when precise arbitrary-distance retrieval in a single layer genuinely matters and you can pay for it.