--- title: Attention & Transformers module: Architectures moduleNumber: 5 lessonNumber: 5 order: 505 summary: > Attention replaces fixed wiring with content-based routing: every position reads from every other through a soft, learned dot-product lookup. We derive scaled dot-product attention and its $\sqrt{d_k}$ correction, build it into multi-head self-attention, inject order with positional encodings, and stack the whole thing into the Transformer block that displaced recurrence and convolution alike. topics: [Architectures] sources: - book: Goodfellow ref: "§10.11 — Explicit Memory & Attention (the Transformer postdates the 2016 text)" - book: Chollet ref: "Ch. 11 — Deep Learning for Text; The Transformer Architecture" --- A [recurrent network](/deep-learning/architectures/recurrent-networks) reads a sequence one step at a time, squeezing the entire past into a single hidden state $h_t$. That bottleneck is the defect: information from position $1$ reaches position $n$ only after $n$ sequential hops, and the gradient connecting them decays along the way: the very problem [LSTMs and GRUs](/deep-learning/architectures/lstm-and-gru) only partially patch. **Attention** removes the hops entirely. Instead of routing information through a chain, every position reads directly from every other position in _one_ step, weighting what it reads by learned, content-dependent relevance.[^gf-attention] > **Definition (Attention).** A differentiable lookup. Given a query vector $q$, a > set of keys $\{k_j\}$, and an associated set of values $\{v_j\}$, attention > returns a convex combination $\sum_j \alpha_j v_j$ of the values, where the > weights $\alpha_j$ measure the compatibility between $q$ and each key $k_j$. It > is a _soft_ dictionary: a hard lookup returns the one value whose key matches; > attention returns a weighted blend of all of them. ## Queries, keys, and values The vocabulary is borrowed from retrieval. A **query** is what a position is looking for; a **key** advertises what each position offers; a **value** is the content actually returned. All three are linear projections of the inputs, so the mechanism is fully learned: three weight matrices determine what each token searches for, what it exposes for matching, and what content it returns. | Object | Symbol | Shape | Role | | --- | --- | --- | --- | | Query | $q = x W_Q$ | $\mathbb{R}^{d_k}$ | what this position is searching for | | Key | $k = x W_K$ | $\mathbb{R}^{d_k}$ | what each position offers for matching | | Value | $v = x W_V$ | $\mathbb{R}^{d_v}$ | the content returned when a key matches | | Score | $q \cdot k_j$ | scalar | raw compatibility of the query with key $j$ | | Weight | $\alpha_j$ | scalar in $(0,1)$ | softmax-normalized score, $\sum_j \alpha_j = 1$ | Compatibility is measured by a dot product: $q \cdot k_j$ is large when the query and key point the same way. Normalizing the scores with a softmax turns them into a probability distribution over positions, and the output is the expectation of the values under that distribution, $$ \alpha_j = \frac{\exp(q \cdot k_j)}{\sum_{j'} \exp(q \cdot k_{j'})}, \qquad \text{out} = \sum_j \alpha_j\, v_j . $$ $$ % caption: Scaled dot-product attention as a dataflow: queries and keys give scaled scores, a softmax turns them into weights, and multiplying by $V$ blends the values. \begin{tikzpicture}[>=stealth, font=\footnotesize, box/.style={draw, minimum width=16mm, minimum height=9mm, align=center}, op/.style={draw, minimum width=15mm, minimum height=9mm, align=center}] \definecolor{acc}{HTML}{2348F2} \node[box, draw=acc, text=acc] (Q) at (0,2.6) {Q}; \node[box, draw=acc, text=acc] (K) at (0,0) {K}; \node[box, draw=acc, text=acc] (V) at (0,-2.6) {V}; \node[op] (mm1) at (2.8,1.3) {\texttt{matmul}}; \node[box] (sc) at (5.4,1.3) {\texttt{scale}}; \node[box] (sm) at (7.9,1.3) {\texttt{softmax}}; \node[op] (mm2) at (10.4,-0.6) {\texttt{matmul}}; \node[box, draw=acc, text=acc] (out) at (13.0,-0.6) {\texttt{output}}; \draw[->, acc, thick] (Q) -- (mm1); \draw[->, acc, thick] (K) -- (mm1); \draw[->, thick] (mm1) -- (sc) node[midway, above, font=\footnotesize] {\texttt{scores}}; \draw[->, thick] (sc) -- (sm); \draw[->, thick] (sm) -- (mm2); \node[font=\footnotesize] at (9.7,0.9) {\texttt{weights}}; \draw[->, acc, thick] (V) -- (mm2); \draw[->, acc, thick] (mm2) -- (out); \end{tikzpicture} $$ ## Scaled dot-product attention Stack the $n$ queries into the rows of $Q$, the $m$ keys into the rows of $K$, and the $m$ values into the rows of $V$. Keeping the query count $n$ and the key/value count $m$ separate matters: in self-attention $n = m$, but in cross-attention a decoder of length $n$ reads an encoder of length $m \ne n$. Queries and keys must share a width $d_k$ so their dot product is defined; values carry an independent width $d_v$. The shapes chain as follows. $$ \underbrace{Q}_{n \times d_k} \qquad \underbrace{K}_{m \times d_k} \qquad \underbrace{V}_{m \times d_v} \qquad \underbrace{QK^\top}_{n \times m} \qquad \underbrace{\softmax\!\parens{\tfrac{QK^\top}{\sqrt{d_k}}}}_{n \times m} \qquad \underbrace{AV}_{n \times d_v} . $$ Every query-key score is a single matrix product $QK^\top \in \mathbb{R}^{n \times m}$: entry $(i,j)$ is the dot product $q_i \cdot k_j$ of query $i$ with key $j$. Divide by $\sqrt{d_k}$, run a softmax along each row so that row $i$ becomes a probability distribution over the $m$ keys, and right-multiply by $V$. The inner dimension $m$ cancels in $A V$, so an $n \times m$ weight matrix times an $m \times d_v$ value matrix returns an $n \times d_v$ output — one $d_v$-vector per query, exactly the input query count. The whole operation collapses to one expression. > **Definition (Scaled dot-product attention).** For queries $Q \in \mathbb{R}^{n > \times d_k}$, keys $K \in \mathbb{R}^{m \times d_k}$, and values $V \in > \mathbb{R}^{m \times d_v}$, > $$ > \Attn(Q, K, V) = \softmax\!\parens{\frac{QK^\top}{\sqrt{d_k}}} V > \;\in\; \mathbb{R}^{n \times d_v} . > $$ > The softmax is applied independently to each row, so row $i$ of the output is a > convex combination of the $m$ value vectors, weighted by how well query $i$ > matches every key. The only unexplained piece is the $1/\sqrt{d_k}$ factor. It is essential: without it the softmax saturates and gradients vanish.[^chollet-attn] ### Why the $\sqrt{d_k}$ scaling Treat the entries of a query $q$ and a key $k$ as independent random variables with mean $0$ and variance $1$. The dot product is a sum of $d_k$ such products, and we can compute the variance of that sum exactly. > **Lemma (Variance of the dot product).** If $q_1, \dots, q_{d_k}$ and $k_1, > \dots, k_{d_k}$ are mutually independent with $\mathbb{E}[q_i] = \mathbb{E}[k_i] > = 0$ and $\Var(q_i) = \Var(k_i) = 1$, then the dot > product $q \cdot k = \sum_{i=1}^{d_k} q_i k_i$ has mean $0$ and variance $d_k$. > **Proof.** Each term $q_i k_i$ has mean $\mathbb{E}[q_i k_i] = \mathbb{E}[q_i]\, > \mathbb{E}[k_i] = 0$ by independence, so $\mathbb{E}[q \cdot k] = 0$. For the > variance, independence across $i$ makes the terms uncorrelated, so variances > add: > $$ > \Var(q \cdot k) = \sum_{i=1}^{d_k} \Var(q_i k_i). > $$ > For a single term, $\Var(q_i k_i) = \mathbb{E}[q_i^2 k_i^2] - > (\mathbb{E}[q_i k_i])^2 = \mathbb{E}[q_i^2]\,\mathbb{E}[k_i^2] - 0 = 1 \cdot 1 = > 1$, again using independence. Summing $d_k$ unit-variance terms gives > $\Var(q \cdot k) = d_k$. $\qed$ So the raw scores have standard deviation $\sqrt{d_k}$, which _grows_ with the model dimension. Feed scores of magnitude $\sim\!\sqrt{d_k}$ into a softmax and, for $d_k$ in the hundreds, the largest entry dwarfs the rest: the softmax saturates onto one position, approaching a one-hot vector. In that regime its Jacobian is nearly zero, and almost no gradient flows back to the queries and keys. Dividing by $\sqrt{d_k}$ rescales the scores to unit variance, $\Var \!\parens{ (q \cdot k)/\sqrt{d_k}} = 1$, keeping the softmax in its sensitive, high-gradient region regardless of dimension. $$ % caption: Without the $1/\sqrt{d_k}$ correction the softmax saturates: large-variance % scores (black) collapse onto one key, while scaled scores (blue) stay usable. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \draw[->, thick] (-0.3,0) -- (6.6,0) node[right, font=\scriptsize] {key index}; \draw[->, thick] (0,-0.2) -- (0,3.0) node[above, font=\scriptsize] {weight}; % saturated (neutral): one tall spike \foreach \x/\h in {0.6/0.15, 1.4/0.2, 2.2/2.55, 3.0/0.25, 3.8/0.15, 4.6/0.18, 5.4/0.12} \draw[black, thick, fill=black!12] (\x-0.14,0) rectangle (\x+0.0,\h); % scaled (blue): spread distribution, offset to the right of each neutral bar \foreach \x/\h in {0.6/0.55, 1.4/0.75, 2.2/1.35, 3.0/1.0, 3.8/0.7, 4.6/0.5, 5.4/0.35} \draw[acc, thick, fill=acc!18] (\x+0.02,0) rectangle (\x+0.16,\h); \node[black, font=\scriptsize, anchor=west] at (2.9,2.4) {unscaled (saturated)}; \node[acc, font=\scriptsize, anchor=west] at (3.2,1.55) {scaled}; \end{tikzpicture} $$ ```algorithm caption: $\textsc{ScaledDotProductAttention}(Q, K, V)$ — soft content-based lookup $S \gets Q K^{T}$ // $n \times n$ raw scores $S \gets S / \sqrt{d_k}$ // unit-variance correction if masked then // decoder self-attention for each $i, j$ with $j > i$ do $S_{ij} \gets -\infty$ // forbid attending to the future for each row $i$ do $A_{i} \gets \softmax(S_{i})$ // weights sum to $1$ return $A V$ // blend the values ``` ### A worked example Push numbers through the formula. Take three tokens with $d_k = d_v = 2$, and, to keep the arithmetic legible, let the queries and keys coincide, so this is self-attention: $$ Q = K = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{bmatrix} \;\in\; \mathbb{R}^{3\times 2}, \qquad V = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0.5 & 0.5 \end{bmatrix} \;\in\; \mathbb{R}^{3\times 2}. $$ **Step 1 — raw scores $S = QK^\top$.** Each entry is $q_i \cdot k_j$. Row $1$ is query $(1,0)$ dotted against the three keys: $(1,0)\cdot(1,0)=1$, $(1,0)\cdot(0,1)=0$, $(1,0)\cdot(1,1)=1$. Filling in all nine, $$ S = QK^\top = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 2 \end{bmatrix} \;\in\; \mathbb{R}^{3\times 3}. $$ **Step 2 — scale by $\sqrt{d_k} = \sqrt 2 \approx 1.414$.** Every score shrinks by the same factor, pulling the logits toward zero before the softmax: $$ \frac{S}{\sqrt 2} = \begin{bmatrix} 0.707 & 0 & 0.707 \\ 0 & 0.707 & 0.707 \\ 0.707 & 0.707 & 1.414 \end{bmatrix}. $$ **Step 3 — row-wise softmax.** Work row $1$ explicitly. Exponentiate: $e^{0.707} \approx 2.028$, $e^{0} = 1$, $e^{0.707} \approx 2.028$, summing to $5.056$. Dividing gives $2.028/5.056 \approx 0.401$ for the first and third keys and $1/5.056 \approx 0.198$ for the second. Doing the same to every row, $$ A = \softmax\!\parens{\frac{S}{\sqrt 2}} = \begin{bmatrix} 0.401 & 0.198 & 0.401 \\ 0.198 & 0.401 & 0.401 \\ 0.248 & 0.248 & 0.503 \end{bmatrix}, $$ and each row sums to $1$, as a distribution over the three keys must. Notice the third token — whose query $(1,1)$ aligns with every key — spreads its weight most evenly but still favours itself (key $3$, weight $0.503$), because $(1,1)\cdot(1,1) = 2$ is the largest score in that row. **Step 4 — blend the values, $O = AV$.** Row $1$ of the output is $0.401\,v_1 + 0.198\,v_2 + 0.401\,v_3 = 0.401(1,0) + 0.198(0,1) + 0.401(0.5,0.5) = (0.602, 0.398)$. All three outputs: $$ O = AV = \begin{bmatrix} 0.602 & 0.398 \\ 0.398 & 0.602 \\ 0.500 & 0.500 \end{bmatrix} \;\in\; \mathbb{R}^{3\times 2}. $$ Each output row is a point _inside_ the triangle spanned by the three value vectors — a convex combination, never an extrapolation beyond them. That is the geometric signature of attention: the output can only ever be a weighted average of the values it was given. ## Self-attention When the queries, keys, and values are all linear projections of the _same_ sequence $X \in \mathbb{R}^{n \times d}$, attention becomes **self-attention**: each position attends to every other position in its own input, including itself. > **Definition (Self-attention).** Self-attention is scaled dot-product attention > in which $Q = X W_Q$, $K = X W_K$, $V = X W_V$ all derive from one input > sequence $X$. The result re-expresses each position as a content-weighted > summary of the whole sequence. Its central object is the **attention matrix** $$ A = \softmax\!\parens{\frac{QK^\top}{\sqrt{d_k}}} \in \mathbb{R}^{n \times n}, \qquad A_{ij} = \text{how much position } i \text{ attends to position } j, $$ a row-stochastic matrix ($\sum_j A_{ij} = 1$) that is a soft, content-based, **all-pairs routing table**: row $i$ says where token $i$ gathers its information. Unlike a convolution's fixed local stencil or a recurrence's strictly leftward chain, every entry is non-zero and _learned from content_: the word "it" can route directly to the noun it refers to, however far back. $$ % caption: A self-attention matrix. Each row is a token's query and darker cells carry more weight; here "it" attends strongly to "animal", resolving the reference in one hop. \begin{tikzpicture}[font=\scriptsize, x=0.95cm, y=0.62cm] \definecolor{acc}{HTML}{2348F2} % column headers (top) \foreach \c/\t in {0/the, 1/animal, 2/crossed, 3/because, 4/it, 5/was, 6/tired} \node[rotate=42, anchor=west, font=\scriptsize] at (\c+0.2, 7.15) {\t}; % row headers (left) \foreach \r/\t in {0/the, 1/animal, 2/crossed, 3/because, 4/it, 5/was, 6/tired} \node[anchor=east, font=\footnotesize] at (-0.15, 6.4-\r) {\texttt{\t}}; % each cell drawn explicitly: \cell{col}{row}{shade 0-100} — light tint + crisp outline \def\cell#1#2#3{\draw[black, fill=acc!#3] (#1+0.07,6.15-#2) rectangle (#1+0.85,6.15-#2+0.78);} % row 0 the \cell{0}{0}{62}\cell{1}{0}{10}\cell{2}{0}{6}\cell{3}{0}{5}\cell{4}{0}{5}\cell{5}{0}{4}\cell{6}{0}{4} % row 1 animal \cell{0}{1}{12}\cell{1}{1}{58}\cell{2}{1}{10}\cell{3}{1}{4}\cell{4}{1}{8}\cell{5}{1}{4}\cell{6}{1}{4} % row 2 crossed \cell{0}{2}{8}\cell{1}{2}{32}\cell{2}{2}{42}\cell{3}{2}{4}\cell{4}{2}{6}\cell{5}{2}{4}\cell{6}{2}{4} % row 3 because \cell{0}{3}{5}\cell{1}{3}{10}\cell{2}{3}{12}\cell{3}{3}{42}\cell{4}{3}{16}\cell{5}{3}{8}\cell{6}{3}{5} % row 4 it -> attends to animal \cell{0}{4}{5}\cell{1}{4}{72}\cell{2}{4}{5}\cell{3}{4}{5}\cell{4}{4}{28}\cell{5}{4}{5}\cell{6}{4}{5} % row 5 was \cell{0}{5}{5}\cell{1}{5}{16}\cell{2}{5}{6}\cell{3}{5}{10}\cell{4}{5}{20}\cell{5}{5}{42}\cell{6}{5}{10} % row 6 tired \cell{0}{6}{5}\cell{1}{6}{22}\cell{2}{6}{5}\cell{3}{6}{6}\cell{4}{6}{16}\cell{5}{6}{12}\cell{6}{6}{56} \end{tikzpicture} $$ ### Permutation equivariance Self-attention has no notion of order. Permuting the rows of $X$ permutes the rows of the output identically and changes nothing else; the mechanism treats its input as a _set_, not a sequence. > **Theorem (Permutation equivariance of self-attention).** Let $P$ be an $n > \times n$ permutation matrix and let $\SA(X) = > \Attn(XW_Q, XW_K, XW_V)$. Then $\SA(PX) = P\, > \SA(X)$. > **Proof.** Permuting the inputs sends $Q \mapsto PQ$, $K \mapsto PK$, $V \mapsto > PV$, since each is $X$ times a fixed projection. The scores become $(PQ)(PK)^\top > = P\,(QK^\top)\,P^\top$. The softmax acts row-wise and $P^\top$ permutes columns > consistently with the row permutation $P$, so $\softmax(P\,S\, > P^\top) = P\,\softmax(S)\,P^\top$. Multiplying by the values, > $$ > P\,\softmax(S)\,P^\top \cdot PV = P\,\softmax(S)\,V, > $$ > because $P^\top P = I$. The right side is $P\,\SA(X)$. $\qed$ Equivariance renders position invisible: "dog bites man" and "man bites dog" produce the same set of outputs, merely reordered. Order must therefore be injected explicitly, the job of positional encoding below. ## Multi-head attention A single attention function forces every position to mix all of its relationships into one set of weights. **Multi-head attention** runs $h$ attention functions in parallel, each with its own projections, so different heads can specialize: one tracking syntactic agreement, another long-range coreference, another local adjacency.[^chollet-mha] > **Definition (Multi-head attention).** Project the inputs $h$ times with > independent matrices, attend in each subspace, then concatenate and project: > $$ > \head_i = \Attn(X W_Q^{(i)}, X W_K^{(i)}, X W_V^{(i)}), > $$ > $$ > \MHA(X) = \Concat(\head_1, \dots, \head_h)\, W_O . > $$ > Each head works in a $d_k = d / h$ dimensional subspace, so the total compute > matches a single full-width head; $W_O \in \mathbb{R}^{d \times d}$ recombines > the heads. $$ % caption: Multi-head attention. The input is projected into $h$ subspaces, each running its own scaled dot-product attention; the outputs are concatenated and mixed by $W_O$. \begin{tikzpicture}[>=stealth, font=\footnotesize, box/.style={draw, minimum width=17mm, minimum height=9mm, align=center}] \definecolor{acc}{HTML}{2348F2} \node[box, draw=acc, text=acc] (in) at (0,0) {input X}; \node[box] (h1) at (3.6,2.2) {head 1}; \node[box] (h2) at (3.6,0) {head 2}; \node[box] (h3) at (3.6,-2.2) {head h}; \node[font=\small] at (3.6,-1.1) {$\vdots$}; \node[box, draw=acc, text=acc] (cat) at (7.3,0) {concat}; \node[box, draw=acc, text=acc] (wo) at (10.4,0) {$W_O$}; \draw[->, acc, thick] (in) -- (h1); \draw[->, acc, thick] (in) -- (h2); \draw[->, acc, thick] (in) -- (h3); \draw[->, acc, thick] (h1) -- (cat); \draw[->, acc, thick] (h2) -- (cat); \draw[->, acc, thick] (h3) -- (cat); \draw[->, acc, thick] (cat) -- (wo); \end{tikzpicture} $$ The shapes are worth tracing once. Fix $d = d_{\text{model}}$ and $h$ heads, and set the per-head width $d_k = d_v = d/h$ (so $h = 8$ heads of a $d = 512$ model each work in $64$ dimensions). For head $i$ the projections are $W_Q^{(i)}, W_K^{(i)}, W_V^{(i)} \in \mathbb{R}^{d \times d/h}$, so from an input $X \in \mathbb{R}^{n \times d}$, $$ \underbrace{X W_Q^{(i)}}_{n \times d/h} \quad \underbrace{X W_K^{(i)}}_{n \times d/h} \quad \underbrace{X W_V^{(i)}}_{n \times d/h} \;\Longrightarrow\; \underbrace{\head_i}_{n \times d/h}, $$ each head returns an $n \times (d/h)$ block. Concatenating the $h$ blocks along the width rebuilds a full $n \times d$ matrix, which $W_O \in \mathbb{R}^{d \times d}$ mixes back into the model width: $$ \underbrace{\Concat(\head_1, \dots, \head_h)}_{n \times d} \;\cdot\; \underbrace{W_O}_{d \times d} \;=\; \underbrace{\MHA(X)}_{n \times d}. $$ Because $h \cdot (d/h) = d$, the total projection and attention cost is the same as one full-width head; heads split the width rather than add to it. The expressive gain is that the model holds $h$ distinct routing tables at once instead of averaging them into one — one head can lock onto the previous token while another tracks long-range coreference, and $W_O$ learns how to combine their outputs. $$ % caption: Multi-head width bookkeeping for $d = 512$, $h = 8$. Each head projects the $n \times 512$ input down to $n \times 64$, attends there, and the $8$ blocks concatenate back to $n \times 512$ before $W_O$. \begin{tikzpicture}[>=stealth, font=\footnotesize, wide/.style={draw=acc, fill=acc!10, minimum width=34mm, minimum height=8mm, align=center}, slab/.style={draw, minimum width=9mm, minimum height=8mm, align=center, fill=black!6}] \definecolor{acc}{HTML}{2348F2} \node[wide] (in) at (0,3.2) {\texttt{X : n x 512}}; % 8 per-head slabs \foreach \i in {0,...,7} \node[slab] (s\i) at (\i*1.05 - 3.7, 1.4) {\texttt{64}}; \node[font=\footnotesize, text=black, anchor=west] at (4.0,1.4) {\texttt{8 heads, n x 64}}; \node[coordinate] (j) at (0,0.05) {}; \node[wide] (cat) at (0,-1.0) {\texttt{concat : n x 512}}; \node[wide] (out) at (0,-2.5) {\texttt{W\_O out : n x 512}}; \draw[->, acc, thick] (in) -- (s3.north); \draw[->, acc, thick] (in) -- (s4.north); \foreach \i in {0,...,7} \draw[black] (s\i) -- (j); \draw[->, black] (j) -- (cat.north); \draw[->, acc, thick] (cat) -- (out); \end{tikzpicture} $$ ## Positional encoding Because self-attention is permutation-equivariant, the model cannot tell position $1$ from position $5$ unless we tell it. The fix is to _add_ a position-dependent vector $\PE(p)$ to each input embedding before the first layer, so that order rides along in the representation itself.[^chollet-pos] > **Definition (Sinusoidal positional encoding).** For position $p$ and embedding > dimension index $i$, with model width $d$, > $$ > \PE(p, 2i) = \sin\!\parens{\frac{p}{10000^{\,2i/d}}}, > \qquad > \PE(p, 2i+1) = \cos\!\parens{\frac{p}{10000^{\,2i/d}}}. > $$ > Each dimension is a sinusoid; the wavelength grows geometrically from $2\pi$ to > $10000 \cdot 2\pi$ across dimensions, so the vector encodes position at many > resolutions at once. The geometric spread of frequencies is the key property: low-index dimensions oscillate quickly to distinguish neighbors, high-index dimensions oscillate slowly to distinguish distant regions. The encoding also admits _relative_ shifts, since $\PE(p+\Delta)$ is a fixed linear function of $\PE(p)$, so the model can learn to attend by offset, not just absolute index. $$ % caption: Sinusoidal positional encodings. Each curve is one embedding dimension over % position $p$: low dimensions (blue) oscillate fast, high ones (red) slowly. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} \draw[->, thick] (-0.2,0) -- (7.6,0) node[right, font=\scriptsize] {position p}; \draw[->, thick] (0,-1.4) -- (0,1.5) node[above, font=\scriptsize] {value}; \draw[black] (0,0) -- (7.4,0); % high frequency (blue) \draw[acc, very thick] plot[domain=0:7.3, samples=120] (\x, {1.1*sin(2.6*\x r)}); % medium frequency (black) \draw[black, very thick] plot[domain=0:7.3, samples=120] (\x, {1.1*sin(1.1*\x r)}); % low frequency (red) \draw[red, very thick] plot[domain=0:7.3, samples=120] (\x, {1.1*sin(0.45*\x r)}); \node[acc, font=\scriptsize, anchor=west] at (6.2,1.25) {fast}; \node[red, font=\scriptsize, anchor=west] at (6.2,-0.55) {slow}; \end{tikzpicture} $$ Learned positional embeddings — a trainable lookup table indexed by position — are the common alternative; they fit the data more tightly but, unlike the sinusoids, do not extrapolate to sequences longer than those seen in training. | Scheme | Form | Generalizes past training length? | Cost | | --- | --- | --- | --- | | Sinusoidal | fixed $\sin/\cos$ of position | yes (deterministic for any $p$) | none | | Learned | trainable table $E_{\text{pos}} \in \mathbb{R}^{n_{\max} \times d}$ | no (undefined for $p > n_{\max}$) | $n_{\max} \cdot d$ params | | Relative | bias on scores by offset $i - j$ | yes | per-head bias | ## The Transformer block Self-attention mixes information _across_ positions; it does no nonlinear processing _within_ a position. The **Transformer block** pairs the two: a multi-head self-attention sublayer followed by a position-wise feed-forward network, each sublayer wrapped in a residual connection and [layer normalization](/deep-learning/regularization/normalization).[^chollet-block] > **Definition (Position-wise feed-forward network).** A two-layer MLP applied > independently and identically to every position: > $$ > \FFN(x) = \ReLU(x W_1 + b_1)\,W_2 + b_2, > $$ > with an inner width typically $4d$. It is the per-token nonlinearity that > attention lacks; sharing weights across positions makes it a $1 \times 1$ > convolution in disguise. Each sublayer is wrapped identically, $\out = \LayerNorm (x + \Sublayer(x))$. The residual skip lets gradients reach early layers undiminished — the same mechanism that powers [residual networks](/deep-learning/architectures/cnn-architectures) — and LayerNorm holds each position's activations at a stable scale across depth. $$ % caption: A Transformer encoder block: multi-head self-attention then a position-wise FFN, each wrapped in an add-and-normalize. The two curved skips are the residual connections. \begin{tikzpicture}[>=stealth, font=\footnotesize, box/.style={draw, minimum width=42mm, minimum height=9mm, align=center}, add/.style={draw, minimum width=42mm, minimum height=8mm, align=center, fill=black!8}] \definecolor{acc}{HTML}{2348F2} \node (in) at (0,0) {input}; \node[box, draw=acc, text=acc, thick] (mha) at (0,1.3) {\texttt{multi-head self-attention}}; \node[add] (an1) at (0,2.7) {\texttt{add \& norm}}; \node[box, draw=acc, text=acc, thick] (ffn) at (0,4.1) {\texttt{feed-forward}}; \node[add] (an2) at (0,5.5) {\texttt{add \& norm}}; \node (out) at (0,6.7) {output}; \draw[->, thick] (in) -- (mha); \draw[->, thick] (mha) -- (an1); \draw[->, thick] (an1) -- (ffn); \draw[->, thick] (ffn) -- (an2); \draw[->, thick] (an2) -- (out); % residual skips on the right \draw[->, acc, thick] (2.1,0.2) .. controls (3.4,0.9) and (3.4,2.0) .. (2.1,2.7) node[pos=0.5, right, font=\scriptsize, text=acc] {skip}; \draw[->, acc, thick] (2.1,3.0) .. controls (3.4,3.7) and (3.4,4.8) .. (2.1,5.5) node[pos=0.5, right, font=\scriptsize, text=acc] {skip}; \end{tikzpicture} $$ ### Encoder and decoder The original Transformer is an **encoder-decoder**. The encoder stacks identical blocks with unrestricted self-attention — every position sees every other. The decoder adds two twists that make it a valid autoregressive generator. | Component | Self-attention | Cross-attention | Sees the future? | | --- | --- | --- | --- | | Encoder block | full (all-pairs) | — | yes (whole input visible) | | Decoder block | _masked_ | attends to encoder output | no (causal mask) | - **Masked self-attention.** To generate token $t$ using only tokens $< t$, the decoder sets $S_{ij} = -\infty$ for $j > i$ before the softmax (the masking branch of the algorithm above), forcing $A_{ij} = 0$ on the future. Generation stays causal. - **Cross-attention.** A second attention sublayer takes its queries from the decoder but its keys and values from the encoder's output, letting each generated token read the entire source sequence — the channel through which a translation model reads the sentence it is translating. Cross-attention is the setting where the $n \ne m$ shapes matter. In an encoder of length $m$ and a decoder generating length $n$, the decoder supplies $Q \in \mathbb{R}^{n \times d_k}$ while the encoder supplies $K, V \in \mathbb{R}^{m \times d_k}$, so the score matrix is a rectangular $n \times m$ lookup — every output position against every source position. Self-attention is the special case $Q = K = V$ from one sequence, giving the square $n \times n$ matrix; cross-attention keeps queries and keys from _different_ sequences. ### The causal mask The mask is a single additive matrix $M \in \mathbb{R}^{n \times n}$ applied to the scaled scores before the softmax: $M_{ij} = 0$ for $j \le i$ and $M_{ij} = -\infty$ for $j > i$. Adding $-\infty$ to a logit sends $e^{-\infty} = 0$, so the softmax assigns those future positions weight exactly $0$ — the reason for the $-\infty$ rather than merely a large negative number. For four tokens, $$ M = \begin{bmatrix} 0 & -\infty & -\infty & -\infty \\ 0 & 0 & -\infty & -\infty \\ 0 & 0 & 0 & -\infty \\ 0 & 0 & 0 & 0 \end{bmatrix}, \qquad A = \softmax\!\parens{\frac{QK^\top}{\sqrt{d_k}}} + M \text{ pattern} = \begin{bmatrix} \bullet & 0 & 0 & 0 \\ \bullet & \bullet & 0 & 0 \\ \bullet & \bullet & \bullet & 0 \\ \bullet & \bullet & \bullet & \bullet \end{bmatrix}, $$ leaving a lower-triangular weight matrix: token $i$ attends only to tokens $1 \dots i$. The mask costs nothing at training time (one addition), yet it is what lets the decoder train on a whole target sequence in parallel while still predicting each token from its prefix alone. $$ % caption: The causal mask. Below and on the diagonal (blue) a token may attend; above it (crossed) the score is set to $-\infty$ so the softmax weight is $0$. Row $i$ sees only tokens $1 \dots i$. \begin{tikzpicture}[font=\scriptsize, x=0.9cm, y=0.9cm] \definecolor{acc}{HTML}{2348F2} \foreach \c/\lab in {0/1, 1/2, 2/3, 3/4, 4/5} \node[font=\scriptsize, text=black] at (\c+0.5, 5.2) {$k_{\lab}$}; \foreach \r/\lab in {0/1, 1/2, 2/3, 3/4, 4/5} \node[font=\scriptsize, text=black, anchor=east] at (-0.05, 4.5-\r) {$q_{\lab}$}; \foreach \r in {0,...,4} \foreach \c in {0,...,4} { \ifnum\c>\r \draw[black] (\c,4-\r) rectangle (\c+1,5-\r); \draw[black] (\c+0.18,4.18-\r) -- (\c+0.82,4.82-\r); \draw[black] (\c+0.18,4.82-\r) -- (\c+0.82,4.18-\r); \else \draw[draw=acc, fill=acc!22] (\c,4-\r) rectangle (\c+1,5-\r); \fi } \end{tikzpicture} $$ ## Recurrence vs. convolution vs. self-attention Why did attention displace both recurrence and convolution for sequences? Compare the three on the costs that matter: how far information must travel to connect two positions (**maximum path length**, which bounds how easily long-range gradients flow), how much of the work is inherently **sequential**, and the **per-layer compute**. | Layer type | Per-layer complexity | Sequential ops | Max path length | | --- | --- | --- | --- | | Recurrent | $O(n\, d^2)$ | $O(n)$ | $O(n)$ | | Convolutional (kernel $w$) | $O(w\, n\, d^2)$ | $O(1)$ | $O(\log_w n)$ | | Self-attention | $O(n^2 d)$ | $O(1)$ | $O(1)$ | Two columns decide it. Self-attention's maximum path length is $O(1)$: _any_ two positions interact directly, so the gradient between them never has to pass through a long chain. Its sequential depth is $O(1)$, so the whole layer parallelizes across positions on a GPU, unlike the strictly stepwise recurrence. The price is the $O(n^2 d)$ term: the $n \times n$ attention matrix is quadratic in sequence length, cheap when $n < d$ (the usual regime) but the dominant cost for long sequences, the bottleneck that later efficient-attention variants attack. $$ % caption: Connectivity, not just cost. Self-attention (left) links every token pair directly at path length $1$; a recurrence (right) leaves distant tokens $O(n)$ hops apart. \begin{tikzpicture}[>=stealth, font=\footnotesize, tok/.style={circle, draw, minimum size=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} % --- self-attention: all-pairs --- \foreach \i in {1,2,3,4} \node[tok, draw=acc, text=acc] (a\i) at (\i*1.25,0) {\i}; \draw[acc] (a1) to[bend left=38] (a2); \draw[acc] (a1) to[bend left=42] (a3); \draw[acc] (a1) to[bend left=46] (a4); \draw[acc] (a2) to[bend left=38] (a3); \draw[acc] (a2) to[bend left=42] (a4); \draw[acc] (a3) to[bend left=38] (a4); \node[align=center, font=\footnotesize] at (3.1,-1.1) {\texttt{self-attention}\\(all-pairs, path $1$)}; % --- recurrence: chain --- \begin{scope}[xshift=7.4cm] \foreach \i in {1,2,3,4} \node[tok] (b\i) at (\i*1.25,0) {\i}; \draw[->, black, thick] (b1) -- (b2); \draw[->, black, thick] (b2) -- (b3); \draw[->, black, thick] (b3) -- (b4); \node[align=center, font=\scriptsize] at (3.1,-1.1) {recurrence\\(chain, path $n$)}; \end{scope} \end{tikzpicture} $$ ## Where attention came from Attention postdates Goodfellow's 2016 text, so the primary sources carry the detail Goodfellow cannot. - **Where attention came from.** The dot-product form here is the streamlined version. The idea started as **additive attention** (Bahdanau et al., ICLR 2015), which scored a query against each key with a small MLP, $\score(q,k) = v^\top \tanh(W_q q + W_k k)$, to let a translation decoder read every encoder state instead of one fixed vector. Vaswani et al., "Attention Is All You Need" (NeurIPS 2017), replaced the MLP with the cheap scaled dot product, added the $1/\sqrt{d_k}$ correction derived above, and removed recurrence entirely. - **Reducing the $O(n^2)$ cost.** The quadratic score matrix is the target of a whole line of work. Two directions matter. _Sparse and linear approximations_ — Longformer (Beltagy et al., 2020) with sliding-window attention, and the Performer/linear-attention family — reduce the asymptotic cost to $O(n\log n)$ or $O(n)$ by never forming the full matrix. _Exact but IO-aware kernels_ — FlashAttention (Dao et al., NeurIPS 2022) — keep the exact softmax but tile the computation so the $n\times n$ matrix never leaves fast on-chip memory, cutting the memory footprint from $O(n^2)$ to $O(n)$ with no change to the result. The second approach is now the default in production Transformers. - **Relative and rotary position.** The additive sinusoidal encoding is only the first of several schemes. Shaw et al. (2018) added learned relative-position biases inside the scores; RoPE (Su et al., 2021) rotates the query and key vectors by an angle proportional to position, so a dot product depends only on the _relative_ offset — the standard choice in modern decoder-only LLMs. The full architecture built from this mechanism — the stacked encoder–decoder, causal masking, and the parameter/compute accounting — is the subject of [the next lesson](/deep-learning/architectures/the-transformer-architecture). ## Takeaways - **Attention** is a differentiable soft lookup: a query scores a set of keys, a softmax turns the scores into weights, and the output is the weighted blend of the values, $\Attn(Q,K,V) = \softmax(QK^\top/\sqrt{d_k})\,V$. - The **$\sqrt{d_k}$** scaling cancels the dot product's variance growth ($\Var(q \cdot k) = d_k$), keeping the softmax out of its saturated, zero-gradient regime. - **Self-attention** ($Q,K,V$ from one sequence) yields an all-pairs routing matrix $A$; being permutation-equivariant, it needs **positional encoding** — sinusoidal or learned — to know order. - **Multi-head** attention runs $h$ parallel attentions in $d/h$-dimensional subspaces, capturing several relationship patterns at once for the cost of one. - The **Transformer block** = multi-head self-attention + position-wise FFN, each in a residual + LayerNorm wrapper; decoders add a causal mask and cross-attention. - Against recurrence and convolution, self-attention wins on **path length** ($O(1)$) and **parallelism** ($O(1)$ sequential ops), paying an $O(n^2 d)$ per-layer cost — the trade that made it the dominant sequence architecture. [^gf-attention]: **Goodfellow**, _Deep Learning_, §10.11 — Explicit Memory & attention over memory cells: content-based addressing as a differentiable soft lookup (the Transformer itself postdates the 2016 text). [^chollet-attn]: **Chollet**, _Deep Learning with Python_, Ch. 11 — Deep Learning for Text: scaled dot-product attention, the $1/\sqrt{d_k}$ correction, and the `softmax(QK^T/\sqrt{d_k})V` core of the Transformer. [^chollet-mha]: **Chollet**, _Deep Learning with Python_, Ch. 11 — Multi-Head Attention: $h$ parallel attention functions in $d/h$-dimensional subspaces, concatenated and projected by $W_O$. [^chollet-pos]: **Chollet**, _Deep Learning with Python_, Ch. 11 — Positional encoding: injecting order into a permutation-equivariant model, sinusoidal versus learned embeddings. [^chollet-block]: **Chollet**, _Deep Learning with Python_, Ch. 11 — The Transformer encoder block: multi-head self-attention plus a position-wise feed-forward network, each in a residual + normalization wrapper.