Block-Sparse Attention

An attention variant that divides the attention map into token blocks and computes scores only for selected block regions instead of every token pair.

Block-sparse attention is a structured sparse-attention variant that groups tokens into blocks and keeps only selected block-to-block connections, lowering long-context attention work while staying easier to implement than arbitrary sparse pair lists.

At a glance

Released

April 2019

Authors

Rewon Child, Scott Gray, Alec Radford, et al.

Optimizes

  • Attention Compute
  • Memory Bandwidth
  • Long Context Inference

What It Is

Block-sparse attention is an attention variant that divides the attention matrix into square regions of tokens and computes scores only for selected regions. Instead of deciding pair by pair, it keeps or skips whole blocks of query-key interactions at once.

Why It Exists

Dense attention becomes expensive on long sequences because every query token can compare with every key token. Block-sparse attention lowers that cost by removing large unused regions, while the regular block layout gives kernels and memory access a more predictable shape than fully irregular sparse attention.

How It Works

The sequence is split into blocks of B tokens. Each query block can attend only to key blocks chosen by a mask, such as nearby diagonal blocks plus a few farther anchor blocks. Inside an allowed block, attention is still dense, but skipped blocks are never scored. That makes block-sparse attention narrower than full attention, more structured than general sparse attention, and less purely local than sliding-window attention when the mask keeps some distant blocks.

Math Or Compute Schema

With sequence length n, block size B, and a block mask M_B, block-sparse attention applies the block mask before softmax so only selected query-block to key-block regions contribute weight. The formulas below contrast dense multi-head attention against a block-masked variant.
Multi-head attention (MHA)
Attention(Qi,Ki,Vi)=softmax ⁣(QiKi⊤dk)Vi\text{Attention}(Q_i, K_i, V_i) = \mathrm{softmax}\!\left(\frac{Q_i K_i^{\top}}{\sqrt{d_k}}\right) V_i
QQ
Query vectors for head i.
KK
Key vectors for head i.
VV
Value vectors for head i.
HH
Number of query heads.
dkd_k
Key dimension per head.
ii
Query head index.
Block-sparse attention
Attention(Qi,Ki,Vi)=softmax ⁣(MB⊙QiKi⊤dk)Vi\text{Attention}(Q_i, K_i, V_i) = \mathrm{softmax}\!\left(M_B \odot \frac{Q_i K_i^{\top}}{\sqrt{d_k}}\right) V_i
QQ
Query vectors for head i.
KK
Key vectors for head i.
VV
Value vectors for head i.
HH
Number of query heads.
BB
Block size in tokens.
dkd_k
Key dimension per head.
ii
Query head index.
MBM_B
Block mask that keeps only selected query-block to key-block regions.

Compared To Nearby Modules

Regular attention scores every token pair. Sparse attention is the broader family that allows many different masks, including irregular ones. Local attention limits each query to a nearby neighborhood; sliding-window attention is one common fixed-band version of that idea. Block-sparse attention sits between them: it is sparse because it skips many pairs, but it keeps those skips aligned to block boundaries so implementations can batch work cleanly. Compared with purely local patterns, block-sparse attention can still keep selected distant blocks when the mask allows.
Comparison dimensionBlock-Sparse AttentionMulti-Head AttentionSparse AttentionLocal AttentionSliding-Window Attention
Connectivity patternSelected block-to-block regions; dense work inside each allowed blockAll n-by-n query-key pairs per headGeneral sparse pair mask with no required block regularityNearby-only neighborhoods around each query tokenFixed local band around each query token
Compute scaling with sequence lengthSubquadratic when the number of kept blocks per query block stays boundedQuadratic O(n²) per headSubquadratic when sparsity fraction is fixedOften near-linear O(n·r) when the local radius stays fixedLinear O(n·W) per head when W is fixed
Distant token reachPossible when the mask keeps far blocks, but only at block-level granularityAny position can attend to any other positionDepends on the chosen sparse patternUsually indirect; far information moves through layers or companion linksUsually no direct distant reach inside one layer

Example Architectures

Structured sparse designs such as Sparse Transformers use block-style masks to keep some long-range paths without paying for a full dense map. The idea also appears in long-context systems that mix local blocks, global blocks, or periodic landmark blocks to stretch the usable context window.

Limitations And Tradeoffs

Coarse block boundaries can hide useful token-level links that do not line up with the chosen regions. Distant information is still limited by the block mask, so the model only reaches what the pattern allows. If the kept blocks are too restrictive, accuracy can drop compared with dense attention even though compute is lower. The same long-context pressure described in Why Long Context Is Hard still applies.

Why It Still Matters

Block-sparse attention remains a useful reference because it shows a practical middle ground: more reach than purely local windows, less cost than dense all-pairs attention, and more hardware-friendly regularity than arbitrary sparse pair selection.

Tags

References

  1. Child, Rewon, et al. "Generating Long Sequences with Sparse Transformers." arXiv, 2019, https://arxiv.org/abs/1904.10509.
  2. Beltagy, Iz, Matthew E. Peters, and Arman Cohan. "Longformer: The Long-Document Transformer." arXiv, 2020, https://arxiv.org/abs/2004.05150.

Bidirectional Attention

Previous Page

Causal Attention

Next Page

On this page

What It IsWhy It ExistsHow It WorksMath Or Compute SchemaCompared To Nearby ModulesExample ArchitecturesLimitations And TradeoffsWhy It Still MattersRelatedTagsReferences