Every method so far computes exact attention. FlashAttention computes it faster, and MQA, GQA, and MLA change what is cached but still let every query see every earlier key. The cost of that is still quadratic, $T^2$ scores per head, and §4.7 quoted a theorem (Keles et al. 2023) saying that exact attention cannot be computed in sub-quadratic time unless a widely believed conjecture in complexity theory fails. So to go below $T^2$ you must change the function. Let each query look at only some of the keys.

Which ones? The attention patterns of trained models give strong hints (§4.7). Many heads are local, attending to the last few tokens. Many dump their spare weight on the first token, the attention sink of §4.4. A few really do look far back. This section builds attention patterns from those observations, one at a time. Sliding windows and how far information travels through a stack of them, global tokens that connect everything in two steps, attention sinks that make windowed generation work, block-sparse patterns that a GPU can exploit, and the newest idea, letting the model learn which blocks to look at.

The sliding window

Let query $t$ attend only to the $w$ most recent positions, itself included,

Each row of the mask now has at most $w$ allowed keys, so the score and value products cost $O(Twd_k)$ instead of $O(T^2d_k)$, and a FlashAttention kernel skips every tile outside the band (§12.3). The cache shrinks too. A layer never needs keys more than $w$ tokens old, so it can keep a rolling buffer of $w$ slots and store the keys and values of token $i$ in slot $i \bmod w$, overwriting the oldest. Mistral 7B (Jiang et al. 2023) uses a window of 4,096 in all 32 layers, and reports that on 32K-token sequences the rolling buffer cuts cache memory by 8 times without hurting quality.

What does a window cost in quality? A single layer can no longer see past $w$ tokens. But a model has many layers, and they compose.

How far a stack of windows can see

After one layer, position $t$ holds information from positions $t-w+1, \dots, t$. After a second layer, it holds information from what those positions held, each of which reached back $w-1$ further. So after $L$ layers,

Proof, by induction on $L$. For $L = 1$ it is the window itself. If after $L$ layers position $u$ depends on $[u - L(w-1), u]$, then at layer $L+1$ position $t$ attends to $u \in [t - w + 1, t]$, whose combined ranges cover $[t - w + 1 - L(w-1), t] = [t - (L+1)(w-1), t]$. Every position in that range is reached, by attending to the right $u$, and nothing earlier is. $\blacksquare$

In plain words, the reach of the network grows linearly with depth, like the receptive field of a stack of convolutions (§0.8), which is what a sliding window is. Mistral's paper states the same thing as information moving forward by up to $W$ tokens per layer, for a theoretical span of about $32 \times 4096 \approx 131$K tokens. (Their $W$ counts the tokens back, our $w$ includes the token itself, so their $Wk$ is our $L(w-1)$ up to that off-by-one.) Longformer (Beltagy et al. 2020) gives the receptive field as $\ell\times w$ for $\ell$ layers with a two-sided window of $w$.

The cell checks the formula by brute force. Treat the mask as the adjacency matrix of a graph, as in §4.6, and compute which tokens can reach which through $L$ hops.

The receptive field is a theoretical upper limit, and it is much larger than what the model uses well in practice. Information that travels 100,000 tokens through a window of 4,096 has to be relayed through dozens of intermediate positions, each of which has many other things to represent, so it arrives faded if it arrives at all. A window is a strong bet that most of what matters is local.

def receptive_field(L, w, dilation=1):
    return L * w

def layers_needed(distance, w, dilation=1):
    return distance // w

Global tokens connect everything in two steps

A window is a band in the mask. Add a few global tokens that attend to every position and are attended to by every position, and the picture changes completely. Any token can now reach any other in two hops, through a global token, at any depth. In the language of graphs, the attention graph's diameter drops from about $T/w$ to 2.

