Sliding-Window Attention and the Reach of a Stacked Local Window

Take a stack of four layers in which each position attends to itself and the two positions before it, a window of three. Trace the field of position 9 backwards. After one layer it has seen positions 7 to 9. After two, 5 to 9, because each of 7, 8 and 9 brought its own three positions. After three, 3 to 9. After four, 1 to 9. The field spans $1 + 4 \times 2 = 9$ positions, and every output position gets the same width, shifted: position 10 after four layers has seen 2 to 10, so position 1 sits one layer beyond its field and a fifth layer would reach it. That multiplication of window by depth is why local attention is not merely a cost-saving approximation, and it is also why the approximation eventually fails.

The cost argument for a fixed window

Full attention costs $O(n^2 d)$ time and $O(n^2)$ memory per layer. A window of width $w$ centered on each query, or extending backward from it in the causal case, restricts each query to $w$ keys, so the cost becomes $O(n w d)$ time and $O(n w)$ memory. The quadratic term disappears entirely, and the per-token cost becomes independent of sequence length.

For $w = 4096$ and $n = 100{,}000$, the score matrix shrinks from $10^{10}$ entries to $4 \times 10^8$, a factor of 25. The saving is not a constant-factor optimization; it changes the asymptotics, which is why windowed attention appears in nearly every long-context architecture in some form. The remaining question is what the restriction does to the model’s ability to use the parts of the sequence it can no longer see directly.

The memory consequence is equally important. A windowed layer’s activation footprint is linear in $n$, so the batch size at a given sequence length stays constant rather than falling as $1/n$. Training at long context becomes a matter of compute rather than of fitting the intermediate tensors, and the KV cache for a windowed model is bounded at $w$ positions per layer rather than growing with generation length.

Reach grows linearly in depth, and that is the whole design

Define the receptive field of an output position after $L$ layers as the set of input positions that can influence it. With a window of $w$ positions per layer and no other path, the field grows by at most $w - 1$ positions per layer, so after $L$ layers it spans at most $L(w-1) + 1$ positions. The arithmetic is a union of intervals: layer 1 gives an interval of width $w$, layer 2 unions $w$ such intervals offset by up to $w$, and so on.

Two features of a transformer break the simple interval picture, and both help. The residual stream carries each position’s representation forward unchanged, so the interval at layer $\ell$ always contains the interval at layer $\ell - 1$; the union is nested rather than disjoint. And the feed-forward sublayer is position-wise, so it transforms content without moving it. Neither changes the width bound, but the nesting is what makes the reach an interval rather than a scattered set.

The bound is also not the whole story, because a stack can propagate information faster than one window per layer when a layer attends to a position that is itself a summary. If a token at the end of a document aggregates its window, and a later token attends to that aggregator, the second token indirectly sees the aggregator’s entire window. Chaining such aggregators gives geometric rather than linear growth in the ideal case: with $L$ layers, $w^L$ positions in principle, if every layer’s aggregator is attended by the next. In practice the growth is between the two, because attention weights are soft and the aggregation is lossy.

That gap between the linear bound and the geometric possibility is where the design work happens. Architectures that add a small number of global tokens, positions that attend to everything and are attended by everything, get reach in one layer at a cost of $O(n)$ extra work per global token. With $G$ global tokens and window $w$, per-token cost is $O((w + G) d)$, and the reach after one layer includes all $G$ global positions, each of which has seen the whole sequence. That is the Longformer construction, and its cost is the $G$ extra rows and columns in the score matrix. The alternative is a sparse pattern with a few strided connections, where every $k$-th position attends globally, which gives reach that grows with the stride rather than requiring dedicated tokens. The BigBird analysis formalizes both and shows that a combination of a window, a set of global tokens, and a set of random connections preserves the properties that make full attention expressive, in the sense of being able to approximate the full attention matrix.

import numpy as np

def window_mask(n, w, causal=True, globals=()):
    """Boolean (n, n): True where query i may attend to key j."""
    i = np.arange(n)[:, None]
    j = np.arange(n)[None, :]
    if causal:
        local = (j <= i) & (j > i - w)          # backward window only
    else:
        local = np.abs(i - j) < w // 2          # centred window
    if not globals:
        return local
    g = np.zeros(n, dtype=bool)
    g[list(globals)] = True
    return local | g[None, :] | g[:, None]      # globals see and are seen

The reach formula is not the effective context

A model with 32 layers and a window of 4,096 has a formal reach of about 131,000 positions. It does not follow that the model uses information from 131,000 positions away, and the distinction between reach and effective context is the most important thing to get right about windowed attention.

