Sliding-window attention makes one small change to the attention mask and gets two big wins for free. Instead of letting every token attend to every earlier token — the all-to-all pattern that costs O(N^2) — it restricts each token to a fixed window of the w most recent tokens. Attention compute drops to O(N·w), linear in sequence length, and the key/value cache stops growing: a rolling buffer of w slots holds everything a token can legally see. The surprise is that locality per layer does not mean the model is short-sighted. Stacking windowed layers compounds the reach, so a token deep in the network effectively sees roughly L·w tokens back. This piece derives the complexity, proves the receptive-field growth, works a concrete Mistral-style example, and shows where sliding windows sit relative to full attention and to global/sparse variants — plus the attention-sink trick that keeps the whole thing stable when you stream past the window.
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.
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.
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 NThe 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 backThe 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.
Sliding window vs global and sparse attention
Sliding windows are the simplest member of a family of sparse-attention patterns that all trade all-to-all for a cheaper connectivity graph. The distinction is which extra edges they add back:
| Pattern | Connectivity | Cost |
|---|---|---|
| Full | every token → every earlier token | O(N^2) |
| Sliding window | local band of width w | O(N·w) |
| Longformer | window + a few global tokens seen by all | O(N·w + N·g) |
| BigBird | window + global + random edges | O(N·(w+g+r)) |
| Dilated window | window with gaps → wider reach, same count | O(N·w) |
Global tokens (Longformer, BigBird) are a small set — a [CLS] slot, question tokens — that attend to everything and are attended by everything, restoring one-hop long-range links for a handful of positions at O(N·g) extra cost. Dilated windows skip tokens to widen reach without more edges, mimicking dilated convolutions. Pure sliding window adds none of these; it leans entirely on depth for range, which keeps the kernel simple and the cache a clean ring buffer.
Attention sinks and StreamingLLM
A subtle failure appears when you try to run a model past its cache size by naively keeping only the last w tokens. Quality collapses — and the reason is the softmax. Trained attention learns to route excess probability mass onto the first few tokens of the sequence, which act as a no-op ‘sink’ for attention it doesn’t need. Evict those initial tokens and the softmax has nowhere to dump the surplus, so the distribution distorts and generation degrades.
StreamingLLM fixes this by pinning a handful of attention-sink tokens (often just the first 4) permanently in the cache alongside the rolling window of recent tokens. The sinks absorb the leftover mass; the window supplies local context; together they let a model stream millions of tokens with a bounded cache and stable quality.
Note the division of labor: Mistral’s rolling buffer works out of the box because the model is trained with the window, so the sink behavior lives inside the window. StreamingLLM is an inference-time patch for pushing any windowed model beyond the length it cached — keep a few sinks plus the last w, and the buffer never overflows.
Practical implications and pitfalls
For CPU and small-model inference, the constant KV cache is the headline: memory no longer scales with conversation length, so a long-running assistant fits a fixed, predictable footprint. The linear prefill helps too, but remember prefill is still O(N·w) — a huge prompt isn’t free, it’s just no longer quadratic.
The pitfalls are mostly about over-trusting the window. First, L·w is a ceiling on reach, not a promise; a retrieval task needing a crisp pointer from token 5 to token 100K may underperform even though 100K is nominally inside the receptive field. Second, the window must match training — shrinking w at inference changes the mask the model expects and hurts quality. Third, the rolling buffer only self-manages if you never need evicted tokens back; the moment you want true global lookup you need sinks, global tokens, or a hybrid layer, not a plain window. Within its contract, though, it is one of the cleanest wins in efficient transformers: a one-line mask change that turns quadratic cost and an unbounded cache into linear cost and a fixed ring buffer.