Recipe
Run one round of byte-pair encoding
Use when: you're given a small word-frequency corpus and asked to find the next BPE merge (or to run several merges in sequence)
Goal: the single next symbol pair to merge, and the corpus's new symbol sequences after that merge
Taught in Byte-pair encoding by hand
Quick recipe
-
1
Write each word as its individual characters, with an end-of-word marker appended.
Example
"low" (freq 5) becomes the symbol sequence l, o, w, _
Why: every merge builds up from single characters -- there is no shortcut past this starting point.
-
2
For every word, count each adjacent symbol pair once per occurrence of that word.
Example
"low" (freq 5) contributes 5 to the pair (l, o), 5 to (o, w), and 5 to (w, _).
Why: a pair that appears in a common word should outweigh the same pair appearing in a rare one, and weighting by frequency is how that gets enforced.
-
3
Sum each pair's count across every word in the corpus, then find the largest total. If two or more pairs tie for the largest total, merge whichever pair was encountered first, scanning the corpus word by word, left to right -- a fixed, repeatable rule, never a free choice.
Why: this is the pair BPE has decided is worth its own symbol -- the entire algorithm is this one greedy choice, repeated.
-
4
Replace every occurrence of the winning pair, in every word, with one new symbol.
Example
Merging (e, s) into "es" turns "newest" from n, e, w, e, s, t, _ into n, e, w, es, t, _.
Why: the new symbol now behaves as a single unit in every future round -- it can itself be merged with a neighbor next time.
-
5
Go back to counting pairs (Step 2) using the updated symbol sequences, and continue for as many merges as the target vocabulary size calls for.
Why: each merge changes which pairs exist, so the count has to be redone from scratch every round -- an old count is stale the moment a merge happens.
Common mistakes
- Forgetting to weight pair counts by word frequency, and instead counting each distinct word only once.
- Merging a pair that spans an end-of-word marker into a following word's first character -- the end-of-word marker exists specifically to prevent this.
- Re-merging a pair from an earlier round using its OLD count instead of recounting after every merge.
- Stopping after finding the most frequent pair once, instead of repeating the whole count-merge cycle for every remaining merge in the budget.