Tokenization fundamentals: Worked examples — AI-ML deep dive

Two phases, never confuse them

Before any example, pin down the two distinct phases most confusion comes from mixing:

The scenario matrix

Now list every case class tokenization can throw at us. Think of this like listing every quadrant before doing angle problems — we want to hit each cell at least once.

#	Case class	What is unusual about it	Covered by
A	Common word, fully in vocab	Greedy path, 1 word → 1 token	Ex 1
B	Rare / long word	Falls back to several subword pieces	Ex 2
C	Out-of-vocabulary chunk	No merge helps; drops to characters/bytes	Ex 3
D	Whitespace & leading-space marker	The `Ġ`/`▁` space encoding, reversibility	Ex 4
E	Empty string / single char (degenerate)	The zero-length and length-one edge cases	Ex 5
F	BPE tie-break (two pairs equal frequency)	Which merge wins, and why order matters	Ex 6
G	Real-world word problem	Cost/sequence-length estimate for a batch	Ex 7
H	Multilingual / emoji bytes	One "character" = many byte-tokens (fertility blow-up)	Ex 8
I	Exam twist: decode ambiguity	Why decode is not just "look up and concat"	Ex 9

Every worked example below is tagged with its cell letter.

Setup: a tiny tokenizer we can fully hand-run

To make examples checkable, we fix a small learned tokenizer. It came from the parent note's corpus ["low","lower","newest","newest","widest"] plus a couple of extras. Its merge list (in learned order — order is sacred, first merge applies first) is:

The rule for applying merges to a single pre-token: start from its characters, then scan the merge list in order; whenever the current merge's pair appears, glue every occurrence, then move to the next merge. Never reach across into a neighbouring pre-token. This is exactly how BPE encodes at inference (see 4.2.02-BPE-algorithm).

Worked example Ex 2 — Cell B: rare/long word breaks into subwords

Encode newest.

Forecast: will it be 1 token, or more?

