spb/artificial-neural-networks-book Public
Artificial Neural Networks — Methods, Equations and Graphical Representations: a complete book, every method with rigorous equations, pseudocode and native TikZ figures.
TeX 100%
1% ============================================================================2% Artificial Neural Networks — Methods, Equations and Graphical3% Representations4% Author : Simon-Pierre Boucher — contact@spboucher.ai5% Chapter 6 : Attention and Transformers (chapters/06-attention.tex)6% ============================================================================78\chapter{Attention and Transformers}\label{chap:attention}910Recurrent networks process a sequence one position at a time: the hidden11state is a bottleneck through which all past information must flow, training12cannot be parallelized along the time axis, and interactions between distant13positions must survive a long chain of state updates. The Transformer14\cite{vaswani2017} removed this bottleneck in a single stroke. It dispenses15entirely with recurrence and convolution, and models every pairwise16interaction between sequence positions \emph{directly}, through a mechanism17called \emph{attention}. Every position can consult every other position in18one step, the whole computation is expressed as a handful of dense matrix19products that parallelize perfectly, and the maximum path length between any20two positions drops to $O(1)$. This chapter builds the architecture from its21smallest component — the scaled dot-product — to the complete22encoder--decoder stack, and closes with the computational trade-offs and the23three model families (BERT, GPT, T5) that grew out of it.2425% ----------------------------------------------------------------------------26\section{From Recurrence to Attention}27% ----------------------------------------------------------------------------2829The guiding intuition is retrieval. Suppose each position of a sequence30emits a \emph{query} describing the information it is looking for, while31every position also exposes a \emph{key} describing the information it32holds, together with a \emph{value} carrying the actual content. Attention33answers each query by comparing it against all keys, converting the34similarity scores into weights, and returning the corresponding weighted35average of the values. The result is a \emph{soft} dictionary lookup: fully36differentiable, so it can be trained end to end by the backpropagation37machinery of the earlier chapters, and content-based, so the pattern of38interaction is decided by the data rather than fixed by the architecture.3940Formally, we work with three matrices: queries41$\mat{Q} \in \R^{n \times d_k}$, keys $\mat{K} \in \R^{m \times d_k}$ and42values $\mat{V} \in \R^{m \times d_v}$, where $n$ is the number of query43positions, $m$ the number of key--value positions, $d_k$ the dimension in44which queries and keys are compared, and $d_v$ the dimension of the45returned content. In \emph{self-attention}, all three are linear46projections of the same sequence ($m = n$); in \emph{cross-attention},47queries come from one sequence and keys/values from another.4849% ----------------------------------------------------------------------------50\section{Scaled Dot-Product Attention}\label{sec:att-sdpa}51% ----------------------------------------------------------------------------5253\begin{definition}[Scaled dot-product attention]\label{def:att-sdpa}54Given $\mat{Q} \in \R^{n \times d_k}$, $\mat{K} \in \R^{m \times d_k}$ and55$\mat{V} \in \R^{m \times d_v}$, scaled dot-product attention is the map56\begin{equation}57 \mathrm{Attention}(\mat{Q}, \mat{K}, \mat{V})58 \;=\;59 \softmax\!\left( \frac{\mat{Q}\mat{K}\transp}{\sqrt{d_k}} \right) \mat{V}60 \;\in\; \R^{n \times d_v},61 \label{eq:att-sdpa}62\end{equation}63where the softmax is applied row-wise \cite{vaswani2017}.64\end{definition}6566Reading \eqref{eq:att-sdpa} from the inside out: the Gram matrix67$\mat{Q}\mat{K}\transp \in \R^{n \times m}$ collects all $n \times m$ dot68products between queries and keys; dividing by $\sqrt{d_k}$ rescales these69similarity scores; the row-wise softmax turns each row into a probability70distribution over the $m$ source positions; and the final product with71$\mat{V}$ computes, for each query, the corresponding convex combination of72value vectors. Writing $\vect{q}_i$ for the $i$-th query and73$\vect{k}_j, \vect{v}_j$ for the $j$-th key and value, the attention weight74that position $i$ places on position $j$ is75\begin{equation}76 \alpha_{ij}77 \;=\;78 \frac{\exp\!\big( \vect{q}_i\transp \vect{k}_j / \sqrt{d_k} \big)}79 {\sum_{j'=1}^{m} \exp\!\big( \vect{q}_i\transp \vect{k}_{j'} / \sqrt{d_k} \big)},80 \qquad81 \sum_{j=1}^{m} \alpha_{ij} = 1,82 \label{eq:att-alpha}83\end{equation}84and the $i$-th output row is $\sum_j \alpha_{ij}\vect{v}_j$. The whole85computation is displayed in Figure~\ref{fig:att-sdpa-flow}.8687\begin{figure}[htbp]88 \centering89 \begin{tikzpicture}[font=\small]90 % --- input blocks ---91 \node[blocinput, minimum width=1.2cm] (Q) at (-1.4, 0) {$\mat{Q}$};92 \node[blocinput, minimum width=1.2cm] (K) at ( 1.4, 0) {$\mat{K}$};93 \node[blocinput, minimum width=1.2cm] (V) at ( 4.6, 0) {$\mat{V}$};94 % --- pipeline ---95 \node[op] (mm1) at (0, 1.5) {$\times$};96 \node[bloc, minimum width=2.7cm] (scale) at (0, 2.7) {Scale by $1/\sqrt{d_k}$};97 \node[bloc, minimum width=2.7cm, dashed] (mask) at (0, 3.9) {Mask (optional)};98 \node[gate, minimum width=2.7cm] (sm) at (0, 5.1) {$\softmax$ (row-wise)};99 \node[op] (mm2) at (0, 6.4) {$\times$};100 \node[blocoutput, minimum width=3.4cm] (out) at (0, 7.6)101 {$\mathrm{Attention}(\mat{Q},\mat{K},\mat{V})$};102 % --- arrows ---103 \draw[fleche] (Q) -- (mm1);104 \draw[fleche] (K) -- (mm1);105 \draw[fleche] (mm1) -- (scale);106 \draw[fleche] (scale)-- (mask);107 \draw[fleche] (mask) -- (sm);108 \draw[fleche] (sm) -- (mm2);109 \draw[fleche, rounded corners=3pt] (V.north) -- (4.6, 6.4) -- (mm2);110 \draw[fleche] (mm2) -- (out);111 % --- annotations ---112 \node[etiquette, anchor=west] at (0.55, 1.5)113 {$\mat{Q}\mat{K}\transp \in \R^{n \times m}$};114 \node[etiquette, anchor=west, align=left] at (1.75, 5.1)115 {weights $\alpha_{ij}$,\\rows sum to $1$};116 \node[etiquette, anchor=west] at (0.55, 6.9)117 {$\in \R^{n \times d_v}$};118 \node[etiquette, anchor=north] at (4.6, -0.55)119 {$\R^{m \times d_v}$};120 \node[etiquette, anchor=north] at (-1.4, -0.55) {$\R^{n \times d_k}$};121 \node[etiquette, anchor=north] at ( 1.4, -0.55) {$\R^{m \times d_k}$};122 \end{tikzpicture}123 \caption{Computational flow of scaled dot-product attention,124 equation~\eqref{eq:att-sdpa}. Queries and keys meet in a matrix product,125 the scores are rescaled by $1/\sqrt{d_k}$, optionally masked126 (Section~\ref{sec:att-block}), normalized row-wise by a softmax, and the127 resulting weights average the values.}128 \label{fig:att-sdpa-flow}129\end{figure}130131\subsection{Why the factor \texorpdfstring{$1/\sqrt{d_k}$}{1/sqrt(dk)}?}132133The scaling factor is not cosmetic; without it, training destabilizes as134$d_k$ grows. The reason is a simple variance computation.135136\begin{property}[Variance of a dot product]\label{prop:att-variance}137Let $\vect{q}, \vect{k} \in \R^{d_k}$ have independent components with138$\E[q_i] = \E[k_i] = 0$ and $\E[q_i^2] = \E[k_i^2] = 1$. Then the dot139product $s = \vect{q}\transp\vect{k}$ satisfies140\begin{equation}141 \E[s] = 0,142 \qquad143 \operatorname{Var}(s)144 = \sum_{i=1}^{d_k} \E[q_i^2]\,\E[k_i^2]145 = d_k .146 \label{eq:att-variance}147\end{equation}148Hence $s/\sqrt{d_k}$ has unit variance, independently of $d_k$.149\end{property}150151\begin{proof}152By independence, $\E[s] = \sum_i \E[q_i]\E[k_i] = 0$. The terms $q_i k_i$153are uncorrelated with mean zero, so154$\operatorname{Var}(s) = \sum_i \E[q_i^2 k_i^2]155 = \sum_i \E[q_i^2]\,\E[k_i^2] = d_k$.156\end{proof}157158The consequence for \eqref{eq:att-alpha} is direct. With the typical head159dimension $d_k = 64$, unscaled logits would have standard deviation160$\sqrt{64} = 8$: the softmax would saturate, placing almost all mass on the161single largest score. In the saturated regime the Jacobian of the softmax is162nearly zero, so the gradients flowing back into $\mat{Q}$ and $\mat{K}$163vanish and the attention pattern stops learning. Dividing by $\sqrt{d_k}$164keeps the logits at unit variance regardless of the head width, holding the165softmax in its responsive regime throughout training \cite{vaswani2017}.166167\begin{remark}168Attention imposes no notion of distance: position $1$ reaches position169$10\,000$ exactly as easily as its neighbour. This is the source of the170Transformer's $O(1)$ maximum path length — and also the reason position171information must be injected explicitly172(Section~\ref{sec:att-positional}).173\end{remark}174175% ----------------------------------------------------------------------------176\section{Multi-Head Attention}\label{sec:att-multihead}177% ----------------------------------------------------------------------------178179A single attention map forces one pattern of interaction per layer: each180query produces one distribution over source positions, and all $d_v$181channels of the output are averaged with those same weights. The182Transformer instead projects queries, keys and values into $h$183lower-dimensional subspaces and runs attention in each subspace in184parallel. With learned projection matrices185$\mat{W}_i^Q \in \R^{d_{\text{model}} \times d_k}$,186$\mat{W}_i^K \in \R^{d_{\text{model}} \times d_k}$ and187$\mat{W}_i^V \in \R^{d_{\text{model}} \times d_v}$, head $i$ computes188\begin{equation}189 \mathrm{head}_i190 \;=\;191 \mathrm{Attention}\big( \mat{Q}\mat{W}_i^Q,\;192 \mat{K}\mat{W}_i^K,\;193 \mat{V}\mat{W}_i^V \big),194 \qquad i = 1, \dots, h,195 \label{eq:att-head}196\end{equation}197and the heads are concatenated and mixed by an output matrix198$\mat{W}^O \in \R^{h d_v \times d_{\text{model}}}$:199\begin{equation}200 \mathrm{MultiHead}(\mat{Q}, \mat{K}, \mat{V})201 \;=\;202 \mathrm{Concat}\big( \mathrm{head}_1, \dots, \mathrm{head}_h \big)\,203 \mat{W}^O .204 \label{eq:att-multihead}205\end{equation}206207In the base model of \cite{vaswani2017}, $h = 8$ and208$d_k = d_v = d_{\text{model}}/h = 512/8 = 64$, so the total computational209cost matches that of single-head attention at full width. What multi-head210buys is expressive diversity: because each head owns its own projections211\eqref{eq:att-head}, different heads can attend according to different212criteria at the same time — one tracking short-range syntax, another213long-range agreement, another positional neighbourhoods. Empirically, heads214do specialize in this way, and the concatenation215\eqref{eq:att-multihead} lets the next layer combine their findings.216217% ----------------------------------------------------------------------------218\section{Positional Encoding}\label{sec:att-positional}219% ----------------------------------------------------------------------------220221Equations \eqref{eq:att-sdpa}--\eqref{eq:att-multihead} are permutation222\emph{equivariant}: shuffling the rows of the inputs merely shuffles the223rows of the output. Word order — the backbone of syntax — is invisible to224the mechanism. The Transformer therefore adds a deterministic225\emph{positional encoding} to the token embeddings before the first layer.226For position $pos$ and dimension pair index $i$, the sinusoidal encoding227of \cite{vaswani2017} is228\begin{align}229 PE_{(pos,\, 2i)} &= \sin\!\left( \frac{pos}{10000^{2i/d_{\text{model}}}} \right),230 \label{eq:att-pe-sin} \\231 PE_{(pos,\, 2i+1)} &= \cos\!\left( \frac{pos}{10000^{2i/d_{\text{model}}}} \right).232 \label{eq:att-pe-cos}233\end{align}234Each coordinate pair traces a sinusoid whose wavelength grows geometrically235from $2\pi$ to $10000 \cdot 2\pi$ as $i$ increases: low dimensions236oscillate rapidly and resolve fine position differences, high dimensions237vary slowly and encode coarse position.238239\begin{property}[Relative positions are linear]\label{prop:att-pe-linear}240For any fixed offset $k$, the pair of components $PE_{(pos+k,\,2i)}$ and241$PE_{(pos+k,\,2i+1)}$ is obtained from the pair $PE_{(pos,\,2i)}$ and242$PE_{(pos,\,2i+1)}$ by a rotation whose angle243depends only on $k$ and $i$ — a consequence of the angle-addition formulas244for sine and cosine. Relative displacement is therefore a fixed245\emph{linear} map of the encoding, which a learned projection can pick up246easily.247\end{property}248249\begin{remark}250The sinusoidal scheme requires no learned parameters and extends, in251principle, to sequence lengths never seen in training. Learned absolute252position embeddings are an equally common alternative; they trade253extrapolation for flexibility.254\end{remark}255256% ----------------------------------------------------------------------------257\section{The Transformer Block}\label{sec:att-block}258% ----------------------------------------------------------------------------259260Attention alone is a weighted average — a linear operation for fixed261weights. The Transformer interleaves it with three further ingredients:262residual connections, layer normalization, and a position-wise263feed-forward network. Each sub-layer (attention or feed-forward) is wrapped264as265\begin{equation}266 \vect{x} \;\longmapsto\;267 \mathrm{LayerNorm}\big( \vect{x} + \mathrm{Sublayer}(\vect{x}) \big),268 \label{eq:att-addnorm}269\end{equation}270the ``Add \& Norm'' of the diagrams: the residual sum preserves a direct271gradient path through the depth of the stack, and the normalization,272\begin{equation}273 \mathrm{LayerNorm}(\vect{x})274 \;=\;275 \vect{\gamma} \odot \frac{\vect{x} - \mu}{\sigma} + \vect{\beta},276 \qquad277 \mu = \frac{1}{d}\sum_{i=1}^{d} x_i,278 \quad279 \sigma^2 = \frac{1}{d}\sum_{i=1}^{d} (x_i - \mu)^2,280 \label{eq:att-layernorm}281\end{equation}282computed over the feature dimension of each position independently, keeps283activations at a stable scale no matter the sequence length or batch284composition. Between the attention sub-layers sits a two-layer network285applied identically — and independently — at every position:286\begin{equation}287 \mathrm{FFN}(\vect{x})288 \;=\;289 \max\big( \vect{0},\; \vect{x}\mat{W}_1 + \vect{b}_1 \big)\, \mat{W}_2290 + \vect{b}_2,291 \label{eq:att-ffn}292\end{equation}293with an inner dimension $d_{f\!f} = 2048$, a fourfold expansion over294$d_{\text{model}} = 512$ \cite{vaswani2017}. If attention is where295positions \emph{communicate}, the FFN \eqref{eq:att-ffn} is where each296position \emph{computes} on what it has gathered.297298\begin{remark}[Pre-LN versus post-LN]299Equation~\eqref{eq:att-addnorm} is the original ``post-LN'' arrangement.300Most modern implementations normalize \emph{before} the sub-layer301($\vect{x} + \mathrm{Sublayer}(\mathrm{LayerNorm}(\vect{x}))$), which302keeps the residual path entirely free of normalization and trains more303stably at large depth.304\end{remark}305306\subsection{The causal mask}307308A language model generating text left to right must not let position $i$309peek at positions $j > i$: prediction of the next token would otherwise be310trivial in training and impossible at inference. Autoregressive decoding is311enforced \emph{inside} the attention by adding a mask matrix312$\mat{M} \in \R^{n \times n}$ to the scaled scores,313\begin{equation}314 M_{ij}315 \;=\;316 \begin{cases}317 0 & \text{if } j \le i, \\[2pt]318 -\infty & \text{if } j > i,319 \end{cases}320 \label{eq:att-mask}321\end{equation}322so that masked attention reads323\begin{equation}324 \mathrm{MaskedAttention}(\mat{Q}, \mat{K}, \mat{V})325 \;=\;326 \softmax\!\left( \frac{\mat{Q}\mat{K}\transp}{\sqrt{d_k}} + \mat{M}327 \right) \mat{V}.328 \label{eq:att-masked}329\end{equation}330The $-\infty$ entries become exact zeros after the softmax331\eqref{eq:att-alpha}, so each position attends only to itself and its past.332This is the ``Mask (optional)'' stage of Figure~\ref{fig:att-sdpa-flow}.333334% ----------------------------------------------------------------------------335\section{The Complete Encoder--Decoder Architecture}\label{sec:att-arch}336% ----------------------------------------------------------------------------337338The full Transformer of \cite{vaswani2017}, designed for339sequence-to-sequence tasks such as translation, assembles these pieces into340the two-column architecture of Figure~\ref{fig:att-transformer}.341342\begin{itemize}343 \item \textbf{Encoder} (left column): the input tokens are embedded,344 positional encodings \eqref{eq:att-pe-sin}--\eqref{eq:att-pe-cos} are345 added, and the result passes through a stack of $N = 6$ identical346 layers. Each layer applies multi-head \emph{self}-attention347 \eqref{eq:att-multihead} — every input position attends to every other348 — followed by the feed-forward network \eqref{eq:att-ffn}, each wrapped349 in Add \& Norm \eqref{eq:att-addnorm}.350 \item \textbf{Decoder} (right column): the output tokens, shifted right351 by one position, are embedded and encoded likewise, then pass through352 $N = 6$ layers of \emph{three} sub-layers each: masked self-attention353 \eqref{eq:att-masked}, which respects causality; \emph{cross}-attention,354 whose queries come from the decoder while keys and values come from355 the encoder output (the $\mat{K}, \mat{V}$ arrow in356 Figure~\ref{fig:att-transformer}); and the feed-forward network.357 \item \textbf{Head}: a final linear projection to vocabulary size and a358 softmax produce the next-token distribution.359\end{itemize}360361Cross-attention is where the two columns meet: each partially generated362target position formulates a query, and retrieves from the source sequence363the content most relevant to producing the next token — a learned,364differentiable alignment between input and output.365366At inference time the decoder is run autoregressively: the source is367encoded once, and tokens are emitted one at a time, each new token being368appended to the prefix that conditions the next step.369Algorithm~\ref{alg:att-decode} states the greedy variant, which commits at370every step to the most probable token; beam search generalizes it by371carrying the $B$ most probable prefixes instead of one.372373\begin{algorithm}[htbp]374 \caption{Greedy autoregressive decoding with a Transformer}375 \label{alg:att-decode}376 \begin{algorithmic}[1]377 \Require source tokens $(x_1, \dots, x_{T_x})$, trained encoder--decoder,378 maximum length $T_{\max}$379 \State $\mat{H}_{\mathrm{enc}} \gets380 \mathrm{Encoder}(x_1, \dots, x_{T_x})$381 \Comment{encode the source once; reused at every step}382 \State $\vect{y} \gets (\langle\mathrm{BOS}\rangle)$383 \Comment{generated prefix}384 \For{$t = 1, \dots, T_{\max}$}385 \State $\mat{Z} \gets$ embed $\vect{y}$ and add positional386 encodings \eqref{eq:att-pe-sin}--\eqref{eq:att-pe-cos}387 \State $\mat{Z} \gets$ decoder stack applied to $\mat{Z}$:388 masked self-attention \eqref{eq:att-masked},389 cross-attention on $\mat{H}_{\mathrm{enc}}$, FFN390 \eqref{eq:att-ffn}, each with Add \& Norm \eqref{eq:att-addnorm}391 \State $\vect{p} \gets \softmax\!\left(\mat{W}_{\mathrm{vocab}}\,392 \vect{z}_t + \vect{b}\right)$393 \Comment{$\vect{z}_t$: last position of $\mat{Z}$}394 \State $y_{t} \gets \argmax_{v}\; p_v$395 \State append $y_t$ to $\vect{y}$396 \If{$y_t = \langle\mathrm{EOS}\rangle$} \State \textbf{break}397 \EndIf398 \EndFor399 \State \Return $\vect{y}$400 \end{algorithmic}401\end{algorithm}402403\begin{figure}[p]404 \centering405 \begin{tikzpicture}[font=\small]406 % ================= ENCODER column =================407 \node[etiquette] (enc-in) at (0, -0.15) {Inputs};408 \node[blocinput, minimum width=3.2cm] (enc-emb) at (0, 0.9) {Input Embedding};409 \node[op] (enc-pe) at (0, 2.0) {$+$};410 \node[etiquette, align=center] at (-1.75, 2.0) {Positional\\Encoding};411 \node[blochidden, minimum width=3.4cm, align=center] (enc-attn) at (0, 3.5)412 {Multi-Head\\Self-Attention};413 \node[bloc, minimum width=3.4cm] (enc-an1) at (0, 4.9) {Add \& Norm};414 \node[blochidden, minimum width=3.4cm] (enc-ffn) at (0, 6.1) {Feed-Forward};415 \node[bloc, minimum width=3.4cm] (enc-an2) at (0, 7.3) {Add \& Norm};416 % main arrows (encoder)417 \draw[fleche] (enc-in) -- (enc-emb);418 \draw[fleche] (enc-emb) -- (enc-pe);419 \draw[fleche] (enc-pe) -- (enc-attn);420 \draw[fleche] (enc-attn)-- (enc-an1);421 \draw[fleche] (enc-an1) -- (enc-ffn);422 \draw[fleche] (enc-ffn) -- (enc-an2);423 % residual arcs (outer/left side)424 \draw[fleche, semithick, rounded corners=2pt]425 (0, 2.72) -- (-2.35, 2.72) -- (-2.35, 4.9) -- (enc-an1.west);426 \draw[fleche, semithick, rounded corners=2pt]427 (0, 5.5) -- (-2.35, 5.5) -- (-2.35, 7.3) -- (enc-an2.west);428 % encoder frame (xN)429 \coordinate (enc-fit-w) at (-2.6, 4.9);430 \begin{scope}[on background layer]431 \node[draw=black!55, rounded corners=4pt, fill=chidden!6, inner sep=9pt,432 fit=(enc-attn)(enc-an1)(enc-ffn)(enc-an2)(enc-fit-w)]433 (encframe) {};434 \end{scope}435 \node[font=\small\bfseries, anchor=east] at ($(encframe.west)+(-0.12,0)$)436 {$\times N$};437 % ================= DECODER column =================438 \node[etiquette, align=center] (dec-in) at (7.4, -0.15)439 {Outputs (shifted right)};440 \node[blocinput, minimum width=3.2cm] (dec-emb) at (7.4, 0.9) {Output Embedding};441 \node[op] (dec-pe) at (7.4, 2.0) {$+$};442 \node[etiquette, align=center] at (9.15, 2.0) {Positional\\Encoding};443 \node[blochidden, minimum width=3.4cm, align=center] (dec-attn) at (7.4, 3.5)444 {Masked Multi-Head\\Self-Attention};445 \node[bloc, minimum width=3.4cm] (dec-an1) at (7.4, 4.9) {Add \& Norm};446 \node[blochidden, minimum width=3.4cm, align=center] (dec-cross) at (7.4, 6.3)447 {Multi-Head\\Cross-Attention};448 \node[bloc, minimum width=3.4cm] (dec-an2) at (7.4, 7.7) {Add \& Norm};449 \node[blochidden, minimum width=3.4cm] (dec-ffn) at (7.4, 8.9) {Feed-Forward};450 \node[bloc, minimum width=3.4cm] (dec-an3) at (7.4, 10.1) {Add \& Norm};451 \node[blocoutput, minimum width=3.4cm] (dec-lin) at (7.4, 11.4) {Linear};452 \node[blocoutput, minimum width=3.4cm] (dec-sm) at (7.4, 12.5) {$\softmax$};453 \node[etiquette] (dec-out) at (7.4, 13.45) {Output probabilities};454 % main arrows (decoder)455 \draw[fleche] (dec-in) -- (dec-emb);456 \draw[fleche] (dec-emb) -- (dec-pe);457 \draw[fleche] (dec-pe) -- (dec-attn);458 \draw[fleche] (dec-attn) -- (dec-an1);459 \draw[fleche] (dec-an1) -- (dec-cross);460 \draw[fleche] (dec-cross)-- (dec-an2);461 \draw[fleche] (dec-an2) -- (dec-ffn);462 \draw[fleche] (dec-ffn) -- (dec-an3);463 \draw[fleche] (dec-an3) -- (dec-lin);464 \draw[fleche] (dec-lin) -- (dec-sm);465 \draw[fleche] (dec-sm) -- (dec-out);466 % residual arcs (outer/right side)467 \draw[fleche, semithick, rounded corners=2pt]468 (7.4, 2.72) -- (9.75, 2.72) -- (9.75, 4.9) -- (dec-an1.east);469 \draw[fleche, semithick, rounded corners=2pt]470 (7.4, 5.5) -- (9.75, 5.5) -- (9.75, 7.7) -- (dec-an2.east);471 \draw[fleche, semithick, rounded corners=2pt]472 (7.4, 8.3) -- (9.75, 8.3) -- (9.75, 10.1) -- (dec-an3.east);473 % decoder frame (xN)474 \coordinate (dec-fit-e) at (10.0, 6.3);475 \begin{scope}[on background layer]476 \node[draw=black!55, rounded corners=4pt, fill=chidden!6, inner sep=9pt,477 fit=(dec-attn)(dec-an1)(dec-cross)(dec-an2)(dec-ffn)(dec-an3)(dec-fit-e)]478 (decframe) {};479 \end{scope}480 \node[font=\small\bfseries, anchor=west] at ($(decframe.east)+(0.12,0)$)481 {$\times N$};482 % ================= K,V bridge encoder -> decoder =================483 \draw[fleche, rounded corners=3pt]484 (enc-an2.north) -- (0, 8.6) -- (3.6, 8.6) -- (3.6, 6.3)485 -- (dec-cross.west);486 \node[etiquette, anchor=south] at (1.8, 8.63) {$\mat{K},\ \mat{V}$ (encoder output)};487 \end{tikzpicture}488 \caption{The complete Transformer encoder--decoder architecture489 \cite{vaswani2017}. Left: the encoder — embedding, positional encoding490 \eqref{eq:att-pe-sin}--\eqref{eq:att-pe-cos}, then $N$ identical layers491 of self-attention and feed-forward, each wrapped in Add \& Norm492 \eqref{eq:att-addnorm} with the residual paths drawn as outer arcs.493 Right: the decoder — masked self-attention \eqref{eq:att-masked},494 cross-attention receiving keys and values $\mat{K}, \mat{V}$ from the495 encoder output, feed-forward, then a linear layer and softmax producing496 the next-token distribution.}497 \label{fig:att-transformer}498\end{figure}499500% ----------------------------------------------------------------------------501\section{Computational Complexity}\label{sec:att-complexity}502% ----------------------------------------------------------------------------503504For sequence length $n$ and model dimension $d$, the score matrix505$\mat{Q}\mat{K}\transp$ of \eqref{eq:att-sdpa} costs $O(n^2 d)$ time and506$O(n^2)$ memory per layer: self-attention is \emph{quadratic in sequence507length}. The feed-forward network \eqref{eq:att-ffn}, by contrast, costs508$O(n d^2)$ — linear in $n$ but quadratic in width. Which term dominates509depends on the regime: for $n < d$ (short sequences, wide models) the FFN510dominates; for long contexts the $n^2$ term takes over and becomes the511principal obstacle, motivating an entire literature of sparse,512low-rank and IO-aware attention variants. Table~\ref{tab:att-complexity}513compares the layer types on the three axes emphasized in514\cite{vaswani2017}: total computation, sequential operations (the obstacle515to parallelism), and maximum path length between two positions (the516obstacle to learning long-range dependencies).517518\begin{table}[htbp]519 \centering520 \caption{Per-layer complexity for sequence length $n$, representation521 dimension $d$ and convolution kernel size $k$ \cite{vaswani2017}.}522 \label{tab:att-complexity}523 \begin{tabular}{lccc}524 \toprule525 Layer type & Complexity per layer & Sequential ops & Max path length \\526 \midrule527 Self-attention & $O(n^2 \, d)$ & $O(1)$ & $O(1)$ \\528 Recurrent & $O(n \, d^2)$ & $O(n)$ & $O(n)$ \\529 Convolutional & $O(k \, n \, d^2)$ & $O(1)$ & $O(\log_k n)$ \\530 \bottomrule531 \end{tabular}532\end{table}533534The trade the Transformer makes is explicit in the first row: it pays a535quadratic compute bill in exchange for constant-depth parallelism and536constant-length interaction paths. For the sequence lengths of machine537translation this trade was decisively favourable, and hardware trends —538matrix units that reward dense, regular computation — have only widened539the advantage since.540541% ----------------------------------------------------------------------------542\section{Model Families: BERT, GPT, T5}\label{sec:att-families}543% ----------------------------------------------------------------------------544545The encoder--decoder of Figure~\ref{fig:att-transformer} contains two546self-sufficient halves, and the field promptly split it apart. Three547canonical families resulted, distinguished by which half they keep and by548their pre-training objective (Table~\ref{tab:att-families}).549550\textbf{BERT} keeps only the \emph{encoder}: attention is bidirectional,551every position sees the whole sequence. It is pre-trained by masked552language modelling — a fraction of input tokens is hidden and must be553reconstructed from both sides of context — which makes it a powerful text554\emph{understanding} machine (classification, retrieval, extraction) but555not a generator.556557\textbf{GPT} keeps only the \emph{decoder}: every layer uses the causal558mask \eqref{eq:att-mask}, and pre-training maximizes the autoregressive559log-likelihood $\sum_t \log p_\theta(x_t \mid x_{<t})$. Generation is560native — sampling one token at a time — and scaling this single recipe to561ever larger models produced the modern lineage of large language models.562563\textbf{T5} keeps \emph{both} halves and casts every task — translation,564summarization, classification, question answering — as text-to-text, with565a span-corruption pre-training objective in which contiguous spans are566masked and regenerated by the decoder.567568\begin{table}[htbp]569 \centering570 \caption{The three canonical Transformer families.}571 \label{tab:att-families}572 \begin{tabular}{llll}573 \toprule574 Family & Architecture & Pre-training objective & Typical use \\575 \midrule576 BERT & Encoder only & Masked language modelling & Understanding \\577 GPT & Decoder only & Next-token prediction & Generation \\578 T5 & Encoder--decoder & Span corruption & Text-to-text \\579 \bottomrule580 \end{tabular}581\end{table}582583Whatever the family, the interior is the same handful of equations: scaled584dot-product attention \eqref{eq:att-sdpa} with its variance-controlled585logits \eqref{eq:att-variance}, multiple heads586\eqref{eq:att-head}--\eqref{eq:att-multihead}, positional information587\eqref{eq:att-pe-sin}--\eqref{eq:att-pe-cos}, and the residual--normalized588block \eqref{eq:att-addnorm}--\eqref{eq:att-ffn}. Few architectures in the589history of the field have combined such simplicity of definition with such590range of consequence.591