Unigram LM and SentencePiece

Every tokeniser discussed so far builds its vocabulary bottom-up: start small, merge upward. The Unigram language-model tokeniser inverts the process, starting absurdly large and pruning down, and that inversion is what makes it possible to assign a genuine probability to every possible segmentation of a string, not just the one the algorithm happens to output.

Top-down vocabulary construction

Kudo, 2018 begins with a large seed vocabulary, commonly all substrings above some frequency threshold, easily hundreds of thousands of candidates, together with a unigram language model that treats every vocabulary entry as having an independent occurrence probability. An EM-like loop then alternates: estimate each piece's probability given the current best segmentations of the corpus (via a Viterbi-style forward pass), then drop the pieces whose removal costs the least corpus likelihood, and repeat until the vocabulary reaches its target size. The resulting vocabulary is chosen to maximise the likelihood of the training corpus under a probabilistic segmentation model, not assembled by greedily chasing the single most frequent adjacent pair at each step the way BPE does.

Multiple valid segmentations

Because every piece carries a probability, a given string generally admits many valid segmentations, and the unigram model can rank them by joint probability (the product of each piece's probability) to find the best one (Viterbi decoding), or sample among the higher-probability candidates. That sampling capability is the direct seed of subword regularisation: training the same word with different valid segmentations across different examples so the model does not overfit to one deterministic split (see bpe-dropout-subword-regularisation for how this idea extended to plain BPE).

SentencePiece: the delivery vehicle

Kudo and Richardson, 2018 built SentencePiece as a language-agnostic tokeniser library implementing both BPE and the unigram algorithm above. Its central contribution sits upstream of the algorithm choice: it treats the raw input as an unmodified stream of Unicode characters, including whitespace, and encodes a space as an explicit symbol, conventionally a leading ▁ marker at the start of a word, rather than relying on a separate whitespace-based pre-tokenisation step. That decision makes the tokenisation reversible by construction: concatenate the decoded pieces, replace ▁ with a literal space, and the original string comes back byte for byte. It also lets the tokeniser segment languages with no whitespace between words, such as Japanese, Thai, or Chinese, without bolting on a language-specific word segmenter first. This is why SentencePiece, rather than a byte-level-BPE tokeniser like tiktoken, is the default for Llama, T5, and PaLM-style multilingual stacks (see tokenisation-bpe).

When it falls down

• Slower to train. The EM-based pruning loop over a much larger seed vocabulary is materially more expensive than BPE's frequency-count-and-merge loop.
• Tokenisation is not a fixed fact. The "canonical" segmentation of a string depends on the decoding strategy applied (Viterbi versus sampling), which can surprise anyone who assumes a tokeniser always produces one deterministic answer (see detokenisation-and-streaming for a related boundary subtlety).
• Whitespace-as-symbol has its own edge cases. The ▁ marker itself consumes vocabulary budget, and mishandling it during decoding can duplicate or drop spaces.

Further reading

• Kudo, 2018, Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates - the Unigram LM tokeniser and the original subword regularisation technique.
• Kudo and Richardson, 2018, SentencePiece: A Simple and Language Independent Subword Tokenizer and Detokenizer for Neural Text Processing - the library implementing both BPE and Unigram.