Chapter 2: Tokenization & Embeddings

WordPiece (Schuster and Nakajima, 2012), later used for BERT, builds its vocabulary with merges like BPE but chooses them differently. The score of a candidate pair $a, b$ is the frequency of the merged unit $ab$ divided by the product of the frequencies of $a$ and $b$. A pair whose halves are individually common but rarely adjacent scores low. A pair that almost always occurs together scores high, even if it is rare overall. Pieces that continue a word carry a "##" prefix, so word-initial and word-internal pieces have different IDs. At encoding time WordPiece takes the longest matching vocabulary entry from the left.

SentencePiece (Kudo and Richardson, 2018) is a toolkit rather than a new merge rule. It trains either a BPE or a Unigram model directly on raw text, without first splitting it into words. Whitespace is treated as an ordinary symbol, written as a special underscore-like character, so it becomes part of the pieces. That makes tokenization lossless: decoding the pieces reproduces the exact original string, spaces included. It also means one tokenizer works across languages that do not use spaces. T5, ALBERT, XLNet, and the original Llama all used SentencePiece models. Rare characters still need a fallback, which is covered in the next topic.

The Unigram model (Kudo, 2018) works in the opposite direction from BPE. It starts with a large candidate vocabulary and prunes it. Each token has an independent probability, and a segmentation $x = (x_1, \ldots, x_n)$ of a word scores the product of its token probabilities. The best segmentation is found by dynamic programming (the Viterbi algorithm). Training alternates between estimating token probabilities with expectation-maximisation and deleting the tokens whose removal hurts corpus likelihood least, until the target size is reached. Because it scores every segmentation, it can also sample alternative splits during training, a technique called subword regularisation.

The three algorithms differ in the direction of training and in the scoring rule. BPE builds up by merging the most frequent pair. WordPiece builds up by merging the pair with the highest likelihood gain, a frequency ratio. Unigram prunes down from a large set using a probabilistic model. BPE and WordPiece encode deterministically, while Unigram can sample several segmentations, which acts as data augmentation. At large vocabularies the downstream quality differences are small. The bigger decisions are vocabulary size, byte fallback, and the language mix of the tokenizer's training data. BPE dominates today partly because GPT-2 and tiktoken popularised it.

Vocabulary size $V$ sets two costs that move in opposite directions. The input embedding matrix has $V \times d$ parameters, where $d$ is the model width, and an untied output layer adds another $d \times V$, so doubling $V$ doubles both. A larger vocabulary, though, gives each text fewer tokens, which saves attention compute and context space. It also stores common multi-character strings as single units. The failure mode at the large end is undertrained rows: rare tokens get too few gradient updates to learn good embeddings. Modern LLMs settle between about 32,000 and 256,000 tokens, with the larger sizes common in multilingual models.

Besides pieces of text, every vocabulary reserves a few special tokens that carry control signals. [BOS] marks the beginning of a sequence and [EOS] the end. [PAD] fills short sequences so a batch is rectangular, and the loss and attention mask ignore it. [MASK] is BERT's blank to fill in, [SEP] separates segments, and [CLS] collects a sequence-level summary. Chat models add role markers for system, user, and assistant turns. Each special token has an ordinary learned embedding. The failure modes are practical. A missing [EOS] in fine-tuning data teaches the model never to stop, and user text that imitates a special token can spoof the chat format.

Fertility measures how many tokens a tokenizer needs per word of a language: tokens divided by words on a reference text. A vocabulary trained mostly on English gives English words dedicated tokens, so English fertility is about 1.2 to 1.5. Languages that were rare in the tokenizer's training data fall back to short fragments or single bytes, with fertility several times higher. High fertility has three costs for users of that language. They pay more per word under per-token pricing, fit fewer words into the context window, and often get lower quality. Petrov et al. (2023) measured length differences of up to 15 times for the same content across languages.

Byte fallback guarantees that any input can be encoded. When a character has no token in the vocabulary, the tokenizer emits its UTF-8 bytes instead, using 256 reserved byte tokens. This removes [UNK], so the model can always reproduce the exact input, which matters for code, names, and rare scripts. Llama's SentencePiece tokenizer uses this scheme, and fully byte-level BPE as in GPT-2 gets the same guarantee by construction. The cost is length. UTF-8 uses 1 byte for ASCII, 2 for most Latin and Cyrillic letters with accents, 3 for most Asian scripts, and 4 for emoji. Unseen text can therefore become 3 or 4 times longer.

