WordPiece and SentencePiece

Overview

WordPiece and SentencePiece are subword tokenization algorithms that break words into smaller pieces to balance vocabulary size and coverage. They solve the out-of-vocabulary (OOV) problem while keeping the vocabulary tractable.

Why subword? Character-level is too granular (long sequences), word-level has infinite vocabulary. Subword is the Goldilocks zone.

[!intuition] Core Intuition

Imagine you're learning English and encounter "unbreakable". If you know "un-", "break", and "-able", you can guess the meaning even if you've never seen the full word. Subword tokenization teaches the model this compositional skill.

The key insight: Frequent words stay whole ("the", "and"), rare words get split into meaningful pieces ("playing" → "play" + "##ing"). The model learns morphology implicitly.

[!definition] WordPiece (Google/BERT)

WordPiece is a likelihood-based (PMI-weighted) subword algorithm developed for BERT. Crucially, it is not raw-frequency based—it chooses merges by which pair most increases the corpus likelihood under a unigram model.

Algorithm (Training):

1. Initialize vocabulary with all characters + special tokens ([UNK], [CLS], [SEP], [MASK])
2. Repeat until vocabulary reaches target size (e.g., 30K):
   • For every pair of consecutive tokens in the corpus, calculate the likelihood increase if we merge them
   • The pair that increases the likelihood most becomes a new token
   • Add it to vocabulary with ## prefix if it's not word-initial

Why likelihood, not frequency? We want the tokenization that makes the training corpus most probable under a unigram language model (each token independent, no context). Under a unigram model the corpus log-likelihood is:

$\mathcal{L} = \sum_{i=1}^{N} \log P(w_i)$

Note there is no context term $P(w_i \mid \text{context})$—each token contributes $\log P(w_i)$ independently. Merging a pair $(a, b) \to ab$ changes $\mathcal{L}$, and WordPiece picks the merge with the largest gain (which turns out to be PMI-weighted, see below).

Contrast with BPE: BPE merges the pair with the highest raw count; WordPiece merges the pair that maximizes likelihood gain. That gain rewards pairs that co-occur more than chance, not merely often.

Tokenization (Inference):

• Greedy longest-match: Start from the beginning of each word, take the longest subword in vocabulary, repeat
• Use ## to mark non-initial pieces: "playing" → ["play", "##ing"]

Key properties:

• Always starts with words separated by whitespace
• Never crosses word boundaries
• Requires pre-tokenized input (space-separated)

[!definition] SentencePiece (Google/T5)

SentencePiece is a language-agnostic, unsupervised text tokenizer that treats the input as a raw stream.

Why "language-agnostic"? Many languages (Chinese, Japanese, Thai) don't use spaces. SentencePiece works directly on raw text, treating whitespace as a special token ▁ (U+2581).

Algorithm choices:

1. BPE mode (Byte-Pair Encoding): Merge most frequent pairs iteratively
2. Unigram mode (default): Start with large vocabulary, prune tokens that minimize likelihood loss

Important: SentencePiece unigram does not use the ## prefix. All tokens are plain substrings; word boundaries are recovered purely from the ▁ marker.

Unigram derivation from first principles:

Assume each token $x_i$ is sampled independently (unigram assumption):

$P(\text{sentence}) = \prod_{i=1}^{n} P(x_i)$

Log-likelihood:

$\mathcal{L} = \sum_{i=1}^{n} \log P(x_i)$

Training objective: Find vocabulary $V$ and token probabilities $P(x)$ that maximize $\mathcal{L}$ across the corpus.

EM algorithm:

1. E-step: For each word, enumerate all possible segmentations, compute each segmentation's probability using current $P(x)$, and derive expected (soft) counts of each token via forward-backward
2. M-step: Update $P(x)$ = (expected count of $x$) / (total expected counts)
3. Prune: Remove tokens that hurt $\mathcal{L}$ least, repeat until target vocabulary size

Why this works: Frequent subwords get high $P(x)$, so they're preferred in segmentations. Rare subwords get pruned.

Key properties:

• Reversible: tokens → original text exactly (because ▁ encodes spaces)
• No pre-tokenization needed
• Handles any language

