Sparse Attention

Attention is the transformer's "look at everything" step: every token in the sequence compares itself against every earlier token to decide what to read.

For a sequence of N tokens that is an N×N score grid — one row per query token, one column per key token.

Now ask

code
Copy
 N = 4,096    →  N² ≈ 16.8M   score entries     (fine)
 N = 128,000  →  N² ≈ 16.4B   score entries     (~1000× more)

Flash Attention (the companion topic) made this IO-optimal — it stopped writing the N² grid to slow memory — but it did not make it asymptotically cheaper. At 128K tokens the attention term (~N²·d per head) rivals or exceeds the FFN term, and prefill cost for long prompts became the dominant billing line for API providers chasing 1M-token contexts.

Picture the real workflow. You are a detective handed a 2,000-page case file, and for each of your 500 questions you must photocopy and read all the pages before then. Nobody works like that. Detectives skim summaries, open the folders that matter, and always keep the latest reports on the desk.

Sparse attention is exactly that: stop reading every page for every question.

The whole family shares one rule

With a fixed window of m = 4,096 neighbors at N = 128,000:

code
Copy
 dense:  128,000 × 128,000   = 16.4 billion pairs
 sparse: 128,000 × 4,096     = 0.5 billion pairs  → ~32× cheaper

Cheap. So why is this a research field and not a one-liner?

Because attention heads live on arbitrary long-range dependencies: induction heads copying a phrase from 50K tokens back, retrieval questions ("what did the user say on page 900?"), the one "needle" token that answers the query. Which entries you drop decides whether quality survives. Drop the wrong column and the model goes blind exactly when it matters.

Three generations of answers emerged:

Attention patterns are pictures: a grid with 1 = "this query may look at this key" and 0 = skipped. Causal (lower-triangular) versions, N = 12, window w = 2:

code
Copy
 DENSE (every query reads all past keys)      Cost: N²/2
 1
 1 1
 1 1 1
 1 1 1 1
 1 1 1 1 1
 ... every row grows → linear rows, quadratic total

 SLIDING WINDOW + GLOBAL (Longformer-style)   Cost: N·w + N·g
 . . . . . . . . . . . .   ← row 0
 1 . . . . . . . . . . .
 1 1 . . . . . . . . . .
 ■ ■ 1 . . . . . . . . .   ← band: only ±w neighbors
 ■ ■ 1 1 . . . . . . . .
 ■ ■ 1 1 1 . . . . . . .
 ↑ col ■ = GLOBAL token (e.g. system prompt):
   its column is readable by EVERY row,
   and its own row reads everything.
   → information hops: any token reaches any
     token in two steps via the global hub.

 TRAINABLE BLOCK-SPARSE (NSA/DSA-style)       Cost: chosen blocks only
 [b0][b1][b2][b3][b4][b5][b6]  ← keys in chunks
  ✓   .   ✓   .   .   ✓   .   ← this query's row picks
        blocks {b0,b2,b5} + always the local window,
        the choice LEARNED from data, not hand-drawn

Fixed masks (middle) are cheap but blind: whoever drew the pattern hoped band + global hubs cover every needed dependency. Trainable masks (bottom) let the model itself discover, per query, which chunks matter.

Carry one picture through the rest: a detective answering questions about a 2,000-page case file.

• Dense attention = re-read all 2,000 pages before every question. Correct, but the work is absurd (that is the N² tax).
• Sliding window = only read the ±20 pages around the current page. Great for continuity — hopeless for "what did the informant say 900 pages ago?"
• Global tokens = keep one page (the index / the suspect list) always on the desk; every question may consult it, and it summarizes connections across everything. The Longformer/BigBird trick.
• DSA (Lightning Indexer) = an assistant who maintains one index card per folder, and for each question points to the top-k relevant 64-page folders. The folders stay uncompressed — open one and you still have every word inside.
• NSA = three reading habits combined per question: (1) the current stack (local window), (2) skim the one-paragraph summaries of every folder (coarse compression path), (3) from those skim clues, fully open the few folders that look decisive (learned selection path).
• Why blocks, not pages = filing cabinets only come out whole. Skipping "one sentence here, one sentence there" saves no trips; skipping entire drawers does. (That is the GPU-kernel constraint in section 6.)
• The failure mode = a detective trained on 400-page cases suddenly handed 100K pages: their folder-skimming habits misfire. Distribution shift — section 7.

