Byte pair encoding has a curious property. It never says what it is trying to achieve. Each merge is the most frequent pair at that moment, and the final vocabulary is whatever that greedy history produced. Ask "is un + believ + able a better split than unbe + liev + able?" and BPE has no answer except "that is the order the merges came in".

Two other families of tokenizers start from an objective instead. WordPiece, the tokenizer of BERT, chooses merges that most increase the likelihood of the training data. The Unigram language model of Kudo (2018), used by T5 and many multilingual models, goes further. It defines a probability for every possible segmentation of a word, picks the most probable one with dynamic programming, and learns its vocabulary by expectation maximization, starting large and pruning down. Along the way it gets something BPE cannot do natively, a principled way to sample different segmentations of the same word, which turns out to be a useful regularizer. This section derives both, then looks at SentencePiece, the library that packages them and changed how tokenizers treat spaces.

WordPiece

WordPiece was introduced by Schuster and Nakajima (2012) for Japanese and Korean voice search, and became famous as BERT's tokenizer (Devlin et al. 2019, with a 30,000-token vocabulary). It has two halves that work quite differently, so we treat them separately.

Training by likelihood

Like BPE, WordPiece training starts from characters and merges pairs bottom up. Words are split with a continuation marker, so "tea" starts as t ##e ##a. The ## marks a piece that continues a word rather than starting one, so word-initial e and word-internal ##e are different symbols.

The difference is the choice of merge. Schuster and Nakajima pick the new unit that most increases the likelihood of the training data under a language model over the current units. Let's work out what that means for the simplest such model, a unigram model in which each token is drawn independently with probability $p(v) = c(v)/T$, where $c(v)$ is the count of symbol $v$ and $T = \sum_v c(v)$ is the total number of tokens. The maximized log-likelihood of the corpus is

Now merge $a$ and $b$, which occur next to each other $c(a,b)$ times. Each occurrence turns two tokens into one, so $c(a)$ and $c(b)$ each drop by $c(a,b)$, a new symbol appears with count $c(a,b)$, and $T$ drops by $c(a,b)$. The change in log-likelihood is exactly

In plain words, the merge helps when the new symbol is frequent and its parts were mostly used together anyway (so removing those uses costs little), and fewer tokens overall also helps. The derivation below shows that when the pair is rare compared with its parts,

The bracket is the pointwise mutual information of the pair (recall PMI from §1.4) minus one. So the likelihood gain is roughly count times PMI. BPE ranks pairs by count alone. Likelihood-based WordPiece also cares whether the two parts actually belong together.

Google never released its WordPiece training code. The widely used Hugging Face implementation (described in their course as a best guess from the published literature) ranks pairs by a simpler score,

which is $e^{\text{PMI}}/T$, the PMI part without the count. Let's compare all of these on the tea corpus from §2.2.

All three criteria disagree. BPE would merge ##e ##a or ##a ##t (count 12, the most frequent pairs). The exact likelihood gain prefers t ##e, because word-initial t occurs 8 times and always before ##e, so merging them costs nothing. Hugging Face's score ties t ##e with s ##e and ranks the frequent ##e ##a lower, because ##e and ##a also occur apart. These differences compound over thousands of merges into genuinely different vocabularies.

def wordpiece_best_pair(words):
    raise NotImplementedError

Encoding by greedy longest match

At inference time WordPiece does not replay merges at all. It keeps only the final vocabulary and segments each word greedily from the left. Take the longest prefix of the word that is in the vocabulary, emit it, and repeat on the rest, where every piece after the first must carry the ## prefix. If at some point no prefix of the remainder is in the vocabulary, the whole word becomes [UNK]. BERT also maps any word longer than 100 characters to [UNK].

This is called MaxMatch, and it is fast and simple. It is also greedy in the bad sense. Suppose the vocabulary contains abc, a, and ##bcde, and the word is "abcde". Greedy takes the longest prefix abc, and then no piece matches de or ##de, so the word becomes [UNK], even though a + ##bcde was available. Real vocabularies contain every single character in both forms, which makes this rare, but the greedy split is still not the most likely split, and it is sensitive to vocabulary details. Here is BERT's actual uncased tokenizer on a few words, from Hugging Face's bert-base-uncased.