[!formula] Likelihood-Based Merging (WordPiece)

For a merge candidate $(a, b)$:

$\Delta \mathcal{L}(a, b) = \text{count}(ab) \cdot \log \frac{P(ab)}{P(a) \cdot P(b)}$

Derivation:

Before merge: segments $(a, b)$ appear as two tokens $\mathcal{L}_{\text{before}} = \text{count}(ab) \cdot [\log P(a) + \log P(b)]$

After merge: they appear as one token $ab$ $\mathcal{L}_{\text{after}} = \text{count}(ab) \cdot \log P(ab)$

Likelihood gain: $\Delta \mathcal{L} = \mathcal{L}_{\text{after}} - \mathcal{L}_{\text{before}} = \text{count}(ab) \cdot \log \frac{P(ab)}{P(a) \cdot P(b)}$

This is the pointwise mutual information (PMI) weighted by frequency. This is exactly why WordPiece is not frequency-based: a pair can be frequent yet have low PMI (if $a$ and $b$ are independently common), so it won't be merged first.

Why maximize this? High PMI means $a$ and $b$ co-occur more than chance → they form a meaningful unit.

[!example] Worked Example 1: WordPiece Tokenization

Input: "unhappiness"

Vocabulary: ["un", "##happ", "##i", "##ness", "happiness"]

Step-by-step greedy longest-match:

1. Start at position 0
2. Try "unhappiness" → not in vocab
3. Try "unhappine" → not in vocab
4. Try "unhapi" → not in vocab
5. Try "unhapp" → not in vocab
6. Try "unhap" → not in vocab
7. Try "unha" → not in vocab
8. Try "unh" → not in vocab
9. Try "un" → found! ✓
10. Move to position 2, now process "happiness"
11. Try "happiness" → found! ✓

Output: ["un", "happiness"]

Why this step? Greedy longest-match ensures we use the largest chunks possible, reducing sequence length.

[!example] Worked Example 2: SentencePiece with Spaces

Input: "Hello world"

SentencePiece vocabulary: ["▁", "▁H", "ello", "▁w", "orld"]

Tokenization:

• "Hello world" → treat space as ▁ → "▁Hello▁world"
• Segment: ["▁H", "ello", "▁w", "orld"]

Detokenization:

• ["▁H", "ello", "▁w", "orld"] → "▁Hello▁world" → replace ▁ with space → "Hello world"

Why ▁? It makes tokenization reversible. You can always reconstruct the original text exactly, including leading/trailing spaces.

[!example] Worked Example 3: SentencePiece Unigram E-step

Corpus: a single word "dogs" observed with count 1 (kept small for clarity).

