WordPiece and SentencePiece: Visual walkthrough

Step 1 — What is a "unigram model" and why do we score with it?

WHAT. Imagine a bag full of little paper tiles. Each tile has one token printed on it — a token is just a piece of text like play, ##ing, or the. We built these tiles earlier by breaking words into subword pieces (that is what tokenization does). A unigram model is the simplest possible guess about this bag: "to make a sentence, I reach in and pull tiles out one at a time, and the tile I pull next does not depend on the tiles I already pulled."

WHY this tool and not another. We could use a fancier model where the next word depends on the previous words (that is what real language models do). But for choosing how to cut words into pieces, we do not want the answer to depend on sentence context — we want a fixed, reusable vocabulary. So we deliberately pick the model with no context: each token stands alone. That single choice is what makes the whole derivation clean.

PICTURE. Each token $x$ owns a slice of a probability pie — a number $P (x)$ between 0 and 1, and all slices add to 1. Frequent tokens get fat slices; rare tokens get thin ones.

Definition

$P (x)$ — token probability, and how to compute it $P (x)$ is the fraction of the "tile pie" that token $x$ owns. Concretely, count how many times $x$ appears in the tokenized corpus and divide by the total number of tokens: $P (x) = \frac{count ( x )}{N}, N = \sum_{y \in V} count (y)$

$count (x)$ ::: how many times tile $x$ was pulled in the whole corpus
$N$ ::: the grand total number of tile-pulls (all tokens, all words)
$P (x) \geq 0$ always (a count cannot be negative).
$\sum_{x \in V} P (x) = \frac{\sum _{x} count ( x )}{N} = 1$ — the slices of the whole vocabulary $V$ fill the pie exactly.

So "fat slice" literally means "high count relative to the corpus size." This same rule defines the probability of every token — including a token we are about to build. When we later ask about a merged tile ab, its probability is nothing new: $P (ab) = count (ab) / N$ , the corpus count of the pair divided by the same total $N$ . Keep this in your pocket — it is exactly the number we plug in at Step 5.

Step 2 — Scoring a whole corpus: from multiply to add

WHAT. A corpus is our whole pile of text, already cut into tokens $w_{1}, w_{2}, \dots, w_{N}$ . Because each pull is independent (Step 1), the probability of pulling that exact sequence is every slice multiplied together:

$P (corpus) = 1st tile P (w_{1}) \times 2nd tile P (w_{2}) \times \dots \times last tile P (w_{N}) = \prod_{i = 1}^{N} P (w_{i})$

Here $\prod$ (capital pi) just means "multiply all of these," exactly like $\sum$ means "add all of these."

WHY switch to logarithms. Multiplying thousands of numbers smaller than 1 gives an unimaginably tiny number — your computer rounds it to zero. The logarithm is the tool that turns multiplication into addition:

$lo g (a \times b) = lo g a + lo g b$

That single property is the only reason we take a log. Applying it:

$L = lo g P (corpus) = \sum_{i = 1}^{N} lo g P (w_{i})$

We call $L$ (script L) the log-likelihood: how well our tile-bag explains the text. Bigger $L$ = the corpus is more probable under our model = a better vocabulary.

PICTURE. Multiplying tiny slices sinks toward zero; taking logs lifts each into a manageable negative number, and we simply stack (add) them.

Note the log of a number below 1 is negative, so $L$ is a sum of negatives — we want it as close to 0 as possible (least negative).

Step 3 — The question WordPiece keeps asking: "should I glue two tiles into one?"

WHAT. WordPiece grows its vocabulary one tile at a time. At each round it looks at a pair of tiles that sit next to each other — call them $a$ then $b$ — and asks: "If I create a brand-new single tile ab and use it wherever a b appeared, does the corpus become more probable?" If yes, and by the most, it adds ab to the vocabulary.

WHY compare, not just count. BPE answers a different question: "which pair appears most often?" WordPiece asks a smarter one: "which pair benefits the score the most?" To decide, we need to compare $L$ before gluing and $L$ after gluing. The difference is the payoff.

PICTURE. Two adjacent tiles a b become a single fused tile ab. Every place the pair occurred, two slices are replaced by one slice.

Let $count (ab)$ be how many times the pair a-then-b appears in the corpus. That is the number of places affected by the glue.

Step 4 — The score BEFORE gluing

WHAT. Focus only on the pieces that touch the merge; everything else in the corpus is unchanged and cancels out later. Before gluing, each of the $count (ab)$ occurrences contributes two tiles: an a and a b.

WHY. From Step 2, one tile $a$ contributes $lo g P (a)$ and one tile $b$ contributes $lo g P (b)$ . One occurrence therefore adds $lo g P (a) + lo g P (b)$ . There are $count (ab)$ identical occurrences, so we multiply:

$L_{before} = count (ab) \cdot [lo g P (a) + lo g P (b)]$

