Byte-Pair Encoding (BPE): Worked examples — AI-ML deep dive

We reuse two ideas from the parent, restated in plain words so nothing is assumed:

Definition The notation and the two things BPE stores

The arrow → in a rule means "becomes": the two symbols on its left, when they sit side by side, get glued into the one symbol on its right. So e s → es reads "an e directly followed by an s becomes the single symbol es." The arrow is not subtraction or logic — it is purely "replace-left-with-right".
A merge rule is one such instruction " $A B \to A B$ ": whenever symbol $A$ is immediately followed by symbol $B$ , glue them into one symbol $A B$ . Rules are numbered in the order they were learned; rule 1 is applied before rule 2, and so on.
A token is one symbol in the current sequence — it might be a single character like g, or a glued-up chunk like est, or a whole word ending like bug</w>.
</w> (read "end-of-word") is a fake extra character we stick after every word so the model can tell est inside a word from est at a word's end.
$V$ (read "target vocabulary size") is the number the trainer stops at — how many distinct tokens we want in the final vocabulary. Same corpus + same $V$ + same tie-break = identical vocabulary.

Two words used constantly below:

Training = learning the merge rules from a corpus. Each iteration counts every adjacent pair across the whole corpus, then merges exactly one pair — the single most frequent — everywhere it occurs. One rule is born per iteration.
Encoding = using already-learned rules to chop a brand-new word into tokens. Here we sweep through the fixed rule list.

The scenario matrix

Every situation BPE can throw at you falls into one of these cells. The figure below lays them out as a grid — glance back at it as you work each example, since every worked example fills exactly one cell of this picture (its tag, like Cell A, points at the grid square).

#	Cell (case class)	What makes it tricky	Example
A	Clean training, no ties	baseline — pick the single most frequent pair	Ex 1
B	Tie during training	two pairs equally frequent → need a deterministic tie-break	Ex 2
C	Encoding, all rules fire	new word fully covered by learned merges	Ex 3
D	Encoding, a rule is blocked	a character sits between two pieces that would have merged	Ex 4
E	Rule-order trap (greedy)	applying rules out of order gives a different, wrong answer	Ex 5
F	Unknown / unseen character	a character never seen in training appears	Ex 6
G	Degenerate inputs	empty string, single character, one-symbol vocab	Ex 7
H	Limiting behaviour	how many merges before the corpus stops shrinking	Ex 8
I	Real-world word problem	morphology: why subwords generalize	Ex 9
J	Exam-style twist	given only the token output, reconstruct the rules	Ex 10

About the figure: it is a 5-column × 2-row grid of ten rectangles, one per matrix row. Each rectangle shows the cell letter (big, top) and a short label (bottom) exactly matching the table. The fill colour encodes the family: teal = pure training cells (A, B, G, J), orange = encoding-mechanics cells (C, D, H), plum = "gotcha" cells (E traps, F unseen input, I meaning). There are no axes — it is a legend/map, not a plot. As you finish each example, mentally tick off its square; Ex 1–10 below cover the ten cells one-to-one, so by Ex 10 the whole grid is filled.

Forecast: guess the winning pair before reading on. Which adjacent pair shows up most often once you weight by word count?

Split into characters + </w>.
```
3×:  a b </w>
2×:  a b c </w>
```
Why this step? BPE always starts from single characters so it can represent any input; the whole vocabulary is built upward from here.
Count adjacent pairs, weighting each occurrence by its word's count.
- (a, b): ab(×3) + abc(×2) = 5
- (b, </w>): ab(×3) = 3
- (b, c): abc(×2) = 2
- (c, </w>): abc(×2) = 2
Why this step? Greedy training merges the pair that compresses the corpus the most, which is the one that occurs most often, so we literally count occurrences.
Merge the single winner (a, b) → ab, replacing it everywhere in this one iteration.
```
3×:  ab </w>
2×:  ab c </w>
```
Why this step? (a,b) at 5 has no rival — no tie-break needed. This is the baseline case. Note that one iteration merges exactly one pair type ((a,b)), though it replaces all its occurrences.

