Sparse Attention Patterns › Worked Example: Tracing Information Flow

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.