Backup-Aware Vocabulary Search for Subword Tokenizers

Every modern language model splits text into pieces from a fixed list of subword tokens, called its vocabulary. The standard algorithms that build this list judge each candidate token only by how much it helps the corpus right now. Byte Pair Encoding repeatedly merges the most frequent adjacent pair. Unigram LM pruning deletes whichever token costs the least corpus likelihood. Neither asks what happens to a word if one of its pieces were missing, or how a word the tokenizer never saw would be split. The result is well documented: unseen words get cut into "alien" fragments that cross morpheme boundaries, such as "h_iked" for "hiked", and downstream models understand those words noticeably worse.

Combinatorial optimization has a name for this failure. It is oblivious local search, meaning search that moves only when the raw objective improves. Its standard fix is to search on a surrogate "potential" that also rewards backup structure. We propose to import one specific fix, the second-closest-facility potential that broke the long-standing locality barrier for $k$-median clustering, into tokenizer construction. Each word is scored by how cheaply it can be segmented and also by how gracefully its segmentation degrades when a token it depends on is removed. Our claim is that vocabularies found by swap-based local search on this backup-aware potential give more morphologically valid splits of unseen words, and better downstream generalization, at equal vocabulary size. The method uses no morphological supervision at all.

Core Claim

In metric $k$-median, oblivious local search tracks only each client's distance to its nearest open facility. A swap that preserves the nearest facility but destroys every good alternative looks free, and the search stalls at a factor-3 locality gap. An Improved Local Search Algorithm for k-Median adds a capped penalty on the distance to the second-closest facility, with $\alpha=3$ and $\beta=1/5$, and reaches $2.836+\epsilon$ with pure local search.

Tokenizer induction has the same shape. Words play the role of clients and their segmentations play the role of facilities. SentencePiece-style pruning estimates a token's removal cost from the words' current best segmentations. Two tokens that back each other up each look cheap to remove, so batch pruning can delete both. Frequency merging, in turn, happily creates whole-string tokens whose words have no reasonable fallback.

We define, for a vocabulary $V$ of fixed size $K$, the potential

$$\Phi(V) = \sum_{w} f(w)\Big(c_1(w,V) + \beta \min\{\bar c_2(w,V),\ \alpha\, c_1(w,V)\}\Big),$$

where $f(w)$ is the corpus frequency of word type $w$ and $c_1(w,V)$ is the negative log-probability of its best segmentation under a unigram token model. The backup cost $\bar c_2(w,V)$ is the average, over the tokens $t$ in that best segmentation, of $c_1(w, V\setminus\{t\})$, the cost of the best split that avoids $t$. This averaging over single deletions is the tokenizer analogue of the random-deletion cushioning in Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search. The cap $\alpha c_1$ keeps words that have no sensible alternative (such as rare names) from dominating the objective, just as in the $k$-median potential.

The hypothesis we test is empirical, not a theorem. Morpheme boundaries are places where many alternative segmentations agree. A vocabulary that minimizes $\Phi$ should therefore place tokens along those boundaries, which is exactly where unseen inflections and compounds need them.

Relation to Prior Work

The research file reports no prior work applying non-oblivious potentials to vocabulary construction. The closest neighbors play three different roles.

The tokenizers we modify supply the baseline and the move set. Neural Machine Translation of Rare Words with Subword Units builds BPE by greedy frequency merges. Subword Regularization prunes a large seed vocabulary by likelihood loss and samples alternative segmentations during training. Our method keeps Kudo's unigram cost model but changes two things: the objective gains a backup term, and the search moves from one-way deletion to add-remove swaps that can undo earlier choices. There is a direct link to Kudo's work. Subword regularization only helps when words actually have several good segmentations, and our potential selects vocabularies for that property.

The evidence of the gap comes from elsewhere. Evaluating Subword Tokenization: Alien Subword Composition and OOV Generalization Challenge shows that morphological compositions beat alien ones by 2.7 to 7.2 points on the Word and Morphology task. It also finds that enlarging BPE past 40,000 to 50,000 tokens does not remove alien fragments. Vocabulary Adaptation for Domain Adaptation in Neural Machine Translation shows the domain version of the problem: technical terms are forced onto source-domain fragments.

Two results constrain the design. Getting the most out of your tokenizer reports that swapping a pretrained model's tokenizer needs more than 50 billion tokens of fine-tuning, so we evaluate by training models from scratch, not by retrofitting. Efficient Submodular Optimization under Noise: Local Search is Robust gives some reassurance that local search tolerates an inexact oracle. This matters because our backup costs are estimated on sampled word types.

Unlike A Local Search-Based Approach for Set Covering, which treats sets as fixed abstract objects, our "coverage" is defined by a segmentation lattice. Adding a token changes the segmentations of many words at once. For that reason we do not claim a proven approximation ratio.

Research Program

The algorithm starts from a Unigram LM vocabulary of size $K$ and a pool of candidate substrings drawn from the seed vocabulary. A move swaps one vocabulary token for one pool candidate. A swap is accepted if $\Phi$ drops by at least a $(1-\epsilon/K)$ factor, the usual rule that keeps local search polynomial. The unigram probabilities are re-fit by EM every fixed number of accepted swaps.