Longformer (Beltagy et al. 2020) combined a sliding window with global attention on a few task-chosen tokens, the [CLS] token for classification or every question token for question answering. Global attention is symmetric (global tokens see everything, and everything sees them), it uses its own projections $\mathbf{W}_Q^g$, $\mathbf{W}_K^g$, $\mathbf{W}_V^g$, initialized from the local ones, and with a fixed number of global tokens the cost stays linear in $T$. The pretrained Longformer used a window of 512 and sequences of 4,096 tokens, eight times BERT's, at the same compute per token as RoBERTa. As a character-level language model it reached 1.10 bits per character on text8 and 1.00 on enwik8 with 41M parameters, with windows growing from the bottom layers to the top.

BigBird (Zaheer et al. 2020) added random attention to the mix. Each query attends to a window of $w$ neighbors, to $g$ global tokens, and to $r$ random keys. In its BERT-style setting the pattern is defined on blocks of 64 tokens, with 2 global blocks, a window of 3 blocks, and 3 random blocks per query block, for sequences of 4,096 tokens. Its theoretical results explain why the global tokens matter. With them, BigBird's sparse attention is a universal approximator of sequence functions and is Turing complete, like full attention. But the paper also proves a limit. Any sparse attention with $\tilde O(T)$ edges, BigBird's included, needs about $T$ layers for some tasks (finding the furthest vector in a set) that full attention solves in one layer, assuming a standard conjecture. Sparsity really is a different, weaker function class.

import numpy as np

def window_sink_mask(T_q, T_k, window, n_sink):
    p = np.arange(T_q)[:, None]                    # forgets the offset of the last T_q positions
    s = np.arange(T_k)[None, :]
    return (s <= p) & (p - s <= window)

Attention sinks, and generating forever

Sliding windows look like the obvious way to generate text longer than any training sequence. Keep a rolling cache of the last $w$ tokens and decode forever at constant memory. Xiao et al. (2023) tried it and watched it fail. With Llama-2-13B on a 65K-token book and a cache of only the 1,024 most recent tokens, perplexity exploded to 5,158 once the text outgrew the cache and the first tokens were evicted.

The reason is the attention sink (§4.4). Trained models park the attention mass they do not need on the first few tokens, whatever those tokens are. Evict them and that mass has to go somewhere, onto tokens that carry real content, and every layer's outputs shift. The fix, StreamingLLM, is to keep the first 4 tokens in the cache permanently, alongside the rolling window. With 4 sink tokens plus 1,020 recent ones, a cache of the same size, the same model's perplexity was 5.40. (Keeping four newline tokens instead of the true first tokens gave 5.60, which shows that position, not content, makes a sink.) The authors ran Llama 2, MPT, Falcon, and Pythia models stably on up to 4 million tokens, at up to 22.2 times lower per-token latency than a sliding window that recomputes its cache.

One more detail makes it work with rotary embeddings. StreamingLLM assigns positions within the cache, not in the original text. If the cache holds original tokens $0, 1, 2, 3, 6, 7, 8$ and the model is decoding the next one, those cached tokens are treated as positions $0, \dots, 6$ and the new one as position 7, so the model never sees a relative distance larger than it was trained on. That requires caching keys before rotation and re-rotating them at each step.

They also tested the explanation directly. Training small (160M-parameter) models from scratch with one dedicated, learnable sink token at the start of every sequence made a single sink enough for streaming, where ordinary models needed four. The extra-logit "attend to nothing" option of §4.4, used per head in OpenAI's gpt-oss models, is the same idea built into the softmax.

import numpy as np

class SinkCache:
    def __init__(self, n_sink, window, d):
        self.keys, self.ids = [], []
        self.window = window
    def append(self, k):
        self.keys.append(k); self.ids.append(len(self.ids))

Local and global layers, mixed

A model does not have to choose one pattern for every layer. The most common design today interleaves cheap local layers with a few full-attention layers. The local layers handle the nearby context that most tokens need, and the global layers handle the rest, at a fraction of the cache.