The last two rows show that BERT's tokenizer is lossy. It lowercases, strips accents, and has no entry for emoji. Section 2.5 discusses this normalization. Making MaxMatch linear in the word length takes a trie with failure links, much like the Aho-Corasick string-matching algorithm. Song et al. (2021) describe this LinMaxMatch algorithm, which is what fast WordPiece implementations use.

def wordpiece_encode(word, vocab, unk="[UNK]", max_chars=100):
    raise NotImplementedError

The Unigram language model

Now the probabilistic view. Fix a vocabulary $\mathcal{V}$ of pieces, each with a probability $p(v)$, where $\sum_{v \in \mathcal{V}} p(v) = 1$. A segmentation of a string $X$ is a sequence of pieces $x = (x_1, \dots, x_M)$ whose concatenation is $X$, and $\mathcal{S}(X)$ is the set of all segmentations of $X$ into pieces of $\mathcal{V}$. Kudo (2018) models each piece as drawn independently, so

In plain words, a segmentation's probability is the product of its pieces' probabilities, and a string's probability adds up all the ways of cutting it. Because every piece costs a factor $p(x_i) < 1$, the model naturally prefers segmentations with few, common pieces.

Tokenizing means choosing the most probable segmentation,

A word of length $n$ has up to $2^{n-1}$ segmentations, so we cannot list them. But the structure is a shortest-path problem, and it yields to dynamic programming.

Viterbi segmentation

Draw the string's positions $0, 1, \dots, n$ as nodes, and for every vocabulary piece that matches $X[j:i]$, draw an edge from node $j$ to node $i$ with weight $\log p(X[j:i])$. Every path from node 0 to node $n$ is a segmentation, and its total weight is the segmentation's log-probability. This graph is called the lattice. Explore one below.

Let $\delta_i$ be the best log-probability of any segmentation of the prefix $X[0:i]$. The last piece of that segmentation is some $X[j:i]$, and what comes before it must itself be the best segmentation of $X[0:j]$ (if it weren't, swapping in the better one would improve the whole). That optimal-substructure argument gives the recursion

In plain words, the best way to reach position $i$ is the best way to reach some earlier position $j$, plus one piece that jumps from $j$ to $i$. Store the best $j$ for every $i$ (a backpointer) and walk back from $n$ to read off the pieces. With pieces at most $\ell_{\max}$ characters long, each $\delta_i$ looks at $\ell_{\max}$ candidates, so Viterbi costs $O(n\,\ell_{\max})$ dictionary lookups.

import math

def viterbi_segment(text, logp):
    raise NotImplementedError

The marginal likelihood, by the forward algorithm

Replace the max in the Viterbi recursion with a sum and you get the probability of the string, summed over every segmentation. Working in log space, with $\operatorname{logsumexp}(a, b) = \log(e^a + e^b)$ (recall the stable version from §0.4),

In plain words, $\alpha_i$ is the log of the total probability of all ways to produce the first $i$ characters. The same recursion run from the right end gives $\beta_i$, the log of the total probability of all ways to produce $X[i:n]$, with $\beta_n = 0$. Together they tell us how likely each lattice edge is. The posterior probability that a segmentation uses the piece $X[j:i]$ exactly at that position is

In plain words, the paths through an edge are any path into node $j$, then the edge, then any path out of node $i$, and dividing by all paths gives the edge's share. This is the forward-backward algorithm you may know from hidden Markov models, applied to a segmentation lattice. The widget above shows these edge posteriors as the opacity of each arc.

Learning the probabilities with EM

Given a corpus of strings $X^{(1)}, X^{(2)}, \dots$ with counts $n_s$ and a fixed vocabulary, we want the piece probabilities that maximize the marginal likelihood

If we knew the true segmentations, this would be easy. The best $p(v)$ would be the count of $v$ divided by the total count of pieces, exactly like estimating a die's probabilities from rolls. But the segmentation is hidden. This is the textbook setting for expectation maximization. Guess $p$, compute the expected counts of every piece under the current model, re-estimate $p$ from those counts, and repeat.

In plain words, the E-step uses forward-backward to work out how often each piece is used, on average over all segmentations weighted by how likely they are, and the M-step sets each probability to its share of those expected uses. Each EM iteration never decreases $\mathcal{J}$.

import math

def unigram_em_step(word_counts, logp):
    raise NotImplementedError

Learning the vocabulary, top down

EM fits probabilities for a fixed vocabulary. The vocabulary itself is chosen by working backwards from a deliberately oversized one. Kudo's algorithm has three steps.

1. Seed. Start with all characters plus a large set of frequent substrings of the corpus (Kudo enumerates them with a suffix array, and SentencePiece keeps one million seed pieces by default). Substrings never cross word boundaries.
2. Fit. Run a few iterations of EM.
3. Prune. For every piece $v$, estimate its loss, how much the likelihood would drop if $v$ were removed and every string had to be segmented without it. Keep the pieces with the largest losses, the top 80% in Kudo's paper (SentencePiece's default shrinking_factor keeps 75%), but always keep single characters so that every string remains segmentable. Return to step 2 until the vocabulary reaches the target size.

