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

Attempt it

Click any words you think contain an error. Click again to unmark.

Mark at least one word to submit.

Quick reference

TL;DR

BPE is greedy: it merges the highest-frequency pair at each step with no lookahead, so each merge is locally optimal, not globally optimal.

Memory aid

Sign in for the mnemonic that makes this stick. See Pro pricing.

Easy to grasp

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.

Key concepts

BPE Algorithm Greedy Algorithm Unigram LM Tokenizer

Detailed answer & concept explanation

~3 min read

Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.

Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.

Sign in for 5 free unlocks/day or go Pro for unlimited. See Pro pricing.

Quick scan · 2–4 min

Everything important, quickly.

2 min: greedy per-step argmax + no lookahead/backtrack + local vs global optimality + Unigram likelihood pruning + why greedy still ships.

Real-world examples

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.
HuggingFace tokenizers exposes both a greedy BPE trainer and a Unigram trainer, letting teams pick local-greedy speed versus likelihood-driven segmentation.

Interviewer follow-ups

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?

Sign in or go Pro to see the approach for this follow-up.

QWhy does greedy BPE remain the production default despite lacking optimality?

Sign in or go Pro to see the approach for this follow-up.

Don't say this

Red flags and common mistakes that signal junior thinking. Click to expand.

Most common mistake

Calling BPE an exact or globally optimal algorithm. It is greedy: each merge is locally optimal, and the cumulative vocabulary carries no global guarantee.

Sign in or go Pro to see all red flags and common mistakes. See Pro pricing.

60-second cheat sheet

The night-before-the-interview bullets. Scan these on the way to the call.

Sign in for 5 unlocks/day or go Pro for unlimited revision sheets. See Pro pricing.

References

Primary sources. Skim if you want the original framing.