Sparse Attention Patterns: Local, Strided

Standard attention computes pairwise scores between all tokens, creating an $n \times n$ attention matrix where $n$ is the sequence length. This quadratic scaling becomes prohibitively expensive for long sequences. A sequence of 1024 tokens requires about one million attention score computations. Scale that to 8192 tokens, and the count jumps to 67 million. For 32768 tokens, you need over a billion. Even on the most powerful GPUs available today, full attention at these lengths is slow enough to make training impractical and inference unusable in real-time applications.

Sparse attention offers a principled solution: instead of attending to every position, each token attends only to a carefully chosen subset. The key insight is that most attention weights in practice are small, meaning many token pairs contribute little to the final representation. By restricting attention to positions that matter most, sparse patterns achieve near-linear complexity while preserving the model's ability to capture important relationships.

To appreciate why this works, think about how you read a paragraph. When processing the word "they" in the middle of a sentence, you scan back a few words to find the referent, not the entire document. When you encounter a technical term, you look at the surrounding clause for context, not at paragraphs from pages ago. The same intuition applies to transformer attention: the information that matters most is usually nearby, with occasional long-range dependencies that require targeted access rather than exhaustive search.

This chapter explores the fundamental sparse attention patterns that form the building blocks of efficient transformers. We will implement local windowed attention, strided patterns, and block-sparse attention, then combine them into hybrid approaches used by models like Sparse Transformer and Longformer, along with BigBird. Along the way we will analyze the complexity guarantees each pattern provides, examine how information flows through sparse attention layers, and understand the hardware realities that make some patterns more practical than others.

The efficiency gains from sparse attention are not merely academic. They directly determine what problems language models can solve. A model that can only process 512 tokens cannot read a research paper in one pass. A model capped at 2048 tokens struggles with long-form code files. Sparse attention, when designed carefully, lifts these limits by orders of magnitude while maintaining most of the expressive power of full attention.

Before diving into specific patterns, let's understand why sparsity works. In natural language, most dependencies are local: a word is most strongly influenced by nearby words. Long-range dependencies exist but are relatively rare. Consider the sentence "The cat that the dog chased ran away." The verb "ran" primarily depends on "cat" (its subject), not on every intervening word. A sparse attention pattern that captures this key dependency while ignoring irrelevant pairs can achieve similar quality to full attention at a fraction of the cost.

The sparsity principle rests on an empirical observation that researchers confirmed early in the development of transformers: trained attention heads are rarely uniformly distributed. When you inspect the attention weight matrices of a trained BERT or GPT model, you find that most entries are very close to zero. The softmax distribution is concentrated, not flat. Some query-key pairs receive nearly all the probability mass, while hundreds of other pairs share a tiny residual. This concentration reflects the structure of language: meaning is local, syntactic dependencies are bounded, and truly global relationships are rare.

Think of a full attention matrix as a complete graph where every node is connected to every other node. A sparse attention pattern is like a sparser graph where each node connects only to its immediate neighbors and a small set of "highways" for long-distance travel. The graph does not need to be complete for information to flow everywhere. If you choose the sparse connections carefully, you can guarantee that any two nodes are still connected through a short path. The transformer's depth, its multiple stacked layers, does the rest: information missing from one layer's direct connections can be picked up indirectly through intermediate positions in subsequent layers.

Let's visualize how attention weights are distributed in practice to motivate sparsity.

The analysis reveals a key insight: attention weights are highly concentrated. Most of the attention mass falls on a small number of positions per query, while the majority of positions receive negligible weight. This natural sparsity suggests we can skip computing many attention scores without significantly affecting the output.

Notice that even our simulated distribution, which uses a simple exponential decay rather than real transformer weights, shows dramatic concentration. The top 10 positions per query capture the vast majority of total attention mass. In real trained transformers, the concentration is often sharper because the model learns to focus attention even more precisely through training. This observation is what gives researchers confidence that sparsity won't break the model: if you only skip positions that would have had near-zero weight anyway, the output changes very little.

