Objective vs. Search: Decomposing What Makes a Good Tokeniser Ahmetcan Yavuz1
Clara Meister2 Tiago Pimentel1 ETH Zürich, 2 EPFL [email protected], [email protected], [email protected] 1
Ahmetcanyvz/comp-vs-like
Ahmetcanyvz/comp-vs-like
Abstract
search procedure
1
bottom-up (merging)
top-down (pruning)
compression
BPE
TopDownComp
log-likelihood
BottomUpLL
ours
objective
arXiv:2609.19145v1 [cs.CL] 16 Sep 2026
Two dominant tokenisation algorithms are used by modern language models: byte-pair encoding (BPE) and UnigramLM. These differ along two orthogonal axes: their optimisation objective (compression vs. log-likelihood) and their search procedure (bottom-up merging vs. top-down pruning). Existing comparisons confound these axes, making it unclear whether their observed differences stem from what is being optimised vs. how it is being optimised. We disentangle the two by introducing two new tokenisation algorithms that complete this 2×2 design space: BottomUpLL, a bottom-up likelihood-based tokeniser, and TopDownComp, a top-down compression-based tokeniser. We train language models with tokenisers produced by each algorithm, varying: model size, vocabulary sizes, and domain (English-only vs. multilingual). Evaluating models on bits-perbyte, we find that the search procedure—not the objective—is the dominant factor: bottom-up tokenisers consistently achieve lower bits-perbyte in most settings. Evaluating models on the BLiMP task, however, shows no consistent relationship between design choice and performance. Overall, our results disentangle the effect of tokeniser design choices on language modelling performance, offering concrete guidance for their more principled construction.
ours
UnigramLM
Figure 1: Design choice factorisation for tokenisation.
tokenisers in current use: (i) byte-pair encoding (BPE), which learns a vocabulary that maximises the compression of a training corpus (Gage, 1994; Sennrich et al., 2016); and (ii) UnigramLM, which learns a vocabulary that maximises the unigram log-likelihood of a training corpus (Kudo, 2018). Despite their widespread usage, though, it remains unclear what makes a good tokeniser. BPE and UnigramLM are used as the default algorithms; yet their design choices have received little direct examination, and upon closer inspection, confound many of the existing comparisons. As a concrete example, the results of Schmidt et al. (2024)— that language models trained with BPE often perform better than those trained with UnigramLM— are commonly read as evidence that compression is a better optimisation objective than unigram loglikelihood. Optimisation objectives, though, are only one facet of a tokeniser learning algorithm. BPE and UnigramLM also differ in the search procedure used to maximize the objective.1 Given a dataset, BPE uses a bottom-up search, greedily merging symbols to maximise compression. UnigramLM relies on a top-down search, starting from an oversized vocabulary and iteratively pruning tokens to maximise log-likelihood. BPE and UnigramLM therefore differ along two axes at once:
Introduction
Before a language model (LM) processes text, its raw character string is mapped to a token string, which defines the model’s input. This mapping is performed by a tokeniser, a foundational component of modern language modelling pipelines, used in virtually all state-of-the-art models (Team, 2026; OpenAI et al., 2025; Team et al., 2026). A tokeniser is defined by several attributes. Some, such as the vocabulary size, are set by the practitioner while others, such as the vocabulary itself, are learned from data by a tokeniser learning algorithm. Two such algorithms account for most
1 The optimisation problem that such algorithms must solve is, in general, NP-hard (Kozma and Voderholzer, 2024; Whittington et al., 2025; Kastreva et al., 2026), so tokeniser learning algorithms typically approximate a solution with a heuristic search procedure.
1
the optimisation objective and the search procedure. A comparison between the two cannot attribute the difference in performance to either axis alone. In this work, we disentangle these two axes. We introduce BottomUpLL, a bottom-up likelihoodbased tokeniser that mirrors BPE’s merge procedure but optimises corpus log-likelihood instead of compression. We also introduce TopDownComp, a top-down compression-based tokeniser that follows UnigramLM’s pruning procedure but optimises compression. Together with BPE and UnigramLM, these methods form a 2 × 2 study crossing objective (compression vs. log-likelihood) and search procedure (bottom-up vs. top-down); see Fig. 1. We train language models with tokenisers produced by all four algorithms, evaluating them in English-only and multilingual settings. We analyse these models with a combination of extrinsic and intrinsic evaluations. Notably, our results show that search procedure has a stronger influence on bits-per-byte (BPB) than the training objective, with bottom-up tokenisers achieving the best BPB scores in nearly all experimental conditions (BPE outperforms TopDownComp, and BottomUpLL outperforms UnigramLM). This ordering does not carry over to grammaticality judgements (on a BLiMP task), though, where neither the objective nor the search procedure separates the tokenisers consistently. Interestingly, at small vocabulary settings, however, the objective still matters, with likelihoodbased tokenisers outperform compression-based ones. Overall, our results highlight the importance of both optimisation objective and search procedure to tokeniser training algorithm design.
2
Notably, tokenisers are usually not allowed to output any possible segmentation of c, being instead constrained to segment it using only the tokens in a finite set called its vocabulary S ⊂ Σ+ . To ensure that any character-string can be represented as tokens, we enforce Σ ⊆ S. How do we convert between character- and token-strings, though? Given just a vocabulary S, there are multiple different ways a character-string could be mapped to items in that vocabulary. For example, if S = {a, aa, aaa}, then the characterstring c = aaa may be encoded as either ⟨a, aa⟩, ⟨aa, a⟩, or ⟨a, a, a⟩, which we refer to as segmentations. Consequently, a tokeniser is defined not only by its vocabulary, but also by how it maps characterstrings to segmentations. This mapping is the job of an encoding function, tok : Σ∗ → S ∗ , which segments the original character-string into tokens; ◦ by definition, we have thus that c = tok(c). Finally, a tokeniser also contains a decoding function, detok : S ∗ → Σ∗ , which converts tokenstrings back into characters, being typically defined as the concatenation of each token’s characters: def detok(s) = s1 ◦s2 ◦· · ·◦s|s| . Formally, we thus dedef
fine a tokeniser as the tuple T = ⟨S, detok, tok⟩.
3
How do we select such a tokeniser? Here, we cast the learning of a tokeniser as the combination of two design components: an objective function and a search procedure. 3.1
Language modelling starts from raw text, which can be represented as character-strings c ∈ Σ∗ ; these are finite sequences of characters c = c1 c2 . . . c|c| over alphabet Σ.2 A tokeniser’s job is then to segment these character-strings into tokenstrings s ∈ S ∗ : sequences s = ⟨s1 , s2 , . . . , s|s| ⟩, where each symbol st is called a token and represents a non-empty character span. Whenever s is a segmentation of c, we say these strings are ◦ equivalent, which we denote as c = s, i.e.:3 ◦
Objective Functions
Given a tokeniser T and a dataset D = {cm }M m=1 , an objective function G assigns a score to the tokeniser. Different objectives encode different notions of what makes a tokeniser useful. We focus on two standard objectives used by tokeniser learning algorithms: compression and log-likelihood. Under the compression objective, the quantity to be minimised is the total number of tokens that the tokeniser produces on the dataset: X def Gcomp (tok, D) = |tok(c)|, (2)
Tokenisation
c = s ⇐⇒ c = s1 ◦ s2 ◦ · · · ◦ s|s| ,
Learning a Tokeniser: Optimisation Objective vs. Search Procedure
c∈D
This is appealing because shorter token strings improve effective context usage and reduce the number of model steps needed to process a dataset. Under the log-likelihood objective, the minimised quantity is the negative log-probability that
(1)
2 As usual, Σ∗ denotes the Kleene star of Σ, while Σ+ denotes the set of all non-empty strings over Σ. 3 We restrict our discussion to lossless tokenisers here.
2
a given probabilistic model pθ assigns the corpus: X def Gll (tok, D) = − log pθ tok(c) . (3)
applying it to a token-string rewrites every (nonoverlapping) occurrence of bigram s′ , s′′ into the token snew = s′ ◦ s′′ . A merge list m = m1 , . . . , mk then defines an encoding function tok↑ [m]: starting from c as a token-string over Σ (one token per character), it applies m1 , . . . , mk in order. The final token-string is our tokenised text. We write the tokeniser class defined by this procedure as TK↑ = tok↑ [m] | m ∈ (Σ+ × Σ+ )K . To select an element from this class, we then start from an empty merge list, and greedily add one merge per step to it, locally optimising an objective G:
c∈D
where pθ ’s parameters θ are themselves optimised to model this tokeniser’s text. This objective is likewise appealing, since log-likelihood is also the training objective of the language models for which these tokenisers are designed—so a log-likelihood optimal tokeniser would, by construction, lead to better models. Optimising log-likelihood directly, however, is intractable, as this objective requires fully training language models pθ for its evaluation. In practice, to make this objective tractable, we typically significantly restrict the class of models pθ . Here, we follow UnigramLM in restricting pθ to unigram language models. For a fixed encoding function tok, let nDs denote the count of token s in def P the tokenised corpus, and let N D = s∈S nDs be the total number of tokens. We then define pθ as pθ (s) =
|s| Y
pθ (st ),
t=1
pθ (s) =
nDs . ND
m⋆ = argmin G(tok↑ [m<k , m], D),
where tok↑ [m<k , m] denotes the encoding function obtained by applying the current merge list m<k followed by the candidate m. The selected merge m⋆ is then appended to the merge list. We refer to a candidate merge’s effect on the objective G(·,D) as its merge gain, and write it ∆s1 ,s2 . By contrast, the top-down procedure starts from a large candidate vocabulary S 0 , with |S 0 | ≫ K, and removes tokens until |S| = |Σ| + K. Notably, this procedure does not rely on merge lists, but instead commits to an objective-optimal encoding function tok⇒ [S], determined by the vocabulary alone. Under compression, tok⇒ [S](c) is the shortest valid segmentation of c using tokens from S. Under log-likelihood, it is instead the most probable segmentation of c under pθ .4 Top-down’s tokeniser class can then be written as: TK↓ = tok⇒ [S] | S ⊂ Σ+ , Σ ⊆ S, |S| = |Σ| + K . To select an item in this class, we then start from a large vocabulary S 0 , from which we iteratively prune the least critical tokens, quantified as the tokens whose removal has the least negative impact on the objective we’re optimizing for:
(4)
Concretely, we will thus use unigram loglikelihood as the objective here, as opposed to ‘full’ log-likelihood, and, for the rest of this paper, loglikelihood stands for unigram log-likelihood. 3.2
Search Procedures
Given one of these objectives and a fixed vocabulary budget K, we might expect a tokeniser to be chosen by directly optimising tokopt = argmin G(tok, D),
(6)
m∈Σ+ ×Σ+
(5)
tok∈TK
where TK denotes whichever class of tokenisers is under consideration. Unfortunately, this optimisation problem is computationally intractable; the compression variant is provably NP-hard (Kozma and Voderholzer, 2024; Whittington et al., 2025; Kastreva et al., 2026), and we suspect the loglikelihood variant to be as well. In practice, heuristic search procedures are therefore required. Such procedures specify both a restricted class of tokenisers and a strategy for selecting an element from that class. We focus on two standard search procedures: bottom-up construction and top-down pruning. The bottom-up procedure builds a tokeniser from the bottom up: the vocabulary starts as the alphabet Σ and grows one token at a time through merge operations. Given a merge m = ⟨s′ , s′′ ⟩,
s✗ = argmin G(tok⇒ [S k−1 \ {s}], D).
(7)
s∈S k−1 \Σ
Here, we index pruning steps by k, mirroring the bottom-up case. This yields S k = S k−1 \ {s✗ }. Importantly, to ensure every string remains encodable, alphabet tokens are never removed; pruning then continues until |S| = |Σ| + K.5 Analogously, we refer to a candidate deletion’s effect on the obG(·,D) jective as its deletion cost, written ∆s . 4
Given a fixed pθ , both cases can be computed efficiently. For log-likelihood, however, the parameters of pθ itself depend on tok, creating a circular definition. In practice, the two are estimated jointly as we explain in §4.2. 5 We note that, for efficiency reasons, in practice, multiple tokens are often pruned in batches.
3
4
Analysed Tokenisers: Old and New
Proof sketch. The full proof is in §A. Replacing an occurrence of the token-pair m = ⟨s1 , s2 ⟩ with the merged token s1 ◦ s2 saves one token. Further, the number of non-overlapping occurrences of a tokenpair is its number of possible merges. Merging the pair therefore shortens the corpus by exactly nDs1 ,s2 tokens, which is its gain under Gcomp .
Combining the objectives and search procedures above, we get a 2 × 2 design space for tokenisation algorithms (illustrated in Fig. 1). Existing tokeniser learning algorithms, namely BPE and UnigramLM, cover only two of these cells. Here, we introduce algorithms that instantiate the two other cells: BottomUpLL, a bottom-up likelihoodbased method, and TopDownComp, a top-down compression-based method.6 Before any of these methods can be run, however, a loose end remains. In the previous section, we describe the search procedures as greedy: at each step, it picks the merge m⋆ or deletion s✗ which (locally) optimises an objective G(·, D). It did not specify, however, how this selection is performed. Taken literally, computing the argmin operations in Eqs. (6) and (7) would require running the objective function G once per candidate to find the optimal one— a computationally impractical operation. Rather than recomputing G every time, most tokenisation algorithms work with incremental scores instead: m⋆ =
argmax ⟨s1 ,s2 ⟩∈Σ+ ×Σ+
s✗ =
argmin s∈S k−1 \Σ
G(·,D)
∆s1 ,s2
∆G(·,D) s
Lemma 1 gives the standard BPE merge rule: the compression-optimal merge is the most (nonoverlappingly) frequent token-pair. In practice, the token-pair counts nDs1 ,s2 are computed once and then updated incrementally after each merge, rather than recomputed from scratch (see §B), which allows us to run BPE efficiently. We can derive an analogous equivalence for BottomUpLL. Lemma 2. The change in log-likelihood due to merging a token-pair can be computed as:7 G (·,D)
∆s1ll,s2
+ (nDs2 − nDs1 ,s2 ) log(nDs2 − nDs1 ,s2 ) − nDs2 log nDs2 + nDs1 ,s2 log nDs1 ,s2
(8a)
− (N D − nDs1 ,s2 ) log(N D − nDs1 ,s2 ) + N D log N D .
(8b)
Proof sketch. The full proof is in §C. Note that, if a token changes from count n1 to count n2 , its contribution to the log-likelihood objective changes by: n2 log n2 − n1 log n1 . The lemma then follows trivially, noting that: (i) the old tokens s1 and s2 change from, e.g., frequency nDs1 to (nDs1 − nDs1 ,s2 ); (ii) the new token s1 ◦ s2 changes from frequency 0 to nDs1 ,s2 . Further, the total count of tokens serves as a normalisation factor in all tokens, and thus enters the log-likelihood with the opposite sign; its contribution changes from N D to N D − nDs1 ,s2 .
Bottom-up tokenisers: BPE and BottomUpLL
For a bottom-up method, each candidate is scored G(·,D) according to its merge gain ∆s1 ,s2 . We now show how this score can be computed efficiently for the two objectives, starting with compression.
BottomUpLL can thus also be implemented efficiently, maintaining local count statistics and updating only affected candidate scores after each merge. Interestingly, an analysis of the merge gain definition in Lemma 2 shows that, for a token-pair to be selected: (i) the pair should occur often enough to matter, but (ii) it should also be favoured when its tokens co-occur more systematically than expected from their individual frequencies.
Lemma 1. The change in compression due to merging a token-pair can be computed as: G
∆s1comp ,s2
(·,D)
= nDs1 ,s2
(10)
(nDs1 − nDs1 ,s2 ) log(nDs1 − nDs1 ,s2 ) − nDs1 log nDs1
Notably, these equations are equivalent to §3.2’s, as the pre-update objective values (e.g., G(tok↑ [m<k ], D)) do not depend on the candidates, and are thus constant. Each search procedure then derives a way to compute (or approximate) these values efficiently, as we show next. 4.1
=
(9)
where nDs1 ,s2 denotes the number of nonoverlapping ⟨s1 , s2 ⟩ sequences in D.
For the case s1 = s2 , the same calculation applies albeit with a modified count update: each merge consumes two occurrences of the same token s1 and thus its count is reduced by 2nD s1 ,s1 instead; other parts of the update remain unchanged. 7
6
Our new methods are closely related to, e.g., WordPiece or PathPiece. We discuss this prior work in detail in §5.
4
4.2
−log pθ (s) to the negative log-likelihood. Under the local replacement approximation, deleting s replaces it with srep s , which contributes − log pθ (srep s ). As the number of such occurrences is nDs , we get Eq. (11).
Top-down tokenisers: UnigramLM and TopDownComp
For top-down methods, each candidate’s score is G(·,D) given by the deletion cost ∆s . Unfortunately, G(·,D) this cost ∆s is non-trivial to compute. This is due to the nature of the encoding function tok⇒ [S] used by top-down algorithms. Unlike in the bottom-up case, deleting a token here can change the preferred segmentation of an entire character-string, not only the local decomposition of the deleted token.8 For the log-likelihood objective, the history gets worse. The segmentations produced by tok⇒ [S] depend on pθ , which is itself estimated from the token counts. Deleting a token changes those counts, which changes pθ , which in turn changes how strings are segmented, which again changes the counts. Computing a deletion’s exact cost would thus require running this loop to convergence for each candidate token. G(·,D) To approximate ∆s , we thus rely on a local replacement approximation: when scoring the deletion of s, we keep the rest of the current model fixed and estimate the loss by only directly replacing occurrences of s with an alternative segmentation under S \ {s}.9 For log-likelihood, this then yields the following result.
After each deletion, we update our encoding function tok⇒ [S k ] by re-estimating pθ . We do this by updating θ via an expectation–maximisation procedure, maximising the log-likelihood of D.11 This updated pθ defines the segmentations produced by tok⇒ , which we use to re-segment our dataset. We now present an analogous update for compression. Lemma 4. Under a local replacement approximation, the estimated change in compression due to deleting a token s ∈ S \ Σ can be approximated as: G
∆s comp
(·,D)
= nDs (|srep s | − 1) ,
(12)
where srep s is the compression-optimal replacement def of s after deletion: srep s = tok⇒ [S k−1 \ {s}](s). Proof sketch. The full proof is in §E. After deleting s, the local replacement uses |srep s | tokens instead, thus increasing the corpus length by |srep s |−1. There are nDs such occurrences. Updating this compression-based tokeniser after a deletion is easier than for log-likelihood. No parameters need to be estimated: the vocabulary S k alone determines the encoding function, so we simply re-segment the corpus under tok⇒ [S k ].
Lemma 3. Under a local replacement approximation, the estimated increase in the negative log-likelihood objective due to deleting a token s ∈ S \ Σ can be approximated as:10
5
ll (·,D) ≈ nDs (log pθ (s) − log pθ (srep ∆G s s )) , (11)
Connection to Prior Work
As mentioned above, the tokenisation learning algorithms we propose are not entirely without precedent, and related to prior methods like WordPiece and PathPiece. In this section, we discuss this connections in detail.
where pθ is the unigram model at step k − 1, and srep s is s’s log-probability–optimal replacement segdef mentation, i.e., srep s = tok⇒ [S k−1 \ {s}](s). Proof sketch. The full proof is in §D. Before deletion, each expected occurrence of s contributes
5.1
8
For example, under a compression objective, suppose S = Σ ∪ {abc, def , cdef }. Then, string abcdef is segmented as ⟨abc, def ⟩. If abc is deleted, however, the shortest segmentation under the reduced vocabulary becomes ⟨a, b, cdef ⟩, which also changes the previously used token def . 9 Note that this introduces an asymmetry between our two search procedures: the bottom-up merge gains in the previous section are exact, whereas the top-down deletion costs are only approximate. We emphasise that this asymmetry is not a design choice on our part, but an inherent property of topdown search procedures, being itself present in UnigramLM. We return to its implications in our Limitations section. 10 In practice, when computing this update, UnigramLM keeps segmentations latent and leverages pθ to compute nD s as the expected count of s, instead of its exact count under tok⇒ .
BottomUpLL and Likelihood-Guided Merging
As noted in §4.1, BottomUpLL favours pairs of tokens that are not only frequent, but which co-occur more often than chance. In fact, let the pointwise mutual information between two tokens be: pθ (s1 , s2 ) pθ (s1 ) pθ (s2 ) N D nDs1 ,s2 = log D D . ns1 ns2 def
PMIadj (s1 , s2 ) = log
11
(13a) (13b)
The details of this procedure fall out of our work’s scope; for an accessible derivation, see Meister (2026).
5
5.2
Relying on the PMI to operationalise this notion of more-often-than-chance co-occurrence, we can G (·,D) use a Taylor approximation of ∆s1ll,s2 to make this explanation of BottomUpLL explicit.
TopDownComp and Top-Down Compression
The closest prior method to TopDownComp is PathPiece (Schmidt et al., 2024), which likewise prunes a large initial vocabulary under a compression objective. The two differ in the deletion score: when scoring the removal of a token s, PathPiece also considers re-segmentation of other vocabulary tokens that contain s as a substring, whereas TopDownComp considers only s’s own local replacement. Adopting the PathPiece variant would change the algorithm in more ways than just the objective, so we keep TopDownComp as the direct compression counterpart of UnigramLM, differing from it in objective alone.
Lemma 5. Under a first-order Taylor approximation, the change in log-likelihood due to merging a token-pair can be approximated as: G (·,D) ∆s1ll,s2 ≈ nDs1 ,s2 PMIadj (s1 , s2 ) − 1 . (14) Proof sketch. The full proof is in §F. Starting from Lemma 2, apply a first-order Taylor expansion independently to each x log x term. Collecting the resulting terms returns the equation above. Eq. (14) is closely related to the objective of another famous bottom-up tokeniser, WordPiece. WordPiece’s definition, however, is far from unified and has shifted over time. As originally proposed by Schuster and Nakajima (2012), WordPiece selects the unit that most increases the likelihood of the data—i.e., using the same objective as BottomUpLL—but approximates the local objective, selecting multiple merges in parallel and only approximately updating their model pθ . WordPiece was later popularised by Wu et al. (2016), whose description suggests, in two consecutive sentences, optimising either a log-likelihood or a compression objective.12 Accordingly, the widely used HuggingFace implementation of WordPiece optimises for compression (Wolf et al., 2020). Finally, WordPiece is often described as merging the pair with the highest PMIadj (Schmidt et al., 2024; Lesci et al., 2025; Hugging Face, 2026), which relates to Eq. (14) but drops the nDs1 ,s2 factor. BottomUpLL is thus closest to the original WordPiece’s description, but differs from all existing versions of this method. Importantly, even closer to Eq. (14) is S-BPE (Vilar and Federico, 2021), which scores merges by a count-weighted PMI criterion. The two expressions are not identical, as S-BPE omits the −1 term, but are otherwise equivalent. We experiment with a tokenisation learning algorithm based on Lemma 5 in some of our experiments, which we then label as BottomUpLL ≈; when no such label is present, BottomUpLL refers to the method described by Lemma 2.
6
Experimental Setup
We will now compare our four tokenisers: BPE, BottomUpLL, TopDownComp, and UnigramLM. All four are trained with an identical preprocessing pipeline (NFC normalisation followed by a bytelevel pretokeniser using the GPT-2 regex) and on the same corpus, so that any difference between them stems only from the objective and the search procedure. §G gives the exact configuration under which we train our tokenisers. Full language model hyperparameter and architectural details are in §H. English setup. For English experiments, we train our tokenisers on a subset with approximately 2B tokens from FineWeb-Edu (Lozhkov et al., 2024), using vocabulary sizes of 8k, 32k, and 128k. We then again use FineWeb-Edu to train language models using these tokenisers, evaluating 100M, 300M, 500M, and 1B parameter models.13 Results for 100M-parameter models are averaged over three random seeds, while larger models use one run per configuration. Finally, unless otherwise stated, models are trained with a Chinchilla-style token budget of approximately 20× as many training tokens as model parameters. Multilingual setup. Our multilingual corpus contains 20B tokens across five languages: 10B English tokens from FineWeb-Edu (Lozhkov et al., 2024), and 2.5B tokens each of German, Spanish, Turkish, and Chinese from FineWeb2 (Penedo et al., 2025). We train our tokenisers on a 10% subsample of this corpus, using a single vocabulary size of 128k. We then train 1B-parameter language models on the full corpus.
12 “The wordpiece model is generated using a data-driven approach to maximize the language-model likelihood of the training data [...] Given a training corpus and a number of desired tokens D, the optimization problem is to select D wordpieces such that the resulting corpus is minimal in the number of wordpieces when segmented according to the chosen wordpiece model.” (Wu et al., 2016)
13
6
Full hyperparameter and architectural details are in §H.
Objective
Search
Gcomp ↓
Gll ↓
Entropy
Zipf α
BPT ↑
Tok Len
Vocab Util ↑
Cov. 50%
8k
BPE TopDownComp BottomUpLL UnigramLM
Gcomp Gcomp Gll Gll
bottom-up top-down bottom-up top-down
59,559,835 59,304,113 61,170,714 68,444,350
6.259 × 108 6.259 × 108 6.167 × 108 6.221 × 108
10.508 10.554 10.081 9.089
1.033 0.919 1.315 1.093
3.844 3.861 3.743 3.345
5.53 5.67 6.05 6.72
99.9% 99.3% 99.4% 99.3%
242 268 152 39
32k
BPE TopDownComp BottomUpLL UnigramLM
Gcomp Gcomp Gll Gll
bottom-up top-down bottom-up top-down
50,327,096 52,204,230 50,920,853 58,161,017
5.544 × 108 5.667 × 108 5.505 × 108 5.697 × 108
11.016 10.856 10.811 9.796
1.195 1.074 1.378 1.272
4.549 4.386 4.496 3.937
6.52 6.29 6.98 7.03
99.8% 99.8% 99.0% 99.8%
269 192 211 51
128k
BPE TopDownComp BottomUpLL UnigramLM
Gcomp Gcomp Gll Gll
bottom-up top-down bottom-up top-down
46,859,565 50,312,483 47,111,733 55,546,423
5.216 × 108 5.484 × 108 5.203 × 108 5.552 × 108
11.132 10.900 11.044 9.996
1.484 1.443 1.574 1.717
4.886 4.551 4.860 4.122
7.06 6.01 7.48 6.46
98.9% 99.8% 96.8% 97.1%
204 149 191 53
Vocab Tokeniser
Table 1: Intrinsic tokenisation results on a held-out test set (47,384 documents). Columns are defined in the Evaluation paragraph of §6. Tab. 5 in §J reports the multilingual counterpart of this table.
Evaluation. We report both extrinsic and intrinsic metrics. For extrinsic metrics, we report our language models’ bits per byte (BPB), computed on a held-out validation set, and minimal-pair grammatical accuracy, computed on BLiMP (Warstadt et al., 2020), MultiBLiMP (Jumelet et al., 2026), and ZhoBLiMP (Liu et al., 2026). For intrinsic metrics, we report Gcomp and Gll . We also report the unigram entropy of our tokenised corpus, its bytes per token (BPT), average vocab token len (Tok Len), vocabulary utilisation (Vocab Util), Zipf α, and Coverage 50%. Detailed definitions are in §I.
7
Results
7.1
Intrinsic Evaluation
This follows directly from the definitions: writing pθ (s) = nDs /N D , and noting that N D , the total number ofP tokens, is exactly GcompP (tok, D), we get − s pθ (s) log pθ (s) = − N1D s nDs log pθ (s) = Gll (tok, D)/N D . Looking at the entropy values in Tab. 1 we see a similar behaviour as before: for small vocabularies, entropy results align with the choice of tokenisation objective; for a larger vocabulary, however, topdown methods achieve consistently lower entropy. Future work should further investigate this relationship between objective and search procedure. Distributional Properties of Tokens. Tab. 1 also reports our tokenisers’ Zipf α and Coverage 50%, where Zipf α is the negated slope of a frequency vs. rank log-log curve, and Coverage 50% is the smallest ℓ such that the ℓ most frequent tokens together account for at least half of all token occurrences in our corpus. A larger Zipf α thus means that token frequency decreases more rapidly with rank, while lower Coverage 50% values indicate that token occurrences are concentrated among fewer token types. Fig. 2 shows corresponding frequency–rank curves. Within each search family, the likelihoodbased method induces a more concentrated tokenfrequency distribution than the compression-based method: BottomUpLL has higher Zipf α, lower entropy, and lower Coverage 50% than BPE, and UnigramLM shows the same pattern relative to TopDownComp. Thus, while the search procedure may dictate the values of Gcomp and Gll , the used objective is still visible in a tokenised corpus’ empirical token-frequency distribution.
Compression vs. Log-likelihood. Tab. 1 presents both the Gcomp and Gll achieved by our tokenisers. From this table, we can see that, for a small vocabulary (of 8k tokens), the compression and log-likelihood scores achieved by the different tokenisers seem to align with their objective function: BPE and TopDownComp achieve better compression, while UnigramLM and BottomUpLL achieve better log-likelihood. For larger vocabularies, however, this surprisingly does not hold, with the bottom-up tokenisers consistently achieving both better compression and log-likelihood, irrespective of their objective function. Another result of interest is with respect to a tokeniser’s entropy, which, intuitively, measures how evenly a tokeniser spreads the frequency of its tokens. This quantity has a strong relationship to our optimisation objectives, which can be seen when we rewrite it: X def Ent(tok, D) = − pθ (s) log pθ (s) (15a)
Other Intrinsic Metrics. Finally, Tab. 1 also presents our tokenisers’ vocabulary utilisation— i.e., the proportion of vocabulary items used at least once on a test set of 47,384 documents—as
s∈S
=
Gll (tok, D) Gcomp (tok, D)
(15b)
7
Frequency
8k vocabulary
32k vocabulary
128k vocabulary
BPE ( =1.03) TopDownComp ( =0.92)
BPE ( =1.19) TopDownComp ( =1.07)
BPE ( =1.48) TopDownComp ( =1.44)
BottomUpLL ( =1.32) UnigramLM ( =1.09)
109 107 105 103 101 100
101
102
Rank
BottomUpLL ( =1.38) UnigramLM ( =1.27)
104 100
103
101
102
Rank
103
104
BottomUpLL ( =1.57) UnigramLM ( =1.72)
100 101 102 103 104 105
Rank
Figure 2: Frequency–rank token distributions induced by each tokeniser on the held-out test set. Solid lines are empirical curves; dashed lines are the fitted power laws, whose negated slopes are the Zipf α values in Tab. 1.
--
82.3
81.7
50.2
41.8
90
BottomUpLL =
82.3
--
94.5
45.1
41.2
80
BottomUpLL
81.7
94.5
--
45.2
41.5
TopDownComp
50.2
45.1
45.2
--
60.7
UnigramLM
41.8
41.2
41.5
60.7
--
ity, defined as |S A ∩S B |/|S A |. Fig. 3 presents these results. From this table, we see that learned vocabularies cluster primarily by search procedure: e.g., bottom-up methods share substantially more tokens with each other than with top-down methods. This indicates that a tokeniser’s search procedure has a large effect on which tokens are included in its final vocabulary. Fig. 4 in §L shows the full set-overlap structure of all five vocabularies. Furthermore, per-example qualitative segmentations for the four tokenisers are shown in §M.
Vocabulary overlap (\%)
BPE
70 60 50
LM mp BPE pLL = pLL nCo nigram U U w m m o U D to to Top Bot Bot
7.2
Extrinsic Evaluation
BPB. Tabs. 2 and 3 present extrinsic results for both the English and multilingual settings. From these tables, we can see that bottom-up tokenisers consistently achieve lower BPB scores than top-down. This holds true for all our experimental conditions, with the only exception of the English 300M models at 32k vocabulary, where TopDownComp outperforms BPE by a negligible margin (0.0003 BPB); the likelihood-based pair (BottomUpLL vs. UnigramLM) favours bottom-up in every setting.14 Comparing tokenisers within a single search procedure, we see that the choice of objective is still relevant, albeit less strongly. Compression-based methods tend to outperform log-likelihood; but there are several exceptions where BottomUpLL outperforms all other methods.
Figure 3: Pairwise vocabulary overlap at 128k vocabulary size. BottomUpLL = denotes the exact variant of this method, which scores merges with Lemma 2, while BottomUpLL ≈ denotes the approximate variant, which uses the PMI-based approximation of Lemma 5. See Tab. 6 in §J for a multilingual counterpart of this table.
well as the average length of the tokens in their vocabularies. Vocabulary utilisation is close to 100% at 8k and 32k, but at 128k, likelihood-based tokenisers have more unused tokens; §K traces this to the intermediate tokens that BottomUpLL creates during merging and then never uses again. Token length behaves differently across vocabulary sizes: at small vocabulary sizes, top-down methods present longer tokens, as they can retain these tokens from the initial seed vocabulary; at larger vocabulary sizes, though, bottom-up methods present longer tokens instead, as they can build these tokens from scratch through successive merges. Interestingly, across both search procedures, the likelihood-based tokenisers have longer tokens than their compression-based counterparts.
Minimal-pair accuracy. Tabs. 2 and 3 also present scores on a minimal-pair grammaticality task, for both the English and multilingual settings. Notably, these results do not show the same clear preference as BPB for bottom-up over topdown. In fact, in the English setting, top-down methods often outperform the bottom-up ones, 14
Because several of these differences are small, we additionally verify their significance with a paired document-level bootstrap over the evaluation set, which confirms the statistical significance of each of these comparisons (see details in §N).
Vocabulary Composition. We now move on to analysing the composition of our tokenisers’ vocabularies. To this end, we compute their similar8
100M
300M
500M
1B
Objective
Search
BLiMP ↑
BPB ↓
BLiMP ↑
BPB ↓
BLiMP ↑
BPB ↓
BLiMP ↑
BPB ↓
8k
BPE TopDownComp BottomUpLL UnigramLM
Gcomp Gcomp Gll Gll
bottom-up top-down bottom-up top-down
.686 ± 6e-3 .687 ± 4e-3 .703 ± 8e-3 .698 ± 5e-3
1.0736 ± 2e-4 1.0750 ± 8e-4 1.0715 ± 6e-4 1.0819 ± 4e-4
.7707 .7699 .7841 .7769
.8739 .8758 .8727 .8758
.7744 .7938 .7951 .7676
.8435 .8441 .8420 .8472
– – – –
– – – –
32k
BPE TopDownComp BottomUpLL UnigramLM
Gcomp Gcomp Gll Gll
bottom-up top-down bottom-up top-down
.714 ± 8e-3 .727 ± 2e-2 .717 ± 7e-3 .719 ± 8e-3
1.0392 ± 5e-4 1.0394 ± 3e-4 1.0374 ± 1e-4 1.0441 ± 9e-4
.7904 .7895 .7827 .7776
.8584 .8581 .8564 .8610
.7958 .7986 .7899 .8015
.8290 .8307 .8281 .8337
– – – –
– – – –
128k
BPE TopDownComp BottomUpLL UnigramLM
Gcomp Gcomp Gll Gll
bottom-up top-down bottom-up top-down
.740 ± 4e-3 .740 ± 8e-3 .725 ± 6e-3 .738 ± 7e-3
1.0138 ± 4e-4 1.0172 ± 4e-4 1.0149 ± 9e-4 1.0298 ± 8e-4
.797 .797 .792 .799
.8462 .8492 .8467 .8547
.813 .815 .798 .803
.8210 .8226 .8207 .8283
.805 .816 .799 .818
.7790 ± 4e-4 .7816 ± 3e-4 .7803 ± 26e-4 .7872 ± 1e-4
Vocab Tokeniser
Table 2: Extrinsic tokenisation results for language models trained in English. Cells marked “–” were not run; 1B models were trained only at 128k vocabulary. 100M results are averaged over three random seeds; for the 1B models, BPB is likewise averaged over three seeds (42, 43, 44), while BLiMP uses a single seed. Values following ± are standard deviations across seeds. Lower is better for BPB; higher is better for BLiMP. Minimal-pair accuracy ↑ Tokeniser
Objective
Search
BPE TopDownComp BottomUpLL UnigramLM
Gcomp Gcomp Gll Gll
bottom-up top-down bottom-up top-down
BPB ↓
BLiMP ↑
eng
deu
spa
tur
cmn
eng
deu
spa
tur
cmn
.812 .808 .808 .803
.974 .969 .970 .973
.955 .966 .952 .964
.958 .956 .950 .959
.890 .853 .873 .897
.799 .718 .803 .728
.8080 .8276 .8082 .8311
.9426 .9711 .9416 .9683
.9025 .9284 .9030 .9303
.8936 .9260 .8929 .9252
1.2464 1.3430 1.2436 1.3575
Table 3: Extrinsic tokenisation results for 1B parameter models trained in a multilingual setting. Minimal-pair accuracy is evaluated on BLiMP (Warstadt et al., 2020), MultiBLiMP (eng, deu, spa, tur; Jumelet et al., 2026), and ZhoBLiMP (cmn; Liu et al., 2026). Lower is better for BPB; higher is better for minimal-pair accuracy.
with UnigramLM outperforming BottomUpLL and TopDownComp outperforming BPE for the 1B models. In the multilingual setting, no consistent pattern arises either, and all tokenisers perform best in at least one language. Our results in German, Spanish, and Turkish, however, suggest that topdown methods may be helpful for morphologically rich languages. More broadly, our multilingual minimal-pair accuracy results suggest different tokenisers induce different inductive biases, which will in turn be uniquely suited to different languages; we leave this direction to future work.
8
bits-per-byte. Our intrinsic evaluations also highlighted a surprising pattern: bottom-up tokenisers produced both more compressed and higher loglikelihood token-strings than top-down tokenisers, independent of the used objective function. The used objective still affects the resulting tokeniser, though, with log-likelihood objective leaving a clear impact on the empirical rank–frequency distribution of its tokens. Overall, our results show that a tokeniser’s effect on language modelling cannot be explained by the objective alone, and that the used search procedure is an important component of tokeniser design. We hope future work will explore the impact of other optimisation objectives and search procedures15 in language modelling.
Conclusion
Our paper disentangles two important design choices in tokeniser learning algorithms: the objective used to score a tokeniser and the search procedure used to optimise it. We analyse two objectives (compression vs. log-likelihood) and search procedures (bottom-up vs. top-down), introducing two new tokenisers in the process: BottomUpLL and TopDownComp. In nearly all experimental conditions, language models trained with bottom-up tokenisers outperformed top-down ones in terms of
Limitations We list a few limitations with our study here. Scale. First, we only train language models up to 1B parameters, and results could shift for larger models or longer training horizons. 15
Investigating the search procedures of, e.g.,Tempus et al. (2026) or Chizhov et al. (2024).
9
Languages. Second, our multilingual experiments cover five selected languages: English, German, Spanish, Turkish, and Chinese. Four of these use the Latin script and all are relatively highresource, so our multilingual results should be read as applying to these five languages rather than to multilingual tokenisation in general. How our findings transfer to low-resource languages, and to scripts with markedly different orthographic conventions, remains an open question that we leave to future work.
measure other downstream task performance, reasoning ability, or long-context behaviour; how our models perform in those different settings is thus left open.
Acknowledgements We thank Philip Whittington for helpful discussions and feedback throughout this project, and the anonymous reviewers for their constructive comments. This work was supported as part of the “Swiss AI initiative” by a grant from the Swiss National Supercomputing Centre (CSCS) under project ID a0229 on Alps.
Single seed at scale. Third, for computational reasons, the 300M and 500M models are trained with a single seed per configuration, as are the multilingual 1B models; the 100M and English 1B models are averaged over three seeds; small differences in results across tokenisers should thus be interpreted with caution.
References Pavel Chizhov, Catherine Arnett, Elizaveta Korotkova, and Ivan P. Yamshchikov. 2024. BPE gets picky: Efficient vocabulary refinement during tokenizer training. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 16587–16604, Miami, Florida, USA. Association for Computational Linguistics.
Tokeniser-training corpus. Fourth, in all our experiments, each tokeniser is trained on the same corpus as the language model trained on top of it. We thus do not analyse the impact of training models on data that differ in domain or style from its tokeniser.
Philip Gage. 1994. A new algorithm for data compression. C Users Journal, 12(2):23–38. Hugging Face. 2026. WordPiece tokenization. Chapter 6.6 of the Hugging Face LLM Course, https://huggingface.co/learn/llm-course/ en/chapter6/6. Accessed August 2026.
Approximate top-down deletion scores. Fifth, as discussed in §4.2, top-down deletion costs rely on the local replacement approximation, whereas bottom-up merge gains are exact for the current step. We asses the impact of this approximation by, at a small scale, training tokenisers for which we compute exact deletion scoring. We find that the local-replacement-approximation tokenisers present an 81.5% vocabulary overlap with these exact ones. Whether this holds at the vocabulary sizes used in our main experiments, however, remains open. A second approximation we rely on for top-down methods is that we prune multiple tokens per round rather than one at a time. We assess the impact of this approximation by retraining the top-down tokenisers with pruning rates of 1% and 0.1% of the vocabulary per round, instead of the 10% used in our main experiments: the resulting vocabularies overlap with the 10% ones by over 97% for UnigramLM and over 99% for TopDownComp, suggesting that this approximation has a limited effect on the learned vocabulary. Details for both experiments are in §O.
Jaap Jumelet, Leonie Weissweiler, Joakim Nivre, and Arianna Bisazza. 2026. MultiBLiMP 1.0: A massively multilingual benchmark of linguistic minimal pairs. Transactions of the Association for Computational Linguistics, 14:193–216. Violeta Kastreva, Philip Whittington, Dennis Komm, and Tiago Pimentel. 2026. Tokenisation over bounded alphabets is hard. In The Fourteenth International Conference on Learning Representations. László Kozma and Johannes Voderholzer. 2024. Theoretical analysis of byte-pair encoding. arXiv preprint arXiv:2411.08671. Taku Kudo. 2018. Subword regularization: Improving neural network translation models with multiple subword candidates. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 66–75. Pietro Lesci, Clara Meister, Thomas Hofmann, Andreas Vlachos, and Tiago Pimentel. 2025. Causal estimation of tokenisation bias. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 28325– 28340, Vienna, Austria. Association for Computational Linguistics.
Evaluation. Finally, we evaluate models with BPB and minimal-pair grammatical benchmarks (BLiMP, MultiBLiMP, ZhoBLiMP). We do not 10
Yikang Liu, Yeting Shen, Hongao Zhu, Lilong Xu, Zhiheng Qian, Siyuan Song, Kejia Zhang, Jialong Tang, Pei Zhang, Baosong Yang, Rui Wang, and Hai Hu. 2026. A systematic assessment of language models with linguistic minimal pairs in Chinese. Transactions of the Association for Computational Linguistics, 14:755–771.
David Vilar and Marcello Federico. 2021. A statistical extension of byte-pair encoding. In Proceedings of the 18th International Conference on Spoken Language Translation (IWSLT 2021), pages 263–275. Alex Warstadt, Alicia Parrish, Haokun Liu, Anhad Mohananey, Wei Peng, Sheng-Fu Wang, and Samuel R. Bowman. 2020. BLiMP: The benchmark of linguistic minimal pairs for English. Transactions of the Association for Computational Linguistics, 8:377– 392.
Anton Lozhkov, Loubna Ben Allal, Leandro von Werra, and Thomas Wolf. 2024. FineWeb-Edu: the finest collection of educational content. Clara Meister. 2026. UnigramLM: An attempt at writing the missing manual. In Proceedings of the Fourteenth International Conference on Learning Representations. ICLR 2026 Blogpost Track.
Philip Whittington, Gregor Bachmann, and Tiago Pimentel. 2025. Tokenisation is NP-complete. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 28133–28153.
OpenAI, Sandhini Agarwal, Lama Ahmad, Jason Ai, Sam Altman, Andy Applebaum, Edwin Arbus, Rahul K. Arora, Yu Bai, Bowen Baker, Haiming Bao, Boaz Barak, Ally Bennett, Tyler Bertao, Nivedita Brett, Eugene Brevdo, Greg Brockman, Sebastien Bubeck, Che Chang, and 107 others. 2025. gptoss-120b & gpt-oss-20b model card. arXiv preprint arXiv:2508.10925.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, and 3 others. 2020. Transformers: State-of-the-art natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 38–45, Online. Association for Computational Linguistics.
Guilherme Penedo, Hynek Kydlíček, Vinko Sabolčec, Bettina Messmer, Negar Foroutan, Amir Hossein Kargaran, Colin Raffel, Martin Jaggi, Leandro Von Werra, and Thomas Wolf. 2025. FineWeb2: One pipeline to scale them all – adapting pre-training data processing to every language. arXiv preprint arXiv:2506.20920.
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V. Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin Johnson, Xiaobing Liu, Łukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, and 12 others. 2016. Google’s neural machine translation system: Bridging the gap between human and machine translation. arXiv preprint arXiv:1609.08144.
Craig W Schmidt, Varshini Reddy, Haoran Zhang, Alec Alameddine, Omri Uzan, Yuval Pinter, and Chris Tanner. 2024. Tokenization is more than compression. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 678–702. Mike Schuster and Kaisuke Nakajima. 2012. Japanese and Korean voice search. In 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5149–5152. Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016. Neural machine translation of rare words with subword units. In Proceedings of the 54th annual meeting of the association for computational linguistics (volume 1: long papers), pages 1715–1725. Kimi Team, Tongtong Bai, Yifan Bai, Yiping Bao, S. H. Cai, Yuan Cao, Ziwei Chai, Y. Charles, H. S. Che, Cheng Chen, Guanduo Chen, Huarong Chen, Jia Chen, Jianlong Chen, Jun Chen, Kefan Chen, Liang Chen, Ruijue Chen, Xinhao Chen, and 318 others. 2026. Kimi K2.5: Visual agentic intelligence. arXiv preprint arXiv:2602.02276. Qwen Team. 2026. Qwen3.5-Omni technical report. arXiv preprint arXiv:2604.15804. Jan Tempus, Philip Whittington, Craig W. Schmidt, Dennis Komm, and Tiago Pimentel. 2026. Tokenisation via convex relaxations. arXiv preprint arXiv:2605.22821.
11
A
Proof of Lemma 1
which maps each token-pair to the word types in which that pair currently occurs. We also maintain a reverse index from tokens to the token-pairs containing them, which allows us to identify which candidate scores may be affected after a merge. When a merge m = ⟨s1 , s2 ⟩ is selected, write
Lemma 1. The change in compression due to merging a token-pair can be computed as: G
∆s1comp ,s2
(·,D)
= nDs1 ,s2
(9)
where nDs1 ,s2 denotes the number of nonoverlapping ⟨s1 , s2 ⟩ sequences in D.
def
snew = s1 ◦ s2 .
Proof. To prove this is the case, first note that replacing a token-pair m = ⟨s1 , s2 ⟩ with merged token s1 ◦ s2 saves exactly 1 token. As the number of non-overlapping occurrences of a token-pair is also the number of possible merges, it is equivalent to the compression this token-pair would achieve:
Each affected word type is scanned through its linked token sequence, and non-overlapping occurrences of ⟨s1 , s2 ⟩ are replaced by snew . The non-overlap condition is enforced during this scan: once an occurrence has been merged, the scan skips over the newly created token, so overlapping occurrences of the same pair are not counted twice. Locally, an occurrence in context
G(tok↑ [m<k ], D) − G(tok↑ [m<k ◦ ⟨s1 , s2 ⟩], D) = nDs1 ,s2 .
(16)
We can now trivially conclude the proof: m⋆ = argmin G(tok↑ [m<k ◦ m], D)
(17a)
⟨sℓ , s1 , s2 , sr ⟩
(19)
⟨sℓ , snew , sr ⟩,
(20)
is replaced by
m∈Σ+ ×Σ+
= argmax −G(tok↑ [m<k ◦ m], D) (17b) m∈Σ+ ×Σ+
= argmax G(tok↑ [m<k ], D)
where sℓ and sr denote the immediate left and right neighbours, if they exist. Therefore, only tokenpairs in this local neighbourhood can change. The old token-pairs
(17c)
m∈Σ+ ×Σ+
− G(tok↑ [m<k ◦ m], D) =
argmax ⟨s1 ,s2 ⟩∈Σ+ ×Σ+
nDs1 ,s2 .
(17d)
⟨sℓ , s1 ⟩,
This concludes the proof.
B
⟨s2 , sr ⟩
(21)
are removed, and the new token-pairs
Updating Counts in bottom-up Procedures
⟨sℓ , snew ⟩,
Both BPE and BottomUpLL repeatedly select a token-pair based on its merge gain on the current tokenised corpus. A naive implementation would recompute token and token-pair counts after each merge, which is expensive on large corpora. Instead, our implementation maintains these counts incrementally and updates only the parts of the corpus affected by the selected merge. The corpus is represented as a collection of unique word types, each with an associated frequency. Each word type stores its current tokenisation using a linked token structure: every token stores pointers to its predecessor and successor, allowing merges to be applied locally without reconstructing the full token string. We maintain a mapping pair_to_words : ⟨s1 , s2 ⟩
⟨s1 , s2 ⟩,
⟨snew , sr ⟩
(22)
are added. Boundary cases are handled by omitting updates involving missing neighbours. For one merged occurrence, the affected pair counts are updated as nDsℓ ,s1 ← nDsℓ ,s1 − 1, n n
D s1 ,s2
D s2 ,sr
− 1,
(23b)
D s2 ,sr
− 1,
(23c)
←n ←n
nDsℓ ,snew ← nDsℓ ,snew + 1, n
D snew ,sr
(23a)
D s1 ,s2
D snew ,sr
←n
+ 1.
(23d) (23e)
When word types have frequencies, these increments and decrements are weighted by the corresponding word-type frequency. For BottomUpLL, we also update unigram counts, since the merge score in Lemma 2 depends on both token counts and pair counts. If nDs1 ,s2
(18)
7→ {word types containing ⟨s1 , s2 ⟩}, 12
denotes the frequency-weighted number of nonoverlapping occurrences of the selected pair that are actually merged, then the unigram counts are updated as nDs1 ← nDs1 − nDs1 ,s2 , n
D s2
D s2
←n
−n
D s1 ,s2
,
nDsnew ← nDs1 ,s2 , D
D
N ←N −n
its corpus count. Under the unigram token model, the empirical probability of s̃ is nDs̃ . (25) ND Therefore, the corpus log-likelihood before applying the merge is X Lbefore = nDs̃ log pθ (s̃) (26a) pθ (s̃) =
(24a) (24b) (24c)
D s1 ,s2
.
s̃
(24d)
= =
=
(26b)
nDs̃ log nDs̃ − N D log N D .
(26c)
Now consider merging the token-pair ⟨s1 , s2 ⟩ into the new token s1 ◦ s2 . For readability, write def
κ = nDs1 ,s2 ,
(27)
Assuming s1 ̸= s2 , applying this merge changes only the counts of s1 , s2 , and the new token s1 ◦ s2 . Specifically, nDs1 7→ nDs1 − κ, D s2
7→ n
D s1 ◦s2
7→ κ.
n n
D s2
− κ,
(28a) (28b) (28c)
All other token counts remain unchanged. Since each merged occurrence replaces two tokens by one token, the total token count changes from N D to N D − κ. The log-likelihood after the merge is therefore X (29) Lafter = nDs̃ log nDs̃ s̃∈{s / 1 ,s2 ,s1 ◦s2 }
+ nDs1 − κ log nDs1 − κ + nDs2 − κ log nDs2 − κ + κ log κ − (N D − κ) log(N D − κ). and the log-likelihood change due to the merge is
Lemma 2. The change in log-likelihood due to merging a token-pair can be computed as: G (·,D)
X
nDs̃ ND
s̃
Proof of Lemma 2
∆s1ll,s2
nDs̃ log
s̃
For BPE, the affected candidate scores are simply the updated pair counts, as in Lemma 1. For BottomUpLL, affected candidate scores are then recomputed using the local likelihood-change expression in Lemma 2. The priority queue of candidate token-pairs is maintained lazily. After a merge, the selected pair is removed from the pair-to-word index, affected reverse-index entries are updated, and affected token-pairs are pushed back onto the heap with fresh scores. Old heap entries are not removed immediately. Instead, stale entries are rejected when popped: the implementation checks the current count and score, and discards the heap entry if it no longer matches the current state. The heap is also periodically rebuilt to control the accumulation of stale entries. This gives an incremental implementation in which the cost of a merge is proportional to the number of affected word types and local token updates, plus the cost of heap maintenance. In practice, this is much cheaper than recomputing all token and token-pair counts over the full corpus after every merge.
C
X
G (·,D)
∆s1ll,s2
(10)
= Lafter − Lbefore .
(30)
Substituting Eqs. (26c) and (30), all unchanged token-count terms cancel, leaving G (·,D) ∆s1ll,s2 = nDs1 − κ log nDs1 − κ (31)
(nDs1 − nDs1 ,s2 ) log(nDs1 − nDs1 ,s2 ) − nDs1 log nDs1 + (nDs2 − nDs1 ,s2 ) log(nDs2 − nDs1 ,s2 ) − nDs2 log nDs2 + nDs1 ,s2 log nDs1 ,s2 − (N D − nDs1 ,s2 ) log(N D − nDs1 ,s2 ) + N D log N D .
− nDs1 log nDs1 + nDs2 − κ log nDs2 − κ − nDs2 log nDs2
Proof. We prove the result by explicitly writing the corpus log-likelihood before and after applying the merge. Let the current tokenised corpus contain N D tokens in total. For each token s̃, let nDs̃ denote
+ κ log κ − (N D − κ) log(N D − κ) + N D log N D . which completes the proof. 13
D
Proof of Lemma 3
Multiplying this per-occurrence increase by the expected number of occurrences nDs gives
Lemma 3. Under a local replacement approximation, the estimated increase in the negative log-likelihood objective due to deleting a token s ∈ S \ Σ can be approximated as:
ll (·,D) ∆G ≈ nDs (log pθ (s) − log pθ (srep s s )) . (37)
This proves the stated local approximation.
E
ll (·,D) ∆G ≈ nDs (log pθ (s) − log pθ (srep s s )) , (11)
Lemma 4. Under a local replacement approximation, the estimated change in compression due to deleting a token s ∈ S \ Σ can be approximated as:
where pθ is the unigram model at step k − 1, and srep s is s’s log-probability–optimal replacement segdef mentation, i.e., srep s = tok⇒ [S k−1 \ {s}](s).
G
∆s comp
Proof. We prove the result under the local replacement approximation stated in the lemma. That is, when scoring the deletion of s, we keep the current token probabilities pθ fixed, keep all other segmentation decisions fixed, and approximate the effect of deletion by replacing each expected occurrence of s with a replacement segmentation under S \ {s}. For UnigramLM, token usage is measured by expected counts under the current posterior over valid segmentations. Thus, nDs is the expected number of times s is used in the corpus. Before deleting s, each such expected occurrence contributes − log pθ (s)
def
tok⇒ [S](c) = argmin |s|. s∈S ∗ ◦ c=s
(12)
(38)
Now consider deleting a token s ∈ S \ Σ. Before deletion, each current occurrence of s contributes exactly one token to the corpus token count. Therefore, the total contribution of all current occurrences of s before deletion is
(32)
Cbefore (s) = nDs .
(39)
After deleting s, the token s can no longer appear as a single token. Under the local replacement calculation, each current occurrence of s is independently replaced by its shortest decomposition under the reduced vocabulary S \{s}, denoted srep s :
(33)
′ srep s = argmin |s |.
(40)
s′ ∈(S\{s})∗ ◦ s=s′
Since pθ is a unigram model, the probability of this replacement token-string is Y pθ (srep ) = pθ (s̃). (34) s
Thus, under this local replacement calculation, each previous occurrence of s contributes |srep s | tokens instead of one token. The total contribution of these occurrences after deletion is
s̃∈srep s
After replacement, each expected occurrence therefore contributes
Cafter (s) = nDs |srep s |.
(41)
Therefore, the estimated increase in corpus length caused by locally replacing all current occurrences of s is
(35)
to the negative log-likelihood objective. Hence, the estimated increase in negative loglikelihood for one expected occurrence of s is − log pθ (srep s ) − − log pθ (s) = log pθ (s) − log pθ (srep s ).
= nDs (|srep s | − 1) ,
Proof. Let S be the current vocabulary, and suppose the corpus has already been segmented using the TopDownComp encoding rule:
s̃∈(S\{s})∗ ◦ s=s̃
− log pθ (srep s )
(·,D)
where srep s is the compression-optimal replacement def of s after deletion: srep s = tok⇒ [S k−1 \ {s}](s).
to the negative log-likelihood objective. After deleting s, the token can no longer be used as a single token. Under the local replacement approximation, each occurrence of s is replaced by the highest-probability valid segmentation of the same string under the reduced vocabulary: srep s = argmax pθ (s̃).
Proof of Lemma 4
G
∆s comp
(·,D)
= Cafter (s) − Cbefore (s)
(42a)
D = ns |srep s | − ns = nDs (|srep s | − 1) .
(42b)
D
(36)
which completes this proof. 14
(42c)
F
G
Proof of Lemma 5
All four tokenisers use the same preprocessing pipeline, implemented with the HuggingFace tokenizers library. Text is normalised with NFC, and pretokenised with a byte-level pretokeniser, ByteLevel(add_prefix_space=False, trim_offsets=True, use_regex=True), which applies the GPT-2 pretokenisation regex. The corresponding decoder and post-processor are:
Lemma 5. Under a first-order Taylor approximation, the change in log-likelihood due to merging a token-pair can be approximated as: G (·,D)
∆s1ll,s2
≈ nDs1 ,s2 PMIadj (s1 , s2 ) − 1 . (14) def
Proof. As in §C, we write κ = nDs1 ,s2 . Starting from Eq. (31), we have G (·,D)
∆s1ll,s2
=
ByteLevel(add_prefix_space=True,
(43)
trim_offsets=True, use_regex=True)
nDs1 − κ log nDs1 − κ − nDs1 log nDs1 + nDs2 − κ log nDs2 − κ − nDs2 log nDs2
ByteLevel(add_prefix_space=True, trim_offsets=False, use_regex=True)
+ κ log κ
(44b)
respectively. This choice is deliberately standard. Because pretokenisation strongly constrains which token boundaries a tokeniser can learn, holding it fixed is necessary for the objective and the search procedure to be the only varying factors in our comparison. We use byte-level fallback throughout, so every string remains encodable and no <unk> tokens are required.
′
= f (x) − κf (x)
(44c)
H
= x log x − κ(log x + 1)
(44d)
All language models follow a Llama-style decoderonly architecture. Tab. 4 summarises the per-size architectural settings. All models use SiLU activations, grouped-query attention with separate K/V head counts, RMSNorm, and rotary positional embeddings (RoPE, θ = 10,000).
− (N D − κ) log(N D − κ) + N D log N D . Now, define f (a) = a log a, which implies f ′ (a) = log a + 1. A first-order Taylor expansion of f (a) around point x gives f (a) ≈ f (x) + (a − x)f ′ (x)
(44a) ′
f (x − κ) ≈ f (x) + (x − κ − x)f (x)
This approximation is accurate whenever κ ≪ x: the neglected remainder is 12 κ2 f ′′ (ξ) = O(κ2 /x), which is small relative to the retained term κ(log x + 1) exactly in that regime. Now, choosing x = nDs1 , we get = nDs1 − κ log nDs1 − κ D s1
≈ n log n
D s1
− κ log n
D s1
(45a)
+1 .
which implies nDs1 − κ log nDs1 − κ − nDs1 log nDs1 ≈ −κ log n
D s1
(45b)
(46) +1 .
Training setup. All models are trained at sequence length 2,048 in bf16-mixed precision with FlashAttention 2. The per-device batch size is 32, and gradient accumulation is adjusted per model size to match a fixed effective batch size. Following Chinchilla-optimal scaling, each model is trained on roughly 20× its parameter count in tokens. Training uses a single fixed random seed (42), except for the 100M setting and the English 1B models at 128k vocabulary, where we train three seeds (42, 43, 44) per configuration. All experiments are implemented in PyTorch with our opensource training stack.
With similar results for x = nDs2 and x = N D . Substituting these terms into Eq. (43), we get G (·,D)
≈ −κ log nDs1 + 1 − κ log nDs2 + 1 + κ log κ + κ (log N D + 1) ND κ = κ log D D − 1 ns1 ns2 = κ PMIadj (s1 , s2 ) − 1 .
Hyperparameters and Architecture
Optimisation. We train models with AdamW using learning rate 3 × 10−4 , β1 = 0.9, β2 = 0.95, weight decay 0.1, and a maximum gradient norm of 1.0. The learning-rate schedule is warmup–stable– decay with 2,000 warmup steps, a stable phase, and 10,000 linear-decay steps, ending with a final learning rate of 10% of its peak value.
f (nDs1 − κ)
∆s1ll,s2
Tokeniser Training Details
(47a) (47b) (47c)
which completes the proof. 15
Size
Hidden
Intermediate
Heads
KV heads
Layers
Tied
100M 300M 500M 1B
576 960 1280 2048
1,536 2,560 3,456 5,632
9 15 16 32
3 5 4 4
30 32 26 22
✓ ✓ ✓ ✓
Table 4: Per-size architecture for the Llama-style language models. “Tied” denotes weight tying between input and output embeddings.
I
Gll = H · N D , where lower suggests a better fit under the empirical unigram model. Zipf α is the negated slope of a log-log OLS fit of frequency vs. rank, with tokens sorted in descending frequency; higher α means a steeper distribution. Coverage 50% is the smallest ℓ such that the ℓ most frequent tokens together account for at least half of all token occurrences in D; smaller ℓ means usage is concentrated on a small core.
Detailed Metric Definitions
This section gives precise definitions for every metric used in the paper. Let D denote a held-out corpus, Nbytes its size in UTF-8 bytes, and N D the number of tokens produced by a given tokeniser on D. Extrinsic. We evaluate models based on two extrinsic metrics. Bits per byte (BPB), defined as − log2 Pθ (D)/Nbytes : the trained model’s negative log-likelihood on D, normalised by the byte count. Lower is better. Because the denominator is a property of the raw text (and hence identical across tokenisers), BPB is directly comparable across tokenisers; token-level perplexity, by contrast, is biased against tokenisers that produce shorter sequences. Minimal-pair grammatical accuracy, which, for an acceptable–unacceptable sentence pair, evaluates the model as correct if it assigns higher per-token log-probability to the acceptable sentence. It than averages this values across a corpus of such pairs. We use BLiMP (Warstadt et al., 2020) for English, MultiBLiMP (Jumelet et al., 2026) for English, German, Spanish, and Turkish, and ZhoBLiMP (Liu et al., 2026) for Chinese. For this metric, higher is better.
Vocabulary overlap. Finally, we also compute vocabulary overlap between tokenisers. For two tokenisers A and B, their overlap is measured as |S A ∩S B |/|S A |, where S A and S B are their learned vocabularies. This measure is symmetric for tokenisers with equal vocabulary size.
J
English vs. Multilingual Intrinsic Comparison
This appendix reports the multilingual counterpart of Tab. 1 and Fig. 3, using the multilingual tokenisers and the concatenation of the five per-language test splits (220,423 documents: 47,384 English, 54,969 German, 54,489 Spanish, 41,986 Turkish, 21,595 Chinese). Compression gaps widen in the multilingual setting. Tab. 5 shows each tokenisers compression in both English-only and multilingual corpora. In English, UnigramLM produces 18.5% more tokens than BPE and TopDownComp 7.4% more. In multilingual, the top-down gap roughly doubles: UnigramLM +39.6%, TopDownComp +26.5%. BottomUpLL remains close to BPE in both settings (+0.5% in English, +0.9% in multilingual). The bottom-up vs. top-down separation observed in the main text therefore grows under a shared multilingual vocabulary budget.
Intrinsic. We evaluate models on 5 types of intrinsic metrics. Compression is Gcomp = N D , i.e., the corpus token count, where lower means more compact. Bytes per token (BPT) is defined as Nbytes /N D , the average number of source bytes captured by one token, where higher means more compact. Vocab Util is the fraction of vocabulary IDs that appear at least once in D. Token length (Tok Len) is the average character length of the entries in the learned vocabulary, with each entry counted once, unweighted by corpus frequency. P (Unigram) Entropy is defined here as H = − s pθ (s) log2 pθ (s), where pθ (s) is a unigram language model trained on token counts. Unigram log-likelihood objective is
Distributional shape changes with the evaluation corpus. Tab. 5 reports the full intrinsic statistics in both settings. All four token distributions flatten in the multilingual setting: Zipf α values 16
Setting
Tokeniser
Objective
Search
Gcomp ↓
Gll ↓
Entropy
Zipf α
BPT ↑
Tok Len
Vocab Util ↑
Coverage 50%
English
BPE TopDownComp BottomUpLL UnigramLM
Gcomp Gcomp Gll Gll
bottom-up top-down bottom-up top-down
46,859,565 50,312,483 47,111,733 55,546,423
5.216 × 108 5.484 × 108 5.203 × 108 5.552 × 108
11.132 10.900 11.044 9.996
1.484 1.443 1.574 1.717
4.886 4.551 4.860 4.122
7.06 6.01 7.48 6.46
98.9% 99.8% 96.8% 97.1%
204 149 191 53
Multilingual
BPE TopDownComp BottomUpLL UnigramLM
Gcomp Gcomp Gll Gll
bottom-up top-down bottom-up top-down
172,372,100 217,983,502 173,917,215 240,669,745
2.262 × 109 2.678 × 109 2.245 × 109 2.597 × 109
13.122 12.286 12.907 10.791
1.247 1.266 1.347 1.598
4.675 3.696 4.633 3.348
6.96 5.52 7.40 6.79
99.92% 99.94% 99.36% 99.74%
1,483 618 1,114 139
Table 5: Intrinsic statistics in English-only and multilingual settings. All values are computed at 128k vocabulary size. The multilingual evaluation corpus is the union of the five per-language test splits.
BPE TopDownComp BottomUpLL UnigramLM
BPE
TopDownComp
BottomUpLL
UnigramLM
— 37.0% 80.5% 32.3%
37.0% — 33.6% 63.6%
80.5% 33.6% — 31.2%
32.3% 63.6% 31.2% —
Table 6: Multilingual vocabulary overlap at 128k vocabulary size; the multilingual counterpart of Fig. 3.
BPE
BottomUpLL (Exact)
BottomUpLL (Approx)
Total absorbed Absorption rate (all) Absorption rate (|s| ≥ 5) Absorption rate (|s| ≥ 10)
34,224 26.8% 21.7% 4.5%
41,599 32.6% 27.8% 8.5%
41,751 32.7% 27.9% 8.8%
Absorbed with zero usage Absorbed with low usage (≤ 10) Not absorbed, zero usage
3.5% 26.2% .2%
9.2% 36.9% .4%
8.7% 36.0% .4%
Table 7: Merge-dynamics for bottom-up methods. Low usage means at most 10 occurrences on the test set. Absorbed with zero or low usage are given as a percentage of total absorptions.
decrease, entropies increase, and Coverage 50% grows by an order of magnitude (e.g., BPE: 204 → 1,483), reflecting the broader set of frequent token types in a five-language corpus. The relative pattern between objectives is preserved, however: UnigramLM retains the steepest Zipf α and lowest entropy in both settings, and likelihood-based methods stay more concentrated than their compressionbased counterparts within each search family.
used on its own. It only becomes wasteful when the absorbed token reduces in frequency enough to be considered not-useful any more. Tab. 7 present absorption rates for both BPE and BottomUpLL. Absorption is common for both methods, and by itself says little. The methods separate, however, on the tokens that are absorbed and then never used at all, which BottomUpLL produces nearly three times as often as BPE (9.2% vs. 3.5%). This is where its lower vocabulary utilisation at 128k comes from. Also interestingly, the absorption gap widens for long tokens (8.5% vs. 4.5% at ten characters or more). This suggests BottomUpLL reaches its final vocabulary through more intermediate steps than BPE, which is how it ends up with longer tokens.
Vocabulary utilisation rises with corpus breadth. The unused-vocabulary tail visible in English (Vocab Util 96.8–99.8%) largely disappears in the multilingual evaluation (99.36–99.94%), because the broader, more diverse corpus exercises a larger portion of the 128k vocabulary. Vocabulary overlap follows the same cluster structure. Tab. 6 is the multilingual counterpart of Fig. 3. BPE and BottomUpLL remain the most similar pair (80.5% overlap); TopDownComp and UnigramLM form a second cluster (63.6%); cross-family overlap stays in the 30–37% range.
K
Metric
L
Analysis of Merge Dynamics
Merge trajectories are only defined for the bottom-up methods, so this analysis covers BPE and BottomUpLL alone. A token is absorbed if it is created by one merge and later appears inside another merge: if a tokeniser first builds physi and then merges it into physic, physi has been absorbed. Absorption is common and not by itself a sign of waste, since an absorbed token usually remains in the vocabulary and can still
Vocabulary Overlap Structure
Fig. 3 reports pairwise vocabulary overlap in English, but pairwise numbers cannot show how the five vocabularies intersect jointly. Fig. 4 gives the full picture as a five-set Venn diagram over the 128k English-only vocabularies. The structure mirrors the pairwise results: the largest regions are those shared by the two bottom-up methods, the two topdown methods retain the largest exclusive regions, and cross-family regions are comparatively small. 17
BPE BottomUpLL = BottomUpLL TopDownComp UnigramLM
3.1k
0.4k 1.4k
12.9k
1.1k
0.7k
1.8k 2.6k
7.1k 9.6k
0.6k
48.6k 0.8k
0.1k
3.4k
0.6k 44.8k 0.5k
1.9k
0.5k 0.5k
1.1k 0.2k 0.4k
0.4k
44.2k
5.8k
4.3k
0.5k 23.8k
34.3k
Figure 4: Five-set Venn diagram of the 128k vocabularies. Each region gives the number of tokens (in thousands) belonging to exactly that combination of tokenisers. The largest two-way region is BPE ∩ BottomUpLL, and the BottomUpLL exact and approximate variants are nearly coextensive.
M
Qualitative Examples
Method
Aggregate metrics show the dominant trends, but they hide the local segmentation decisions that produce those trends. Here, we inspect a small set of representative examples covering plain English, scientific terminology, code-like text, URLs, Chinese, and multilingual accented text. These examples are illustrative rather than statistically decisive, but they make the inductive biases of the methods easier to interpret. Tab. 8 reports the total number of tokens produced across the 10 illustrative examples. The ordering broadly matches the full compression benchmark.
BPE TopDownComp BottomUpLL (Exact) BottomUpLL (Approx) UnigramLM
# of Tokens ↓ 156 160 154 153 173
Table 8: Total number of tokens produced across 10 illustrative test examples. Lower is better.
BottomUpLL often produces the shortest segmentation. It tends to preserve long technical units such as Photosynthesis or fragments of encephalography as large tokens. BPE is also compact, but more often splits these words into high-frequency pieces. This is consistent with the merge-dynamics analysis: BottomUpLL is more willing to build long lexical chains through intermediate tokens.
Scientific and medical terminology. On examples such as: (i) Photosynthesis converts carbon dioxide and water into glucose and oxygen. or (ii) Electroencephalography is used to diagnose neurological disorders. 18
Code and punctuation-heavy text. On code-like or SQL-like strings, BPE is usually strongest. For example, on: (iii) SELECT * FROM users WHERE id = 1; DROP TABLE users;– BPE produces the fewest tokens and preserves punctuation patterns such as ;–. UnigramLM is much more fragmented, often splitting short code tokens such as id, if, or def into character-level tokens. This reflects the concentration of its token distribution: unless short code tokens are strongly supported by the learned vocabulary, the model falls back to smaller tokens.
web-like text, BottomUpLL tends to form longer lexical units, UnigramLM can preserve some accented or non-Latin fragments while fragmenting other domains, and TopDownComp behaves as a compression-oriented top-down method.
N
Significance of BPB Differences
Some BPB differences between tokenisers are small, so we test whether they are robust to the choice of evaluation documents. For each objective-matched pair of tokenisers, we run a paired document-level bootstrap over the held-out English test set (47,384 documents). In each of 10,000 iterations we resample documents with replacement and use the same resampled indices for both models, so that the shared per-document difficulty cancels. We then recompute each model’s corpus-level BPB on the resampled set and record the difference between the bottom-up and top-down model. Tab. 9 reports point estimates and 95% confidence intervals for the 128k-vocabulary models, using seed 42 for each configuration.
URL-like text. For URL strings such as: (iv) https://www.example.com/path/to/ resource?query=value&page=1 BPE and TopDownComp are especially compact. BPE often preserves web-specific substrings such as https, while BottomUpLL may split them into statistically meaningful but less URL-specific pieces such as http+s. This is a case where frequency-driven compression appears better matched to the surface regularities of web text than likelihood-based lexical cohesion. Chinese text. On the short Chinese example: (v) 人工智能正在改变世界 UnigramLM produces the fewest tokens among the inspected methods. This does not contradict the multilingual BPB results in Tab. 3, where bottomup methods are much better on Chinese overall. Rather, it shows that example-level token count and corpus-level language-model BPB can diverge: a tokeniser may preserve some non-Latin chunks well while still producing a worse distribution of tokens for language modelling across the full evaluation set.
Size
Comparison
∆ BPB
95% CI
300M
BPE vs. TopDownComp BottomUpLL vs. UnigramLM
−0.0031 −0.0080
[−0.0032, −0.0029] [−0.0082, −0.0078]
500M
BPE vs. TopDownComp BottomUpLL vs. UnigramLM
−0.0016 −0.0075
[−0.0017, −0.0014] [−0.0077, −0.0074]
1B
BPE vs. TopDownComp BottomUpLL vs. UnigramLM
−0.0025 −0.0039
[−0.0027, −0.0023] [−0.0041, −0.0037]
Table 9: Paired document-level bootstrap (10,000 resamples) of BPB differences between objectivematched tokenisers at 128k vocabulary. Negative values indicate the bottom-up method achieves lower BPB. All confidence intervals exclude zero.
All six confidence intervals lie entirely below zero, indicating that, for each objective, the bottomup tokeniser achieves significantly lower BPB than its top-down counterpart, and that this ordering is not an artifact of the particular held-out documents used for evaluation.
Multilingual accented text. Finally, for: (vi) ¡Hola! ¿Cómo estás? Très bien, merci. Danke schön! all methods produce similar total counts, but the internal boundaries differ. UnigramLM tends to preserve accented fragments such as Cómo and estás more coherently, while BPE more often splits them into smaller pieces. Thus, even when example-level token counts are similar, tokenisers can impose different boundaries that may matter for downstream behaviour.
Training-seed variance. The bootstrap above controls for the choice of evaluation documents, but not for randomness in model training. To assess the latter, we retrain the English 1B models at 128k vocabulary with two additional seeds (43 and 44), giving three seeds per tokeniser. Tab. 10 reports the per-seed BPB values. Both objectivematched orderings are preserved in the mean: BPE outperforms TopDownComp, and BottomUpLL outperforms UnigramLM. We note that BottomUpLL
Take away. Together, these examples illustrate the same qualitative biases seen in the aggregate analyses: BPE is robust on punctuation-heavy and 19
shows a noticeably larger spread than the other tokenisers, driven by a single seed; averaged over three seeds it attains a lower BPB than TopDownComp, whereas on seed 42 alone the ordering is reversed.
deletion costs and once using the local replacement approximation. The two procedures agree on 652 of the 800 resulting tokens, an overlap of 81.5%. The approximation therefore recovers most, but not all, of the vocabulary that exact scoring would select. We note that this is a small-vocabulary and small-corpus setting, though, and that the effect of the approximation at the scales used in our main experiments remains open.
Seed Tokeniser BPE TopDownComp BottomUpLL UnigramLM
42
43
44
0.7795 0.7819 0.7833 0.7872
0.7787 0.7817 0.7789 0.7871
0.7787 0.7813 0.7787 0.7873
Mean 0.7790 ± 4e-4 0.7816 ± 3e-4 0.7803 ± 26e-4 0.7872 ± 1e-4
Table 10: Per-seed BPB for the English 1B models at 128k vocabulary. Mean is taken over the three seeds, with standard deviation.
O
Effect of the Top-Down Approximations
In this section, we investigate the impact of our approximations in top-down methods. Pruning rate. For efficiency and as is standard practice, our top-down methods remove batches of tokens at each pruning round, rather than a single token. Specifically, our main experiments prune 10% of the current vocabulary per round. To assess how much this batching affects the learned vocabulary, we re-train UnigramLM and TopDownComp at 128k vocabulary using pruning rates of 1% and 0.1% per round, and measure the vocabulary overlap with the corresponding 10% tokeniser. For UnigramLM, the overlap is 97.3% at a 1% pruning rate and 97.1% at 0.1%; for TopDownComp it remains above 99% in both cases. Inspecting the non-overlapping tokens, we find that they occur very rarely in the tokenised corpus. Pruning in batches therefore appears to have a limited effect on the resulting vocabulary. Local replacement. Our second approximation is the local replacement approximation of §4.2, which scores a deletion by re-segmenting only the deleted token, rather than recomputing the objective over the whole corpus. Computing exact deletion costs requires re-segmenting the corpus once per candidate token at every pruning step, which is intractable at the vocabulary sizes used in our main experiments. We therefore compare the two at a small scale: on 5,000 lines of English FineWeb, we prune from a seed vocabulary of 3,000 tokens down to 800 with a pruning rate of 10%, once using exact 20