Sliding Window and Sparse Attention, from Longformer to CSA2

1. Why attention is expensive

Scaled dot-product attention^[1] computes, for every query q_i, a score against every key k_j, normalises the scores with a softmax, and takes the weighted sum of values v_j:

Attention(Q, K, V) = softmax( Q Kᵀ / √d ) V

For a causal language model, query i may only see keys j ≤ i, so there are about n²/2 query–key pairs. Two matrix products touch all of them (QKᵀ and PV), each costing roughly 2·d floating-point operations per pair. Per head and per layer:

FLOPs(dense, prefill)  ≈ 4 · n² · d        (full n×n, or ≈ 2·n²·d causal-only)
FLOPs(dense, one decode step) ≈ 4 · n · d   (one query against n keys)
KV cache (bytes)       = 2 · L · H · d · bytes_per_element · n

Three separate costs grow with n, and they hurt in different phases:

• Prefill compute (reading the prompt) is quadratic in n. At one million tokens, dense attention is ~10¹² pair scores per head per layer.
• Decode bandwidth (writing the answer) is linear in n per generated token, but it is memory-bound: every step has to stream the whole KV cache from high-bandwidth memory (HBM) through the GPU, and HBM bandwidth (a few TB/s) — not FLOPs — sets the speed.
• KV cache memory is linear in n and multiplies by batch size. It decides how many concurrent requests fit on a GPU and whether a 1M-token context fits at all.

Kernel work such as FlashAttention^[2] does not change the arithmetic count; it removes the n×n score matrix from memory by computing attention in tiles that stay in on-chip SRAM. That is why the patterns below are almost always implemented as block sparsity: a GPU computes attention in tiles (typically 64–128 keys wide), so skipping a tile saves real time while skipping a single key inside a tile saves nothing.

2. Sliding window attention (SWA)

Definition. Each query attends only to the most recent w keys (positions i−w+1 … i). The score matrix becomes a diagonal band of width w. Also called local attention or banded attention; introduced for transformers by Longformer^[3] and popularised for decoders by Mistral 7B^[4].

FLOPs(SWA, prefill) ≈ 4 · n · w · d           linear in n
KV cache (SWA)      = 2 · L · H · d · bytes · min(n, w)   bounded, not growing

Rationale. Most of the attention mass in trained models falls on nearby tokens; the window keeps that exactly. The cache can be a rolling buffer of size w: position i overwrites slot i mod w, so memory is constant however long the conversation runs.

Why it still sees far away: stacked receptive fields. Information hops one window per layer. After L layers a token can (in principle) be influenced by L·w earlier tokens. Mistral 7B used w = 4096 over 32 layers, a theoretical reach of ~131k tokens. In practice the signal attenuates with each hop, which is why pure SWA models do poorly on precise long-range recall (find-the-needle tasks).

Variants that fix SWA's blind spots

• Attention sinks (StreamingLLM)^[5]. Trained models dump surplus attention mass onto the first few tokens. If a rolling window evicts them the softmax distribution collapses and perplexity explodes. Keeping g ≈ 4 initial tokens permanently in the cache ("sinks") restores stable streaming generation at zero training cost. (Try the Window + attention sinks pattern above.)
• Interleaved local / global layers. Gemma 2^[6] alternates one full-attention layer with one 4096-token local layer; Gemma 3^[7] uses a 5:1 ratio of local (1024-token) to global layers. The global layers provide exact long-range recall; the local layers cut KV memory by roughly the local fraction. This "hybrid" is now the mainstream way to ship SWA.
• Dilated windows. Attend to every r-th key in a wider band (Longformer). Same cost as a window of w, receptive field grows r×, at the price of skipping neighbours. Rarely used in decoder LLMs today.
• SWA Bounded Replay (DeepSeek-V4.1-Flash)^[13]. When a long conversation is paged out and back in, the window KV is not persisted; the model recomputes it by replaying only the last w tokens, so the persistent cache holds only the compressed global part.

3. Sparse attention: a map of the design space

"Sparse attention" means any scheme where each query scores only a subset of the keys. The subset can be chosen three ways, and the choice drives both quality and hardware efficiency:

4. Fixed patterns (2019–2020)

Sparse Transformer (Child et al., 2019)^[8]