The reason is that propagation is lossy. Each hop passes information through a softmax-weighted average and a residual addition; the signal is mixed with whatever else the intermediate position attended to. A chain of 32 hops multiplies the mixing, and the information from the far end arrives attenuated relative to the local content. The formal bound says the far position can influence the output; it says nothing about whether the learned weights route it.

This is why effective context is measured rather than assumed. A probe that places a single relevant fact at a controlled distance from the query tests the propagation directly, and the expected shape of the result follows from the mechanism: within one window the query reads the fact directly, while beyond it the fact must survive one or more hops, and each hop is a weighted average that mixes it with whatever the intermediate position also attended to. Tasks that require exact retrieval of a distant token, copying a string from position 1 at position 50,000, are the hardest case, because exact retrieval tolerates no attenuation. Tasks that require a summary or a topic are easier, because the summary can be carried by an aggregator token that many positions attend to.

The practical implication is that the window width should be chosen against the distance distribution of the task, not against the maximum context length. A window that covers the typical distance between a pronoun and its antecedent, or between a definition and its use, captures most of the benefit. Widening beyond that buys formal reach that the model may not learn to use, at linear cost.

Causal windows and the cache

In a decoder, the window extends backward from each query, so position $i$ attends to $[i - w + 1, i]$. The KV cache then holds only the last $w$ positions: older keys can be discarded outright, because no future query will attend to them. This bounds decode-time cache at $w$ per layer per sequence regardless of how long the generation runs, which is the property that makes unbounded streaming generation possible at all.

The discard is exact, not approximate, for a pure windowed layer: a position that falls out of every future query’s window is provably unused. That exactness is what distinguishes a windowed cache from an eviction policy applied to full attention. Eviction has to guess which positions will not be needed; a window proves it.

Two implementation details matter. First, the cache becomes a ring buffer: position $i$ overwrites slot $i \bmod w$, so the array size is fixed and no reallocation occurs. The kernel must handle the wrap, which means the keys for a query are not contiguous in memory but split across the buffer boundary. A ring of $w$ positions holds at most two contiguous runs, so the kernel processes two segments rather than one, a small complication that is the reason some implementations allocate $2w$ and keep a duplicate region.

Second, layers with different window widths need different cache sizes, and a stack that alternates local and global layers needs the global layers’ cache to grow without bound while the local ones stay fixed. Interleaving is the usual compromise: most layers local, a few global, with the global layers’ cost amortized over the local ones. The resulting cache is dominated by the global layers at long generation lengths, which is why the ratio of global to local layers is a memory decision as much as a quality one.

Where the window interacts badly with the rest of the block

Three interactions are worth naming because they are not obvious from the cost analysis.

Rotary embeddings and windows interact through frequency aliasing. A window of 4,096 positions keeps every query within a range where the slow coordinates of the rotation have not wrapped, so the relative encoding is unambiguous inside the window. Push the window wider and the slowest coordinates begin to alias, exactly as described in rotary position embeddings and relative offsets, and the model’s ability to distinguish distances inside the window degrades. A window chosen to match the encoding’s usable range avoids the problem; a window chosen purely for reach may not.

Grouped-query attention and windows compound. Sharing key heads cuts the cache by $h/g$; windowing bounds it at $w$. Together the cache is $2 L w g d_k s$, which for 32 layers, $w = 4096$, $g = 8$, $d_k = 128$, 16-bit is about 512 MiB per sequence, small enough that many sequences fit, and the binding constraint moves from cache to compute. The combination is covered in grouped-query attention and KV cache sharing.

Tiled kernels and windows interact through block alignment. A window whose width is not a multiple of the kernel’s key block size leaves a partially covered block at the window edge, which needs per-element masking on every query block rather than only on the diagonal. Choosing $w$ as a multiple of the block size removes that cost entirely. The block-skipping logic is in IO-aware attention tiling; the point is that the window width is a kernel parameter as well as a modelling one.

The last interaction is with the positional encoding’s role in masking. A causal mask already restricts each position to a prefix; a window restricts it further to a suffix of that prefix. The composition is a band, and the band is what the model actually learns to use. A model trained with a window sees a band at every layer and learns weights suited to it; evaluating the same model with a wider window at inference presents attention patterns it never saw, and the weights do not automatically exploit the extra range. This is why window extension at inference is not equivalent to training at the wider window, and why the architectures that support long context either train at that length or use a mechanism whose structure the model was trained with, such as global tokens or a sparse pattern with strided links.

The cost of getting this wrong is not a crash. The model runs, produces fluent output, and quietly ignores the distant context it was given. That failure is harder to detect than an out-of-memory error and is the reason effective-context measurement, rather than nominal context length, is the number that matters.