How Small Can a Tokenizer Vocabulary Be? Data Quality Sets the Vocabulary Floor

Every language model splits text into subword units from a fixed vocabulary. Its size is set once, before training, and never changes. Recent work asks how large it should be: compute-optimal vocabulary grows with model scale [4]. How little suffices has drawn far less attention, though it is where the parameters are: our 4-layer encoders shrink from 8.9M parameters to 4.0M between vocabulary 20,000 and 750. Tokenizer differences that seem negligible at typical vocabulary sizes may become more important at smaller ones [3]. We ask how small a vocabulary can be before classification quality collapses; the answer depends less on the tokenization algorithm than on how clean the corpus is. To test this we sweep vocabulary from 100 to 20,000 tokens on MultiEURLEX [1], assigning EU legislation to 567 legal-topic labels, roughly five per document, over a 20k-document training set. To isolate the tokenizer's contribution we train 4-layer transformer encoders from scratch, since pretrained models arrive with a vocabulary already fixed. The same protocol runs on the parallel English, French and German editions, holding label set and domain fixed so language is the only variable. We sweep nine vocabulary sizes under normalization and six under raw, since three grid points fall below the character floor. Crossing these with two tokenizers, five seeds and three languages gives 450 runs, none collapsing to the degenerate state described below. We fix a 512-word window before tokenizing, so every vocabulary size sees the same text; a fixed token budget would instead measure truncation. nDCG@5 rises steeply with vocabulary then flattens near 0.61 (0.57-0.63 across languages). Taking onset as the smallest vocabulary whose seed median reaches 95% of the plateau (the median score over the largest third of the grid), we find that where it falls is not a stable property of the tokenizer. Plateau onset by condition, as English / French / German: raw unigram LM 2000 / 2000 / 2000; raw WordPiece 2000 / 2000 / 2000; normalized unigram LM 750 / 750 / 2000; normalized WordPiece 2000 / 1000 / 2000. Two effects appear only after normalization. In English the unigram model reaches the plateau with a 2.7x smaller vocabulary than WordPiece. German needs more vocabulary than English or French wherever they differ, consistent with compounding giving it 1.53x English's unique-word inventory (487,519 vs. 318,410 types). English and French are not separable: they tie under one tokenizer, French leads under the other, and the ordering flips under an alternative plateau definition, so we report only the German shift; that too is observed rather than established. All three also lose 0.038-0.050 nDCG@5 between peak and vocabulary 20,000, where rare tokens go undertrained. On raw text every language-tokenizer pair plateaus at 2000: corpus noise masks the differences tokenizer and morphology otherwise produce. A tokenizer's vocabulary cannot be smaller than its corpus's character inventory, the base-character-set problem identified for byte-level BPE by [5]. On raw legal text that inventory is 350-354 characters in all three languages, inflated by corrupted encodings and markup residue, and grows with corpus size. After normalization it is exactly 37 in every language, fixed by construction: a 9.5x reduction, and identical across languages, so the floor itself cannot account for the cross-lingual differences. Below the floor no subword can form, and the model classifies documents using character fragments carrying no linguistic signal. Cleaning therefore does not merely improve accuracy at a given vocabulary size, it changes which vocabulary sizes exist, so vocabulary size and corpus hygiene are confounded in any low-vocabulary comparison controlling for neither. Separately, a training pathology worth reporting on its own. Sparse multi-label problems are routinely handled by weighting positives by inverse label frequency. This makes "predict every frequent label" the optimum of the loss, not a failure to reach it: with $w=(1-p)/p$ the constant-prediction optimum is $\sigma^{*}=wp/(wp+1-p)=0.5$ for every label the cap does not clip. Our models emitted 50-165 labels per document against a true average of five, which reads as underfitting and is not; initializing the output bias at the label prior [2] removes it. Medians and IQRs over seeds are reported throughout. [1] Chalkidis et al. MultiEURLEX. EMNLP'21. [2] Lin et al. Focal Loss. ICCV'17. [3] Lotz et al. Beyond Text Compression. ACL'25. [4] Tao et al. Scaling Laws with Vocabulary. NeurIPS'24. [5] Wang et al. Byte-Level Subwords. AAAI'20.