Characters: n e w e s t. Why? BPE always starts from the base characters before rebuilding.
Merge 1 l o: no l here → skip. Why? A merge only fires if its exact pair is currently adjacent; it is not, so we skip.
Merge 2 lo w: no lo → skip. Why? lo was never created (merge 1 didn't fire), so its follow-up can't apply.
Merge 3 e s → es: the pair e s appears once (positions 4–5) → n e w es t. Why? We follow list order; e s is the first applicable merge, so it fires now.
Merge 4 es t → est: pair es t present → n e w est. Why? Merge 3 just created es, and it now sits next to t, matching merge 4's pair exactly — so it fires in turn.
Merge 5 n e → ne: pair n e present → ne w est. Why? The original n and e at the start are still adjacent and untouched, matching merge 5's pair, so this merge applies.
Merge 6 ne w → new: pair ne w present → new est. Why? Merge 5 just created ne, which sits directly before w, matching merge 6's pair — the final merge fires and the scan ends.

Result: ["new", "est"] → 2 tokens.

Verify: The word split into meaningful morphemes new + est — exactly the compositionality BPE is designed for. widest would reuse the same est token, confirming shared structure. Fertility $= 2/1 = 2$ . ✓

Worked example Ex 3 — Cell C: out-of-vocabulary, falls to characters

Encode wild (word never merged, but every letter is a base token).

Forecast: does it become <unk>, or letters?

Characters: w i l d. Why? Start from the base level as always.
Scan all six merges: l o? no. lo w? no. e s? no. es t? no. n e? no. ne w? no. Why this matters: not one merge's pair is present in w i l d, so nothing glues — the word contains no learned pattern.
Stop. Output stays at character level. Why? When the merge list is exhausted with no matches, the current (character) segmentation is the final answer.

Result: ["w", "i", "l", "d"] → 4 tokens.

Why NOT <unk>? <unk> is only used when a symbol is not in the base vocabulary at all. Because our base vocab is character-level and includes w,i,l,d, every letter is representable, so a true byte/char-level BPE has no OOV — it degrades gracefully into pieces (this is the OOV escape route from 4.1.05-Vocabulary-and-OV).

Verify: All four characters w,i,l,d are individually in the base set → the decode concat("w","i","l","d") = "wild" recovers the input exactly. Fertility here $= 4/1 = 4$ (high, because it is rare). ✓

Worked example Ex 4 — Cell D: leading-space marker and reversibility

Encode low lower the GPT-2 way (spaces become ▁, first word has no leading space), keeping the two phases separate.

Forecast: how many final tokens, and where does the space live?

Phase 1 — pre-tokenization (produces pre-tokens, not final tokens):

Split on whitespace and attach the leading-space marker: pre-tokens ["low", "▁lower"]. Why? Attaching the space to the following word (as ▁) lets decode reinsert spaces perfectly — the marker records "there was a space before this word."

Phase 2 — BPE inside each pre-token separately (no crossing boundaries): 2. BPE-tokenize low: characters l o w → merge 1 → lo w → merge 2 → low. Result: ["low"]. Why? Same chain as Ex 1; the pre-token low fully merges into one token. 3. BPE-tokenize ▁lower: characters ▁ l o w e r. Merge 1 l o → lo fires (▁ lo w e r); merge 2 lo w → low fires (▁ low e r); no further merge matches ▁, low, e, or r. Result: ["▁", "low", "e", "r"]. Why? Our tiny list has no merge gluing ▁ to low, nor low+e, so this pre-token yields four BPE tokens.

Final token sequence (concatenate the two phase-2 results): ["low", "▁", "low", "e", "r"] → 5 tokens.

Decode check (now consistent with the real output): look up each token's string and concatenate: "low" + "▁" + "low" + "e" + "r" = "low▁lower"; then replace every ▁ with a real space: "low lower".

Verify: Round-trip decode(encode("low lower")) == "low lower". Exactly one ▁ appears in the sequence → exactly one internal space is restored, and the first word has no marker → no leading space. ✓ (See 3.4.03-Sequence-length-and-padding for why deterministic reversibility matters when batching.)

Worked example Ex 5 — Cell E: degenerate inputs (empty & single char)

Encode "" (empty string) and "a" (single char not in a merge).

Forecast: what does zero-length text produce?

Empty string:

Pre-tokenize "" → [] (no words). Why? There is nothing to split, so pre-tokenization yields zero pre-tokens.
No pre-tokens means no characters to merge and nothing to number. Result: [] → 0 tokens. (In practice a model may still prepend <bos>, giving [<bos>], but the content is empty.)

Single char "a":

Characters: a. Why? One pre-token a, dropped to its single character.
No merge pair even exists (a pair needs two symbols; we have one). Every merge is skipped trivially. Why? BPE merges operate on adjacent pairs; with only one symbol there is no pair to match. Result: ["a"] → 1 token.

Verify: length of encode("") is $0$ ; length of encode("a") is $1$ . Both round-trip: decode([]) = "", decode(["a"]) = "a". The "pair needs ≥2 symbols" rule is the boundary condition that keeps single characters safe. ✓

Worked example Ex 6 — Cell F: BPE tie-break — two pairs, equal frequency

We show two mini-trainings. Part 1: a clear winner. Part 2: a genuine tie, resolved by a fixed rule.

Part 1 — clear winner. Train on ["low","low","ow"]. Count adjacent pairs across the corpus (characters l o w | l o w | o w):

l o: appears in low×2 = 2 times
o w: appears in low×2 + ow×1 = 3 times

Forecast: guess the winner before step 2.

List counts: o w = 3, l o = 2. Why count pairs, not single chars? BPE's objective is to merge the most frequent adjacent pair — that is the argmax rule from the parent note; single-character counts don't tell us which pattern to compress.
o w (3) beats l o (2). Merge o w → ow; corpus becomes l ow | l ow | ow. Why? The argmax picks the strictly larger count, so the higher-frequency pair is compressed first.
Recount on the new corpus: l ow appears twice → merge l ow → low. Why? After the first merge, we recompute pair counts on the updated tokens (frequencies change after every merge), and now l ow is the most frequent, so it fires next.

Part 2 — a genuine tie. Train on ["ab","cd"]. Characters: a b | c d. Pair counts: a b = 1, c d = 1 — a true tie.

The argmax is ambiguous (both count 1), so we invoke the tie-break rule. Why? Training must be reproducible: two runs must produce identical vocabularies, so the ambiguity cannot be left to chance.
Apply a fixed deterministic rule — here, lexicographically smallest pair wins. Compare ("a","b") vs ("c","d"): ("a","b") is smaller, so merge a b → ab first. Why? Lexicographic order is a total, deterministic ordering, so it always yields exactly one winner regardless of hardware or dictionary iteration order.
Next round: only c d remains with count 1 → merge c d → cd. Why? With the tie resolved, the remaining pair is now the unique argmax.

Verify: Part 1 winner count $3 > 2$ ; after two merges the tokens ow then low exist (vocab grew by exactly 2). Part 2: ("a","b") < ("c","d") lexicographically, so ab is created before cd. ✓

Worked example Ex 7 — Cell G: real-world word problem (cost estimate)

You send 10,000 chat messages to a model. Each message averages 18 words, and your tokenizer's fertility is 1.4 tokens/word. The API charges $0.50 per 1,000,000 tokens. Estimate the token count and cost.

Forecast: rough guess of total tokens first.

Tokens per message $= words \times fertility = 18 \times 1.4 = 25.2$ . Why fertility? Fertility $=$ tokens/words is defined (see top of page) to convert word counts into token counts — multiplying by it is the inverse of that division.
Total tokens $= 10, 000 \times 25.2 = 252, 000$ . Why multiply by message count? Each message contributes its own token cost, so total $=$ per-message cost $\times$ number of messages.
Cost $= \dfrac{252{,}000}{1{,}000{,}000} \times \$ 0.50 = 0.252 \times 0.50 = $0.126$. Why divide by a million? The price is quoted per million tokens, so we convert our raw token count into "millions" before multiplying by the per-million price.

Result: ≈ 252,000 tokens, ≈ $0.13.

Verify: Units cancel: $msg \times \frac{words}{msg} \times \frac{tokens}{word} = tokens$ , then $\text{tokens}\times\frac{\$ }{\text{token}}=$ $. S ani t y : a f r a c t i o n o f a ce n tp er t h o u s an d s h or t m ess a g es i s pl a u s ib l e . ✓ B ec a u se T r an s f or m er cos t sc a l es l ik e$ O(n^2)$ in sequence length, halving fertility would more than halve compute for long inputs — see 5.1.02-Transformer-architecture.

Worked example Ex 8 — Cell H: emoji / multilingual byte blow-up

Encode the emoji 🌍 with a byte-level BPE (no merge learned for it).

Forecast: 1 token? or many?

🌍 is not one byte. In UTF-8 it is the 4-byte sequence F0 9F 8C 8D. Why bytes? Byte-level BPE (GPT-2 style) works on the 256 possible bytes, guaranteeing any Unicode text is representable with no OOV.
With no learned merge combining these bytes, each stays separate. Why? Just like Ex 3, when no merge's pair matches, the segmentation stays at the base (here byte) level. Result: 4 tokens for one visible character.

Verify: len("🌍".encode("utf-8")) == 4. This is why fertility explodes for scripts under-represented in training — a whole language can cost several tokens per character (the core issue in 4.2.08-Multilingual-tokenization). ✓

Worked example Ex 9 — Cell I: exam twist — decode is not naive concat

You receive IDs whose tokens are ["est", "▁", "ne", "w"]. Naively concatenating gives "est▁new". Is the decode "est new"? Explain the trap and give the exact algorithm.

Forecast: guess the correct output string.

First, the exact decode algorithm (two stages, in order):

Now run it:

Lookup + concatenate the token strings: "est" + "▁" + "ne" + "w" = "est▁new". Why no separator? Sub-pieces like ne+w are meant to fuse into new seamlessly; inserting separators would corrupt words.
Marker cleanup: replace the single ▁ with a real space → "est new". Why is this the trap? Students expect "look up each ID, glue, done." But the marker ▁ is not literal text — step 3 must transform it back into whitespace, otherwise the raw ▁ glyph would leak into the output.
Note the silent fusion: ne+w carry no marker between them, so they join into new with no space — only markered gaps become spaces. Why? Spaces are restored only where a ▁ marker sat; a boundary with no marker is an internal sub-word join, not a word break.

Result: decode = "est new" (7 characters: e s t space n e w).

Verify: Character count: "est new" has length 7. Marker rule: exactly one ▁ present → exactly one space inserted → exactly one word boundary. The internal ne|w join produces no space (no marker). ✓

Recall Self-test (reveal after guessing)

Encoding low gives how many tokens? ::: 1 (it is a single learned merge chain → ["low"]) What is fertility, in one line? ::: tokens ÷ words — the average number of BPE tokens each word costs. A pre-token and a BPE token — what's the difference? ::: A pre-token is a whitespace/punctuation chunk (a boundary); BPE runs inside it and may output one or several BPE tokens; BPE never merges across pre-token boundaries. Why does byte-level BPE have no OOV? ::: Every byte 0–255 is in the base vocab, so any text degrades into byte tokens instead of <unk>. In a true frequency tie during BPE training, what resolves it? ::: A fixed deterministic tie-break (e.g. lexicographically smallest pair) so training is reproducible. How many tokens does 🌍 cost in byte-level BPE with no learned merge? ::: 4 (its UTF-8 encoding is 4 bytes). Why isn't decode just lookup-and-concat? ::: After lookup+concat, a cleanup step must replace every ▁/Ġ marker with a real space.

Where this connects

The merge mechanics: 4.2.02-BPE-algorithm
Likelihood-based cousins: 4.2.03-WordPiece-and-SentencePiece
What happens to token IDs next: 4.3.01-Word-embedings
OOV theory behind Ex 3/Ex 8: 4.1.05-Vocabulary-and-OV, 4.2.08-Multilingual-tokenization
Why sequence length (Ex 7) is expensive: 5.1.02-Transformer-architecture, 3.4.03-Sequence-length-and-padding

The figure above shows Ex 2 as a merge tree: characters at the bottom fuse upward along the learned merges into new and est.

This second figure shows fertility across our examples — how many tokens each input costs — making the "rare = more tokens" pattern visible at a glance.