Objective vs. Search: Decomposing What Makes a Good Tokeniser

Tokenisers used by systems such as OpenAI models and Llama-style decoders differ in two entangled ways: the objective they optimise—compression or unigram log-likelihood—and the search strategy—bottom-up merging or top-down pruning. This paper isolates those factors in a 2×2 design by introducing BottomUpLL, which combines bottom-up search with likelihood optimisation, and TopDownComp, which combines top-down pruning with compression. The experiments train tokenisers on 2B tokens from FineWeb-Edu for English and on a 20B-token, five-language corpus, then train Llama-style language models from 100M to 1B parameters with vocabularies of 8k, 32k, and 128k. Across nearly every condition, search procedure matters more than objective for bits-per-byte: bottom-up methods outperform their top-down counterparts. In the English 1B, 128k-vocabulary setting, BPE reaches 0.7790 BPB versus 0.7872 for UnigramLM, while multilingual results show the same bottom-up advantage. However, this ordering does not consistently transfer to grammaticality on BLiMP, MultiBLiMP, or ZhoBLiMP; at small vocabularies, likelihood objectives can help. The analysis also finds that learned vocabularies cluster by search strategy, with BPE and BottomUpLL sharing 80.5% of tokens at 128k, and that top-down deletion scores require approximations: a local replacement method recovers 81.5% of the vocabulary selected by exact scoring. The central conclusion is that tokeniser search is an independent architectural choice, not merely an implementation detail behind the objective.