Full self-attention makes every one of N tokens look at all N others, so cost and memory blow up like O(N²) — double the context and you quadruple the bill. Most of those pairs are wasted: language is overwhelmingly local, and a token rarely needs to attend directly to something thousands of positions away. Sliding-window attention (Longformer, Mistral, BigBird) makes each token attend only to the previous W tokens — a thin diagonal band instead of a full square — dropping the cost to O(N·W), linear in sequence length. And you don't lose long-range reach; you earn it with depth. I built a demo that draws the band and the growing receptive field live. Here's how it works.
One rule decides every cell
The attention matrix has queries as rows and keys as columns; a filled cell means "this query may attend that key." Sliding-window keeps a cell only if the key is inside the window and (for a decoder) not in the future.
function allowed(i, j){
if (causal && j > i) return false; // no peeking at the future
const dist = i - j; // how far back key j is
return dist >= 0 && dist <= W - 1; // inside the local window?
}
That's the whole band: query i sees keys [i−W+1 … i], a fixed W-wide slice.
Mask, then softmax over the window
You build the band as a boolean mask, set every out-of-window score to −∞ before the softmax, and each row normalizes over just its window — a weighted blend of W neighbours instead of N.
if (!mask[i][j]) scores[i][j] = -Infinity; // block out-of-window pairs
const weights = scores.map(softmax); // rows sum to 1 over the window
The saving: O(N²) → O(N·W)
Counting filled cells, full attention is N² and the band is roughly N·W, so when W ≪ N the win is dramatic. At N=32k, W=4k that's ~1.0B pairs down to ~131M — about 8× less; at N=100k, W=4k the window computes ~4% of full attention. The demo's default N=24, W=4 already shows a 6× gap. Slide W up to N and the band fills the whole triangle — you're back to full attention with no saving, which is a nice sanity check that the mask is doing exactly what it claims. As a bonus, a windowed decoder's KV-cache becomes a fixed-size rolling buffer of the last W entries — O(W) memory, streamable to unbounded length regardless of how much you've already generated.
Depth buys distance — ~L·W
The obvious objection: if a token only sees W back, how does it ever learn long-range structure? The same way a stack of small convolutions grows a large receptive field. Layer ℓ's window feeds layer ℓ+1's window, so information hops one window further per layer.
const field = Math.min(N, 1 + L * (W - 1)); // ≈ L·W <- reach from depth
So L layers with window W behave as if the context were ~L·W, while every layer stays cheap at O(N·W). Mistral's 4k window over 32 layers reaches far beyond 4k tokens.
Variants: dilated windows and global tokens
Two extensions push the reach further for the same cost. A dilated window keeps W keys but spaces them by d, so it spans (W−1)·d + 1 tokens — different heads use different dilations (Longformer). A few global tokens (like a [CLS] or task token) attend to and are attended by everyone, a full row-and-column, so any token can reach any other in two hops. Local window plus global tokens is exactly the Longformer/BigBird recipe.
Sliding-window attention is a sparse-approximate method: it changes which pairs are computed. That makes it complementary to FlashAttention, which computes exact full attention with a smarter IO pattern — it changes how, not which — so real systems stack them: Mistral runs a windowed pattern with a Flash kernel underneath.
The lesson I took away: quadratic attention isn't a law of nature, it's a default. Restrict each token to a local band, lean on depth to carry information across those bands, and you get linear cost with long-range reach.
Drag W, N and the layer count, and watch the band thin out while the receptive field grows:
https://dev48v.infy.uk/ai/days/day48-sliding-window-attention.html
Top comments (0)