Verify: total pair-count of (a,b) = $3 + 2 = 5$ , strictly larger than every other pair (max of the rest is 3). Merge is unambiguous. ✓

Forecast: which pair? And — could two different people get two different vocabularies here?

Split + count.
```
4×:  x y </w>
4×:  y x </w>
```
- (x, y): xy(×4) = 4
- (y, x): yx(×4) = 4
- (y, </w>): xy(×4) = 4
- (x, </w>): yx(×4) = 4
Why this step? Four pairs are dead even at 4. If we merged "whichever" we'd get different vocabularies on different machines — that breaks reproducibility.
Break the tie with a stated total ordering. We define it precisely: compare each candidate as the ordered pair (first symbol, second symbol). To compare two symbols, compare them character by character using their Unicode code points, left to right — the standard "dictionary" order on strings. The extra symbol </w> is compared as its literal four-character string </w>; its first character < has code point 60, which is smaller than any letter (x=120, y=121), so any symbol beginning with < sorts before any letter. Sorting the four candidates $(^{'} x^{'},^{'} < / w >^{'}) < (^{'} x^{'},^{'} y^{'}) < (^{'} y^{'},^{'} < / w >^{'}) < (^{'} y^{'},^{'} x^{'})$ the smallest is ('x','</w>'). Why this step? A deterministic tie-break — the exact same total ordering on every machine — is what makes "same corpus + same $V$ → same vocabulary" true. Any fixed ordering works; we just pin one down and share it.
Merge (x, </w>) → x</w>. Every implementation using this same string-ordering tie-break gets the identical result.

Verify: all four candidate pairs have count exactly $4$ ; the tie is real. Dictionary-order (Unicode code-point) comparison of the four pair-tuples, with </w> starting at code point 60, puts ('x','</w>') first. ✓

Forecast: how many tokens come out?

Split. l o w e s t </w> Why this step? Encoding always begins from characters, exactly like training's step 0.
Greedy encoding: scan for the lowest-numbered rule that matches anywhere, apply it, repeat.
- Rule 1 (l,o) matches → lo w e s t </w>
- Rule 2 (lo,w) matches → low e s t </w>
- Rule 3 (e,s) matches → low es t </w>
- Rule 4 (es,t) matches → low est </w>
Why this step? We always try the earliest-learned rule first because later rules were built assuming earlier merges already happened (est can only form after es exists).
No rule matches → stop. Output [low, est, </w>].

Verify: 6 input characters (+</w>) collapse to 3 tokens; each output token is a chunk that appears in the rule list (low from rule 2, est from rule 4, </w> untouched). ✓

Forecast: will ug</w> ever form?

Split. h u g s </w>
Apply rule 1 (u,g): h ug s </w>. Why this step? (u,g) is adjacent, so rule 1 fires.
Try rule 2 (ug, </w>): look for ug immediately followed by </w>. Here we have ug, then s, then </w>. The s sits between them, so ug and </w> are not adjacent. Why this step? Merge rules only fire on directly adjacent symbols. A single intervening character blocks the merge entirely.
No rule matches → stop. Output [h, ug, s, </w>].

Verify: rule 2 requires the literal adjacency ug </w>; scanning h ug s </w> finds no such adjacency (the pair present is ug s, then s </w>). Correctly blocked → 4 tokens. ✓

Forecast: is the answer [ab, c] or [a, bc]?

Split. a b c </w>
Correct greedy way — lowest rule index first. Rule 1 (a,b) fires → ab c </w>. Now rule 2 needs (b,c), but b has been eaten into ab; the pair present is (ab, c) which matches no rule. Stop. Output [ab, c, </w>]. Why this step? Greedy encoding's "locally best" = smallest rule index, not left-to-right scanning of the word — so rule 1 wins the contested b.
Wrong way (illustration only) — if you'd applied rule 2 first: (b,c)→bc gives a bc </w>, then (a,b) no longer exists → output [a, bc, </w>]. Different answer! Why this shows the trap: both rules "wanted" the b. Only the earlier-learned rule is allowed to claim it, guaranteeing every encoder produces the same tokens.

