Exercises — Tokenization fundamentals

• "ing" — subword (a suffix, not a standalone word)
• "cat" — word (a complete word)
• "?" — character (a single symbol)
• "un" — subword (a prefix)
• "z" — character (a single letter)

Why: a character is one symbol; a word stands alone with meaning; a subword is a meaningful chunk smaller than a word (prefix/suffix/stem fragment).

• $A$ = Normalization + Pre-tokenization + Token Splitting (cleaning then splitting into token strings).
• $B$ = Numericalization — the dictionary lookup that turns token strings into integer IDs.
• Integers come from $B$. Everything before $B$ is still text.

Fertility is tokens per word: $\text{Fertility}=\frac{\text{tokens}}{\text{words}}=\frac{11}{8}=1.375$ This sits inside the typical BPE range of $1.3$–$1.5$, so the tokenizer is behaving normally.

Known tokens $=200-3=197$. $\text{Coverage}=\frac{197}{200}=0.985=98.5\%$ $98.5\%<99.5\%$, so coverage is below the healthy threshold — too many unknowns, hinting the vocabulary is a poor fit for this document.

Encode. Pre-tokenize with the space marker Ġ: $[\text{"Hello"},\text{","},\text{"G˙world"},\text{"!"}]$ Look each token up in the vocabulary above: $[15496,11,995,50256]$ Decode. Reverse-lookup each ID, concatenate, then swap every Ġ for a space: $\text{"Hello"}+\text{","}+\text{"G˙world"}+\text{"!"}=\text{"Hello,G˙world!"}\to \text{"Hello, world!"}$ The Ġ is what makes decoding reversible — it remembers the space belonged before world.

(Note: the parent note used a shortened toy ID list [15496, 11, 995, 0] where ! was written as 0. That 0 clashes with <pad>, so here ! gets its own distinct ID 50256 — every token needs a unique integer.)

Multiply each in-word pair by that word's count:

• l o: in low(×3) + lower(×2) $=5$
• o w: in low(×3) + lower(×2) $=5$
• e s: in newest(×2) + widest(×1) $=3$
• s t: in newest(×2) + widest(×1) $=3$

l o and o w tie at 5 (the maximum). BPE breaks ties by a fixed rule (e.g. first seen); the parent note merges l o first. Either choice is valid as long as it is deterministic.

Why pairs across ␣ are excluded: the space marker ␣ fences off each word. BPE only merges pairs inside a single word, so cross-boundary pairs like w ␣ (end of low) or ␣ l (start of next low) are never candidates. Why do this? If merges could cross word boundaries, the tokenizer would glue the end of one word to the start of the next (e.g. low + lower → a wl token), producing tokens that depend on random word order and never generalise. Fencing with ␣ keeps every learned token a genuine within-word chunk (prefix/stem/suffix).

Merging lo and low only touches the low… words — it does not change any e s or s t counts. So: $\text{count}(\text{"e s"})=3(\text{newest}\times 2+\text{widest}\times 1)$ Merge e s→es. Now count es t:

• newest → n e w es t : one es t, ×2 = 2
• widest → w i d es t : one es t, ×1 = 1 $\text{count}(\text{"es t"})=2+1=3$ So est becomes a shared suffix for both newest and widest. This is the whole point of BPE — the suffix est emerges purely from frequency and is now reusable.

First, a notation we use here: let $V_t$ = the ==vocabulary after $t$ merges==, and $|V_t|$ = its size. So $V_0$ is the starting character vocabulary (zero merges done), $V_1$ after one merge, and so on.

Each merge adds exactly one new token, so: $|V_{t+1}|=|V_t|+1$ After 4 merges that is $+4$ tokens. If the character vocab started at $|V_0|=11$ (the set {l,o,w,e,r,n,s,t,i,d,␣}), then: $|V_4|=11+4=15$

Causal chain:

1. Word-level treats each word as atomic → a rare word not in the top $50,000$ has no token → becomes <unk> → information lost.
2. BPE keeps all characters (or bytes) as base tokens in $V_0$, and only adds merges on top.
3. Therefore any string can always be spelled out from those base units, even one never seen in training ("COVID-19" → C o v i d - 1 9 or partial merges).
4. Result: no out-of-vocabulary word exists — the worst case is more tokens, never a missing one.

Trade-off: rare words get long token sequences (higher fertility), but they are never dropped.

$\frac{n_{\text{char}}}{n_{\text{word}}}=\frac{250}{45}\approx 5.556$ Squared (attention is quadratic in length): ${\left(\frac{250}{45}\right)}^2\approx 30.86$ Character-level costs about 31× more attention compute per document. But word-level pays with $6\%$ <unk> (lost meaning). Tension: shrink $\bar{n}$ for speed (favours words) vs keep coverage high (favours characters). BPE sits in the middle — moderate $\bar{n}$, $\approx 100\%$ coverage — which is why it wins. See sequence length and the $O(n^2)$ attention.

(a) Tokens = fertility × words: $n_A=1.30\times 1000=1300,n_B=1.60\times 1000=1600$ (b) Cost ratio: $\frac{n_B^2}{n_A^2}={\left(\frac{1600}{1300}\right)}^2={\left(\frac{16}{13}\right)}^2\approx 1.515$ B costs about $1.52\times$ A's attention compute. (c) Both clear the $99.5\%$ coverage bar ($99.8\%$ and $99.9\%$). Since it is latency-bound, pick the cheaper one → A. B's extra $0.1\%$ coverage buys almost nothing but costs $\approx 52\%$ more compute. Choose A.

$n_{\text{eng}}=1.4\times 500=700,n_{\text{other}}=3.2\times 500=1600$ Fertility ratio: $\frac{3.2}{1.4}\approx 2.286$ The under-represented script is shredded into more than 2× as many tokens per word — its words fall back toward characters/bytes because few merges cover it. This is the multilingual fairness / cost gap: the same content costs more tokens (hence more money and more sequence length) in low-resource languages. See multilingual tokenization.

How to read this: the ::: marks a hidden answer — cover everything to the right of :::, recall it, then check. Fertility is defined as ::: tokens divided by words. Coverage must stay above ::: 99.5%. Each BPE merge changes vocabulary size by ::: exactly +1. Attention cost scales with sequence length $n$ (the number of tokens in the sequence) as ::: $O(n^2)$. BPE avoids OOV because ::: characters/bytes remain in the base vocabulary, so any string can always be spelled out.