Sparse Attention Patterns › Local Attention Windows

The most intuitive sparse pattern is local attention, where each token attends only to tokens within a fixed window around it. This pattern exploits the locality of language: consecutive words form phrases, sentences have local structure, and most grammatical dependencies span short distances.

Local attention is the simplest possible restriction you can impose on the attention matrix. Rather than building an elaborate sparse structure, you just draw a band along the diagonal and say: tokens can see their neighbors, but nothing beyond. Despite its simplicity, this approach works remarkably well for many tasks. Linguistic research has consistently found that the majority of syntactic dependencies, the head-dependent relationships that determine grammatical structure, span fewer than five words. Named entity recognition, part-of-speech tagging, and many types of sentiment analysis can be solved almost entirely with local context. Even for tasks that seem to require global reasoning, local attention in lower layers combined with full or near-full attention in upper layers often achieves excellent results, because early layers aggregate local evidence that later layers then reason about globally.

The hardware story for local attention is also appealing. Because each query attends to a contiguous segment of the key sequence, memory accesses are sequential and cache-friendly. This is in contrast to patterns like random sparse attention, where the irregular access pattern thrashes the cache and reduces effective throughput. Local attention can be implemented as a series of small, dense matrix multiplications on sliding windows, each of which maps cleanly to optimized GPU kernels.

To formalize local attention, we need to answer a simple question: which positions should a token be allowed to attend to? The intuition is straightforward. Imagine you're reading position 10 in a sequence. Local attention says you can "look" at positions 8, 9, 10, 11, and 12 if the window size is 2, but nothing beyond that range. The window creates a neighborhood around each position.

Let's define this precisely. For a window size $w$, each query at position $i$ attends to positions in the range $[i - w, i + w]$. This range includes:

• $w$ positions to the left (earlier in the sequence)
• The current position $i$ itself
• $w$ positions to the right (later in the sequence)

The total number of attended positions is $2w + 1$. Notice that this count is independent of sequence length $n$. Whether your sequence has 100 tokens or 100,000 tokens, each position still attends to exactly $2w + 1$ neighbors. This independence is what gives local attention its $O(n)$ complexity: $n$ positions, each computing $2w + 1$ attention scores, yields $n \cdot (2w + 1)$ total operations.

Now we need a mechanism to enforce this pattern. In transformer attention, we use an attention mask $M$ that modifies the attention scores before the softmax. The mask for local attention is:

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

where:

• $M_{ij}$: the mask value applied when query position $i$ attends to key position $j$
• $i$: the query position (which token is asking "what should I attend to?")
• $j$: the key position (a candidate token that might be attended to)
• $w$: the window size (the radius of the local neighborhood)
• $|i - j|$: the absolute distance between positions (how far apart are they?)

The mask works through the attention computation. Recall that standard attention computes:

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

When $M_{ij} = 0$, the attention score passes through unchanged. When $M_{ij} = -\infty$, adding negative infinity to any finite score produces negative infinity. The softmax function then converts $e^{-\infty} = 0$, effectively blocking query $i$ from attending to key $j$. This elegant mechanism lets us selectively disable attention connections without changing the core attention computation.

Local attention achieves significant sparsity even with generous window sizes. A window of 8 positions (17 attended positions per query) reduces computation by over 45% for a 32-token sequence. The savings grow with sequence length: for a 4,096-token sequence with window 256, sparsity exceeds 93%.

The optimal window size depends on the task and sequence characteristics. Here are key considerations:

• Linguistic dependencies: Most grammatical dependencies span fewer than 10-15 tokens. A window of 256-512 tokens covers most syntactic structures.
• Task requirements: Sentiment analysis might need only local context, while question answering may require longer-range connections.
• Computational budget: Larger windows provide more context but increase memory and compute proportionally.
• Layer depth: Some architectures use smaller windows in early layers and larger windows (or global attention) in later layers.

The relationship between window size and quality is not always monotonic, which can be counterintuitive. A very large window does not always outperform a smaller one, because forcing attention to consider many irrelevant positions can reduce the signal-to-noise ratio. The softmax normalization distributes probability mass across all attended positions, so attending to many low-relevance tokens necessarily dilutes the weight given to high-relevance ones. This means that for tasks with highly local structure, a tightly bounded window of 64 or 128 tokens can outperform a window of 1024 tokens on the same task.

In practice, window size is treated as a hyperparameter that you tune based on validation performance. A useful starting heuristic: set the window to roughly the length of the longest meaningful span in your data. For sentence-level tasks, 128 tokens is usually sufficient. For paragraph-level reasoning, 256 to 512 works well. For document-level understanding where cross-paragraph connections matter, you will need to supplement local windows with a global attention mechanism, which we cover later in this chapter when discussing combined patterns.