Spot the error: 'BPE finds the globally optimal vocabulary by iteratively merging the most frequent pair.'
Click any words you think contain an error. Click again to unmark.
BPE is greedy: it merges the highest-frequency pair at each step with no lookahead, so each merge is locally optimal, not globally optimal.
Imagine driving home and always turning toward whichever road looks busiest right now, never checking a map. You make a sensible choice at every junction, but the full route can still be far from the shortest one, because a good early turn can lock you out of a better path later. BPE works like that. At each step it merges whatever pair is most frequent right then, commits to it forever, and never reconsiders. The final vocabulary is reasonable but not provably the best. A planner that scored whole routes, which is what the Unigram approach does, could find a better overall answer that no single greedy turn would reveal.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
This question looks like a vocabulary quibble, but it probes whether you understand the kind of algorithm BPE is. Calling it globally optimal is not a minor overstatement; it misclassifies a greedy heuristic as an exact optimizer, and the two have very different guarantees.
The statement makes two linked claims: that BPE finds the globally optimal vocabulary, and that it is an exact optimization algorithm guaranteeing the best possible result for a target size. Both are false for the same underlying reason.
We will establish what greedy means here, why local optimality never adds up to a global proof, how the Unigram LM tokenizer takes a genuinely different approach, and why greedy BPE still wins in production despite all of this.
What 'greedy' means for BPE
BPE builds a vocabulary by repeating one move. Count every adjacent pair in the current corpus representation, take the single most frequent pair, add it as a new symbol, and replace all its occurrences. Repeat until the vocabulary hits the target size.
The decision rule is a pure argmax on current frequency:
Two properties define the greedy character. The choice uses only present information, no estimate of how this merge affects future options. And the choice is irrevocable: once a pair is merged it is never un-merged, and no alternative merge order is ever explored. That is the textbook signature of a greedy algorithm.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
Real products, models, and research that use this idea.
- OpenAI's cl100k_base and o200k_base both use greedy BPE merges; they are fast and deterministic, not provably optimal.
- SentencePiece's Unigram LM mode prunes tokens by corpus likelihood, the global objective BPE's greedy loop lacks, and powers Llama and T5 tokenizers.
What an interviewer would ask next. Try answering before peeking at the approach.
QCan you construct a small example where BPE's greedy choice is provably worse than the optimal vocabulary?
Build a toy corpus where merging the most frequent pair first blocks a later merge that would compress more; compare total token counts under each order.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Calling BPE an exact or globally optimal algorithm. It is greedy: each merge is locally optimal, and the cumulative vocabulary carries no global guarantee.
60 second bullets to scan on the way to the call.
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.