Sliding Window Attention › How Sliding Window Attention Works

To understand sliding window attention, we need to answer three questions: What does "local" mean mathematically? How do we enforce locality in the attention computation? And how does this change the algorithm's behavior? Let's build up the formalism step by step, starting from the intuition and arriving at a complete mathematical specification.

In standard attention, every token can attend to every other token. This creates a fully connected graph where information flows freely between all positions. But we observed that most meaningful connections occur between nearby tokens. The first step toward efficiency is formalizing what "nearby" means.

Consider token $i$ in a sequence. Which tokens should it attend to? The natural answer is: tokens within some fixed distance. If we set a window size $w$, we want token $i$ to attend only to tokens $j$ that are close enough. We measure closeness by position distance:

$$|i - j| \leq \lfloor w/2 \rfloor$$

where:

• $i$: the position of the query token (the one computing its representation)
• $j$: the position of the key token (a candidate for attention)
• $w$: the window size (total number of positions each token can attend to)
• $|i - j|$: the absolute distance between the two positions
• $\lfloor w/2 \rfloor$: half the window size (rounded down), giving the maximum distance in each direction

This formula defines a neighborhood around each token. With $w = 5$, token at position 10 can attend to positions 8, 9, 10, 11, and 12. The neighborhood extends $\lfloor 5/2 \rfloor = 2$ positions in each direction, plus the token itself. Token at position 3 can attend to positions 1, 2, 3, 4, and 5. Every token has the same sized window, centered on itself.

Why floor instead of exact division? Window sizes are typically odd (like 3, 5, or 257) so the token sits exactly in the middle. For even windows, the floor gives a slight asymmetry, attending to one more position on one side than the other. This rarely matters in practice.

Now we face a practical question: how do we tell the attention mechanism which positions each token should attend to? Standard attention computes a score between every query-key pair. We need a way to "zero out" the scores for positions outside the neighborhood.

The solution is an attention mask: a matrix that modifies the raw attention scores before softmax. The mask acts like a filter, allowing some connections and blocking others. For each pair of positions $(i, j)$, we assign a mask value:

$$M_{ij} = \begin{cases} 0 & \text{if } |i - j| \leq \lfloor w/2 \rfloor \\ -\infty & \text{otherwise} \end{cases}$$

where:

• $M_{ij}$: the mask value at position $(i, j)$
• $0$: no modification (allow attention)
• $-\infty$: block this connection entirely

Why these particular values? The mask gets added to the raw attention scores before softmax. Adding 0 leaves the score unchanged, preserving normal attention behavior for positions within the window. Adding $-\infty$ ensures that after the exponential in softmax, the weight becomes exactly 0:

$$\text{softmax}(\ldots + (-\infty)) = \frac{e^{-\infty}}{\sum} = \frac{0}{\sum} = 0$$

The blocked position contributes nothing to the output. In implementation, we use a large negative number like $-10^9$ rather than true infinity to avoid numerical issues, but the effect is identical.

With the mask defined, we can write the full sliding window attention computation. Start with the standard attention formula:

$$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V$$

This computes scores between all query-key pairs ($QK^T$), normalizes them into weights (softmax), and uses those weights to aggregate values. Sliding window attention inserts the mask before softmax:

$$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T + M}{\sqrt{d_k}}\right)V$$

where:

• $Q \in \mathbb{R}^{n \times d_k}$: the query matrix, with one row per token
• $K \in \mathbb{R}^{n \times d_k}$: the key matrix, with one row per token
• $V \in \mathbb{R}^{n \times d_v}$: the value matrix, containing information to aggregate
• $M \in \mathbb{R}^{n \times n}$: the sliding window mask
• $QK^T \in \mathbb{R}^{n \times n}$: the raw attention scores before masking
• $d_k$: the dimension of query and key vectors
• $\sqrt{d_k}$: scaling factor to prevent dot products from growing too large

The computation proceeds in four steps:

1. Compute raw scores: Multiply queries by keys to get $n \times n$ scores
2. Apply mask: Add $M$ to block positions outside each token's window
3. Normalize: Apply softmax row-wise to convert scores to weights
4. Aggregate: Multiply weights by values to get the output

After masking and softmax, each row of the weight matrix sums to 1, but the non-zero weights are concentrated in a band around the diagonal. Token 5 has non-zero weights only for tokens 3-7 (with $w=5$). Token 100 has non-zero weights only for tokens 98-102. The sparse pattern emerges from the mask, even though we computed all $n^2$ scores.

Several window configurations are possible. The most common is the symmetric window where each token looks an equal distance forward and backward:

The symmetric window suits bidirectional models like BERT where context flows in both directions. The causal window is essential for autoregressive models like GPT, where tokens must not attend to future positions. Asymmetric windows can be useful when past context is more informative than future context, or vice versa.

Understanding the complexity reduction is key to appreciating why sliding window attention matters. Standard attention computes $n \times n$ attention scores because every token attends to every other token. With a sliding window of size $w$, each token attends to at most $w$ positions, yielding approximately $n \cdot w$ attention scores instead.

The critical insight is that $w$ is a fixed constant (typically 128-512), independent of sequence length. This transforms the complexity:

$$O(n^2 d) \to O(n \cdot w \cdot d) = O(n \cdot d)$$

where:

• $n$: sequence length (the variable that grows with input size)
• $w$: window size (a fixed hyperparameter, constant with respect to $n$)
• $d$: model dimension (also fixed for a given model architecture)

Since both $w$ and $d$ are constants for a given model, the complexity is linear in $n$. This linear scaling means we can process sequences of arbitrary length with proportional, rather than quadratic, cost. A 10x longer sequence requires only 10x more computation, not 100x.