Tokens and language modelling

Take the English word lower. A byte-pair encoder cuts it into two pieces, low and er, because that pair appears often enough to earn its own entry [S:190:4]. Byte-pair encoding is a compression procedure: it begins with single characters and repeatedly merges the most frequent adjacent pair into a new symbol [S:98:22]. A tokeniser is the program that applies those merges to new text, and each piece it returns is a token.

The model never sees the letters l-o-w-e-r. It sees two integer positions in a fixed list, one for low and one for er. !A tokeniser turns text into entries from a fixed list. lower is cut into low and er, and each piece is looked up as one unit. The model sees two units, not the five letters, and a word the list has never held can still be built from pieces it has. The figure is schematic. Status: schematic.

The list those integers index is the vocabulary: the finite set of tokens the model may use. GPT-2's vocabulary had 50,257 entries over byte-level pieces [S:224:4]. Writing in 2019, its authors described the byte-pair vocabularies then in common use as 32,000 to 64,000 entries, a band that includes their own [S:224:3-4]. The size is a chosen hyperparameter: BERT used 30,000 entries and Llama 3 uses 128,000 [S:219:4; S:431:7]. !Scoring a sequence one token at a time. The model gives the probability 0.6 at the start, cat 0.5 after the, and sat 0.4 after the cat; the probabilities multiply to $0.6\times 0.5\times 0.4=0.12$. A uniform model over the same three tokens gives $(1/3{)}^3=0.037$, so the trained model finds the sentence 3.24 times more likely. The probabilities are synthetic, taken from the section's worked example. Status: synthetic.

Word-level systems kept one entry per word. Neural translation models, sequence-to-sequence systems trained to map one language to another, often capped that list at 30,000 to 50,000 words, which left rare and unseen words with no entry at all [S:190:1]. Subword units remove that dead end for any word whose characters are in the base alphabet.

Byte-level byte-pair encoding is total: every string is a sequence of bytes, and a fixed base of 256 byte symbols covers all of them, so nothing is unrepresentable [S:224:4]. A lossy tokeniser is the exception. One that lowercases, strips accents or replaces unknown characters with a placeholder erases a distinction, and no later scale recovers it.

Prediction works one position at a time. Next-token prediction means choosing a probability for the token after the tokens already read. The model returns a probability distribution over the vocabulary: one non-negative number per entry, summing to one. Training compares that distribution with the token that actually came next, and the parameters, the numbers training adjusts, move so the correct token scores higher next time [S:91:13]. Repeat that on enough text, and training pushes the parameters toward whatever regularities reduce the surprise, a number that is zero when the next token was certain and grows as its probability falls.

The conditional probability of a token given its predecessors is the number the model outputs. The probability $P$ of a whole sequence is the product of those numbers. For tokens $w_1$ to $w_T$,

$$P(w_1,\dots ,w_T)=\prod _{t=1}^{T}P(w_t\mid w_1,\dots ,w_{t-1}).$$

The vertical bar reads "given", the product sign multiplies the $T$ factors, and the subscript $t$ runs over positions from the first to the last. A language model is exactly this: a probability distribution over sequences of tokens.

That equation says a sentence is scored one token at a time, with every earlier token available as context [S:224:2]. Nothing in it assumes the tokens are words, and nothing in it assumes the context stops at a sentence boundary. The context window is the number of tokens the model may read at once; a longer window buys more context and costs more memory and time.

Worked example. A toy model has three tokens: the, cat, sat. Suppose it gives the probability 0.6 at the start, cat probability 0.5 after the, and sat probability 0.4 after the cat. The probability of the whole sequence is $0.6\times 0.5\times 0.4=0.12$.

A model that spread its probability evenly over the three tokens would give $(1/3{)}^3=0.037$ to the same sequence. The trained model finds this sentence about three times more likely than the uniform model does.

The idea breaks at the tokeniser. A fixed vocabulary spends its entries on pieces common in the training text, so rare scripts, writing systems with few training examples, arrive in fragments [S:224:3-4]. A byte-level tokeniser can represent any string from 256 byte symbols, at the cost of longer sequences and less text per token [S:224:4]. A lossy tokeniser is the one case where a distinction disappears for good.

This is the scale question in miniature: same objective, more parameters, more text. What changes is how much structure those parameters must absorb to keep lowering the surprise. The next section asks where that text comes from.

