WordPiece and SentencePiece: Worked examples — AI-ML deep dive

This is a hands-on drill page for WordPiece and SentencePiece. The parent note built the theory; here we run the machines by hand on every kind of input they can meet, so you never freeze on an exam or a weird real-world string.

Before we start, one promise: no symbol appears before it is explained. If you have not yet met terms like "greedy longest-match", "soft count", "log-likelihood", or "PMI", read the callouts below — each is rebuilt from zero right where it is used.

The scenario matrix

A tokenizer is a little machine. Its behaviour changes depending on what kind of string you feed it. Below is the full list of "cell types" — every distinct situation the two algorithms (WordPiece greedy match and SentencePiece unigram) can hit. Each worked example afterwards is tagged with the cell it covers.

#	Cell (scenario class)	Which algorithm shows it
A	Whole word is in vocab (no split)	WordPiece greedy
B	Word splits into several `##` pieces	WordPiece greedy
C	A character is missing from vocab → `[UNK]`	WordPiece greedy
D	Two candidate merges, one frequent but low-PMI, one rarer but high-PMI	WordPiece training
E	Spaces / no-space languages via the `▁` marker	SentencePiece encode + decode
F	Multiple valid segmentations → pick the most probable	SentencePiece unigram inference
G	Degenerate input: empty string, single character, all-unknown	both, edge cases
H	Real-world word problem (morphology of a novel word)	WordPiece / SentencePiece
I	Exam-style twist: greedy longest-match gives a worse split than the unigram optimum	both, contrast

The figures on this page are not decorations — each one is a step of the derivation drawn out. When a figure appears, stop and read the picture first; the text just narrates what the picture already shows.

Tools we will use — built from zero

Four ideas power every example. We define each in plain words first.

[!example] Example 1 — Cell A: the word is already a token

Statement. Vocab = ["the", "un", "##happ", "##i", "##ness"]. Tokenize "the".

Forecast: guess the output before reading on. (One token? Two?)

Stand at position 0 of "the". Why this step? Greedy always starts at the left edge.
Longest chunk in vocab starting here that fits: try "the" — it is in the vocab. Grab it. Why this step? Longest-match takes the biggest legal bite; "the" is the whole word, nothing longer exists.
Left edge is now at the end of the string → stop. Why this step? With nothing left to read, the loop terminates.

Output: ["the"].

Verify: one token, no ## (it is word-initial), and gluing it back gives "the". ✓ Frequent words stay whole — exactly the design goal from the parent note.

[!example] Example 2 — Cell B: split into `##` pieces

Statement. Vocab = ["un", "##happ", "##i", "##ness", "happiness"]. Tokenize "unhappiness".

Forecast: how many pieces? Where do the ## marks land?

The figure below is the walk: read the arrows left to right, each bite is a numbered step.