In practice, this principle has a direct implication for engineering. You do not need a perfectly optimal sparse mask that always selects exactly the positions that would have had high weight. You need a mask that reliably covers the positions that matter for most inputs. Local attention, strided attention, and block-sparse attention are all heuristics in this sense: they do not know in advance which positions a given query will want to attend to, but they bet that nearby positions and a few strategic long-range anchors will cover most of the important cases.

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:

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:

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.

The log-log plot reveals the linear relationship between sequence length and speedup. Doubling the sequence length approximately doubles the speedup, regardless of window size. Smaller windows provide greater speedups but capture less context.

While local attention captures nearby dependencies, it cannot directly model long-range relationships. Strided attention addresses this by having each position attend to positions at regular intervals throughout the sequence. This creates "highways" for information to flow across long distances.

Local attention's weakness becomes apparent when you consider a task like coreference resolution at the document level. Suppose a legal document uses "the plaintiff" in paragraph 1 and refers back to it as "she" in paragraph 15. With a local window of 256 tokens, these two mentions may be too far apart to be directly connected in any single attention layer. Local attention simply cannot bridge the gap without multiple intervening layers, and even then, the signal can degrade as it passes through many intermediate representations.

Strided attention solves this by designating certain positions as hubs, or broadcast points, that every other position can access directly. Think of it as adding express train stops to a transit system. The local bus (local attention) handles short trips within the neighborhood, while the express train (strided attention) connects distant neighborhoods through major stations. Even if you need to take a two-hop journey, you can reach any station in the system in at most two connections.

Local attention has a fundamental limitation: it cannot see beyond the window. Position 0 can never directly attend to position 1000, no matter how many attention scores we compute within that single layer. To bridge long distances, we need a different pattern.

The key insight behind strided attention is the concept of hub positions. Think of hubs like train stations in a transit network. Not every location has a direct connection to every other location, but major stations connect to many destinations. Similarly, strided attention designates certain positions as hubs that all other positions can access.

For a stride $s$, we designate every $s$-th position as a hub. With stride $s = 4$, positions 0, 4, 8, 12, 16, ... become hubs. Each query position can attend to:

1. All hub positions: Every position can reach the hubs, creating information highways across the sequence
2. Every position from a hub: Hub queries attend to the full sequence, so they can gather and relay information
3. Itself: Self-attention is always preserved so each token can access its own representation

This creates a two-hop connectivity pattern. Consider positions 3 and 97 in a sequence. They cannot directly attend to each other (neither is a hub for typical stride values). But in layer 1, position 3 attends to hub 4, and position 97 attends to hub 96. In layer 2, both hubs can attend to each other (since hubs attend to all other hubs), and information flows between them. After just two layers, any two positions are connected.

The formal mask for strided attention is:

where:

• $M_{ij}$: the mask value when query $i$ considers attending to key $j$
• $s$: the stride parameter (the spacing between hub positions)
• $j \mod s$: the remainder when dividing $j$ by $s$. When this equals 0, position $j$ is a hub
• $i \mod s = 0$: the global-hub condition. Hub queries can gather information from every position
• $j = i$: the self-attention condition. This keeps diagonal connectivity

The first condition ($j \mod s = 0$) produces vertical stripes because every query attends to the same hub columns. The second ($i \mod s = 0$) produces horizontal stripes because each hub query attends to the full sequence. The final condition adds the self-attention diagonal. Together, these conditions guarantee two-hop global information flow while retaining $O(n^2/s)$ rather than $O(n^2)$ attention pairs.

Strided attention creates a distinctive grid: vertical columns show that all queries attend to the hubs, horizontal rows show that hub queries attend to every position, and a diagonal preserves self-attention. These bidirectional hub connections let information propagate across the sequence in two hops.

A key property of strided attention is the maximum "hop distance" between any two positions. With stride $s$:

• Any position is at most $s/2$ steps from a hub position
• In one attention layer, information can travel to a hub
• In the next layer, it can travel from the hub to any other position