Computing each loss exactly would mean re-running EM once per piece. SentencePiece approximates it. For each piece, it finds the best alternative segmentation of that piece using the other pieces (the second-best Viterbi path of the piece itself), counts how often the piece occurs in the Viterbi segmentations of the corpus, and estimates the loss as that frequency times the drop in log-probability from replacing the piece with its alternative. The cell below implements this whole loop on a few lines of text, using the same Viterbi and forward-backward recursions you just wrote.

Now the training loop itself, from seed vocabulary to a final size of 60 pieces.

The marginal likelihood does not fall as the vocabulary shrinks from 167 pieces to 60. It even rises, from $-441.5$ to $-426.7$ nats. The pruned pieces were ones the model barely used, and each round of EM keeps improving the probabilities of the pieces that remain. Two iterations per round are far from convergence. Run EM to convergence on all 167 seed pieces and the likelihood reaches about $-425.5$, so the rise comes from EM, and pruning away almost two thirds of the vocabulary costs only about one nat. The final vocabulary contains whole words (the, light, keeper, kept) and reusable pieces such as ing and house. Words that never occurred are built from the high-probability pieces they contain, so "lightkeeper" becomes light + keeper and "starlight" ends in light (with st + ar in front, since star never made it into this tiny vocabulary). Notice that the training direction is the opposite of BPE's. BPE grows a vocabulary from characters upward. Unigram shrinks one from an oversized seed downward, and it judges every piece by its effect on a global objective.

Sampling segmentations, subword regularization

The Unigram model gives a full distribution over segmentations, not just a best one. Kudo's (2018) insight was that training a model on sampled segmentations, a different one each time a sentence is seen, works like data augmentation. The model sees "lighthouse" as light house most of the time, but occasionally as li ght house or light ho use, so it learns how the pieces compose and becomes more robust to segmentation noise and misspellings. Kudo calls this subword regularization and reports consistent gains in machine translation, especially for low-resource and out-of-domain settings.

Kudo samples a segmentation with probability proportional to a sharpened or flattened version of the model,

