Sparse Attention

Sparse attention is a family of attention mechanisms in which each query scores only a chosen subset of keys instead of every key in the sequence. Full self-attention over N tokens computes N² scores per head, so doubling a document's length quadruples the attention cost, while a pattern in which each token attends to k others costs N·k. The pattern can be fixed in advance, such as a local window, or chosen from the content, such as the highest-scoring keys for each query. OpenAI's 2019 Sparse Transformer used strided patterns that cost O(N√N) to model sequences tens of thousands of steps long, and current large language models (LLMs) use sparse layers to serve context windows of more than 100,000 tokens.

Common Sparsity Patterns#

Fixed patterns decide in advance which pairs to score. Sliding window attention lets each token see only the previous w tokens: Mistral 7B uses a 4,096-token window, and OpenAI's open-weight gpt-oss models alternate dense layers with 128-token window layers, the same alternation of dense and locally banded layers that GPT-3 used. Each windowed layer carries information another w tokens forward, so a deep stack still connects distant tokens. Strided patterns add every s-th earlier token so information also jumps long distances in a single layer. Global tokens attend to, and are attended by, every position: Longformer assigns them to task tokens such as a classification token, BigBird adds random connections as well, and attention sinks keep the first few tokens visible to every query so streaming generation stays stable.

Content-based patterns choose the pairs from the data. DeepSeek's Native Sparse Attention (NSA, 2025) combines compressed summaries of key blocks, a selection of the most relevant blocks, and a sliding window, all trained end to end. DeepSeek Sparse Attention in DeepSeek-V3.2 runs a small "lightning indexer" that scores every earlier token for each query and then computes full attention over only the top 2,048, so each query's main attention cost stays fixed however long the context grows. Production models often combine these rules:

Turning a Pattern Into Savings#

A mask applied to a dense score matrix still computes every score, so speedups come from kernels that skip empty tiles of the matrix. Flash attention kernels support sliding windows directly, and PyTorch's FlexAttention compiles any mask function into a block-sparse GPU kernel. Its create_block_mask shows which blocks such a kernel skips for a 1,024-token window plus four sink tokens:

from torch.nn.attention.flex_attention import create_block_mask

seq_len, window, sinks = 8192, 1024, 4


def local_plus_sinks(b, h, q_idx, kv_idx):
    """Causal attention to the previous 1,024 tokens plus the first 4 tokens."""
    causal = q_idx >= kv_idx
    return causal & ((q_idx - kv_idx <= window) | (kv_idx < sinks))


# FlexAttention splits the mask into 128 x 128 blocks so its kernels can skip empty blocks
block_mask = create_block_mask(local_plus_sinks, B=None, H=None, Q_LEN=seq_len, KV_LEN=seq_len, device="cpu")
print(block_mask)

The printout reports sparsity=85.47%, the share of 128 × 128 blocks of the 8,192 × 8,192 score matrix that hold no allowed pair, and draws the pattern as a diagonal band for the window plus a column on the left for the sink tokens. When flex_attention runs under torch.compile, its kernel skips those blocks entirely.

Sparse Attention vs. Related Terms#

• Flash attention: An IO-aware kernel that computes exact attention over every pair by tiling the work in fast on-chip memory. Its tiles are also the unit that block-sparse kernels skip.
• Linear attention: Keeps every pair but replaces the softmax with a feature map, so all past keys and values compress into a fixed-size state.
• Deformable attention: A vision mechanism in which each query attends to a few sampling points at learned offsets in a feature map instead of to a fixed pattern.
• Mixture of experts (MoE): Sparsity in parameters, where each token activates only a few expert networks while its attention pattern stays dense.

Applications#

Long-context language models are the main use: sparse layers bound the compute, and windowed layers also bound the KV cache, which lets models summarize long reports or search large codebases in one request. BigBird applied its sparse pattern to DNA sequences, where an input of thousands of base pairs is far longer than a typical sentence, to predict promoter regions. In computer vision, the token count grows with image resolution, so models restrict attention to local regions: the Swin Transformer attends within shifted windows. YOLO12, an attention-centric detector from researchers at the University at Buffalo and the University of Chinese Academy of Sciences that runs in the Ultralytics package, uses area attention: its stride-16 backbone stage splits the 40 × 40 feature map of a 640-pixel image into four horizontal strips of 400 tokens and attends only within each strip, scoring a quarter of the 2.56 million pairs that full attention over all 1,600 tokens would need.