Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Sparse Attention Patterns › Strided Attention Patterns

Michael BrenndoerferUpdated June 25, 202510 min read

Language AI HandbookAll chapters

Part 17 of 67Efficient Attention

Chapter 118Sparse Attention Patterns › Strided Attention Patterns

Reading section 4 of 13 · Strided Attention Patterns · 10 minSection 4 of 13 · 10 min

Section 4 of 13 · 10 min read

Sparse Attention Patterns › Strided Attention PatternsOne section · Sections in this chapter4 / 13 ↓

Sections in this chapter13

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

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.

Stride FormulationLink Copied

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:

All hub positions: Every position can reach the hubs, creating information highways across the sequence
Every position from a hub: Hub queries attend to the full sequence, so they can gather and relay information
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:

M_{ij} = \begin{cases} 0 & \text{if } j \mod s = 0 \text{ or } i \mod s = 0 \text{ or } j = i \\ -\infty & \text{otherwise} \end{cases}

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.

In[13]:

Code

def create_strided_attention_mask(seq_len, stride):
    """
    Create a strided attention mask.
    Each position attends to every stride-th hub plus itself, while hub
    queries attend to the full sequence so they can relay information.

    Args:
        seq_len: Length of the sequence
        stride: Attend to every stride-th position

    Returns:
        mask: (seq_len, seq_len) boolean mask
    """
    mask = np.zeros((seq_len, seq_len), dtype=bool)

    for i in range(seq_len):
        # Attend to strided positions
        for j in range(0, seq_len, stride):
            mask[i, j] = True
        # Always attend to self
        mask[i, i] = True

    # Global hubs gather from every position as well as broadcasting to them.
    mask[::stride, :] = True

    return mask


# Create strided masks
seq_len = 32
stride_4 = create_strided_attention_mask(seq_len, stride=4)
stride_8 = create_strided_attention_mask(seq_len, stride=8)

Out[14]:

Visualization

Grid pattern with horizontal and vertical lines every 4 positions plus a diagonal. — Stride 4: Every fourth position is a bidirectional hub, creating horizontal and vertical stripes plus a self-attention diagonal.

Grid pattern with horizontal and vertical lines every 8 positions plus a diagonal. — Stride 8: Fewer bidirectional hubs create a sparser grid while preserving two-hop connectivity.

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.

Information Flow in Strided AttentionLink Copied

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.

In[15]:

Code

def analyze_reachability(seq_len, stride, num_layers):
    """
    Analyze how many positions are reachable after num_layers of strided attention.

    Returns:
        reachability: (seq_len,) array of reachable position counts per starting position
    """
    # Start with identity (each position reaches itself)
    reachable = np.eye(seq_len, dtype=bool)

    # Create strided mask
    mask = create_strided_attention_mask(seq_len, stride)

    # Propagate through layers
    for _ in range(num_layers):
        # Reachability is transitive: if A reaches B and B reaches C, A reaches C
        reachable = (reachable.astype(int) @ mask.astype(int)) > 0
        reachable |= np.eye(seq_len, dtype=bool)

    return reachable.sum(axis=1)


seq_len = 64
stride = 8
reachability_by_layer = []
for layers in range(1, 5):
    reach = analyze_reachability(seq_len, stride, layers)
    reachability_by_layer.append(
        (layers, reach.min(), reach.max(), reach.mean())
    )

Out[16]:

Console

Reachability in strided attention (seq_len=64, stride=8):

  Layers    Min Reach    Max Reach   Mean Reach
------------------------------------------------
       1            9           64         15.9
       2           64           64         64.0
       3           64           64         64.0
       4           64           64         64.0

After just 2 layers of strided attention, every position can reach every other position. This demonstrates the power of strided patterns for long-range information flow, achieving global connectivity with sparse local computation.

The reachability analysis gives you a useful design tool. Before finalizing your sparse pattern, you can simulate how many layers are required to achieve full connectivity and verify that your model has enough depth to guarantee global information flow. A 12-layer transformer with 2-hop connectivity in strided attention has six complete cycles of information propagation, which is usually more than sufficient. A shallow 4-layer model with a large stride might only complete two cycles, which could limit performance on tasks requiring complex multi-step reasoning.

The visualization of the fully connected second-layer reachability matrix is worth dwelling on. Every cell is active, meaning every position can influence every other position within just two attention layers. This complete connectivity comes at a fraction of the cost of full attention: ordinary queries attend to approximately $n/s + 1$ positions, while the smaller set of hub queries attends densely. The global connectivity emerges from composing these sparse layers. This compositionality is a core principle in efficient transformer design and explains why depth and sparsity are complementary rather than competing properties.

Out[17]:

Visualization

Heatmap showing partial connectivity after one layer of strided attention. — After layer 1: Vertical and horizontal stripes show that ordinary positions can reach hubs and hubs can reach every position.

Fully connected heatmap after two layers of strided attention. — After layer 2: All positions are mutually reachable. Information can now flow between any pair of positions in the sequence.

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.