The formal statement. Fix a corpus and a number of merges $k$. This chapter follows the Speech and Language Processing presentation: the trainer begins with the character set, with whitespace attached to the start of each word, and merges only inside words. It then repeats a single step: count every pair of adjacent symbols, merge the most frequent pair into a new symbol, and add that symbol to the vocabulary. The trainer stops after $k$ merges, so the final vocabulary holds the character set plus $k$ entries, and $k$ is the only free parameter [S:98:22]. Sennrich's original trainer adds one end-of-word symbol to the base alphabet, so its final vocabulary is the character set plus one plus $k$ [S:190:3]. The difference is bookkeeping; the chapter uses the first convention throughout.

The encoder is a separate program. It splits a new string into characters and applies the learned merges in the order they were learned [S:98:24]. A language model then maps a prefix of tokens to a distribution over the vocabulary, and the chain rule turns those conditionals into the probability of the whole sequence [S:224:2].

The derivation. The chain rule is one line of algebra. For events $A$ and $B$ with $P(A)>0$, conditioning gives $P(A,B)=P(A)P(B\mid A)$. Apply that to the final token and the prefix, then to the prefix and its own final token, and induction over the length gives the product in L1. No approximation enters: the product is exact for every distribution over sequences.

The step I omit is the proof that a softmax output defines a valid distribution. That needs only two facts, that every output is non-negative and that the outputs sum to one.

An edge case. L1 says subword units remove the dead end for any word whose characters are in the base alphabet, and that byte-level encoding is total. The first claim is true and incomplete. The merges are chosen by frequency in one corpus, so the entries follow the language of that corpus [S:98:25]. A multilingual tokeniser trained on web text spends most of its entries on English, and other languages arrive in shorter pieces [S:98:25]. One Spanish sentence can then take 33 tokens where its English translation takes 18 [S:98:25]. A character-level tokeniser still has no token for a character it never saw; only the byte-level base alphabet covers every string.

A fixed list is fixed in size, not fair in its allocation.

What L1 hid, and why that was safe there. L1 folded the trainer and the encoder into the single word "tokeniser". Separating them locates the failure: the trainer is a compression procedure, and the encoder is a greedy lookup that never reconsiders a merge. From the reader's side the two programs act as one, and only the vocabulary size is visible, so the fold costs nothing at a first pass.

Where the analogy breaks. "A probability machine over tokens" suggests that the units are neutral carriers. They are not. The same string receives different probabilities under different tokenisers, so two models are comparable only when their vocabularies match [S:98:55]. L1 states this at the end; the formal version turns it into a condition on every comparison you make.

Original sources. The subword move is Sennrich, Haddow and Birch's adaptation of byte-pair encoding from data compression to word segmentation [S:190:2]. Their problem was an open vocabulary. Neural translation models kept a fixed list of 30,000 to 50,000 words, and rare names, compounds and inflections had no entry [S:190:1]. Merging characters or character sequences gives a fixed list that can still spell an unseen word, provided its characters are in the base alphabet [S:190:2].

GPT-2 changed the base alphabet from Unicode characters to bytes, which brings the base vocabulary down to 256 symbols [S:224:4].

An open question. Nobody has settled how to divide one fixed vocabulary among many languages. Tokenisers trained on web text spend most of their entries on English, so other languages are split into shorter tokens [S:98:25].

Spanish is not a low-resource language, and the example in the textbook still gives it 33 tokens where the English takes 18 [S:98:25]. Evidence that would settle the allocation question is a controlled comparison at fixed vocabulary size, fixed model size and fixed training compute, scored by bytes per token and by downstream accuracy in each language. A compression ratio alone will not do, because it measures length and not learning.

A frontier method. SuperBPE allows a second stage of merges across spaces and punctuation, producing tokens that span more than one word [S:98:25]. The method depends on this section twice. It begins from an ordinary byte-pair vocabulary, and its gain is reported in bytes per token, which is the compression quantity that byte-pair encoding optimises.

What to read next. Read section 2.4 of Speech and Language Processing for the trainer and the encoder as separate programs [S:98:22]. Then read Sennrich et al. for the original adaptation and its translation results [S:190:3]. Read the GPT-2 input-representation section for the byte-level variant [S:224:4], and keep the multilingual page open beside them, because it shows what a fixed budget costs in practice [S:98:25].