Spot the error: 'BPE finds the globally optimal vocabulary by iteratively merging the most frequent pair.'

The error is the word **globally optimal**, repeated in the claim that BPE is an exact optimization algorithm. BPE is not exact and gives no global guarantee. BPE is a greedy algorithm. At each step it counts adjacent pairs, picks the single most frequent one, merges it everywhere, and repeats. The choice at each step is locally optimal: best by frequency at that moment. But greedy algorithms commit to each choice permanently and never look ahead or backtrack. That is why the cumulative result is only locally optimal. A merge that looks best at step 5 can block a combination that would have produced a better vocabulary overall. There is no guarantee the final vocabulary is the best possible for the target size. The fix is to say BPE finds a locally optimal vocabulary through greedy frequency-based merging, not a globally optimal one.

The mistake is calling BPE **globally optimal** and an exact optimization algorithm. BPE is greedy, so it is neither. At each step BPE merges the pair with the highest current frequency: $$\text{merge} = \arg\max_{(a,b)} \; \text{count}(a, b)$$ That is a locally optimal decision, the best move at that instant. But BPE never looks ahead and never backtracks. It commits to each merge permanently. A choice that maximizes frequency now can foreclose a combination that would have produced a smaller or better-compressing vocabulary later. So the cumulative outcome carries no global guarantee. The corrected statement: BPE finds a locally optimal vocabulary via greedy frequency-based merging; it does not guarantee the globally optimal vocabulary for a given target size. The useful contrast is the Unigram LM tokenizer. It starts from a large candidate set and prunes tokens that hurt corpus likelihood least, using an EM-style objective over the whole vocabulary. That global, likelihood-driven view is what greedy merging structurally cannot offer.