Most large language models first cut text into pieces called tokens using a vocabulary learned from corpus statistics. In multilingual corpora dominated by English, words in smaller languages get cut into many more pieces. Each extra piece makes the model slower and more expensive to train, and it lowers accuracy. Across 16 African languages, the average number of tokens per word (called fertility) explains up to half the variance in multiple-choice accuracy, with drops of up to 18 percentage points per extra token per word (The Token Tax). This proposal asks how much of that unfairness comes from the training procedure rather than from the goal the tokenizer optimizes.
The Unigram tokenizer behind SentencePiece is a latent variable model. It treats the way each word is split as hidden and fits piece probabilities with Expectation-Maximization (EM), an algorithm that alternates between guessing the hidden splits and refitting the probabilities. Then it prunes the vocabulary greedily. Latent variable models trained by EM are known to settle into poor local optima, solutions that cannot be improved by small changes but are far from the best. In word alignment, one such degenerate solution is the "garbage collector" effect, where rare words soak up unrelated alignments. A fix that steers EM away from these solutions also exists: Graça et al. constrain the posterior, the E-step's distribution over hidden splits, using a small convex projection (Expectation Maximization and Posterior Constraints). We propose to measure whether multilingual Unigram training has a cross-lingual garbage-collector problem of its own, where low-resource words get assembled from short fragments shaped by high-resource languages. We would then replace the unconstrained E-step and pruning score with versions that enforce a per-language fertility budget.
Core Claim
We make two testable claims. First, at a fixed vocabulary size, Unigram training is sensitive to its seed vocabulary, data order and pruning schedule. That sensitivity shows up mostly as variance in per-language fertility for low-resource languages, while aggregate compression barely moves. If this holds, part of the token tax is an optimization artifact. Second, putting per-language expected fertility constraints into the E-step and the pruning criterion reaches a given per-language fertility profile at lower total token count than the obvious data-side fix. That fix is upsampling low-resource languages before tokenizer training. The second claim is the novel and risky one. If reweighting matches the constrained method at matched fertility, the constraint adds nothing, and we will report that outcome.
Formally, let $x$ be a word in language $\ell$ and $z$ one of its segmentations with $|z|$ pieces. Let $p_\theta(z \mid x)$ be the unconstrained Unigram posterior. The constrained E-step replaces it, for each language, with
$$q_\ell = \arg\min_{q} \; \mathrm{KL}\big(q \,\|\, p_\theta\big) \quad \text{s.t.} \quad \mathbb{E}_{x \sim \ell,\; z \sim q(\cdot \mid x)}\big[|z|\big] \le b_\ell,$$
where $b_\ell$ is a target fertility for language $\ell$. By the convex dual used in Graça et al., the solution has a simple form:
$$q_\ell(z \mid x) \propto p_\theta(z \mid x)\, \exp(-\lambda_\ell |z|),$$
with one nonnegative multiplier $\lambda_\ell$ per language, found by a one-dimensional line search. This acts as a language-specific per-piece penalty inside the forward-backward lattice computation, so the cost is essentially that of standard Unigram training. The M-step is unchanged. The pruning step scores each candidate piece by the loss in constrained rather than unconstrained likelihood. This matters because Which Pieces Does Unigram Tokenization Really Need? finds EM can be cut to a single iteration without collapse. That result suggests the discrete pruning path, not the continuous EM fit, is where the method's choices are effectively made. A constraint applied only in the E-step might therefore do little, so we apply it in both places.
Relation to Prior Work
The latent-variable side of this proposal comes from three sources. Graça et al. supply the method: an E-step projection with fertility-style constraints, which cut Hansards English–French alignment error from about 18% to 13% when they added an agreement constraint. They never applied it to segmentation lattices. Two papers motivate the restart study. Lee and Berg-Kirkpatrick show that initialization and reparameterization move a hidden Markov language model's perplexity from about 540 to about 313, so latent sequence models are very sensitive to where training starts. The broader treatment of local optima in latent models by Sutton et al. says the same in general terms.
Spectral learning (Hsu et al.) and moment-plus-likelihood methods (Estimating Latent-Variable Graphical Models using Moments and Likelihoods) offer guarantees against local optima. Their requirements are a rank condition for spectral learning and three independent observed views per latent variable for the moment methods. A segmentation lattice over a variable-length vocabulary does not naturally satisfy either, so we do not pursue them here.
Three lines of work already treat segmentation as latent. Grave et al. sum over all segmentations inside a neural language model, reaching 1.426 bits per character averaged over the 7-language Multilingual Wikipedia Corpus. Ataman et al. learn latent morphology inside a translation model. Land and Pinter simplify Unigram training and report 0.620 versus BPE's 0.221 English boundary recall at a 16K vocabulary. None of these examines restart variance, and none imposes per-language constraints on the tokenizer's own training. We do not change the language model at all, only the tokenizer that feeds it.
Two papers constrain our design. They find morphological boundary alignment explains almost none of the variance in downstream scores: $R^2 = 0.024$ for recall in Evaluating Morphological Alignment of Tokenizers in 70 Languages. They also find that cross-family gaps largely vanish once data and byte premium are controlled (Why do language models perform worse for morphologically complex languages?). We therefore deliberately constrain fertility, the quantity those results leave standing, and not morpheme boundaries. MorphScore enters only as a diagnostic. The harms documented for Aymara (Plata) and the suffix-driven perplexity spikes in Japanese (Gambardella et al.) motivate checking that lowering fertility does not simply produce worse splits.
Research Program
The first phase is a landscape audit. We train standard SentencePiece Unigram tokenizers at 32K and 64K vocabularies on a deliberately skewed multilingual mixture. English from FineWeb is the dominant share, the seven Multilingual Wikipedia Corpus languages are the mid-resource portion, and text in the AfriMMLU languages is the low-resource tail. The research file names no corpus for that tail, so we would have to source it, and we will report its size per language.
We train at least 20 restarts per setting. Restarts vary the subsampling of the seed vocabulary built from the suffix array, the data order, and the pruning shrink rate. For each restart we measure four things. The first is per-language fertility on FLORES-200, chosen because it is parallel, so content is held fixed across languages. The second is total token count. The third is the final likelihood. The fourth is a "borrowed piece" rate: the fraction of a language's tokens that are pieces at most three characters long whose training frequency comes mostly from another language. This rate is our operational test for a cross-lingual garbage collector.
The second phase implements fertility-constrained EM with the constrained pruning score. Budgets $b_\ell$ are set by one simple rule: a target ratio to English fertility on FLORES-200. We sweep that ratio to trace a curve of total tokens against the worst-language fertility. The third phase trains small decoder language models, around 300M parameters, on identical byte budgets with each tokenizer. This checks whether lower fertility at fixed total compression helps the model or just moves cost around.
Baselines
The naive reference point is standard SentencePiece Unigram trained on the natural mixture, and alongside it byte-pair encoding (BPE) at the same vocabulary size. This is what practitioners actually ship. For Unigram, the only reported number in the file is English boundary recall of 0.620 at 16K, versus 0.221 for BPE (Land and Pinter). We found no reported per-language fertility for SentencePiece on AfriMMLU languages on Lacuna, so we will measure our own.
The second baseline is the simplified pipeline of Land and Pinter: one EM iteration with Final-Style Pruning. It is the strongest published variant of Unigram training, and it already shows that EM details matter less than expected.
The strongest competitor on this question is data-side rebalancing. One version applies temperature-based upsampling of low-resource languages before Unigram training. A second version allocates a fixed vocabulary quota to each language, trains per-language tokenizers and merges them. Both target fertility directly with no optimization machinery.
Every method gets the same raw text and vocabulary size, plus a matched tuning budget of 20 configurations. That budget covers the sampling temperature or quota ratio for rebalancing and the fertility ratio for our method. Methods are compared on the same curve of total tokens against worst-language fertility. Beating rebalancing means one of two outcomes. Either our method reaches the same worst-language fertility with fewer total tokens, or it reaches lower worst-language fertility at equal total tokens. In both cases the margin must exceed the restart variance measured in phase one.
The key ablation applies the constraint only in the E-step, with ordinary pruning. A second ablation applies only the constrained pruning score. Together these show which ingredient does the work.
Why not just…?
Why not just upsample low-resource languages before training the tokenizer? This is the most serious threat, and it may well work as well as our method. Reweighting raises the counts of every piece in language $\ell$. The constraint instead changes which splits of language-$\ell$ words get counted, favoring longer pieces. The two should differ most when upsampling also inflates rare-language noise and spends vocabulary on low-value pieces. The matched-fertility comparison above decides the question. If the two curves coincide within restart variance, we will report that posterior constraints add nothing beyond data rebalancing.
Why not just train fewer EM iterations, since Unigram is already robust? Land and Pinter show robustness of aggregate compression and English MorphScore. They do not measure restart variance or per-language fertility in a skewed multilingual mix. Phase one measures exactly that. If the variance there is negligible too, the "optimizer artifact" half of our claim fails. The constraint would then stand only as a change of objective, compared to rebalancing on the same terms.
Why not just drop tokenizers and model bytes? ByteFlow reports 63.19% average downstream accuracy against 60.15% for a BPE LLaMA baseline at 1.3B parameters. That result is on English FineWeb-Edu, though, and the byte premium makes non-Latin scripts systematically longer in bytes (Why do language models perform worse…). Byte models move the fairness problem into sequence length rather than removing it. Our work is also complementary: subword tokenizers remain what most deployed systems use.
Decisive Checks
The first check is restart variance. Across restarts, the spread in low-resource fertility on FLORES-200 must be large relative to the spread in total tokens. Concretely, the coefficient of variation for low-resource languages should be several times that of English. If it is not, we drop the local-optima framing.
The second check is the matched-fertility frontier against rebalancing, described under Baselines. This is the go or no-go test for the method.
The third check is downstream. We report tokenizer-independent bits per byte on held-out text per language, SIB-200 topic classification and MultiBLiMP grammatical acceptability across tokenizers. All use the same language model budget. AfriMMLU accuracy is reported for completeness, though we expect 300M-parameter models to sit near chance on it.
The fourth check is a guard against degenerate splits. MorphScore and the borrowed-piece rate should not get worse as fertility falls. If they do, we have only traded short fragments for arbitrary long ones.
A positive result would show that part of the token tax is fixable inside the tokenizer's own optimizer at almost no extra cost. A negative result against rebalancing would still be useful. It would tell practitioners that the cheap data-side fix is all they need.
References
- The Token Tax: Systematic Bias in Multilingual Tokenization
- Expectation Maximization and Posterior Constraints
- Which Pieces Does Unigram Tokenization Really Need?
- Optimizing Hidden Markov Language Models: An Empirical Study of Reparameterization and Initialization Techniques
- An Introduction to Conditional Random Fields
- A Spectral Algorithm for Learning Hidden Markov Models
- Estimating Latent-Variable Graphical Models using Moments and Likelihoods
- Training Hybrid Language Models by Marginalizing over Segmentations
- A Latent Morphology Model for Open-Vocabulary Neural Machine Translation
- Evaluating Morphological Alignment of Tokenizers in 70 Languages
- Why do language models perform worse for morphologically complex languages?
- Tokenization as Cultural Erasure: How Corpus Composition Shapes the Representation of Aymara Morphology in NLP Systems
- Inconsistent Tokenizations Cause Language Models to be Perplexed by Japanese Grammar
- ByteFlow: Language Modeling through Adaptive Byte Compression without a Tokenizer