LM2-T3 — Byte-Pair Encoding

Learning objectives

After this lesson, you should be able to:

• Run the BPE learning algorithm by hand on a small word-count table and write the merge list.
• Encode a new word by replaying the merges in the order they were learned.
• Explain why byte-level BPE never produces an unknown token and how GPT-2’s vocabulary size of 50,257 arises.
• Estimate how the number of merges changes vocabulary size and sequence length.

The idea: let frequency decide what becomes a unit

Suppose you must compress a text by inventing new abbreviations. A sensible strategy is to find the two symbols that occur next to each other most often, give the pair a new single symbol, and repeat. Common letter pairs become units, then common syllables, then whole common words. That is byte-pair encoding, originally a data compression idea, adapted to build subword vocabularies for neural translation by Sennrich and colleagues (2016).

Learning: count, merge, repeat

The learning phase uses a table of word counts from a training corpus. Every word is first written as a sequence of characters followed by an end-of-word marker. Then, for a chosen number of rounds:

1. Count every adjacent pair of symbols over all words, weighting each word by how often it occurs.
2. Pick the pair with the highest count. Break ties by a fixed rule so that the result is reproducible.
3. Replace every occurrence of that pair, in every word, by one new symbol that joins the two.
4. Write the pair at the end of the merge list. The vocabulary has grown by one symbol.

The merge list is the tokenizer. Its order matters: a later merge can only use symbols that earlier merges created.

Encoding: replay the merges in order

To encode a new word, write it as characters plus the end marker, then apply the merges in the order they were learned. Wherever the pair of a merge appears, join it. When the list is finished, the remaining symbols are the tokens. A word seen often in training collapses to one token; a word never seen collapses only as far as its parts were seen, and in the worst case stays as characters. Nothing is ever unknown, because single characters are always in the vocabulary.

Why it works so well in practice

Frequency is a good proxy for usefulness. A piece that is common appears in many contexts, so its embedding gets many training examples; a rare piece is not given its own token and is spelled out from common ones. The vocabulary size is simply the number of base symbols plus the number of merges, a knob you choose before training the tokenizer.

The mathematics: pair counts, vocabulary size and compression

Let the corpus be a set of distinct words w, each with a count c(w). Write each word as a symbol sequence s₁, …, s_k. The count of an adjacent pair (a, b) is

w

a distinct word type in the corpus, written as symbols plus the end marker.

c(w)

how many times the word occurs in the corpus (a word-count table, not a list of all running text).

a, b

two symbols that sit next to each other; initially characters, later merged symbols.

#{ i : … }

how many positions i of the word hold the pair (a, b); this counts overlaps inside one word.

Each merge adds one symbol, so after M merges

where V_base is the number of base symbols: about 26 in a lowercase toy example, 256 for byte-level BPE. GPT-2’s tokenizer has 256 byte symbols and 50,000 merges, plus one special end-of-text token: 256 + 50,000 + 1 = 50,257. The merges needed for a given text are decided by the data, but the budget M is chosen by the designer.

Each merge replaces two symbols by one wherever the pair appears, so the total number of symbols in the corpus falls by exactly the pair’s count (counted without overlaps). If the corpus has N_sym symbols before merge j and the merged pair had count n_j, then

Counts only get smaller as merges proceed, since later pairs involve rarer symbols. That is why the first merges give the largest compression and later ones give diminishing returns, while each one adds a vocabulary entry that must be learned and stored.

A worked example: four words, seven merges

Use the word counts low 5, lower 2, newest 6, widest 3. Each word is spelled as characters plus the end marker, for instance n e w e s t </w>.

Round 1. Count pairs. e+s occurs in newest (6) and widest (3): 9. s+t: 9. t+</w>: 9. w+e occurs in lower (2) and newest (6): 8. l+o: 5 + 2 = 7. o+w: 7. Three pairs tie at 9; take the alphabetically first, e+s, and merge it. Now newest is n e w es t </w> and widest is w i d es t </w>.

Round 2. es+t now has count 9, as does t+</w>; es+t wins the tie. Round 3. est+</w> has count 9 and wins outright. Notice what happened: the learner discovered the suffix “est” at the end of a word, just from counts.

Encoding a new word. The word “lowest” was not in the corpus. Start with l o w e s t </w>. Replay the merges in order: e+s gives l o w es t </w>; es+t gives l o w est </w>; est+</w> gives l o w est</w>; l+o gives lo w est</w>; lo+w gives low est</w>. The remaining merges do not apply. The result is two tokens, low and est</w>, built from pieces seen in different words.

