From the alignment problem in machine translation, through Bahdanau's
additive scoring and Luong's dot-product simplification, to a rigorous
derivation of Query, Key, and Value — then outward into information
retrieval, kernel regression, expressive power, and scaling laws.
◉ This page is independent of the Transformers masterclass. It treats attention as a mathematical object in its own right — its history, its derivation, its theoretical guarantees and limits — rather than as one component of a larger architecture.
// the encoder bottleneck · statistical MT alignment · why a fixed vector fails
Before attention existed, sequence-to-sequence models faced a problem with no good solution: how does a decoder know which part of a long input is relevant at each step of generation? The answer attention provides is so foundational that it is easy to forget it was once an open research question with a specific, narrow origin — machine translation.
The Encoder-Decoder Bottleneck
Sutskever et al. (2014) encoded an entire source sentence into a single fixed-length vector \(\mathbf{c}\) — the final hidden state of an RNN — and decoded the target sentence entirely from \(\mathbf{c}\):
Vanilla Encoder-DecoderPre-Attention
\[\mathbf{c} = \mathbf{h}_{T_x} \quad\text{(final encoder hidden state — ALL information must fit here)}\]
\[p(y_i \mid y_{<i}, \mathbf{c}) = g(y_{i-1}, s_{i-1}, \mathbf{c}) \quad\text{(every decoder step reuses the SAME }\mathbf{c}\text{)}\]
Every target word, regardless of which source words it actually corresponds to, is generated by conditioning on the identical compressed vector c. A 50-word sentence and a 5-word sentence are both squeezed into the same fixed-size c — translation quality degrades sharply as source length grows (Cho et al. 2014 measured this directly).
Alignment in Classical Statistical MT
Long before neural networks, statistical machine translation (Brown et al.'s IBM Models, 1990s) had already formalized the idea that translation requires a latent alignment — a mapping from each target word to the source word(s) it translates:
IBM Model Alignment — Classical FormulationStatistical MT
\[P(\mathbf{y}\mid\mathbf{x}) = \sum_{\mathbf{a}} P(\mathbf{y},\mathbf{a}\mid\mathbf{x}), \quad a_i \in \{1,\ldots,T_x\} \text{ — which source word does } y_i \text{ align to?}\]
a is the alignment: a_i = j means target word i is generated from source word j. This sum over all possible (exponentially many) alignments is intractable in general — IBM Models made restrictive independence assumptions to make it tractable. Neural attention would later replace this discrete, hard latent variable with a continuous, differentiable, soft one.
⊙
The Reframing That Changed Everything
Bahdanau, Cho & Bengio (2014) asked: what if the alignment \(a_i\) — instead of being a discrete latent variable summed over combinatorially — were replaced by a continuous probability distribution over source positions, predicted by a small neural network and trained end-to-end via backpropagation? This single reframing — hard discrete alignment → soft differentiable alignment — is the entire conceptual leap that attention represents. Everything in this page is a refinement of that one idea.
2
1st Attention
Bahdanau Attention — Additive Alignment
// the original 2014 mechanism · learned alignment as a small MLP · context vector
Bahdanau's mechanism (often called "additive" or "concat" attention) was the first working neural attention. It computes a soft alignment score using a small feedforward network, then takes a weighted average of encoder states as the context.
Bahdanau Attention — Full SpecificationAdditive / Concat
\[e_{ij} = \mathbf{v}_a^T\tanh(\mathbf{W}_a\mathbf{s}_{i-1} + \mathbf{U}_a\mathbf{h}_j) \quad\text{(alignment score: decoder state }i\text{, encoder state }j\text{)}\]
\[\alpha_{ij} = \frac{\exp(e_{ij})}{\sum_{k=1}^{T_x}\exp(e_{ik})} \quad\text{(softmax normalization over source positions)}\]
\[\mathbf{c}_i = \sum_{j=1}^{T_x}\alpha_{ij}\mathbf{h}_j \quad\text{(context vector — weighted average of ALL encoder states)}\]
s_{i-1} is the decoder's previous hidden state (what it's "looking for"). h_j is the j-th encoder hidden state (what's "available"). W_a, U_a, v_a are learned matrices/vector — together they form a single-hidden-layer MLP scoring function. Every decoder step now gets its OWN context vector c_i, computed freshly from the entire source — solving the fixed-vector bottleneck from §01.
Why "Additive"?
The score \(e_{ij}\) sums the two projected vectors \(\mathbf{W}_a\mathbf{s}_{i-1}\) and \(\mathbf{U}_a\mathbf{h}_j\) before applying a nonlinearity — hence "additive." This is structurally identical to a one-hidden-layer neural network with a single output unit, applied to the concatenation \([\mathbf{s}_{i-1};\mathbf{h}_j]\):
This is why Luong (2015) later called this variant "concat" attention — it is mathematically the same operation as stacking [W_a U_a] into one matrix and applying it to the concatenated [s;h] vector. The score function is a learned, trainable similarity measure — NOT a fixed dot product. This flexibility comes at a cost: an extra weight matrix and a nonlinearity, evaluated T_x times per decoder step.
Two Proto-Roles Already Present
Look closely at the score function: \(\mathbf{s}_{i-1}\) plays the role of what the decoder is searching for, while \(\mathbf{h}_j\) plays a dual role — it is simultaneously used to compute the matching score (inside \(\tanh\)) AND used directly as the content being aggregated in \(\mathbf{c}_i=\sum_j\alpha_{ij}\mathbf{h}_j\). This conflation of "matching role" and "content role" into one vector \(\mathbf{h}_j\) is precisely the inefficiency that the Query-Key-Value framework (§04) will resolve.
3
Simplification
Dot-Product Attention
// Luong's multiplicative scoring · three score variants · the efficiency argument
One year after Bahdanau, Luong, Pham & Manning (2015) asked a simple question: does the score function need a learned nonlinear MLP at all? Their answer — multiplicative (dot-product) scoring — removed the nonlinearity and the extra hidden layer, replacing both with a single matrix multiplication.
Luong's Three Score FunctionsMultiplicative
\[\text{dot:}\quad e_{ij} = \mathbf{s}_{i-1}^T\mathbf{h}_j\]
\[\text{general:}\quad e_{ij} = \mathbf{s}_{i-1}^T\mathbf{W}_a\mathbf{h}_j\]
\[\text{concat:}\quad e_{ij} = \mathbf{v}_a^T\tanh(\mathbf{W}_a[\mathbf{s}_{i-1};\mathbf{h}_j]) \quad\text{(Bahdanau's form, included for comparison)}\]
"dot" requires NO learned parameters in the score itself — pure geometric similarity between vectors. "general" inserts one learned bilinear matrix W_a between the two vectors, giving a learnable notion of similarity while remaining a single matrix multiply (no nonlinearity, no extra hidden layer). This "general" form is the direct ancestor of the QKV framework derived in §04.
The Efficiency Argument
Score Function
Parameters
Compute per (i,j) pair
GPU-Friendly?
Bahdanau (concat)
\(\mathbf{W}_a, \mathbf{U}_a, \mathbf{v}_a\)
2 matmuls + tanh + 1 matmul
Sequential-ish, awkward to batch across \(j\)
Luong general
\(\mathbf{W}_a\) only
2 matmuls (\(\mathbf{W}_a\mathbf{h}_j\), then dot with \(\mathbf{s}\))
Batches as one big matmul: \(\mathbf{S}\mathbf{W}_a\mathbf{H}^T\)
Luong dot
none
1 matmul: \(\mathbf{S}\mathbf{H}^T\)
Maximally GPU-friendly
The crucial practical insight: computing all \(T_x\) scores for a single query \(\mathbf{s}_{i-1}\) simultaneously is just one matrix-vector product \(\mathbf{H}\mathbf{s}_{i-1}\) (where \(\mathbf{H}\) stacks all \(\mathbf{h}_j\) as rows) — instead of \(T_x\) separate evaluations of a tanh-MLP. Across a whole batch of queries, this becomes a single matrix-matrix product. This is precisely the operation that will become \(\mathbf{Q}\mathbf{K}^T\) in §04 and beyond.
·
Why Dot Product Measures Similarity
\(\mathbf{a}^T\mathbf{b} = \|\mathbf{a}\|\|\mathbf{b}\|\cos\theta\) — the dot product is large precisely when two vectors point in similar directions and have large magnitude. If embeddings are trained so that "semantically related" vectors point in similar directions, dot product becomes a learned, geometric notion of relevance — with zero extra parameters beyond the embeddings themselves.
4
The Core Result
From Alignment Scores to Q, K, V — The Rigorous Derivation
// the derivation most articles skip · low-rank factorization · decoupling match from content
Almost every introduction to attention simply asserts that there are three projections — Query, Key, Value — and moves on. This section derives why exactly three objects are needed, and why each one is necessary, starting from the "general" bilinear score of §03.
W is a single learned matrix of size d_s × d_h. This already works and trains fine — but it has a hidden inefficiency: W must encode an entire d_s × d_h similarity transform as one monolithic object, and there is no way to separately control "how to search" versus "what to retrieve."
Step 2 — Factor W via Low-Rank Decomposition
// Any matrix W admits a (possibly low-rank) factorization W = Wq^T Wk
1
By the SVD (covered in the SVD masterclass), any \(\mathbf{W}\in\mathbb{R}^{d_s\times d_h}\) factors exactly as \(\mathbf{W}=\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^T\). Truncating to the top \(d_k\) singular values gives a rank-\(d_k\) approximation:
\[\mathbf{W} \approx \mathbf{U}_{d_k}\boldsymbol{\Sigma}_{d_k}\mathbf{V}_{d_k}^T = \underbrace{(\mathbf{U}_{d_k}\boldsymbol{\Sigma}_{d_k}^{1/2})}_{\mathbf{W}_Q^T}\underbrace{(\boldsymbol{\Sigma}_{d_k}^{1/2}\mathbf{V}_{d_k}^T)}_{\mathbf{W}_K}\]
2
Substitute back into the score:
\[e_{ij} = \mathbf{s}_i^T\mathbf{W}\mathbf{h}_j \approx \mathbf{s}_i^T\mathbf{W}_Q^T\mathbf{W}_K\mathbf{h}_j = (\mathbf{W}_Q\mathbf{s}_i)^T(\mathbf{W}_K\mathbf{h}_j)\]
3
Define \(\mathbf{q}_i \triangleq \mathbf{W}_Q\mathbf{s}_i\) and \(\mathbf{k}_j \triangleq \mathbf{W}_K\mathbf{h}_j\). The score becomes a pure dot product:
\[\boxed{e_{ij} = \mathbf{q}_i^T\mathbf{k}_j}\]
This is not an approximation we're stuck with — instead of deriving Wq, Wk by SVD-factoring a pre-existing W, we simply LEARN Wq and Wk directly via gradient descent from the start. The SVD argument proves that this parametrization loses no expressive power versus a full bilinear W (for d_k ≥ rank(W)), while typically using FAR fewer parameters: 2·d·d_k vs d_s·d_h. ∎
Step 3 — Why a THIRD Projection Is Needed
We've now derived Query and Key from the score function alone. But the score function only tells us how much to attend to position \(j\) — it says nothing about what content gets aggregated. In Bahdanau and Luong, the content is simply the raw \(\mathbf{h}_j\):
The Remaining ConflationThe Problem
\[\mathbf{c}_i = \sum_j\alpha_{ij}\mathbf{h}_j \quad\text{— same } \mathbf{h}_j \text{ used for matching (via } \mathbf{k}_j=\mathbf{W}_K\mathbf{h}_j\text{) AND for content}\]
Forcing the same h_j to serve double duty — as the basis for the Key projection AND as the raw content aggregated into the context — needlessly couples two different jobs: "what makes me a good match" and "what information I contribute when matched." There's no mathematical reason these should be the same subspace of h_j.
// Introducing an independent content projection
4
Decouple by introducing a third learned projection \(\mathbf{W}_V\), applied to \(\mathbf{h}_j\) only for the purpose of content aggregation:
\[\mathbf{v}_j \triangleq \mathbf{W}_V\mathbf{h}_j\]
5
Replace the context vector definition:
\[\mathbf{c}_i = \sum_j\alpha_{ij}\mathbf{v}_j = \sum_j\alpha_{ij}(\mathbf{W}_V\mathbf{h}_j)\]
Now the "what makes a good match" subspace (Key, via W_K) and the "what content to deliver" subspace (Value, via W_V) are free to be entirely different linear transforms of h_j — learned independently, optimized independently by gradient descent, subject to no shared-parameter constraint whatsoever. ∎
The Complete QKV Theorem
Starting from a single learned bilinear alignment score \(\mathbf{s}^T\mathbf{W}\mathbf{h}\), (1) low-rank factorization of \(\mathbf{W}\) produces two independently-learned projections \(\mathbf{W}_Q,\mathbf{W}_K\) whose dot product reconstructs the score with no loss of expressive power (for sufficient rank), and (2) decoupling the content-aggregation vector from the key-matching vector via a third projection \(\mathbf{W}_V\) removes an unnecessary shared-parameter constraint. The result — \(\mathbf{q}=\mathbf{W}_Q\mathbf{s}\), \(\mathbf{k}=\mathbf{W}_K\mathbf{h}\), \(\mathbf{v}=\mathbf{W}_V\mathbf{h}\), \(\text{score}=\mathbf{q}^T\mathbf{k}\), \(\text{output}=\sum\text{softmax}(\text{score})\cdot\mathbf{v}\) — is not an arbitrary architectural choice. It is the unique minimal generalization of Bahdanau/Luong attention that (a) preserves the expressive power of a full bilinear score and (b) removes every avoidable coupling between matching and content.
5
Generalization
Self-Attention — Q = K = V From One Sequence
// cross-attention vs self-attention · removing the recurrent decoder · parallelization
Everything in §01–§04 was cross-attention: a decoder state \(\mathbf{s}_i\) (from one sequence) attends to encoder states \(\mathbf{h}_j\) (from a different sequence). Self-attention makes a single, almost trivial-seeming change: let the query source and the key/value source be the same sequence.
Every token in X simultaneously plays the role of query (it asks "what's relevant to me?"), key (it advertises "here's what I contain"), and value (it offers "here's what I'll contribute"). The SAME projections WQ, WK, WV from §04 apply — only the source of the input sequence changed from (decoder, encoder) to (X, X).
Why This Seemingly Small Change Is Revolutionary
Aspect
Cross-Attention (Bahdanau/Luong)
Self-Attention
Query source
Decoder RNN hidden state \(\mathbf{s}_{i-1}\)
Token \(i\) of the SAME sequence \(\mathbf{X}\)
Requires recurrence?
Yes — \(\mathbf{s}_{i-1}\) depends sequentially on \(\mathbf{s}_{i-2}\), etc.
No — every \(\mathbf{q}_i\) computed independently and in parallel
Captures within-sequence structure?
No — only source↔target relations
Yes — directly models token↔token relations within one sequence
Path length between any two tokens
N/A (different sequences)
\(O(1)\) — direct attention edge, no recurrent chain
⇄
Historical Precursors
Self-attention did not appear fully-formed in "Attention Is All You Need" (2017). Cheng, Dong & Lapata (2016) proposed "intra-attention" inside LSTMs to let a token attend to its own sequence history. Parikh et al. (2016) used "decomposable attention" for natural language inference by attending between two sentences with the same mechanism. Vaswani et al.'s contribution was recognizing that self-attention, stacked and combined with positional encoding, could entirely replace the recurrent backbone — not merely augment it.
The dot-product score \(\mathbf{q}^T\mathbf{k}\) from §04 has a subtle numerical problem that only appears at scale: as the dimension \(d_k\) grows, the variance of the score grows with it, eventually breaking the softmax.
// Deriving the necessity of the 1/√d_k scaling factor
1
Assume \(\mathbf{q},\mathbf{k}\in\mathbb{R}^{d_k}\) have independent components with mean 0, variance 1 (a reasonable assumption near initialization). The dot product is a sum of \(d_k\) independent products:
\[\mathbf{q}^T\mathbf{k} = \sum_{i=1}^{d_k}q_ik_i, \quad \mathbb{E}[q_ik_i]=0,\;\;\text{Var}(q_ik_i)=\mathbb{E}[q_i^2]\mathbb{E}[k_i^2]=1\]
2
Since the \(d_k\) terms are independent, variances add:
\[\text{Var}(\mathbf{q}^T\mathbf{k}) = \sum_{i=1}^{d_k}\text{Var}(q_ik_i) = d_k\]
Standard deviation grows as √d_k. For d_k=512 (a typical model dimension): std ≈ 22.6 — scores routinely reach ±60 or more.
3
Examine softmax behavior at this scale. If one score is even moderately larger than the rest (say by 10+ in raw units), softmax saturates:
\[\text{softmax}(60, 2, -3, \ldots) \approx (1.0, \approx0, \approx0,\ldots)\]
The gradient of a saturated softmax is ≈ 0 everywhere except the (already-dominant) max — learning stalls. This is precisely the vanishing gradient problem applied to the attention score itself.
4
Divide scores by \(\sqrt{d_k}\) to restore unit variance:
\[\text{Var}\!\left(\frac{\mathbf{q}^T\mathbf{k}}{\sqrt{d_k}}\right) = \frac{d_k}{d_k} = 1 \quad\text{(independent of }d_k\text{!)}\]
\[\boxed{\text{Attention}(\mathbf{Q},\mathbf{K},\mathbf{V}) = \text{softmax}\!\left(\frac{\mathbf{QK}^T}{\sqrt{d_k}}\right)\mathbf{V}}\]
This is exactly the "scaled dot-product attention" formula from Vaswani et al. — now derived from a one-line variance computation rather than asserted. ∎
σ²
Connection to §03
Luong's plain "dot" score (§03) has exactly this unscaled-variance problem and was empirically found to underperform the "general" (learned bilinear) variant on large hidden sizes — Luong's own paper noted dot-product attention worked better only for smaller dimensions. The \(1/\sqrt{d_k}\) fix, discovered three years later, is precisely what was needed to make pure dot-product scoring competitive at any dimension.
7
Capacity
Multi-Head Attention
// multiple representation subspaces · why concatenation beats one large head
A single attention head computes one weighted average per query — one notion of "relevance." Multi-head attention runs several attention computations in parallel, each in a different learned subspace, then combines the results.
Splitting d_model into h heads of size d_model/h costs roughly the SAME total compute as one head of the full size d_model — the FLOPs for the QKᵀ step scale as h·(n²·d_model/h) = n²·d_model, independent of h. Multi-head attention is "free" in this sense — you're not paying extra for the extra flexibility.
Why Splitting Into Subspaces Increases Expressiveness
⊕
One Large Head ≠ Many Small Heads
A single attention head produces exactly one attention distribution \(\boldsymbol{\alpha}_i\) per query — one weighting over all keys. Every output dimension of that head is forced to use the same weighting. Multiple heads break this constraint: head 1 might place high weight on syntactically adjacent tokens, head 2 on the most semantically similar token regardless of distance, head 3 on a fixed positional offset. Concatenating these gives an output that simultaneously reflects several different attention distributions — something a single softmax fundamentally cannot produce, no matter how large \(d_k\) is made.
Empirical Specialization
Interpretability studies (Voita et al. 2019, Clark et al. 2019) directly confirm the theoretical motivation: trained heads specialize. Some heads attend almost exclusively to the previous token (positional heads). Others track long-range coreference (pronoun → antecedent). Others attend broadly and seem to compute something closer to a bag-of-words average. This division of labor across heads is not designed by hand — it emerges purely from gradient descent exploiting the architectural freedom that multi-head splitting provides.
The most intuitive way to understand attention is as a differentiable, soft generalization of a database lookup — every step of the standard "query a database" workflow has a direct attention analogue.
Hard / Discrete Lookup
A SQL query retrieves exactly the row(s) whose key matches the query exactly. The result is sharp: either a record is returned, or it isn't. There is no gradient — a tiny change to the query either returns the same row or a completely different one.
Soft / Differentiable Lookup (Attention)
Attention retrieves a weighted blend of every value, where the weight reflects how well each key matches the query. A small change to the query smoothly reweights the blend — the entire operation is differentiable end-to-end, which is exactly why it can be trained with backpropagation.
The softmax output α is literally a categorical probability distribution over "which value to retrieve." The attention output is the EXPECTED VALUE under this distribution — not a sample from it, but the exact expectation (computed in closed form, since the support is finite and known). This view directly connects attention to importance sampling and to the REINFORCE-style hard-attention mechanisms (Xu et al. 2015) that preceded soft attention in image captioning — hard attention samples i ~ Cat(α); soft attention takes the expectation exactly.
Lineage: Memory-Augmented Networks
Attention's "content-addressable" framing has a direct lineage through memory-augmented neural networks that predate or coincide with Bahdanau's mechanism: Memory Networks (Weston et al. 2014) and Neural Turing Machines (Graves et al. 2014) both equip a network with an external memory bank addressed by content similarity rather than a fixed index — exactly the query-key matching at the heart of attention. The key historical difference: NTMs used attention to read/write an explicit, persistent external memory across many time steps; Transformer self-attention uses the same content-addressing mechanism but treats the current sequence itself as the memory, recomputed fresh at every layer.
A second, equally rigorous lens reveals attention to be a textbook statistical estimator in disguise: the Nadaraya-Watson kernel regression estimator from classical nonparametric statistics (1964) — six decades before "Attention Is All You Need."
\[\hat{y}(\mathbf{q}) = \frac{\sum_{i=1}^n K(\mathbf{q},\mathbf{k}_i)\,y_i}{\sum_{j=1}^n K(\mathbf{q},\mathbf{k}_j)} \quad\text{(predict } y \text{ at query point } \mathbf{q}\text{, given training pairs }(\mathbf{k}_i,y_i)\text{)}\]
K is any kernel function measuring similarity between q and each training input k_i — classically a Gaussian/RBF kernel K(q,k)=exp(−‖q−k‖²/2σ²). This is the original "local averaging" nonparametric regression estimator: predict by averaging nearby training labels, weighted by similarity.
The Exact Equivalence
// Proving attention IS Nadaraya-Watson with an exponential kernel
Substitute into the Nadaraya-Watson formula, with \(y_i \to \mathbf{v}_i\):
\[\hat{\mathbf{y}}(\mathbf{q}) = \frac{\sum_i\exp(\mathbf{q}^T\mathbf{k}_i/\sqrt{d_k})\,\mathbf{v}_i}{\sum_j\exp(\mathbf{q}^T\mathbf{k}_j/\sqrt{d_k})}\]
3
This is, term for term, the softmax-weighted average:
\[= \sum_i\text{softmax}\!\left(\frac{\mathbf{q}^T\mathbf{k}_i}{\sqrt{d_k}}\right)\mathbf{v}_i = \text{Attention}(\mathbf{q},\mathbf{K},\mathbf{V})\]
Attention IS Nadaraya-Watson kernel regression, with the kernel given by the exponentiated, scaled dot product, and the "training set" given by the key-value pairs presently in context. No approximation, no analogy — an exact algebraic identity. ∎
Every attention layer performs nonparametric kernel regression at inference time, where the "training data" is the set of key-value pairs in the current context, and the kernel is the (scaled, exponentiated) dot product between learned Query and Key projections. The kernel itself — i.e., which notion of similarity is used — is learned via \(\mathbf{W}_Q,\mathbf{W}_K\), rather than fixed in advance (as a Gaussian RBF kernel's bandwidth would be in classical statistics). This is precisely the "kernel trick" of SVMs and Gaussian Processes, except the kernel itself is now parametrized and trained end to end.
Why This View Explains In-Context Learning
↻
In-Context Learning as Live Kernel Regression
When a large language model performs "in-context learning" — adapting its behavior based on examples placed in the prompt, with no parameter updates — the kernel regression view gives a precise mechanistic explanation: the few-shot examples in the prompt become the key-value training pairs \((\mathbf{k}_i,\mathbf{v}_i)\), and the model's prediction for a new query is literally a kernel-weighted average over those examples, computed fresh at each forward pass. This reframes "in-context learning" not as a mysterious emergent ability but as Nadaraya-Watson regression performed live, once per query, using whatever examples happen to be in the context window.
Attention is remarkably powerful, but it has a precise, provable limitation that is rarely stated explicitly — and an equally precise theoretical ceiling on what it (plus depth) can achieve.
The Convex-Hull Limitation — A Theorem
Theorem: Attention Output Lies in the Convex Hull of Values
For any query \(\mathbf{q}\) and any set of values \(\{\mathbf{v}_1,\ldots,\mathbf{v}_n\}\), the attention output \(\sum_i\alpha_i\mathbf{v}_i\) satisfies \(\sum_i\alpha_i=1\) and \(\alpha_i\geq0\) (softmax guarantees both). Therefore the output is, by definition, a convex combination of the values — it lies in \(\text{conv}(\mathbf{v}_1,\ldots,\mathbf{v}_n)\), and can never lie outside this convex hull, no matter how the query is chosen.
This is a genuine limitation: a single attention operation cannot extrapolate — it can only interpolate among the values already present. Any function requiring an output beyond the span of available values (e.g., doubling a value, or producing something qualitatively new) cannot be computed by attention alone. This is precisely why every practical architecture pairs attention with position-wise feedforward layers (which CAN extrapolate, having no such convexity constraint) — attention mixes information across positions; the FFN transforms it.
Universal Approximation — With Enough Depth
Universal Approximation for TransformersYun et al. 2020
\[\text{Transformers (attention + FFN, stacked)} \text{ can approximate any continuous seq-to-seq function } f:\mathcal{X}^n\to\mathcal{Y}^n\]
\[\text{to arbitrary precision } \epsilon, \text{ on any compact domain, given sufficient depth and width.}\]
The proof strategy: attention layers are used to perform a "contextual shift" that effectively implements a lookup table / quantization of the input, and FFN layers perform the necessary nonlinear value mapping per token — together they can approximate any continuous function on compact sets, in the same spirit as the classical universal approximation theorem for single-hidden-layer networks (covered in the Neural Networks masterclass), but for sequence-to-sequence maps.
Turing Completeness
∞
Pérez, Marinković & Barceló (2019)
A Transformer with arbitrary numerical precision and unbounded recurrence (i.e., allowed to feed its own output back as input indefinitely, as in autoregressive generation) is Turing complete — it can simulate any Turing machine. This result requires idealized (infinite-precision) arithmetic and unbounded generation length; finite-precision, fixed-depth Transformers are formally weaker (closer to bounded-depth threshold circuits), which is an active area of theoretical research (e.g., results placing fixed-depth Transformers within the complexity class \(\mathsf{TC}^0\)).
Dong et al. proved that pure self-attention (no residual connections, no FFN) applied repeatedly causes every token's representation to collapse toward the SAME vector — all positional/contextual distinctions wash out doubly-exponentially fast with depth. This is precisely why residual connections (x + Attention(x)) are not a minor implementation detail but a mathematical necessity for deep attention stacks: they prevent the rank-collapse degeneracy by ensuring each layer's output retains a component equal to its input.
11
Computation
Scaling Laws of Attention
// the quadratic cost · the crossover point · KV-cache memory · entropy dilution at long range
Attention's mathematical elegance comes with a specific computational price tag — one that scales in a precisely characterizable way with sequence length and model dimension, and that has shaped years of architecture research.
The Quadratic-vs-Quadratic Crossover
FLOPs Breakdown — Attention vs ProjectionsCompute Scaling
\[\text{Attention scores + weighted sum (}\mathbf{QK}^T\text{, then }\cdot\mathbf{V}\text{): } O(n^2d)\]
\[\text{Q,K,V projections + output projection: } O(nd^2)\]
\[\text{Crossover: attention dominates when } n > d; \text{ projections dominate when } n < d\]
For typical model dimensions (d ≈ 1,000–10,000) and typical sequence lengths in earlier Transformers (n ≈ 512), the projection cost O(nd²) often dominated. As context lengths have grown into the tens of thousands or beyond, the O(n²d) attention term increasingly dominates — this single crossover is the central motivation behind the entire research program of long-context / efficient attention (sparse attention, linear attention, Flash Attention's IO-optimization).
KV-Cache Memory at Inference
Inference-Time Memory ScalingKV-Cache
\[\text{KV-cache size per layer} = 2 \times n \times d_k \times h \times (\text{bytes per value})\]
\[\text{Total across } L \text{ layers: } O(L\cdot n\cdot d_{\text{model}}) \quad\text{(grows LINEARLY in context length } n\text{, not quadratically)}\]
During autoregressive generation, every previously-computed Key and Value vector must be cached and reused (recomputing them from scratch at every new token would be O(n²) wasteful). This KV-cache, not the attention computation itself, is usually the dominant practical memory bottleneck for long-context inference — it is why multi-query attention (sharing K,V across heads) and grouped-query attention exist: they shrink this linear-in-n memory cost by a constant factor (the number of heads), trading a small amount of model quality for substantially reduced cache size.
Entropy Dilution at Long Range
↓
Attention Doesn't Scale Its Focus for Free
The softmax in §06 was variance-stabilized independent of \(n\) — but as the number of competing keys \(n\) grows, even a well-conditioned distribution \(\boldsymbol{\alpha}\) tends to spread its probability mass more thinly (higher entropy) unless the scores actively sharpen to compensate. Empirically, attention distributions over very long contexts often become diffuse — many keys receive small but non-negligible weight — which is one contributing factor to the "lost in the middle" phenomenon observed in long-context language models, where information placed in the middle of a long prompt is attended to less reliably than information at the very start or end.
Sub-Quadratic Alternatives — A Brief Map
Approach
Complexity
Core Idea
Sparse attention (Longformer, BigBird)
\(O(n\cdot k)\)
Each query attends to only \(k\ll n\) keys (local window + a few global tokens)
Linear attention (Performer, Linear Transformers)
\(O(nd^2)\)
Approximate the softmax kernel with a finite-dimensional feature map, avoiding the explicit \(n\times n\) matrix entirely
Flash Attention
\(O(n^2d)\) time, \(O(n)\) memory
Same exact computation as standard attention, reorganized to avoid materializing the full \(n\times n\) matrix in slow GPU memory
State-space models (Mamba)
\(O(nd)\)
Not attention at all — a different (recurrent-style) sequence operator entirely
12
Synthesis
The Complete Mental Model
// everything unified · one diagram · the full thread from alignment to scaling
Fig 1. Complete attention mental map — from the alignment problem through Bahdanau and Luong, the rigorous QKV derivation, self-attention with scaling, multi-head splitting, three theoretical interpretations, and the scaling laws that govern its computational cost.
The complete story in one coherent thread:
Attention solves the alignment problem — replacing the intractable discrete latent alignment of statistical MT, and the lossy fixed-vector bottleneck of vanilla encoder-decoder RNNs, with a continuous, differentiable, end-to-end-trainable soft alignment.
Bahdanau's additive scoring \(\mathbf{v}_a^T\tanh(\mathbf{W}_a\mathbf{s}+\mathbf{U}_a\mathbf{h})\) was the first working mechanism — flexible but computationally heavier than necessary, and still conflating the "matching" and "content" roles of \(\mathbf{h}_j\).
Luong's multiplicative scoring simplified this to \(\mathbf{s}^T\mathbf{W}\mathbf{h}\) (or plain \(\mathbf{s}^T\mathbf{h}\)) — a single matrix multiply, GPU-friendly, and the direct ancestor of the modern formulation.
The QKV framework is a derivation, not an assumption: factoring the bilinear score matrix \(\mathbf{W}=\mathbf{W}_Q^T\mathbf{W}_K\) (provably lossless for sufficient rank, by the SVD) yields Query and Key as a dot product; introducing an independent \(\mathbf{W}_V\) decouples content from matching. Three projections are the unique minimal generalization that preserves expressiveness while removing unnecessary coupling.
Self-attention applies the identical Q,K,V machinery with the query source and key/value source set to the same sequence — eliminating the sequential decoder dependency entirely and enabling full parallelization.
Scaling by \(1/\sqrt{d_k}\) is a one-line variance computation, not an arbitrary constant — without it, dot-product scores grow with dimension and saturate the softmax, killing gradients.
Multi-head attention runs several attention computations in independent subspaces at roughly no extra FLOP cost, allowing different heads to specialize in different relevance patterns that a single softmax distribution cannot jointly express.
Three theoretical lenses illuminate what attention IS: a differentiable content-addressable memory lookup (information retrieval), an exact instance of Nadaraya-Watson kernel regression with a learned exponential kernel (explaining in-context learning), and a function with a provable convex-hull output limitation alongside universal-approximation power when stacked with FFN layers.
Scaling laws — \(O(n^2d)\) compute, \(O(n)\) KV-cache memory, entropy dilution over long contexts — are the precise mathematical reasons efficient-attention research (sparse, linear, Flash Attention) exists, and why long-context modeling remains an active frontier.
What Attention Really Is
Strip away every architectural elaboration, and attention is a single, precise mathematical operation: a convex combination of value vectors, weighted by a learned, normalized similarity between a query and a set of keys. Everything else — Bahdanau's MLP, Luong's bilinear form, the \(1/\sqrt{d_k}\) scaling, the multi-head split — is refinement of how that similarity is computed, not a change to what the operation fundamentally does. Understanding attention rigorously means being able to derive Query, Key, and Value from the alignment problem itself, rather than accepting them as three mysteriously-appearing matrices — and recognizing that the same operation simultaneously IS a soft database lookup, IS kernel regression, and IS subject to provable expressive limits that no amount of scale alone can remove.
SHAHID||Portfolio