SentencePiece › Training Algorithms

SentencePiece offers two algorithms for learning the vocabulary: BPE and the unigram language model. Both algorithms work on the ▁-encoded text and produce a vocabulary of subword tokens, but they approach the problem from opposite directions and embody fundamentally different philosophies about how to define a good vocabulary. Understanding both algorithms gives you better intuition for diagnosing tokenization problems and selecting configurations.

The algorithms we described in the previous chapters operate on pretokenized input, so the vocabulary they learn cannot create tokens that cross word boundaries. In SentencePiece, because the ▁ character is just another character, the algorithms can in principle create tokens like "ing▁the" that span a word ending and the beginning of the next. In practice this rarely happens for high-frequency patterns, because such cross-boundary patterns are not consistent enough to be worth merging. But the algorithm is free to make this choice based on data, not based on a rule we imposed.

BPE in SentencePiece works exactly as described in the earlier BPE chapter, but now operating on ▁-encoded text rather than pretokenized words. The key difference is that merges can cross what would traditionally be word boundaries, because the boundary information is encoded in the ▁ character itself rather than in empty space.

At each step, the algorithm counts every pair of adjacent tokens in the corpus and identifies the pair $(a, b)$ that appears most frequently. This is the pair whose frequency across the entire corpus, not just within individual words, is highest. The algorithm computes:

$$(a^*, b^*) = \arg\max_{(a,b)} \text{count}(a, b)$$

where:

• $(a, b)$: a pair of adjacent tokens in the current representation of the training corpus
• $\text{count}(a, b)$: the number of times tokens $a$ and $b$ appear consecutively anywhere in the corpus
• $(a^*, b^*)$: the optimal pair to merge, which becomes a new single token $ab$

Why does this greedy selection make sense? Notice that by merging the most frequent pair at each step, we are always reducing the total number of tokens in the corpus by the maximum possible amount in a single merge operation. Each merge of pair $(a, b)$ reduces the token count by exactly $\text{count}(a, b)$ occurrences. Choosing the maximum-frequency pair maximizes this reduction. The greedy strategy does not guarantee the globally optimal vocabulary, but it is computationally tractable and produces high-quality vocabularies in practice.

The algorithm adds the merged token to the vocabulary and replaces all occurrences of the pair in the corpus. This continues until the vocabulary reaches the target size. The sequence of merges is saved as the model, and applying the same merges in order to any new text produces the same tokenization.

An important property of BPE in SentencePiece: the ▁ character participates in merges just like any other character. So the very first merges in a multilingual corpus might produce tokens like "▁t", "▁a", or even "▁the" as full tokens if those patterns are frequent enough. The algorithm does not treat ▁ as a special separator; it simply learns whatever patterns appear most frequently in the data. This means that in a well-trained model, most high-frequency words will appear as single tokens with the ▁ prefix, which is exactly the behavior you want.

Where BPE builds vocabulary bottom-up through greedy merging, the unigram language model takes a top-down approach. It starts with a large initial vocabulary containing all substrings up to some maximum length, then prunes it down to the target size using the Expectation-Maximization (EM) algorithm. Think of BPE as sculpting by addition (you start with individual characters and add larger units) while unigram is sculpting by subtraction (you start with a vast vocabulary and remove the least useful pieces).

The fundamental question the unigram model answers is: given a vocabulary $V$, what is the best way to tokenize any piece of text? And working backwards: which vocabulary $V$ gives us the best tokenizations across the entire training corpus?

To answer these questions formally, the goal is to find a vocabulary $V$ and associated token probabilities $\{P(x)\}_{x \in V}$ that maximize the likelihood of the training corpus. The model assumes that tokens within a segmentation are independent (hence "unigram"), so the probability of a segmentation $\mathbf{x} = (x_1, x_2, \ldots, x_k)$ is simply the product of the individual token probabilities.

For a corpus of texts $T_1, T_2, \ldots, T_N$, the objective is to maximize the total corpus log-likelihood:

$$\mathcal{L}(V) = \sum_{t=1}^{N} \log P(T_t)$$

where:

• $\mathcal{L}(V)$: the log-likelihood of the corpus under vocabulary $V$ and its associated probability distribution
• $P(T_t)$: the probability of text $T_t$, summed over all possible segmentations

The probability of a text must account for the fact that there are many valid ways to segment it. Rather than committing to a single segmentation (as BPE does), the unigram model marginalizes over all possible segmentations, which is what makes it probabilistic rather than deterministic:

