Learn: Sparse & Sliding-Window Attention

What you're learning

How to break the $O(s^2)$ wall by changing which pairs of tokens are allowed to attend, instead of changing the attention math itself. By the end you’ll be able to derive the effective receptive field of stacked windowed layers, place Longformer/BigBird on a pattern taxonomy, and explain why the first few tokens become “attention sinks” that make streaming decoding stable.

Sixth lesson of the Attention Mechanisms curriculum. Assumes lessons 01–05 (SDPA, MHA, positions, the quadratic bottleneck, and KV-cache / MQA-GQA-MLA). Vocabulary follows the attention-glossary.

---

1. Learning map

graph TD
    A["Problem: O(s²) dense attention<br/>every token sees every token"] --> B["Observation: attention<br/>weight is mostly LOCAL"]
    B --> C["Idea: restrict the PATTERN<br/>with a sparsity mask"]
    C --> D["Sliding window<br/>O(s·w), Mistral"]
    C --> E["+ Global tokens<br/>Longformer"]
    C --> F["+ Random edges<br/>BigBird (universal)"]
    D --> G["Depth grows the<br/>receptive field: ≈ L·w"]
    D --> H["Streaming decode:<br/>rolling KV window"]
    H --> I["Attention sinks<br/>StreamingLLM"]
    style B fill:#44a,color:#fff
    style C fill:#44a,color:#fff
    style I fill:#a44,color:#fff

---

2. Intuition: you don’t need every token to see every other

Lesson 04 left us at a wall: dense attention costs $O(s^2)$ in both compute and the size of the score matrix. But look at a trained attention map and a striking fact jumps out — most of the weight is local. A token attending mostly to its recent neighbors, plus a handful of special positions, explains the bulk of the mass. The all-pairs $s\times s$ interaction is paying in full for a matrix that is nearly sparse.

So the move is not to change the attention formula (softmax over QKᵀ stays exactly as in lesson 01) — it’s to change the pattern: decide ahead of time which $(i,j)$ pairs are even allowed to interact, and mask out the rest before softmax. Set the disallowed scores to $-\infty$ and they contribute nothing. If each query is only allowed $O(w)$ keys instead of $O(s)$, the cost collapses from $O(s^2)$ to $O(s\cdot w)$.

The CNN analogy (this is the load-bearing intuition)

A single convolution layer has a tiny receptive field, yet a deep CNN “sees” the whole image — because receptive fields compound with depth. Windowed attention is the same trick: one layer only looks $w$ tokens back, but a token’s window includes neighbors whose own windows reached further back last layer. Information propagates outward one window per layer, so $L$ stacked layers give an effective receptive field of $\approx L\cdot w$. Locality per layer, globality through depth.

"Sparse" ≠ "lossy by definition"

Restricting the pattern is an approximation of full attention — but a cheap-and-often-harmless one, because the discarded entries were small anyway. The failure mode is specific: genuinely long-range dependencies that no path of stacked windows can bridge within $L$ layers (e.g. a fact stated once at token 5 that matters at token 50,000 in a model too shallow for $L\cdot w$ to reach it). The global/random patterns below exist precisely to patch that hole.

---

3. The math: a taxonomy of patterns

Everything here is one operation with a binary mask $M\in \{0,1{\}}^{s\times s}$ applied to the scores:

$A=\mathrm{softmax}\left(\frac{Q{K}^{\top }}{\sqrt{d_k}}+\log M\right)V,\log M_{ij}=\{\begin{array}{ll}0& \text{allowed}\\ -\infty & \text{masked}\end{array}$

Dense causal attention is the special case $M_{ij}=1[j\le i]$. The cost of the core is proportional to the number of allowed entries, $\Vert M{\Vert }_0$, not $s^2$. Every pattern below is a choice of which entries stay 1.

3a. Sliding-window (local) attention — Mistral 7B

Each token attends only to itself and the previous $w$ tokens (causal window of size $w$):¹

$M_{ij}=1\left[i-w<j\le i\right]$

Allowed entries per row: $\le w$. Total core cost drops from $O(s^{2}d)$ to $\boxed{O(swd)}$ — linear in sequence length for fixed $w$. Mistral 7B uses $w=4096$ with a 32-layer stack.¹

Receptive field via depth. Layer 1 lets token $i$ see back to $i-w$. Those tokens, at layer 1, had already pulled in information from their windows, i.e. back to $i-2w$. Inductively, after $\ell$ layers token $i$ is influenced by tokens as far back as $i-\ell \cdot w$ (in the causal case; $i\pm \ell w$ for bidirectional). So an $L$-layer model has

$\text{effective receptive field}\approx L\cdot w.$

For Mistral, $L\cdot w=32\times 4096=131,072$ tokens of theoretical reach — far beyond any single layer’s 4096-token window.¹

Why this is the default long-context primitive

Sliding-window attention needs no new parameters and no new kernels beyond a masked SDPA — it’s a change to the mask and to what you keep in the KV cache. That’s why it’s the cheap workhorse (Mistral, and the local layers of many “hybrid” models that interleave a few full-attention layers for global reach).

3b. Longformer — window + dilation + global tokens

Longformer keeps the sliding window but adds two ingredients:²

• Dilation. Put gaps of size $d_{\text{dil}}$ inside the window (attend to every $d_{\text{dil}}$-th token), so a fixed budget of allowed keys reaches $d_{\text{dil}}\times$ further per layer — the same idea as dilated convolutions. Used in some heads to widen reach without widening cost.
• Global tokens. A few designated positions (e.g. [CLS], or question tokens in QA) attend to everything and are attended to by everything. This adds two full rows/columns per global token to $M$: a global token is a hub that any position can reach in one hop.

Cost stays $O(sw+sg)$ with $g\ll s$ global tokens — still linear in $s$. Longformer was the design that scaled BERT-style bidirectional attention to thousands of tokens for documents.²

3c. BigBird — window + global + random

BigBird combines three pattern types:³

1. Window — local neighbors (as above),
2. Global — a few tokens attend to / are attended by all (as in Longformer),
3. Random — each query attends to $r$ randomly chosen keys.

The random edges are the theoretical punchline: viewing the mask as a graph, random edges turn it into a sparse random (expander-like) graph with small diameter, so any two tokens are connected by a short path. Zaheer et al. prove that with these three ingredients BigBird is a universal approximator of sequence functions and is Turing-complete — i.e. sparsity this structured loses no expressive power in the limit, while costing $O(s)$ instead of $O(s^2)$.³

"Universal" is an existence result, not a free lunch

BigBird’s universality says a sparse-attention Transformer can represent what a dense one can — it does not say a given trained BigBird matches dense attention at fixed depth/width, nor that random access patterns are hardware-friendly. In practice window+global do most of the work; the random component is finicky to implement efficiently on GPUs (gather-scatter, poor coalescing). This is why deployed long-context stacks lean on window+global (+ a few dense layers) more than on random edges.

Quiz (retrieval): A model has $L=24$ layers and a causal sliding window of $w=512$. From memory: (a) per-layer attention cost in $s$, and (b) the deepest-layer effective receptive field. Could token 20,000 influence the prediction at token 20,050 through the window alone? What about influencing token 200,000?

Answer

(a) $O(swd)$ — linear in $s$ for fixed $w$. (b) $\approx L\cdot w=24\times 512=12,288$ tokens. Token 20,000 → 20,050 is a distance of 50 $\ll w$, so it’s captured within a single layer’s window — trivially yes. Token 20,000 → 200,000 is a distance of 180,000 $\gg L\cdot w=12,288$: no path of stacked windows can bridge it in 24 layers. That gap is exactly what global tokens (Longformer/BigBird) or occasional full-attention layers exist to fix.

---

4. Attention sinks & StreamingLLM

Now a twist that only shows up at inference / streaming time. Suppose you want to decode an effectively infinite stream (a chat that never ends) with bounded memory. The obvious idea: keep a rolling KV window — cache only the most recent $w$ tokens, evict the oldest. This is just sliding-window attention applied to the KV cache (lesson 05). It should work… and it catastrophically fails: perplexity blows up the moment the earliest tokens get evicted.⁴

The empirical finding — attention sinks. Xiao et al. observed that a huge fraction of attention mass, across layers and heads, is dumped onto the first few tokens of the sequence — regardless of whether those tokens are semantically important. They named these attention sinks. Evicting them is what breaks the model.⁴

Why do sinks exist? This is the mechanistic point worth locking in. Softmax is a convex combination: its weights are non-negative and must sum to 1. A query has no way to say “I don’t want to attend to anything this step” — even when the right answer is attend to nothing, softmax still forces it to spend all its probability mass somewhere. So the network learns a dumping ground: a default location to park the leftover mass harmlessly. The first tokens are the natural choice because, under causal masking, they are the only positions visible to every query in the sequence — they’re the universally reachable “ground” of the causal graph. The model overtrains a bias to route excess softmax mass there.

Sinks are the "softmax has to sum to 1" tax made visible

The clean way to remember it: dense softmax attention cannot output “no-op”, so it manufactures a no-op by over-attending to a fixed, always-visible position. (This is also the motivation behind proposed fixes like a learned “off” logit — sometimes called softmax-off-by-one / attention with a zero-sink slot — which give the model an explicit place to send the leftover mass.) [verify: the “+1 in the softmax denominator” fix is Evan Miller’s Attention Is Off By One, not from the StreamingLLM paper.]

The fix — StreamingLLM. Keep a tiny number of initial “sink” tokens permanently in the KV cache plus the rolling recent window. Concretely: cache the first $k$ tokens (Xiao et al. find $k\approx 4$ suffices) and the most recent $w$ tokens, dropping the middle.⁴ With the sinks retained, the leftover-mass dumping ground still exists, the attention distributions stay in-distribution, and the model decodes stably over millions of tokens with $O(w)$ memory — no fine-tuning required.⁴

StreamingLLM extends stability, not memory

It does not give the model access to information from the evicted middle tokens — those are gone. It lets a fixed-window model keep generating coherently forever without the perplexity explosion. If you need the model to actually recall far-back content, you need real long context (bigger window, retrieval, or global/dense layers), not sinks.

Quiz (retrieval): Explain in two sentences why attention sinks form, and why a naive rolling-window KV cache (recent-$w$ only) breaks while StreamingLLM (sinks + recent-$w$) doesn't.

Answer

Softmax weights are non-negative and sum to 1, so a query is forced to place all its mass somewhere even when it wants to attend to nothing; the model learns to dump this leftover mass on the first few tokens, which are visible to every query under causal masking — those become “sinks.” A naive rolling window evicts exactly those sink tokens, so queries must redistribute their large parked mass onto tokens that were never trained to receive it, pushing the attention distribution out of distribution and spiking perplexity; StreamingLLM keeps ~4 initial sink tokens alongside the recent window, preserving the dumping ground and keeping distributions in-distribution.

Quiz (retrieval): Mistral uses a sliding window during training. StreamingLLM uses sinks + a rolling window at inference on already-trained models. Why are these not the same technique even though both keep a window?

Answer

Mistral’s window is an architectural choice baked into training: the model never attends outside $w$, and long-range reach comes from the $L\cdot w$ depth effect. StreamingLLM is a test-time KV-cache eviction policy applied to models (possibly full-attention ones) that were not trained for infinite streaming — it exploits the emergent attention-sink phenomenon to keep those models stable when you throw away most of their KV cache. One shapes what the model can learn to attend to; the other manages what you keep in memory at decode time.

---

5. Illustration: the masks side by side

Rows = queries, columns = keys; a filled cell means “allowed” ($M_{ij}=1$). Causal (lower-triangular) case, $s=8$, window $w=2$.

Grey = local window; blue = global hub token (reads and is read by all); red = retained “sink” token(s) kept in the KV cache alongside the rolling recent window. Longformer/BigBird add global (and BigBird also random) edges on top of the window; StreamingLLM keeps sinks + recent and evicts the middle. Source: patterns from Mistral¹, Longformer², BigBird³, StreamingLLM⁴.

---

6. FLOPs & memory

Reusing the lesson-01 accounting (multiply-add = 2 FLOPs; batch $b$, model dim $d$, single-head view), the attention core cost is proportional to the number of allowed score entries:

Pattern	Allowed entries	Core FLOPs (scores + A·V)	Scaling in $s$
Dense	$s^2$	$\approx 4b{s}^{2}d$	quadratic
Sliding window ($w$)	$sw$	$\approx 4bswd$	linear
Window + global ($g$)	$sw+2gs$	$\approx 4bs(w+2g)d$	linear ($g\ll s$)
BigBird (win + $g$ global + $r$ random)	$s(w+2g+r)$	$\approx 4bs(w+2g+r)d$	linear

The projections $Q,K,V,O$ still cost $O(bs{d}^2)$ regardless of the pattern — sparsity only touches the $s^2$ term. So sparse attention pays off precisely in the long-context regime where the $s^2$ term dominates the $s{d}^2$ term (roughly $s\gtrsim d$); at short $s$ the projections dominate and sparsity buys little.

KV-cache / memory (the inference story). This is where sliding windows shine at decode time (recall lesson 05’s KV cache):

• Dense decode: KV cache grows $O(s)$ — every past token’s K and V is retained forever. This is usually the binding inference constraint at long context.
• Sliding-window decode: you only ever need the last $w$ tokens’ K/V, so the cache is bounded at $O(w)$, independent of how much you’ve generated. Mistral implements this as a rolling buffer cache of fixed size $w$.¹
• StreamingLLM decode: $O(k+w)$ — the $k\approx 4$ sink tokens plus the recent window — enabling constant-memory generation over unbounded streams.⁴

Try it: sparse vs dense in the calculator

Open the Attention FLOPs & KV-cache calculator. Set $d=4096$, $b=1$, and compare dense prefill at $s=32\text{k}$ against a windowed estimate: multiply the dense $Q{K}^{\top }$/$AV$ terms by $w/s$ (e.g. $w=4096,s=32\text{k}\Rightarrow \times \frac{1}{8}$). Then watch the KV cache: dense grows with $s$, but a rolling window pins it at the size for $w$ tokens. The conceptual link: sparsity rescales the $s^2$ term by $w/s$ and caps the cache at $w$.

Quiz (retrieval): You switch a 32k-context layer from dense to a sliding window of $w=2048$. Estimate the factor reduction in (a) the $Q{K}^{\top }$ score FLOPs and (b) the decode-time KV-cache size.

Answer

(a) Scores go from $\propto s^2$ to $\propto sw$, a factor of $w/s=2048/32768=1/16$ — a 16× reduction. (b) The KV cache goes from $O(s)$ (32k tokens) to $O(w)$ (2k tokens), also 16× smaller and, crucially, constant as generation continues rather than growing. Note projections and MLP are untouched, so end-to-end speedup is smaller than 16×.

---

7. Practice

Problem: designing a long-context stack

You must serve 128k-token context on a fixed memory budget. You consider (i) pure sliding window $w=4096$ over $L=32$ layers, and (ii) sliding window in 30 layers + full attention in 2 layers. What long-range dependencies does (i) provably miss, and how does (ii) fix it? What does it cost?

Solution. (i) Effective receptive field $\approx L\cdot w=32\times 4096=131,072\approx 128\text{k}$ — so in principle a signal can propagate end-to-end, but only via a length-32 chain of windows, i.e. every intermediate layer must preserve and relay it. Fragile for a single token that matters 128k away, and it fully breaks for context $>131\text{k}$. (ii) The 2 full-attention layers give every token a one-hop path to any other token, robustly bridging arbitrary distances; cost is $2\times$ the dense $O(s^{2}d)$ term (the 2 dense layers) $+30\times$ the cheap $O(swd)$ term — dominated by those 2 dense layers but far below 32 dense layers. This “mostly-local, a-few-global/dense” hybrid is the standard long-context recipe.

Problem: why not just make $w$ huge?

If depth gives receptive field $L\cdot w$, why not set $w=s$ and use one layer? Conversely, why not $w=1$ and rely entirely on depth?

Solution. $w=s$ is just dense attention — you’re back to $O(s^2)$, defeating the purpose. $w=1$ makes each layer see only itself + one neighbor, so reaching distance $s$ needs $\sim s$ layers (absurd depth) and forces every long-range signal through a long, lossy relay chain, hurting optimization and fidelity. The sweet spot is $w$ large enough that (a) most real dependencies are intra-window and (b) $L\cdot w\gtrsim s$ with realistic $L$, while $w\ll s$ so the $O(sw)$ saving is real. Mistral’s $w=4096,L=32$ is one such balance.

---

Read next / primary sources

• Sliding window / rolling KV cache: Jiang et al., Mistral 7B — arXiv:2310.06825, §2 (Sliding Window Attention, Rolling Buffer Cache).¹
• Window + dilation + global: Beltagy, Peters, Cohan, Longformer — arXiv:2004.05150.²
• Window + global + random, universality proof: Zaheer et al., Big Bird — arXiv:2007.14062 (the universality/Turing-completeness argument is in the appendix).³
• Attention sinks / streaming: Xiao et al., Efficient Streaming Language Models with Attention Sinks (StreamingLLM) — arXiv:2309.17453.⁴

Ask your teacher

Want the receptive-field induction written out formally, a walk-through of BigBird’s expander-graph diameter argument, or a look at how FlashAttention kernels handle a windowed mask efficiently? Ask — I can go deeper on any piece or hand you a harder problem.

What’s next

• 07-linear-and-subquadratic — instead of masking the $s\times s$ matrix, avoid materializing it at all: kernel/linear attention and state-space-style methods that are subquadratic by construction.
• Back to 05-mqa-gqa-mla — sparse patterns and KV-head sharing are complementary levers on the same inference-memory bottleneck; production stacks combine them.

---

References

Reference: attention-mechanisms | attention-glossary | Filed: 2026-09-10

Footnotes

1. Jiang, Sablayrolles, Mensch, et al., “Mistral 7B” — arXiv:2310.06825 (2023). Introduces Sliding Window Attention ($w=4096$, 32 layers, effective context $\approx L\cdot w$) and the fixed-size Rolling Buffer KV cache. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

2. Beltagy, Peters, Cohan, “Longformer: The Long-Document Transformer” — arXiv:2004.05150 (2020). Sliding-window + dilated-window + task-motivated global attention; linear $O(s)$ scaling for long documents. ↩ ↩² ↩³ ↩⁴

3. Zaheer, Guruganesh, Dubey, et al., “Big Bird: Transformers for Longer Sequences” — arXiv:2007.14062 (2020). Combines window, global, and random attention; proves the resulting sparse attention is a universal approximator and Turing-complete. ↩ ↩² ↩³ ↩⁴

4. Xiao, Tian, Chen, Han, Lewis, “Efficient Streaming Language Models with Attention Sinks” — arXiv:2309.17453 (2023). Identifies the attention-sink phenomenon (mass concentrated on initial tokens) and shows that retaining ~4 sink tokens plus a rolling recent window enables stable, constant-memory decoding over millions of tokens without fine-tuning. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