WordPiece, Unigram and SentencePiece

Key idea

WordPiece: merge by count(ab) ÷ (count(a) × count(b)), encode longest-match-first with ## pieces. Unigram: start big, prune; encode by the most probable path through a lattice. SentencePiece: treat text as a raw stream with ▁ for spaces

Real world

Reading a web address with no spaces, like “expertsexchange”. You could read it as “expert sex change” or “experts exchange”. You pick the split that makes the most likely sense.

In an LLM

BERT reads “hedgehogs” as “hedge”, “##hog”, “##s”. T5 has 61 ways to split “sunflowers” into pieces it knows, and picks “▁sunflower” + “s” because that has the highest probability.

Two questions

Every subword tokenizer answers two questions:

1. Training: which pieces go into the vocabulary?
2. Encoding: given the vocabulary, how is a new word cut into pieces?

BPE answers both with merges: merge the most frequent pair, and later replay the merges in order. The two other families in wide use answer them differently.

Here are the three families side by side, before the details. Come back to this table after each section.

WordPiece

WordPiece was invented at Google for Japanese and Korean voice search (Schuster and Nakajima, 2012), used in Google’s translation system in 2016, and made famous by BERT in 2018.

Before the vocabulary: normalising

BERT does not feed raw text to WordPiece. First it cleans it: the uncased model turns everything to lower case, strips accents (“café” becomes “cafe”), puts spaces around punctuation and around every Chinese character, and splits on whitespace. Only then does WordPiece run on each word. That is why the widget below lower-cases whatever you type, and why BERT cannot tell “Apple” from “apple”.

Encoding: longest match first

WordPiece does not store merges. It stores only the vocabulary, and splits a word greedily: from the start of the word, take the longest string that is in the vocabulary, then continue from where it ended. Pieces that continue a word are written with a “##” prefix, and live in the vocabulary as separate entries: “ing” at the start of a word and “##ing” inside one are different tokens. If at some point no piece matches at all, the whole word becomes [UNK].

Here is BERT’s real vocabulary at work. Watch it try “unaffable”, “unaffabl”, “unaffab”… until something matches:

BERT’s own documentation uses “unaffable” → “un”, “##aff”, “##able” as its example. The real uncased vocabulary gives “una”, “##ffa”, “##ble”: greedy longest-match grabs “una” because it is a longer match than “un”, even though “un” is the better linguistic choice. Greedy is fast, but not always sensible.

Training: likelihood, not counts

WordPiece builds its vocabulary like BPE, by merging pairs, but chooses the pair that most increases the likelihood of the training data rather than the most frequent one. In practice that is computed as a score:

A pair scores high when its two parts are rarely seen apart. Compare the two rules on the same corpus:

On the “low, newest, widest” corpus, BPE merges “e” + “s” first (9 times). WordPiece merges “i” + “d” first: it occurs only 3 times, but “i” and “d” never appear anywhere else, so the score is $3 / (3 \times 3) = 0.33$, the highest. WordPiece prefers pieces that “belong together” over pieces that are merely common.

Unigram

The Unigram language model tokenizer (Kudo, 2018) turns the problem around. Instead of building up from characters by merging, it starts with a huge vocabulary and prunes it. And instead of fixed rules for splitting, it treats segmentation as a probability question.

Every piece has a probability

Each piece $x$ in the vocabulary has a probability $p(x)$. A segmentation of a word into pieces $x_1, \dots, x_k$ has probability

and the tokenizer outputs the most probable segmentation. Probabilities multiply, so in practice we add their logarithms; every piece below shows its log-probability, a negative number where closer to zero means more likely.

A word can usually be split in hundreds of ways. Drawing every piece that matches somewhere in the word gives a lattice: a segmentation is any left-to-right path through it. The best path is found with the Viterbi algorithm algorithm: go left to right, and at each position remember only the best way to get there. Then trace back from the end.