• Gemma 2 (2024) alternates a sliding window of 4,096 with global attention over 8,192 tokens, every other layer. Shrinking the window at inference to 1,024 barely changed perplexity (1.63 to 1.64).
• Gemma 3 (2025) uses 5 local layers for every global one, with a local window of only 1,024 tokens, and 128K context. The paper reports that perplexity is barely affected even at 7 local layers per global one.
• gpt-oss (OpenAI 2025) alternates full attention with a banded window of only 128 tokens, layer by layer.
• ModernBERT uses global attention every third layer and a 128-token window elsewhere (§7.1).

The saving is in the cache. Local layers keep at most $w$ tokens each, so at long context nearly all of the cache belongs to the global layers. The cell computes it for a Gemma 3 27B-shaped model (62 layers, 16 key-value heads of width 128), with 10 global layers in the 5-to-1 pattern.

At 128K tokens the mixed design needs about a sixth of the cache, and almost all of what remains is the 10 global layers. The cost is that only those layers can look far back directly.

Block-sparse patterns, and what hardware wants

Before windows became standard, the first large experiment with sparse attention was the Sparse Transformer (Child et al. 2019). It factorized attention into two heads. In the strided pattern, one head attends to the previous $l$ positions and the other to every $l$-th position, with the stride $l$ close to $\sqrt{T}$, so any position reaches any earlier one in two steps and the cost is $O(T\sqrt{T})$. The fixed pattern, which worked better on text, lets a position attend within its block of $l$ and to a few summary positions at the end of every earlier block. The models reached 0.99 bits per byte on enwik8 (context 12,288) and 2.80 bits per dimension on CIFAR-10, and modeled raw audio sequences of 65,536 samples.

What a GPU can exploit is sparsity at the granularity of tiles. A FlashAttention-style kernel skips a 128 by 128 tile only if every entry in it is masked. A pattern that keeps one entry in every tile saves nothing, while a pattern that keeps whole tiles saves exactly the fraction it drops. That is why BigBird defines its pattern on blocks, why block-sparse FlashAttention's cost is $\Theta(Td + T^2d^2s/M)$ for a fraction $s$ of nonzero blocks (§12.3), and why every modern sparse method selects blocks of keys. Compare the patterns in the gallery, and watch the gap between the fraction of entries kept and the fraction of tiles a kernel must visit.

import numpy as np

def bigbird_blocks(n, n_window=3, n_global=2, n_random=3, seed=0):
    i, j = np.arange(n)[:, None], np.arange(n)[None, :]
    return np.abs(i - j) <= n_window // 2          # window only

def diameter(mask):
    return 1

Learned sparsity, choosing which blocks to read

Fixed patterns decide in advance what each query may see. The newest methods let the model decide, per query, which blocks of keys are worth reading, and make that choice cheap enough to run inside the kernel.

MoBA (Lu et al. 2025), "mixture of block attention", treats key blocks like experts in a mixture of experts (§13.2). Each query scores every earlier block by its dot product with the block's mean-pooled key, keeps the top $k$ blocks plus its own (with a causal mask inside it), and attends only there. Moonshot reports that it has been deployed to serve long-context requests for its Kimi assistant.

Native Sparse Attention (NSA, Yuan et al. 2025) runs three branches and mixes them with learned gates $g \in [0, 1]$ per branch.

1. Compression. Blocks of 32 consecutive keys, with a stride of 16, are each compressed by a small learned network into one key and one value, and the query attends to all of them. This is a coarse view of the whole past.
2. Selection. The compressed branch's attention scores rank the blocks, and the query attends with full resolution to the top 16 blocks of 64 tokens, always including the first block and the 2 most recent. The scores are summed over the query heads of a GQA group, so the whole group reads the same blocks, which makes the memory access pattern efficient on GPUs.
3. Sliding window. The most recent 512 tokens, attended to directly, so the local pattern does not have to be learned by the other branches.

The word native is the point. The sparsity is used during pretraining, not imposed on a dense model afterwards, so the model learns to put what matters where the selection will find it. A 27B-parameter mixture-of-experts model with 3B active parameters, pretrained on 270B tokens, matched or beat its full-attention counterpart on the paper's benchmarks, and at 64K tokens its kernel ran 9.0 times faster in the forward pass and 6.0 times faster in the backward pass than FlashAttention-2 (both in Triton, on A100s). For decoding the paper estimates an 11.6 times speedup from the reduction in memory access, reading 5,632 instead of 65,536 tokens' keys and values.