This means any two positions are connected within 2 layers, regardless of their distance in the sequence. This is significantly better than local attention, which requires $O(n/w)$ layers to connect distant positions, where $n$ is the sequence length and $w$ is the window size.

The two-hop connectivity guarantee is powerful, but it comes with an important caveat: it only guarantees that information can flow, not that the model will learn to use those connections effectively. The hub positions must compress information gathered from the full sequence into useful intermediate representations. If a hub is not semantically relevant to the query being resolved, the two-hop path can carry noise rather than signal. This is one reason why strided attention tends to work better as part of a combined pattern alongside local attention, rather than as a standalone approach. Local attention handles the high-density short-range dependencies, while strided attention provides the long-range connectivity backbone.

Notice also that the choice of which positions become hubs is fixed at design time in basic strided attention. Positions 0, $s$, $2s$, and so on always serve as hubs regardless of what content they contain. This rigidity is a trade-off: it makes the pattern simple and predictable, but it means the hubs are not adaptively chosen based on content. Some tokens are naturally more "important" than others (section headers in a document, named entities, clause boundaries), but strided attention has no way to recognize and exploit this importance. The Longformer architecture addresses this limitation by introducing learnable global tokens that can attend to and be attended by all positions, giving the model a way to designate important positions dynamically.

The visualization shows how reachability expands with depth. After layer 1, vertical and horizontal stripes show the bidirectional hub connections, while the diagonal preserves self-access. After layer 2, the matrix is fully connected. This shows that any position can reach any other position through an intermediate hub.

Block-sparse attention groups positions into blocks and defines attention patterns at the block level. This approach is particularly hardware-friendly because modern GPUs and TPUs are optimized for matrix operations on contiguous memory blocks.

To understand why block structure matters, you need to understand something about how GPUs execute operations. A GPU is organized around a hierarchy of processing units: threads, warps (groups of 32 threads), and thread blocks (groups of warps). When you launch a matrix multiplication, the GPU divides the work into tiles that map to these hardware units. The key constraint is that all threads in a warp must execute the same instruction at the same time, a property called lock-step execution. If some threads are doing useful work while others are idle because their data was masked out, you are wasting hardware capacity.

Arbitrary sparse patterns suffer from this problem. If you randomly mask out 90% of an attention matrix, the remaining 10% is scattered unpredictably across the matrix. When you implement this as a GPU kernel, many warps end up executing mixed instructions: some threads are computing real values while others are computing masked-out positions. The theoretical 10x speedup from 90% sparsity does not materialize in practice because the hardware cannot efficiently exploit irregular sparsity.

Block-sparse attention avoids this problem by ensuring that the sparse structure aligns with hardware boundaries. Instead of masking individual elements, you skip entire blocks. A block-skipped operation means the entire warp either executes or does not execute together, achieving full hardware utilization on the blocks that do execute.

The patterns we've seen so far, local and strided, define attention at the level of individual positions. Block-sparse attention takes a different approach: it groups positions into contiguous blocks and defines attention at the block level. This abstraction has a practical motivation. Modern GPUs are designed to process data in aligned, contiguous chunks. By organizing attention into blocks that match hardware execution units, we can achieve theoretical speedups in actual wall-clock time.

Imagine dividing a 1024-token sequence into blocks of size $b = 64$. This creates $1024/64 = 16$ blocks. Instead of asking "which of 1024 positions can position $i$ attend to?", we ask "which of 16 blocks can block $B_i$ attend to?" This coarser-grained question has fewer possible answers, and each answer involves a dense $64 \times 64$ matrix operation that GPUs handle efficiently.

The key parameters for block-sparse attention are:

• $b$: the block size (number of positions per block)
• $k$: the number of blocks each query block attends to

If we select $k$ blocks for each query block, the complexity analysis proceeds as follows:

1. Number of query blocks: The sequence divides into $n/b$ blocks
2. Attention per query block: Each block attends to $k$ other blocks
3. Operations per block pair: Computing attention between two blocks of size $b$ requires $b \times b = b^2$ score computations