Introduced in DeepSeek-V3.2-Exp (July 2025) and made the default in DeepSeek V3.2, DSA restructures attention around page-granular selection:

1. Lightning Indexer — a tiny extra scoring network (shared Q with 1 head-dim, ReLU + top-k) that rates every 64-token KV page of the context. The index-card assistant from the analogy.
2. Sparse top-k gather — the main attention then reads only the ~top-k (e.g., 20) most relevant pages plus mandatory recent/local pages, instead of the full history.
3. No compression of the KVs themselves — selection happens at page granularity, so fine-grained information stays intact inside any selected page (contrast with token-compression schemes, which blur details to save space).

Because every query touches a roughly constant number of pages, per-layer attention FLOPs drop from O(N²) to O(N·k). DeepSeek measured a ~50% total compute reduction at 128K context with quality parity — and better scores on many long-context evals, because the indexer focuses attention rather than diluting it across everything.

Crucially it transfers: DSA ships with an optical (fine-grained) masking compatibility layer so sparse selection stays correct inside FlashInfer-style kernels, and the API price for V3.2 was cut ~30-50% on long inputs. Sparse attention's first real production deployment.

NSA (NVIDIA, May 2025, arXiv 2505.17265) distilled the design rules that 2025 sparse attention converged on:

• Three parallel paths per query: a fixed sliding-window for locality; a coarse compression path (pool every block of keys into a summary token and attend coarsely — the folder summaries); and a fine-grained selection path — a learned gate scores each block and a top-k bitmask admits whole blocks (open the decisive folders).
• Block-granular, not token-granular — because of the hardware. GPUs and FlashAttention-style fused kernels execute contiguous tile loads. Token-level sparsity — erasing random individual entries of the score matrix — cuts the theoretical FLOP count but cannot be exploited by hardware: the tile still gets loaded. Sparsity must be structured into dense blocks to actually run fast. The masked-out entries are a spreadsheet fiction; the memory bus keeps paying for them.
• Natively trainable: unlike post-hoc sparsification (pruning a trained dense model), models trained from scratch with NSA improve quality over dense baselines at 32K context (better passkey/RAG retrieval) while prefill/decode speedups grow with length. Learning to select sharpens what the model reads.

Inference-only alternatives keep dense training and sparsify only the serving path: H2O-style eviction (drop cached tokens predicted unimportant), Quest-style page-wise KV selection (DSA's idea, applied at serving time without retraining), and A2CS (hybrid offline-coarse + online-fine, ~3.5× decode at 1M). These avoid retraining but inherit whatever quality cliff the pattern can't paper over.

Sparse attention's failure mode is distribution shift from training to deployment: a model trained with 4K windows or fixed patterns degrades unpredictably when prompted with 100K of code, tables, or a needle query — the detective lost in the 100K-page case. The dependency it needs to see was dropped by the pattern, silently, and the answer is gone rather than wrong.

Hybrid layer schedules — interleave a few dense global layers among many local ones, so at least some rows still read everything — are the classic insurance. The trainable 2025 generation reduces but does not eliminate this: selection itself must be trained at long context, which is itself a data-engineering feat (document packing, length curricula).

As of 2025-2026:

• sliding-window hybrids dominate open-weights long-context serving (Gemma 2/3, Mistral);
• DSA ships in a deployed frontier API (DeepSeek-V3.2);
• NSA-style block-sparse is the research default for new long-context pretrains;
• and Kimi Mooncake / Kimi K2 practice shows infrastructure (KV-cache pooling + prefill/decode disaggregation) is as important as mask design for actual 1M-token economics.