A one-hot vector represents token $i$ as a length-$V$ vector of zeros with a single 1 at position $i$. It is huge, and every pair of distinct words is equally far apart, so it encodes no similarity. An embedding matrix $W_E \in \mathbb{R}^{V \times d}$ replaces it. Multiplying $W_E$ by the one-hot vector simply selects row $i$, so in practice the operation is a table lookup. Here $d$ is the embedding width, typically 768 to 8,192 in modern LLMs. The rows start random and are trained along with the rest of the network, so words that appear in similar contexts drift toward similar vectors.

Cosine similarity compares two embeddings $a$ and $b$ by the angle $\theta$ between them. It is their dot product divided by the product of their lengths $\|a\|$ and $\|b\|$, which gives $\cos\theta$, between $-1$ for opposite directions and $1$ for the same direction. Dividing by length removes magnitude, which often tracks word frequency rather than meaning. High similarity captures both synonyms, such as happy and joyful, and related words, such as king and queen. One pitfall: antonyms such as hot and cold appear in similar contexts, so they often score high. Similarity measures shared usage, not shared meaning.

Trained static embeddings often encode relations as consistent directions. If the vector from man to woman is roughly the same as the vector from king to queen, then king minus man plus woman lands near queen, as in the formula. The same pattern appears for country to capital, verb tense, and singular to plural. To solve an analogy, compute the target vector and return the nearest word by cosine, excluding the three input words. That exclusion matters, because the nearest raw neighbour is often an input word itself. Analogies are a diagnostic of embedding structure, not a guarantee. Many relations are not linear, and the directions also encode social biases.

Static embeddings such as Word2Vec and GloVe give each word one vector, so "bank" gets a single vector that averages its river sense and its finance sense. Contextual embeddings fix this by letting the network recompute each token's vector from its surrounding sentence. ELMo did this with bidirectional LSTMs. BERT and GPT do it with self-attention, where each layer adds context-dependent updates to a residual stream that starts from the static lookup. The first layer's vector is still context-free. By the upper layers, the same word in different sentences has clearly different vectors. The cost is compute, since a static lookup is replaced by a full forward pass.

The original Transformer adds a fixed vector $PE_{pos}$ to the embedding of the token at position $pos$. Dimension pair $2i$ and $2i+1$ holds the sine and cosine of $pos$ divided by $10000^{2i/d}$, where $d$ is the model width. Low dimensions oscillate quickly and high dimensions slowly, with wavelengths from $2\pi$ up to nearly $10000 \cdot 2\pi$, so each position gets a distinct pattern, like the hands of a clock running at many speeds. Moving by a fixed offset $k$ is the same rotation of each sine-cosine pair wherever you start, so relative offsets are easy to learn. The encoding needs no parameters but extrapolates poorly in practice.

Learned positional embeddings treat position like a second vocabulary. A matrix $P \in \mathbb{R}^{L_{\max} \times d}$ holds one trainable $d$-dimensional vector per position, up to the maximum length $L_{\max}$. The input to the first layer is the token embedding plus the row of $P$ for that position. GPT-2 and BERT use this scheme, and it is simple and flexible, since the model learns whatever positional pattern helps. The hard limit is the table. Positions beyond $L_{\max}$ have no row at all, and rows near the end of the table get less training, because fewer training sequences reach those positions.

RoPE (Su et al., 2021) encodes position by rotating vectors instead of adding to them. Each query and key vector is split into pairs of dimensions, and the pair at position $m$ is rotated by angle $m\theta$, as in the formula, with a different frequency $\theta$ for each pair. The attention score is a dot product, and rotating a query by $m\theta$ and a key by $n\theta$ leaves a dot product that depends only on the difference $m - n$. So attention sees relative distance, though each vector was rotated by absolute position. It adds no parameters and is used by Llama, Mistral, and most recent LLMs. Beyond the trained length it still needs scaling tricks.

ALiBi (Press et al., 2022) adds no positional vectors at all. Instead, each attention score $q_i K^T$ gets a penalty proportional to distance. A key $j$ positions back receives bias $-m \cdot j$, so nearby tokens are favoured, as in the formula. Each head has its own fixed slope $m$, a geometric sequence such as $1/2, 1/4, \ldots, 1/256$ for 8 heads, so some heads focus locally and others look far back. There are no learned parameters, and because the penalty is defined for any distance, models trained on short sequences handle longer ones gracefully. The cost is a built-in bias toward recent tokens, which can hurt tasks that need precise long-range retrieval.