Figure s04 — The word unhappiness printed once at the top; four labelled arrows underneath show each greedy bite in order (un, then the red mid-word piece ##happ, then ##i, then ##ness). The single red arrow marks the first non-initial (##) piece, reminding you that everything after the first bite wears a ##.

Position 0. Try the whole "unhappiness", then shrink one letter at a time: "unhappines", … none in vocab, down to "un" — found. Why this step? Greedy tries longest first and only shortens when forced, so it must fail on every longer prefix before accepting "un".
New left edge after "un" → remaining string "happiness". This piece is not word-initial, so any match here wears a ##. Why this step? We are now inside the word, and ## is precisely the marker for "glued to the previous piece."
Longest match on "happiness": the token "##happ" matches the letters happ. Why this step? "happiness" as a whole is only in vocab as a word-initial token "happiness"; but here we are mid-word, so we need the ##-prefixed versions. "##happ" is the longest such.
Remaining "iness" → longest ## match is "##i" (letters i). Why this step? No longer ## entry (like ##in or ##iness) is in the vocab, so the single-letter ##i is the biggest legal bite.
Remaining "ness" → "##ness" matches. Left edge at end → stop. Why this step? ##ness consumes the rest of the word in one bite, so the loop ends.

Output: ["un", "##happ", "##i", "##ness"].

Verify: strip every ## and concatenate: un + happ + i + ness = unhappiness. ✓ Four tokens, first has no ##, the rest do — matches the "non-initial pieces are prefixed" rule.

[!example] Example 3 — Cell C: an unknown character → `[UNK]`

Statement. Vocab = ["ca", "##t", "[UNK]"]. Tokenize "caź" (the letter ź is not anywhere in vocab).

Forecast: does the whole word die, or just the bad part?

Position 0: longest match is "ca". Grab it. Why this step? Greedy longest-match always takes the biggest legal bite at the left edge; "ca" is the longest vocab entry that fits.
Remaining "ź". Look for "##ź" or "ź" — nothing. Greedy shrinks to a single character and still finds nothing. Why this step? Once no vocab entry matches even a single leftover character, greedy has no legal bite to take and cannot advance.
When no subword (not even a single character) matches, WordPiece cannot proceed on this word. The whole word is replaced by the special unknown token. Why this step? WordPiece never crosses word boundaries and cannot invent a token, so an untokenizable word collapses to [UNK] entirely rather than emitting a partial split.

Output: ["[UNK]"] (the entire word "caź" becomes one [UNK]).

Verify: this is the classic OOV failure mode. Note we did not get ["ca", "[UNK]"] — in standard WordPiece, if any piece of a word is untokenizable, the entire word is emitted as [UNK]. Contrast: a byte-level tokenizer would never hit this. ✓

[!example] Example 4 — Cell D: frequent-but-low-PMI vs rare-but-high-PMI merge

Statement. During WordPiece training we must choose which pair to merge first. Corpus statistics below. First, how the table is built:

pair $(a, b)$	$count (ab)$	$P (ab)$	$P (a)$	$P (b)$
`(e, r)`	1000	0.010	0.100	0.090
`(q, u)`	50	0.0005	0.0060	0.0090

Forecast: (e,r) is 20× more frequent. Does it win the merge?

Use the gain formula $Δ L = count (ab) \cdot lo g \frac{P ( ab )}{P ( a ) P ( b )}$ (natural log).

For (e,r): ratio $= \frac{0.010}{0.100 \times 0.090} = \frac{0.010}{0.0090} \approx 1.111$ . Why this step? The ratio is the "together vs by chance" test. $1.111$ is barely above $1$ — e and r are common independently, so seeing them together is almost expected.
$lo g (1.111) \approx 0.10536$ . Multiply by count $1000$ : $Δ L \approx 105.4$ . Why this step? The gain formula weights the log-ratio by how many times the merge would apply.
For (q,u): ratio $= \frac{0.0005}{0.0060 \times 0.0090} = \frac{0.0005}{0.000054} \approx 9.259$ . Why this step? q is almost never seen without u, so together-vs-chance is far above $1$ — high PMI.
$lo g (9.259) \approx 2.2257$ . Multiply by count $50$ : $Δ L \approx 111.3$ . Why this step? Even with only 50 occurrences, the large log-ratio lifts the gain above (e,r)'s.

Output: merge (q,u) first — its gain $111.3$ beats (e,r)'s $105.4$ , despite being 20× rarer.

Verify: this is the reason WordPiece $\neq =$ BPE. BPE (raw count) would pick (e,r) (count 1000). WordPiece (PMI-weighted) picks (q,u). Both gains are re-checked numerically below. ✓

Figure s01 — Two pairs on the x-axis. Black bars (left axis) show the raw count(ab): (e,r) towers at 1000 vs (q,u) at 50. The paired bars (right axis) show the merge gain $Δ L$ ; the red bar for (q,u) is the taller of the two gains, so despite far lower count it wins the merge. The figure visually demonstrates that count-ranking and gain-ranking disagree.

Look at the red bar: even though the black "count" bar for (e,r) towers over (q,u), the red "gain" bar for (q,u) wins — the log-ratio multiplier flips the ranking.

[!example] Example 5 — Cell E: the `▁` space marker, encode and decode

Statement. SentencePiece vocab = ["▁", "▁H", "ello", "▁w", "orld"]. Encode "Hello world", then decode back.

Forecast: where does the space go — into a token or between tokens?

The figure traces the round-trip: raw text → ▁-stream → tokens → back to text.

Figure s05 — Four stacked boxes read top to bottom: (1) raw "Hello world", (2) the red "▁Hello▁world" after every space becomes ▁, (3) the token list [▁H | ello | ▁w | orld], (4) the decoded "Hello world" after swapping ▁ back to spaces. Downward arrows connect the stages; the red stage highlights that the space now lives inside a token, which is what makes the round-trip exact.

Encode:

Replace every space with ▁: "Hello world" → "▁Hello▁world". Why this step? SentencePiece treats the raw stream as one string; the space is now an ordinary symbol attached to the next word.
Segment left to right using vocab: "▁H" | "ello" | "▁w" | "orld". Why this step? These are the vocab pieces that tile the stream; note the space ▁ lives inside "▁H" and "▁w", marking word starts.

Output (encode): ["▁H", "ello", "▁w", "orld"].

Decode: 3. Concatenate all tokens: ▁H + ello + ▁w + orld = "▁Hello▁world". Why this step? Detokenizing is pure gluing — no boundaries are guessed because the pieces already carry their own ▁. 4. Replace every ▁ with a space: "Hello world". Why this step? ▁ was our stand-in for space, so undoing that swap restores the original spacing exactly.

Verify: decoded string equals the original character for character, including the single interior space. This is the reversibility property. Notice there is no ## anywhere — SentencePiece uses plain substrings, boundaries are recovered from ▁ alone. ✓

[!example] Example 6 — Cell F: pick the most probable segmentation

Statement. SentencePiece unigram, vocab & probabilities:

token	$P (x)$	token	$P (x)$
`dog`	0.40	`g`	0.10
`s`	0.20	`d`	0.05
`do`	0.10	`o`	0.05
`gs`	0.05	`dogs`	0.05

Tokenize "dogs" at inference (unigram picks the single most probable cut).

Forecast: will it keep "dogs" whole, or split into ["dog","s"]?

Enumerate the valid cuts and multiply token probs (unigram assumption):
- ["dog","s"] $= 0.40 \times 0.20 = 0.0800$
- ["dogs"] $= 0.05$
- ["do","g","s"] $= 0.10 \times 0.10 \times 0.20 = 0.0020$
- ["d","o","gs"] $= 0.05 \times 0.05 \times 0.05 = 0.000125$
- ["d","o","g","s"] $= 0.05 \times 0.05 \times 0.10 \times 0.20 = 0.00005$ Why this step? Each product is $P (segmentation)$ ; inference wants the biggest.
Compare: the largest product is 0.0800 from ["dog","s"]. Why this step? Inference is defined as "return the single most probable cut," so we simply take the max.

Output: ["dog", "s"].

Verify: $0.0800 > 0.05 > 0.0020 > \dots$ — highest product wins, checked below. In practice SentencePiece finds this maximum with a Viterbi search (defined in Example 7) in linear time, not by brute force. ✓

Figure s02 — Horizontal bars, one per candidate segmentation of "dogs", length = $P (segmentation)$ . The top red bar [dog,s] (0.080) is clearly longest, followed by black [dogs] (0.050); the remaining cuts are near-zero slivers. An arrow labels the red bar as the chosen cut, showing inference just picks the longest bar.

The red bar is the winning ["dog","s"] — it stands clearly above the next contender ["dogs"], so that is the chosen cut.

[!example] Example 7 — Cell F (soft): the E-step expected counts

Before the steps, three words this example needs — each built from zero:

Definition EM, E-step, M-step, and Viterbi — in plain words

EM ("Expectation–Maximization") is a two-phase training loop used when we cannot see the "right" answer directly. Here we never observe which cut produced a word, so we guess softly, then improve.

E-step (Expectation): with the current token probabilities fixed, spread a soft weight over all possible cuts of each word and tally how much each token is "expected" to have been used. Output = expected counts.
M-step (Maximization): with those expected counts fixed, re-set each $P (x)$ to its share of the counts — the setting that maximizes $L$ . Then loop back to the E-step.
Viterbi search: a fast bookkeeping trick (dynamic programming) that finds the single best cut, or the total over all cuts, in linear time — instead of listing the exponentially many cuts by hand. Think of it as filling a small table left-to-right, reusing earlier answers.

Statement. Same numbers as Example 6, but now we are training (an E-step of EM), not inferring. Instead of picking one cut, we spread a soft weight over all cuts and count each token by its share.

Forecast: the token dog — will its expected count be near $1$ , or well below?

The figure shows the soft weights as a pie: [dog,s] takes most of the mass, [dogs] the rest.

Figure s06 — A pie chart of the posterior weights over the segmentations of "dogs". The red wedge [dog,s] fills about 61% of the circle, the black wedge [dogs] about 38%, and a thin grey wedge holds the remaining ~2% of the three tiny cuts. The pie makes concrete that the E-step assigns fractional credit across all cuts rather than choosing one.

We already have the five products. Their sum is the normalizer $Z = 0.0800 + 0.05 + 0.0020 + 0.000125 + 0.00005 = 0.132175.$ Why this step? To turn products into probabilities that add to $1$ , we need their total to divide by.
Posterior weight of each cut $= P (cut) / Z$ . Why this step? Dividing every product by their sum $Z$ rescales the five numbers so they add to exactly $1$ — that is what makes them a valid probability distribution over segmentations, so a token can now claim a fractional "share" of the word.
- [dog,s]: $0.0800/0.132175 \approx 0.6053$
- [dogs]: $0.05/0.132175 \approx 0.3783$
- the other three together $\approx 0.0165$ .
Expected (soft) count of a token = sum of the posterior weights of every cut that contains it. Why this step? Each cut "votes" for its tokens with its own probability; a token present in a very likely cut earns most of its count from there.
- $E [dog] = 0.6053$ (only [dog,s] contains it).
- $E [dogs] = 0.3783$ .
- $E [s] = 0.6053$ (from [dog,s]) $+ 0.0020/ Z$ (from [do,g,s]) $+ 0.00005/ Z$ (from [d,o,g,s]) $\approx 0.6053 + 0.01513 + 0.00038 \approx 0.6208$ .

Output: $E [dog] \approx 0.605, E [dogs] \approx 0.378, E [s] \approx 0.621$ .

Verify: the posterior weights over all cuts must sum to $1$ : $0.6053 + 0.3783 + 0.0165 \approx 1.000$ . ✓ In the M-step these soft counts get re-normalized into new $P (x)$ ; tokens like do, gs collect almost nothing and are eventually pruned. This soft assignment (vs Example 6's hard pick) is the training-vs-inference difference.

[!example] Example 8 — Cell G: degenerate inputs

Statement. Run each machine on the three nastiest inputs: (i) the empty string "", (ii) a single unknown symbol "§" with vocab ["a","##b"], (iii) a word made only of known single chars "ab" with vocab ["a","##b"].

Forecast: which of these emit [UNK], which emit nothing, which tile cleanly?

Empty string. Left edge is already at the end. Nothing to grab → output [] (an empty token list). SentencePiece: "" → "" → [] too. Why this step? The greedy loop's exit condition ("left edge at end") is already true before we take a single bite, so it emits nothing.
"§" with no matching char. Position 0, no "§" and no "##§" in vocab, shrink to single char — still nothing → whole word ["[UNK]"]. Why this step? Same OOV collapse as Example 3; a lone unknown symbol is the smallest possible untokenizable word, so the entire word becomes one [UNK].
"ab". Position 0: longest match is "a" (word-initial). Remaining "b" is non-initial → "##b" matches → ["a","##b"]. Why this step? Even a two-letter word obeys the ## rule: the first bite is bare because it is word-initial, the second wears ## because it is inside the word.

Output: [], ["[UNK]"], ["a","##b"] respectively.

Verify: reassemble case (iii): a + b (drop ##) $=$ ab ✓. Empty input gives empty output (idempotent, reversible) ✓. Unknown symbol gives a single [UNK], never a crash ✓. All three degenerate corners behave.

[!example] Example 9 — Cell H: real-world morphology of a novel word

Statement. A user types the never-before-seen word "retokenizing". WordPiece vocab = ["re", "##token", "##izing", "##ize", "##ing", "token"]. Tokenize it, and explain what the model "understands".

Forecast: will it recover the meaningful pieces re + token + izing?

Position 0: longest match is "re" (word-initial). Why this step? No longer word-initial token matches at the left edge; "re" is the longest legal bite there.
Remaining "tokenizing", now non-initial. Longest ## match: "##token" (letters token). Why this step? We are inside the word, so only ## entries are legal; "##token" is the longest one that starts here.
Remaining "izing". Longest ## match: "##izing" matches exactly. Why this step? "##izing" (5 letters) beats "##ize" and "##ing", and greedy always takes the longest legal bite.

Output: ["re", "##token", "##izing"].

Verify: glue back → re + token + izing = retokenizing ✓. The model never saw this word, yet it recovered the prefix re-, the root token, and the suffix cluster -izing. This is the compositional payoff: unseen words become combinations of seen pieces, solving OOV. ✓

[!example] Example 10 — Cell I: the exam twist (greedy vs optimal)

Statement. This is the trap examiners love. Vocab with unigram probabilities:

token	$P (x)$
`ab`	0.30
`cd`	0.30
`abc`	0.10
`d`	0.01
`a`	0.05
`bcd`	0.02

Word "abcd". (a) What does a left-to-right greedy longest-match produce? (b) What does the unigram most-probable cut produce? Are they the same?

Forecast: you might assume both agree. Do they?

Greedy. Position 0: longest vocab match is "abc" (3 letters, beats "ab"). Grab it. Remaining "d" → "d". Why this step? Greedy only ever looks for the longest bite at the current edge; it cannot see the future consequences of that bite. Greedy output: ["abc", "d"], probability $0.10 \times 0.01 = 0.0010$ .
Unigram optimum. Score all cuts:
- ["ab","cd"] $= 0.30 \times 0.30 = 0.0900$
- ["abc","d"] $= 0.10 \times 0.01 = 0.0010$
- ["a","bcd"] $= 0.05 \times 0.02 = 0.0010$ Why this step? Unigram compares whole segmentations, so it can prefer two medium pieces over one long-then-tiny piece.
Best is ["ab","cd"] at $0.0900$ . Why this step? Unigram inference returns the segmentation with the maximum product, which is ["ab","cd"].

Output: greedy gives ["abc","d"] ( $P = 0.0010$ ); unigram gives ["ab","cd"] ( $P = 0.0900$ ) — different, and unigram's is 90× more probable.

Verify: $0.0900 > 0.0010$ confirmed below. Lesson: greedy longest-match (WordPiece) and probability-maximizing (SentencePiece unigram) can disagree. Grabbing the longest first piece is not the same as the best overall cut. ✓

Figure s03 — Three bars, one per candidate cut of "abcd", height = $P (segmentation)$ . The red bar [ab,cd] (0.090, the unigram optimum) towers over the short black bar [abc,d] (0.001, what greedy actually returns) and the equally short [a,bcd]. An arrow notes the red bar is 90× more probable than greedy's choice — a picture of why "longest first" is not "best overall."

The red bar ["ab","cd"] dwarfs greedy's ["abc","d"] — a picture of why "longest first" is not "best overall".

[!recall]- Self-test (reveal after you try)

Every cell A–I covered?

A(Ex1) B(Ex2) C(Ex3) D(Ex4) E(Ex5) F(Ex6,7) G(Ex8) H(Ex9) I(Ex10) — all nine.

Why does WordPiece pick (q,u) over the 20× more frequent (e,r)?

The PMI log-ratio for (q,u) is large (q rarely appears without u), and count × log-ratio = 111.3 beats 105.4.

What replaces an untokenizable WordPiece word?

The whole word becomes a single [UNK], not a partial split.

Can greedy longest-match differ from the unigram most-probable cut?

Yes — Example 10: greedy ["abc","d"] vs optimal ["ab","cd"].

What is the expected count of a token in the E-step?

The sum of posterior weights of every segmentation that contains that token.

What does

L

stand for and does training raise or lower it?

Log-likelihood; training raises it (equivalently lowers the loss

- L