Two heads alternate: a local head attending to the previous s positions and a strided head attending to every position j where (i − j) mod s = 0 (a column pattern). With s ≈ √n every token reaches every other in two hops and cost drops to O(n√n). Designed for images and audio where the stride matches a row length; on text the columns are arbitrary.

Longformer (Beltagy et al., 2020)^[3]

Sliding window (optionally dilated) plus a handful of global tokens that attend to and are attended by everything — the [CLS] token, or question tokens in QA. Cost O(n·(w + g)). Introduced the custom CUDA banded kernel that later kernels generalised.

BigBird (Zaheer et al., 2020)^[9]

Window + global + r random blocks per query. The random edges make the attention graph an expander, which is what lets the authors prove the sparse model is still a universal approximator and Turing complete. Random blocks are ugly on hardware (scattered reads) and disappeared from later decoder designs, but the theoretical result is why "window plus a few long-range edges" is a sound recipe.

Block-sparse attention (as a kernel primitive)

Any of the above can be expressed as a boolean grid over B×B tiles. OpenAI's blocksparse library, Triton block-sparse kernels, and PyTorch's FlexAttention^[10] take such a grid (plus an optional score-modifying function) and skip empty tiles. This is the implementation substrate for everything in the next section. One caveat, visible in the DeepSeek-V4 torchtitan port^[19]: FlexAttention rebuilds its block mask whenever the mask changes, which is every forward pass for data-dependent selection, so purpose-built kernels (Attention Gym's fused selected_attention) ran 3–11× faster on CSA.

5. Dynamic, natively trained sparsity (2025–2026)

The recent generation shares a template: keep an exact sliding window for recent tokens, summarise or index the distant past cheaply, then let each query select a top-k slice of that past for exact attention. The differences are in what is indexed (tokens vs. blocks vs. compressed entries), how the scorer is trained, and how much is shared across layers.

NSA — Native Sparse Attention (DeepSeek, Feb 2025)^[11]

Three parallel branches, combined by a learned per-head gate:

1. Compression. Keys/values in each block of l tokens are pooled by a small MLP into one compressed entry. Coarse global view at n/l cost.
2. Selection. Attention scores against the compressed entries rank the blocks; the top-k blocks are expanded back to their original token-level KV and attended exactly.
3. Sliding window. The last w tokens, exact.

Selection is per block so reads are contiguous; the whole scheme is trained from scratch ("native") with a custom Triton kernel. Reported 9× forward and 6× backward speed-ups at 64k context vs. FlashAttention-2, with quality matching dense.

MoBA — Mixture of Block Attention (Moonshot AI, Feb 2025)^[12]

Treats attention like a mixture-of-experts router: the context is split into blocks, each block is summarised by its mean key, and a query is routed to the top-k blocks by query·mean-key score (its own block always included). No gate, no compression branch — just block routing on the real KV, which makes it easy to switch between sparse and full attention in the same model. Used in Kimi models.

DSA — DeepSeek Sparse Attention (DeepSeek-V3.2, Sep 2025)^[14]

Two parts. A lightning indexer — a small, separate attention head set (FP8, few heads, small head dimension) — computes a cheap relevance score between the current query and every cached token. Then a fine-grained token selector keeps the top-k tokens (k = 2048 in V3.2) and runs full Multi-head Latent Attention (MLA) only over them. Indexing is still O(n) per query but with a tiny constant; the expensive MLA becomes O(k). Trained by first distilling the indexer to imitate dense attention scores, then continuing pre-training with the sparse mask. Reported ~50% lower long-context API cost.

CSA — Compressed Sparse Attention (DeepSeek-V4, 2026)^[15]

DSA still stored one KV entry per token, so memory stayed linear. CSA first compresses the sequence axis — every m tokens become one KV entry — and then applies DSA-style indexing and top-k over the compressed entries. Detailed in §6.

HCA — Heavily Compressed Attention (DeepSeek-V4)^[15]

The same compression idea pushed to m = 128. The compressed history is now so short (a 1M context becomes ~8k entries) that the layer attends to all of it densely; no indexer needed. V4 interleaves CSA and HCA layers so the network has both a fine-grained sparse path and a coarse dense path over the same history. Both keep a 128-token uncompressed window.

CSA2 — Compressed Sparse Attention 2 (DeepSeek-V4.1-Flash, Sep 2026)^[13]

Keeps CSA's per-layer mechanics but shares the expensive artefacts (compressed KV, indexer keys, selected indices) across groups of layers. Detailed in §7.

6. CSA in depth

CSA is best understood as three stages applied to the hidden states H ∈ ℝ^n×d_model of a layer.

Stage 1 — Compress the KV cache along the sequence

Each token produces a candidate KV vector and a compression weight vector via linear projections. Following the V4 report, there are two such pairs (branches a and b) with separate weights:

Cᵃ = H·W^{aKV}    Cᵇ = H·W^{bKV}      candidate compressed KV   (n × c)
Zᵃ = H·W^{aZ}     Zᵇ = H·W^{bZ}       compression logits       (n × c)

Within each aligned block of m tokens (stride m, so blocks do not overlap), the logits are softmax-normalised per channel and used to pool the m candidates into a single entry. Two branches give two entries per block, so with m = 4 the cache holds n/4 × 2 = n/2 latent entries — a 2× reduction in stored entries on top of MLA's already-compressed per-entry width. The pooling is learned, so the model decides which of the four tokens dominates each channel of the summary.

Stage 2 — Index and select

A lightning indexer (as in DSA) scores the query against every compressed entry. Because there are only n/m of them, indexing is m× cheaper than in DSA for the same context. The top-k compressed entries per query are selected. Public reference implementations materialise a [batch, n, H_I, n/m] FP32 score tensor before the top-k, which at 1M context is hundreds of GB; StreamIndex^[17] shows a chunked partition-merge top-k that never forms it (6.2 GB peak at 1M tokens on one H200).

Stage 3 — Attend

The query attends, in one fused softmax, over the union of: the k selected compressed entries, the last 128 uncompressed tokens (sliding window), and a learned per-head attention sink logit that absorbs mass when nothing is relevant. The reference kernel returns the log-sum-exp so the branches can be normalised jointly^[19].

What CSA saves

For one decode step in one layer with context n, window w, top-k, compression m, indexer with H_I heads of dimension d_I:

The V4 report's whole-model numbers at 1M context, relative to V3.2 (which already had DSA): V4-Pro runs at 27% of the single-token inference FLOPs and 10% of the KV cache; V4-Flash at 10% and 7%^[16]. Those figures also include MoE, precision and system changes, so they upper-bound the attention contribution.

7. CSA2 in depth

CSA's remaining waste is per-layer duplication: 40 layers each building their own compressed cache, their own indexer keys, and their own top-k pick over largely the same information. CSA2 removes it with three ideas^[13].

Idea 1 — Static per-layer modes: Full, Reindex, Reuse

• Full. The layer builds its own compressed main KV and indexer keys, runs the indexer, and selects its own top-k. It publishes all three for later layers.
• Reindex. The layer borrows the compressed KV and indexer keys from the most recent Full layer, but runs its own indexer queries and makes a fresh top-k selection. New attention pattern, no new cache.
• Reuse. The layer borrows everything, including the selected indices. It only computes attention over the already-chosen entries plus its own sliding window.

Modes are fixed at architecture time (static), so kernels and cache layout are known in advance. Because only Full layers own a global cache, the persistent KV footprint scales with the number of Full layers rather than with L. This is the same instinct as cross-layer KV sharing (as in Gemma 3n or YOCO-style designs) applied to the compressed sparse cache and to the selection itself.

Idea 2 — Hierarchical Sparse Indexer

In the decoder, the first Full-mode layer builds a candidate pool from the full context. Later indexing layers search only inside that pool, so their cost is bounded by the pool size and no longer grows with context length. A third-party explainer describes V4.1-Flash as reading 512 selected entries plus a 128-token window per query^[18].

Idea 3 — FP4 main KV cache

Compressed KV and indexer keys are stored in 4-bit floating point (E2M1 values with one E4M3 scale per 16 channels); the window KV stays FP8. With modes and FP4 together, the global cache is 890 bytes per token — about a quarter of V4-Flash and, per the model card, 437× smaller than the original DeepSeek-V1 per token^[13]. Surrounding architecture: a Causal Encoder-Decoder of 20 + 20 layers where the decoder's global KV is projected from the final encoder states, activating ~8B parameters per token in prefill and ~16B in decode out of a 552B mixture-of-experts backbone.

8. GPU cost calculator: FLOPs and bytes per decode step

Set a model shape and context and compare mechanisms. Decode is the phase that matters for chat and agent workloads: each new token re-reads the cache, so "bytes read" is the number to watch; on an H100-class GPU at ~3 TB/s, 30 GB read per step caps you at ~100 tokens/s for a batch of one.

9. When to use what

Failure modes to watch

• Needle-in-a-haystack recall degrades with pure windows and with aggressive compression (HCA's 128-token summaries cannot recover a single number).
• Indexer mismatch. A top-k selector trained to imitate dense attention is only as good as that imitation; distribution shift (new languages, code) can silently drop the right tokens.
• Materialised score tensors. Naive top-k implementations allocate n × n/m scores per indexer head and OOM long before the model does^[17].
• Block masks that change every step. Generic block-sparse frameworks assume a static mask; data-dependent selection needs a fused kernel or you lose most of the win^[19].
• Batching. Different sequences select different blocks, so per-request gathers must be vectorised; naive loops serialise the batch.

10. Glossary

Attention sink

A token (usually the first one, or a learned pseudo-token) that absorbs attention mass when a query has nothing relevant to look at. Keeping sinks resident makes windowed attention numerically stable.

Block sparsity

Restricting attention at the granularity of tiles (e.g., 64×64 query–key blocks) instead of individual pairs, matching how GPU kernels stage data into shared memory.

BigBird

Google's 2020 sparse encoder: window + global + random blocks, with universal-approximation proofs.

Causal mask

The rule that token i may attend only to tokens j ≤ i in a decoder.

CED — Causal Encoder-Decoder

DeepSeek-V4.1-Flash's layout: 20 causal encoder layers whose final states supply the decoder's global KV cache.

CSA — Compressed Sparse Attention

DeepSeek-V4's mechanism: learned pooling of every m tokens into one KV entry, a lightning indexer over the compressed entries, top-k selection, plus a 128-token exact window and a per-head sink.

CSA2 — Compressed Sparse Attention 2

DeepSeek-V4.1-Flash's version: CSA with static per-layer Full / Reindex / Reuse modes that share compressed KV, indexer keys and top-k indices across layers, a hierarchical indexer, and an FP4 cache.

Decode

The generation phase: one new query per step attending over the cached context. Memory-bandwidth-bound.

Dilated attention

A window that attends to every r-th key, widening reach for the same cost.

DSA — DeepSeek Sparse Attention

DeepSeek-V3.2's mechanism: a lightning indexer scores all cached tokens; only the top-k (2048) get full MLA attention.

E2M1 / E4M3

Floating-point layouts: 1 sign, 2 exponent, 1 mantissa bit (FP4); 1 sign, 4 exponent, 3 mantissa bits (FP8). FP4 values are stored with a shared FP8 scale per group of channels.

FlashAttention

An exact attention kernel that tiles the computation so the n×n score matrix never touches HBM; IO-aware, not approximate.

FlexAttention

PyTorch's compiler-driven API for attention variants defined by a mask and a score-modification function; generates block-sparse kernels.

FLOP

Floating-point operation. A multiply-add counts as 2.

Global token

A token that attends to, and is attended by, all positions regardless of the sparse pattern.

GQA — Grouped-Query Attention

Several query heads share one key/value head, shrinking the KV cache by the group size.

HBM — High-Bandwidth Memory

The GPU's main memory (80–288 GB on current data-centre parts, ~3–8 TB/s). The KV cache lives here.

HCA — Heavily Compressed Attention

DeepSeek-V4 layers that compress 128 tokens per entry and attend densely over the resulting short cache.

Hierarchical Sparse Indexer

CSA2's decoder trick: the first Full layer produces a candidate pool; later layers search only that pool, so indexing cost stops scaling with context.

KV cache

Stored keys and values for all past tokens in every layer, so decode does not recompute them.

Lightning indexer

A small, low-precision attention-like scorer (few heads, small dimension) used only to rank candidates for selection.

Local attention

Synonym for sliding window attention.

LSE — log-sum-exp

The softmax normaliser; kernels return it so partial results over different key subsets can be merged exactly.

MLA — Multi-head Latent Attention

DeepSeek-V2/V3 attention that caches one low-rank latent per token from which all heads' K and V are reconstructed.

MoBA — Mixture of Block Attention

Moonshot's block routing: each query attends to the top-k context blocks ranked by similarity to the block's mean key.

MoE — Mixture of Experts

Feed-forward layers split into experts, only a few of which are active per token. Orthogonal to attention sparsity.

NSA — Native Sparse Attention

DeepSeek's Feb-2025 three-branch (compress / select / window) gated attention, trained from scratch.

Prefill

Processing the prompt in parallel before generation begins. Compute-bound; quadratic for dense attention.

Receptive field

The set of input positions that can influence a given output; for stacked windows it grows by w per layer.

Rolling buffer cache

A fixed-size KV cache of w slots written cyclically; the memory form of sliding window attention.

SWA — Sliding Window Attention

Each query attends to the previous w tokens only.

SWA Bounded Replay

Recomputing window KV by re-running the last w tokens instead of persisting it; keeps the persistent cache to the compressed global part.

Top-k selection

Keeping the k highest-scoring candidates. A hard (non-differentiable) operation; gradients flow through the scores of the selected items only.

11. References

1. Vaswani et al., Attention Is All You Need, 2017. arXiv:1706.03762
2. Dao et al., FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness, 2022. arXiv:2205.14135; FlashAttention-2, arXiv:2307.08691
3. Beltagy, Peters, Cohan, Longformer: The Long-Document Transformer, 2020. arXiv:2004.05150
4. Jiang et al., Mistral 7B, 2023 (sliding window 4096, rolling buffer cache). arXiv:2310.06825
5. Xiao et al., Efficient Streaming Language Models with Attention Sinks, 2023. arXiv:2309.17453
6. Gemma Team, Gemma 2: Improving Open Language Models at a Practical Size, 2024. arXiv:2408.00118
7. Gemma Team, Gemma 3 Technical Report, 2025. arXiv:2503.19786
8. Child, Gray, Radford, Sutskever, Generating Long Sequences with Sparse Transformers, 2019. arXiv:1904.10509
9. Zaheer et al., Big Bird: Transformers for Longer Sequences, 2020. arXiv:2007.14062
10. Dong et al., FlexAttention: A Programming Model for Generating Optimized Attention Kernels, 2024. arXiv:2412.05496
11. Yuan et al. (DeepSeek), Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention, 2025. arXiv:2502.11089
12. Lu et al. (Moonshot AI), MoBA: Mixture of Block Attention for Long-Context LLMs, 2025. arXiv:2502.13189
13. DeepSeek-AI, DeepSeek-V4.1-Flash: Pushing the Limits of KV Cache Compression, model card, Sep 2026. huggingface.co/deepseek-ai/DeepSeek-V4.1-Flash
14. DeepSeek-AI, DeepSeek-V3.2-Exp: Boosting Long-Context Efficiency with DeepSeek Sparse Attention, Sep 2025. github.com/deepseek-ai/DeepSeek-V3.2-Exp
15. DeepSeek-AI, DeepSeek-V4: Towards Highly Efficient Million-Token Context Intelligence, 2026. arXiv:2606.19348
16. Raschka, CSA and HCA (LLM Architecture Gallery) and Recent Developments in LLM Architectures: KV Sharing, mHC, and Compressed Attention, 2026. sebastianraschka.com/llm-architecture-gallery/csa-hca
17. Jaber & Jaber, StreamIndex: Memory-Bounded Compressed Sparse Attention via Streaming Top-k, 2026. arXiv:2605.02568
18. Tiwari, DeepSeek V4.1 Sparse Attention Explained with Pictures, KGP Talkie, Sep 2026 (third-party explainer). kgptalkie.com
19. torchtitan PR #4452, Refactor DeepSeek v4 to use Attention Gym's Compressed Sparse Attention, 2026. github.com/pytorch/torchtitan/pull/4452
20. DeepSeek-AI, DeepSeek-V2 (Multi-head Latent Attention), 2024. arXiv:2405.04434
21. Ainslie et al., GQA: Training Generalized Multi-Query Transformer Models, 2023. arXiv:2305.13245
22. Kitaev, Kaiser, Levskaya, Reformer: The Efficient Transformer, 2020. arXiv:2001.04451
23. Roy et al., Efficient Content-Based Sparse Attention with Routing Transformers, 2020. arXiv:2003.05997
24. Tang et al., Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference, 2024. arXiv:2406.10774
25. Zhang et al., H2O: Heavy-Hitter Oracle for Efficient Generative Inference, 2023. arXiv:2306.14048
26. Tay et al., Efficient Transformers: A Survey, 2020. arXiv:2009.06732

Figures quoted for DeepSeek models are as reported by the cited sources; whole-model efficiency ratios include changes beyond attention. Compiled September 2026.