4.4 Transformers

The last architecture in this course is the one behind today’s large language models. CNNs were designed for images; transformers were designed for sequences.

Motivation

A language model generates text one piece at a time. Given “I have a ca”, what comes next? In class, people guessed t, p, r and n, which give “cat”, “cap”, “car” and “can”. All are plausible. A language model makes the same kind of guess, but as a probability distribution over every possible next character. It then picks a character, appends it, and repeats: “I have a ca” → “I have a cat” → … → “I have a cat named Cookie!”

What architecture makes good guesses like this? The GPT-3 paper (“Language Models are Few-Shot Learners”, 2020) describes its model in one line: it uses the same model and architecture as GPT-2, which is built from transformer layers. The transformer was introduced in 2017 in a paper titled “Attention Is All You Need.” Its full architecture has several components. Some we already know: a “feed forward” block is just an MLP. Others, such as the normalization layers, are simple enough to learn on your own. Today we unpack the three ideas that are new: input embedding, attention and positional encoding.

Today: a character-level language model

We’ll build a toy version of a transformer: a character-level language model.

Tokenization. Before anything reaches the network, the string is split into tokens. In a character-level model, each character is a token: \[ \text{"I have a ca"} \;\xrightarrow{\text{tokenization}}\; [\text{`I'}, \text{` '}, \text{`h'}, \text{`a'}, \text{`v'}, \text{`e'}, \text{` '}, \text{`a'}, \text{` '}, \text{`c'}, \text{`a'}]. \] Tokenization is decided in advance and is not learned. Modern language models use tokens somewhere between a character and a word, but the idea is the same.

Modeling task: given a sequence of tokens (the context), predict a distribution over the next token.

For our model, the vocabulary is the 26 letters plus the space: 27 possible tokens. (We treat “I” as lowercase.)

Input embedding

Motivation

Neural networks operate on vectors, but our model input is a list of characters. There’s no natural arithmetic on characters.

Goal: find a vector representation for each token.

Idea: one-hot encoding. Give each token its own coordinate: \[ \text{`a'} \to [1, 0, 0, \dots, 0]^\top \in \mathbb{R}^{27}, \qquad \text{`b'} \to [0, 1, 0, \dots, 0]^\top \in \mathbb{R}^{27}, \qquad \text{etc.} \]

Issue: all token representations are orthogonal to each other. (They’re also very sparse, which is inefficient.) We’d like the dot product between two representations to mean something. Similar tokens should have a larger dot product than unrelated ones. With one-hot encodings, every pair of different tokens has dot product 0, so every token is equally unrelated to every other. This matters even more when tokens are words.

Better idea: learn \(d\)-dimensional embeddings from data. Each token in the vocabulary gets its own vector in \(\mathbb{R}^d\), kept in a lookup table, and those vectors are parameters learned by backprop. The dimension \(d\) is a hyperparameter.

Example

Take a vocabulary of three tokens: “machine learning”, “boring” and “fun”.

We don’t hand-design these vectors. We let the data decide.

After the input embedding, a context of \(T\) tokens becomes a matrix \(E \in \mathbb{R}^{T \times d}\), with one row per token. (Stacking the embeddings as rows follows the literature.) For “I have a ca”, \(T = 11\).

Attention

Motivation

Issue: the same token takes on different meanings based on the context. In “I have a ca”, the three a’s all get the same input embedding. But the “a” that stands alone as a word plays a very different role from the “a” inside “have” or at the end of “ca.”

Idea: let tokens pass information among themselves, so that each token’s representation can be updated based on the other tokens in its context.

Attention is an operation that computes a weighted average of information passed by tokens: \[ \text{Attention}(E) = \text{softmax}\!\left( \frac{QK^\top}{\sqrt{d_k}} \right) V. \]

Like a dense layer in an MLP or a convolution in a CNN, attention is an operation that takes us from one layer to the next. It has three sets of parameters:

The input is \(E \in \mathbb{R}^{T \times d}\), and the output is \(A \in \mathbb{R}^{T \times d'}\): still one row per token, but each token now has an updated embedding, possibly in a different dimension \(d'\). The dimensions \(d_k\) and \(d'\) are hyperparameters.

Unpacking the formula

The definition has two parts: information passed by tokens, and weights for averaging it. Start with the information.

Values: what each token passes along. Each token decides what information to send to the next layer. The simplest choice is a linear transformation of its embedding: \[ V := E W_V \in \mathbb{R}^{T \times d'}. \] Each row of \(V\) is the information that token passes to the next layer. As intuition, for the tokens of “hello”, the rows might encode something like “similar to a” for e, “line!” for each l, and “circle!” for o.

Weights over tokens. Suppose we had a \(T \times T\) matrix whose row \(i\) is a probability distribution over the \(T\) tokens, for example \((0.1, 0.3, 0, 0.3, 0.3)\). Multiplying this matrix by \(V\) makes row \(i\) of the output a weighted average of the rows of \(V\), using the weights in row \(i\). That is exactly a weighted average of information passed by tokens. So what remains is to find good weights.

Queries and keys: who should listen to whom. Each token gets two more vectors: \[ Q := E W_Q \in \mathbb{R}^{T \times d_k}, \qquad K := E W_K \in \mathbb{R}^{T \times d_k}. \]

To see whether token \(j\) offers what token \(i\) is looking for, take a dot product: \[ (QK^\top)_{ij} = Q_i \cdot K_j. \] The matrix \(QK^\top \in \mathbb{R}^{T \times T}\) has a row for each query and a column for each key. A high value means “yes, that’s what I want.” For example, if row 1 of \(QK^\top\) is \((-2, \dots, -10, \dots, 100)\), the first token badly wants the information from the last token and doesn’t want the information from the others.

Softmax, by rows. To turn each row of scores into weights, apply softmax: exponentiate each entry, making it positive, and divide by the row’s sum, so the row adds up to 1: \[ \text{softmax}(s_1, \dots, s_T) = \left( \frac{e^{s_1}}{\sum_j e^{s_j}}, \dots, \frac{e^{s_T}}{\sum_j e^{s_j}} \right). \] Before the softmax, the scores are divided by \(\sqrt{d_k}\), a normalization that helps the model train better. Each row of \(\text{softmax}(QK^\top / \sqrt{d_k}) \in \mathbb{R}^{T \times T}\) is then a set of weights over the key tokens, and multiplying by \(V\) gives the updated embeddings \(A\).

The query and key story is intuition. What attention really learns is not fully understood. Unlike convolution, which signal processing had used for a long time, attention was invented by the deep learning community, and it’s a remarkably creative idea.

Worked example

Take the context “cat” with \(d = 2\) and embeddings \(\text{c} = (1, 0)\), \(\text{a} = (0, 1)\), \(\text{t} = (1, 1)\). To keep the arithmetic simple, take \(W_Q = W_K = W_V = I\), so \(Q = K = V = E\) and \(d_k = d' = 2\).

\[ \frac{QK^\top}{\sqrt 2} = \frac{1}{\sqrt 2} \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 2 \end{bmatrix} \approx \begin{bmatrix} 0.71 & 0 & 0.71 \\ 0 & 0.71 & 0.71 \\ 0.71 & 0.71 & 1.41 \end{bmatrix}. \]

For the first row, \(e^{0.71} \approx 2.03\) and \(e^0 = 1\), so the softmax gives weights \((2.03, 1, 2.03)/5.06 \approx (0.40, 0.20, 0.40)\). The updated embedding of “c” is \[ 0.40\,(1, 0) + 0.20\,(0, 1) + 0.40\,(1, 1) \approx (0.80, 0.60). \] The full output is \[ A \approx \begin{bmatrix} 0.80 & 0.60 \\ 0.60 & 0.80 \\ 0.75 & 0.75 \end{bmatrix}. \] Each token’s new embedding now mixes in information from the others.

Positional encoding

Issue: attention is permutation-equivariant. Reordering the input tokens just reorders the output rows the same way: \[ \text{Attention}(E_{[c, a, t]}) = \text{permute}\big(\text{Attention}(E_{[t, a, c]})\big). \] \(\implies\) The model processes [c, a, t] and [t, a, c] the same way, up to reordering. Yet “cat” and “tac” mean different things, and word order matters just as much.

In the worked example above, feeding in “tac” gives exactly the same three output rows in reverse order: \((0.75, 0.75)\) for t, \((0.60, 0.80)\) for a and \((0.80, 0.60)\) for c. Nothing in the computation depends on where a token sits. For the same reason, the two l’s in “hello” would always get identical outputs.

Solution: add positional information to the input embedding. Each position \(1, \dots, T\) gets its own vector in \(\mathbb{R}^d\), collected in a positional encoding matrix \(P \in \mathbb{R}^{T \times d}\). These vectors are also parameters learned from data. Before attention, we add the two: \[ E + P \in \mathbb{R}^{T \times d}. \] Now the model knows not only that the context contains “I”, ” “,”h”, … but also that “I” is first, ” ” is second, and so on. (The original transformer paper used fixed sinusoidal functions of the position instead of learned vectors. Both approaches are common.)

Example

Putting the pieces together gives a tiny character-level language model.

\[ \text{tokens} \;\xrightarrow{\text{input embedding}}\; E \in \mathbb{R}^{T \times d} \;\xrightarrow{\ + P\ }\; E + P \;\xrightarrow[\;W_Q,\ W_K,\ W_V\;]{\text{attention}}\; A \in \mathbb{R}^{T \times d'} \;\xrightarrow[\;\text{last row}\;]{\text{dense } (W, b)\ \&\ \text{softmax}}\; (0, 1)^{27} \]

  1. Input embedding and positional encoding. Look up the embedding of each token, and add the positional encoding: \(E + P \in \mathbb{R}^{T \times d}\).
  2. Attention. Let the tokens talk to each other once, to incorporate the context: \(A \in \mathbb{R}^{T \times d'}\).
  3. Predict. Take the updated embedding of the last token, the “a” in “ca”, which has now absorbed information from the whole context. A dense layer with \(W \in \mathbb{R}^{d' \times 27}\) and \(b \in \mathbb{R}^{27}\) maps it to 27 scores, and a softmax turns the scores into probabilities.

Parameter count (all learned by SGD + backprop):

component parameters
positional encoding \(T \times d\)
input embedding \(27 \times d\) (one \(d\)-dim vector per token in the vocabulary)
attention weights \((d \times d_k) \times 2 + (d \times d')\)
dense layer \(d' \times 27 + 27\)

Real transformers add more on top of this: several attention operations in parallel (multi-head attention), MLP blocks, normalization, and many such layers stacked on top of each other. GPT-style models also mask the attention so that each token can only look at the tokens before it, which lets the model learn to predict the next token at every position at once. But the core ideas are the three we covered today: input embedding, attention and positional encoding.

Try it yourself

With \(d = d' = 16\) and \(d_k = 8\) and a context length of \(T = 32\), how many parameters does the toy model have? Which component would grow if we tokenized by words instead of characters?