Verify: the two candidate outputs [ab,c] and [a,bc] genuinely differ; enforcing "smallest rule index first" selects [ab,c] uniquely. ✓

Forecast: does BPE crash, or emit <UNK>, or something else?

Split. z a b </w>. Why this step? The base vocabulary is the set of characters seen in training, here {a, b, </w>}. The unseen z is simply kept as its own single-character symbol — the parent note's headline promise is that decomposing down to characters means any string is representable, so there is no <UNK>.
Apply rule 1 (a,b): z ab </w>. Why this step? z is just another single symbol sitting there; rules operate around it normally.
No rule mentions z → it stays alone. Output [z, ab, </w>].

Verify: output length = 3 tokens; the unseen z survives as its own token (never dropped, never <UNK>), while the known pair ab still merges. ✓

Recall Why zero

<UNK> tokens? Because the base vocabulary is the individual characters, any string can be spelled out symbol by symbol. ::: The worst case is "every character is its own token" — long, but never unrepresentable. (Real systems push this even further by using raw bytes as the base, so even never-seen scripts work; the parent note keeps to the character-level picture, which is all we need here.)

Forecast: what's the token count for each?

(a) Empty string. Split → </w> only (or nothing, depending on convention; we keep </w>). No adjacent pair exists, so no rule fires. Output [</w>]. Why this step? A merge needs two symbols; with fewer than two nothing can happen. Degenerate but well-defined.
(b) Single character "a". Split → a </w>. Only possible pair is (a, </w>); if no rule covers it, output [a, </w>]. Why this step? Confirms the algorithm never errors on length-1 words — it simply has nothing to merge unless a rule matches.
(c) No rules learned (vocab = base chars only), encode "ab". Split → a b </w>, no rules → output [a, b, </w>]. Why this step? With zero merges, BPE degrades gracefully to character-level tokenization — the well-known lower bound.

Verify: counts are (a) 1 token, (b) 2 tokens, (c) 3 tokens; each equals "characters + </w>, minus zero merges." ✓

Forecast: can training crush aaaa down to one token? How many rules does it take?

First, name the quantity: let $n$ = the number of identical characters in the run; here $n = 4$ .

Split. a a a a </w> (so $n = 4$ symbols before </w>).
Iteration 1 learns rule a a → aa. Training merges the single most frequent pair, (a,a), replacing every non-overlapping occurrence in one pass (scan left to right; after gluing positions 1–2 into aa, continue from position 3): a a a a → aa aa. Corpus is now aa aa </w>. Why this step? One iteration = one new rule = one merged pair type, replaced everywhere. (a,a) is the only pair, so it wins outright.
Iteration 2 learns a different rule aa aa → aaaa. Now the most frequent (only) pair is (aa, aa) — note the symbols are aa, not a, so this is a genuinely new rule, not a repeat of iteration 1's a a → aa. Merging gives aaaa </w> — one token. Why this step? After iteration 1 there are no more (a,a) pairs left to merge (they all became aa), so training must pick a new pair type; the pair that now exists is (aa,aa).
Iteration 3: no pair remains. The sequence is aaaa </w>; the only adjacency is (aaaa, </w>), which (if we stop before merging word-endings) leaves nothing frequent to compress. Merging has bottomed out. Why this matters: this mirrors the parent's "diminishing returns" — once the frequent internal pairs are gone, extra vocabulary slots buy you nothing.
Counting the rules — the $⌈ lo g_{2} n ⌉$ fact. Each iteration here at best doubles the length of the chunk being built (a→aa→aaaa). To turn a run of $n$ identical characters into one token by such doublings takes $⌈ lo g_{2} n ⌉$ distinct rules. For $n = 4$ : $⌈ lo g_{2} 4 ⌉ = 2$ , matching the two distinct rules a a → aa and aa aa → aaaa. Why "distinct"? Point (3) established each stage merges a different-sized symbol, so these are two separate rules in the learned list, not one rule reused.