DeepSeek Sparse Attention (DSA), introduced in DeepSeek-V3.2-Exp, selects individual tokens instead of blocks. A small "lightning indexer" with a few heads computes a cheap score $I_{t,s} = \sum_j w_{t,j}\operatorname{ReLU}(\mathbf{q}_{t,j}\cdot\mathbf{k}_s)$ for every earlier token (it can run in FP8), and the main attention reads only the 2,048 highest-scoring tokens per query. The indexer is still quadratic but far cheaper than the attention it replaces, which becomes $O(Tk)$. It was added to an existing dense model by continued training, first warming up the indexer alone and then training the whole sparse model on about 944B tokens at 128K context.

import numpy as np

def topk_block_attention(Q, K, V, B, k):
    T = len(Q)
    S = Q @ K.T / np.sqrt(Q.shape[1])
    S = np.where(np.tril(np.ones((T, T), bool)), S, -np.inf)       # full causal attention, no selection
    P = np.exp(S - S.max(1, keepdims=True)); P /= P.sum(1, keepdims=True)
    return P @ V

Linear attention, a preview

There is a more radical way out of the quadratic cost, which is to drop the softmax. If the similarity $\exp(\mathbf{q}^\top\mathbf{k})$ is replaced by a product of feature maps $\phi(\mathbf{q})^\top\phi(\mathbf{k})$, causal attention becomes

and the two sums can be carried forward as a fixed-size state, updated once per token. The model becomes a recurrent network with $O(1)$ cost per generated token and no growing cache. Katharopoulos et al. (2020) used $\phi(\mathbf{x}) = \operatorname{elu}(\mathbf{x}) + 1$ and measured image generation thousands of times faster than softmax attention. The price is the sharp, content-addressed lookup that softmax provides, since a fixed-size state cannot remember everything. Refining that state, with decay and selection, leads to the linear-time sequence models such as linear attention and Mamba, and to hybrid models that mix a few full-attention layers with many recurrent ones, the same local-global trade as above in a different form.

In PyTorch

FlexAttention (§12.4) expresses any of these patterns as a mask predicate, and its block mask shows exactly which tiles a kernel will visit. Here is a sliding window with four attention sinks, checked against a dense mask, with the block mask printed for a longer sequence.

At 4,096 tokens the block mask keeps the diagonal band of 128 by 128 tiles and the first column (the sinks), and the printed sparsity is the fraction of tiles a kernel skips. (For long sequences the printout merges neighboring tiles into one character cell, so the picture is coarser than the kernel's real 128-token grid.)

Read more

• Beltagy, Peters & Cohan (2020). Longformer: The Long-Document Transformer. Sliding, dilated, and global attention, with the receptive field argument in Section 3.1.
• Zaheer et al. (2020). Big Bird: Transformers for Longer Sequences. Random, window, and global attention, with proofs of universality, Turing completeness, and the limits of sparsity.
• Xiao et al. (2023). Efficient Streaming Language Models with Attention Sinks. Why window attention fails, attention sinks, and StreamingLLM.
• Child et al. (2019). Generating Long Sequences with Sparse Transformers. The strided and fixed factorized patterns, the first large-scale sparse attention.
• Jiang et al. (2023). Mistral 7B. Sliding-window attention and the rolling buffer cache in a widely used model.
• Yuan et al. (2025). Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention. Compression, selection, and window branches, with the kernel design.
• Lu et al. (2025). MoBA: Mixture of Block Attention for Long-Context LLMs. Top-k block selection with mean-pooled keys, deployed in production.
• Gemma Team (2025). Gemma 3 Technical Report. The 5-to-1 local-global design and its effect on cache memory and perplexity.

Watch next

▶

▶

▶