Byte-pair encoding

Key idea

Training: count adjacent pairs, merge the most frequent, repeat until the vocabulary is big enough. Encoding: pre-tokenise, then apply the learned merges in order

Real world

Inventing your own shorthand. You notice you write “th” constantly, so you give it one squiggle. Then “the” (squiggle + e) is so common it gets its own. After a while your list of squiggles, in the order you invented them, is your shorthand system.

In an LLM

GPT-2’s first merge was “Ġ” + “t” (a space then t), its seventh “Ġt” + “he”, making “ the”. After 50,000 merges, “ unbelievable” is one token, while the rarer “ hedgehogs” stops at three: “ hedge”, “h”, “ogs”.

The idea

Byte-pair encoding (byte-pair encoding) started life in 1994 as a data-compression trick: find the most common pair of adjacent bytes in a file, replace it with a single unused byte, repeat. In 2016 Sennrich, Haddow and Birch used it to build vocabularies for translation models. GPT-2 made it the default for language models, and today GPT-4, Llama 3, Mistral, Qwen and most other LLMs use a version of it.

The training algorithm fits in four lines:

1. Split every word of a training corpus into single characters.
2. Count every pair of adjacent symbols, across the whole corpus.
3. Merge the most frequent pair into one new symbol, everywhere it occurs, and add it to the vocabulary.
4. Repeat from step 2 until the vocabulary is the size you want.

The output is not just a vocabulary. It is an ordered list of merges, and that order is used again when encoding new text.

Training, step by step

This is the example from Sennrich’s paper: a corpus where “low” appears 5 times, “lower” 2 times, “newest” 6 times and “widest” 3 times. Press play and watch the pair counts, the merges and the two curves. Then edit the corpus, or try the other examples.

Follow the first few merges. “e” + “s” occurs 9 times (6 in “newest”, 3 in “widest”). Two other pairs, “s” + “t” and “t” + “”, also occur 9 times; when counts tie, the pair seen first wins, so “e” + “s” becomes the symbol “es”. Now “es” + “t” occurs 9 times, so “est” is next, then “est”, an ending that marks the end of a word. Only then does “low” get built. Each merge is chosen on the corpus as it is after the previous merges, which is why the order matters.

Two things happen together, as the chart shows: the corpus gets shorter (fewer, bigger symbols) and the vocabulary grows by one per merge. You stop when the vocabulary reaches the size you chose in advance: 50,257 for GPT-2, about 100,000 for GPT-4, 128,256 for Llama 3.

The box at the bottom encodes a word that is not in the corpus. With the merges learned from “low”, “newest” and “widest”, the unseen word “lowest” comes out as “low” + “est_”: BPE builds new words from the pieces it learned for old ones.

Encoding new text

Once trained, the tokenizer encodes any text by replaying the merges. Split a word into single symbols, then repeatedly merge the neighbouring pair that was learned earliest (the lowest merge number), until no neighbouring pair is in the list.

Here is GPT-2’s real tokenizer, with all 50,000 of its merges:

In “ unbelievable” the first merge is “l” + “e” (merge 38), then the space joins the “u” (merge 79). After twelve merges in all, the whole word is one token: it was common enough in GPT-2’s training text to be merged all the way. Turn off the space and the same letters end as four tokens, “un”, “bel”, “iev”, “able”: in GPT-2, “unbelievable” after a space and at the start of a line are different strings. The quirks page has more of these surprises.

Pre-tokenization: where merges may not go

Run BPE on raw text and it will happily learn merges like “dog.” and “dog!” and “dog?”, wasting vocabulary on every combination of word and punctuation. So before BPE runs, text is split into chunks by a fixed rule, and merges never cross a chunk boundary. This step is called Pre-tokenization.

In GPT-2 the rule is a regular expression that separates letters, numbers, punctuation and whitespace, with a space allowed to stick to the front of the following chunk:

's|'t|'re|'ve|'m|'ll|'d| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+

\p{L} is any letter, \p{N} any digit. Later tokenizers tweaked it. GPT-4’s splits numbers into groups of at most three digits; GPT-4o’s also starts a new chunk at a capital letter. Compare them:

These rules matter more than they look. Splitting numbers into fixed groups of three makes arithmetic more regular for the model. Keeping a space at the front of words is why “ cat” and “cat” are different tokens. And because the GPT-2 rule only knows lower-case contractions, “I'LL” is cut into “I”, “'”, “LL”.

from collections import Counter
 
def train_bpe(word_freqs, num_merges):
    # word_freqs: {("l","o","w","</w>"): 5, ...}
    merges = []
    for _ in range(num_merges):
        pairs = Counter()
        for word, f in word_freqs.items():
            for a, b in zip(word, word[1:]):
                pairs[a, b] += f
        if not pairs:
            break
        best = max(pairs, key=pairs.get)
        merges.append(best)
        word_freqs = {merge(w, best): f for w, f in word_freqs.items()}
    return merges
 
def encode_word(symbols, ranks):            # ranks: {(a, b): merge index}
    while len(symbols) > 1:
        pairs = [(ranks.get(p, float("inf")), i) for i, p in enumerate(zip(symbols, symbols[1:]))]
        rank, i = min(pairs)
        if rank == float("inf"):
            break
        symbols = merge(symbols, symbols[i:i + 2])
    return symbols