Multiplying these together:

When $k$ and $b$ are constants independent of $n$, this expression is linear in sequence length. The quadratic term has vanished. Even better, each $b \times b$ block attention can use highly optimized dense matrix multiplication routines, achieving near-peak GPU utilization.

Block-sparse attention provides a hardware-efficient abstraction for implementation. The regular block structure maps directly to GPU thread blocks, enabling efficient parallel execution with minimal memory overhead.

The advantage of block-sparse attention goes beyond theoretical complexity. Modern GPUs achieve peak performance when operating on aligned, contiguous memory blocks. Random sparse patterns, while mathematically equivalent, suffer from irregular memory access patterns that underutilize hardware.

Block-sparse attention can be 3x or more efficient than random sparse patterns at the same sparsity level. This hardware awareness matters for practical implementations and explains why production models favor structured sparsity.

The choice of block size is a real engineering decision with trade-offs. Smaller blocks give you finer-grained control over which pairs attend to each other, but they reduce the size of each dense matrix multiplication, making it harder to achieve peak GPU utilization. Larger blocks maximize GPU efficiency but coarsen the sparsity pattern: you either attend to an entire block of tokens or none of them, which can include irrelevant tokens or exclude relevant ones at the block boundary. A block size of 64 threads is a common practical choice because it aligns with GPU warp sizes and provides a good balance between granularity and throughput.

Block-sparse attention does not inherently specify which blocks to attend to. The diagonal and tridiagonal patterns we implement here are just two examples. In practice, you can combine block-sparse structure with any higher-level pattern: local attention at the block level (attend to the current block and its neighbors), strided attention at the block level (attend to every $k$-th block), or even content-adaptive selection where the blocks to attend to are determined dynamically based on query-key similarity scores computed at a coarser granularity. The Routing Transformer and Reformer use variations of this last idea, selecting blocks based on locality-sensitive hashing rather than fixed structural patterns.

Real-world efficient attention mechanisms combine multiple patterns to balance local context, global reach, and computational efficiency. The Sparse Transformer paper introduced the idea of factorizing attention across multiple heads, with different heads using different patterns.

The motivation for combining patterns comes from recognizing that no single sparse pattern dominates all task types. Local attention excels at capturing short-range syntactic structure but fails at long-range coreference. Strided attention provides long-range connectivity but may miss fine-grained local interactions between adjacent tokens. Block-sparse attention is hardware-efficient but requires careful alignment of content with block boundaries. By combining patterns, you can cover each other's blind spots.

The combination can happen in two fundamentally different ways. The first approach takes the union of two masks: a position pair is allowed if it is allowed by either pattern. This gives you the benefits of both patterns in every head. The disadvantage is that the combined mask is denser than either individual mask, increasing computation. The second approach assigns different patterns to different heads: local heads capture nearby context while strided heads capture long-range context. This keeps each head sparse and adds no overhead per head, but it requires enough heads to cover the pattern space. Models with 8 or 16 heads can dedicate 4 to local attention and 4 to strided attention without sacrificing capacity. Both strategies work in practice, and the choice often comes down to the number of available attention heads and the relative importance of local versus global relationships in the target task.

The most common combination pairs local attention for nearby tokens with strided attention for long-range connections. Together, they ensure every pair of positions can communicate within a small number of layers while maintaining overall sparsity.

An elegant approach from Sparse Transformer assigns different patterns to different attention heads. Half the heads might use local attention while the other half use strided attention. This factorization allows the model to learn which pattern is most useful for different types of dependencies.

Factorized attention provides flexibility: local heads handle nearby dependencies while strided heads capture long-range patterns. The model learns to route information through the appropriate heads during training.

