% ============================================================================
%  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_{<t})$. Generation is
native — sampling one token at a time — and scaling this single recipe to
ever larger models produced the modern lineage of large language models.

\textbf{T5} keeps \emph{both} halves and casts every task — translation,
summarization, classification, question answering — as text-to-text, with
a span-corruption pre-training objective in which contiguous spans are
masked and regenerated by the decoder.

\begin{table}[htbp]
  \centering
  \caption{The three canonical Transformer families.}
  \label{tab:att-families}
  \begin{tabular}{llll}
    \toprule
    Family & Architecture & Pre-training objective & Typical use \\
    \midrule
    BERT & Encoder only & Masked language modelling & Understanding \\
    GPT  & Decoder only & Next-token prediction      & Generation \\
    T5   & Encoder--decoder & Span corruption        & Text-to-text \\
    \bottomrule
  \end{tabular}
\end{table}

Whatever the family, the interior is the same handful of equations: scaled
dot-product attention \eqref{eq:att-sdpa} with its variance-controlled
logits \eqref{eq:att-variance}, multiple heads
\eqref{eq:att-head}--\eqref{eq:att-multihead}, positional information
\eqref{eq:att-pe-sin}--\eqref{eq:att-pe-cos}, and the residual--normalized
block \eqref{eq:att-addnorm}--\eqref{eq:att-ffn}. Few architectures in the
history of the field have combined such simplicity of definition with such
range of consequence.
