BPE Encoding Algorithm
What you'll learn: How to apply learned BPE merge rules to tokenize new text in the correct sequence.
The Core Idea
Once you've trained a BPE tokenizer (learning which character pairs to merge), you need to actually use those merge rules to tokenize new text. The key insight: you must apply merges in the exact order they were learned during training. This ensures consistency—the same text always produces the same tokens.
Think of it like following a recipe where the order matters: you can't frost a cake before baking it. Similarly, if during training you learned to merge "e" + "r" before merging "er" + "s", you must follow that same sequence when encoding.
How BPE Encoding Works
- Start with characters: Break your input text into individual characters (or bytes)
- Apply merge rules in order: Go through your learned merge list from first to last
- Find and merge: For each rule, scan the current token sequence and merge all occurrences of that pair
- Repeat: Continue until you've applied all merge rules
- Result: Your final token sequence
Example Walkthrough
Suppose you learned these merges in order: [("l", "o"), ("lo", "w")]
To encode "lower":
- Start:
["l", "o", "w", "e", "r"] - Apply merge 1 ("l"+"o"):
["lo", "w", "e", "r"] - Apply merge 2 ("lo"+"w"):
["low", "e", "r"] - Final tokens:
["low", "e", "r"]
Notice how merge order matters: we only got "low" because we merged "l"+"o" first!
Key Takeaway: BPE encoding applies learned merge rules sequentially in training order, transforming character sequences into subword tokens through iterative pair replacement.