Byte-pair encoding, worked through by hand
Word-level vocabularies break on the first unseen word, and character-level ones make sequences very long. Byte-pair encoding sits between the two: start from characters and repeatedly merge the most frequent adjacent pair until the vocabulary reaches the size you want.
A tiny corpus
Take the counts low:5, lower:2, newest:6, widest:3. Split every word into
characters plus an end-of-word mark. The most frequent pair is e s (9 times), so it
becomes es. Next comes es t, then est </w>, and the
suffix -est has become a single token after three merges.
merges = [("e","s"), ("es","t"), ("est","</w>"), ("l","o"), ("lo","w")]
What to remember
- The model is the ordered merge list. Applying merges in a different order gives a different segmentation.
- Frequent words end up as one token, rare words fall apart into pieces, and nothing is ever out of vocabulary.
- Vocabulary size is a trade-off between sequence length and embedding table size. For a single language 16–32k merges is a common starting point.
- Whitespace handling differs between implementations. Compare token counts only when the pre-tokenizer is the same.
I keep a short script that prints the merge table step by step. Watching the first fifty merges on a new corpus is a quick way to spot encoding problems and stray markup.