Attention variants 2: a first look at sliding windows, linear attention and SSMs
Full attention looks at every earlier token, so its cost grows with the square of the length and its cache grows forever. This session takes a first look at three ways out: sliding windows (Mistral, Gemma), linear attention, and state space models like Mamba. It also explains attention sinks, the strange reason a pretrained model breaks when you drop its first token.
What you will learn
- Sliding-window attention: the banded mask, its cost, the rolling buffer KV cache, and the reach of about L × W tokens through L layers
- Local + global designs: global tokens (Longformer, BigBird) and interleaved layers (Gemma 2 and Gemma 3), with cache numbers
- Linear attention: the kernel trick, why it is an RNN with a d × d state, and why the cost becomes O(T)
- What linear attention loses: sharp focus and recall, shown with real weights
- State space models: the discretized recurrence, and how Mamba makes it selective
- Attention sinks: why softmax creates them and how StreamingLLM keeps a model stable over millions of tokens
- How to choose between these designs, and where they appear in long-context and video systems
Why this matters
Standard attention lets every token look at every earlier token. That is its power, and also its cost: the work grows with the square of the sequence length, and the KV cache grows with the length itself. At 128K tokens, those costs dominate everything else.
In session 26 we made the KV cache smaller by sharing keys and values between heads (MQA, GQA) or compressing them (MLA). Those methods keep the idea that each token can see the whole past. This session looks at three ideas that break that rule on purpose, and at one strange effect that appears when you do:
- Sliding-window attention. Each token looks only at the last \(W\) tokens. Mistral 7B uses it in every layer; Gemma 2 and Gemma 3 mix window layers with full layers. [Certain]
- Linear attention. Remove the softmax, use a “kernel” feature map instead, and attention becomes an RNN with a fixed-size state. Cost per token becomes constant.
- State space models (SSMs) such as Mamba. A recurrent layer with a fixed-size state, designed from the start to be trained in parallel and run as an RNN.
- Attention sinks. Models put a lot of attention on the first token, even when it means nothing. If you throw it out of a sliding window, the model breaks. Keep it, and the model can stream millions of tokens (StreamingLLM).
This is a first look. Each idea gets a full deep dive later, in the efficient-inference part of the course: session 116, session 99, session 100 and session 101. Here the goal is to understand what each one does, what it costs, and what it gives up, so that you can place it on a map and answer a first interview question about it.
The starting point: full causal attention
Recall the attention output for the token at position \(i\) in a decoder. It is a weighted average of the value vectors of all positions \(j \le i\):
- Read the symbols
- \(\mathbf{q}_i, \mathbf{k}_j, \mathbf{v}_j\)
- the query of token \(i\), and the key and value of token \(j\), each a vector of length \(d\) (one head)
- \(\alpha_{ij}\)
- how much token \(i\) attends to token \(j\); for each \(i\) the weights are positive and sum to 1
- \(T\)
- the sequence length (used below)
Two costs follow directly. Compute: there is one score \(\mathbf{q}_i^\top \mathbf{k}_j\) for every pair \(j \le i\), so \(T(T+1)/2\) scores per head per layer. For \(T = 32{,}768\) that is 536,887,296 scores. Memory at inference: to make token \(i\), we need the keys and values of all earlier tokens. They are kept in the KV cache, which grows by one entry per token, forever.
Everything in this session changes one of two things: which pairs \((i, j)\) are allowed (sliding windows, sinks, global tokens), or how the weighted average is computed (linear attention, SSMs).
Sliding-window attention
The simplest change: token \(i\) may only attend to the last \(W\) tokens, itself included. All other scores are masked to \(-\infty\) before the softmax, exactly like the causal mask, so they get weight 0:
\(W\) is the window size. Each row of the attention matrix now has at most \(W\) non-zero entries, so the work is about \(T \cdot W\) scores instead of \(T^2/2\). For \(T = 32{,}768\) and \(W = 4{,}096\), it is 125,831,168 scores instead of 536,887,296: 4.27 times fewer. The gain grows with \(T\).
Information still travels: the receptive field
A window does not mean the model forgets everything older than \(W\). In layer 1, token \(i\) sees positions \(i-W+1\) to \(i\). But each of those hidden states already summarizes its own window from the layer below. So after \(L\) layers, information can come from up to
The Mistral 7B paper uses exactly this argument: with \(W = 4{,}096\) and 32 layers, the theoretical span is about \(32 \times 4{,}096 = 131{,}072\) tokens. [Certain] The word “theoretical” matters. Information that must pass through 32 hand-offs gets mixed and diluted on the way. Direct attention to a fact 100K tokens back is not the same as an indirect path through every layer. [Likely] Figure 1 lets you see the window and the reach.
How to read Figure 1
Start with “Sliding window”, \(W = 4\), and the last row (query 15). It has 4 direct keys. Move \(L\) to 2, 3, 4: the reach grows by \(W - 1 = 3\) positions per layer, to 7, 10 and 13 positions, as formula (27.3) says. Now pick “Window + global tokens”: positions 0 and 8 can be seen by everyone and see everything before them. With \(L = 2\) the last row already reaches all 16 positions, because a global token acts as a hub. The readout also counts how many of the 136 causal pairs are kept.
The KV cache becomes a fixed-size ring
The biggest practical win is at inference. A token that has left the window will never be attended to again, in any layer. So we can delete its keys and values. Mistral calls this a rolling buffer cache: a cache with exactly \(W\) slots, where the keys and values of token \(i\) are written into slot \(i \bmod W\), overwriting the oldest entry. [Certain] Memory stops growing once \(T \gt W\):
- Read the symbols
- \(2\)
- one key and one value per token
- \(L, H_{kv}, d_h\)
- number of layers, number of key-value heads (after GQA), and the size of one head
- \(b\)
- bytes per number: 2 for FP16 or BF16
- \(\min(T, W)\)
- how many tokens are cached: all of them for full attention (\(W = \infty\)), at most \(W\) with a window
Mistral 7B has \(L = 32\) layers, \(H_{kv} = 8\) KV heads (GQA with 32 query heads), \(d_h = 128\), and \(W = 4{,}096\). [Certain] In BF16, one token costs \(2 \times 32 \times 8 \times 128 \times 2 = 131{,}072\) bytes, which is 128 KiB.
At \(T = 32{,}768\) tokens, a full cache needs \(32{,}768 \times 128\) KiB = 4 GiB per sequence. The rolling buffer keeps only 4,096 tokens: 0.5 GiB. That is the 8× saving reported in the Mistral paper for a 32K sequence. [Certain] At 128K tokens the full cache would be 16 GiB; the rolling buffer is still 0.5 GiB.
The rolling buffer is the first algorithm of this session:
- input: window \(W\); cache slots \(K[0..W{-}1]\), \(V[0..W{-}1]\); optional number of sink tokens \(S\) (0 for plain sliding window)
- for each new token at position \(i = 0, 1, 2, \dots\):
- compute \(\mathbf{q}_i, \mathbf{k}_i, \mathbf{v}_i\)
- if \(i \lt S\): store \(\mathbf{k}_i, \mathbf{v}_i\) in a separate sink area that is never overwritten
- else: write them into slot \((i - S) \bmod (W - S)\) // overwrites the oldest non-sink token
- scores \(\leftarrow \mathbf{q}_i^\top \mathbf{k} / \sqrt{d}\) for every filled slot // order of slots does not matter for softmax
- \(\mathbf{o}_i \leftarrow \softmax(\text{scores})\, V\) // at most \(W\) entries: constant cost per token
One detail: the slots are not in time order, but softmax and the weighted sum do not care about order. Position information was already put into the keys (with RoPE, before caching), so nothing is lost. [Certain]
Local + global patterns
A pure window can never look directly far back. Two families of fixes are used in practice:
- Global tokens (Longformer, BigBird). A few chosen positions, for example a [CLS] token or the question in a QA task, attend to everything and are attended by everyone. They act as hubs (Figure 1, last mode). BigBird also adds a few random links. [Certain] These designs were mostly used in encoders for long documents.
- Interleaved layers. Some layers use a window, others use full attention. Gemma 2 alternates 1:1 with a 4,096-token window. Gemma 3 uses 5 local layers for every global layer, with a window of only 1,024 tokens, and a 128K context. [Certain] Only the global layers need a full-length KV cache.
A simple estimate, assuming all layers have the same KV shape. At \(T = 131{,}072\), a global layer caches 131,072 tokens and a local layer caches 1,024. The average over 6 layers is \((5 \times 1{,}024 + 131{,}072) / 6 = 22{,}699\) tokens, which is 17.3% of an all-global model. The 1:1 pattern of Gemma 2 with \(W = 4{,}096\) would keep 51.6%. Most of the remaining cost is in the few global layers.
Figure 2 puts these numbers side by side for the Mistral 7B shape, so you can change \(T\) and \(W\).
How to read Figure 2
At \(T = 32{,}768\) and \(W = 4{,}096\) the full cache is 4 GiB and the window cache is 0.5 GiB: the 8× from the worked example. Move \(T\) to the right: the full bar keeps growing, the window bar stops at \(W\), and the linear-attention state never changes (8 MiB). The 5:1 bar always uses a window of 1,024 for its local layers, like Gemma 3. The readout also gives the number of attention scores per head and layer for full and windowed attention.
Linear attention: the kernel trick
Sliding windows keep softmax and drop pairs. Linear attention keeps all pairs and drops the softmax. Write the attention weight with a general similarity function \(\text{sim}(\mathbf{q}, \mathbf{k})\). Softmax attention uses \(\text{sim} = \exp(\mathbf{q}^\top\mathbf{k}/\sqrt{d})\). Katharopoulos et al. (2020) replaced it with a dot product of feature maps, a function \(\phi\) applied to the query and to the key separately:
Here \(\operatorname{elu}(x) = x\) for \(x \gt 0\) and \(e^x - 1\) otherwise, so \(\phi(x) \gt 0\) always. Positive weights are needed so that the normalized weights still look like an average. This idea is called the kernel trick, because a function \(\text{sim}(\mathbf{q}, \mathbf{k})\) that can be written as \(\phi(\mathbf{q})^\top\phi(\mathbf{k})\) is a kernel. Plug it into (27.1):
The trick is the step in the middle: \(\phi(\mathbf{q}_i)\) does not depend on \(j\), so it moves out of the sum. What is left, \(S_i\), is a \(d \times d\) matrix that does not depend on the query at all. It can be built once and updated one token at a time:
- Read the symbols
- \(\phi(\mathbf{k}_i)\, \mathbf{v}_i^\top\)
- an outer product: a \(d \times d\) matrix that “writes” value \(\mathbf{v}_i\) under the address \(\phi(\mathbf{k}_i)\)
- \(S_i\)
- the state: a fixed-size memory that sums all writes so far
- \(\mathbf{z}_i\)
- the sum of all addresses, used to normalize (it plays the role of the softmax denominator)
- \(\phi(\mathbf{q}_i)^\top S_i\)
- a “read” from the memory with the query as the address
This is an RNN. The paper’s title says it: “Transformers are RNNs”. [Certain] At inference, each new token costs a fixed \(O(d^2)\) work and the state has a fixed size, no matter how long the sequence is. In training we can use the parallel form, with the causal mask applied to \(\phi(Q)\phi(K)^\top\), or a chunked mix of both.
Why the cost is \(O(T)\)
Without the causal mask, the whole computation is a question of where to put the brackets. With \(Q, K, V \in \R^{T \times d}\):
Matrix multiplication is associative, so both give the same result. Softmax blocks this: \(\exp(\mathbf{q}^\top\mathbf{k})\) cannot be split into a part for \(\mathbf{q}\) and a part for \(\mathbf{k}\) with a finite \(\phi\). The second order is cheaper when \(T \gt d\). For \(T = 4{,}096\) and \(d = 128\), the score matrix \(T \times T\) has 16.8 million entries, while the state is a \(128 \times 128\) matrix with 16,384 entries. The authors report up to 4,000× faster autoregressive generation on very long sequences. [Certain]
- input: queries, keys, values \(\mathbf{q}_i, \mathbf{k}_i, \mathbf{v}_i \in \R^{d}\) for \(i = 1..T\); feature map \(\phi\)
- \(S \leftarrow 0_{d \times d}\), \(\mathbf{z} \leftarrow 0_d\)
- for \(i = 1\) to \(T\):
- \(S \leftarrow S + \phi(\mathbf{k}_i)\mathbf{v}_i^\top\) // write, formula (27.7)
- \(\mathbf{z} \leftarrow \mathbf{z} + \phi(\mathbf{k}_i)\)
- \(\mathbf{o}_i \leftarrow S^\top\phi(\mathbf{q}_i) \,/\, (\phi(\mathbf{q}_i)^\top\mathbf{z})\) // read; \(O(d^2)\) per token, no KV cache
- return \(\mathbf{o}_1, \dots, \mathbf{o}_T\)
What linear attention loses
There is no free lunch. Two things are lost, and both explain why pure linear attention has not replaced softmax in large LLMs: [Likely]
- Sharpness. Softmax can put almost all its weight on one token, because \(\exp\) grows very fast. A feature map like \(\operatorname{elu} + 1\) grows only linearly, so the weights stay spread out. Figure 3 makes this concrete: with 8 keys and a perfectly matching query, softmax gives the matching key a weight of 0.982 at scale 16. Linear attention gives it only 0.222, and that value hardly moves as the scale grows.
- Memory capacity. All the past is squeezed into one \(d \times d\) matrix. It can hold only about \(d\) different key directions without interference. With more tokens, new writes blur old ones. This shows up as weak recall: copying a phone number from far back, or finding one fact in a long document. [Likely]
How to read Figure 3
Move the scale \(s\) up. A larger query norm makes softmax sharper: the weight of key 0 rises from 0.268 at \(s = 1\) to 1.000 at \(s = 32\), and its entropy falls toward 0. Linear attention barely changes: its largest weight goes from 0.195 to 0.225, and the keys at 45° and 315° stay almost as important as key 0. A model with linear attention cannot “look at exactly one token”, which is the thing that recall tasks need.
Many later designs fix part of this. Performer uses random features that approximate the softmax kernel. [Certain] RetNet, gated linear attention and Mamba-2 multiply the state by a decay or a learned gate before each write, so old notes fade instead of piling up. [Likely] That brings us to state space models.
State space models and Mamba
A state space model (SSM) comes from control theory. It describes a system with a hidden state \(\mathbf{h}(t)\) that changes over continuous time, driven by an input \(x(t)\):
For text, time is discrete: one token per step. With a step size \(\Delta\), the standard “zero-order hold” rule turns (27.9) into a recurrence:
- Read the symbols
- \(x_t, y_t\)
- one input channel and one output channel at step \(t\); a layer runs many channels side by side
- \(\mathbf{h}_t \in \R^{N}\)
- the state for that channel; \(N\) is the state size (Mamba’s speed tests use \(N = 16\)) [Certain]
- \(A, B, C\)
- learned matrices; \(A\) is usually diagonal with negative entries, so the state decays
- \(\Delta\)
- the step size: small \(\Delta\) means “barely change the state”, large \(\Delta\) means “reset the state toward the new input”
This looks like an RNN, and it is one. The difference from an LSTM is that the recurrence is linear in \(\mathbf{h}\) (no tanh inside the loop). Linear recurrences can be computed for all \(t\) at once, with a convolution (S4) or a parallel scan, so training is parallel like a transformer. At inference, the model is an RNN with a fixed-size state: no KV cache. [Certain]
A 1-D example with \(A = -1\), \(B = C = 1\) makes (27.10) simple: \(\bar a = e^{-\Delta}\) and \(\bar b = 1 - e^{-\Delta}\), so
The state is a moving average whose memory length is set by \(\Delta\).
The Mamba idea: make the SSM selective
Earlier SSMs (S4) used the same \(\Delta, B, C\) for every token. Such a model is linear time-invariant: it treats every token the same way, so it cannot decide to remember one token and ignore the next. Gu and Dao (2023) argue that this is why such models were weak on language, which needs content-based decisions. [Certain] Mamba makes \(\Delta\), \(B\) and \(C\) functions of the current input:
\(A\) stays a fixed learned parameter. Because \(\bar A_t\) now changes with \(t\), the convolution trick of S4 no longer works. Mamba instead uses a hardware-aware parallel scan that keeps the state in fast on-chip memory. [Certain] The Mamba block also replaces both the attention and the MLP block, with an expansion factor of 2. [Certain] Figure 4 shows why selectivity matters.
How to read Figure 4
The readout gives the final state \(h_{15}\) and the part of it that still comes from token 3, which is \((1 - e^{-\Delta_3}) \prod_{t \gt 3} e^{-\Delta_t}\). With a fixed \(\Delta\), there is a trade-off: a large \(\Delta\) writes token 3 strongly but erases it quickly; a small \(\Delta\) keeps it but writes it weakly. No fixed \(\Delta\) keeps more than about 2.9% of it. The selective model writes strongly once and then barely erases: 74.7% is left after 12 filler tokens.
- input: state \(\mathbf{h} \in \R^N\) from the last token; new input vector \(\mathbf{x}_t\) and its channel value \(x_t\)
- \(\Delta_t \leftarrow \operatorname{softplus}(\text{Linear}_\Delta(\mathbf{x}_t))\); \(\;B_t \leftarrow \text{Linear}_B(\mathbf{x}_t)\); \(\;C_t \leftarrow \text{Linear}_C(\mathbf{x}_t)\) // formula (27.12)
- \(\bar{\mathbf{a}} \leftarrow \exp(\Delta_t\, \operatorname{diag}(A))\) // elementwise, each entry in (0, 1)
- \(\mathbf{h} \leftarrow \bar{\mathbf{a}} \odot \mathbf{h} + \Delta_t B_t\, x_t\) // formula (27.10); Mamba uses this simpler \(\bar B \approx \Delta B\)
- \(y_t \leftarrow C_t^\top \mathbf{h}\)
- return \(y_t\) and the new \(\mathbf{h}\) // constant time and memory per token
The size of the state is easy to count. For a layer with model width 2,048, expansion 2 and \(N = 16\), there are \(2 \times 2{,}048 = 4{,}096\) channels with 16 numbers each: 65,536 numbers per layer, whatever the sequence length. Mamba reports about 5× higher generation throughput than a transformer of similar size, and Mamba-3B matching transformers twice its size in their tests. [Certain] (These are the paper’s numbers; the gap at larger scales and on recall-heavy tasks is a topic of session 101.)
One family, seen from far away
Put formulas (27.7) and (27.10) next to each other. Linear attention adds \(\phi(\mathbf{k}_t)\mathbf{v}_t^\top\) to a matrix state and never forgets. An SSM multiplies the state by \(\bar A\) (forget a bit) and adds \(\bar B x_t\). A gated linear-attention layer does both: \(S_t = G_t \odot S_{t-1} + \mathbf{k}_t\mathbf{v}_t^\top\). Mamba-2 makes this link exact and calls it “state space duality”. [Certain] So the real design question is: how big is the state, and how does the model decide what to forget? Softmax attention answers “never forget, keep everything” and pays with a growing KV cache.
In practice, many recent models are hybrids: mostly SSM or linear-attention layers, plus a few full-attention layers for exact recall. Jamba, for example, mixes Mamba layers and transformer layers with MoE and supports up to 256K tokens. [Certain] Its ratio is one attention layer for every seven Mamba layers. [Likely]
Attention sinks
Back to sliding windows, with a surprise. Take a model trained with full attention, such as Llama 2, and run it with a plain sliding-window cache: keep the last \(W\) tokens and evict the rest. As soon as the first token is evicted, the output becomes nonsense and perplexity explodes. [Certain] Xiao et al. (2023) found the reason. Trained LLMs put a large share of attention on the first few tokens in many heads and layers, even when those tokens are just “<s>” or “The”. They called these tokens attention sinks.
Why does this happen? Softmax weights must sum to 1:
A head that finds nothing useful still has to put its weight somewhere. The first token is visible to every later token, so the model learns to use it as a “do nothing” place: a key that matches many queries, with a value close to zero. [Likely] Evicting it forces the weight onto the remaining tokens. Every remaining weight is divided by \(1 - \alpha_{\text{sink}}\), so if the sink had 0.5, all other weights double, and the head now outputs a mix it never produced in training.
StreamingLLM fixes this without any training: keep the keys and values of the first 4 tokens forever, plus a rolling window of recent tokens (for example 4 + 1,020). Positions are assigned inside the cache, not in the original text. [Certain] With this, Llama 2, MPT, Falcon and Pythia model text stably for up to 4 million tokens, and it is up to 22.2× faster than recomputing a sliding window from scratch. [Certain] Note what it does not do: it does not give the model memory of the evicted middle. A fact that left the window is gone.
How to read Figure 5
With the full cache the sink takes 0.495 of the attention, and the 7 most recent tokens (9–15) share 0.263. Switch to “Window only”: the sink is gone, and the same 7 tokens jump to 0.866 of the weight, more than 3 times as much. The output value changes from 0.131 to 0.271. Switch to “Sink + window”: the sink takes 0.653, the recent tokens get 0.347, close to the full-cache pattern. The output (0.044) is not identical, because tokens 1–8 are really gone, but the head behaves as it did in training.
Two follow-ups are worth knowing. First, the paper suggests adding a dedicated placeholder token to every training sequence, so that one known token plays the sink role. [Certain] Second, the same effect appears in vision: Vision Transformers dump attention into a few background patches with very large norms, and adding extra “register” tokens removes these artifacts. [Certain] Some recent open-weight models, for example OpenAI’s gpt-oss, build a learned sink directly into each attention head. [Likely]
PyTorch: windows, linear attention and a selective scan
The code below checks four claims of this session on random data: a windowed mask equals full attention on the first \(W\) rows; a rolling buffer gives the same outputs as the windowed mask; causal linear attention in parallel form equals its RNN form; and a selective \(\Delta\) keeps a key token that a fixed \(\Delta\) forgets. It runs on CPU in well under a second.
import torch, torch.nn.functional as F torch.manual_seed(0) T, d, W = 12, 8, 4 q, k, v = torch.randn(3, T, d).unbind(0) # 1) causal and sliding-window masks, formula (27.2) i = torch.arange(T)[:, None]; j = torch.arange(T)[None, :] causal = j <= i window = causal & (i - j < W) # keys j with i - W < j <= i def attend(mask): s = (q @ k.T) / d ** 0.5 return torch.softmax(s.masked_fill(~mask, float("-inf")), dim=-1) @ v full, swa = attend(causal), attend(window) print(int(causal.sum()), int(window.sum())) # 78 vs 42 scores print((full[:W] - swa[:W]).abs().max().item()) # 0.0: the first W rows are identical # 2) rolling-buffer decoding gives the same outputs as the windowed mask (Algorithm 1) Kbuf, Vbuf = torch.zeros(W, d), torch.zeros(W, d) out = [] for t in range(T): Kbuf[t % W], Vbuf[t % W] = k[t], v[t] # overwrite the oldest slot n = min(t + 1, W) s = Kbuf[:n] @ q[t] / d ** 0.5 # order inside the buffer does not matter out.append(torch.softmax(s, 0) @ Vbuf[:n]) print((torch.stack(out) - swa).abs().max().item()) # about 1e-7 # 3) causal linear attention: parallel form = recurrent form, (27.6)-(27.7), Algorithm 2 phi = lambda x: F.elu(x) + 1 A = (phi(q) @ phi(k).T) * causal # T x T, no softmax par = (A @ v) / A.sum(-1, keepdim=True) S, z, rec = torch.zeros(d, d), torch.zeros(d), [] for t in range(T): S = S + torch.outer(phi(k[t]), v[t]) # state: d x d, fixed size z = z + phi(k[t]) rec.append(phi(q[t]) @ S / (phi(q[t]) @ z)) print((torch.stack(rec) - par).abs().max().item()) # about 1e-7 # 4) a one-channel selective scan, formula (27.11): A = -1, B = C = 1 x = torch.tensor([0., 0., 0., 1., .2, -.1, .3, 0., -.2, .1, .2, 0.]) def scan(delta): h, hs = torch.tensor(0.), [] for t in range(len(x)): a = torch.exp(-delta[t]) # A_bar = exp(delta * A) h = a * h + (1 - a) * x[t] # B_bar = 1 - exp(-delta) hs.append(h) return torch.stack(hs) fixed = scan(torch.full((12,), 0.5)) select = scan(torch.where(x.abs() > 0.5, 3.0, 0.02)) # big step only on the key token print(round(fixed[-1].item(), 4), round(select[-1].item(), 4)) # 0.062 0.8188
Real implementations differ in important ways: sliding windows are done inside FlashAttention kernels (which skip the masked blocks instead of computing them), linear attention is trained in chunks, and Mamba’s scan is a fused GPU kernel. The math is the same as above.
Where this is used
| Setting | Design | Why |
|---|---|---|
| Mistral 7B (v0.1) | Sliding window \(W = 4{,}096\) in all 32 layers, rolling buffer cache | Fixed cache; 8× less cache memory at 32K tokens |
| Gemma 2, Gemma 3 | Local and global layers interleaved (1:1 with \(W = 4{,}096\); 5:1 with \(W = 1{,}024\)) | Most layers have a small cache; a few global layers keep long-range recall |
| Long-document encoders (Longformer, BigBird) | Window + global tokens (+ random links in BigBird) | Classify or answer questions over documents of thousands of tokens |
| Chat and agents that run for hours | Attention sinks + window (StreamingLLM) | Endless streaming with fixed memory; the far past is dropped |
| Mamba, RWKV, RetNet and hybrids such as Jamba | Recurrent layers with a fixed-size state, often with a few attention layers | Constant memory and time per token; high throughput for long outputs |
| Live video streams (surveillance, sports, key-moment detection) | Window over recent frame tokens + a few sink or summary tokens, or an SSM over frames [Likely] | Frames arrive forever; cost per frame must not grow with stream length |
| Long video classification and action recognition | Local attention inside short clips, global attention or SSM layers across clips [Likely] | An hour of video has hundreds of thousands of patch tokens; full attention over all of them is too expensive (session 206) |
| Vision Transformers (DINOv2 and others) | Extra register tokens | Give the model a sink so that background patches stay clean |
Common mistakes
- Saying a sliding-window model “cannot see beyond \(W\)”. Through stacked layers it can reach about \(L \cdot W\) tokens (27.3). The correct statement: it cannot attend directly beyond \(W\), and long indirect paths are weak.
- Running a full-attention model with a plain window cache. Evicting the first tokens destroys the attention sinks and the output collapses. Keep the first few tokens (StreamingLLM), or use a model trained with windows.
- Assigning original positions after eviction. StreamingLLM assigns positions inside the cache. Using the original text positions creates distances the model never saw in training.
- Thinking linear attention is an approximation of softmax. With \(\phi = \operatorname{elu} + 1\) it is a different model with different behavior (Figure 3). Only random-feature methods such as Performer try to approximate softmax.
- Forgetting the denominator \(\mathbf{z}\) in linear attention, or computing it without the causal mask. The output then grows with sequence length, or leaks future tokens.
- Calling Mamba “just an RNN like an LSTM”. Its recurrence is linear in the state, so it can be trained with a parallel scan, and its gates come from the input through \(\Delta_t, B_t, C_t\). An LSTM has a nonlinear recurrence and must be trained step by step.
- Comparing only FLOPs. For short sequences (\(T \lt d\) or a few thousand tokens), full attention with FlashAttention is often as fast as the “efficient” variant, and better. The gains of these variants are mainly in long contexts and in decode memory.
Interview questions
What is sliding-window attention, and what does it save?basic
A model uses \(W = 4{,}096\) in 32 layers. How far back can information travel?core
How does a rolling buffer cache work, and why is the order of slots not a problem?core
Why do Gemma 2 and Gemma 3 mix local and global layers instead of using only windows?core
Explain the kernel trick in linear attention. Why is the cost \(O(T)\)?core
What does linear attention lose compared with softmax attention?advanced
What is a state space model, and how is Mamba different from S4?core
How is Mamba different from an LSTM?advanced
What is an attention sink, and why does a plain sliding-window cache break a pretrained LLM?core
Does StreamingLLM give the model a 4-million-token memory?advanced
You must serve a model that writes very long outputs on small GPUs. Which of these designs would you consider, and what would you test?advanced
Exercises
- With \(T = 16\) and \(W = 4\), how many query–key pairs does the sliding-window mask keep? Check in Figure 1.
- Compute the BF16 KV cache of Mistral 7B at \(T = 8{,}192\), with and without the 4,096-token rolling buffer.
- A model has 24 layers and a window of 2,048. What is its theoretical reach (formula 27.3)?
- Show that \((\phi(Q)\phi(K)^\top)V = \phi(Q)(\phi(K)^\top V)\) has the costs in (27.8). For which \(T\) is the second order cheaper when \(d = 64\)?
- In the 1-D SSM (27.11) with a fixed \(\Delta\), the share of token 3 left after 12 more tokens is \((1 - a)\,a^{12}\) with \(a = e^{-\Delta}\). Find the best \(a\) and the best share.
- A sink has weight 0.6 in some head. The window cache evicts it. By what factor does every other weight change?
Answerscheck
Key takeaways
- Sliding-window attention (27.2) keeps only the last \(W\) keys: about \(T \cdot W\) scores, and a rolling KV cache of fixed size (27.4). Reach through \(L\) layers is about \(L \cdot W\) (27.3), but only indirectly.
- Local + global designs (Longformer, BigBird, Gemma 2 and 3) keep a few full-attention paths for recall and make most of the cache small.
- Linear attention replaces \(\exp\) with a feature-map dot product (27.5). Attention becomes an RNN with a \(d \times d\) state (27.7) and \(O(T)\) cost (27.8), but it loses sharpness and recall.
- SSMs are linear recurrences (27.10) that train in parallel and run with constant memory. Mamba makes \(\Delta, B, C\) depend on the input (27.12), so it can choose what to remember.
- Softmax must sum to 1 (27.13), so trained models park attention on the first tokens. Keep these attention sinks when you evict tokens (StreamingLLM).
Key formulas
References for this session
- Jiang et al. (2023). Mistral 7B
- Katharopoulos et al. (2020). Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention
- Gu & Dao (2023). Mamba: Linear-Time Sequence Modeling with Selective State Spaces
- Xiao et al. (2023). Efficient Streaming Language Models with Attention Sinks
- Vaswani et al. (2017). Attention Is All You Need
- Jiang et al. (2023). Mistral 7B
- Beltagy et al. (2020). Longformer: The Long-Document Transformer
- Zaheer et al. (2020). Big Bird: Transformers for Longer Sequences
- Child et al. (2019). Generating Long Sequences with Sparse Transformers
- Gemma Team (2024). Gemma 2: Improving Open Language Models at a Practical Size
- Gemma Team (2025). Gemma 3 Technical Report
- Katharopoulos et al. (2020). Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention
- Choromanski et al. (2020). Rethinking Attention with Performers
- Gu et al. (2021). Efficiently Modeling Long Sequences with Structured State Spaces
- Gu & Dao (2023). Mamba: Linear-Time Sequence Modeling with Selective State Spaces
- Dao & Gu (2024). Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality
- Sun et al. (2023). Retentive Network: A Successor to Transformer for Large Language Models
- Peng et al. (2023). RWKV: Reinventing RNNs for the Transformer Era
- Lieber et al. (2024). Jamba: A Hybrid Transformer-Mamba Language Model
- Xiao et al. (2023). Efficient Streaming Language Models with Attention Sinks
- Darcet, Oquab, Mairal, Bojanowski (2023). Vision Transformers Need Registers
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models