$$P(T_t) = \sum_{\mathbf{x} \in S(T_t)} P(\mathbf{x}) = \sum_{\mathbf{x} \in S(T_t)} \prod_{i=1}^{|\mathbf{x}|} P(x_i)$$

where:

• $S(T_t)$: the set of all possible segmentations of text $T_t$ using tokens from $V$
• $P(\mathbf{x})$: the probability of segmentation $\mathbf{x}$, which equals the product of individual token probabilities under the unigram independence assumption
• $P(x_i)$: the probability of the $i$-th token in segmentation $\mathbf{x}$

Why does this formula make sense? Notice that we are treating the text as having been generated by randomly choosing a segmentation, then generating each token independently according to its unigram probability. The marginal probability of observing the text is then the sum over all the ways that process could have produced it. This is exactly the setup of a hidden Markov model where the segmentation is the hidden variable. Maximizing this likelihood pushes the model to assign high probability to the most natural-looking segmentations while still maintaining a coherent probability distribution over all segmentations.

Since the sum over all segmentations is exponentially large (there are an exponential number of ways to segment even a moderately long string), computing it naively is intractable. The key computational tool is the Viterbi forward-backward algorithm, which computes the sum efficiently by dynamic programming in time proportional to the string length times the maximum token length.

Training alternates between two steps that mirror the E-step and M-step of standard EM. In the E-step, for each text the algorithm uses the forward-backward algorithm to compute expected token counts: how often, averaged over all possible segmentations weighted by their probability under the current model, does each token appear? These are called expected counts or soft counts because they are fractional rather than integer. In the M-step, the algorithm re-estimates token probabilities from these expected counts:

$$P(x) = \frac{\text{expected\_count}(x)}{\sum_{x' \in V} \text{expected\_count}(x')}$$

where:

• $\text{expected\_count}(x)$: the fractional count for token $x$ across the corpus, derived from the E-step forward-backward computation
• The denominator normalizes these counts into a valid probability distribution

After each EM iteration, the algorithm computes how much removing each token $x$ would reduce the corpus log-likelihood. This quantity, called the loss of token $x$, measures how much the rest of the vocabulary can compensate for that token's absence. Tokens whose removal causes the smallest loss are least necessary and are candidates for pruning. Typically 10 to 20 percent of the vocabulary is removed per iteration, and the E-step and M-step cycle repeats until the target vocabulary size is reached.

The pruning criterion is elegant because it accounts for token interactions. A token that appears frequently but whose occurrences can always be covered by two shorter tokens has a low loss and will be pruned. A token that appears less frequently but covers sequences that would otherwise require many short tokens has a high loss and will be retained. The algorithm learns vocabulary coverage patterns, not just raw frequency.

Both BPE and unigram produce similar results in practice, and in fact many production models have been trained with both and achieved comparable downstream performance. But they have different properties that matter in specific settings, and understanding those properties helps you make an informed choice rather than just defaulting to one or the other.

BPE is deterministic: given a vocabulary, the tokenization of any text is uniquely determined by applying the merge rules in order. This consistency is useful for systems where reproducibility is critical and for any analysis that assumes a fixed tokenization. Given the same input and the same model, BPE always produces exactly the same output, making debugging straightforward. BPE also tends to be faster to apply at inference time because it is just a sequence of string replacement operations; no probability computation is needed.

The unigram model is probabilistic: for any text, there are multiple valid segmentations, each with an associated probability under the model. The most probable segmentation can be found with the Viterbi algorithm and is used as the default at inference time. But during training, SentencePiece can sample from this distribution rather than always taking the most probable segmentation. This technique, called subword regularization, acts as a form of data augmentation: the model sees the same text split in different ways across different training steps, which helps it learn that meaning is carried by morphemes rather than specific token boundaries.

Subword regularization is especially valuable for translation and other sequence-to-sequence tasks. If the model always sees "tokenization" split as ["token", "ization"], it may not learn that "token" carries the same meaning in "tokenize" and "tokenized". By occasionally sampling ["token", "iz", "ation"] or ["tokeniz", "ation"], the model sees more variation in how the same morphemes appear across contexts. Empirically, models trained with subword regularization generalize better to out-of-vocabulary words and morphological variants than models trained with deterministic tokenization.

For most practitioners building new models today, the choice between BPE and unigram is less important than the vocabulary size and the quality and size of the training corpus. If you need subword regularization for a translation or generation task, choose unigram. If you need guaranteed reproducibility or the fastest possible inference, choose BPE. If you are unsure, unigram is generally the safer default.