Vocabulary (plain substrings, NO ## prefix): ["d", "o", "g", "s", "do", "dog", "gs", "dogs"]

Current token probabilities (from a previous M-step):

E-step — enumerate segmentations of "dogs" and score each:

1. ["dog", "s"] → $0.40 \times 0.20 = 0.0800$ Why this step? Product of independent token probs (unigram assumption).
2. ["do", "g", "s"] → $0.10 \times 0.10 \times 0.20 = 0.0020$
3. ["d", "o", "gs"] → $0.05 \times 0.05 \times 0.05 = 0.000125$
4. ["dogs"] → $0.05$
5. ["d", "o", "g", "s"] → $0.05 \times 0.05 \times 0.10 \times 0.20 = 0.00005$

Normalize (sum $Z = 0.0800 + 0.0020 + 0.000125 + 0.05 + 0.00005 = 0.132275$):

Expected (soft) counts of each token = sum of posterior weights of segmentations that contain it:

• $E[\text{dog}] = 0.605$
• $E[\text{s}] = 0.605 + 0.00038 \approx 0.605$ (from seg 1 and 5)
• $E[\text{dogs}] = 0.378$
• $E[\text{do}], E[\text{g}], E[\text{gs}], E[\text{d}], E[\text{o}]$ ≈ tiny

Why forward-backward? For long words the number of segmentations is exponential; forward-backward computes these expected counts in linear time without enumerating them all. The M-step then re-normalizes these expected counts into new $P(x)$, and low-count tokens (like do, gs) get pruned in later rounds.

Key takeaway: This is soft, probabilistic assignment across all segmentations — very different from WordPiece's hard greedy merge, and it uses plain substrings, not ##-prefixed pieces.

[!mistake] Common Mistake 1: Confusing BPE and WordPiece

Wrong idea: "WordPiece and BPE are the same because both merge frequent pairs."

Why it feels right: Both are greedy merge algorithms on pairs.

The fix:

• BPE merges the pair with highest frequency (simple count)
• WordPiece merges the pair with highest likelihood increase (PMI weighted)

Example: Suppose ("e", "r") appears 100 times, ("er", "s") appears 50 times. BPE merges ("e", "r") first. But if ("er", "s") has very high PMI (they're almost always together), WordPiece might merge ("er", "s") first because it increases likelihood more.

Formula difference:

BPE: $\arg\max_{(a,b)} \text{count}(a, b)$

WordPiece: $\arg\max_{(a,b)} \text{count}(ab) \cdot \log \frac{P(ab)}{P(a) \cdot P(b)}$

[!mistake] Common Mistake 2: Thinking SentencePiece Can't Handle Spaces

Wrong idea: "SentencePiece is for languages without spaces, so it breaks on English."

Why it feels right: The documentation emphasizes "language-agnostic" and Chinese examples.

The fix: SentencePiece handles spaces better than WordPiece because it encodes them explicitly as ▁. You can perfectly reconstruct the original text, including multiple spaces or leading spaces.

Example:

• Input: " Hello world " (note multiple spaces)
• WordPiece: Pre-tokenization normalizes spaces → information loss
• SentencePiece: encodes each space as its own ▁, fully reversible

[!mistake] Common Mistake 3: Mixing ## into SentencePiece

Wrong idea: "SentencePiece unigram tokens use ## for non-initial pieces, like WordPiece."

Why it feels right: Both are subword tokenizers from Google, so people assume the notation is shared.

The fix: ## is a WordPiece-only convention. SentencePiece tokens are plain substrings; word/space information is carried entirely by the ▁ marker. So a SentencePiece vocabulary looks like ["▁the", "▁dog", "s"], never ["the", "##s"].

[!recall]- Explain to a 12-year-old

Imagine you're making a dictionary for texting. You want it to be small (so it fits on your phone), but you also want to be able to write any word.

WordPiece is like: "Let's keep whole words for common stuff like 'the' and 'cat'. But if someone texts 'supercalifragilisticexpialidocious', we'll break it into pieces we've seen before: 'super', 'cali', 'fragi', etc."

The trick: We don't just pick pieces that show up a lot — we pick pieces that belong together. If "play" and "ing" appear next to each other much more than you'd expect by luck, we glue them into "playing". (This "more than luck" idea is called PMI.)

SentencePiece is even smarter: instead of breaking words first, it treats spaces as just another character (we write it as ▁). This works for Chinese (no spaces) and English (lots of spaces) the same way. And you can always go backwards — turn the pieces back into the exact original message.

[!mnemonic] Memory Hook

WordPiece: Word-boundary aware (never crosses spaces, uses ##) SentencePiece: Sentence-level raw (treats spaces as ▁, no ##, no pre-tokenization)

PMI = "Pair Must Integrate" → WordPiece merges pairs that belong together (high mutual information, NOT just high frequency)

Unigram = "You Need Independence Guess Repeatedly And Modify" → EM algorithm iterates on independent token probabilities

Connections

• Byte-Pair Encoding (BPE): WordPiece uses likelihood/PMI instead of raw frequency
• Tokenization Fundamentals: Subword as the middle ground between character and word
• BERT Architecture: Uses WordPiece with 30K vocabulary
• T5 and mT5: Use SentencePiece unigram for 100+ languages
• Out-of-Vocabulary Problem: Subword tokenization eliminates OOV
• Morphology and Compositionality: Subwords capture morphemes implicitly
• Pointwise Mutual Information: The math behind WordPiece merging
• Expectation Maximization: Powers SentencePiece unigram training

Flashcards

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)