Sparse Attention Patterns

Sparse attention restricts which keys each query can read. Local windows, a few global tokens, strided connections and random connections give different paths for information to move through a sequence.

The mask defines connectivity. Efficient execution additionally requires a kernel that avoids work on blocked pairs; putting a sparse-looking mask on a dense matmul does not by itself save that work.

Follow one query across its keys

Select a query row, then toggle the pattern primitives. The outlined row shows its allowed key columns; the readout below shows how a zero or negative-infinity bias changes the row before softmax. Add the causal restriction to remove future keys without changing the meaning of the axes.

The random primitive and logits are deterministic teaching values. The labels describe pattern families: the example's token-level masks are not exact Longformer or BigBird block layouts.

Block logits before normalization

Let Aᵢⱼ indicate whether query i may attend to key j. Construct an additive logit bias, not a multiplicative zero mask:

A blocked logit becomes negative infinity, so its softmax weight is zero. Multiplying the logit by zero would leave a finite zero logit and a positive weight. For example, logits [1, 0] with only the first key allowed should produce [1, 0], not the unmasked distribution [0.731, 0.269].

An all-blocked row has no valid attention distribution. The explorer reports that condition instead of inventing probabilities. Real patterns must provide a valid visible key or define a separate handling policy.

This dense PyTorch example demonstrates the masking semantics:

import math
import torch


def masked_attention(q, k, v, allowed):
    """Apply a Boolean visibility mask to dense attention logits."""
    logits = q @ k.transpose(-2, -1) / math.sqrt(q.shape[-1])
    logits = logits.masked_fill(~allowed, float('-inf'))
    weights = logits.softmax(dim=-1)
    return weights @ v

allowed must broadcast to the query-key score shape and give each query at least one allowed key. This code still forms dense logits. Sparse or block-sparse kernels use the pattern to compute and normalize only eligible entries.

Count connectivity before claiming a speedup

For n queries, let query i read kᵢ keys. The number of eligible pairs is E=\sum_i k_i. A sparse implementation can perform score and value work proportional to E × d, excluding projections and implementation overhead.

Writing O(n × k) uses an average or bound on keys per query. It is linear in n only when that bound stays fixed as n grows.

Storing only the eligible score/weight entries costs O(E) space. Dense materialization costs O(n²) score storage, while exact tiled algorithms such as FlashAttention avoid that materialization without changing full-attention connectivity. Pair count, score storage and observed runtime are different quantities.

How model families combine the primitives

Longformer combines local windows with task-selected global tokens. A global token reads the full sequence and is visible to ordinary tokens; a classification token is one possible choice, not a universal rule for every task.

BigBird combines local, global and random connections, commonly using block-sparse layouts. Its theoretical expressivity results rely on specified assumptions. They do not guarantee identical dense-attention weights or quality for every trained checkpoint.

Sparse Transformer uses structured factorized patterns, including local and strided connections, for generative modeling. Its pattern and causal constraints depend on the data layout.

Exact window sizes, block counts and supported lengths belong to a particular checkpoint and implementation. The family name alone does not determine those values.

Choose the path the task needs

A useful pattern must let required information reach the output. Local windows provide nearby connections; global tokens offer short paths across the sequence; strided or random links distribute longer-range connections. Stacking layers can extend the receptive field, but does not restore every direct full-attention edge.

For generation, preserve causal visibility and evaluate tasks that need distant facts. For classification, decide which token aggregates the result and how evidence can reach it. For images or video, reflect the actual spatial and temporal layout rather than assuming a text stride has the same meaning.

Content-dependent top-k selection is another option, but discovering important keys can itself be expensive. Include selection and indexing costs when comparing it with a fixed sparse layout.

Start from full self-attention, then compare sliding window attention as one local pattern and linear attention approximations as a different change to the attention calculation.

Related concepts