The factorization approach has an elegant information-theoretic justification. In standard multi-head attention, each head learns to focus on different types of relationships: some heads attend to syntactic structure, others to semantic similarity, others to positional patterns. By explicitly assigning structural patterns to heads at the architectural level, you are encoding inductive biases that align with these empirically observed behaviors. A head that can only attend locally is forced to specialize in local patterns; a head that can only attend at stride positions must specialize in global patterns. This constraint acts as a form of regularization, reducing the space of possible attention behaviors each head must search during training.

To solidify your understanding of how different sparse patterns complement each other, let's trace the flow of information through a small example. Consider a 12-token sequence representing the sentence "The quick brown fox jumps over the lazy dog today." We will use position indices 0 through 11.

Suppose we use local attention with window 1 (each position attends to itself and one neighbor on each side) and strided attention with stride 3. The local attention pattern connects each position to its immediate neighbors: position 5 ("over") attends to positions 4, 5, and 6. The strided attention pattern designates positions 0, 3, 6, and 9 as hubs, which every position can attend to.

Now trace the path from position 1 ("quick") to position 10 ("today"). In a single attention layer, position 1 cannot reach position 10 directly under either pattern: they are too far apart for local attention (distance 9, window 1) and neither is a hub for strided attention under stride 3. But position 1 can attend to hubs 0 and 3, while those hub queries attend to the full sequence and can gather information from position 10. In the next layer, position 1 can retrieve that information through a hub. The bidirectional hub connections therefore link any two positions within two layers.

Notice that this two-hop connectivity works even though the total number of attention pairs remains well below full attention. In this 12-token example, local window-1 attention uses at most $12 \times 3 = 36$ pairs. For stride 3, the four hub queries each attend to all 12 positions, while the other eight queries attend to four hubs plus themselves, for 88 strided pairs before overlap with the local pattern. Full attention would require $12 \times 12 = 144$ pairs. For long sequences and larger practical strides, the savings grow substantially while the two-hop path remains available.

Having established the theory behind sparse patterns, let's implement a complete sparse attention module. This implementation prioritizes clarity over performance. This shows how the mask-based approach works in practice. Understanding this foundation will help you work with optimized libraries like xformers or Flash Attention later.

The mask-based implementation we build here is conceptually the simplest possible approach. You compute the full attention score matrix, apply the mask to zero out disallowed pairs, and run softmax as usual. This approach does not save computation in terms of floating-point operations: you still compute all $n^2$ scores before masking. What it does save is the cost of reasoning about which positions to compute and how to reconstruct a dense output from sparse inputs. For small sequences on a laptop, this simplification is fine. For large sequences in production, you need a kernel that avoids computing the masked entries altogether, which is what xformers and Flash Attention provide.

The value of implementing the mask-based version first is that it gives you a correct reference implementation you can use to validate more complex sparse kernels. Any optimized implementation should produce exactly the same output as the mask-based version for the same mask. If they differ, something is wrong with the optimization. This test-driven approach to building sparse attention is how most research teams develop and validate new patterns.

Sparse attention follows the same computational structure as standard attention, with one addition: we apply a mask before the softmax to block certain attention connections. The algorithm proceeds in four steps:

1. Compute raw attention scores: Multiply queries by keys to get similarity scores
2. Apply the sparse mask: Set blocked positions to $-\infty$ (we use $-10^9$ numerically)
3. Softmax normalization: Convert scores to probability weights (blocked positions become zero)
4. Weighted sum: Combine values according to the attention weights

Let's implement each step:

To validate our implementation and demonstrate the effectiveness of sparse patterns, let's compare the outputs of full attention versus a combined local + strided pattern:

Let's verify the computational savings from sparse attention empirically. The theoretical analysis we've done with Big-O notation tells us what the scaling should be, but empirical measurements validate whether our implementation achieves that scaling and quantify the constant factors that Big-O notation abstracts away.

The benchmark confirms the theoretical complexity analysis: sparse patterns scale better than full attention, with the advantage growing as sequence length increases. Note that our NumPy implementation doesn't fully exploit sparsity since it still computes the full matrix before masking. Production implementations using optimized sparse kernels would show even larger speedups.