To make this tractable, we compute $c_1$ and the deletion costs on the lattice of each word type, not on running text. A swap only touches the word types that contain the affected substrings, and an inverted index from substrings to word types makes the incremental update cheap. Candidate swaps are proposed by sampling, weighted toward tokens that umLabeller would flag as alien. This weighting affects only which swaps are proposed, never whether they are accepted, so no morphological signal enters the objective.

The analysis part asks whether the backup term alone recovers morphology. We will measure how the alien rate, the morph rate and compression trade off as $\beta$ and $\alpha$ vary, with $\beta=0$ as the oblivious limit. We will also check the mechanism directly: do the tokens that $\Phi$ adds and removes, relative to Unigram LM, sit at UniMorph morpheme boundaries more often than chance?

Baselines

The naive reference point is standard BPE from Sennrich et al. at matched vocabulary size, including the 40,000 to 50,000 range that Batsuren et al. found best. On WMT15 English–German it reaches a rare-word unigram F1 of 41.8% with the BPE-J90k model, against 36.8% for the dictionary back-off baseline. BLEU gains over back-off are up to 1.1 for English–German and 1.3 for English–Russian.

The strongest existing method is SentencePiece Unigram LM with subword regularization. Kudo reports gains of +1 to +2 BLEU over BPE on low-resource English–Vietnamese (IWSLT15). The file gives no absolute BLEU for that system, so we will reproduce it ourselves. It is the strongest competitor because it already uses the same cost model and already exploits alternative segmentations.

All tokenizers will be trained on identical corpora at identical $K$. Downstream models will use the same architecture, number of training steps and hyperparameter search budget, with only the tokenizer varying. Subword regularization will be applied to every unigram-based variant, including ours.

Two ablations isolate the key ingredient. The first runs our swap search with $\beta=0$, so any gain from allowing swaps is separated from gain due to the backup term. The second replaces $\Phi$ with the full marginal likelihood summed over all segmentations. This also implicitly rewards having alternatives, but it has neither the deletion structure nor the cap.

Beating the baselines means two things at matched compression (tokens per word within 2%). The first is a lower umLabeller alien rate on held-out words. The second is a gain on the Word and Morphology and Word and Definition tasks that exceeds seed variance, together with no BLEU loss on WMT15 or IWSLT15.

Why not just…?

Why not just prune Unigram LM more gently, one token at a time? Part of the redundant-pair failure comes from batch deletion, so exact single-token pruning might recover most of the benefit. The $\beta=0$ swap-search ablation, run next to exact one-at-a-time pruning, measures this directly. If the two match our full method, the backup term contributes nothing, and we would report the result as a finding about pruning schedules.

Why not just pre-segment with a morphological analyzer before running BPE? This is the most serious threat on the alien-rate metric, because it optimizes that metric almost directly. Its limits are that it needs a morphological analyzer and UniMorph-style data for each language, and it does nothing for domain terminology or code, which have no analyzer. We will include it as a supervised upper reference on English. We will then test transfer to EMEA medical terminology and German compounds, where analyzer coverage is weaker. Our claim is only that the unsupervised potential closes a substantial part of the gap to the supervised method, not that it beats it.

Why not just optimize marginal likelihood, which already rewards words with many segmentations? Marginal likelihood is dominated by the best path. It does not ask whether the fallback survives when a specific token is removed. This is exactly the difference between summing over facilities and asking what happens when the nearest one closes. The marginal-likelihood ablation above settles the question empirically. If it matches $\Phi$, the $k$-median analogy adds nothing, and we will say so.

Why not just enlarge the vocabulary? Batsuren et al. find that alien fragments persist past 40,000 to 50,000 tokens. The tokenizer study reports that larger vocabularies raise embedding and softmax costs. All of our comparisons are therefore made at fixed $K$.

Proposed Experiments

We will first measure the tokenizers intrinsically on held-out English word types drawn from UniMorph and WordNet. Using umLabeller, which the authors report classifies subword compositions with 98% accuracy, we will record the vocab, morph and alien rates. We will also report deletion robustness: the average increase in segmentation cost when a random vocabulary token is removed.

Second, we will pretrain small BERT-style encoders from scratch on BookCorpus with each tokenizer and evaluate them on the OOV Generalization Challenge 1.0, which has three tasks: Word and Definition, Word and Morphology, and Word and Word. The reference gap to close is the 2.7 to 7.2 point advantage of morphological over alien compositions on Word and Morphology.

Third, we will train translation models on WMT15 English–German and English–Russian and on IWSLT15 English–Vietnamese. We will report BLEU and rare-word F1, with the BPE figure of 41.8% as the anchor. We will add Europarl-to-EMEA French–English to test whether gains carry over to unseen medical terminology. For that transfer, the file reports only statistical-MT BLEU (20.34 to 20.80 from graph propagation), which is not directly comparable.

The decisive check is the pair of ablations. If the full potential cuts the alien rate and improves Word and Morphology over both $\beta=0$ swap search and marginal-likelihood search, at matched compression and across three seeds, then the backup-aware potential is doing the work. If not, the idea fails cleanly.