Byte-Pair Encoding (BPE)

What Problem Does BPE Solve?

Three tokenization approaches and their problems:

1. Word-level: Vocabulary explodes (millions of words), can't handle typos/"unknownwords" → <UNK> tokens everywhere
2. Character-level: Small vocab (26-100 chars), but sequences become VERY long, model must learn spelling from scratch
3. BPE (subword-level): Fixed vocab size (10k-50k), handles rare words by decomposition, captures morphology

The 80/20: BPE gets you 80% of word-level efficiency with 20% of the vocabulary size, plus zero <UNK> tokens.

The BPE Algorithm: From First Principles

Why This Design?

• Greedy frequency-based merging: Optimizes for compression (store common patterns once)
• Bottom-up construction: Starts from characters (handles any input) and builds up (captures frequent patterns)
• Deterministic: Same corpus + same $V$ → same vocabulary (reproducible)

BPE Training: Worked Example

Let's train BPE on a tiny corpus with target vocab size = 11. To make counting easy, assume the corpus has these word frequencies: low (×5), lower (×2), newest (×6), widest (×3).

Corpus (with counts): 5× "low" 2× "lower" 6× "newest" 3× "widest"

Step 0: Initialize with Characters

Split each word into characters with a word boundary </w>:

5×:  l o w </w>
2×:  l o w e r </w>
6×:  n e w e s t </w>
3×:  w i d e s t </w>

Base vocabulary $V_0 = \{l, o, w, e, r, n, s, t, i, d, \text{</w>}\}$ → size = 11

Frequencies of pairs (multiply pair occurrences by word count):

• (l, o): appears in low(×5) + lower(×2) = 7
• (o, w): low(×5) + lower(×2) = 7
• (w, </w>): low(×5) = 5
• (w, e): lower(×2) + newest(×6) = 8 ← highest
• (e, s): newest(×6) + widest(×3) = 9 ← actually highest
• (s, t): newest(×6) + widest(×3) = 9
• (e, r): lower(×2) = 2

Step 1: Merge Most Frequent Pair

Top pairs tie at 9: (e, s) and (s, t). Break tie alphabetically → merge (e, s).

New token: es
Updated corpus:

5×:  l o w </w>
2×:  l o w e r </w>
6×:  n e w es t </w>
3×:  w i d es t </w>

$V_1 = V_0 \cup \{\text{es}\}$ → size = 12

Why this step? es is shared by newest and widest (9 times) → maximum compression this round.

Step 2: Next Merge

Recount pairs:

• (es, t): newest(×6) + widest(×3) = 9 ← most frequent
• (w, e): lower(×2) + newest(×6) = 8
• (l, o): 7, (o, w): 7

Merge (es, t) → new token est

Updated corpus:

5×:  l o w </w>
2×:  l o w e r </w>
6×:  n e w est </w>
3×:  w i d est </w>

$V_2 = V_1 \cup \{\text{est}\}$ → size = 13

Continue Until Target Vocab Size...

The algorithm would continue, next merging (w, e) (=8), then (l, o) (=7), then (lo, w), eventually forming subwords like low, est</w>, newest</w>, etc.

Final learned merges (the "BPE merge rules", in order):

1. e s → es
2. es t → est
3. w e → we
4. l o → lo
5. lo w → low
...

Encoding Example: "lowest"

Merge rules learned (simplified, in order):

1. e s → es
2. es t → est
3. l o → lo
4. lo w → low

Step-by-step (apply rules by priority, lowest index first):

Input: l o w e s t </w>

Apply rule 1 (e s→es):   l o w es t </w>
Apply rule 2 (es t→est): l o w est </w>
Apply rule 3 (l o→lo):   lo w est </w>
Apply rule 4 (lo w→low): low est </w>

Output tokens: [low, est, </w>]

Why this encoding? "low" and "est" are frequent subwords. The model will see "est" in "lowest", "newest", "widest" → learns comparative/superlative morphology.

Why BPE Works: The Math

Why this formula? Each merge replaces 2 adjacent symbols with 1 wherever the pair occurs, growing the average token length $k$. So the sequence length shrinks roughly linearly with $k$: $L_{\text{BPE}} \approx C/k$. Crucially, $k$ grows with the number of merges but with diminishing returns — the first merges (very frequent pairs) shorten sequences a lot, later merges (rare pairs) barely help. This is empirical, not a clean logarithmic law in $V$.

Diminishing returns: Going from 10k → 50k vocab increases $k$ only slightly, so the extra sequence-length reduction is small compared to 1k → 10k.

Modern BPE Variants

WordPiece (BERT)

• Similar to BPE but chooses each merge to maximize the training-corpus likelihood under a unigram language model
• Concretely, it picks the pair whose merge gives the largest increase in log-likelihood, $\Delta \log P(\text{corpus})$. For a unigram model this is closely related to the ratio $\frac{P(ab)}{P(a)\,P(b)}$ (pointwise mutual information), but the exact criterion is the likelihood gain, not raw PMI.
• Why: Better theoretical grounding (each merge is chosen to make the data more probable, not just more compressed)

SentencePiece (T5, LLaMA)

• Treats input as a raw byte/character stream (no pre-tokenization on whitespace)
• Learns BPE (or unigram LM) directly on Unicode characters or bytes
• Why: Language-agnostic, treats spaces as normal symbols, works for languages without clear word boundaries

Byte-level BPE (GPT-2, GPT-3)

• Runs BPE on bytes (UTF-8 encoded) instead of characters
• Base vocab = 256 bytes, then merge
• Why: Truly universal (any text in any language), no special handling needed

BPE in Practice: Hyperparameters

The 80/20: 30k vocab, min frequency = 2, byte-level pre-tokenization covers most modern LM needs.

Connections

• 4.2.01-Tokenization-Overview: BPE is one of three major tokenization strategies
• 4.2.03-WordPiece-Tokenization: Variant using likelihood gain instead of raw frequency
• 4.2.04-SentencePiece: Unigram LM + BPE without pre-tokenization
• 4.3.01-Language-Model-Basics: Tokenization is preprocessing for LMs; vocab size affects model size
• 3.1.05-Embedding-Layer: Vocab size $V$ determines embedding matrix size $(V \times d)$
• 6.2.02-Inference-Optimization: Smaller vocab → fewer embedding lookups → faster inference

#flashcards/ai-ml

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)