Vol. II · Tokens Plate 3 of 10byte-pair encoding, BPE, merges, training a tokeniser, compressionDL

Byte-Pair Encoding.

Count every adjacent pair of symbols, merge the most frequent into a new one, and repeat: a vocabulary grows out of the data.

Byte-pair encoding starts with the text as bytes. It counts every pair of adjacent symbols in the corpus, finds the most frequent — in English, usually a space followed by t, or t followed by h — and replaces every occurrence with a single new symbol. That is one merge, and it adds one token to the vocabulary. Then it counts again and merges again. After a few hundred merges the vocabulary holds common syllables and short words; after tens of thousands, most common words are single tokens.

The procedure is greedy and simple, and the vocabulary it produces reflects the training text exactly: frequent things become short. Two practical details matter. The corpus is first split into words (plate II.4) so that merges never cross word boundaries, and ties between equally frequent pairs have to be broken by a fixed rule, or two implementations trained on the same text would disagree. The course’s own engine breaks ties alphabetically and is checked against a reference implementation merge for merge.

Below: BPE trained in your browser on 60 000 characters of the course corpus. Move the slider to choose how many merges to keep; the curve shows how the corpus shrinks with each merge, the list shows the first merges learned, and the sample is encoded with the merges kept so far.

What you will learn

Run byte-pair encoding by hand on a small text.
Explain why frequent sequences become single tokens.
Measure how each merge shortens the corpus.
Recognise the role of deterministic tie-breaking.

Workshop

Left: tokens needed for the 60 000-character training slice after each merge (it starts as one token per byte). Right: the sample sentence encoded with the merges kept.

Frequent things become short

The 60 000-character slice is 60,529 bytes. The first fifty merges alone shrink it to 40,341 tokens, because they capture the commonest pairs — a space before a letter, th, he, in. After 200 merges it is 30,163 tokens, 2.01 times shorter than bytes, and the sample sentence needs 28 tokens, 1.89 characters each. By 1 000 merges the slice is down to 19,921 tokens. Each new merge saves less than the last: the curve flattens because the most frequent pairs are used up first, which is why vocabularies stop growing at tens or hundreds of thousands rather than millions.

Notice what BPE learns without being told: spaces attach to the start of the following word, so ·the and the become different tokens; common endings such as ing and tion appear early; capitalised and lower-case forms are separate. The course tokeniser is the same algorithm run for 7 935 merges over the whole bilingual corpus with the Hugging Face tokenizers library, and the course’s own engine reproduces both its merges on small texts and its encodings of held-out text exactly. Plate II.4 shows how the merges are applied to new text.

Philip Gage published byte-pair encoding in 1994 in the C Users Journal as a simple compression scheme: replace the commonest pair of bytes by an unused byte, record the substitution, repeat. Twenty-one years later the same loop became the standard way to build a language model’s vocabulary.

Terms

Byte-pair encoding (BPE): Building a vocabulary by repeatedly merging the most frequent adjacent pair of symbols.
Merge: One step of BPE: a pair of symbols replaced everywhere by a new token, recorded in order.
Merge list: The ordered list of merges; with the base alphabet it defines the tokeniser completely.
Tie-breaking: The fixed rule for choosing between equally frequent pairs, so training is reproducible.

BPE merges the most frequent pair, again and again; the vocabulary is the record of those merges, and frequent text ends up short.