3. Attention
Draft
The bottleneck that attention removed
To predict the next token a model has to fetch things it read earlier: the noun a pronoun stands for, the bracket still open, a name introduced forty tokens ago. A transformer fetches them with one operation. The position that needs something emits a query; every earlier position has left a key and a value; the query is scored against the keys, the scores become weights, and what comes back is the weighted sum of the values.
sentence Lily found a red ball in the garden. She gave the ball to her mom. reader the second “ball”, token 14 of 18 (token 1 is the start token) head block 3, head 4 of gpt-pico token cosine with its query score = 12 × cosine weight = softmax(score) ball 0.84 10.1 0.82 ████████████████████ ball (itself) 0.64 7.7 0.07 ██ the 0.56 6.7 0.03 █ a 0.53 6.3 0.02 found 0.50 5.9 0.01 the other 9 0.04 █ to her mom . after the reader: masked 0 output the values of the tokens, each times its weight, added up: 0.82 × value(ball) + ... the head adds it to the stream at the reader's position (the live figure needs JavaScript; it loads about 2.3 MB, the weights of gpt-pico)
At the second "ball" in the example sentence, block 3, head 4 of gpt-pico scores each key by 12 times the cosine of its angle with the query (Section 3.4 gives the reason for that form). The first "ball" has cosine 0.84 and score 10.1, and after the softmax it holds 0.82 of the weight, about eleven times what the runner-up gets for a cosine 0.20 smaller. What the head writes at the reader is the values of those tokens averaged under these weights. No other part of a transformer moves information between positions, and what follows traces that one operation from the problem it was invented for to the variants of 2026.
The problem came from translation. In 2014 a neural translation system was a pair of recurrent networks: an encoder read the source sentence word by word into a state vector, and a decoder wrote the translation from the encoder's last state. Whatever the decoder needed to know about the source had to pass through that one vector, for a sentence of five words or of fifty. The paper that changed this gives the diagnosis and the remedy in one sentence of its abstract.
Neural machine translation is a recently proposed approach to machine translation. Unlike the traditional statistical machine translation, the neural machine translation aims at building a single neural network that can be jointly tuned to maximize the translation performance. The models proposed recently for neural machine translation often belong to a family of encoder–decoders and encode a source sentence into a fixed-length vector from which a decoder generates a translation. In this paper, we conjecture that the use of a fixed-length vector is a bottleneck in improving the performance of this basic encoder–decoder architecture, and propose to extend this by allowing a model to automatically (soft-)search for parts of a source sentence that are relevant to predicting a target word, without having to form these parts as a hard segment explicitly. With this new approach, we achieve a translation performance comparable to the existing state-of-the-art phrase-based system on the task of English-to-French translation. Furthermore, qualitative analysis reveals that the (soft-)alignments found by the model agree well with our intuition.
—D. Bahdanau, K. Cho and Y. Bengio, "Neural machine translation by jointly learning to align and translate" (2014).arXiv 1409.0473, abstract. On English to French the model scored 26.75 BLEU (a count of overlap with reference translations; higher is better) on all test sentences, against 17.82 for the same model reading through one vector (Table 1).
Their encoder keeps one vector per source word, an annotation, and before writing each word the decoder scores every annotation against its own state.
Definition 3.1.1 (additive attention). Let \(h_1, \dots, h_T\) be the annotations of the source words and \(s_{i-1}\) the state of the decoder before it writes word \(i\). With a learned vector \(v_a\) and learned matrices \(W_a\) and \(U_a\),
\[e_{ij} = v_a^{\top} \tanh\bigl(W_a s_{i-1} + U_a h_j\bigr), \qquad \alpha_{ij} = \frac{\exp(e_{ij})}{\sum_{l=1}^{T} \exp(e_{il})}, \qquad c_i = \sum_{j=1}^{T} \alpha_{ij}\, h_j . \tag{3.1}\]The context vector \(c_i\) is what the decoder reads when it writes word \(i\).
The paper calls this "a mechanism of attention in the decoder". Two of its properties outlived the system. The weights are a probability distribution and $$c_i$$ is an expectation under it, not a sample, so the read is differentiable and trains with everything else. And the read is addressed by content, by what the state \(s_{i-1}\) asks for and not by where things are stored.
The next three years simplified the score to a dot product or a bilinear form \(h_t^{\top} W_a \bar h_s\), the form every transformer uses, and widened the use: memory networks looked up stored facts with the same read, and pointer networks used the weights themselves as the output.M.-T. Luong, H. Pham and C. D. Manning, "Effective approaches to attention-based neural machine translation", 2015 (arXiv 1508.04025); J. Weston, S. Chopra and A. Bordes, "Memory networks" (arXiv 1410.3916); O. Vinyals, M. Fortunato and N. Jaitly, "Pointer networks" (arXiv 1506.03134). By 2017 the operation had a description that no longer mentions translation.
An attention function can be described as mapping a query and a set of key-value pairs to an output, where the query, keys, values, and output are all vectors. The output is computed as a weighted sum of the values, where the weight assigned to each value is computed by a compatibility function of the query with the corresponding key.
—A. Vaswani and seven co-authors, "Attention is all you need" (2017).A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser and I. Polosukhin, NeurIPS 2017 (arXiv 1706.03762), Section 3.2.
That paper removed the recurrent networks. If a decoder can look up what it needs in the encoder's annotations, a layer can look up what it needs in its own input: self-attention, in which queries, keys and values all come from the same sequence. Any position reaches any other in one step, and all positions are computed at once, so training runs in parallel over the length of the sequence. The price is a number of scores quadratic in that length, in every layer. The GPT models of Section 1 keep half of the 2017 design, the decoder, whose self-attention reads only backward.
The mechanism
The 2017 paper states its operation in a few sentences and one equation.
3.2.1 Scaled Dot-Product Attention
We call our particular attention "Scaled Dot-Product Attention" (Figure 2). The input consists of queries and keys of dimension \(d_{k}\), and values of dimension \(d_{v}\). We compute the dot products of the query with all keys, divide each by \(\sqrt{d_{k}}\), and apply a softmax function to obtain the weights on the values.
In practice, we compute the attention function on a set of queries simultaneously, packed together into a matrix \(Q\). The keys and values are also packed together into matrices \(K\) and \(V\). We compute the matrix of outputs as:
\[\mathrm{Attention}(Q,K,V)=\mathrm{softmax}(\frac{QK^{T}}{\sqrt{d_{k}}})V \qquad (1)\]
A language model needs the version that reads only backward, and it is clearest for one head. Throughout, \(x_1, \dots, x_n \in \mathbb R^d\) are the vectors that the \(n\) tokens of the context present to a layer (the normalized residual stream of Section 5), \(d_k\) is the width of a head, and logarithms are natural.
Definition 3.2.1 (a causal attention head). A head has four matrices, \(W_Q, W_K, W_V \in \mathbb R^{d_k \times d}\) and \(W_O \in \mathbb R^{d \times d_k}\). Position \(i\) emits a query \(q_i = W_Q x_i\), a key \(k_i = W_K x_i\) and a value \(v_i = W_V x_i\). The scores, the pattern and the output of the head are
\[s_{ij} = \frac{q_i^{\top} k_j}{\sqrt{d_k}}, \qquad A_{ij} = \frac{\exp(s_{ij})\, \mathbb 1[j \le i]}{\sum_{l \le i} \exp(s_{il})}, \qquad o_i = W_O \sum_{j \le i} A_{ij}\, v_j . \tag{3.2}\]The indicator is the causal mask: position \(i\) reads positions \(1, \dots, i\) and nothing after them.
The paper implements the mask by setting the scores of the forbidden pairs to \(-\infty\), which gives them weight zero. The mask lets one pass over \(n\) tokens train \(n\) predictions at once: the output at position \(i\) is computed from the first \(i\) tokens only, as it will be when the model writes and token \(i + 1\) does not exist yet.
Proposition 3.2.2 (what follows from the definition). (i) Each row of \(A\) is a probability vector supported on \(j \le i\), with \(A_{11} = 1\); hence \(o_i\) lies in the convex hull of the vectors \(W_O W_V x_j\), \(j \le i\). (ii) The pattern depends on \(W_Q\) and \(W_K\) only through the \(d \times d\) matrix \(W_Q^{\top} W_K\), of rank at most \(d_k\), and the output depends on \(W_V\) and \(W_O\) only through \(W_O W_V\): indeed \(s_{ij} = x_i^{\top} W_Q^{\top} W_K\, x_j / \sqrt{d_k}\). (iii) Adding to the scores of row \(i\) a number \(c_i\) that does not depend on \(j\) leaves \(A\) unchanged.
Proof. (i) and (ii) are read off (3.2). (iii) The factor \(e^{c_i}\) multiplies the numerator and every term of the denominator. ∎
By (i) a head can only average what earlier positions offer: three identical values average to the same vector as one. Item (ii) splits a head into two questions, where to look and what to move, the QK and OV circuits that Section 9 reads from trained weights. Item (iii) is why a softmax can be computed in pieces (Section 3.6).
Multi-head attention allows the model to jointly attend to information from different representation subspaces at different positions. With a single attention head, averaging inhibits this.
—Vaswani et al. (2017).Section 3.2.2.
Definition 3.2.3 (multi-head attention). A layer of width \(d\) with \(h\) heads gives each head the width \(d_k = d/h\) and its own four matrices, and adds their outputs: \(\mathrm{attn}(x)_i = \sum_{a=1}^{h} o_i^{(a)}\).
The widths are chosen so that \(h\) heads cost what one head of full width would. In the paper's ablation at constant cost, one head of width 512 scored 24.9 on the translation metric BLEU, eight heads of width 64 scored 25.8, and 32 heads of width 16 fell back to 25.4. That fall has a reason in item (ii) of the proposition: the scores of a head form a matrix of rank at most \(d_k\) however long the context, and a narrow head cannot produce every pattern.Vaswani et al., Table 3, rows (A). S. Bhojanapalli, C. Yun, A. S. Rawat, S. J. Reddi and S. Kumar, "Low-rank bottleneck in multi-head attention models", 2020 (arXiv 2002.07028), Theorem 1: a head at least as wide as the context can produce any pattern with positive entries, a narrower one cannot.
In the code. Definition 3.2.1 for all the heads of a layer at once, with the scores and the pattern written out as tensors; the lines that record each quantity, the cache of Section 3.7 and dropout, which the recipe does not use, are part of it. It is project and forward_explicit of CausalSelfAttention in gpt-pp's model.py.
def project(self, x: Tensor) -> tuple[Tensor, Tensor, Tensor]:
"""Queries (B, H, T, dh), keys and values (B, Hkv, T, dh): three linear maps of the residual stream."""
B, T, _ = x.shape
q = self.q(x).view(B, T, self.n_head, self.d_head).transpose(1, 2)
k = self.k(x).view(B, T, self.n_kv_head, self.d_head).transpose(1, 2)
v = self.v(x).view(B, T, self.n_kv_head, self.d_head).transpose(1, 2)
return q, k, v
...
def forward_explicit(self, x: Tensor, rot: Rotation, bias: Tensor, hook: Hooks, layer: int,
kv: Optional[KVCache] = None) -> Tensor:
"""The same attention written out, each step handed to `hook`.
`bias` (T, T_keys) or (H, T, T_keys) is added to the scores: -inf on the keys a query may not see, plus
the ALiBi term if any. With a KV cache, x holds only the new tokens and the keys and values of the
earlier ones come from the cache.
"""
B, T, _ = x.shape
q, k, v = self.project(x)
q = hook(f"attn.{layer}.q", q)
k = hook(f"attn.{layer}.k", k)
v = hook(f"attn.{layer}.v", v)
q, k = self.position(q, k, rot)
if kv is not None:
k, v = kv.extend(layer, k, v)
k, v = self.share(k, v)
scores = q @ k.transpose(-2, -1) / math.sqrt(self.d_head) + bias # (B, H, T, T_keys)
scores = hook(f"attn.{layer}.scores", scores)
pattern = hook(f"attn.{layer}.pattern", scores.softmax(dim=-1)) # each row sums to one
z = pattern if self.dropout == 0 else F.dropout(pattern, self.dropout, self.training)
z = hook(f"attn.{layer}.z", z @ v) # (B, H, T, dh): each head's weighted average of values
if hook.wants(f"attn.{layer}.result"):
# What each head writes into the residual stream, (B, H, T, d): the output matrix applied to z one
# head at a time. Their sum over heads (plus the bias) is attn_out. Recorded, not replaceable.
w_o = self.o.weight.view(-1, self.n_head, self.d_head)
hook(f"attn.{layer}.result", torch.einsum("bhtk,dhk->bhtd", z, w_o.to(z.dtype)))
return self.o(z.transpose(1, 2).reshape(B, T, -1))
project applies \(W_Q\), \(W_K\) and \(W_V\) of all the heads as three products and cuts each result into slices of width d_head, one a head: q has the shape (B, H, T, dh) of its docstring, for sequences, heads, tokens and the head's width \(d_k\). In forward_explicit, scores is the \(s_{ij}\) of (3.2) with the mask already added, bias holding \(-\infty\) where \(j > i\); pattern is \(A\); z is each head's average \(\sum_j A_{ij} v_j\); and self.o, applied to the heads' averages set side by side, is \(W_O\) and the sum over heads of Definition 3.2.3 in one product. The formula has none of the rest. position normalizes queries and keys (Section 3.4) and turns them by their positions (Section 4); kv and share are the cache and the shared heads of Section 3.7; dropout, in a variant that sets it, strikes entries of the pattern and not of the output; and result, what one head alone writes to the stream, is computed only when it is asked for.
Quirk. gpt-pp computes attention on two paths. This one, the explicit path, is the path of the analyses, which read and replace its tensors through hook (Section 9), and of every token the model writes: the function generate and the chat replies of Section 7 decode with the cache of Section 3.7, which exists on this path only. Training runs the other, forward, one call of a fused kernel in which no score exists as a tensor (Section 3.6). The test test_fast_path_equals_explicit_path holds the logits of the two within \(10^{-5}\) of each other, with the weights in 64-bit floats, over 31 variants of the model; in the 16-bit floats of training they agree less closely (Section 3.6).
Quirk. The names given to hook are what an analysis can read or replace, and two of them need care. attn.{layer}.q and attn.{layer}.k are recorded before position, so they are the plain projections: \(q^{\top} k/\sqrt{d_k}\) computed from recorded queries and keys is not the model's score once queries and keys are normalized or turned. And scores are recorded with the \(-\infty\) of the mask in them; Section 9 reads the model through these names.
Example 3.2.4 (the shapes). The setup: gpt-pp has 12 layers of width 768 with 12 heads of width 64 and a context of 1,024 tokens. Across its heads each of the four matrices of a layer is \(d \times d\), so attention holds 28,311,552 of the model's 135,266,304 parameters (in gpt-pico, 393,216 of 2,228,224). On a full context one layer computes \(12 \times 1{,}024^2 = 12{,}582{,}912\) scores per sequence to move 1,024 vectors of 768 numbers: 16 scores for every number moved. ◁
The habits of gpt-pico's 24 heads can be scored over 512 held-out stories and checked against their patterns on individual passages.The LLM internals specimen sheet draws the same grid for a model of 40 layers with 40 heads each.
passage Once upon a time there was a little boy. He liked to explore and ... (64 tokens) the weight on the token just before the reader, for each of the 24 heads of gpt-pico (mean over 512 held-out stories; an even spread of the weight would give 0.03) head 1 head 2 head 3 head 4 block 1 0.29 P 0.15 0.17 0.18 block 2 0.12 0.19 0.38 P 0.18 block 3 0.21 0.17 0.29 P 0.09 D block 4 0.15 0.24 0.28 P 0.07 block 5 0.13 0.10 0.18 0.08 block 6 0.20 0.22 0.05 0.03 P previous-token head · D duplicate-token head: a habit of at least 8 times an even spread selected block 3, head 4, a duplicate-token head previous 0.09 · start 0.04 · itself 0.17 · duplicate 0.22 · induction 0.02 reads 16.6 tokens back · entropy 3.55 bits in the passage, the token “ail” reads the token “ail” 16 back with weight 0.72 (the live figure needs JavaScript; it loads about 2.3 MB, the weights of gpt-pico)
Four heads make a habit of reading the token just before the reader, one in each of blocks 1 to 4 (0.28 to 0.38, where an even spread gives 0.03). One head reads earlier copies of the reading token, with 0.22 of its weight on repeated random tokens, nine times an even spread: it is the head of the opening figure. The other 19 have no habit by the scoring rule, which asks for eight times an even spread.
Two habits of larger models are absent. No head rests on the start token, which gets 0.15 of a head's weight at most, and none is an induction head, the kind that finds an earlier copy of the current token and reads what followed it (Section 9): the largest score on that test is 0.06, against 0.024 for an even spread. One head comes close on the text gpt-pico was trained for: in the story of the figure, block 6, head 4 reads from the "r" of a second "rail" the "ail" that followed the first, with weight 0.82 (one passage, not a score). Section 8 asks why gpt-pico does not copy, where a model of its width trained on web text has begun to.
Three readings of one formula
Strip (3.2) to one query \(q\) against stored pairs \((k_j, v_j)\), with \(\beta\) for the factor in front of the dot product, \(1/\sqrt{d_k}\) in the 2017 paper:
\[\mathrm{read}(q) \;=\; \sum_{j} \frac{\exp(\beta\, q^{\top} k_j)}{\sum_{l} \exp(\beta\, q^{\top} k_l)}\; v_j . \tag{3.3}\]The formula has been read three times, as statistics, as a memory and as a network, and the third reading organizes the efficient variants of 2019 to 2026.
A kernel smoother. Given pairs \((k_j, v_j)\) and a similarity \(s(k, q) \ge 0\), the classical nonparametric estimate of the value at a new point \(q\) is the weighted average \(\sum_j s(k_j, q)\, v_j / \sum_l s(k_l, q)\), the Nadaraya-Watson estimator: regression by a local constant.
Proposition 3.3.1 (attention is a Gaussian kernel smoother). With the Gaussian kernel \(s_\beta(k, q) = \exp(-\tfrac{\beta}{2} \lVert k - q \rVert^2)\), the Nadaraya-Watson estimate at \(q\) is
\[\sum_j \frac{\exp\bigl(\beta\, q^{\top} k_j - \tfrac{\beta}{2} \lVert k_j \rVert^2\bigr)}{\sum_l \exp\bigl(\beta\, q^{\top} k_l - \tfrac{\beta}{2} \lVert k_l \rVert^2\bigr)}\; v_j .\]If all keys have the same norm this is (3.3) exactly. If they do not, (3.3) is the smoother in which key \(j\) carries the prior weight \(\exp(\tfrac{\beta}{2} \lVert k_j \rVert^2)\), whatever the query.
Proof. \(-\tfrac{\beta}{2}\lVert k - q\rVert^2 = \beta\, q^{\top} k - \tfrac{\beta}{2}\lVert k \rVert^2 - \tfrac{\beta}{2}\lVert q \rVert^2\), and the last term does not depend on \(j\), so it cancels by Proposition 3.2.2 (iii). ∎
The bandwidth of the kernel is \(\beta^{-1/2}\): as \(\beta \to 0\) the read is the plain mean of the values, and as \(\beta \to \infty\) it is the value of the nearest key. For twelve keys on a line, take scores \(-\beta (q - k)^2\), the kernel of the proposition with \(2\beta\) for \(\beta\); a query at 4.7 gives 0.43, 0.32 and 0.14 of its weight to its three nearest keys and returns 1.51, the weighted mean of all twelve values. A head is the same estimator in \(d_k\) dimensions, with keys and queries that the model has learned to place.Y.-H. H. Tsai, S. Bai, M. Yamada, L.-P. Morency and R. Salakhutdinov, "Transformer dissection: a unified understanding of Transformer's attention via the lens of kernel", EMNLP 2019 (arXiv 1908.11775); K. A. Wang, J. Shi and E. B. Fox, "Test-time regression: a unifying framework for designing sequence models with associative memory", 2025 (arXiv 2501.12352), Equations 50 and 51.
def head(q, K, V, beta):
scores = -beta * (q - K) ** 2
weights = softmax(scores)
return weights @ V
twelve keys on a line, each with a value; the query q = 4.70; beta = 1
key 4.4 5.3 3.6 the other 9
weight 0.43 0.32 0.14 0.11 in all
value 1.9 0.8 2.1
output 1.51, the weighted mean of the values
beta 0.01 0.1 1 10 100
output 2.14 1.87 1.51 1.83 1.90 at q = 4.70
hears 12.0 10.2 3.7 1.3 1.0 of 12 keys
beta → 0: the mean of all values, 2.18. beta → ∞: the value of the nearest key, 1.90.
(the live figure needs JavaScript; it computes everything in the page and loads no data)
The second half of the proposition is a warning: a key with a large norm is read by every query, relevant or not (Sections 3.4 and 3.8).
An associative memory. A Hopfield network stores patterns as the minima of an energy and retrieves one by descending from a partial cue. In 2020 Ramsauer and co-authors wrote down the energy whose descent step is (3.3) with the keys as their own values.
Proposition 3.3.2 (attention is a descent step on an energy). Let \(k_1, \dots, k_N \in \mathbb R^{d}\) be stored patterns, \(\beta > 0\), and
\[E(\xi) = \tfrac12 \lVert \xi \rVert^2 - \frac{1}{\beta} \log \sum_{j=1}^{N} \exp\bigl(\beta\, \xi^{\top} k_j\bigr), \qquad \xi^{+} = \sum_{j} \frac{\exp(\beta\, \xi^{\top} k_j)}{\sum_l \exp(\beta\, \xi^{\top} k_l)}\; k_j .\]Then \(\nabla E(\xi) = \xi - \xi^{+}\) and \(E(\xi^{+}) \le E(\xi) - \tfrac12 \lVert \xi^{+} - \xi \rVert^2\).
Proof. Let \(g(\xi) = \tfrac12 \lVert \xi \rVert^2 - E(\xi)\). It is a log-sum-exp of linear functions, hence convex, and \(\nabla g(\xi) = \xi^{+}\), which gives the gradient. By convexity \(g(\zeta) \ge g(\xi) + (\zeta - \xi)^{\top} \xi^{+}\) for every \(\zeta\), so \(E(\zeta) \le \tfrac12 \lVert \zeta \rVert^2 - g(\xi) - (\zeta - \xi)^{\top} \xi^{+}\). At \(\zeta = \xi^{+}\) the right side is \(-\tfrac12\lVert \xi^{+} \rVert^2 - g(\xi) + \xi^{\top}\xi^{+}\), which equals \(E(\xi) - \tfrac12 \lVert \xi^{+} - \xi \rVert^2\). ∎
Iterating the read can only lower the energy, and it stops where \(\xi = \xi^{+}\); one head performs one step, started at the query. The paper that drew the correspondence states it in one sentence of its abstract, after the capacity of such a memory and the kinds of point where the iteration stops.
We introduce a modern Hopfield network with continuous states and a corresponding update rule. The new Hopfield network can store exponentially (with the dimension of the associative space) many patterns, retrieves the pattern with one update, and has exponentially small retrieval errors. It has three types of energy minima (fixed points of the update): (1) global fixed point averaging over all patterns, (2) metastable states averaging over a subset of patterns, and (3) fixed points which store a single pattern. The new update rule is equivalent to the attention mechanism used in transformers. This equivalence enables a characterization of the heads of transformer models. These heads perform in the first layers preferably global averaging and in higher layers partial averaging via metastable states. The new modern Hopfield network can be integrated into deep learning architectures as layers to allow the storage of and access to raw input data, intermediate results, or learned prototypes. These Hopfield layers enable new ways of deep learning, beyond fully-connected, convolutional, or recurrent networks, and provide pooling, memory, association, and attention mechanisms. We demonstrate the broad applicability of the Hopfield layers across various domains. Hopfield layers improved state-of-the-art on three out of four considered multiple instance learning problems as well as on immune repertoire classification with several hundreds of thousands of instances. On the UCI benchmark collections of small classification tasks, where deep learning methods typically struggle, Hopfield layers yielded a new state-of-the-art when compared to different machine learning methods. Finally, Hopfield layers achieved state-of-the-art on two drug design datasets. The implementation is available at: https://github.com/ml-jku/hopfield-layers
—H. Ramsauer and co-authors, "Hopfield networks is all you need" (2020).arXiv 2008.02217, abstract. The energy and the update are their Equations 1 to 3, the energy without its additive constants; the capacity is their Theorem 3.
Which of the three kinds of point is reached depends on \(\beta\).
Fast weights. A network has activities, which change with every input, and weights, which change only in training. Weights written during the forward pass, by the input itself, are called fast weights. In 2016 Ba, Hinton and co-authors gave a recurrent network a fast matrix made of outer products of its own past states, and saw what it was.
A fast associative memory has several advantages when compared with the type of memory assumed by a Neural Turing Machine (NTM) [Graves et al., 2014], Neural Stack [Grefenstette et al., 2015], or Memory Network [Weston et al., 2014]. First, it is not at all clear how a real brain would implement the more exotic structures in these models e.g., the tape of the NTM, whereas it is clear that the brain could implement a fast associative memory in synapses with the appropriate dynamics. Second, in a fast associative memory there is no need to decide where or when to write to memory and where or when to read from memory. The fast memory is updated all the time and the writes are all superimposed on the same fast changing component of the strength of each synapse. Every time the input changes there is a transition to a new hidden state which is determined by a combination of three sources of information: The new input via the slow input-to-hidden weights, \(C\), the previous hidden state via the slow transition weights, \(W\), and the recent history of hidden state vectors via the fast weights, \(A\). The effect of the first two sources of information on the new hidden state can be computed once and then maintained as a sustained boundary condition for a brief iterative settling process which allows the fast weights to influence the new hidden state. Assuming that the fast weights decay exponentially, we now show that the effect of the fast weights on the hidden vector during an iterative settling phase is to provide an additional input that is proportional to the sum over all recent hidden activity vectors of the scalar product of that recent hidden vector with the current hidden activity vector, with each term in this sum being weighted by the decay rate raised to the power of how long ago that hidden vector occurred. So fast weights act like a kind of attention to the recent past but with the strength of the attention being determined by the scalar product between the current hidden vector and the earlier hidden vector rather than being determined by a separate parameterized computation of the type used in neural machine translation models [Bahdanau et al., 2015].
—J. Ba, G. Hinton, V. Mnih, J. Z. Leibo and C. Ionescu, "Using fast weights to attend to the recent past" (2016).arXiv 1610.06258, Section 3. Fast weights appear in a paper of Hinton and Plaut of 1987 that Ba et al. cite, and a network trained by gradient descent to write the weights of another in a technical report of J. Schmidhuber (FKI-147-91, Technische Universität München, March 1991).
Remove the softmax from (3.3) and this is what attention is: the read becomes \(\sum_j v_j\, (k_j^{\top} q) = W q\) with \(W = \sum_j v_j k_j^{\top}\), a matrix written by one outer product per token. Schlag, Irie and Schmidhuber identified this linear attention with the fast weight programmers of the early 1990s, in which a slow network learns to write the weights of a fast one. The matrix has a fixed size however long the context, and that is its limit.
Proposition 3.3.3 (a linear memory holds at most \(d_k\) pairs). Let \(W = \sum_{j=1}^{N} v_j k_j^{\top}\) with keys in \(\mathbb R^{d_k}\). Reading with the key \(k_i\) returns \(W k_i = \sum_j (k_j^{\top} k_i)\, v_j\). This equals \(v_i\) for every \(i\) and every choice of the values if and only if the keys are orthonormal, which requires \(N \le d_k\).
Proof. Orthonormal keys reduce the sum to \(v_i\). Conversely, if the sum equals \(v_i\) for all choices of the values, then \(k_j^{\top} k_i\) is one for \(j = i\) and zero otherwise, and at most \(d_k\) vectors of \(\mathbb R^{d_k}\) are orthonormal. ∎
Sec. 4.1 argues that the linear Transformers can end up in an overcapacity regime, if the sequence length \(L\) exceeds the dimension \(d_{\text{dot}}\) of the keys. Once in overcapacity, an ideal memory model should dynamically interact with the memory contents and selectively determine which associations to remember or to forget. This is in stark contrast to the standard Transformer which stores immutable pairs of key and value vectors by concatenation, thus increasing the storage size. While such models work well in practice, we consider a model’s capability to update previously acquired knowledge to be critical for many problems. Hence, from the perspective of dynamic interaction with the memory, the purely additive update rule of Eqs. 17 may be sub-optimal. This motivates us to improve the elementary differentiable programming instruction (i.e. the update rule) of FWPs.
—I. Schlag, K. Irie and J. Schmidhuber, "Linear Transformers are secretly fast weight programmers" (2021).ICML 2021 (arXiv 2102.11174), Section 4.2. The identity \(\exp(q^{\top} k) = \mathbb E_{\omega \sim \mathcal N(0, I)}[\phi_\omega(q)\, \phi_\omega(k)]\) with \(\phi_\omega(x) = \exp(\omega^{\top} x - \tfrac12 \lVert x \rVert^2)\) makes softmax attention a linear memory with infinitely many features (K. Choromanski and co-authors, "Rethinking attention with Performers", ICLR 2021, arXiv 2009.14794, Lemma 1).
Softmax attention escapes the limit by not compressing: it keeps every pair. Seen as a network, (3.3) is a perceptron with one hidden layer: one unit per stored pair, with input weights \(\beta k_j\), the exponential as its activation and output weights \(v_j\), followed by a division by the sum of the activations. Its weights are fast weights and its width is the length of the context. The other half of a transformer block, its multilayer perceptron or MLP, is the same device with slow weights, keys and values written by training (Section 5.4). Attention never runs out of capacity because its hidden layer grows with the context, and its cost per query grows with the context for the same reason.
Mixture-of-top-k attention
The paper that turns this view into a program for efficient attention is "Mixture-of-top-k attention: efficient attention via scalable fast weights", by Wen, Huang, Meng, He and Li.Q. Wen, Z. Huang, X. Meng, W. He and C.-G. Li, NeurIPS 2026 (arXiv 2602.01219), read here in version 6, of 27 September 2026. Version 1, of 1 February 2026, had another title and other numbers, and the conference version may differ again. Its abstract states the proposal.
The vanilla self-attention mechanism in Transformers can be viewed as a two-layer fast-weight MLP, whose weights are dynamically induced by inputs and whose hidden dimension is equal to the sequence length \(N\). As the context extends, the expressive capacity of such an \(N\)-width MLP increases, but it becomes unscalable for extremely long sequences. Recently, this fast-weight perspective has motivated the Mixture-of-Experts (MoE) attention mechanism, which partitions the sequence into rigid blocks, treats them as fast-weight experts, and sparsely routes the tokens to them. In this paper, we elevate this perspective to a unifying framework for efficient attention mechanisms, interpreting them as making fast weights scalable through either routing or compression, and organizing them into a five-dimensional taxonomy. Then, we propose Mixture-of-Top-\(k\) Attention (MiTA), which employs a small set of landmark queries to gather top-\(k\) attended key-value pairs as query-aware and deformable routed experts, while compressing the \(N\)-width MLP into a narrower shared expert. Consequently, our MiTA improves the flexibility of prior MoE attention from rigid to deformable fast-weight experts, as well as the scalability of prior top-\(k\) attention from query-specific set to reusable top-\(k\) set. We conduct extensive experiments on vision tasks showing the superior effectiveness and efficiency of our MiTA, and also uncovering intriguing properties such as an emergent token-pruning effect and easy generalization from standard attention. Code is available at https://github.com/QishuaiWen/MiTA.
The proposal has two parts. The classification: if full attention is a perceptron of width \(N\), an efficient attention has to make it smaller, and there are two ways. Compression replaces the \(N\) hidden units by fewer that summarize them: the single matrix of linear attention, a projection of keys and values to a fixed length, a few landmark tokens. Routing keeps the units and sends each query to a few of them: a window, a block chosen by a cheap score, the top \(k\) keys of that query. The paper sorts the methods of Sections 3.6 and 3.8 on five axes and names the weakness of each pure strategy.
On the other hand, unlike the methods mentioned above that scale fast weights by accessing a subset of them, linear attention [12] and Test-Time Training (TTT) [17] compress the \(N\)-width MLP into one (or several [13]) light-weight module(s), analogous to model compression [26] and knowledge distillation [27]. Therefore, from a fast-weight scaling perspective, we divide the scaling approaches of existing efficient attention methods discussed in this paper into two general categories: a) scaling by routing, and b) scaling by compression (see Fig. 1 for an illustration). Scaling by compression alone sacrifices a precise access to the original key-value pairs; whereas scaling by routing alone lacks a global summary of the full context. Although these two approaches are not mutually exclusive, most existing methods typically adopt only one of them.
—Wen et al. (2026).Section 1, version 6.
The mechanism does both with one device, a small set of landmark queries.
Definition 3.3.4 (mixture-of-top-\(k\) attention). Let \(q_1, \dots, q_N\), \(k_1, \dots, k_N\) and \(v_1, \dots, v_N\) in \(\mathbb R^d\) be the queries, keys and values of a sequence, and fix integers \(m\) and \(k\) much smaller than \(N\) and \(s \ge 1\).
- Landmarks: \(\tilde q_1, \dots, \tilde q_m\) are the averages of the queries over \(m\) equal windows of the sequence.
- Routed experts: for each landmark \(a\), the set \(\mathcal I_a\) holds the \(k\) indices \(j\) with the largest \(k_j^{\top} \tilde q_a\), and expert \(a\) is the set of pairs \((k_j, v_j)\) with \(j \in \mathcal I_a\).
- Shared expert: each landmark reads the whole sequence by full attention, \(\tilde v_a = \mathrm{read}(\tilde q_a)\) as in (3.3) with \(\beta = 1/\sqrt d\), and the shared expert is the set of the \(m\) pairs \((\tilde q_a, \tilde v_a)\), in which landmark queries serve as keys.
- Routing: a query \(q\) is sent to the \(s\) landmarks with the largest \(q^{\top} \tilde q_a\).
- Read: the output for \(q\) is (3.3) over the \(m + ks\) pairs of the shared expert and of the \(s\) experts that \(q\) was sent to.
Every query reads \(m + ks\) pairs in place of \(N\), so the final attention costs \(O(N(m + ks))\) against \(O(N^2)\), after two \(N \times m\) matrices of scores. Every experiment in the paper uses \(s = 1\). Block attention (Section 3.8) also routes each query to a few experts, but to contiguous blocks fixed in advance; top-\(k\) attention gives every query a private set of keys, \(N\) sets in all, where here \(m\) sets are each reused by all the queries routed to them.
The evidence is on images and on a benchmark of long sequences, and nowhere else. Trained from scratch on ImageNet-1K, a small vision transformer of 5.7M parameters reaches 72.2% top-1 accuracy with full attention and 71.1% with mixture-of-top-\(k\) at \(m = k = 25\), each query reading 50 pairs out of the 196 patches of an image; the next size up loses 0.1 points, 79.8 against 79.9. On Long Range Arena, with \(m = k = 128\) on sequences of 1,000 to 4,000 elements, the average accuracy is 58.91 against 58.19 for full attention, and training takes 2.4 hours against 10.6 on one consumer GPU.Wen et al., version 6: Table 2 (ImageNet-1K with the training recipe of DeiT; attention through landmark tokens alone is at 70.3 there, or 71.1 with an added bias term, and linear attention at 68.0), Table 5 (Long Range Arena, against PyTorch's fused attention, hyperparameters not tuned) and Table 6 (removing either half costs accuracy on the small model: 71.1 with both, 70.8 with routing alone, 70.3 with compression alone). The 196 patches, a 224-pixel image in 16-pixel patches, are our arithmetic. The paper is exact about what this does not cover.
This work primarily focuses on the vision domain, and we do not evaluate the proposed method in the decoding phase of LLMs. This choice is mainly due to our limited computational resources. That said, the method and related work are presented in a modality-agnostic manner, and we discuss their applicability beyond vision. We consider the application to LLMs as an important direction for future work. The main contribution of this paper is conceptual, namely a unified perspective that facilitates principled improvements, rather than a domain-specific instantiation.
—Wen et al. (2026), "Limitations".Appendix D, version 6; the whole section.
For a language model three things are therefore open. The definition is not causal: a landmark averages queries from a window that can extend past the reading position, and an expert can hold keys that lie after a query routed to it, so a decoder needs a variant that the paper does not specify. The speed was measured against a general fused kernel at lengths of a few thousand, not at the lengths where language models use sparse attention. And loss on text against keys read, the test that matters for a GPT, is in no paper we found; Section 3.8 lays the selection over a real attention pattern of gpt-pico.
Why the scores are scaled
The 2017 paper compares its dot product with the additive score of Definition 3.1.1 and gives its reason for the factor \(1/\sqrt{d_k}\).
3.2.1 Scaled Dot-Product Attention
The two most commonly used attention functions are additive attention [2], and dot-product (multiplicative) attention. Dot-product attention is identical to our algorithm, except for the scaling factor of \(\frac{1}{\sqrt{d_{k}}}\). Additive attention computes the compatibility function using a feed-forward network with a single hidden layer. While the two are similar in theoretical complexity, dot-product attention is much faster and more space-efficient in practice, since it can be implemented using highly optimized matrix multiplication code.
While for small values of \(d_{k}\) the two mechanisms perform similarly, additive attention outperforms dot product attention without scaling for larger values of \(d_{k}\) [3]. We suspect that for large values of \(d_{k}\), the dot products grow large in magnitude, pushing the softmax function into regions where it has extremely small gradients. To counteract this effect, we scale the dot products by \(\frac{1}{\sqrt{d_{k}}}\).
Proposition 3.4.1 (the size of a dot product). Let \(q, k \in \mathbb R^{d_k}\). (i) If their \(2 d_k\) coordinates are independent with mean 0 and variance 1, then \(\mathbb E[q^{\top} k] = 0\) and \(\operatorname{Var}(q^{\top} k) = d_k\). (ii) The same holds if \(q\) and \(k\) are independent and uniform on the sphere of radius \(\sqrt{d_k}\).
Proof. (i) \(\mathbb E[(\sum_i q_i k_i)^2] = \sum_i \mathbb E[q_i^2]\, \mathbb E[k_i^2] = d_k\), the cross terms having mean zero. (ii) \(q^{\top} k = d_k \cos\theta\) for the angle \(\theta\) between them, and the cosine of two independent uniform directions has mean 0 and variance \(1/d_k\) (Section 2.4). ∎
So an unscaled score has standard deviation \(\sqrt{d_k}\), eight at the paper's head width of 64, and a scaled one has standard deviation one. What a large standard deviation does to a softmax can be said exactly.
Proposition 3.4.2 (a softmax against its scale). For scores \(z \in \mathbb R^n\) and \(\beta \ge 0\) let \(p = \mathrm{softmax}(\beta z)\) and \(H(\beta) = -\sum_j p_j \log p_j\). (i) \(\partial p / \partial z = \beta\, (\operatorname{diag}(p) - p p^{\top})\), and every entry of this matrix is at most \(\beta\, (1 - \max_j p_j)\) in absolute value. (ii) \(dH/d\beta = -\beta \operatorname{Var}_{p}(z) \le 0\): the entropy falls from \(\log n\) at \(\beta = 0\) to the logarithm of the number of largest scores as \(\beta \to \infty\).
Proof. (i) Differentiate \(p_j = e^{\beta z_j}/Z\) with \(Z = \sum_l e^{\beta z_l}\). A diagonal entry is \(\beta p_j (1 - p_j)\) and an off-diagonal one is \(-\beta p_j p_l\); in each, one factor is at most \(1 - \max_j p_j\) and the other at most one. (ii) \(H = \log Z - \beta\, \mathbb E_p[z]\), with \(\tfrac{d}{d\beta} \log Z = \mathbb E_p[z]\) and \(\tfrac{d}{d\beta}\mathbb E_p[z] = \operatorname{Var}_p(z)\). ∎
Item (i) is the precise form of the paper's suspicion: a row that has put nearly all its weight on one key passes almost no gradient to its scores. Item (ii) makes the scale a dial with one direction, read by \(e^{H}\), the effective number of keys of a row: \(n\) for a uniform row, one for a row that points. Whether a row of random scores averages or points depends on how their spread compares with the largest of \(n\) draws.
Proposition 3.4.3 (the maximum of \(n\) Gaussians). If \(g_1, \dots, g_n\) are \(\mathcal N(0, \sigma^2)\), independent or not, then \(\mathbb E \max_j g_j \le \sigma \sqrt{2 \log n}\). If they are independent, the two sides agree to leading order as \(n \to \infty\).
Proof of the bound. For \(\lambda > 0\), Jensen's inequality gives \(\exp(\lambda\, \mathbb E \max_j g_j) \le \mathbb E \max_j e^{\lambda g_j} \le \sum_j \mathbb E\, e^{\lambda g_j} = n\, e^{\lambda^2 \sigma^2/2}\), so \(\mathbb E \max_j g_j \le \tfrac{\log n}{\lambda} + \tfrac{\lambda \sigma^2}{2}\). Take \(\lambda = \sqrt{2 \log n}/\sigma\). ∎
Remark 2.7.7 (Gaussian samples have no outliers). The factor \(\sqrt{\log N}\) appearing in Proposition 2.7.6 is unavoidable: in Exercise 2.38 you will see that i.i.d. random variables \(g_i \sim N(0, 1)\) satisfy
\[\mathbb E \max_{i \le N} \lvert g_i \rvert \approx \sqrt{2 \ln N}.\]The good news is that the logarithmic factor grows slowly and is often negligible. This is great for sampling because it helps prevent extreme outliers. On average, the farthest point in an \(N\)-point sample from a normal distribution is only \(\sqrt{2\ln N}\) standard deviations away from the mean!
—R. Vershynin, High-Dimensional Probability, second edition (2026).Cambridge University Press, Remark 2.7.7; the bound above is Proposition 2.7.6 of the book.
Remark 3.4.4 (two regimes of a random row). Let the scores of a row be independent \(\mathcal N(0, \sigma^2)\) and \(Z = \sum_j e^{z_j}\). Under the weights \(e^{z_j}/Z\) a Gaussian sample has mean \(\sigma^2\), so the terms that carry \(Z\) are those with \(z_j\) near \(\sigma^2\). They exist among \(n\) draws while \(\sigma^2\) is below the largest draw, about \(\sigma\sqrt{2\log n}\), that is for \(\sigma < \sigma_c = \sqrt{2 \log n}\), which is 3.72 at \(n = 1{,}024\). Then \(H \approx \log n - \sigma^2/2\): the row attends to about \(n\, e^{-\sigma^2/2}\) keys. For \(\sigma > \sigma_c\) the few largest scores carry the sum and the row points at an arbitrary key. Unscaled, \(\sigma = \sqrt{d_k}\) exceeds \(\sigma_c\) as soon as \(d_k > 2 \log n\), at \(n = 1{,}024\) for every head wider than 13. Scaled, \(\sigma = 1\) and the row starts as an average over \(1{,}024\, e^{-1/2} \approx 621\) keys. The argument is a heuristic, known in physics as the freezing of the random energy model. This can be checked on random queries and keys in \(d_k\) dimensions, scored by the raw dot product, by the dot product divided by \(\sqrt{d_k}\), and by normalized queries and keys times a gain.
one query against n = 1,024 random keys in d dimensions; 16 queries averaged
scores spread, d = 64 keys attended, exp(H), at d =
2 8 16 64 256 1,024
q·k √64 = 8.00 290 31.9 6.9 2.5 1.2 1.2
q·k / √d 1 526 569 592 623 627 626
12 cos(q, k) 12/√64 = 1.50 195 49.2 70.8 365 780 955
predicted for Gaussian scores of spread σ: n exp(−σ²/2), and 1 once σ passes √(2 ln n) = 3.72
at d = 64: 1.0, 621, 332 keys; plain dot products freeze beyond d = 2 ln n = 13.9
plain dot products at d = 64: largest weight 0.73, gradient through the softmax 0.39 of 1
the same divided by √d: largest weight 0.015, gradient 1.00 of 1
grow q and k 2 times: q·k / √d has spread 4, past 3.72; 12 cos(q, k) does not move
(the live figure needs JavaScript; it draws the vectors in the page and loads no data)
At a head width of 64 and 1,024 keys 16 random rows attend 2.5 keys on average under plain dot products, with 0.73 of the weight on one key, and 623 under the same scores divided by \(\sqrt{64}\), where the heuristic says one and 621. Grow every entry of the queries and keys two times, as training may, and the divided scores have spread four, past 3.72, and attend 13.8 keys, while the cosine times a gain of 12 attends 365 before and after.
That is the weakness of the 2017 argument: it is about the first step of training, and a head can sharpen itself afterwards by growing its weights. By Proposition 3.3.1 a long key also gets extra weight from every query. Query-key normalization, proposed in 2020, removes the freedom: queries and keys are normalized, in the paper to unit length, and a score is a gain times their cosine, \(s_{ij} = g \cos(q_i, k_j)\).A. Henry, P. R. Dachapally, S. Pawar and Y. Chen, "Query-key normalization for Transformers", Findings of EMNLP 2020 (arXiv 2010.04245). Their gain is one learned number initialized at \(\log_2(L^2 - L)\) for a training length \(L\), about \(2.9 \log L\). The scale \(\sqrt{d_k}\) for unit vectors is in I. Loshchilov, C.-P. Hsieh, S. Sun and B. Ginsburg, "nGPT: normalized Transformer with representation learning on the hypersphere", 2024 (arXiv 2410.01131). The scores of a row then lie in \([-g, g]\), and bounded scores obey a lemma of two lines.
Proposition 3.4.5 (bounded scores must disperse). If the \(n\) scores of a row lie in an interval of width \(\delta\), every weight of the row lies between \(e^{-\delta}/n\) and \(e^{\delta}/n\).
Proof. Let \(M\) be the top of the interval. A numerator is at most \(e^{M}\) and the denominator at least \(n\, e^{M - \delta}\); a numerator is at least \(e^{M - \delta}\) and the denominator at most \(n\, e^{M}\). ∎P. Veličković, C. Perivolaropoulos, F. Barbero and R. Pascanu, "Softmax is not enough", ICML 2025 (arXiv 2410.01104), Lemma 2.1. Their Theorem 2.2 shows that over a finite vocabulary the scores of every head are bounded.
Example 3.4.6 (one matched key among \(n\)). The setup: one key whose score exceeds by \(\delta\) the equal scores of the \(n - 1\) others. Its weight is \(1/(1 + (n - 1)\, e^{-\delta})\), one half at \(\delta = \log(n - 1)\). With normalized queries and keys, an exact match has cosine one and unrelated keys in high dimension have cosine near zero (Section 2.4), so \(\delta = g\): at a context of 512 a gain of 8 caps such a head at a weight of 0.854 and a gain of 12 at 0.997; at a context of 256 a gain of 5.7 caps it at 0.540. The gain a head needs in order to point grows like \(\log n\). ◁
Example 3.4.7 (the gain, measured). The setup: the 8-layer model of the ladder (512 wide, eight heads of width 64, context 512) trained for 50M tokens of FineWeb-EDU, and gpt-pico (four heads of width 32, context 256) trained for 60M tokens of TinyStories, both with the 2026 recipe as it stood when these probes ran; one run for each constant gain, compared by held-out loss in nats per token. On the 8-layer model a gain of 8, which is \(\sqrt{d_k}\) and reproduces the 2017 scale at initialization, was worse than gains of 11.5 or 16 by 0.014 to 0.019 nats, about twice the most that two seeds of a run under this recipe have differed by (0.008, over fourteen pairs); 11.5 and 16 were within 0.005 of each other. On gpt-pico a gain of 5.7, again \(\sqrt{d_k}\), was worse than 8.1, 11.3 and 15 by 0.012 to 0.015, and those three were within 0.003; gpt-pico has no second seed to hold that against. When each head learns its own gain, starting from \(\sqrt{d_k}\), the heads of the 8-layer model end at 14.9 on average (8.2 in the first layer, 14 to 18 above it) and those of gpt-pico at 12.6; the loss was lower by a further 0.004 to 0.005, inside that spread, and a later run does not show it (Section 3.8). The recipe of gpt-pp uses the constant 12 for every head, on the flat part of both curves; that the 2017 scale is worse is what both models say. These are short runs, which say where to start; the ceilings of Example 3.4.6 are consistent with them. ◁
In the code. The gain is set where a layer is built and applied where its queries and keys are prepared for the scores, to the query alone. It is __init__ and position of CausalSelfAttention in gpt-pp's model.py.
def __init__(self, cfg: ModelConfig):
super().__init__()
self.n_head, self.n_kv_head, self.d_head = cfg.n_head, cfg.kv_heads, cfg.d_head
self.q = nn.Linear(cfg.d_model, self.n_head * self.d_head, bias=cfg.bias)
self.k = nn.Linear(cfg.d_model, self.n_kv_head * self.d_head, bias=cfg.bias)
self.v = nn.Linear(cfg.d_model, self.n_kv_head * self.d_head, bias=cfg.bias)
self.o = nn.Linear(self.n_head * self.d_head, cfg.d_model, bias=cfg.bias)
self.qk_norm = cfg.qk_norm
# Queries and keys normalized to unit root-mean-square have norm sqrt(dh), and scores are divided by
# sqrt(dh): the score of such a pair is sqrt(dh) * cos. This gain on the query makes it qk_scale * cos.
self.qk_gain = cfg.qk_scale / math.sqrt(self.d_head)
self.qk_factor = nn.Parameter(torch.ones(self.n_head)) if cfg.qk_norm and cfg.qk_scale_learned else None
self.dropout = cfg.dropout
...
def position(self, q: Tensor, k: Tensor, rot: Rotation) -> tuple[Tensor, Tensor]:
"""Normalize queries and keys (QK normalization) and turn them by their positions (rotary)."""
if self.qk_norm:
q = F.rms_norm(q, (self.d_head,), eps=1e-6) * self.qk_gain
k = F.rms_norm(k, (self.d_head,), eps=1e-6)
if self.qk_factor is not None:
q = q * self.qk_factor.view(-1, 1, 1).to(q.dtype)
if rot is not None:
q, k = rotate(q, *rot), rotate(k, *rot)
return q, k
cfg.qk_scale is the gain \(g\), 12 in the recipe. F.rms_norm divides a vector by the root of the mean of its squares, so a normalized key has length \(\sqrt{d_k}\), eight in gpt-pp, and a query, multiplied by qk_gain, has length \(g\); the division by \(\sqrt{d_k}\) in the scores then leaves \(s_{ij} = g \cos(q_i, k_j)\), the score that the opening figure prints as 12 times the cosine. With qk_scale_learned each head multiplies its queries by one more number, qk_factor, which starts at one: the learned gains of Example 3.4.7. The first lines are the four matrices of Definition 3.2.1 for all the heads of a layer, self.q, self.k, self.v and self.o, each a layer of its own; GPT-2's code holds the first three as one matrix, one of the reasons its released weights do not load here (Section 5).
Quirk. This is not the paper's form. The paper normalizes queries and keys to unit length and multiplies their product by the gain; the code normalizes them to unit root mean square, puts \(g/\sqrt{d_k}\) on the query alone and keeps the division by \(\sqrt{d_k}\) of (3.2), so that both paths of Section 3.2 compute the plain scaled dot product and the scale argument of PyTorch's fused function goes unused. The score is the same up to the \(10^{-6}\) added under the root.
Quirk. rotate, the rotary position of Section 4, comes after the normalization and changes no length, so the scores keep their bound in a model with positions. It pairs coordinate \(i\) of a head with coordinate \(i + d_k/2\), where the paper pairs neighbours; Section 4.4 says what follows from that.
Known issue. The unit of qk_scale changed during the build. The probes of Example 3.4.7 ran when it was counted in units of \(\sqrt{d_k}\): their recorded configurations say 1, 1.44 and 2 where the example says 8, 11.5 and 16 for the 8-layer model, and 1, 1.44, 2 and 2.65 where it says 5.7, 8.1, 11.3 and 15 for gpt-pico. Their checkpoints were deleted, because today's code would read those numbers as gains; the example gives every gain in today's unit, so none of its numbers changes.
Since 2017 the thinking has moved in two ways. Normalization now has a derivation and not only a use: by Proposition 3.3.1, softmax attention is a proper local constant regressor exactly when the keys have equal norm.Wang, Shi and Fox (2025), after their Equation 51: "softmax attention with QKNorm is a locally zeroth order non-parametric approximation of the true key-value map." And the right scale depends on the length of the context: by Proposition 3.4.5 a head with bounded scores spreads its weight like $$1/n$$ as the context grows, however sharp it was at the lengths it was trained on.
Remark 3.4.8 (the critical scale has three published answers). How fast must the scale grow with \(n\) for attention to stay selective? For independent Gaussian scores of spread \(\sigma\), the transition of Remark 3.4.4 is at \(\beta_c = \sqrt{2 \log n}/\sigma\). For tokens at equal angles, with pairwise inner product \(\rho\), a theorem of 2025 puts it at \(\beta_n = \gamma \log n\) with \(\gamma = 1/(1 - \rho)\), where the weight \(e^{\beta_n}\) of a token on itself balances the weight \(n\, e^{\beta_n \rho}\) of the others: Example 3.4.6 with \(\delta = \beta_n (1 - \rho)\). For keys drawn from a continuous density on a sphere of fixed dimension \(d\), a paper of 2026 from the same group finds \(\beta_n \asymp n^{2/(d-1)}\), the scale at which the cap of radius \(\beta^{-1/2}\) that a softmax sees around its query holds one key.S. Chen, Z. Lin, Y. Polyanskiy and P. Rigollet, "Critical attention scaling in long-context transformers", ICLR 2026 (arXiv 2510.05554), Theorem 2.1; G. Bruno, S. Chen, Z. Lin, Y. Polyanskiy and P. Rigollet, "Scaling limits of long-context transformers", 2026 (arXiv 2605.08505, version 2 of 3 November 2026), Theorems 3.1 to 3.3. The answers differ because the law of the best score differs: a Gaussian tail, a gap, a power law at the edge of the sphere. That reconciliation is ours and not a published statement, and which model describes the keys of a trained network is open.
What a stack of attention does
A head averages (Proposition 3.2.2), and a network is a stack of heads. What does averaging do when it is repeated? The first answer, in 2021, was alarming.
Attention-based architectures have become ubiquitous in machine learning. Yet our understanding of the reasons for their effectiveness remains limited. This work proposes a new way to understand self-attention networks: we show that their output can be decomposed into a sum of smaller terms, each involving the operation of a sequence of attention heads across layers. Using this decomposition, we prove that self-attention possesses a strong inductive bias towards “token uniformity”. Specifically, without skip connections or multi-layer perceptrons (MLPs), the output converges doubly exponentially to a rank-1 matrix. On the other hand, skip connections and MLPs stop the output from degeneration. Our experiments verify the identified convergence phenomena on different variants of standard transformer architectures.
—Y. Dong, J.-B. Cordonnier and A. Loukas, "Attention is not all you need: pure attention loses rank doubly exponentially with depth" (2021).arXiv 2103.03404, abstract.
A matrix of rank one means here that every token carries the same vector. The mechanism is elementary.
Proposition 3.5.1 (an average contracts). Let \(A\) be an \(n \times n\) matrix with nonnegative entries and rows that sum to one, and suppose that any two of its rows overlap: \(\sum_j \min(A_{ij}, A_{lj}) \ge a > 0\) for all \(i, l\). Then for every \(u \in \mathbb R^n\),
\[\max_i (Au)_i - \min_i (Au)_i \;\le\; (1 - a)\,\bigl(\max_j u_j - \min_j u_j\bigr) .\]Proof. \((Au)_i - (Au)_l = \sum_j (A_{ij} - A_{lj})\, u_j\). The positive parts of the differences \(A_{ij} - A_{lj}\) sum to \(1 - \sum_j \min(A_{ij}, A_{lj}) \le 1 - a\), and so do the negative parts, so the sum is at most \((1 - a) \max_j u_j - (1 - a) \min_j u_j\). ∎
Apply it to each coordinate of the values. Unmasked attention with scores in an interval of width \(\delta\) has every entry at least \(e^{-\delta}/n\) (Proposition 3.4.5), so \(a \ge e^{-\delta}\): every layer of pure attention shrinks the spread of the values across tokens by at least the factor \(1 - e^{-\delta}\). Under the causal mask all rows still overlap on the first token, and the collapse, slower, is toward it. The theorem of 2021 is stronger.
Theorem 3.5.2 (rank collapse; Dong, Cordonnier and Loukas). Let \(X \in \mathbb R^{n \times d}\) hold the tokens as rows, let \(\operatorname{res}(X) = X - \mathbf 1 x^{\top}\) be its difference from the nearest matrix with equal rows, and \(\lVert X \rVert_{1,\infty} = \sqrt{\lVert X \rVert_1 \lVert X \rVert_\infty}\). For a network \(\mathrm{SAN}\) of \(L\) layers of single-head attention without skip connections or MLPs, whose weights satisfy \(\lVert W_{QK}^{l} \rVert_1\, \lVert W_V^{l} \rVert_{1,\infty} \le \omega\) in every layer \(l\),
\[\lVert \operatorname{res}(\mathrm{SAN}(X)) \rVert_{1,\infty} \;\le\; \Bigl(\frac{4 \gamma\, \omega}{\sqrt{d_k}}\Bigr)^{\frac{3^L - 1}{2}}\; \lVert \operatorname{res}(X) \rVert_{1,\infty}^{\,3^L},\]where \(\gamma\) depends on the entries of the patterns.
The exponent \(3^L\) is the doubly exponential rate. The bound contracts only when the residual is already small, the paper's own experiments find the collapse hard to observe at a width of 128, and it is a statement about attention alone, not a description of trained transformers. With a skip connection a layer computes \(x + \mathrm{attn}(x)\), and the network expands into a sum over paths through any subset of the layers, among them the path through none, which contracts nothing; an MLP changes the bound by its Lipschitz constant. That is what skip connections and MLPs are for (Section 5.5).Where the harm is in practice: L. Noci and co-authors, "Signal propagation in Transformers: theoretical perspectives and the role of rank collapse", 2022 (arXiv 2206.03126), show that collapse at initialization makes the gradients of the queries and keys vanish.
The picture of 2023 to 2026 keeps the skip connection and the normalization and asks what remains of the collapse. With both, a layer moves each token a little and puts it back on a sphere, and a deep stack becomes a flow in time.
Definition 3.5.3 (self-attention dynamics). The tokens are particles \(x_1(t), \dots, x_n(t)\) on the unit sphere \(\mathbb S^{d-1}\), time \(t\) is depth, and
\[\dot x_i = \mathsf P^{\perp}_{x_i}\Bigl(\sum_{j=1}^{n} A_{ij}(t)\, x_j\Bigr), \qquad A_{ij}(t) = \frac{e^{\beta \langle x_i, x_j \rangle}}{\sum_{l} e^{\beta \langle x_i, x_l \rangle}}, \qquad \mathsf P^{\perp}_{x}\, y = y - \langle x, y \rangle\, x . \tag{3.4}\]The projection \(\mathsf P^{\perp}_x\) keeps a particle on the sphere, as normalization does, and \(\beta\) gathers the factor \(1/\sqrt{d_k}\) and the scale of the query and key matrices, which like the value matrix are taken to be the identity.
Each particle moves along the sphere toward the attention-weighted average of the particles. The model has no MLP, the same weights at every layer and no mask.B. Geshkovski, C. Letrouit, Y. Polyanskiy and P. Rigollet, "A mathematical perspective on Transformers", Bulletin of the American Mathematical Society 62 (2025), pages 427 to 479 (arXiv 2312.10794), Section 2.2; the theorem below is their Theorems 6.1 and 6.3 with Lemma 6.4.
Theorem 3.5.4 (clustering). (i) If \(d \ge 3\), then for every \(\beta \ge 0\) and almost every initial configuration there is a point \(x^{\ast}\) of the sphere with \(x_i(t) \to x^{\ast}\) for all \(i\). (ii) If the initial particles lie in an open hemisphere, which holds almost surely for \(n \le d\) independent uniform points, then \(\lVert x_i(t) - x^{\ast} \rVert \le C e^{-\lambda t}\), also for general query and key matrices.
Why. For (ii), suppose \(\langle x_i, w \rangle > 0\) for all \(i\) and some direction \(w\), and let \(i\) attain the smallest of these inner products, \(c\). By (3.4), \(\tfrac{d}{dt}\langle x_i, w\rangle = \sum_j A_{ij}\bigl(\langle x_j, w \rangle - \langle x_i, x_j \rangle\, c\bigr) \ge c \sum_j A_{ij}\,(1 - \langle x_i, x_j \rangle) \ge 0\): the smallest inner product can only grow, and a cone of particles only narrows. For (i), the flow increases the energy \(\tfrac{1}{2\beta} \sum_{i,j} e^{\beta \langle x_i, x_j \rangle}\), which is largest when all particles coincide; every other stationary configuration is a saddle, reached from a set of starts of measure zero.
One point for all tokens is the collapse of Theorem 3.5.2 again, now with skip connections and normalization in place, and it contradicts what trained networks are seen to do. The authors' resolution is about time scales.
Following [SABP22] and [VBC20], we observe that Transformers are in fact flow maps on \(\mathcal{P}(\mathbb{R}^{d})\), the space of probability measures over \(\mathbb{R}^{d}\). To realize this flow map from measures to measures, Transformers evolve a mean-field interacting particle system. More specifically, every particle (called a token in this context) follows the flow of a vector field which depends on the empirical measure of all particles. In turn, the continuity equation governs the evolution of the empirical measure of particles, whose long-time behavior is of crucial interest. In this regard, our main observation is that particles tend to cluster under these dynamics. This phenomenon is of particular relevance in learning tasks such as next-token prediction, wherein one seeks to map a given input sequence (i.e., a sentence) of \(n\) tokens (i.e., words) onto a given next token. In this case, the output measure encodes the probability distribution of the next token, and its clustering indicates a small number of possible outcomes. Our results on a simplified but insightful toy model indicate that the limiting distribution is actually a point mass, leaving no room for diversity or randomness, which is at odds with practical observations. This apparent paradox is resolved by the existence of a long-time metastable state. As can be seen from Figures 3 and 5, the Transformer flow appears to possess two different time-scales: in a first phase, tokens quickly form a few clusters, while in a second (much slower) phase, through the process of pairwise merging of clusters, all tokens finally collapse to a single point. This appears to corroborate behavior observed empirically in trained Transformer models, which goes under the names token uniformity, over-smoothing [CZC+22, RZZD23, GWDW23, WAWJ24, WAW+24, DBK24, SWJS24], or rank-collapse [DCL21, FZH+22, NAB+22, JDB23, ZMZ+23, ZLL+23, NLL+24, BHK24, CNQG24]; see also Figure 1.
—Geshkovski, Letrouit, Polyanskiy and Rigollet (2025).Section 1, the third paragraph.
The slow phase was a conjecture in that paper and has been a theorem since 2024: particles that start in a few tight groups, with inner products at most \(\alpha < 1\) between points of different groups, stay in their groups for a time that grows like \(e^{(1 - \alpha)\beta}\), and in high dimension random points are such a configuration with high probability.B. Geshkovski, H. Koubbi, Y. Polyanskiy and P. Rigollet, "Dynamic metastability in the self-attention model", 2024 (arXiv 2410.06833), Theorem 1.2 and Corollary 4.4, stated here without their constants. The count of clusters is in P. Rigollet, "The mean-field dynamics of Transformers", to appear in the Proceedings of the ICM 2026 (arXiv 2512.01868), Section 5.3. The metastable phase has of order \(\sqrt{\beta}\) clusters, and here the readings of Section 3.3 meet: the flow (3.4) iterates the kernel smoother of Proposition 3.3.1 on its own keys, an algorithm that statisticians use to find the modes of a density, and its long-lived clusters are the metastable states of the Hopfield reading, now in depth.
Under (3.4), tokens on a three-dimensional sphere gather into clusters, remain in them for a long time, then merge one cluster at a time. The energy rises at each merger; the long waits between them are the metastable phase.
n tokens x_1 … x_n on the unit sphere; time t is depth. Each token moves toward the mean of all tokens, weighted by its attention to them: dx_i/dt = P_i Σ_j a_ij x_j a_ij = exp(β x_i·x_j) / Σ_k exp(β x_i·x_k) P_i removes the part along x_i, which keeps x_i on the sphere 32 tokens from one random start, β = 9: time clusters their sizes energy ÷ its maximum 0 32 1 each 0.08 9.6 4 14 9 6 3 0.31 ● ● ● ● 246 3 15 14 3 0.42 ● ● ● 3,147 2 17 15 0.50 ● ● 1.2 × 10⁵ 1 32 1.00 ● four clusters by time 9.6; the last two merge 13,000 times later the last merge from the same start: β = 3 at 12.5, β = 6 at 925, β = 12 at 1.6 × 10⁷ (the live figure needs JavaScript; it loads about 0.7 MB of three.js for the sphere and no data)
From one random start of 32 tokens at \(\beta = 9\), four clusters have formed by time 10 and the last two do not merge until time \(1.2 \times 10^5\), some 13,000 times later. Each unit of \(\beta\) multiplies that last wait by about five, which is what \(e^{(1 - \alpha)\beta}\) predicts for two clusters 126 degrees apart.
What this says about real networks is limited: a trained transformer lives at a finite time of a flow whose weights change from layer to layer and which has MLPs, and the theory for that case is open. What survives is a way of judging components by how they spend the contraction that depth brings, and the placement of the normalization is the first example.
For tokens that start at equal angles, the distance of their common cosine from one decays like \(e^{-2t}\) when the normalization follows the addition, as in the 2017 model, and like \(1/t^2\) when it normalizes only what a layer reads, as in every GPT since GPT-2: an exponential rate against a polynomial one, in line with the practice that Section 5.2 takes up.Rigollet (2026), Section 6.2. Normalization does more than set a rate: X. Wu, A. Ajorlou, Y. Wang, S. Jegelka and A. Jadbabaie, "On the role of attention masks and LayerNorm in Transformers", NeurIPS 2024 (arXiv 2405.18781), refute the 2021 paper's section title "Layer normalization plays no role" by exhibiting equilibria of every rank from one to full.
Cost, and why exact attention won
The first paper on attention named its price: the weights have to be computed for every source word and every target word, a drawback its authors called not severe for sentences of 15 to 40 words. At the 1,024 tokens of gpt-pp a layer computes 16 scores for every number it moves (Example 3.2.4), and the ratio, \(h\, n / d\), grows with the context: 128 at 8,192 tokens, 15,625 at a million. Between 2019 and 2021 the response was to stop computing most of the matrix. In the terms of Section 3.3, a method either routes each query to a part of the memory or compresses the memory.
Fixed sparse patterns route by position: strided and local positions in the Sparse Transformer, a sliding window and a few global tokens in Longformer, random tokens as well in BigBird. Hashing routes by content: Reformer sorts the keys into buckets and attends inside a bucket. Low rank compresses: Linformer projects the keys and values to a fixed number, and Nyströmformer rebuilds the pattern from a few landmark rows and columns. Kernel features compress as well: Performer and the linear transformers replace the exponential by a finite feature map, which makes attention the linear memory of Proposition 3.3.3 with \(m\) features, at cost \(O(nm)\) and capacity \(m\).R. Child, S. Gray, A. Radford and I. Sutskever, "Generating long sequences with sparse Transformers", 2019 (arXiv 1904.10509); I. Beltagy, M. E. Peters and A. Cohan, "Longformer", 2020 (arXiv 2004.05150); M. Zaheer and co-authors, "Big Bird", 2020 (arXiv 2007.14062); N. Kitaev, Ł. Kaiser and A. Levskaya, "Reformer", ICLR 2020 (arXiv 2001.04451); S. Wang and co-authors, "Linformer", 2020 (arXiv 2006.04768); Y. Xiong and co-authors, "Nyströmformer", AAAI 2021 (arXiv 2102.03902); A. Katharopoulos, A. Vyas, N. Pappas and F. Fleuret, "Transformers are RNNs", ICML 2020 (arXiv 2006.16236). A benchmark built to compare them, Long Range Arena, found no winner.
Averaged over five tasks on sequences of 1,000 to 4,000 elements, the full transformer scored 54.39. Of the alternatives read here, two of the fastest, Performer and Linformer, scored 51.41 and 51.36 at 5.7 and 5.5 times its training speed at 4,000 elements, and the most accurate, BigBird, 55.01 at 1.1 times.Y. Tay and co-authors, "Long Range Arena: a benchmark for efficient Transformers", ICLR 2021 (arXiv 2011.04006), Tables 1 and 2, which have further rows. None of them displaced full attention in the language models of the following years. The reason was found in 2022, and it is not about arithmetic.
Transformers are slow and memory-hungry on long sequences, since the time and memory complexity of self-attention are quadratic in sequence length. Approximate attention methods have attempted to address this problem by trading off model quality to reduce the compute complexity, but often do not achieve wall-clock speedup. We argue that a missing principle is making attention algorithms IO-aware—accounting for reads and writes between levels of GPU memory. We propose FlashAttention, an IO-aware exact attention algorithm that uses tiling to reduce the number of memory reads/writes between GPU high bandwidth memory (HBM) and GPU on-chip SRAM. We analyze the IO complexity of FlashAttention, showing that it requires fewer HBM accesses than standard attention, and is optimal for a range of SRAM sizes. We also extend FlashAttention to block-sparse attention, yielding an approximate attention algorithm that is faster than any existing approximate attention method. FlashAttention trains Transformers faster than existing baselines: 15% end-to-end wall-clock speedup on BERT-large (seq. length 512) compared to the MLPerf 1.1 training speed record, 3× speedup on GPT-2 (seq. length 1K), and 2.4× speedup on long-range arena (seq. length 1K-4K). FlashAttention and block-sparse FlashAttention enable longer context in Transformers, yielding higher quality models (0.7 better perplexity on GPT-2 and 6.4 points of lift on long-document classification) and entirely new capabilities: the first Transformers to achieve better-than-chance performance on the Path-X challenge (seq. length 16K, 61.4% accuracy) and Path-256 (seq. length 64K, 63.1% accuracy).
—T. Dao, D. Y. Fu, S. Ermon, A. Rudra and C. Ré, "FlashAttention: fast and memory-efficient exact attention with IO-awareness" (2022).NeurIPS 2022 (arXiv 2205.14135), abstract. For the A100 its Section 2.1 gives 40 to 80 GB of high-bandwidth memory and 192 KB of on-chip memory for each of 108 processors. The comparison on GPT-2 medium is its Figure 2: forward and backward pass, 1,024 tokens, 64 sequences.
The missing principle, the paper argues, is to count what an algorithm reads and writes between the levels of a GPU's memory. A GPU keeps its tensors in gigabytes of high-bandwidth memory and computes in a few hundred kilobytes of on-chip memory per processor, about ten times faster to reach. Written as three library calls, attention forms the scores \(S = QK^{\top}\) in the large memory, reads them back to take the softmax \(A\), writes that, reads it back to multiply by \(V\), and keeps \(A\) for the backward pass. On GPT-2 medium the paper's algorithm does more arithmetic than the three calls (75.2 against 66.6 billion operations), moves nine times fewer bytes (4.4 against 40.3 GB) and takes 5.7 times less time (7.3 against 41.7 ms); that is the attention operation alone, where the threefold speedup of the abstract is of training GPT-2 end to end. It has to do two things: take a softmax without having the whole row at hand, and run the backward pass without a stored pattern.
The softmax in pieces. Take one row of scores \(s_{i1}, s_{i2}, \dots\), with the factor \(1/\sqrt{d_k}\) absorbed into the queries, and a set \(J\) of keys. Keep three things:
\[m = \max_{j \in J} s_{ij}, \qquad \ell = \sum_{j \in J} e^{s_{ij} - m}, \qquad a = \sum_{j \in J} e^{s_{ij} - m}\, v_j . \tag{3.5}\]Proposition 3.6.1 (partial softmaxes merge). Write \(R(J) = (m, \ell, a)\) for the summary (3.5). For disjoint sets of keys \(J\) and \(J^{\prime}\), with \(m = \max(m_J, m_{J^{\prime}})\),
\[R(J \cup J^{\prime}) = \bigl(m,\;\; e^{m_J - m}\, \ell_J + e^{m_{J^{\prime}} - m}\, \ell_{J^{\prime}},\;\; e^{m_J - m}\, a_J + e^{m_{J^{\prime}} - m}\, a_{J^{\prime}}\bigr) .\]The merge is associative and commutative, no exponent in it is positive, and \(1 \le \ell \le \lvert J \rvert\). When \(J\) is all the keys the row may read, the output of attention is \(a/\ell\) and the logarithm of its normalizer is \(m + \log \ell\).
Proof. The map \((m, \ell, a) \mapsto (e^{m} \ell,\, e^{m} a) = \bigl(\sum_J e^{s_{ij}},\, \sum_J e^{s_{ij}} v_j\bigr)\) turns the merge into the addition of a number and of a vector. The summary is those two sums, stored so that nothing overflows: the largest term of \(\ell\) is one. ∎
For a single softmax read one element at a time the merge dates from 2018.M. Milakov and N. Gimelshein, "Online normalizer calculation for softmax", 2018 (arXiv 1805.02867). M. N. Rabe and C. Staats, "Self-attention does not need \(O(n^2)\) memory", 2021 (arXiv 2112.05682), had the lazy division, and saved memory, not time. FlashAttention applies it to blocks: the matrix of scores is cut into tiles of \(B_r\) queries by \(B_c\) keys, small enough that a tile is born, exponentiated, multiplied into its values and discarded without leaving the on-chip memory.
Algorithm 3.6.2 TILED-ATTENTION
(forward pass of one head, in the order used since 2023)
Input Q, K, V with n rows each, in the large memory; a tile Br x Bc.
Output O = softmax(Q K^T + mask) V, and L, one number per row.
1. for each block Qi of Br queries (the blocks in parallel):
2. load Qi; m <- -inf, l <- 0, a <- 0 (one of each per row)
3. for each block (Kj, Vj) of Bc keys and values:
4. if the mask hides the whole tile, skip it
5. load Kj, Vj; S <- Qi Kj^T; set masked entries to -inf
6. m_new <- max(m, rowmax(S))
7. P <- exp(S - m_new)
8. l <- exp(m - m_new) l + rowsum(P)
9. a <- exp(m - m_new) a + P Vj
10. m <- m_new
11. write Oi <- a / l and Li <- m + log l
Lines 6 to 10 are Proposition 3.6.1 with \(J\) the keys read so far and \(J^{\prime}\) the new tile. Nothing of size $$n^2$$ is written anywhere.
Example 3.6.3 (four tokens by hand). The setup: four tokens, a head of width two, tiles of two by two, no mask, and numbers chosen so that every exponential is a power of two:
\[Q = \log 2 \begin{pmatrix} 1 & 0\\ 0 & 1\\ 1 & 1\\ -1 & 0 \end{pmatrix}, \quad K = \begin{pmatrix} 0 & 1\\ 1 & 0\\ 2 & 0\\ 0 & 2 \end{pmatrix}, \quad V = \begin{pmatrix} 8 & 0\\ 0 & 8\\ 8 & 8\\ 16 & -8 \end{pmatrix}, \quad e^{S} = \begin{pmatrix} 1 & 2 & 4 & 1\\ 2 & 1 & 1 & 4\\ 2 & 2 & 4 & 4\\ 1 & \tfrac12 & \tfrac14 & 1 \end{pmatrix} .\]Take the first row. Directly, its weights are \((1, 2, 4, 1)/8\) and its output is \(\bigl((8, 0) + 2\,(0, 8) + 4\,(8, 8) + (16, -8)\bigr)/8 = (7, 5)\). In tiles: the first tile holds keys 1 and 2 with \(e^{S} = (1, 2)\), so \(m = \log 2\), \(P = (\tfrac12, 1)\), \(\ell = \tfrac32\) and \(a = \tfrac12 (8, 0) + (0, 8) = (4, 8)\). The second tile holds keys 3 and 4 with \(e^{S} = (4, 1)\). The maximum rises to \(\log 4\), the old summary is multiplied by \(e^{m - m_{\text{new}}} = \tfrac12\), \(P = (1, \tfrac14)\), and
\[\ell = \tfrac12 \cdot \tfrac32 + \tfrac54 = 2, \qquad a = \tfrac12 (4, 8) + (8, 8) + \tfrac14 (16, -8) = (14, 10), \qquad o_1 = \frac{a}{\ell} = (7, 5), \qquad L_1 = \log 4 + \log 2 = \log 8 .\]Under the causal mask the same row reads key 1 alone and \(o_1 = v_1 = (8, 0)\), the tile of keys 3 and 4 is never loaded for rows 1 and 2, and three of the four tiles are computed. ◁
slow memory (large, far) fast memory (small, on the chip) Q, K, V 8 rows of 2 -- a tile of each --> S = Q K' (2 x 2), then P = exp(S - m) O 8 rows of 2 <-- once a block ---- per query: m (running maximum), l (running sum) scores and weights, 8 x 8: never stored the tile of queries 5, 6 and keys 5, 6 (scores are multiples of ln 2 = 0.69) query scores m before m alpha l before l 5 0.69, mask 1.39 1.39 1 2 2.5 6 1.39, 2.77 1.39 2.77 0.25 2 1.75 numbers across the boundary, 8 tokens, tiles of 2, 10 of 16 tiles under the causal mask naive order 320 scores and weights written to slow memory, read back 2022, keys outside 232 64 phases, one after the other; 40 divisions 2023, rows outside 120 52 phases, one after the other; 16 divisions 2024, overlapped 120 the same 52 phases in 36 slots 2022, 2023, 2024: FlashAttention, FlashAttention-2, FlashAttention-3 output against softmax(Q K') V: the largest difference is 1.8 × 10⁻¹⁵ at 1,024 tokens of width 64, tiles of 128: 7.22 × 10⁵ against 4.46 × 10⁶ (the live figure needs JavaScript; it computes everything in the page and loads no data)
Extending Example 3.6.3 to eight tokens under the causal mask, the tiled loop of 2023 moves 120 numbers across the boundary where the three calls move 320, and its outputs agree with the direct formula to within \(2 \times 10^{-15}\); counted the same way at 1,024 tokens, a head of width 64 and tiles of 128, it is \(7.2 \times 10^5\) numbers against \(4.5 \times 10^6\).
The backward pass without the matrix. The textbook backward pass of a softmax uses the whole pattern. It does not have to.
Proposition 3.6.4 (the backward pass needs one number per row). Let \(O = AV\) with \(A\) the row-wise softmax of \(S = QK^{\top}\), let \(\bar O\) be the gradient of a loss with respect to \(O\), and \(\bar A = \bar O V^{\top}\). Then
\[\bar V = A^{\top} \bar O, \qquad \bar S_{ij} = A_{ij}\,\bigl(\bar A_{ij} - D_i\bigr) \;\text{ with }\; D_i = \sum_{l} A_{il}\, \bar A_{il}, \qquad \bar Q = \bar S K, \qquad \bar K = \bar S^{\top} Q,\]and (i) \(D_i = \bar o_i^{\top} o_i\); (ii) \(A_{ij} = \exp(s_{ij} - L_i)\) with \(L_i\) the number saved by Algorithm 3.6.2. Hence every tile of \(A\) and of \(\bar S\) can be rebuilt from \(Q_i\), \(K_j\), \(V_j\), the outputs and \(L\).
Proof. The formula for \(\bar S\) is the Jacobian of Proposition 3.4.2 applied to a row. (i) \(\sum_l A_{il}\, \bar o_i^{\top} v_l = \bar o_i^{\top} \sum_l A_{il} v_l\). (ii) \(L_i = \log \sum_l e^{s_{il}}\). ∎
So the backward pass recomputes each tile of the pattern instead of storing it, five matrix products per tile where the forward pass has two. That is the extra arithmetic, and a good trade: a matrix product is what a GPU does at full speed, and a trip to the large memory is not.
Theorem 3.6.5 (the traffic of attention). Count the numbers moved between a large memory and a fast memory of size \(M\), with \(d_k \le M \le n d_k\). The three-call implementation moves \(\Theta(n d_k + n^2)\) and the tiled algorithm \(\Theta(n^2 d_k^2 / M)\). No algorithm that computes exact attention with ordinary matrix products (nor, by the paper's last result, with fast ones) moves fewer than a constant times \(\min(n^2 d_k/\sqrt{M},\; n^2 d_k^2/M)\), so for \(M \ge d_k^2\) tiling is optimal.
Why. A tile of \(B_r B_c\) scores is made from \((B_r + B_c)\, d_k\) numbers, because the scores have rank \(d_k\) (Proposition 3.2.2): it is cheaper to carry the factors than the product. The lower bound is a theorem of 2024, whose authors put the question and the answer in their abstract.Dao et al. (2022), Theorem 2 and Proposition 3, where the lower bound is proved only for \(M\) of order \(n d_k\).
Self-attention is at the heart of the popular Transformer architecture, yet suffers from quadratic time and memory complexity. In a recent significant development, FlashAttention shows that the I/O complexity of attention is the true bottleneck in scaling Transformers. Given two levels of memory hierarchy, a fast cache (e.g. GPU on-chip SRAM) where computation happens and a slow memory (e.g. GPU high-bandwidth memory) where the data resides, the I/O complexity measures the number of accesses to the slow memory. FlashAttention is an I/O-aware algorithm for self-attention that requires \(\frac{N^{2}d^{2}}{M}\) I/O operations where \(N\) is the dimension of the attention matrix, \(d\) is the head-dimension and \(M\) is the size of cache. However, is this I/O complexity optimal? The known lower bound only rules out an I/O complexity of \(o(Nd)\) when \(M=\Theta(Nd)\), since the output of the attention mechanism that needs to be written in the slow memory is \(\Omega(Nd)\). The main question that remained open after FlashAttention is whether this I/O complexity is optimal for any value of M.
We resolve the above question in its full generality by showing an I/O complexity lower bound that matches the upper bound provided by FlashAttention for any values of \(M\geq d^{2}\) within any constant factors. Further, we give a better algorithm with lower I/O complexity for \(M<d^{2}\), and show that it is optimal as well. Moreover, our lower bounds do not rely on using combinatorial matrix multiplication for computing the attention matrix. We show even if one uses fast matrix multiplication, the above I/O complexity bounds cannot be improved. We do so by introducing a new communication complexity protocol for matrix compression, and connecting communication complexity to I/O complexity. To the best of our knowledge, this is the first work to establish a connection between communication complexity and I/O complexity, and we believe this connection could be of independent interest and will find many more applications in proving I/O complexity lower bounds in future.
—B. Saha and C. Ye, "The I/O complexity of attention, or how optimal is Flash Attention?" (2024).arXiv 2402.07443, abstract. Their \(N\) and \(d\) are the \(n\) and \(d_k\) of the theorem.
With head widths of 64 to 128 and a fast memory near 100 KB, real kernels are in the optimal regime.
After that the algorithm did not change. What changed, three times, is which part of the chip stands idle.
Version 2 (2023): the processor. On an A100 GPU the tiled kernel reached 25 to 40% of the rate at which the same chip multiplies matrices, for three reasons. Arithmetic outside the matrix-multiply units is 16 times dearer per operation, so the output is kept unnormalized until the last tile and one number per row is saved, where the 2022 version divided after every tile and saved two (lines 8, 9 and 11 of Algorithm 3.6.2). One job per head leaves most of the chip idle when sequences are long and batches small, so every block of queries becomes a job of its own (line 1). And inside a job the threads are divided among the queries and no longer among the keys, so they have no partial sums to exchange. The result was 50 to 73% of the chip's peak, about twice version 1.T. Dao, "FlashAttention-2: faster attention with better parallelism and work partitioning", 2023 (arXiv 2307.08691): 312 against 19.5 trillion floating-point operations per second for the two kinds of arithmetic. The algorithm box of that paper carries a misprint worth knowing.
Algorithm 1 FlashAttention-2 forward pass
6: for \(1\leq j\leq T_{c}\) do
7: Load \(\mathbf{K}_{j},\mathbf{V}_{j}\) from HBM to on-chip SRAM.
8: On chip, compute \(\mathbf{S}_{i}^{(j)}=\mathbf{Q}_{i}\mathbf{K}_{j}^{T}\in\mathbb{R}^{B_{r}\times B_{c}}\).
9: On chip, compute \(m_{i}^{(j)}=\mathrm{max}(m_{i}^{(j-1)},\mathrm{rowmax}(\mathbf{S}_{i}^{(j)}))\in\mathbb{R}^{B_{r}}\), \(\tilde{\mathbf{P}}_{i}^{(j)}=\exp(\mathbf{S}_{i}^{(j)}-m_{i}^{(j)})\in\mathbb{R}^{B_{r}\times B_{c}}\) (pointwise), \(\ell_{i}^{(j)}=e^{m_{i}^{j-1}-m_{i}^{(j)}}\ell_{i}^{(j-1)}+\mathrm{rowsum}(\tilde{\mathbf{P}}_{i}^{(j)})\in\mathbb{R}^{B_{r}}\).
10: On chip, compute \(\mathbf{O}_{i}^{(j)}=\mathrm{diag}(e^{m_{i}^{(j-1)}-m_{i}^{(j)}})^{-1}\mathbf{O}_{i}^{(j-1)}+\tilde{\mathbf{P}}_{i}^{(j)}\mathbf{V}_{j}\).
11: end for
In Example 3.6.3 the printed line multiplies the accumulator of the first row by 2 instead of \(\tfrac12\) before the second tile, which gives \(a = 2\,(4, 8) + (12, 6) = (20, 22)\) and the output \((10, 11)\) in place of \((7, 5)\).Two reports of the misprint are open on the kernel's public issue tracker, number 991 of June 2024 and number 2342 of March 2026; no reply from the authors was visible on 14 November 2026.
Version 3 (2024): time. On the next generation of chips the kernel of version 2 used 35% of the peak rate.
Attention, as a core layer of the ubiquitous Transformer architecture, is the bottleneck for large language models and long-context applications. FlashAttention elaborated an approach to speed up attention on GPUs through minimizing memory reads/writes. However, it has yet to take advantage of new capabilities present in recent hardware, with FlashAttention-2 achieving only 35% utilization on the H100 GPU. We develop three main techniques to speed up attention on Hopper GPUs: exploiting asynchrony of the Tensor Cores and TMA to (1) overlap overall computation and data movement via warp-specialization and (2) interleave block-wise matmul and softmax operations, and (3) block quantization and incoherent processing that leverages hardware support for FP8 low-precision. We demonstrate that our method, FlashAttention-3, achieves speedup on H100 GPUs by 1.5-2.0× with FP16 reaching up to 740 TFLOPs/s (75% utilization), and with FP8 reaching close to 1.2 PFLOPs/s. We validate that FP8 FlashAttention-3 achieves 2.6× lower numerical error than a baseline FP8 attention.
The H100 multiplies matrices at 989 TFLOPS (\(10^{12}\) floating-point operations per second) in 16-bit floats and evaluates exponentials, on a separate unit, at 3.9. A tile costs \(4 B_r B_c d_k\) operations of matrix product and \(B_r B_c\) exponentials, so the ratio of the two times is \(R_{\text{mm}}/(4\, d_k R_{\exp})\): 0.50 at a head width of 128 and 0.99 at 64, the head width of GPT-2 and of gpt-pp, where the softmax of a tile takes as long as its two products. The answer is to overlap in time what cannot be made faster. One group of threads only issues loads, ahead of need. Two groups of computing threads alternate, so that the softmax of one runs while the products of the other hold the matrix units (the paper's pingpong). And the products run in 8-bit floats, kept accurate by one scale per tile and by multiplying \(Q\) and \(K\) by a random orthogonal matrix \(M\) before rounding, which changes nothing, since \((QM)(KM)^{\top} = QK^{\top}\), and spreads an outlier of size \(c\) over all coordinates at about \(c/\sqrt{d_k}\).FlashAttention-3, Sections 3.1 to 3.3 and Table 2: 661 TFLOPs/s with every technique, 582 without the overlap of products and softmax inside a group, 570 without the specialized loader threads.
Version 4 (2026): the other units. On the generation after that the matrix units more than double, to 2.25 PFLOPS (\(10^{15}\) operations per second), and the exponential unit and the shared memory do not move: the ratio above becomes \(128/d_k\) by the paper's rates per processor, 2 at a head width of 64. The fourth version takes work away from the units that did not scale. A part of each row's exponentials, 10 to 25%, is computed in software as \(2^x = 2^{\lfloor x \rfloor}\, 2^{x - \lfloor x \rfloor}\), a shift of the exponent and a cubic polynomial, on multiply-add units that would otherwise idle. The rescaling of lines 8 and 9 is skipped unless \(e^{m}\) has grown by more than a factor of \(2^8\): by Proposition 3.6.1 the reference \(m\) only has to be common to \(\ell\) and \(a\). In Example 3.6.3, keeping \(m = \log 2\) through the second tile gives \(P = (2, \tfrac12)\), \(\ell = 4\), \(a = (28, 20)\) and again \((7, 5)\).T. Zadouri, M. Hoehnerbach, J. Shah, T. Liu, V. Thakkar and T. Dao, "FlashAttention-4: algorithm and kernel pipelining co-design for asymmetric hardware scaling", MLSys 2026 (arXiv 2603.05451): up to 1,613 TFLOPs/s, 71% utilization, on a B200 (the blog post that accompanied the paper says 1,605). FlashAttention-3 does not run on that chip.
Between 2017 and 2026 the function did not change. What changed is the order in which its numbers visit fast memory and, with each generation of hardware, which unit of the chip the kernel has to keep busy.
In the code. gpt-pp does not implement Algorithm 3.6.2: on the path that trains, attention is one call of PyTorch's F.scaled_dot_product_attention, which chooses a kernel itself, on queries, keys and values in 16-bit floats. The scores are written out on the other path, for the analyses and for every token the model writes (Section 3.2). It is CausalSelfAttention.forward in gpt-pp's model.py.
def forward(self, x: Tensor, rot: Rotation, bias: Optional[Tensor]) -> Tensor:
"""The fast path: softmax(q k^T / sqrt(dh) + mask) v in one fused kernel (FlashAttention where it applies).
`bias` is the ALiBi table, which contains the causal mask; without it the kernel masks causally itself."""
B, T, _ = x.shape
q, k, v = self.project(x)
q, k = self.position(q, k, rot)
k, v = self.share(k, v)
z = F.scaled_dot_product_attention(
q, k, v,
attn_mask=None if bias is None else bias.to(q.dtype),
is_causal=bias is None,
dropout_p=self.dropout if self.training else 0.0,
)
return self.o(z.transpose(1, 2).reshape(B, T, -1))
Projection, normalization, sharing and the output matrix are the calls of forward_explicit (Section 3.2); what the kernel returns is that function's z, and scores and pattern never exist as tensors. The difference is measured on our own cards: the 12-layer model at its context of 1,024 tokens trains at 46,600 tokens a second with the fused kernel and at 27,500 with the scores written out, on the same card and before compilation, and at its peak the whole model holds 1.1 GB of memory a sequence with the fused kernel and 2.2 with the scores written out.
PyTorch. F.scaled_dot_product_attention, as it is in PyTorch 2.9.1, applies dropout whether or not the model is training, so the code passes a dropout_p of zero outside training itself; and it raises an error when given both attn_mask and is_causal, so the code passes one or the other: the flag for the recipe, and for the ALiBi positions of Section 4 a table of biases that already holds the \(-\infty\) of the mask. Its documentation calls the function "beta and subject to change" and says that its output "may be different depending on what backend kernel is chosen". After that version, by the release notes and not by any test of this series, 2.10 adds a FlashAttention-4 kernel to the function, 2.14 computes shared key and value heads (Section 3.7) natively in one of its kernels, and 2.15 prefers another kernel on some cards: the same call may run other code on a newer PyTorch.
PyTorch. The table is a trap. The function accepts a mask or a bias passed as a tensor, but by its source at version 2.9.1 the FlashAttention kernel does not, and the call goes to the next kernel in the library's order, memory-efficient attention, without any message; which kernel ran on our cards was read from that source and not observed. At 32 sequences of 512 tokens the table cost 6% of the training rate, 193,000 against 205,000 tokens a second, and no memory; it was not measured at the full batch (Section 4.4 describes the variant).
Known issue. In the 16-bit floats of training (bfloat16 under torch.autocast; Section 6.7 says which operation runs in which precision) the two paths of Section 3.2 are not the same arithmetic. Scores, softmax and average happen inside one kernel on 16-bit queries, keys and values; forward_explicit adds its mask, a tensor of 32-bit floats, to a 16-bit product, which promotes the scores, and takes the softmax in 32 bits. On the 12-layer model, text sampled through one path and through the other with the same seed is the same for 101 tokens and then parts (Section 7.6), and an activation that an analysis reads under these floats is the explicit path's number, not the one the trained path computed.
Decoding and the cache
Training computes all \(n\) rows of every pattern at once. Writing is different: the model produces one token, appends it, and must produce the next. Done naively, that is a full forward pass over a context one token longer at every step, almost all of which recomputes what the previous step had.
Proposition 3.7.1 (the past does not change). In a causal transformer the vector of position \(i\) at every layer, and so its query, key and value in every head, is a function of the tokens \(1, \dots, i\) only.
Proof. By induction on the layer. The embedding of a position depends on its own token. A layer adds to position \(i\) the outputs (3.2) of its heads, which read positions \(j \le i\) of the layer below, and an MLP applied to position \(i\) alone. ∎
So when token \(n + 1\) arrives, the keys and values of tokens 1 to \(n\) are known and will never change: keep them. A new token then costs one pass of its own through the layers, with one query per head against the stored keys, where recomputing costs a pass for every token so far. The stored keys and values are the KV cache, the fast-weight memory of Section 3.3 made literal.
In the code. The cache is two lists, with one tensor of keys and one of values for each layer, and one method that appends to them. It is KVCache in gpt-pp's model.py.
class KVCache:
"""The keys and values of every layer for the tokens decoded so far.
Under a causal mask the key and value of a token never change once computed, so decoding one more token
needs one new query against the stored keys: linear work per token instead of quadratic.
"""
def __init__(self, n_layer: int):
self.keys: list[Optional[Tensor]] = [None] * n_layer
self.values: list[Optional[Tensor]] = [None] * n_layer
self.length = 0 # tokens whose keys and values are stored
def extend(self, layer: int, k: Tensor, v: Tensor) -> tuple[Tensor, Tensor]:
"""Store the keys and values of the new tokens (B, Hkv, T_new, dh); return those of all tokens."""
if self.keys[layer] is not None:
k = torch.cat((self.keys[layer], k), dim=2)
v = torch.cat((self.values[layer], v), dim=2)
self.keys[layer], self.values[layer] = k, v
return k, v
extend is called by forward_explicit (Section 3.2) between position and share. So a stored key is already normalized and turned by its position, which Proposition 3.7.1 permits because neither depends on a later token; a stored value is the plain projection; and with shared heads the cache holds the Hkv heads before they are copied. The layer then computes queries for the new tokens alone, and scores has one row for each of them and one column for every token so far.
In the code. The model's side is the explicit path of the whole model, which is given only the new tokens when it is given a cache, and the mask it builds for them. It is causal_bias and forward_explicit of GPT in gpt-pp's model.py.
def causal_bias(self, t0: int, t1: int) -> Tensor:
"""What the explicit path adds to the scores of queries at positions [t0, t1) against keys at [0, t1):
-inf where the key is after the query, and the ALiBi term if any."""
if self.cfg.pos == "alibi":
return self.alibi[:, t0:t1, :t1]
return torch.full((t1 - t0, t1), float("-inf"), device=self.embed.weight.device).triu(diagonal=t0 + 1)
...
def forward_explicit(self, idx: Tensor, hook: Optional[Hooks] = None, kv: Optional[KVCache] = None) -> Tensor:
"""The same function with attention written out and every activation handed to `hook`.
With a KV cache, idx holds only the tokens that follow those already in the cache, and the logits
returned are those of the new tokens.
"""
hook = hook or Hooks()
t0 = 0 if kv is None else kv.length
t1 = t0 + idx.size(1)
self.extend_positions(t1)
x = hook("embed", self.embed_tokens(idx, t0))
rot, bias = self.rotation(t0, t1), self.causal_bias(t0, t1)
for layer, block in enumerate(self.blocks):
x = block.forward_explicit(x, rot, bias, hook, layer, kv)
if kv is not None:
kv.length = t1
x = hook("final_norm", self.final_norm(x))
return hook("logits", self.unembed_logits(x))
With a cache, t0 is the number of tokens already stored and t1 - t0 the number of new ones: the rotation is taken at the new tokens' positions, the mask has one row a new token, and kv.length moves once every layer has stored its keys and values. Without one, t0 is zero and this is the whole forward pass of Section 3.2's explicit path. The mask is a tensor of 32-bit floats, \(-\infty\) where a key may not be read and, in the recipe, zero where it may, which is what promotes the scores in Section 3.6.
Quirk. Nothing in KVCache limits its length. The function that writes text, generate in generate.py, keeps it within the context the model was trained at: a full cache is thrown away and rebuilt from the most recent half of the window, so that past the first window a token is predicted from between half a window and a whole one (Section 7.6).
Counted in multiply-adds in the 12 blocks, the token at position 1,024 costs 104 million with the cache and 96.6 billion without, and all the tokens decoded with the cache cost together what the last one alone costs without it. Sharing keys and values among heads reduces the memory bill further.The shape of thought draws the same cache inside a whole forward pass, as ticks that climb its core, with four heads reading them.
layer without the cache with the cache 12 ■ ■ ■ ■ ■ ■ ■ ■ ■ · · · k k k k k k k k ■ · · · : ■ ■ ■ ■ ■ ■ ■ ■ ■ · · · k k k k k k k k ■ · · · 1 ■ ■ ■ ■ ■ ■ ■ ■ ■ · · · k k k k k k k k ■ · · · token 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 ■ computed for token 9 k a key and a value held in the cache · not yet written gpt-pp's shape: 12 layers, 12 heads of width 64, an MLP 3,072 wide, numbers of 2 bytes multiply-adds token 9 token 1,024 token 1,000,000 without the cache 765 M 96.6 G 9.30 × 10¹⁵ with the cache 85.1 M 104 M 18.5 G bytes in the cache 324 KiB 36.0 MiB 34.3 GiB the cache at a million tokens, by key-value heads (the weights: 258 MiB) multi-head 12 grouped 4 grouped 2 multi-query 1 34.3 GiB 11.4 GiB 5.72 GiB 2.86 GiB (the live figure needs JavaScript; it computes everything in the page and loads no data)
Known issue. The counts above are of arithmetic, not of time. On one card the 12-layer model wrote 1,024 tokens at 167 tokens a second with the cache and at 176 without it, the whole context going through forward at every step (Section 7.6). The cause was not profiled; what the code shows is that extend copies a layer's stored keys and values into a new tensor with torch.cat for every token, and that nothing is allocated ahead.
The cache turns a problem of arithmetic into a problem of memory. Every new token has to read every stored key and value of every layer once, and that, not the arithmetic, bounds the speed of writing.
Multi-head attention layers, as used in the Transformer neural sequence model, are a powerful alternative to RNNs for moving information across and between sequences. While training these layers is generally fast and simple, due to parallelizability across the length of the sequence, incremental inference (where such paralleization is impossible) is often slow, due to the memory-bandwidth cost of repeatedly loading the large "keys" and "values" tensors. We propose a variant called multi-query attention, where the keys and values are shared across all of the different attention "heads", greatly reducing the size of these tensors and hence the memory bandwidth requirements of incremental decoding. We verify experimentally that the resulting models can indeed be much faster to decode, and incur only minor quality degradation from the baseline.
—N. Shazeer, "Fast Transformer decoding: one write-head is all you need" (2019).arXiv 1911.02150, abstract; the spelling is the source's. His Tables 2 and 1: 46 against 3.8 microseconds per token in the decoder with shared keys and values, at a log-perplexity of 1.424 against 1.439 and a BLEU of 28.4 against 28.5.
His remedy, multi-query attention, keeps \(h\) query heads and one head of keys and values. Grouped-query attention, four years later, interpolates: each group of query heads has its own key and value head. On the T5-XXL model it kept nearly all the quality of multi-head attention (47.1 against 47.2 averaged over seven tasks) at nearly the speed of multi-query attention (0.28 against 0.24 seconds per sample, where multi-head took 1.51).J. Ainslie, J. Lee-Thorp, M. de Jong, Y. Zemlyanskiy, F. Lebrón and S. Sanghai, "GQA: training generalized multi-query Transformer models from multi-head checkpoints", EMNLP 2023 (arXiv 2305.13245), Table 1, with eight groups. A third step compresses: the multi-head latent attention of DeepSeek caches one vector of small width \(d_c\) per token and layer, of which keys and values are linear maps that at inference are absorbed into the query and output matrices.DeepSeek-AI, "DeepSeek-V2: a strong, economical, and efficient mixture-of-experts language model", 2024 (arXiv 2405.04434), Sections 2.1.2 to 2.1.4 and Table 1. Its Table 9 reports, for the larger of two models, 860.2K cached numbers per token with multi-head attention against 34.6K with the latent; at 16 bits a number and a million tokens that is 1.7 TB against 69 GB.
| attention | numbers cached per token | in the 12-layer model |
|---|---|---|
| multi-head | \(2\, n_h\, d_h\, l\) | 18,432 |
| grouped-query | \(2\, n_g\, d_h\, l\) | 6,144 |
| multi-query | \(2\, d_h\, l\) | 1,536 |
| multi-head latent | \((d_c + d_h^{R})\, l\) |
In the code. Grouped-query and multi-query attention are one method, called on both paths just before the scores. It is CausalSelfAttention.share in gpt-pp's model.py.
def share(self, k: Tensor, v: Tensor) -> tuple[Tensor, Tensor]:
"""Grouped-query attention: each key/value head serves n_head / n_kv_head query heads."""
if self.n_kv_head != self.n_head:
group = self.n_head // self.n_kv_head
k, v = k.repeat_interleave(group, dim=1), v.repeat_interleave(group, dim=1)
return k, v
n_head is the \(n_h\) of the table and n_kv_head its \(n_g\), one for multi-query attention; repeat_interleave hands each head of keys and values to \(n_h/n_g\) neighbouring query heads.
Quirk. The sharing is a copy. Keys and values are repeated up to \(n_h\) heads before the scores, and the enable_gqa argument of PyTorch's fused function is not used. The cache stores the \(n_g\) heads before the copy, since extend runs before share, so the memory of the table is saved and the arithmetic of a step is not. The matrices self.k and self.v have \(n_g d_h\) rows (__init__, Section 3.4), so a model with fewer key and value heads also has fewer parameters; Section 3.8 measures what the sharing costs.
Example 3.7.2 (the cache at a million tokens). The setup: the shape of gpt-pp, multi-head attention, 16-bit floats, one sequence. A token leaves \(2 \times 12 \times 64 \times 12 = 18{,}432\) numbers, 36,864 bytes. At the model's own context of 1,024 tokens the cache is 36.0 MiB. At a million tokens it would be 34.3 GiB, more than a 32 GB card of the kind the model was trained on holds and 136 times the model's own weights at the same precision; it outweighs the weights from 7,339 tokens on. ◁
The caches that hold a million tokens in 2026 are therefore built from three moves, usually together. Store less per token: grouped or latent keys and values. Read less per step: a window, or since 2025 a learned selection of what to read (Section 3.8). And read in parallel: the keys are split into chunks, each attended on its own processor, and the partial results are merged by Proposition 3.6.1 across processors instead of across time.A window of 4,096 tokens is used in every layer of Mistral 7B (arXiv 2310.06825) and in every other layer of Gemma 2 (arXiv 2408.00118). The parallel read is Flash-Decoding (T. Dao, D. Haziza, F. Massa and G. Sizov, Stanford CRFM, 12 October 2023). In Example 3.6.3 the two tiles of the first row are two such chunks, with outputs \((8, 16)/3\) and \((48, 24)/5\) and normalizers 3 and 5, and \(\tfrac38 (8, 16)/3 + \tfrac58 (48, 24)/5 = (7, 5)\).
A windowed cache fails once the text is longer than the window, and the remedy taught something about the softmax.
Deploying Large Language Models (LLMs) in streaming applications such as multi-round dialogue, where long interactions are expected, is urgently needed but poses two major challenges. Firstly, during the decoding stage, caching previous tokens’ Key and Value states (KV) consumes extensive memory. Secondly, popular LLMs cannot generalize to longer texts than the training sequence length. Window attention, where only the most recent KVs are cached, is a natural approach — but we show that it fails when the text length surpasses the cache size. We observe an interesting phenomenon, namely attention sink, that keeping the KV of initial tokens will largely recover the performance of window attention. In this paper, we first demonstrate that the emergence of attention sink is due to the strong attention scores towards initial tokens as a “sink” even if they are not semantically important. Based on the above analysis, we introduce StreamingLLM, an efficient framework that enables LLMs trained with a finite length attention window to generalize to infinite sequence length without any fine-tuning. We show that StreamingLLM can enable Llama-2, MPT, Falcon, and Pythia to perform stable and efficient language modeling with up to 4 million tokens and more. In addition, we discover that adding a placeholder token as a dedicated attention sink during pre-training can further improve streaming deployment. In streaming settings, StreamingLLM outperforms the sliding window recomputation baseline by up to 22.2× speedup. Code and datasets are provided in the link.
—G. Xiao, Y. Tian, B. Chen, S. Han and M. Lewis, "Efficient streaming language models with attention sinks" (2023).ICLR 2024 (arXiv 2309.17453), abstract.
A head that has nothing to read at some position still has to put its unit of weight somewhere, and the large models of that paper put it on the first tokens. gpt-pico has no such head (Section 3.2). The constraint that the weights of a row sum to one is the first thing that the variants below relax.
Variants to 2026, and what the ladder measures
Every variant since 2017 attacks one of three costs of formula (3.2): the softmax, with its scale and its unit sum; the cache, which was Section 3.7; and the read of everything by everything.
The softmax. Its unit sum couples the weights of a row: weight that is not wanted on one key must go to another, which is what a sink absorbs. Later work finds that a sink acts like a bias on a key, a score added for every query whatever its content (the prior weight of Proposition 3.3.1, in our reading), and that sinks do not form in models of up to a billion parameters once the normalization is removed.X. Gu and co-authors, "When attention sink emerges in language models: an empirical view", ICLR 2025 (arXiv 2410.10781). Several proposals change the function itself. Differential attention subtracts two patterns computed by the two halves of a head, \(\bigl(\mathrm{softmax}(Q_1 K_1^{\top}/\sqrt{d}) - \lambda\, \mathrm{softmax}(Q_2 K_2^{\top}/\sqrt{d})\bigr) V\) with a learned \(\lambda\), so that entries can be negative and what both halves see cancels. Sigmoid attention drops the normalization: \(A_{ij} = \sigma(q_i^{\top} k_j + b)\) with \(b = -\log n\), which keeps the sum of a row of order one at initialization. Sparse normalizers replace the exponential map by a projection onto the simplex and return exact zeros.T. Ye and co-authors, "Differential Transformer", ICLR 2025 (arXiv 2410.05258), whose authors report matching a transformer with about 65% of its parameters or of its training tokens; J. Ramapuram and co-authors, "Theory, analysis, and best practices for sigmoid self-attention", 2024 (arXiv 2409.04431); A. F. T. Martins and R. F. Astudillo, "From softmax to sparsemax", 2016 (arXiv 1602.02068). Each reports gains in its own paper; we found no independent replication at scale, and no released frontier model that documents using one of them.
The read of everything by everything. A trained head puts most of the weight of a row on few keys, and keeping only the \(k\) largest scores of every row can cost nothing: a six-layer language model on WikiText-103 scored a perplexity of 30.51 reading the top 64 of 1,024 keys and 30.96 reading all of them.A. Gupta, G. Dar, S. Goodman, D. Ciprut and J. Berant, "Memory-efficient Transformers via top-k attention", 2021 (arXiv 2106.06899). The approximations of 2020 chose what to drop before seeing the scores, or blurred all of them. Top-$$k$$ drops after seeing them, which is accurate and saves no arithmetic. The sparse attention of 2025 and 2026 closes the gap with a second, much cheaper scorer that predicts where the weight will be, followed by exact attention on what it selects. MoBA scores the mean of the keys of each block of 512 tokens against the query and reads the three best, and always its own; Native Sparse Attention adds a compressed token per block and a sliding window. The sparse attention of DeepSeek scores every earlier token with a small indexer, \(I_{t,s} = \sum_j w_{t,j}\, \mathrm{ReLU}(q^{I}_{t,j} \cdot k^{I}_{s})\) over a few heads in 8-bit arithmetic, keeps the best 2,048 and trains the indexer to match the main model's own attention, so that the main attention falls from \(O(L^2)\) to \(O(Lk)\) for a context of \(L\) tokens. Mixture-of-top-\(k\) (Section 3.3) belongs to this family.E. Lu and co-authors, "MoBA: mixture of block attention for long-context LLMs", 2025 (arXiv 2502.13189); J. Yuan, H. Gao, D. Dai and co-authors, "Native sparse attention: hardware-aligned and natively trainable sparse attention", ACL 2025 (arXiv 2502.11089); DeepSeek-AI, "DeepSeek-V3.2: pushing the frontier of open large language models", 2025 (arXiv 2512.02556), Sections 2.1 and 2.3.
These selectors are trained into the model, with kernels designed beside them, and they are in use: MoBA's authors report serving long-context requests with it, and Native Sparse Attention reports reading the equivalent of 5,632 tokens per step at a context of 65,536.Native Sparse Attention, Table 4. A preprint of 2026 reports attention work per token reduced 28-fold at a million tokens: X. Lai and co-authors, "MiniMax sparse attention" (arXiv 2606.13392), of which only the abstract was read. So the verdict of Section 3.6 needs a correction. Approximating the attention matrix lost; selecting what to read and then attending exactly, with a trained selector and a kernel designed with it, is how several open models serve million-token contexts in 2026, beside hybrids that compress the past into a state.
The selection rules can be compared on the duplicate-token head of gpt-pico, on the first 64 tokens of a held-out story. For each rule, count the keys a query reads and the share of the original head's attention mass they hold.
one attention matrix of gpt-pico (block 3, head 4, a held-out story of 64 tokens) and what each scheme would let a query read of it: keys read, and the share of the attention mass they hold scheme year, paper setting keys mass full causal attention 2017 Vaswani et al. 33.0 100 % ██████████ sliding window 2015 Luong et al. window of 8 7.7 55 % ██████ strided 2019 Sparse Transformer stride 8 11.2 62 % ██████ block-sparse 2019 Sparse Transformer blocks of 8 8.1 50 % █████ global tokens 2020 Longformer 2 global + window of 6 7.7 57 % ██████ hash buckets 2020 Reformer 4 buckets 8.8 43 % ████ top-k keys 2021 Gupta et al. k = 8 7.7 84 % ████████ mixture of top-k 2026 Wen et al. m = k = 8 12.9 50 % █████ keys: read per query, on average over the 63 tokens of the story. For the mixture of top-k: the 8 landmark summaries and the keys of its landmark that lie before the query, 4.9 of 8. The summaries are not entries of the matrix: mass kept cannot credit what they carry. The matrix was trained with full attention; nothing is retrained. (the live figure needs JavaScript; it loads about 2.3 MB, the weights of gpt-pico)
Give each query about eight keys and it matters a great deal which eight: the last eight hold 55% of this head's attention, and the eight it would itself rank highest 84%. The mixture of top-\(k\), at \(m = k = 8\), reads 12.9 pairs per query and keeps 50% of the mass, and that is not a verdict on the method, for two reasons. Its paper sets no causal mask, so on a causal matrix 3.1 of a landmark's eight keys lie after the query on average and cannot be read; and the eight landmark summaries are counted as pairs read and credited with no mass, although they are a compressed view of the whole context. This measures attention mass kept in a model trained with full attention, not the loss of a model trained with the mask; nothing was retrained.
What the ladder measures. The ladder varies attention in two ways, each a single change to the 8-layer model trained on the same 50M tokens, one seed each. With the scores left unnormalized, as \(q^{\top} k/\sqrt{d_k}\), the held-out loss is 4.074 nats a token against 4.045 for the recipe: worse by 0.029, and by 0.032 in a second seed of both runs. That is the cost at 50M tokens, and in this one pair of runs it was still shrinking when they ended: at the same number of tokens the model with unnormalized scores trailed the recipe by 0.069 nats at 20M tokens, 0.045 at 30M and 0.035 at 40M, whereas the costs of sharing keys and values, reported below, had leveled by then (0.031 at 40M and 0.030 at 50M with two key and value heads, 0.051 and 0.050 with one). With a gain learned by each head, which in this run starts from the recipe's 12 where the probe of Example 3.4.7 started from \(\sqrt{d_k}\), it is 4.047, not distinguishable from the recipe in one run each: the further 0.004 to 0.005 of Example 3.4.7 did not repeat. In the cumulative ladder from the 2019 recipe, at 100M tokens and two seeds a rung, query-key normalization is the fifth change: the loss falls from 4.026 to 4.010 in one seed and from 4.020 to 4.013 in the other, where the two seeds of a rung differ by 0.006 and 0.003. The step has the same sign in both seeds and is not much larger than their spread. Sharing keys and values among the eight heads, at the same 50M tokens, gives 4.048 with four key and value heads, 4.075 with two and 4.096 with one, for caches of 4,096, 2,048 and 1,024 numbers per token in place of 8,192. These runs also have fewer parameters, because \(W_K\) and \(W_V\) lose rows with the key and value heads (Section 3.7): a half, a quarter and an eighth of their rows remain. Sharing between pairs of heads is free at this size and budget, 0.003 being inside the spread of two seeds. Below that it costs: 0.030 with two, as much as leaving the scores unnormalized, and about 0.05 with one.
The ladder does not train the replacements of the softmax or the sparse selections; for those the evidence is the papers' own.