Byte-pair encoding by hand: six merges

Tokenization & decoding · Part 2 of 8

Where do those subword pieces come from? From an almost embarrassingly simple procedure called byte-pair encoding, or BPE: start with letters, and keep gluing together the pair that occurs most often. Let us do it by hand.

The recipe

1. Start with characters. Split every word into single letters and add an end-of-word mark, written _.
2. Count pairs. Count how often each pair of neighbouring symbols occurs, weighting by how often the word occurs.
3. Merge the winner. Replace every occurrence of the most frequent pair by one new symbol.
4. Repeat until you have as many merges as you decided on. The vocabulary is the starting letters plus every symbol you created.

A tiny example

Our toy “training text” has five words: stall (6 times), talk (8), walls (4), talks (7) and walks (2). The first six merges, in order:

1. a + l → al (seen 27 times)
2. t + al → tal (seen 21 times)
3. tal + k → talk (seen 15 times)
4. s + _ → s_ (seen 13 times)
5. talk + _ → talk_ (seen 8 times)
6. talk + s_ → talks_ (seen 7 times)

The merge list is the tokenizer

To tokenize new text, split it into letters and replay the merges in the same order. Words the tokenizer never saw still work: stalks becomes s | talks_, built from pieces learned elsewhere, and walk becomes w | al | k | _, a little clumsy because this tiny text never saw it whole. With more text, common words end up as single tokens and only rare ones are cut up.

Real tokenizers work the same way but on bytes rather than letters (“byte-level BPE”). That guarantees that any text, in any script, can be represented with no unknown token. It does not guarantee that the text will be represented efficiently, which is the subject of the next post.

Takeaways

• BPE starts from characters and repeatedly merges the most frequent adjacent pair.
• The ordered list of merges is the whole tokenizer.
• Unseen words are still split into learned pieces.
• Byte-level BPE can represent any text, but not always efficiently.

Next in the series (Part 3): Not every language pays the same price