Explain the Unigram LM tokenization algorithm and how its training differs fundamentally from BPE. What does stochastic tokenization enable?

**BPE** and **Unigram LM** are the two main subword tokenizer training algorithms, and they work in opposite directions. BPE starts from the smallest possible vocabulary, individual characters or bytes, and grows. At each step it finds the most frequent adjacent pair and merges it into a new token, repeating until the vocabulary reaches the target size. BPE always produces exactly one tokenization of any string. Unigram LM starts from a large candidate vocabulary, every n-gram up to some length plus common subwords, and shrinks. At each step it works out which tokens contribute least to describing the training text, measured by corpus likelihood, and removes them. It repeats until the vocabulary reaches the target size. The special property of Unigram LM is that it learns a probability for every possible split of a string, not just one. So the same word can be cut differently on different training passes. That built-in variation is a kind of data augmentation, making the model sturdier on spelling and morphology variation, which BPE cannot offer because it is deterministic.

**BPE is additive**, starting from characters and merging up by frequency. **Unigram LM is subtractive**, starting from a large vocabulary and pruning down by likelihood. Unigram LM frames vocabulary selection as likelihood maximization through an EM loop. The E-step estimates token probabilities across all possible segmentations of the training sentences. The M-step prunes the tokens whose removal costs the least likelihood. The objective sums the corpus log-likelihood over every segmentation, treating the split as a hidden variable. BPE, by contrast, has a single criterion: merge the most frequent pair, irreversibly. The capability this unlocks is **stochastic tokenization**. Because Unigram LM yields a distribution over segmentations, training can sample different splits of the same word. For example, 'tokenization' becomes token plus ization on one pass and token, iz, ation on another. That is subword-level data augmentation, which improves robustness to typos, morphology, and out of distribution text. At inference you switch back to the single most probable split for reproducibility. BPE produces one deterministic segmentation and cannot do this.