Tokenization — Advanced

Why

BPE encodes by applying its ordered merge rules greedily from highest to lowest priority, committing to each merge as it fires without ever reconsidering earlier choices in light of later ones. Because it takes locally best steps, the final segmentation can use more tokens than a globally optimal split would, and finding the truly minimal segmentation is an NP-hard problem BPE does not attempt. The random-skip option describes BPE-Dropout, a training-time augmentation, not standard deterministic encoding. The single-byte-preference option is wrong because BPE prefers to apply high-priority merges, which build longer tokens, not to keep bytes separate. The trivial-in-linear-time option is false: minimal segmentation is not trivially solvable, which is exactly why greedy BPE is used as a practical approximation. Unigram, by contrast, uses Viterbi to find the segmentation that maximizes total token probability, which is globally optimal under its model. This distinction is the core reason Unigram can produce shorter or more principled segmentations than BPE on some inputs, even though BPE dominates in practice for its simplicity and speed.

Why

BPE adds exactly one merge rule per iteration, and when two pairs tie for top frequency the implementation must resolve the tie with a fixed, deterministic rule, such as lexicographic order, so that training the same corpus twice yields the identical merge table. Determinism matters because the merge table is the tokenizer's entire trained state, and a tokenizer must produce reproducible IDs. Merging both pairs at once is wrong because it changes the algorithm's semantics and can produce different downstream counts, and the standard formulation adds one merge at a time. Choosing randomly is wrong because it would make the tokenizer non-reproducible, so the same corpus could yield different vocabularies on different runs. Aborting on ties is absurd, since ties are common and easily resolved. The deterministic tie-break is a small but essential detail: it is part of why a BPE tokenizer is a pure function of its training corpus and hyperparameters. Different libraries may choose different tie-break rules, which is one reason two BPE tokenizers trained on the same data can still differ.

Why

That score is the pointwise mutual information of the pair, measuring how much more often x and y co-occur than their independent probabilities would predict. WordPiece merges the pair that maximizes this quantity, so it can prefer a pair that is individually rare but strongly cohesive over a high-frequency pair whose members already appear commonly on their own. The identical-to-BPE option is wrong: frequency and PMI coincide only in special cases, and in general they select different merges, which is why BERT's WordPiece and a BPE tokenizer diverge on rare or morphologically complex words. The most-frequent-character option misdescribes the criterion, which scores pairs by mutual information, not by any single character's global frequency. The penalize-long-tokens option invents a length cap that is not part of the PMI criterion. The practical effect is that WordPiece splits tend to align with morpheme-like boundaries because cohesive units score highly, whereas BPE splits follow surface co-occurrence counts. Knowing the criterion lets you predict which tokenizer will segment technical vocabulary more cleanly.

Why

Unigram begins with an oversized candidate vocabulary and uses Expectation-Maximization to estimate each token's probability: the E-step finds probable segmentations of the corpus under current probabilities, and the M-step updates probabilities from the token counts in those segmentations. It then computes, for each token, how much removing it would increase the corpus negative log-likelihood, and prunes the tokens whose removal hurts least, repeating until it reaches the target size. The gradient-descent-on-transformer-weights option confuses tokenizer training with model training; the tokenizer is built before and independently of the model. The merge-in-E-step option describes a BPE-like constructive process, but Unigram is reductive and has no merges. The random-vocabularies option is not how Unigram works; it is a principled prune-down guided by loss, not random search. The result is a vocabulary where each surviving token earns its place by measurably reducing encoding cost, giving Unigram an information-theoretic grounding that BPE's merge-order-dependent vocabulary lacks. This EM-plus-pruning procedure is also what yields the probability model needed for subword regularization.

Why

Both algorithms share the same asymptotic complexity, but they differ in optimality. WordPiece's greedy decode takes the longest matching prefix at each position and moves on, which can lock in a locally long piece that forces a worse split later. Unigram's Viterbi is a dynamic program that implicitly considers all valid segmentations and returns the one with the highest total token probability, so it is globally optimal under its model despite the same time bound. The runs-faster option is wrong: they have the same complexity, and the advantage is optimality, not speed. The ignores-vocabulary option is false, since greedy longest-match matches against the vocabulary and does not split on whitespace. The lowercases-input option invents a normalization step that is not why Viterbi wins; the win comes from exploring the full segmentation space. This is why Unigram can avoid the garden-path splits that greedy longest-match sometimes produces. It is a classic case where two algorithms with equal complexity differ sharply in solution quality because one is greedy and the other does global dynamic programming.