Verify: applying the two distinct learned rules a a→aa (folding both (a,a) occurrences in one pass) then aa aa→aaaa to aaaa (4 chars) yields the single token aaaa; and $⌈ lo g_{2} 4 ⌉ = 2$ counts those two rules. ✓

Forecast: how many pieces, and which linguistic units do they map to?

Split. u n h a p p i n e s s </w> — 11 characters plus </w>. Why this step? Encoding always begins from characters.
Apply the learned merges greedily until the frequent subwords assemble. The internal merges (learned earlier for un, happi, ness) glue the runs, yielding the segmentation $un + happi + ness + </w> .$ Why happi, not happy? In English the adjective happy becomes happi before the suffix -ness (happy → happiness). So the characters actually adjacent to -ness are h a p p i, and it is that character run — happi — that BPE sees frequently and merges.
What the model gains. It has seen un (negation) in unhappy, undo, unfair; it has seen ness (noun-maker) in happiness, kindness. So even if unhappiness is rare or unseen as a whole word, the model composes its meaning from familiar parts. Why this matters: this is the entire payoff over word-level tokenization — generalization to unseen words via shared subwords, feeding cleaner vectors into the 3.1.05-Embedding-Layer. These subword IDs then flow into 4.3.01-Language-Model-Basics as the atomic prediction units.

Verify: un+happi+ness reassembled = unhappiness (11 letters); concatenation reproduces the original string exactly, confirming a lossless segmentation. ✓

Forecast: how many rules, and in what order?

From "est" → [est]: the three characters e s t fused into one token est. Why this step? To glue three characters into one you need two binary merges (each rule only fuses two symbols), and they must chain so that the intermediate chunk exists before the final glue.
Deduce the two merges and their order. Either (e,s)→es then (es,t)→est, or (s,t)→st then (e,st)→est — both reduce e s t to est. Following the parent note's convention we take the first chain. Final ordered rule set:
```
Rule 1: e s → es
Rule 2: es t → est
```
Why this step? Two rules is the minimum: zero or one rule can never turn three separate characters into a single token, so this is the smallest set that reproduces [est].
Check against "best". Split b e s t </w>. Rule 1 (e,s) fires → b es t </w>; then rule 2 (es,t) fires → b est </w>. No rule mentions b or the pair (b, est), so b stays alone. Output [b, est, </w>] = the given [b, est]. Why this step? A reconstructed rule set is only valid if it reproduces every given encoding; this set reproduces both, and its absence of a b est→best rule is exactly why b stays separate.

Verify: applying {e s→es, es t→est} to best yields [b, est] and to est yields [est]; both match the exam's stated outputs, and no smaller rule set (0 or 1 rules) can fuse three characters into one token. ✓

Cross-check: all ten cells covered

Every matrix cell now has exactly one worked example. The mapping:

Recall Self-test

A rule ug </w>→ug</w> is in your set. Encoding "hugs" — does it fire? ::: No. The s sits between ug and </w>, so they are not adjacent (Cell D). Two pairs tie at count 7 during training. What decides the winner? ::: A fixed deterministic total ordering on the pairs (dictionary order on the symbol strings); never "random" or "first seen" (Cell B). You learned zero merge rules. How does BPE encode text? ::: As pure character-level tokens — the graceful lower bound (Cell G). What does the arrow → mean in a rule? ::: "Becomes" — replace the two left symbols, when adjacent, with the one right symbol.

Related: Byte-Pair Encoding (BPE) · 4.2.01-Tokenization-Overview · 4.2.03-WordPiece-Tokenization · 4.2.04-SentencePiece · 6.2.02-Inference-Optimization