PICTURE. Two thin slices per occurrence, stacked $count (ab)$ times.

Step 5 — The score AFTER gluing

WHAT. After we create the tile ab, every one of those $count (ab)$ occurrences is now a single tile with its own slice $P (ab)$ .

WHY. One occurrence now contributes $lo g P (ab)$ (one tile, one term). Times $count (ab)$ occurrences:

$L_{after} = count (ab) \cdot lo g P (ab)$

Where does the number $P (ab)$ come from? From the very same rule as any other tile (Step 1): $P (ab) = count (ab) / N$ . The merged tile is not special — its probability is just its corpus count over the total. That is why $count (ab)$ appears twice in the final formula: once as "how many places we affect" and once, hidden inside $P (ab)$ , as "how fat the new slice is."

PICTURE. One fatter slice per occurrence replaces the two thin ones.

Step 6 — Subtract: the merge payoff appears

WHAT. The payoff of gluing is simply "after minus before":

$Δ L = L_{after} - L_{before}$

WHY subtract. Everything in the corpus not touching this pair contributes the same amount to both scores, so it vanishes in the subtraction. Only the affected pieces survive. Plugging Steps 4 and 5 in:

$Δ L = count (ab) lo g P (ab) - count (ab) [lo g P (a) + lo g P (b)]$

Factor out $count (ab)$ :

$Δ L = count (ab) [lo g P (ab) - lo g P (a) - lo g P (b)]$

Now use the log rule backwards — $lo g x - lo g y = lo g \frac{x}{y}$ — to fold the three logs into one:

$Δ L (a, b) = count (ab) \cdot lo g \frac{P ( ab )}{P ( a ) P ( b )}$

PICTURE. The two "before" slices subtract, the "after" slice adds, and what is left is a single log-ratio scaled by how often the pair occurs.

Step 7 — Reading the log-ratio: this is Pointwise Mutual Information

WHAT. The inside piece $lo g \frac{P ( ab )}{P ( a ) P ( b )}$ has its own name: Pointwise Mutual Information (PMI). See Pointwise Mutual Information.

WHY it means "surprise." Ask: if a and b were independent (unrelated), how often would they land side by side by pure luck? The answer is $P (a) \cdot P (b)$ — the product of two independent chances. The actual chance of ab is $P (ab)$ . The ratio compares reality to luck:

$P (ab) > P (a) P (b)$ → ratio $> 1$ → $lo g$ is positive → they stick together more than chance → glue them! (e.g. play+##ing)
$P (ab) = P (a) P (b)$ → ratio $= 1$ → $lo g = 0$ → they are independent → gluing buys nothing.
$P (ab) < P (a) P (b)$ → ratio $< 1$ → $lo g$ is negative → they avoid each other → gluing would hurt the score.

PICTURE. Three regimes of the log-ratio along a number line, with the zero point marking "pure chance."

Step 8 — Edge cases, degenerate inputs, ties, and when to STOP

WHAT. Real corpora throw ugly inputs. Let us check every corner of the formula.

Case A — the pair never appears: $count (ab) = 0$ . Then $Δ L = 0 \times (anything finite) = 0$ . No occurrences to improve, so no payoff. Correct — such a merge is never chosen.

Case B — perfect chance overlap: $P (ab) = P (a) P (b)$ . Log-ratio $= lo g 1 = 0$ , so $Δ L = 0$ regardless of count. The tiles are independent; fusing them neither helps nor hurts. WordPiece skips it in favour of a truly-bonded pair.

Case C — anti-correlated pair: $P (ab) < P (a) P (b)$ . Log-ratio is negative, so $Δ L < 0$ . Merging would lower the corpus likelihood. WordPiece never picks a negative-score merge — it would make the vocabulary worse.

Case D — a piece with probability zero: $P (a) = 0$ or $P (b) = 0$ . Here we must be careful about which zero. If a base piece truly never occurred, then it also never occurred next to its partner, so $count (ab) = 0$ too. The score is then $0 \cdot lo g \frac{0}{0}$ — an indeterminate $0/0$ inside the log, not a clean $\pm \infty$ . WordPiece sidesteps the whole mess by never scoring a pair that does not occur: the merge-candidate list is built only from pairs actually seen (Case A gives them zero payoff anyway). And this cannot arise for the base pieces themselves, because at initialization the vocabulary contains every single character (see the Out-of-Vocabulary Problem fix), so every base piece has appeared at least once and has $P > 0$ . This is exactly why WordPiece seeds the vocab with all characters before any merging.

Case E — word boundaries. WordPiece never glues across whitespace. A candidate ab where a ends one word and b starts the next is simply not a valid pair. Non-initial pieces wear the ## badge (##ing) so the model knows they attach to the left. This is a rule imposed on top of the score, not something the score decides.

Case F — a tie: two pairs share the exact same top $Δ L$ . Because scores are real numbers built from integer counts, exact ties do happen (especially early, on tiny corpora). The rule must be deterministic so that training is reproducible — two runs on the same corpus must build the same vocabulary. In practice WordPiece breaks ties by a fixed convention: pick the candidate that comes first in a stable ordering (e.g. lexicographically smallest pair string, or first-seen order). Which rule matters less than that it is fixed; a random tie-break would make the vocabulary non-reproducible.

Case G — no positive-payoff merge left: the stopping criterion. Two things can end training. (1) Target size reached: the vocabulary hits its budget (e.g. 30K tiles) — we stop even if good merges remain. (2) No merge helps: if every candidate pair scores $Δ L \leq 0$ (all pairs are at-chance or anti-correlated, Cases B and C), there is no merge that raises the likelihood, so WordPiece stops early. In practice the size budget almost always triggers first, but the " $max_{a, b} Δ L (a, b) \leq 0$ " condition is the honest mathematical stop: keep merging only while a strictly positive payoff exists.

PICTURE. A dial of $Δ L$ across the cases: zero for A and B, negative for C, indeterminate/forbidden for D and E, a tie shown as two equal bars for F, and a hard stop at G.

The one-picture summary

The whole derivation on one canvas: independence (Step 1) $\to$ log turns products into sums (Step 2) $\to$ ask "glue or not?" (Step 3) $\to$ score before (Step 4) minus score after (Step 5) $\to$ the log-ratio $\times$ count survives (Step 6) $\to$ that ratio is surprise, i.e. PMI (Step 7) $\to$ every edge case behaves, ties break deterministically, and training stops when no positive merge is left (Step 8).

Recall Feynman retelling — say it like you would to a friend

We pretend a sentence is made by pulling word-tiles out of a bag one at a time, blindly. A tile's chance of being pulled is its slice of a pie — and that slice is just its count divided by the total number of tiles pulled, so common tiles have big slices. Crucially, a brand-new fused tile gets its slice by the very same rule: its pair-count divided by the same total. The "goodness" of our tile-bag is the chance it would produce our actual text; because multiplying tiny chances is hopeless, we take logarithms (natural log — the base only rescales, it never changes who wins) and add them instead. Now WordPiece asks, over and over: "If I fuse two neighbouring tiles into one new tile, does the text become more likely?" To find out, it compares the score with them separate versus fused. Almost everything cancels; what remains is how often the pair shows up times how surprised we are to see them together. Surprise means: do they appear side-by-side more than pure luck ( $P (a) \times P (b)$ ) would predict? If yes (positive surprise), fuse them; if they only meet by luck (zero surprise) or avoid each other (negative), leave them apart. If two pairs tie for best, a fixed rule (not a coin flip) breaks the tie so the vocabulary is reproducible. After we glue a pair, that new tile steals occurrences, so we recount everything and refresh all the slices before the next round — that recounting loop is the EM idea. We keep going until either the vocabulary is full or no fusion helps anymore. That surprise number is called PMI, and it is the whole reason WordPiece beats plain BPE: BPE glues the most common pair, WordPiece glues the most bonded pair.

Recall

WordPiece merge score formula ::: $Δ L (a, b) = count (ab) \cdot lo g \frac{P ( ab )}{P ( a ) P ( b )}$ How $P (x)$ is computed from raw counts ::: $P (x) = count (x) / N$ , where $N$ is the total number of tokens in the corpus How the merged token's probability $P (ab)$ is defined ::: by the exact same rule, $P (ab) = count (ab) / N$ — the pair's corpus count over the total Which logarithm base does WordPiece use ::: any base works since it only ranks; natural log (nats) by convention, base 2 gives PMI in bits Why take logs of the likelihood ::: to turn a product of many tiny probabilities into a sum, avoiding underflow — using $lo g (ab) = lo g a + lo g b$ What the log-ratio equals when $a, b$ are independent ::: exactly 0, since $P (ab) = P (a) P (b)$ makes the ratio 1 Why is Case D ( $P (a) = 0$ or $P (b) = 0$ ) not a real division-by-zero ::: if a piece never occurred then $count (ab) = 0$ too, giving indeterminate $0/0$ ; WordPiece only scores pairs that actually occur, so it never arises How are ties in $Δ L$ broken ::: by a fixed deterministic rule (e.g. lexicographic / first-seen order), never randomly, so the vocabulary is reproducible What happens to $P (a), P (b), P (ab)$ after each accepted merge ::: all counts change, so the whole unigram distribution is renormalized (EM re-estimation) before the next round When does WordPiece stop merging ::: when the vocabulary hits its target size, or when no candidate pair has a strictly positive $Δ L$ The difference between BPE and WordPiece in one line ::: BPE merges the highest-count pair; WordPiece merges the highest $Δ L$ (count times PMI) pair What guarantees $P (a) > 0$ and $P (b) > 0$ so the ratio never divides by zero ::: the vocabulary is seeded with every character before merging