In plain words, $\lambda$ is an inverse temperature. Large $\lambda$ nearly always returns the Viterbi segmentation, and small $\lambda$ makes all segmentations close to equally likely. (Kudo writes this exponent as α, and SentencePiece's API calls it alpha. We write $\lambda$ here because α is our forward variable.) Sampling exactly from all segmentations uses the forward-filtering, backward-sampling algorithm. Run the forward recursion with $\lambda \log p$ in place of $\log p$, then walk backwards from node $n$, choosing each previous node $j$ with probability proportional to $\exp(\alpha_j + \lambda\log p(X[j:i]))$. Move the sharpness slider in the lattice widget above and sample a few times to see the effect.

BPE-dropout

BPE has no probabilities to sample from, so Provilkov, Emelianenko and Voita (2020) proposed a simpler trick that gives the same effect. During encoding, at every step, each possible merge is skipped with probability $p_{\text{drop}}$, and the highest-priority surviving merge is applied. If every possible merge is dropped, encoding stops. With $p_{\text{drop}} = 0$ this is ordinary BPE, and with $p_{\text{drop}} = 1$ it returns characters. They used $p_{\text{drop}} = 0.1$ during training and ordinary BPE ($p_{\text{drop}} = 0$) at test time, and found it matched or beat subword regularization while being trivially compatible with existing BPE tokenizers.

def bpe_dropout_encode(word, merges, p, rng):
    raise NotImplementedError

SentencePiece, and what to do about spaces

Every tokenizer so far has assumed that something else splits text into words first, usually on spaces. That assumption fails for Chinese, Japanese, and Thai, which are written without spaces, and it makes detokenization ambiguous. If "Hello world." is pre-tokenized into Hello, world, ., how does the decoder know there was a space before "world" but not before the period? Rule-based detokenizers for each language were a constant source of bugs.

Kudo and Richardson (2018) fixed this with SentencePiece, a library that treats the input as a raw stream of characters in which the space is just another symbol. It replaces each space with the visible meta symbol ▁ (U+2581) and then runs BPE or Unigram directly on the result, so pieces like ▁world carry their own leading space. Decoding is trivially lossless. Concatenate the pieces and turn every ▁ back into a space.

"Hello world."  ->  "▁Hello▁world."  ->  ['▁Hello', '▁world', '.']  ->  "▁Hello▁world."  ->  "Hello world."

Several defaults are worth knowing, because they change behavior in ways that surprise people.

• add_dummy_prefix=true adds a ▁ at the start of the text, so the first word is tokenized like any other word. The decoder removes it again.
• normalization_rule_name="nmt_nfkc" applies Unicode NFKC normalization (§2.5) and remove_extra_whitespaces=true collapses runs of spaces, so round trips are exact only up to normalization.
• character_coverage=0.9995 keeps the characters that cover 99.95% of the training text and treats the rarest characters as unknown, unless byte_fallback=true spells them out in byte tokens (§2.3).
• split_digits=false by default. Llama 1 and 2 turned it on to split numbers into single digits.
• The default model_type is unigram. Llama 1 and 2 used bpe.

SentencePiece's ▁ and GPT-2's leading-space convention (Ġworld) are two answers to the same question, where spaces go. Both attach the space to the following word. GPT-style byte-level tokenizers do it through the regex pre-tokenizer and never normalize, while SentencePiece does it inside the model and normalizes by default.

The real way, and the gradient trick

In production you call a library. In research, it is often handy to compute expected piece counts with automatic differentiation instead of writing the backward pass. The reason is a general fact about log-sum-exp. Treat each $\log p(v)$ as a free variable $\theta_v$. Then $\log P(X) = \operatorname{logsumexp}_{x}\sum_v c_v(x)\theta_v$, and its derivative with respect to $\theta_v$ is the posterior expected count, $\partial \log P(X) / \partial \theta_v = \mathbb{E}[c_v(x) \mid X]$. So the forward algorithm plus backward() is the E-step.

Bostrom and Durrett (2020) compared BPE and Unigram head to head for pretraining and found that Unigram's segmentations align more closely with morphology and that its models matched or beat BPE's on downstream tasks. Even so, byte-level BPE dominates large language models, mainly because it is simple, fast, lossless without normalization, and good enough once vocabularies are large.

Read more

• Schuster & Nakajima (2012). Japanese and Korean Voice Search. The original WordPiece, chosen by likelihood gain.
• Kudo (2018). Subword Regularization, Improving Neural Network Translation Models with Multiple Subword Candidates. The Unigram language model, its EM training and pruning, and sampled segmentations.
• Kudo & Richardson (2018). SentencePiece, a simple and language independent subword tokenizer and detokenizer. Lossless tokenization with the ▁ meta symbol, and the library design.
• Provilkov, Emelianenko & Voita (2020). BPE-Dropout, Simple and Effective Subword Regularization. Stochastic BPE in one changed line.
• Song et al. (2021). Fast WordPiece Tokenization. Linear-time MaxMatch with a trie and failure links.
• Bostrom & Durrett (2020). Byte Pair Encoding is Suboptimal for Language Model Pretraining. Unigram versus BPE, compared for pretraining.
• Hugging Face. WordPiece and Unigram tokenization, LLM course chapter 6. From-scratch implementations of both.

Watch next

▶

▶

▶