The gap between "pairs computed" and actual execution time matters. In our mask-based implementation, the number of pairs plotted corresponds to the non-masked entries, but the actual execution time includes computing the full score matrix and then applying the mask. This is why execution time does not scale as favorably as the pair count alone would suggest. A true sparse implementation that skips computing masked entries would show a much closer alignment between pair counts and execution times.

This distinction between theoretical sparsity and practical speedup is one of the central engineering challenges in sparse attention research. The theoretical analysis shows what should be possible. Achieving it requires specialized kernels, careful memory layouts, and hardware-specific optimizations. Libraries like xformers and Flash Attention have invested significant engineering effort into closing this gap, and they represent the practical tools you would use when deploying sparse attention in production systems.

When implementing sparse attention in practice, several factors influence the choice of pattern and parameters. The theoretical complexity savings are only part of the story: you also need to think about training dynamics, gradient flow, and the match between your sparse pattern and the structure of your task.

Different tasks and sequence lengths call for different patterns:

• Short sequences (less than 512 tokens): Full attention is often fast enough. Sparse patterns may not provide significant benefit and add implementation complexity.
• Medium sequences (512 to 2048 tokens): Local attention with a window of 128-256 tokens works well for most tasks. Add strided or global attention for tasks requiring long-range dependencies.
• Long sequences (more than 2048 tokens): Combined patterns are essential. Consider factorized attention across heads or hierarchical approaches.

A useful way to think about pattern selection is to ask: what are the longest-range dependencies that matter for my task? For document classification where the answer depends on a few key sentences spread throughout a document, you need global connectivity. Local attention alone will fail because no single sentence can directly attend to another sentence far away. For sentence-level tasks like named entity recognition or dependency parsing, local attention is often sufficient and much faster.

When you are uncertain about the dependency structure of your task, starting with a combined local + global pattern is a safe default. Local attention handles the majority of dependencies efficiently, while global tokens (a small set of positions that attend to and are attended by all positions) handle any long-range interactions. This is the approach Longformer uses and it provides a good baseline across a wide range of tasks.

Sparse attention reduces both memory and compute, but the savings differ in important ways that affect system design:

• Compute: Scales directly with sparsity. 90% sparsity means 10x fewer FLOPs in theory, though in practice the achievable speedup depends on whether the implementation skips computing masked entries or simply masks them after computation.
• Memory: Storing the sparse mask adds overhead. For very sparse patterns, mask storage can dominate for short sequences. The attention weight matrix itself also shrinks with sparsity, which matters for the activation memory needed during backpropagation.

For high sparsity (95%+) and long sequences, sparse storage provides significant memory savings. However, for shorter sequences or moderate sparsity, the overhead of sparse formats can negate the benefits.

The memory analysis has an important implication for training. Transformer training stores activations during the forward pass for use in the backward pass. The attention weight matrix is one of the largest activations: for a sequence of length $n$ with $h$ heads, the attention matrices consume $h \times n^2 \times 4$ bytes in float32 format. For a 4096-token sequence with 12 heads, that is $12 \times 4096^2 \times 4 \approx 800$ MB per layer. Gradient checkpointing can reduce this at the cost of recomputing activations, but sparse attention offers a cleaner solution: if you store only the non-masked attention weights in sparse format, memory consumption drops proportionally to sparsity. For 95% sparsity, the 800 MB per-layer cost drops to 40 MB, enabling much longer sequences or larger batch sizes on the same hardware.

This interaction between sparsity and memory, alongside batch size, is one of the main reasons why sparse attention has such a large practical impact. Longer sequences not only become computationally feasible, they become memory-feasible for training as well. The two constraints relax together, which is why the jump from 512-token to 4096-token models was not incremental but felt like a phase transition in what language models could accomplish.

Sparse attention patterns can affect gradient flow during training. Positions that are never attended to receive no gradient signal through attention. This is typically acceptable when patterns ensure every position is reachable within a few layers, but can cause issues with overly aggressive sparsity.

