Problem. A corpus is given as word frequencies. Each word starts as a sequence of single-character symbols. One BPE step:
- count every adjacent pair of symbols across the corpus, weighted by word frequency;
- pick the most frequent pair (ties: the lexicographically smallest pair);
- replace every occurrence of that pair, left to right, with one merged symbol.
words = {"learn": 5, "learner": 2, "learning": 6, "lean": 3, "earn": 4}
pair counts: (e, a) 20, (a, r) 17, (r, n) 17, (l, e) 16, ...
merge (e, a): l ea r n l ea r n e r l ea r n i n g l ea n ea r n
Repeat the step thousands of times and frequent words become single symbols while rare words stay split into pieces: that's the subword vocabulary of most language models. Training runs many steps, so the cost of one step decides whether training takes minutes or days.
ML context. BPE (and its byte-level variant) is how GPT-style tokenizers are trained. Every merge adds one token to the vocabulary. The efficient step here, touching only the words that contain the merged pair, is the core of real tokenizer trainers; lesson 15.12 runs the full training loop with a priority queue over pair counts.