The same algorithm in Python

from collections import Counter

counts = {"low": 5, "lower": 2, "newest": 6, "widest": 3}
words = {tuple(w) + ("</w>",): c for w, c in counts.items()}
merges = []

def merge_pair(seq, pair):
    out, i = [], 0
    while i < len(seq):
        if i < len(seq) - 1 and (seq[i], seq[i + 1]) == pair:
            out.append(seq[i] + seq[i + 1]); i += 2
        else:
            out.append(seq[i]); i += 1
    return tuple(out)

for _ in range(7):
    pairs = Counter()
    for seq, c in words.items():
        for a, b in zip(seq, seq[1:]):
            pairs[(a, b)] += c
    best = min(pairs, key=lambda p: (-pairs[p], p))     # highest count, then alphabetical
    merges.append(best)
    words = {merge_pair(seq, best): c for seq, c in words.items()}

print(merges[:3])   # [('e', 's'), ('es', 't'), ('est', '</w>')]

def encode(word):
    seq = tuple(word) + ("</w>",)
    for pair in merges:
        seq = merge_pair(seq, pair)
    return list(seq)

print(encode("lowest"))   # ['low', 'est</w>']

The two functions are the whole algorithm. A production tokenizer adds speed (it never rescans the full corpus after every merge) and a pre-splitting step, but the logic is the same.

Engineering implications and limitations

Byte-level BPE. GPT-2 does not start from characters but from the 256 possible byte values of the UTF-8 encoding of the text. Every string of any language, emoji or binary-looking junk is a sequence of bytes, so every string can be encoded and nothing is ever unknown. The price: a rare character may cost two to four tokens (several bytes), which is why non-English text and emoji tend to use more tokens.

Pre-tokenization. Real tokenizers first split text with a pattern (words, numbers, punctuation, spaces) and only merge inside each piece. This stops merges from crossing word boundaries and from gluing unrelated punctuation to words. GPT-2 attaches a leading space to the word that follows, which is why “ robot” and “robot” are different tokens.

Use a library for real work. The book uses OpenAI’s tiktoken package with the GPT-2 vocabulary for the main text. Training your own tokenizer on a big corpus is the job of a fast implementation; the Python above is for understanding, and it would take far too long on gigabytes of text.

Tokenizer and model are a pair. Retraining a tokenizer changes every ID, so a model trained with one tokenizer cannot use another. Version them together.

Train the tokenizer on representative text. A tokenizer trained on English prose splits source code, equations or part numbers into many pieces. If your robot’s logs or commands matter, check how they tokenize before choosing it.

Deterministic tie-breaking. Different tie-breaking rules give different (equally valid) merge lists. If you reimplement a tokenizer, copy the reference rules exactly, or encodings will differ by one token and results will not match.

Common misconceptions

Engineering takeaways

1. BPE starts from characters or bytes and repeatedly merges the most frequent adjacent pair; the ordered merge list is the tokenizer.
2. Encoding replays the merges in order; frequent words become one token and unseen words become several pieces, never unknown.
3. Vocabulary size is base symbols plus merges: 256 + 50,000 + 1 special token = 50,257 for GPT-2.
4. Early merges shorten the text most; later ones give diminishing returns and rarely trained embeddings.
5. Use a fast library for real corpora, pre-split text with a pattern, and keep the tokenizer versioned with the model.

References and further reading

For the usage of the GPT-2 tokenizer through tiktoken and the discussion of byte-pair encoding see Chapter 2 of the book (companion code linked above).

• Sennrich, R., Haddow, B. and Birch, A. (2016). Neural Machine Translation of Rare Words with Subword Units. arXiv:1508.07909.
• Sennrich et al. (2016), Subword Units (research paper)
• Build a Large Language Model (From Scratch), Chapter 2: Working with Text Data (primary book reference)

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: the special tokens that mark the end of text, padding and unknown words, and why byte-level tokenization never fails.

Related content

Nothing below is required to finish this lesson.

• Before
  LM2-T2: Characters, Words, Subwords and Token IDs

  Compare tokenization granularities and build a vocabulary that maps tokens to integer IDs.

• Lab
  LM2-L2: Implement Byte-Pair Encoding

  Learn merges from a tiny corpus and encode text with them.