Byte-Pair Encoding (BPE)
BPE, used by GPT and many modern models, builds a subword vocabulary by iteratively merging the most frequent adjacent symbol pair. It solves the out-of-vocabulary problem: common words become single tokens, rare words decompose into known subword pieces — nothing maps to [UNK].
The algorithm, step by step
- Split every training word into characters plus a special end-of-word marker
</w>: "low" →["l","o","w","</w>"]. - Start with the character vocabulary (every unique character is a token).
- Count the frequency of every adjacent pair across all word representations, weighted by word frequency.
- Find the most frequent pair .
- Merge all occurrences of into the new symbol in every word.
- Add to the vocabulary.
- Repeat steps 3–6 until the vocabulary reaches the target size (e.g. 50 000 tokens).
The learned merge list (the ordered sequence of pairs) is the tokenizer: to tokenize new text, apply the same merges in the same order.
Watch it run
Training corpus: "low"×5, "lower"×2, "newest"×6. Step through four merges being learned, then watch the learned merge list tokenize "lowest" — a word that never appears in the corpus. The code panel highlights the line executing at each step.
BPE — learning the merge list, then tokenizing an unseen word
Split every training word into characters plus the end-of-word marker </w>. The starting vocabulary is just the distinct characters — no subwords learned yet.
Step through the two halves of BPE. Training (steps 1–14): count adjacent pairs, merge the most frequent, repeat — the ordered merge list is the whole tokenizer. Inference (steps 15–20): replay those same merges, in the same order, on "lowest" — a word absent from the corpus — and watch it decompose into learned subwords instead of falling back to [UNK].
Three things to notice as you step:
- Frequency is the entire selection rule. The first merge is
(w, e)with count 8 — not because "we" is meaningful, but because that pair happens to be the commonest. Meaningful subwords emerge as a side effect of frequency. - Words without the winning pair are untouched. "low" sits out merge 1 entirely; each merge only rewrites the words that contain the pair.
- The merge list is ordered, and the order is load-bearing. At inference the rules replay in the order they were learned — apply them in a different order and you get different tokens for the same string.
Result: the vocabulary learns reusable subwords. "lowest" was never in the
corpus, yet it tokenizes to ["lo", "we", "s", "t", "</w>"] with no [UNK] —
the same mechanism that turns "unhappiness" into ["un", "happi", "ness"].
Implementation from scratch
vocab = {" ".join(word) + " </w>": freq
for word, freq in [("low", 5), ("lower", 2), ("newest", 6)]}
def get_pairs(vocab):
pairs = {}
for word, freq in vocab.items():
symbols = word.split()
for i in range(len(symbols) - 1):
pair = (symbols[i], symbols[i+1])
pairs[pair] = pairs.get(pair, 0) + freq
return pairs
def merge_vocab(pair, vocab):
new_vocab = {}
bigram = " ".join(pair)
replacement = "".join(pair)
for word, freq in vocab.items():
new_word = word.replace(bigram, replacement)
new_vocab[new_word] = freq
return new_vocab
num_merges = 10
for _ in range(num_merges):
pairs = get_pairs(vocab)
if not pairs:
break
best = max(pairs, key=pairs.get)
vocab = merge_vocab(best, vocab)
print(f"Merged {best} → {''.join(best)}")
Main variants
WordPiece (used by BERT) is similar but merges based on language-model likelihood improvement rather than raw frequency, producing tokens prefixed with ## for word-continuation: "unhappiness" → ["un", "##happi", "##ness"].
Byte-level BPE (GPT-2 onwards) operates on raw bytes instead of Unicode characters — the base vocabulary is exactly 256 symbols and any string is representable, including emoji and arbitrary Unicode.
Vocabulary size trade-off
Bigger vocabulary → shorter sequences (fewer tokens per sentence) but a larger embedding matrix and rarer token updates. GPT-2 used 50 257 tokens; modern LLMs typically use 32k–128k.
Related concepts
- Text Preprocessing: where tokenization fits in the NLP pipeline
- Word Embeddings: what happens to tokens after tokenization