Step through “unbelievable”. At each position Viterbi compares every piece that ends there (in amber) and keeps the one with the best total. At the end, the whole-word piece “▁unbelievable” wins, far ahead of “▁un” + “believable”: it carries 99.9% of the probability of all 170 possible segmentations. Try “Wonderland”: T5 has “▁Wonder” but no “land” piece that fits, so it ends with an odd “l” + “and”.

Training: start big, prune

1. Start with a very large vocabulary: every character plus the most frequent substrings of the training text (hundreds of thousands).
2. Estimate each piece’s probability from how often it appears in the best segmentations of the corpus (the EM algorithm: segment, re-count, repeat).
3. For each piece, measure how much the corpus likelihood would drop if it were removed.
4. Remove the least useful 20% or so (never single characters, so every word can still be spelled).
5. Repeat from step 2 until the vocabulary is the target size.

Sampling: subword regularisation

Because Unigram gives every segmentation a probability, it can do something BPE and WordPiece cannot: sample. Press “Sample a segmentation” above a few times. For “unbelievable” with α = 0.1, the best split comes up only 21% of the time; with α = 0.5, 97% of the time. During training, Subword regularisation feeds the model a different plausible split of the same word each time. The model then cannot rely on one exact segmentation, which makes it more robust to typos and unusual words. (BPE later got a similar trick, BPE-dropout, which randomly skips merges.)

SentencePiece

SentencePiece (Kudo and Richardson, 2018) is a library, not a third algorithm. It trains either a BPE or a Unigram model, and its main idea is to treat the input as a raw stream of characters, spaces included:

• A space is replaced by the visible character ▁ (U+2581) and treated like any other character. Pieces such as “▁the” mean “the at the start of a word”. Decoding is just joining the pieces and turning ▁ back into spaces, so tokenizing never loses information.
• No language-specific word splitting is needed. That matters for Chinese, Japanese and Thai, which do not put spaces between words.
• Options control the details: what share of characters to cover (rare characters left out become unknown, or with byte fallback become bytes, see bytes and Unicode), whether to split numbers into single digits, and whether to add a ▁ at the very start of the text.

T5 and ALBERT use SentencePiece Unigram. Llama 1 and 2, Mistral 7B and Gemma use SentencePiece BPE with byte fallback.

One word, three algorithms

Now run one word through all three. Same word, three real tokenizers. The cut can differ because the algorithms differ (merge order, longest match, best path) and because the vocabularies differ (50,257, 30,522 and 32,100 pieces, learned from different text).

Try “unhappiness” and “Wonderland”. For “unhappiness”, BERT gives “un”, “##ha”, “##pp”, “##iness” and T5 gives “▁un”, “h”, “app”, “iness”: neither finds “happi” or “happy”. Pieces come from counting text, and counting does not know about prefixes and suffixes. “sunflowers” shows how much the answers can differ: GPT-2 cuts “ sun”, “fl”, “owers”, BERT cuts “sun”, “##flower”, “##s”, and T5 cuts “▁sunflower”, “s”. None of the three guarantees pieces a linguist would recognise.

Side by side

Six real tokenizers on the same text, printed exactly as each library stores its pieces:

Which model uses which

The pattern: WordPiece and Unigram were popular for the encoder models of 2018 to 2020. Generative LLMs since then have almost all used BPE, either byte-level or SentencePiece with byte fallback, and the vocabularies keep growing; see vocabulary size. The tokens the table does not count, such as end-of-text and chat markers, are on special tokens.

def wordpiece(word, vocab, unk="[UNK]"):
    pieces, start = [], 0
    while start < len(word):
        end = len(word)
        while end > start:
            sub = word[start:end] if start == 0 else "##" + word[start:end]
            if sub in vocab:
                break
            end -= 1
        if end == start:
            return [unk]                 # no piece fits: the whole word is unknown
        pieces.append(sub)
        start = end
    return pieces