% ============================================================================ % Artificial Neural Networks — Methods, Equations and Graphical % Representations % Author : Simon-Pierre Boucher — contact@spboucher.ai % Chapter 6 : Attention and Transformers (chapters/06-attention.tex) % ============================================================================ \chapter{Attention and Transformers}\label{chap:attention} Recurrent networks process a sequence one position at a time: the hidden state is a bottleneck through which all past information must flow, training cannot be parallelized along the time axis, and interactions between distant positions must survive a long chain of state updates. The Transformer \cite{vaswani2017} removed this bottleneck in a single stroke. It dispenses entirely with recurrence and convolution, and models every pairwise interaction between sequence positions \emph{directly}, through a mechanism called \emph{attention}. Every position can consult every other position in one step, the whole computation is expressed as a handful of dense matrix products that parallelize perfectly, and the maximum path length between any two positions drops to $O(1)$. This chapter builds the architecture from its smallest component — the scaled dot-product — to the complete encoder--decoder stack, and closes with the computational trade-offs and the three model families (BERT, GPT, T5) that grew out of it. % ---------------------------------------------------------------------------- \section{From Recurrence to Attention} % ---------------------------------------------------------------------------- The guiding intuition is retrieval. Suppose each position of a sequence emits a \emph{query} describing the information it is looking for, while every position also exposes a \emph{key} describing the information it holds, together with a \emph{value} carrying the actual content. Attention answers each query by comparing it against all keys, converting the similarity scores into weights, and returning the corresponding weighted average of the values. The result is a \emph{soft} dictionary lookup: fully differentiable, so it can be trained end to end by the backpropagation machinery of the earlier chapters, and content-based, so the pattern of interaction is decided by the data rather than fixed by the architecture. Formally, we work with three matrices: queries $\mat{Q} \in \R^{n \times d_k}$, keys $\mat{K} \in \R^{m \times d_k}$ and values $\mat{V} \in \R^{m \times d_v}$, where $n$ is the number of query positions, $m$ the number of key--value positions, $d_k$ the dimension in which queries and keys are compared, and $d_v$ the dimension of the returned content. In \emph{self-attention}, all three are linear projections of the same sequence ($m = n$); in \emph{cross-attention}, queries come from one sequence and keys/values from another. % ---------------------------------------------------------------------------- \section{Scaled Dot-Product Attention}\label{sec:att-sdpa} % ---------------------------------------------------------------------------- \begin{definition}[Scaled dot-product attention]\label{def:att-sdpa} Given $\mat{Q} \in \R^{n \times d_k}$, $\mat{K} \in \R^{m \times d_k}$ and $\mat{V} \in \R^{m \times d_v}$, scaled dot-product attention is the map \begin{equation} \mathrm{Attention}(\mat{Q}, \mat{K}, \mat{V}) \;=\; \softmax\!\left( \frac{\mat{Q}\mat{K}\transp}{\sqrt{d_k}} \right) \mat{V} \;\in\; \R^{n \times d_v}, \label{eq:att-sdpa} \end{equation} where the softmax is applied row-wise \cite{vaswani2017}. \end{definition} Reading \eqref{eq:att-sdpa} from the inside out: the Gram matrix $\mat{Q}\mat{K}\transp \in \R^{n \times m}$ collects all $n \times m$ dot products between queries and keys; dividing by $\sqrt{d_k}$ rescales these similarity scores; the row-wise softmax turns each row into a probability distribution over the $m$ source positions; and the final product with $\mat{V}$ computes, for each query, the corresponding convex combination of value vectors. Writing $\vect{q}_i$ for the $i$-th query and $\vect{k}_j, \vect{v}_j$ for the $j$-th key and value, the attention weight that position $i$ places on position $j$ is \begin{equation} \alpha_{ij} \;=\; \frac{\exp\!\big( \vect{q}_i\transp \vect{k}_j / \sqrt{d_k} \big)} {\sum_{j'=1}^{m} \exp\!\big( \vect{q}_i\transp \vect{k}_{j'} / \sqrt{d_k} \big)}, \qquad \sum_{j=1}^{m} \alpha_{ij} = 1, \label{eq:att-alpha} \end{equation} and the $i$-th output row is $\sum_j \alpha_{ij}\vect{v}_j$. The whole computation is displayed in Figure~\ref{fig:att-sdpa-flow}. \begin{figure}[htbp] \centering \begin{tikzpicture}[font=\small] % --- input blocks --- \node[blocinput, minimum width=1.2cm] (Q) at (-1.4, 0) {$\mat{Q}$}; \node[blocinput, minimum width=1.2cm] (K) at ( 1.4, 0) {$\mat{K}$}; \node[blocinput, minimum width=1.2cm] (V) at ( 4.6, 0) {$\mat{V}$}; % --- pipeline --- \node[op] (mm1) at (0, 1.5) {$\times$}; \node[bloc, minimum width=2.7cm] (scale) at (0, 2.7) {Scale by $1/\sqrt{d_k}$}; \node[bloc, minimum width=2.7cm, dashed] (mask) at (0, 3.9) {Mask (optional)}; \node[gate, minimum width=2.7cm] (sm) at (0, 5.1) {$\softmax$ (row-wise)}; \node[op] (mm2) at (0, 6.4) {$\times$}; \node[blocoutput, minimum width=3.4cm] (out) at (0, 7.6) {$\mathrm{Attention}(\mat{Q},\mat{K},\mat{V})$}; % --- arrows --- \draw[fleche] (Q) -- (mm1); \draw[fleche] (K) -- (mm1); \draw[fleche] (mm1) -- (scale); \draw[fleche] (scale)-- (mask); \draw[fleche] (mask) -- (sm); \draw[fleche] (sm) -- (mm2); \draw[fleche, rounded corners=3pt] (V.north) -- (4.6, 6.4) -- (mm2); \draw[fleche] (mm2) -- (out); % --- annotations --- \node[etiquette, anchor=west] at (0.55, 1.5) {$\mat{Q}\mat{K}\transp \in \R^{n \times m}$}; \node[etiquette, anchor=west, align=left] at (1.75, 5.1) {weights $\alpha_{ij}$,\\rows sum to $1$}; \node[etiquette, anchor=west] at (0.55, 6.9) {$\in \R^{n \times d_v}$}; \node[etiquette, anchor=north] at (4.6, -0.55) {$\R^{m \times d_v}$}; \node[etiquette, anchor=north] at (-1.4, -0.55) {$\R^{n \times d_k}$}; \node[etiquette, anchor=north] at ( 1.4, -0.55) {$\R^{m \times d_k}$}; \end{tikzpicture} \caption{Computational flow of scaled dot-product attention, equation~\eqref{eq:att-sdpa}. Queries and keys meet in a matrix product, the scores are rescaled by $1/\sqrt{d_k}$, optionally masked (Section~\ref{sec:att-block}), normalized row-wise by a softmax, and the resulting weights average the values.} \label{fig:att-sdpa-flow} \end{figure} \subsection{Why the factor \texorpdfstring{$1/\sqrt{d_k}$}{1/sqrt(dk)}?} The scaling factor is not cosmetic; without it, training destabilizes as $d_k$ grows. The reason is a simple variance computation. \begin{property}[Variance of a dot product]\label{prop:att-variance} Let $\vect{q}, \vect{k} \in \R^{d_k}$ have independent components with $\E[q_i] = \E[k_i] = 0$ and $\E[q_i^2] = \E[k_i^2] = 1$. Then the dot product $s = \vect{q}\transp\vect{k}$ satisfies \begin{equation} \E[s] = 0, \qquad \operatorname{Var}(s) = \sum_{i=1}^{d_k} \E[q_i^2]\,\E[k_i^2] = d_k . \label{eq:att-variance} \end{equation} Hence $s/\sqrt{d_k}$ has unit variance, independently of $d_k$. \end{property} \begin{proof} By independence, $\E[s] = \sum_i \E[q_i]\E[k_i] = 0$. The terms $q_i k_i$ are uncorrelated with mean zero, so $\operatorname{Var}(s) = \sum_i \E[q_i^2 k_i^2] = \sum_i \E[q_i^2]\,\E[k_i^2] = d_k$. \end{proof} The consequence for \eqref{eq:att-alpha} is direct. With the typical head dimension $d_k = 64$, unscaled logits would have standard deviation $\sqrt{64} = 8$: the softmax would saturate, placing almost all mass on the single largest score. In the saturated regime the Jacobian of the softmax is nearly zero, so the gradients flowing back into $\mat{Q}$ and $\mat{K}$ vanish and the attention pattern stops learning. Dividing by $\sqrt{d_k}$ keeps the logits at unit variance regardless of the head width, holding the softmax in its responsive regime throughout training \cite{vaswani2017}. \begin{remark} Attention imposes no notion of distance: position $1$ reaches position $10\,000$ exactly as easily as its neighbour. This is the source of the Transformer's $O(1)$ maximum path length — and also the reason position information must be injected explicitly (Section~\ref{sec:att-positional}). \end{remark} % ---------------------------------------------------------------------------- \section{Multi-Head Attention}\label{sec:att-multihead} % ---------------------------------------------------------------------------- A single attention map forces one pattern of interaction per layer: each query produces one distribution over source positions, and all $d_v$ channels of the output are averaged with those same weights. The Transformer instead projects queries, keys and values into $h$ lower-dimensional subspaces and runs attention in each subspace in parallel. With learned projection matrices $\mat{W}_i^Q \in \R^{d_{\text{model}} \times d_k}$, $\mat{W}_i^K \in \R^{d_{\text{model}} \times d_k}$ and $\mat{W}_i^V \in \R^{d_{\text{model}} \times d_v}$, head $i$ computes \begin{equation} \mathrm{head}_i \;=\; \mathrm{Attention}\big( \mat{Q}\mat{W}_i^Q,\; \mat{K}\mat{W}_i^K,\; \mat{V}\mat{W}_i^V \big), \qquad i = 1, \dots, h, \label{eq:att-head} \end{equation} and the heads are concatenated and mixed by an output matrix $\mat{W}^O \in \R^{h d_v \times d_{\text{model}}}$: \begin{equation} \mathrm{MultiHead}(\mat{Q}, \mat{K}, \mat{V}) \;=\; \mathrm{Concat}\big( \mathrm{head}_1, \dots, \mathrm{head}_h \big)\, \mat{W}^O . \label{eq:att-multihead} \end{equation} In the base model of \cite{vaswani2017}, $h = 8$ and $d_k = d_v = d_{\text{model}}/h = 512/8 = 64$, so the total computational cost matches that of single-head attention at full width. What multi-head buys is expressive diversity: because each head owns its own projections \eqref{eq:att-head}, different heads can attend according to different criteria at the same time — one tracking short-range syntax, another long-range agreement, another positional neighbourhoods. Empirically, heads do specialize in this way, and the concatenation \eqref{eq:att-multihead} lets the next layer combine their findings. % ---------------------------------------------------------------------------- \section{Positional Encoding}\label{sec:att-positional} % ---------------------------------------------------------------------------- Equations \eqref{eq:att-sdpa}--\eqref{eq:att-multihead} are permutation \emph{equivariant}: shuffling the rows of the inputs merely shuffles the rows of the output. Word order — the backbone of syntax — is invisible to the mechanism. The Transformer therefore adds a deterministic \emph{positional encoding} to the token embeddings before the first layer. For position $pos$ and dimension pair index $i$, the sinusoidal encoding of \cite{vaswani2017} is \begin{align} PE_{(pos,\, 2i)} &= \sin\!\left( \frac{pos}{10000^{2i/d_{\text{model}}}} \right), \label{eq:att-pe-sin} \\ PE_{(pos,\, 2i+1)} &= \cos\!\left( \frac{pos}{10000^{2i/d_{\text{model}}}} \right). \label{eq:att-pe-cos} \end{align} Each coordinate pair traces a sinusoid whose wavelength grows geometrically from $2\pi$ to $10000 \cdot 2\pi$ as $i$ increases: low dimensions oscillate rapidly and resolve fine position differences, high dimensions vary slowly and encode coarse position. \begin{property}[Relative positions are linear]\label{prop:att-pe-linear} For any fixed offset $k$, the pair of components $PE_{(pos+k,\,2i)}$ and $PE_{(pos+k,\,2i+1)}$ is obtained from the pair $PE_{(pos,\,2i)}$ and $PE_{(pos,\,2i+1)}$ by a rotation whose angle depends only on $k$ and $i$ — a consequence of the angle-addition formulas for sine and cosine. Relative displacement is therefore a fixed \emph{linear} map of the encoding, which a learned projection can pick up easily. \end{property} \begin{remark} The sinusoidal scheme requires no learned parameters and extends, in principle, to sequence lengths never seen in training. Learned absolute position embeddings are an equally common alternative; they trade extrapolation for flexibility. \end{remark} % ---------------------------------------------------------------------------- \section{The Transformer Block}\label{sec:att-block} % ---------------------------------------------------------------------------- Attention alone is a weighted average — a linear operation for fixed weights. The Transformer interleaves it with three further ingredients: residual connections, layer normalization, and a position-wise feed-forward network. Each sub-layer (attention or feed-forward) is wrapped as \begin{equation} \vect{x} \;\longmapsto\; \mathrm{LayerNorm}\big( \vect{x} + \mathrm{Sublayer}(\vect{x}) \big), \label{eq:att-addnorm} \end{equation} the ``Add \& Norm'' of the diagrams: the residual sum preserves a direct gradient path through the depth of the stack, and the normalization, \begin{equation} \mathrm{LayerNorm}(\vect{x}) \;=\; \vect{\gamma} \odot \frac{\vect{x} - \mu}{\sigma} + \vect{\beta}, \qquad \mu = \frac{1}{d}\sum_{i=1}^{d} x_i, \quad \sigma^2 = \frac{1}{d}\sum_{i=1}^{d} (x_i - \mu)^2, \label{eq:att-layernorm} \end{equation} computed over the feature dimension of each position independently, keeps activations at a stable scale no matter the sequence length or batch composition. Between the attention sub-layers sits a two-layer network applied identically — and independently — at every position: \begin{equation} \mathrm{FFN}(\vect{x}) \;=\; \max\big( \vect{0},\; \vect{x}\mat{W}_1 + \vect{b}_1 \big)\, \mat{W}_2 + \vect{b}_2, \label{eq:att-ffn} \end{equation} with an inner dimension $d_{f\!f} = 2048$, a fourfold expansion over $d_{\text{model}} = 512$ \cite{vaswani2017}. If attention is where positions \emph{communicate}, the FFN \eqref{eq:att-ffn} is where each position \emph{computes} on what it has gathered. \begin{remark}[Pre-LN versus post-LN] Equation~\eqref{eq:att-addnorm} is the original ``post-LN'' arrangement. Most modern implementations normalize \emph{before} the sub-layer ($\vect{x} + \mathrm{Sublayer}(\mathrm{LayerNorm}(\vect{x}))$), which keeps the residual path entirely free of normalization and trains more stably at large depth. \end{remark} \subsection{The causal mask} A language model generating text left to right must not let position $i$ peek at positions $j > i$: prediction of the next token would otherwise be trivial in training and impossible at inference. Autoregressive decoding is enforced \emph{inside} the attention by adding a mask matrix $\mat{M} \in \R^{n \times n}$ to the scaled scores, \begin{equation} M_{ij} \;=\; \begin{cases} 0 & \text{if } j \le i, \\[2pt] -\infty & \text{if } j > i, \end{cases} \label{eq:att-mask} \end{equation} so that masked attention reads \begin{equation} \mathrm{MaskedAttention}(\mat{Q}, \mat{K}, \mat{V}) \;=\; \softmax\!\left( \frac{\mat{Q}\mat{K}\transp}{\sqrt{d_k}} + \mat{M} \right) \mat{V}. \label{eq:att-masked} \end{equation} The $-\infty$ entries become exact zeros after the softmax \eqref{eq:att-alpha}, so each position attends only to itself and its past. This is the ``Mask (optional)'' stage of Figure~\ref{fig:att-sdpa-flow}. % ---------------------------------------------------------------------------- \section{The Complete Encoder--Decoder Architecture}\label{sec:att-arch} % ---------------------------------------------------------------------------- The full Transformer of \cite{vaswani2017}, designed for sequence-to-sequence tasks such as translation, assembles these pieces into the two-column architecture of Figure~\ref{fig:att-transformer}. \begin{itemize} \item \textbf{Encoder} (left column): the input tokens are embedded, positional encodings \eqref{eq:att-pe-sin}--\eqref{eq:att-pe-cos} are added, and the result passes through a stack of $N = 6$ identical layers. Each layer applies multi-head \emph{self}-attention \eqref{eq:att-multihead} — every input position attends to every other — followed by the feed-forward network \eqref{eq:att-ffn}, each wrapped in Add \& Norm \eqref{eq:att-addnorm}. \item \textbf{Decoder} (right column): the output tokens, shifted right by one position, are embedded and encoded likewise, then pass through $N = 6$ layers of \emph{three} sub-layers each: masked self-attention \eqref{eq:att-masked}, which respects causality; \emph{cross}-attention, whose queries come from the decoder while keys and values come from the encoder output (the $\mat{K}, \mat{V}$ arrow in Figure~\ref{fig:att-transformer}); and the feed-forward network. \item \textbf{Head}: a final linear projection to vocabulary size and a softmax produce the next-token distribution. \end{itemize} Cross-attention is where the two columns meet: each partially generated target position formulates a query, and retrieves from the source sequence the content most relevant to producing the next token — a learned, differentiable alignment between input and output. At inference time the decoder is run autoregressively: the source is encoded once, and tokens are emitted one at a time, each new token being appended to the prefix that conditions the next step. Algorithm~\ref{alg:att-decode} states the greedy variant, which commits at every step to the most probable token; beam search generalizes it by carrying the $B$ most probable prefixes instead of one. \begin{algorithm}[htbp] \caption{Greedy autoregressive decoding with a Transformer} \label{alg:att-decode} \begin{algorithmic}[1] \Require source tokens $(x_1, \dots, x_{T_x})$, trained encoder--decoder, maximum length $T_{\max}$ \State $\mat{H}_{\mathrm{enc}} \gets \mathrm{Encoder}(x_1, \dots, x_{T_x})$ \Comment{encode the source once; reused at every step} \State $\vect{y} \gets (\langle\mathrm{BOS}\rangle)$ \Comment{generated prefix} \For{$t = 1, \dots, T_{\max}$} \State $\mat{Z} \gets$ embed $\vect{y}$ and add positional encodings \eqref{eq:att-pe-sin}--\eqref{eq:att-pe-cos} \State $\mat{Z} \gets$ decoder stack applied to $\mat{Z}$: masked self-attention \eqref{eq:att-masked}, cross-attention on $\mat{H}_{\mathrm{enc}}$, FFN \eqref{eq:att-ffn}, each with Add \& Norm \eqref{eq:att-addnorm} \State $\vect{p} \gets \softmax\!\left(\mat{W}_{\mathrm{vocab}}\, \vect{z}_t + \vect{b}\right)$ \Comment{$\vect{z}_t$: last position of $\mat{Z}$} \State $y_{t} \gets \argmax_{v}\; p_v$ \State append $y_t$ to $\vect{y}$ \If{$y_t = \langle\mathrm{EOS}\rangle$} \State \textbf{break} \EndIf \EndFor \State \Return $\vect{y}$ \end{algorithmic} \end{algorithm} \begin{figure}[p] \centering \begin{tikzpicture}[font=\small] % ================= ENCODER column ================= \node[etiquette] (enc-in) at (0, -0.15) {Inputs}; \node[blocinput, minimum width=3.2cm] (enc-emb) at (0, 0.9) {Input Embedding}; \node[op] (enc-pe) at (0, 2.0) {$+$}; \node[etiquette, align=center] at (-1.75, 2.0) {Positional\\Encoding}; \node[blochidden, minimum width=3.4cm, align=center] (enc-attn) at (0, 3.5) {Multi-Head\\Self-Attention}; \node[bloc, minimum width=3.4cm] (enc-an1) at (0, 4.9) {Add \& Norm}; \node[blochidden, minimum width=3.4cm] (enc-ffn) at (0, 6.1) {Feed-Forward}; \node[bloc, minimum width=3.4cm] (enc-an2) at (0, 7.3) {Add \& Norm}; % main arrows (encoder) \draw[fleche] (enc-in) -- (enc-emb); \draw[fleche] (enc-emb) -- (enc-pe); \draw[fleche] (enc-pe) -- (enc-attn); \draw[fleche] (enc-attn)-- (enc-an1); \draw[fleche] (enc-an1) -- (enc-ffn); \draw[fleche] (enc-ffn) -- (enc-an2); % residual arcs (outer/left side) \draw[fleche, semithick, rounded corners=2pt] (0, 2.72) -- (-2.35, 2.72) -- (-2.35, 4.9) -- (enc-an1.west); \draw[fleche, semithick, rounded corners=2pt] (0, 5.5) -- (-2.35, 5.5) -- (-2.35, 7.3) -- (enc-an2.west); % encoder frame (xN) \coordinate (enc-fit-w) at (-2.6, 4.9); \begin{scope}[on background layer] \node[draw=black!55, rounded corners=4pt, fill=chidden!6, inner sep=9pt, fit=(enc-attn)(enc-an1)(enc-ffn)(enc-an2)(enc-fit-w)] (encframe) {}; \end{scope} \node[font=\small\bfseries, anchor=east] at ($(encframe.west)+(-0.12,0)$) {$\times N$}; % ================= DECODER column ================= \node[etiquette, align=center] (dec-in) at (7.4, -0.15) {Outputs (shifted right)}; \node[blocinput, minimum width=3.2cm] (dec-emb) at (7.4, 0.9) {Output Embedding}; \node[op] (dec-pe) at (7.4, 2.0) {$+$}; \node[etiquette, align=center] at (9.15, 2.0) {Positional\\Encoding}; \node[blochidden, minimum width=3.4cm, align=center] (dec-attn) at (7.4, 3.5) {Masked Multi-Head\\Self-Attention}; \node[bloc, minimum width=3.4cm] (dec-an1) at (7.4, 4.9) {Add \& Norm}; \node[blochidden, minimum width=3.4cm, align=center] (dec-cross) at (7.4, 6.3) {Multi-Head\\Cross-Attention}; \node[bloc, minimum width=3.4cm] (dec-an2) at (7.4, 7.7) {Add \& Norm}; \node[blochidden, minimum width=3.4cm] (dec-ffn) at (7.4, 8.9) {Feed-Forward}; \node[bloc, minimum width=3.4cm] (dec-an3) at (7.4, 10.1) {Add \& Norm}; \node[blocoutput, minimum width=3.4cm] (dec-lin) at (7.4, 11.4) {Linear}; \node[blocoutput, minimum width=3.4cm] (dec-sm) at (7.4, 12.5) {$\softmax$}; \node[etiquette] (dec-out) at (7.4, 13.45) {Output probabilities}; % main arrows (decoder) \draw[fleche] (dec-in) -- (dec-emb); \draw[fleche] (dec-emb) -- (dec-pe); \draw[fleche] (dec-pe) -- (dec-attn); \draw[fleche] (dec-attn) -- (dec-an1); \draw[fleche] (dec-an1) -- (dec-cross); \draw[fleche] (dec-cross)-- (dec-an2); \draw[fleche] (dec-an2) -- (dec-ffn); \draw[fleche] (dec-ffn) -- (dec-an3); \draw[fleche] (dec-an3) -- (dec-lin); \draw[fleche] (dec-lin) -- (dec-sm); \draw[fleche] (dec-sm) -- (dec-out); % residual arcs (outer/right side) \draw[fleche, semithick, rounded corners=2pt] (7.4, 2.72) -- (9.75, 2.72) -- (9.75, 4.9) -- (dec-an1.east); \draw[fleche, semithick, rounded corners=2pt] (7.4, 5.5) -- (9.75, 5.5) -- (9.75, 7.7) -- (dec-an2.east); \draw[fleche, semithick, rounded corners=2pt] (7.4, 8.3) -- (9.75, 8.3) -- (9.75, 10.1) -- (dec-an3.east); % decoder frame (xN) \coordinate (dec-fit-e) at (10.0, 6.3); \begin{scope}[on background layer] \node[draw=black!55, rounded corners=4pt, fill=chidden!6, inner sep=9pt, fit=(dec-attn)(dec-an1)(dec-cross)(dec-an2)(dec-ffn)(dec-an3)(dec-fit-e)] (decframe) {}; \end{scope} \node[font=\small\bfseries, anchor=west] at ($(decframe.east)+(0.12,0)$) {$\times N$}; % ================= K,V bridge encoder -> decoder ================= \draw[fleche, rounded corners=3pt] (enc-an2.north) -- (0, 8.6) -- (3.6, 8.6) -- (3.6, 6.3) -- (dec-cross.west); \node[etiquette, anchor=south] at (1.8, 8.63) {$\mat{K},\ \mat{V}$ (encoder output)}; \end{tikzpicture} \caption{The complete Transformer encoder--decoder architecture \cite{vaswani2017}. Left: the encoder — embedding, positional encoding \eqref{eq:att-pe-sin}--\eqref{eq:att-pe-cos}, then $N$ identical layers of self-attention and feed-forward, each wrapped in Add \& Norm \eqref{eq:att-addnorm} with the residual paths drawn as outer arcs. Right: the decoder — masked self-attention \eqref{eq:att-masked}, cross-attention receiving keys and values $\mat{K}, \mat{V}$ from the encoder output, feed-forward, then a linear layer and softmax producing the next-token distribution.} \label{fig:att-transformer} \end{figure} % ---------------------------------------------------------------------------- \section{Computational Complexity}\label{sec:att-complexity} % ---------------------------------------------------------------------------- For sequence length $n$ and model dimension $d$, the score matrix $\mat{Q}\mat{K}\transp$ of \eqref{eq:att-sdpa} costs $O(n^2 d)$ time and $O(n^2)$ memory per layer: self-attention is \emph{quadratic in sequence length}. The feed-forward network \eqref{eq:att-ffn}, by contrast, costs $O(n d^2)$ — linear in $n$ but quadratic in width. Which term dominates depends on the regime: for $n < d$ (short sequences, wide models) the FFN dominates; for long contexts the $n^2$ term takes over and becomes the principal obstacle, motivating an entire literature of sparse, low-rank and IO-aware attention variants. Table~\ref{tab:att-complexity} compares the layer types on the three axes emphasized in \cite{vaswani2017}: total computation, sequential operations (the obstacle to parallelism), and maximum path length between two positions (the obstacle to learning long-range dependencies). \begin{table}[htbp] \centering \caption{Per-layer complexity for sequence length $n$, representation dimension $d$ and convolution kernel size $k$ \cite{vaswani2017}.} \label{tab:att-complexity} \begin{tabular}{lccc} \toprule Layer type & Complexity per layer & Sequential ops & Max path length \\ \midrule Self-attention & $O(n^2 \, d)$ & $O(1)$ & $O(1)$ \\ Recurrent & $O(n \, d^2)$ & $O(n)$ & $O(n)$ \\ Convolutional & $O(k \, n \, d^2)$ & $O(1)$ & $O(\log_k n)$ \\ \bottomrule \end{tabular} \end{table} The trade the Transformer makes is explicit in the first row: it pays a quadratic compute bill in exchange for constant-depth parallelism and constant-length interaction paths. For the sequence lengths of machine translation this trade was decisively favourable, and hardware trends — matrix units that reward dense, regular computation — have only widened the advantage since. % ---------------------------------------------------------------------------- \section{Model Families: BERT, GPT, T5}\label{sec:att-families} % ---------------------------------------------------------------------------- The encoder--decoder of Figure~\ref{fig:att-transformer} contains two self-sufficient halves, and the field promptly split it apart. Three canonical families resulted, distinguished by which half they keep and by their pre-training objective (Table~\ref{tab:att-families}). \textbf{BERT} keeps only the \emph{encoder}: attention is bidirectional, every position sees the whole sequence. It is pre-trained by masked language modelling — a fraction of input tokens is hidden and must be reconstructed from both sides of context — which makes it a powerful text \emph{understanding} machine (classification, retrieval, extraction) but not a generator. \textbf{GPT} keeps only the \emph{decoder}: every layer uses the causal mask \eqref{eq:att-mask}, and pre-training maximizes the autoregressive log-likelihood $\sum_t \log p_\theta(x_t \mid x_{