Topic 3

Byte pair encoding: learning merges

Byte pair encodingByte pair encoding (BPE)A way to learn a subword vocabulary: start from single symbols and repeatedly merge the most frequent adjacent pair. Encoding replays the learned merges in order.Where this is taught (BPE) is the most widely used way to learn a subwordSubwordA token that can be a whole word or a fragment of one. Common words get one token; rare words are built from several.Where this is taught vocabularyVocabularyThe fixed list of every token a tokenizer knows. Its size is a design choice made before training.Where this is taught from data. Sennrich, Haddow and Birch adapted it from a data-compression algorithm to segment rare words for neural machine translation. The idea fits in one sentence: start from single symbols, then repeatedly merge the most frequent adjacent pair into a new symbol, until the vocabulary is the size you want.

BPE has two separate phases, and confusing them is the most common misunderstanding:

• Training runs once, over a large corpus, and produces an ordered list of merge rules. This page.
• Encoding runs on every request and replays those merge rules, in order, on new text. Next page.

Suppose the training corpus contains only four words: cat ×4, cats ×3, hat ×6, that ×2. Split every word into characters, so the base vocabulary is a, c, h, s, t. Now count every adjacent pair, weighted by how often its word appears.

Run the training yourself

Press Merge to apply one merge at a time. Watch the pair counts change after each merge: fusing a + t destroys the h + a pair and creates h + at. Then edit the corpus and see how the merges change.

After four merges with the default corpus, the learned vocabulary is a, c, h, s, t, at, hat, cat, cats and, more importantly, the ordered merge list is a+t, h+at, c+at, cat+s.