The key insight is that multi-layer transformers compose attention patterns. Even if layer 1 uses sparse attention, the effective receptive field grows with depth. A position unreachable in one layer may become reachable through intermediate positions in subsequent layers.

In practice, gradient flow problems from sparse attention tend to manifest as slow convergence rather than complete training failure. The model learns to use the connections it has, but it takes more gradient updates to discover useful long-range patterns through indirect paths. You can diagnose this by monitoring the validation loss curve: if the model with sparse attention converges to the same final loss as full attention but requires more training steps, the gradient flow is working but is less efficient. If the model plateaus at a higher loss and does not improve with more training, the sparse pattern may be cutting off critical information paths that the model needs.

A practical mitigation is to start training with a dense pattern and gradually increase sparsity during training. This approach, sometimes called sparse attention annealing, allows the model to first learn useful representations with full connectivity, then adapt those representations to work within sparse constraints. It often achieves better final performance than training with a fixed sparse pattern from the start, especially for tasks where long-range dependencies are important but not uniform across examples.

Sparse attention patterns represent a fundamental advance in efficient transformer design, enabling the processing of sequences that would be impossible with full attention. However, they come with trade-offs that practitioners must understand before committing to a sparse architecture.

The most significant limitation is the potential loss of long-range dependencies. While patterns like local + strided ensure connectivity in the graph-theoretic sense, graph connectivity and semantic relevance are different things. A two-hop path between two distant tokens allows information to flow, but the intermediate hub token acts as a bottleneck: it must encode information from both sides and pass the right parts to the right destinations. When the hub token is semantically unrelated to both endpoints, this information routing becomes unreliable. Tasks requiring precise long-range reasoning, such as mathematical proofs, complex code understanding, or legal contract analysis, may suffer from aggressive sparsity in ways that are difficult to diagnose. The model might appear to perform well on average benchmarks while failing systematically on the subset of examples that require long chains of reasoning through non-obvious intermediaries.

Implementation complexity is another practical concern that is easy to underestimate. While conceptually simple, efficient sparse attention requires careful memory management and often custom CUDA kernels to achieve the theoretical speedups. The mask-based implementation we built in this chapter is correct but not fast: it computes the full dense score matrix before applying the mask, capturing none of the computational benefits of sparsity. To realize speedups, you need kernels that skip computing masked entries entirely, maintain separate memory layouts for the sparse data, and handle the edge cases at sequence boundaries without introducing correctness bugs. Libraries like xformers and Flash Attention provide these optimized implementations, but integrating them into existing codebases requires significant engineering effort and careful testing. The block-sparse approach helps here by mapping to hardware-friendly operations, but still requires infrastructure beyond standard dense attention.

Sparse patterns can also interact poorly with certain pre-training strategies. Language models pre-trained with full attention and then fine-tuned with sparse attention sometimes struggle to adapt because the learned representations were built assuming global context availability. The model's weights effectively "expect" long-range information in certain positions, and switching to a sparse mask abruptly removes that information. This mismatch can cause performance degradation that takes significant additional fine-tuning to recover from. The lesson is that sparse attention works best when the model is trained with the sparse pattern from the beginning, not retrofitted onto a fully-trained model.

Despite these challenges, sparse attention patterns have enabled a generation of long-context models that would otherwise be impossible to train or serve. Longformer and BigBird, along with their successors, process entire documents and books as well as code repositories that were previously inaccessible to transformers. The efficiency gains are substantial: processing a 4,096-token document with sparse attention uses roughly the same resources as a 512-token document with full attention. This has opened new applications in document understanding, long-form generation, question answering over entire books, and multi-turn conversation where the context window spans many conversation turns.

The impact extends beyond direct applications. The insights from sparse attention research influenced a broader shift in how researchers think about the attention mechanism. Earlier work had treated the $n \times n$ attention matrix as an essential, inviolable structure. Sparse attention demonstrated that most of this structure was redundant and that carefully chosen subsets could preserve most of the representational power. This insight cascaded into research on linear attention approximations, attention-free architectures like Mamba and Hyena, and retrieval-augmented models that replace attention with explicit memory lookup. Sparse attention patterns are an engineering optimization with a broader conceptual effect: they changed how the community understands what attention needs to compute.

Sparse attention patterns address the quadratic complexity bottleneck of standard attention by restricting each query to attend to a subset of keys. Rather than computing all $n^2$ pairwise interactions, sparse patterns select a carefully structured subset that preserves the most important interactions while discarding the redundant ones.

The key patterns covered in this chapter are:

• Local attention: Each position attends to a fixed window of nearby tokens, exploiting the locality of language. Complexity is $O(n \cdot w)$ where $n$ is the sequence length and $w$ is the window size. Best suited for tasks where most relevant information is nearby, like named entity recognition and part-of-speech tagging.

• Strided attention: Positions attend to regularly-spaced hub positions, enabling long-range information flow within two hops. Complexity is $O(n \cdot n/s)$ where $s$ is the stride, creating highways for information propagation across long sequences. Provides global connectivity guarantee regardless of sequence length.

• Block-sparse attention: Groups positions into blocks of size $b$ and defines attention at the block level. Complexity is $O(n \cdot k \cdot b)$ where $k$ is the number of blocks attended to. Hardware-friendly due to regular memory access patterns that align with GPU execution units.

• Combined patterns: Real systems combine multiple patterns, often using factorized multi-head attention where different heads use different patterns. The union of local and strided patterns covers both short-range density and long-range connectivity.

The effectiveness of sparse attention rests on a key observation: most attention weights are small, concentrated on a few important positions. By carefully selecting which positions to attend to, sparse patterns preserve most of the representational power of full attention while dramatically reducing computational cost. The empirical confirmation of this observation, that trained attention matrices are highly concentrated even without explicit sparsity constraints, is what gives the sparse attention approach its theoretical grounding.

Choosing a sparse pattern requires understanding your task's dependency structure, your sequence length distribution, and your hardware constraints. Local patterns are easy to implement and cache-friendly. Global patterns require more engineering effort but enable qualitatively different capabilities. Block structure improves hardware efficiency at the cost of pattern granularity.

These building blocks form the foundation for efficient attention mechanisms like Longformer and BigBird, along with Sparse Transformer. The next chapters explore specific architectures that combine sparse patterns with additional techniques like sliding windows and global tokens to achieve even better trade-offs between efficiency and expressiveness. As you move into those architectures, you will see the patterns from this chapter appear repeatedly as components in more sophisticated designs.

When implementing sparse attention patterns, several parameters control the trade-off between efficiency and model quality:

• window_size: The number of positions each query attends to on each side in local attention. Larger windows capture more context but increase computation. Typical values range from 64 to 512 tokens. Start with 256 for most tasks and adjust based on whether the model struggles with local dependencies.

• stride: The interval between hub positions in strided attention. Smaller strides provide denser global connectivity but increase computation. Common values are 8 to 64. A stride of $\sqrt{n}$ (where $n$ is sequence length) balances coverage and efficiency.

• block_size: The size of contiguous blocks in block-sparse attention. Must be chosen to align with GPU warp sizes (typically 32 or 64) for optimal hardware utilization. Larger blocks reduce indexing overhead but coarsen the sparsity pattern.

• sparsity_ratio: The fraction of attention pairs that are masked out. Higher sparsity (0.9+) dramatically reduces computation but may degrade quality on tasks requiring dense interactions. Monitor validation loss when increasing sparsity.

• num_heads: In factorized multi-head attention, determines how many heads use each pattern type. Splitting evenly between local and strided heads works well as a starting point. Models may benefit from more local heads for tasks with strong locality.

• pattern: The combination strategy for multiple sparse patterns. Options include union (OR), which is most common, or alternating patterns across layers. The union approach ensures positions blocked by one pattern may still be reached through another.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about sparse attention patterns and their role in efficient transformer design.