Paper deep dive
Objective vs. Search: Decomposing What Makes a Good Tokeniser
Ahmetcan Yavuz, Clara Meister, Tiago Pimentel
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 9/19/2026, 2:47:04 AM
Summary
This paper investigates the factors contributing to effective tokenisation in language models by disentangling optimisation objectives (compression vs. log-likelihood) from search procedures (bottom-up merging vs. top-down pruning). The authors introduce two new algorithms, BottomUpLL and TopDownComp, to complete a 2x2 design space alongside existing BPE and UnigramLM methods. Experimental results indicate that the search procedure is the dominant factor for bits-per-byte performance, with bottom-up approaches consistently outperforming top-down ones, while grammaticality performance (BLiMP) shows no consistent relationship with these design choices.
Entities (13)
Relation Signals (10)
Byte Pair Encoding → optimisesobjective → Compression
confidence 95% · BPE... learns a vocabulary that maximises the compression of a training corpus
BottomUpLL → optimisesobjective → Log-Likelihood
confidence 95% · BottomUpLL... optimises corpus log-likelihood
UnigramLM → optimisesobjective → Log-Likelihood
confidence 95% · UnigramLM, which learns a vocabulary that maximises the unigram log-likelihood of a training corpus
TopDownComp → optimisesobjective → Compression
confidence 95% · TopDownComp... optimises compression.
Byte Pair Encoding → usessearchprocedure → Bottom-Up Merging
confidence 95% · BPE uses a bottom-up search, greedily merging symbols to maximise compression.
UnigramLM → usessearchprocedure → Top-Down Pruning
confidence 95% · UnigramLM relies on a top-down search, starting from an oversized vocabulary and iteratively pruning tokens
BottomUpLL → usessearchprocedure → Bottom-Up Merging
confidence 95% · BottomUpLL, a bottom-up likelihood-based tokeniser
TopDownComp → usessearchprocedure → Top-Down Pruning
confidence 95% · TopDownComp, a top-down compression-based tokeniser
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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 2x2 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-per-byte, we find that the search procedure -- not the objective -- is the dominant factor: bottom-up tokenisers consistently achieve lower bits-per-byte 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.
Tags
Links
- Source: https://arxiv.org/abs/2609.19145v1
- Canonical: https://arxiv.org/abs/2609.19145v1
PDF not stored locally. Use the link above to view on the source site.
Full Text
129,466 characters extracted from source content.
Expand or collapse full text
Objective vs. Search: Decomposing What Makes a Good Tokeniser Ahmetcan Yavuz Affiliation: ETH Zürich Clara Meister Affiliation: EPFL Tiago Pimentel Email: ayavuz@ethz.ch, clara.meister@epfl.ch, tiago.pimentel@inf.ethz.ch Ahmetcanyvz/comp-vs-like & Ahmetcanyvz/comp-vs-like Affiliation: ETH Zürich Abstract 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-per-byte, we find that the search procedure—not the objective—is the dominant factor: bottom-up tokenisers consistently achieve lower bits-per-byte 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. 1 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 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 (i) UnigramLM, which learns a vocabulary that maximises the unigram log-likelihood of a training corpus (Kudo, 2018). BPETopDownCompBottomUpLLUnigramLMoursoursbottom-up(merging)top-down(pruning)search procedurecompressionlog-likelihoodobjective Figure 1: Design choice factorisation for tokenisation. 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 log-likelihood. 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.11 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. 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: 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 likelihood-based 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×22× 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 likelihood-based tokenisers outperform compression-based ones. Overall, our results highlight the importance of both optimisation objective and search procedure to tokeniser training algorithm design. 2 Tokenisation Language modelling starts from raw text, which can be represented as character-strings ∈Σ∗ [rgb]0.2734,0.4688,1c∈ [rgb]0.2734,0.4688,1 ^*; these are finite sequences of characters =c1c2…c|| [rgb]0.2734,0.4688,1c= [rgb]0.2734,0.4688,1 [rgb]0.2734,0.4688,1c_1 [rgb]0.2734,0.4688,1c_2… [rgb]0.2734,0.4688,1c_| [rgb]0.2734,0.4688,1c| over alphabet Σ [rgb]0.2734,0.4688,1 .22 2 As usual, Σ∗ [rgb]0.2734,0.4688,1 ^* denotes the Kleene star of Σ [rgb]0.2734,0.4688,1 , while Σ+ [rgb]0.2734,0.4688,1 ^+ denotes the set of all non-empty strings over Σ [rgb]0.2734,0.4688,1 . A tokeniser’s job is then to segment these character-strings into token-strings ∈∗ [rgb]0.8633,0.1953,0.5508s∈ [rgb]0.8633,0.1953,0.5508S^*: sequences =⟨s1,s2,…,s||⟩ [rgb]0.8633,0.1953,0.5508s= [rgb]0.8633,0.1953,0.5508 [rgb]0.8633,0.1953,0.5508s_ [rgb]0,0,01, [rgb]0.8633,0.1953,0.5508s_ [rgb]0,0,02,…, [rgb]0.8633,0.1953,0.5508s_ [rgb]0,0,0| [rgb]0.8633,0.1953,0.5508s| , where each symbol st [rgb]0.8633,0.1953,0.5508s_ [rgb]0,0,0t is called a token and represents a non-empty character span. Whenever [rgb]0.8633,0.1953,0.5508s is a segmentation of [rgb]0.2734,0.4688,1c, we say these strings are equivalent, which we denote as =∘ [rgb]0.2734,0.4688,1c = [rgb]0.8633,0.1953,0.5508s, i.e.:33 3 We restrict our discussion to lossless tokenisers here. =∘⇔=s1∘s2∘⋯∘s||, [rgb]0.2734,0.4688,1c = [rgb]0.8633,0.1953,0.5508s [rgb]0.2734,0.4688,1c= [rgb]0.8633,0.1953,0.5508s_ [rgb]0,0,01 [rgb]0.8633,0.1953,0.5508s_ [rgb]0,0,02 … [rgb]0.8633,0.1953,0.5508s_ [rgb]0,0,0| [rgb]0.8633,0.1953,0.5508s|, (1) Notably, tokenisers are usually not allowed to output any possible segmentation of [rgb]0.2734,0.4688,1c, being instead constrained to segment it using only the tokens in a finite set called its vocabulary ⊂Σ+ [rgb]0.8633,0.1953,0.5508S⊂ [rgb]0.2734,0.4688,1 ^+. To ensure that any character-string can be represented as tokens, we enforce Σ⊆ [rgb]0.2734,0.4688,1 [rgb]0.8633,0.1953,0.5508S. How do we convert between character- and token-strings, though? Given just a vocabulary [rgb]0.8633,0.1953,0.5508S, there are multiple different ways a character-string could be mapped to items in that vocabulary. For example, if =a,aa,aaa, [rgb]0.8633,0.1953,0.5508S=\ [rgb]0.8633,0.1953,0.5508a, [rgb]0.8633,0.1953,0.5508a, [rgb]0.8633,0.1953,0.5508a\, then the character-string =aaa [rgb]0.2734,0.4688,1c= [rgb]0.2734,0.4688,1a may be encoded as either ⟨a,aa⟩ [rgb]0.8633,0.1953,0.5508 a,a , ⟨aa,a⟩ [rgb]0.8633,0.1953,0.5508 a,a , or ⟨a,a,a⟩ [rgb]0.8633,0.1953,0.5508 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 character-strings to segmentations. This mapping is the job of an encoding function, :Σ∗→∗ [rgb]1,0.4688,0.0781 tok: [rgb]0.2734,0.4688,1 ^*→ [rgb]0.8633,0.1953,0.5508S^*, which segments the original character-string into tokens; by definition, we have thus that =∘() [rgb]0.2734,0.4688,1c = [rgb]1,0.4688,0.0781 tok( [rgb]0.2734,0.4688,1c). Finally, a tokeniser also contains a decoding function, :∗→Σ∗ [rgb]1,0.4688,0.0781 detok: [rgb]0.8633,0.1953,0.5508S^*→ [rgb]0.2734,0.4688,1 ^*, which converts token-strings back into characters, being typically defined as the concatenation of each token’s characters: ()=defs1∘s2∘⋯∘s|| [rgb]1,0.4688,0.0781 detok( [rgb]0.8633,0.1953,0.5508s) def= [rgb]0.8633,0.1953,0.5508s_ [rgb]0,0,01 [rgb]0.8633,0.1953,0.5508s_ [rgb]0,0,02 … [rgb]0.8633,0.1953,0.5508s_ [rgb]0,0,0| [rgb]0.8633,0.1953,0.5508s|. Formally, we thus define a tokeniser as the tuple =def⟨,,⟩ [rgb]0.8633,0.1953,0.5508T def= [rgb]0.8633,0.1953,0.5508S, [rgb]1,0.4688,0.0781 detok, [rgb]1,0.4688,0.0781 tok . 3 Learning a Tokeniser: Optimisation Objective vs. Search Procedure 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 Objective Functions Given a tokeniser [rgb]0.8633,0.1953,0.5508T and a dataset =mm=1MD=\ [rgb]0.2734,0.4688,1c_m\_m=1^M, an objective function [rgb]1,0.4688,0.0781 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: comp(,)=def∑∈|()|, [rgb]1,0.4688,0.0781 G_comp( [rgb]1,0.4688,0.0781 tok,D) def= _ [rgb]0.2734,0.4688,1c | [rgb]1,0.4688,0.0781 tok( [rgb]0.2734,0.4688,1c)|, (2) 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 a given probabilistic model p_ θ assigns the corpus: l(,)=def−∑∈logp(()). [rgb]1,0.4688,0.0781 G_l( [rgb]1,0.4688,0.0781 tok,D) def=- _ [rgb]0.2734,0.4688,1c p_ θ ( [rgb]1,0.4688,0.0781 tok( [rgb]0.2734,0.4688,1c) ). (3) 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 [rgb]1,0.4688,0.0781 tok, let nsDn_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD denote the count of token s [rgb]0.8633,0.1953,0.5508s in the tokenised corpus, and let ND=def∑s∈nsDN @scalerel@objD def= _ [rgb]0.8633,0.1953,0.5508s∈ [rgb]0.8633,0.1953,0.5508Sn_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD be the total number of tokens. We then define p_ θ as p()=∏t=1||p(st),p(s)=nsDND.p_ θ( [rgb]0.8633,0.1953,0.5508s)= _t=1^| [rgb]0.8633,0.1953,0.5508s|p_ θ( [rgb]0.8633,0.1953,0.5508s_ [rgb]0,0,0t), p_ θ( [rgb]0.8633,0.1953,0.5508s)= n_ [rgb]0.8633,0.1953,0.5508s @scalerel@objDN @scalerel@objD. (4) Concretely, we will thus use unigram log-likelihood as the objective here, as opposed to ‘full’ log-likelihood, and, for the rest of this paper, log-likelihood 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 =argmin∈K(,), [rgb]1,0.4688,0.0781 tok_ opt= _ [rgb]1,0.4688,0.0781 tok _K [rgb]1,0.4688,0.0781 G( [rgb]1,0.4688,0.0781 tok,D), (5) where KT_K 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 log-likelihood 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 Σ [rgb]0.2734,0.4688,1 and grows one token at a time through merge operations. Given a merge m=⟨s′,s′⟩ [rgb]0.8633,0.1953,0.5508m= [rgb]0.8633,0.1953,0.5508s , [rgb]0.8633,0.1953,0.5508s , applying it to a token-string rewrites every (non-overlapping) occurrence of bigram s′,s′ [rgb]0.8633,0.1953,0.5508s , [rgb]0.8633,0.1953,0.5508s into the token snew=s′∘s′ [rgb]0.8633,0.1953,0.5508s new= [rgb]0.8633,0.1953,0.5508s [rgb]0.8633,0.1953,0.5508s . A merge list =m1,…,mk [rgb]0.8633,0.1953,0.5508m= [rgb]0.8633,0.1953,0.5508m_1,…, [rgb]0.8633,0.1953,0.5508m_k then defines an encoding function ↑[] [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508m]: starting from [rgb]0.2734,0.4688,1c as a token-string over Σ [rgb]0.2734,0.4688,1 (one token per character), it applies m1,…,mk [rgb]0.8633,0.1953,0.5508m_1,…, [rgb]0.8633,0.1953,0.5508m_k in order. The final token-string is our tokenised text. We write the tokeniser class defined by this procedure as K↑=↑[]∣∈(Σ+×Σ+)KT_K = \ [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508m] [rgb]0.8633,0.1953,0.5508m∈( [rgb]0.2734,0.4688,1 ^+× [rgb]0.2734,0.4688,1 ^+)^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 [rgb]1,0.4688,0.0781 G: m⋆=argminm∈Σ+×Σ+(↑[<k,m],), [rgb]0.8633,0.1953,0.5508m = _ [rgb]0.8633,0.1953,0.5508m∈ [rgb]0.2734,0.4688,1 ^+× [rgb]0.2734,0.4688,1 ^+ [rgb]1,0.4688,0.0781 G( [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508m_<k, [rgb]0.8633,0.1953,0.5508m],D), (6) where ↑[<k,m] [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508m_<k, [rgb]0.8633,0.1953,0.5508m] denotes the encoding function obtained by applying the current merge list <k [rgb]0.8633,0.1953,0.5508m_<k followed by the candidate m [rgb]0.8633,0.1953,0.5508m. The selected merge m⋆ [rgb]0.8633,0.1953,0.5508m is then appended to the merge list. We refer to a candidate merge’s effect on the objective as its merge gain, and write it Δs1,s2(⋅,) _ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 [rgb]1,0.4688,0.0781 G(·,D). By contrast, the top-down procedure starts from a large candidate vocabulary 0 [rgb]0.8633,0.1953,0.5508S_0, with |0|≫K| [rgb]0.8633,0.1953,0.5508S_0| K, and removes tokens until ||=|Σ|+K| [rgb]0.8633,0.1953,0.5508S|=| [rgb]0.2734,0.4688,1 |+K. Notably, this procedure does not rely on merge lists, but instead commits to an objective-optimal encoding function ⇒[] [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508S], determined by the vocabulary alone. Under compression, ⇒[]() [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508S]( [rgb]0.2734,0.4688,1c) is the shortest valid segmentation of [rgb]0.2734,0.4688,1c using tokens from [rgb]0.8633,0.1953,0.5508S. Under log-likelihood, it is instead the most probable segmentation of [rgb]0.2734,0.4688,1c under p_ θ.44 4 Given a fixed p_ θ, both cases can be computed efficiently. For log-likelihood, however, the parameters of p_ θ itself depend on [rgb]1,0.4688,0.0781 tok, creating a circular definition. In practice, the two are estimated jointly as we explain in § 4.2. Top-down’s tokeniser class can then be written as: K↓=⇒[]∣⊂Σ+,Σ⊆,||=|Σ|+KT_K = \ [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508S] [rgb]0.8633,0.1953,0.5508S⊂ [rgb]0.2734,0.4688,1 ^+, [rgb]0.2734,0.4688,1 [rgb]0.8633,0.1953,0.5508S,| [rgb]0.8633,0.1953,0.5508S|=| [rgb]0.2734,0.4688,1 |+K \. To select an item in this class, we then start from a large vocabulary 0 [rgb]0.8633,0.1953,0.5508S_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: s✗=argmins∈k−1∖Σ(⇒[k−1∖s],). [rgb]0.8633,0.1953,0.5508s_✗= _ [rgb]0.8633,0.1953,0.5508s∈ [rgb]0.8633,0.1953,0.5508S_k-1 [rgb]0.2734,0.4688,1 [rgb]1,0.4688,0.0781 G( [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508S_k-1 \ [rgb]0.8633,0.1953,0.5508s\],D). (7) Here, we index pruning steps by k, mirroring the bottom-up case. This yields k=k−1∖s✗ [rgb]0.8633,0.1953,0.5508S_k= [rgb]0.8633,0.1953,0.5508S_k-1 \ [rgb]0.8633,0.1953,0.5508s_✗\. Importantly, to ensure every string remains encodable, alphabet tokens are never removed; pruning then continues until ||=|Σ|+K| [rgb]0.8633,0.1953,0.5508S|=| [rgb]0.2734,0.4688,1 |+K.55 5 We note that, for efficiency reasons, in practice, multiple tokens are often pruned in batches. Analogously, we refer to a candidate deletion’s effect on the objective as its deletion cost, written Δs(⋅,) _ [rgb]0.8633,0.1953,0.5508s [rgb]1,0.4688,0.0781 G(·,D). 4 Analysed Tokenisers: Old and New Combining the objectives and search procedures above, we get a 2×22× 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 likelihood-based method, and TopDownComp, a top-down compression-based method.66 6 Our new methods are closely related to, e.g., WordPiece or PathPiece. We discuss this prior work in detail in § 5. 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⋆ [rgb]0.8633,0.1953,0.5508m or deletion s✗ [rgb]0.8633,0.1953,0.5508s_✗ which (locally) optimises an objective (⋅,) [rgb]1,0.4688,0.0781 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 [rgb]1,0.4688,0.0781 G once per candidate to find the optimal one—a computationally impractical operation. Rather than recomputing [rgb]1,0.4688,0.0781 G every time, most tokenisation algorithms work with incremental scores instead: m⋆ [rgb]0.8633,0.1953,0.5508m =argmax⟨s1,s2⟩∈Σ+×Σ+Δs1,s2(⋅,) = _ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 ∈ [rgb]0.2734,0.4688,1 ^+× [rgb]0.2734,0.4688,1 ^+ _ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 [rgb]1,0.4688,0.0781 G(·,D) (8a) s✗ [rgb]0.8633,0.1953,0.5508s_✗ =argmins∈k−1∖ΣΔs(⋅,) =\,\,\,\,\,\, _ [rgb]0.8633,0.1953,0.5508s∈ [rgb]0.8633,0.1953,0.5508S_k-1 [rgb]0.2734,0.4688,1 \,\,\,\,\,\, _ [rgb]0.8633,0.1953,0.5508s [rgb]1,0.4688,0.0781 G(·,D) (8b) Notably, these equations are equivalent to § 3.2’s, as the pre-update objective values (e.g., (↑[<k],) [rgb]1,0.4688,0.0781 G( [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508m_<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 Bottom-up tokenisers: BPE and BottomUpLL For a bottom-up method, each candidate is scored according to its merge gain Δs1,s2(⋅,) _ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 [rgb]1,0.4688,0.0781 G(·,D). We now show how this score can be computed efficiently for the two objectives, starting with compression. Lemma 1. The change in compression due to merging a token-pair can be computed as: Δs1,s2comp(⋅,)=ns1,s2D _ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 [rgb]1,0.4688,0.0781 G_comp(·,D)=n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD (9) where ns1,s2Dn_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD denotes the number of non-overlapping ⟨s1,s2⟩ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 sequences in D. Proof sketch. The full proof is in Appendix A. Replacing an occurrence of the token-pair m=⟨s1,s2⟩ [rgb]0.8633,0.1953,0.5508m= [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 with the merged token s1∘s2 [rgb]0.8633,0.1953,0.5508s^1 [rgb]0.8633,0.1953,0.5508s^2 saves one token. Further, the number of non-overlapping occurrences of a token-pair is its number of possible merges. Merging the pair therefore shortens the corpus by exactly ns1,s2Dn_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD tokens, which is its gain under comp [rgb]1,0.4688,0.0781 G_comp. ∎ Lemma 1 gives the standard BPE merge rule: the compression-optimal merge is the most (non-overlappingly) frequent token-pair. In practice, the token-pair counts ns1,s2Dn_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD are computed once and then updated incrementally after each merge, rather than recomputed from scratch (see App. 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:77 7 For the case s1=s2 [rgb]0.8633,0.1953,0.5508s^1= [rgb]0.8633,0.1953,0.5508s^2, the same calculation applies albeit with a modified count update: each merge consumes two occurrences of the same token s1 [rgb]0.8633,0.1953,0.5508s^1 and thus its count is reduced by 2ns1,s1D2n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD instead; other parts of the update remain unchanged. Δs1,s2l(⋅,)= _ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 [rgb]1,0.4688,0.0781 G_l(·,D)\!= (10) (ns1D−ns1,s2D)log(ns1D−ns1,s2D)−ns1Dlogns1D \,\,(n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD-n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD) (n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD-n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD)-n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD +(ns2D−ns1,s2D)log(ns2D−ns1,s2D)−ns2Dlogns2D \,\,+(n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD-n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD) (n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD-n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD)-n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD +ns1,s2Dlogns1,s2D \,\,+n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD −(ND−ns1,s2D)log(ND−ns1,s2D)+NDlogND. \,\,-(N @scalerel@objD-n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD) (N @scalerel@objD-n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD)+N @scalerel@objD N @scalerel@objD. Proof sketch. The full proof is in Appendix C. Note that, if a token changes from count n1n_1 to count n2n_2, its contribution to the log-likelihood objective changes by: n2logn2−n1logn1n_2 n_2-n_1 n_1. The lemma then follows trivially, noting that: (i) the old tokens s1 [rgb]0.8633,0.1953,0.5508s^1 and s2 [rgb]0.8633,0.1953,0.5508s^2 change from, e.g., frequency ns1Dn_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD to (ns1D−ns1,s2D)(n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD-n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD); (i) the new token s1∘s2 [rgb]0.8633,0.1953,0.5508s^1 [rgb]0.8633,0.1953,0.5508s^2 changes from frequency 0 to ns1,s2Dn_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD. 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 NDN @scalerel@objD to ND−ns1,s2DN @scalerel@objD-n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD. ∎ 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 (i) it should also be favoured when its tokens co-occur more systematically than expected from their individual frequencies. 4.2 Top-down tokenisers: UnigramLM and TopDownComp For top-down methods, each candidate’s score is given by the deletion cost Δs(⋅,) _ [rgb]0.8633,0.1953,0.5508s [rgb]1,0.4688,0.0781 G(·,D). Unfortunately, this cost Δs(⋅,) _ [rgb]0.8633,0.1953,0.5508s [rgb]1,0.4688,0.0781 G(·,D) is non-trivial to compute. This is due to the nature of the encoding function ⇒[] [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508S] 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.88 8 For example, under a compression objective, suppose =Σ∪abc,def,cdef [rgb]0.8633,0.1953,0.5508S\!=\! [rgb]0.2734,0.4688,1 ∪\ [rgb]0.8633,0.1953,0.5508abc, [rgb]0.8633,0.1953,0.5508def, [rgb]0.8633,0.1953,0.5508cdef\. Then, string abcdef [rgb]0.2734,0.4688,1abcdef is segmented as ⟨abc,def⟩ [rgb]0.8633,0.1953,0.5508 abc,def . If abc [rgb]0.8633,0.1953,0.5508abc is deleted, however, the shortest segmentation under the reduced vocabulary becomes ⟨a,b,cdef⟩ [rgb]0.8633,0.1953,0.5508 a,b,cdef , which also changes the previously used token def [rgb]0.8633,0.1953,0.5508def. For the log-likelihood objective, the history gets worse. The segmentations produced by ⇒[] [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508S] 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. To approximate Δs(⋅,) _ [rgb]0.8633,0.1953,0.5508s [rgb]1,0.4688,0.0781 G(·,D), we thus rely on a local replacement approximation: when scoring the deletion of s [rgb]0.8633,0.1953,0.5508s, we keep the rest of the current model fixed and estimate the loss by only directly replacing occurrences of s [rgb]0.8633,0.1953,0.5508s with an alternative segmentation under ∖s [rgb]0.8633,0.1953,0.5508S \ [rgb]0.8633,0.1953,0.5508s\.99 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 top-down search procedures, being itself present in UnigramLM. We return to its implications in our Limitations section. For log-likelihood, this then yields the following result. Lemma 3. Under a local replacement approximation, the estimated increase in the negative log-likelihood objective due to deleting a token s∈∖Σ [rgb]0.8633,0.1953,0.5508s∈ [rgb]0.8633,0.1953,0.5508S [rgb]0.2734,0.4688,1 can be approximated as:1010 10 In practice, when computing this update, UnigramLM keeps segmentations latent and leverages p_ θ to compute nsDn_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD as the expected count of s [rgb]0.8633,0.1953,0.5508s, instead of its exact count under ⇒ [rgb]1,0.4688,0.0781 tok_ . Δsll(⋅,)≈nsD(logp(s)−logp(srep)), _ [rgb]0.8633,0.1953,0.5508s [rgb]1,0.4688,0.0781 G_l(·,D)≈ n_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD ( p_ θ( [rgb]0.8633,0.1953,0.5508s)- p_ θ( [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s) ), (11) where p_ θ is the unigram model at step k−1k-1, and srep [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s is s [rgb]0.8633,0.1953,0.5508s’s log-probability–optimal replacement segmentation, i.e., srep=def⇒[k−1∖s](s) [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s def= [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508S_k-1 \ [rgb]0.8633,0.1953,0.5508s\]( [rgb]0.8633,0.1953,0.5508s). Proof sketch. The full proof is in Appendix D. Before deletion, each expected occurrence of s [rgb]0.8633,0.1953,0.5508s contributes −logp(s)-\! p_ θ( [rgb]0.8633,0.1953,0.5508s) to the negative log-likelihood. Under the local replacement approximation, deleting s [rgb]0.8633,0.1953,0.5508s replaces it with srep [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s, which contributes −logp(srep)- p_ θ( [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s). As the number of such occurrences is nsDn_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD, we get Eq. 11. ∎ After each deletion, we update our encoding function ⇒[k] [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508S_k] by re-estimating p_ θ. We do this by updating θ via an expectation–maximisation procedure, maximising the log-likelihood of D.1111 11 The details of this procedure fall out of our work’s scope; for an accessible derivation, see Meister (2026). This updated p_ θ defines the segmentations produced by ⇒ [rgb]1,0.4688,0.0781 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∈∖Σ [rgb]0.8633,0.1953,0.5508s∈ [rgb]0.8633,0.1953,0.5508S [rgb]0.2734,0.4688,1 can be approximated as: Δscomp(⋅,)=nsD(|srep|−1), _ [rgb]0.8633,0.1953,0.5508s [rgb]1,0.4688,0.0781 G_comp(·,D)=n_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD (| [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s|-1 ), (12) where srep [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s is the compression-optimal replacement of s [rgb]0.8633,0.1953,0.5508s after deletion: srep=def⇒[k−1∖s](s) [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s def= [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508S_k-1 \ [rgb]0.8633,0.1953,0.5508s\]( [rgb]0.8633,0.1953,0.5508s). Proof sketch. The full proof is in Appendix E. After deleting s [rgb]0.8633,0.1953,0.5508s, the local replacement uses |srep|| [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s| tokens instead, thus increasing the corpus length by |srep|−1| [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s|-1. There are nsDn_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD such occurrences. ∎ Updating this compression-based tokeniser after a deletion is easier than for log-likelihood. No parameters need to be estimated: the vocabulary k [rgb]0.8633,0.1953,0.5508S_k alone determines the encoding function, so we simply re-segment the corpus under ⇒[k] [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508S_k]. 5 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. 5.1 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: PMIadj(s1,s2) _adj( [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2) =deflogp(s1,s2)p(s1)p(s2) def= p_ θ( [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2)p_ θ( [rgb]0.8633,0.1953,0.5508s^1)\,p_ θ( [rgb]0.8633,0.1953,0.5508s^2) (13a) =logNDns1,s2Dns1Dns2D. = N @scalerel@objD\,n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objDn_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objDn_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD. (13b) Relying on the PMI to operationalise this notion of more-often-than-chance co-occurrence, we can use a Taylor approximation of Δs1,s2l(⋅,) _ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 [rgb]1,0.4688,0.0781 G_l(·,D) to make this explanation of BottomUpLL explicit. Lemma 5. Under a first-order Taylor approximation, the change in log-likelihood due to merging a token-pair can be approximated as: Δs1,s2l(⋅,)≈ns1,s2D(PMIadj(s1,s2)−1). _ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 [rgb]1,0.4688,0.0781 G_l(·,D)≈ n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD (PMI_adj( [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2)-1 ). (14) Proof sketch. The full proof is in Appendix F. Starting from Lemma 2, apply a first-order Taylor expansion independently to each xlogx x term. Collecting the resulting terms returns the equation above. ∎ Equation 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.1212 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) 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 PMIadjPMI_adj (Schmidt et al., 2024; Lesci et al., 2025; Hugging Face, 2026), which relates to Eq. 14 but drops the ns1,s2Dn_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD 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-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. 5.2 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 [rgb]0.8633,0.1953,0.5508s, PathPiece also considers re-segmentation of other vocabulary tokens that contain s [rgb]0.8633,0.1953,0.5508s as a substring, whereas TopDownComp considers only s [rgb]0.8633,0.1953,0.5508s’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. Vocab Tokeniser Objective Search comp [rgb]1,0.4688,0.0781 G_comp ↓ l [rgb]1,0.4688,0.0781 G_l ↓ Entropy Zipf α BPT ↑ Tok Len Vocab Util ↑ Cov. 50% 8k BPE comp [rgb]1,0.4688,0.0781 G_comp bottom-up 59,559,835 6.259×1086.259× 10^8 10.508 1.033 3.844 5.53 99.9% 242 TopDownComp comp [rgb]1,0.4688,0.0781 G_comp top-down 59,304,113 6.259×1086.259× 10^8 10.554 0.919 3.861 5.67 99.3% 268 BottomUpLL l [rgb]1,0.4688,0.0781 G_l bottom-up 61,170,714 6.167× 6.167× 10^8 10.081 1.315 3.743 6.05 99.4% 152 UnigramLM l [rgb]1,0.4688,0.0781 G_l top-down 68,444,350 6.221×1086.221× 10^8 9.089 1.093 3.345 6.72 99.3% 39 32k BPE comp [rgb]1,0.4688,0.0781 G_comp bottom-up 50,327,096 5.544×1085.544× 10^8 11.016 1.195 4.549 6.52 99.8% 269 TopDownComp comp [rgb]1,0.4688,0.0781 G_comp top-down 52,204,230 5.667×1085.667× 10^8 10.856 1.074 4.386 6.29 99.8% 192 BottomUpLL l [rgb]1,0.4688,0.0781 G_l bottom-up 50,920,853 5.505× 5.505× 10^8 10.811 1.378 4.496 6.98 99.0% 211 UnigramLM l [rgb]1,0.4688,0.0781 G_l top-down 58,161,017 5.697×1085.697× 10^8 9.796 1.272 3.937 7.03 99.8% 51 128k BPE comp [rgb]1,0.4688,0.0781 G_comp bottom-up 46,859,565 5.216×1085.216× 10^8 11.132 1.484 4.886 7.06 98.9% 204 TopDownComp comp [rgb]1,0.4688,0.0781 G_comp top-down 50,312,483 5.484×1085.484× 10^8 10.900 1.443 4.551 6.01 99.8% 149 BottomUpLL l [rgb]1,0.4688,0.0781 G_l bottom-up 47,111,733 5.203× 5.203× 10^8 11.044 1.574 4.860 7.48 96.8% 191 UnigramLM l [rgb]1,0.4688,0.0781 G_l top-down 55,546,423 5.552×1085.552× 10^8 9.996 1.717 4.122 6.46 97.1% 53 Table 1: Intrinsic tokenisation results on a held-out test set (47,384 documents). Columns are defined in the Evaluation paragraph of § 6. Table 5 in Appendix J reports the multilingual counterpart of this table. 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 byte-level 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. Appendix G gives the exact configuration under which we train our tokenisers. Full language model hyperparameter and architectural details are in Appendix 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.1313 13 Full hyperparameter and architectural details are in Appendix H. 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×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. 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 comp [rgb]1,0.4688,0.0781 G_comp and l [rgb]1,0.4688,0.0781 G_l. 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 App. I. 7 Results 7.1 Intrinsic Evaluation Compression vs. Log-likelihood. Tab. 1 presents both the comp [rgb]1,0.4688,0.0781 G_comp and l [rgb]1,0.4688,0.0781 G_l achieved by our tokenisers. From this table, we can see that, for a small vocabulary (of 8k8k 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: Ent(,) ( [rgb]1,0.4688,0.0781 tok,D) =def−∑s∈p(s)logp(s) def=- _ [rgb]0.8633,0.1953,0.5508s∈ [rgb]0.8633,0.1953,0.5508Sp_ θ( [rgb]0.8633,0.1953,0.5508s) p_ θ( [rgb]0.8633,0.1953,0.5508s) (15a) =l(,)comp(,) = [rgb]1,0.4688,0.0781 G_l( [rgb]1,0.4688,0.0781 tok,D) [rgb]1,0.4688,0.0781 G_comp( [rgb]1,0.4688,0.0781 tok,D) (15b) This follows directly from the definitions: writing p(s)=nsD/NDp_ θ( [rgb]0.8633,0.1953,0.5508s)=n_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD/N @scalerel@objD, and noting that NDN @scalerel@objD, the total number of tokens, is exactly comp(,) [rgb]1,0.4688,0.0781 G_comp( [rgb]1,0.4688,0.0781 tok,D), we get −∑sp(s)logp(s)=−1ND∑snsDlogp(s)=l(,)/ND- _ [rgb]0.8633,0.1953,0.5508sp_ θ( [rgb]0.8633,0.1953,0.5508s) p_ θ( [rgb]0.8633,0.1953,0.5508s)=- 1N @scalerel@objD _ [rgb]0.8633,0.1953,0.5508sn_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD p_ θ( [rgb]0.8633,0.1953,0.5508s)= [rgb]1,0.4688,0.0781 G_l( [rgb]1,0.4688,0.0781 tok,D)/N @scalerel@objD. 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, top-down methods achieve consistently lower entropy. Future work should further investigate this relationship between objective and search procedure. 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 Table 1. 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 Appendix J for a multilingual counterpart of this table. Distributional Properties of Tokens. Table 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. Figure 2 shows corresponding frequency–rank curves. Within each search family, the likelihood-based method induces a more concentrated token-frequency 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 comp [rgb]1,0.4688,0.0781 G_comp and l [rgb]1,0.4688,0.0781 G_l, the used objective is still visible in a tokenised corpus’ empirical token-frequency distribution. 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 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; Appendix 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. Vocabulary Composition. We now move on to analysing the composition of our tokenisers’ vocabularies. To this end, we compute their similarity, defined as |A∩B|/|A| | [rgb]0.8633,0.1953,0.5508S_A∩ [rgb]0.8633,0.1953,0.5508S_B|| [rgb]0.8633,0.1953,0.5508S_A|. Figure 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. Figure 4 in Appendix L shows the full set-overlap structure of all five vocabularies. Furthermore, per-example qualitative segmentations for the four tokenisers are shown in Appendix M. 7.2 Extrinsic Evaluation 100M 300M 500M 1B Vocab Tokeniser Objective Search BLiMP ↑ BPB ↓ BLiMP ↑ BPB ↓ BLiMP ↑ BPB ↓ BLiMP ↑ BPB ↓ 8k BPE comp [rgb]1,0.4688,0.0781 G_comp bottom-up .686 ± 6e-3 1.0736 ± 2e-4 .7707 .8739 .7744 .8435 – – TopDownComp comp [rgb]1,0.4688,0.0781 G_comp top-down .687 ± 4e-3 1.0750 ± 8e-4 .7699 .8758 .7938 .8441 – – BottomUpLL l [rgb]1,0.4688,0.0781 G_l bottom-up .703 ± 8e-3 1.0715 ± 6e-4 .7841 .8727 .7951 .8420 – – UnigramLM l [rgb]1,0.4688,0.0781 G_l top-down .698 ± 5e-3 1.0819 ± 4e-4 .7769 .8758 .7676 .8472 – – 32k BPE comp [rgb]1,0.4688,0.0781 G_comp bottom-up .714 ± 8e-3 1.0392 ± 5e-4 .7904 .8584 .7958 .8290 – – TopDownComp comp [rgb]1,0.4688,0.0781 G_comp top-down .727 ± 2e-2 1.0394 ± 3e-4 .7895 .8581 .7986 .8307 – – BottomUpLL l [rgb]1,0.4688,0.0781 G_l bottom-up .717 ± 7e-3 1.0374 ± 1e-4 .7827 .8564 .7899 .8281 – – UnigramLM l [rgb]1,0.4688,0.0781 G_l top-down .719 ± 8e-3 1.0441 ± 9e-4 .7776 .8610 .8015 .8337 – – 128k BPE comp [rgb]1,0.4688,0.0781 G_comp bottom-up .740 ± 4e-3 1.0138 ± 4e-4 .797 .8462 .813 .8210 .805 .7790 ± 4e-4 TopDownComp comp [rgb]1,0.4688,0.0781 G_comp top-down .740 ± 8e-3 1.0172 ± 4e-4 .797 .8492 .815 .8226 .816 .7816 ± 3e-4 BottomUpLL l [rgb]1,0.4688,0.0781 G_l bottom-up .725 ± 6e-3 1.0149 ± 9e-4 .792 .8467 .798 .8207 .799 .7803 ± 26e-4 UnigramLM l [rgb]1,0.4688,0.0781 G_l top-down .738 ± 7e-3 1.0298 ± 8e-4 .799 .8547 .803 .8283 .818 .7872 ± 1e-4 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 ↑ BPB ↓ Tokeniser Objective Search BLiMP ↑ eng deu spa tur cmn eng deu spa tur cmn BPE comp [rgb]1,0.4688,0.0781 G_comp bottom-up .812 .974 .955 .958 .890 .799 .8080 .9426 .9025 .8936 1.2464 TopDownComp comp [rgb]1,0.4688,0.0781 G_comp top-down .808 .969 .966 .956 .853 .718 .8276 .9711 .9284 .9260 1.3430 BottomUpLL l [rgb]1,0.4688,0.0781 G_l bottom-up .808 .970 .952 .950 .873 .803 .8082 .9416 .9030 .8929 1.2436 UnigramLM l [rgb]1,0.4688,0.0781 G_l top-down .803 .973 .964 .959 .897 .728 .8311 .9683 .9303 .9252 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 (Jumelet et al., 2026, eng, deu, spa, tur;), and ZhoBLiMP (Liu et al., 2026, cmn;). Lower is better for BPB; higher is better for minimal-pair accuracy. BPB. Tables 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.00030.0003 BPB); the likelihood-based pair (BottomUpLL vs. UnigramLM) favours bottom-up in every setting.1414 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 Appendix N). 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. Minimal-pair accuracy. Tables 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 top-down. In fact, in the English setting, top-down methods often outperform the bottom-up ones, 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 top-down 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 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 bits-per-byte. Our intrinsic evaluations also highlighted a surprising pattern: bottom-up tokenisers produced both more compressed and higher log-likelihood 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 procedures1515 15 Investigating the search procedures of, e.g.,Tempus et al. (2026) or Chizhov et al. (2024). in language modelling. 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. 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 high-resource, 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. 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. 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. 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%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 re-training the top-down tokenisers with pruning rates of 1%1\% and 0.1%0.1\% of the vocabulary per round, instead of the 10%10\% used in our main experiments: the resulting vocabularies overlap with the 10%10\% ones by over 97%97\% for UnigramLM and over 99%99\% for TopDownComp, suggesting that this approximation has a limited effect on the learned vocabulary. Details for both experiments are in Appendix O. Evaluation. Finally, we evaluate models with BPB and minimal-pair grammatical benchmarks (BLiMP, MultiBLiMP, ZhoBLiMP). We do not 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. References Chizhov et al. (2024) P. Chizhov, C. Arnett, E. Korotkova, and I. P. Yamshchikov BPE gets picky: efficient vocabulary refinement during tokenizer training. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, Y. Al-Onaizan, M. Bansal, and Y. Chen (Eds.), Miami, Florida, USA, p. 16587–16604. External Links: Link, Document Cited by: footnote 15. Gage (1994) P. Gage A new algorithm for data compression. C Users Journal 12 (2), p. 23–38. External Links: Link Cited by: §1. Hugging Face (2026) Hugging Face WordPiece tokenization. Note: Chapter 6.6 of the Hugging Face LLM Course, https://huggingface.co/learn/llm-course/en/chapter6/6Accessed August 2026 Cited by: §5.1. Jumelet et al. (2026) J. Jumelet, L. Weissweiler, J. Nivre, and A. Bisazza MultiBLiMP 1.0: a massively multilingual benchmark of linguistic minimal pairs. Transactions of the Association for Computational Linguistics 14, p. 193–216. External Links: Link Cited by: Appendix I, §6, Table 3. Kastreva et al. (2026) V. Kastreva, P. Whittington, D. Komm, and T. Pimentel Tokenisation over bounded alphabets is hard. In The Fourteenth International Conference on Learning Representations, External Links: Link Cited by: §3.2, footnote 1. Kozma and Voderholzer (2024) L. Kozma and J. Voderholzer Theoretical analysis of byte-pair encoding. arXiv preprint arXiv:2411.08671. External Links: Link Cited by: §3.2, footnote 1. Kudo (2018) T. Kudo 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), p. 66–75. External Links: Link Cited by: §1. Lesci et al. (2025) P. Lesci, C. Meister, T. Hofmann, A. Vlachos, and T. Pimentel Causal estimation of tokenisation bias. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), W. Che, J. Nabende, E. Shutova, and M. T. Pilehvar (Eds.), Vienna, Austria, p. 28325–28340. External Links: Link, Document, ISBN 979-8-89176-251-0 Cited by: §5.1. Liu et al. (2026) Y. Liu, Y. Shen, H. Zhu, L. Xu, Z. Qian, S. Song, K. Zhang, J. Tang, P. Zhang, B. Yang, R. Wang, and H. Hu A systematic assessment of language models with linguistic minimal pairs in Chinese. Transactions of the Association for Computational Linguistics 14, p. 755–771. External Links: Link, Document Cited by: Appendix I, §6, Table 3. Lozhkov et al. (2024) A. Lozhkov, L. Ben Allal, L. von Werra, and T. Wolf FineWeb-Edu: the finest collection of educational content. Hugging Face. External Links: Link, Document Cited by: §6, §6. Meister (2026) C. Meister UnigramLM: an attempt at writing the missing manual. In Proceedings of the Fourteenth International Conference on Learning Representations, Note: ICLR 2026 Blogpost Track External Links: Link Cited by: footnote 11. OpenAI et al. (2025) OpenAI, S. Agarwal, L. Ahmad, J. Ai, S. Altman, A. Applebaum, E. Arbus, R. K. Arora, Y. Bai, B. Baker, H. Bao, B. Barak, A. Bennett, T. Bertao, N. Brett, E. Brevdo, G. Brockman, S. Bubeck, C. Chang, K. Chen, M. Chen, E. Cheung, A. Clark, D. Cook, M. Dukhan, C. Dvorak, K. Fives, V. Fomenko, T. Garipov, K. Georgiev, M. Glaese, T. Gogineni, A. Goucher, L. Gross, K. G. Guzman, J. Hallman, J. Hehir, J. Heidecke, A. Helyar, H. Hu, R. Huet, J. Huh, S. Jain, Z. Johnson, C. Koch, I. Kofman, D. Kundel, J. Kwon, V. Kyrylov, E. Y. Le, G. Leclerc, J. P. Lennon, S. Lessans, M. Lezcano-Casado, Y. Li, Z. Li, J. Lin, J. Liss, Lily, Liu, J. Liu, K. Lu, C. Lu, Z. Martinovic, L. McCallum, J. McGrath, S. McKinney, A. McLaughlin, S. Mei, S. Mostovoy, T. Mu, G. Myles, A. Neitz, A. Nichol, J. Pachocki, A. Paino, D. Palmie, A. Pantuliano, G. Parascandolo, J. Park, L. Pathak, C. Paz, L. Peran, D. Pimenov, M. Pokrass, E. Proehl, H. Qiu, G. Raila, F. Raso, H. Ren, K. Richardson, D. Robinson, B. Rotsted, H. Salman, S. Sanjeev, M. Schwarzer, D. Sculley, H. Sikchi, K. Simon, K. Singhal, Y. Song, D. Stuckey, Z. Sun, P. Tillet, S. Toizer, F. Tsimpourlas, N. Vyas, E. Wallace, X. Wang, M. Wang, O. Watkins, K. Weil, A. Wendling, K. Whinnery, C. Whitney, H. Wong, L. Yang, Y. Yang, M. Yasunaga, K. Ying, W. Zaremba, W. Zhan, C. Zhang, B. Zhang, E. Zhang, and S. Zhao Gpt-oss-120b & gpt-oss-20b model card. arXiv preprint arXiv:2508.10925. External Links: Link Cited by: §1. Penedo et al. (2025) G. Penedo, H. Kydlíček, V. Sabolčec, B. Messmer, N. Foroutan, A. H. Kargaran, C. Raffel, M. Jaggi, L. Von Werra, and T. Wolf FineWeb2: one pipeline to scale them all – adapting pre-training data processing to every language. arXiv preprint arXiv:2506.20920. External Links: Link Cited by: §6. Schmidt et al. (2024) C. W. Schmidt, V. Reddy, H. Zhang, A. Alameddine, O. Uzan, Y. Pinter, and C. Tanner Tokenization is more than compression. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, p. 678–702. External Links: Link Cited by: §1, §5.1, §5.2. Schuster and Nakajima (2012) M. Schuster and K. Nakajima Japanese and Korean voice search. In 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Vol. , p. 5149–5152. External Links: Link, Document Cited by: §5.1. Sennrich et al. (2016) R. Sennrich, B. Haddow, and A. Birch 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), p. 1715–1725. External Links: Link Cited by: §1. Team et al. (2026) K. Team, T. Bai, Y. Bai, Y. Bao, S. H. Cai, Y. Cao, Z. Chai, Y. Charles, H. S. Che, C. Chen, G. Chen, H. Chen, J. Chen, J. Chen, J. Chen, K. Chen, L. Chen, R. Chen, X. Chen, Y. Chen, Y. Chen, Y. Chen, Y. Chen, Y. Chen, Y. Chen, Y. Chen, Y. Chen, Z. Chen, Z. Chen, D. Cheng, Y. Cheng, M. Chu, J. Cui, J. Deng, M. Diao, H. Ding, M. Dong, M. Dong, Y. Dong, Y. Dong, A. Du, C. Du, D. Du, L. Du, Y. Du, Y. Fan, S. Fang, Q. Feng, Y. Feng, G. Fu, K. Fu, H. Gao, T. Gao, Y. Ge, S. Geng, C. Gong, X. Gong, Z. Gongque, Q. Gu, X. Gu, Y. Gu, L. Guan, S. Guan, Y. Guo, X. Hao, D. He, T. He, W. He, W. He, Y. He, Y. He, C. Hong, H. Hu, J. Hu, Y. Hu, Z. Hu, K. Huang, R. Huang, W. Huang, Z. Huang, C. Jia, T. Jiang, Z. Jiang, X. Jin, Y. Jing, G. Lai, A. Li, C. Li, C. Li, F. Li, G. Li, G. Li, H. Li, H. Li, J. Li, J. Li, J. Li, L. Li, M. Li, W. Li, W. Li, X. Li, X. Li, Y. Li, Y. Li, Y. Li, Y. Li, Z. Li, Z. Li, Z. Li, W. Liao, J. Lin, X. Lin, Y. Lin, Z. Lin, Z. Lin, C. Liu, C. Liu, H. Liu, L. Liu, S. Liu, S. Liu, S. Liu, T. Liu, T. Liu, W. Liu, X. Liu, Y. Liu, Y. Liu, Y. Liu, Y. Liu, Z. Liu, Z. Liu, E. Lu, H. Lu, Z. Lu, G. Luo, J. Luo, T. Luo, Y. Luo, L. Ma, S. Mao, Y. Mei, X. Men, F. Meng, Z. Meng, Y. Miao, M. Ni, K. Ouyang, S. Pan, B. Pang, Y. Qian, R. Qin, Z. Qin, J. Qiu, B. Qu, Z. Shang, Y. Shao, T. Shen, Z. Shen, J. Shi, L. Shi, S. Shi, F. Song, P. Song, T. Song, X. Song, H. Su, J. Su, Z. Su, L. Sui, J. Sun, J. Sun, T. Sun, F. Sung, Y. Tai, C. Tang, H. Tang, X. Tang, Z. Tang, J. Tao, S. Teng, C. Tian, P. Tian, B. Wang, C. Wang, C. Wang, C. Wang, D. Wang, D. Wang, D. Wang, F. Wang, H. Wang, H. Wang, H. Wang, H. Wang, H. Wang, H. Wang, J. Wang, J. Wang, J. Wang, K. Wang, L. Wang, Q. Wang, S. Wang, S. Wang, S. Wang, W. Wang, X. Wang, X. Wang, Y. Wang, Y. Wang, Y. Wang, Y. Wang, Y. Wang, Y. Wang, Z. Wang, Z. Wang, Z. Wang, Z. Wang, Z. Wang, Z. Wang, Z. Wang, C. Wei, M. Wei, C. Wen, Z. Wen, C. Wu, H. Wu, J. Wu, R. Wu, W. Wu, Y. Wu, Y. Wu, Y. Wu, Z. Wu, C. Xiao, J. Xie, X. Xie, Y. Xie, B. Xing, B. Xu, J. Xu, J. Xu, J. Xu, L. H. Xu, L. Xu, S. Xu, W. Xu, X. Xu, X. Xu, Y. Xu, Y. Xu, Y. Xu, Z. Xu, Z. Xu, J. Yan, Y. Yan, G. Yang, H. Yang, J. Yang, K. Yang, N. Yang, X. Yang, X. Yang, X. Yang, Y. Yang, Y. Yang, Y. Yang, Z. Yang, Z. Yang, Z. Yang, H. Yao, D. Ye, H. Ye, W. Ye, Z. Ye, P. Yebo, B. Yin, C. Yu, L. Yu, T. Yu, T. Yu, E. Yuan, M. Yuan, X. Yuan, Y. Yue, W. Zeng, D. Zha, H. Zhan, D. Zhang, H. Zhang, J. Zhang, P. Zhang, Q. Zhang, R. Zhang, X. Zhang, X. Zhang, Y. Zhang, Y. Zhang, Y. Zhang, Y. Zhang, Y. Zhang, Y. Zhang, Y. Zhang, Y. Zhang, Y. Zhang, Y. Zhang, Z. Zhang, C. Zhao, F. Zhao, J. Zhao, S. Zhao, X. Zhao, X. Zhao, Y. Zhao, Z. Zhao, H. Zheng, R. Zheng, S. Zheng, T. Zheng, J. Zhong, L. Zhong, W. Zhong, M. Zhou, R. Zhou, X. Zhou, Z. Zhou, J. Zhu, L. Zhu, X. Zhu, Y. Zhu, Z. Zhu, J. Zhuang, W. Zhuang, Y. Zou, and X. Zu Kimi K2.5: visual agentic intelligence. arXiv preprint arXiv:2602.02276. External Links: Link Cited by: §1. Team (2026) Q. Team Qwen3.5-Omni technical report. arXiv preprint arXiv:2604.15804. External Links: Link Cited by: §1. Tempus et al. (2026) J. Tempus, P. Whittington, C. W. Schmidt, D. Komm, and T. Pimentel Tokenisation via convex relaxations. arXiv preprint arXiv:2605.22821. External Links: 2605.22821, Link Cited by: footnote 15. Vilar and Federico (2021) D. Vilar and M. Federico A statistical extension of byte-pair encoding. In Proceedings of the 18th International Conference on Spoken Language Translation (IWSLT 2021), p. 263–275. External Links: Link Cited by: §5.1. Warstadt et al. (2020) A. Warstadt, A. Parrish, H. Liu, A. Mohananey, W. Peng, S. Wang, and S. R. Bowman BLiMP: the benchmark of linguistic minimal pairs for English. Transactions of the Association for Computational Linguistics 8, p. 377–392. External Links: Link, Document Cited by: Appendix I, §6, Table 3. Whittington et al. (2025) P. Whittington, G. Bachmann, and T. Pimentel Tokenisation is NP-complete. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 28133–28153. External Links: Link Cited by: §3.2, footnote 1. Wolf et al. (2020) T. Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, P. Cistac, T. Rault, R. Louf, M. Funtowicz, J. Davison, S. Shleifer, P. von Platen, C. Ma, Y. Jernite, J. Plu, C. Xu, T. Le Scao, S. Gugger, M. Drame, Q. Lhoest, and A. Rush Transformers: state-of-the-art natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, Q. Liu and D. Schlangen (Eds.), Online, p. 38–45. External Links: Link, Document Cited by: §5.1. Wu et al. (2016) Y. Wu, M. Schuster, Z. Chen, Q. V. Le, M. Norouzi, W. Macherey, M. Krikun, Y. Cao, Q. Gao, K. Macherey, J. Klingner, A. Shah, M. Johnson, X. Liu, Ł. Kaiser, S. Gouws, Y. Kato, T. Kudo, H. Kazawa, K. Stevens, G. Kurian, N. Patil, W. Wang, C. Young, J. Smith, J. Riesa, A. Rudnick, O. Vinyals, G. Corrado, M. Hughes, and J. Dean Google’s neural machine translation system: bridging the gap between human and machine translation. arXiv preprint arXiv:1609.08144. External Links: Link Cited by: §5.1, footnote 12. Appendix A Proof of Lemma 1 See 1 Proof. To prove this is the case, first note that replacing a token-pair m=⟨s1,s2⟩ [rgb]0.8633,0.1953,0.5508m= [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 with merged token s1∘s2 [rgb]0.8633,0.1953,0.5508s^1 [rgb]0.8633,0.1953,0.5508s^2 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: (↑[<k],)−(↑[<k∘⟨s1,s2⟩],) [rgb]1,0.4688,0.0781 G( [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508m_<k],D)- [rgb]1,0.4688,0.0781 G( [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508m_<k [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 ],D) =ns1,s2D. =n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD. (16) We can now trivially conclude the proof: m⋆ [rgb]0.8633,0.1953,0.5508m =argminm∈Σ+×Σ+(↑[<k∘m],) = _ [rgb]0.8633,0.1953,0.5508m∈ [rgb]0.2734,0.4688,1 ^+× [rgb]0.2734,0.4688,1 ^+ [rgb]1,0.4688,0.0781 G( [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508m_<k [rgb]0.8633,0.1953,0.5508m],D) (17a) =argmaxm∈Σ+×Σ+−(↑[<k∘m],) = _ [rgb]0.8633,0.1953,0.5508m∈ [rgb]0.2734,0.4688,1 ^+× [rgb]0.2734,0.4688,1 ^+- [rgb]1,0.4688,0.0781 G( [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508m_<k [rgb]0.8633,0.1953,0.5508m],D) (17b) =argmaxm∈Σ+×Σ+(↑[<k],) = _ [rgb]0.8633,0.1953,0.5508m∈ [rgb]0.2734,0.4688,1 ^+× [rgb]0.2734,0.4688,1 ^+ [rgb]1,0.4688,0.0781 G( [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508m_<k],D) (17c) −(↑[<k∘m],) - [rgb]1,0.4688,0.0781 G( [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508m_<k [rgb]0.8633,0.1953,0.5508m],D) =argmax⟨s1,s2⟩∈Σ+×Σ+ns1,s2D. = _ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 ∈ [rgb]0.2734,0.4688,1 ^+× [rgb]0.2734,0.4688,1 ^+n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD. (17d) This concludes the proof. ∎ Appendix B Updating Counts in bottom-up Procedures 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⟩ \_to\_words: [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 (18) ↦word types containing ⟨s1,s2⟩, \word types containing [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 \, 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⟩ [rgb]0.8633,0.1953,0.5508m= [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 is selected, write snew=defs1∘s2. [rgb]0.8633,0.1953,0.5508s^new def= [rgb]0.8633,0.1953,0.5508s^1 [rgb]0.8633,0.1953,0.5508s^2. Each affected word type is scanned through its linked token sequence, and non-overlapping occurrences of ⟨s1,s2⟩ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 are replaced by snew [rgb]0.8633,0.1953,0.5508s^new. 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 ⟨sℓ,s1,s2,sr⟩ [rgb]0.8633,0.1953,0.5508s , [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2, [rgb]0.8633,0.1953,0.5508s^r (19) is replaced by ⟨sℓ,snew,sr⟩, [rgb]0.8633,0.1953,0.5508s , [rgb]0.8633,0.1953,0.5508s^new, [rgb]0.8633,0.1953,0.5508s^r , (20) where sℓ [rgb]0.8633,0.1953,0.5508s and sr [rgb]0.8633,0.1953,0.5508s^r denote the immediate left and right neighbours, if they exist. Therefore, only token-pairs in this local neighbourhood can change. The old token-pairs ⟨sℓ,s1⟩,⟨s1,s2⟩,⟨s2,sr⟩ [rgb]0.8633,0.1953,0.5508s , [rgb]0.8633,0.1953,0.5508s^1 , [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 , [rgb]0.8633,0.1953,0.5508s^2, [rgb]0.8633,0.1953,0.5508s^r (21) are removed, and the new token-pairs ⟨sℓ,snew⟩,⟨snew,sr⟩ [rgb]0.8633,0.1953,0.5508s , [rgb]0.8633,0.1953,0.5508s^new , [rgb]0.8633,0.1953,0.5508s^new, [rgb]0.8633,0.1953,0.5508s^r (22) are added. Boundary cases are handled by omitting updates involving missing neighbours. For one merged occurrence, the affected pair counts are updated as nsℓ,s1D n_ [rgb]0.8633,0.1953,0.5508s , [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD ←nsℓ,s1D−1, ← n_ [rgb]0.8633,0.1953,0.5508s , [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD-1, (23a) ns1,s2D n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD ←ns1,s2D−1, ← n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD-1, (23b) ns2,srD n_ [rgb]0.8633,0.1953,0.5508s^2, [rgb]0.8633,0.1953,0.5508s^r @scalerel@objD ←ns2,srD−1, ← n_ [rgb]0.8633,0.1953,0.5508s^2, [rgb]0.8633,0.1953,0.5508s^r @scalerel@objD-1, (23c) nsℓ,snewD n_ [rgb]0.8633,0.1953,0.5508s , [rgb]0.8633,0.1953,0.5508s^new @scalerel@objD ←nsℓ,snewD+1, ← n_ [rgb]0.8633,0.1953,0.5508s , [rgb]0.8633,0.1953,0.5508s^new @scalerel@objD+1, (23d) nsnew,srD n_ [rgb]0.8633,0.1953,0.5508s^new, [rgb]0.8633,0.1953,0.5508s^r @scalerel@objD ←nsnew,srD+1. ← n_ [rgb]0.8633,0.1953,0.5508s^new, [rgb]0.8633,0.1953,0.5508s^r @scalerel@objD+1. (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 ns1,s2Dn_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD denotes the frequency-weighted number of non-overlapping occurrences of the selected pair that are actually merged, then the unigram counts are updated as ns1D n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD ←ns1D−ns1,s2D, ← n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD-n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD, (24a) ns2D n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD ←ns2D−ns1,s2D, ← n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD-n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD, (24b) nsnewD n_ [rgb]0.8633,0.1953,0.5508s^new @scalerel@objD ←ns1,s2D, ← n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD, (24c) ND N @scalerel@objD ←ND−ns1,s2D. ← N @scalerel@objD-n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD. (24d) 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. Appendix C Proof of Lemma 2 See 2 Proof. We prove the result by explicitly writing the corpus log-likelihood before and after applying the merge. Let the current tokenised corpus contain NDN @scalerel@objD tokens in total. For each token s~ [rgb]0.8633,0.1953,0.5508s, let ns~Dn_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD denote its corpus count. Under the unigram token model, the empirical probability of s~ [rgb]0.8633,0.1953,0.5508s is p(s~)=ns~DND. p_ θ( [rgb]0.8633,0.1953,0.5508s)= n_ [rgb]0.8633,0.1953,0.5508s @scalerel@objDN @scalerel@objD. (25) Therefore, the corpus log-likelihood before applying the merge is ℒbefore _before =∑s~ns~Dlogp(s~) = _ [rgb]0.8633,0.1953,0.5508sn_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD p_ θ( [rgb]0.8633,0.1953,0.5508s) (26a) =∑s~ns~Dlogns~DND = _ [rgb]0.8633,0.1953,0.5508sn_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD n_ [rgb]0.8633,0.1953,0.5508s @scalerel@objDN @scalerel@objD (26b) =∑s~ns~Dlogns~D−NDlogND. = _ [rgb]0.8633,0.1953,0.5508sn_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD n_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD-N @scalerel@objD N @scalerel@objD. (26c) Now consider merging the token-pair ⟨s1,s2⟩ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 into the new token s1∘s2 [rgb]0.8633,0.1953,0.5508s^1 [rgb]0.8633,0.1953,0.5508s^2. For readability, write κ=defns1,s2D, κ def=n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD, (27) Assuming s1≠s2 [rgb]0.8633,0.1953,0.5508s^1≠ [rgb]0.8633,0.1953,0.5508s^2, applying this merge changes only the counts of s1 [rgb]0.8633,0.1953,0.5508s^1, s2 [rgb]0.8633,0.1953,0.5508s^2, and the new token s1∘s2 [rgb]0.8633,0.1953,0.5508s^1 [rgb]0.8633,0.1953,0.5508s^2. Specifically, ns1D n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD ↦ns1D−κ, n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD-κ, (28a) ns2D n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD ↦ns2D−κ, n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD-κ, (28b) ns1∘s2D n_ [rgb]0.8633,0.1953,0.5508s^1 [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD ↦κ. κ. (28c) All other token counts remain unchanged. Since each merged occurrence replaces two tokens by one token, the total token count changes from NDN @scalerel@objD to ND−κN @scalerel@objD-κ. The log-likelihood after the merge is therefore ℒafter _after =∑s~∉s1,s2,s1∘s2ns~Dlogns~D = _ [rgb]0.8633,0.1953,0.5508s∉\ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2, [rgb]0.8633,0.1953,0.5508s^1 [rgb]0.8633,0.1953,0.5508s^2\n_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD n_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD (29) +(ns1D−κ)log(ns1D−κ) + (n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD-κ ) (n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD-κ ) +(ns2D−κ)log(ns2D−κ) + (n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD-κ ) (n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD-κ ) +κlogκ−(ND−κ)log(ND−κ). +κ κ-(N @scalerel@objD-κ) (N @scalerel@objD-κ). and the log-likelihood change due to the merge is Δs1,s2l(⋅,)=ℒafter−ℒbefore. _ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 [rgb]1,0.4688,0.0781 G_l(·,D)=L_after-L_before. (30) Substituting Eqs. 26c and 29, all unchanged token-count terms cancel, leaving Δs1,s2l(⋅,) _ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 [rgb]1,0.4688,0.0781 G_l(·,D) =(ns1D−κ)log(ns1D−κ) = (n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD-κ ) (n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD-κ ) (31) −ns1Dlogns1D -n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD +(ns2D−κ)log(ns2D−κ) + (n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD-κ ) (n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD-κ ) −ns2Dlogns2D -n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD +κlogκ +κ κ −(ND−κ)log(ND−κ)+NDlogND. -(N @scalerel@objD-κ) (N @scalerel@objD-κ)+N @scalerel@objD N @scalerel@objD. which completes the proof. ∎ Appendix D Proof of Lemma 3 See 3 Proof. We prove the result under the local replacement approximation stated in the lemma. That is, when scoring the deletion of s [rgb]0.8633,0.1953,0.5508s, 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 [rgb]0.8633,0.1953,0.5508s with a replacement segmentation under ∖s [rgb]0.8633,0.1953,0.5508S \ [rgb]0.8633,0.1953,0.5508s\. For UnigramLM, token usage is measured by expected counts under the current posterior over valid segmentations. Thus, nsDn_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD is the expected number of times s [rgb]0.8633,0.1953,0.5508s is used in the corpus. Before deleting s [rgb]0.8633,0.1953,0.5508s, each such expected occurrence contributes −logp(s) - p_ θ( [rgb]0.8633,0.1953,0.5508s) (32) to the negative log-likelihood objective. After deleting s [rgb]0.8633,0.1953,0.5508s, the token can no longer be used as a single token. Under the local replacement approximation, each occurrence of s [rgb]0.8633,0.1953,0.5508s is replaced by the highest-probability valid segmentation of the same string under the reduced vocabulary: srep=defargmax~∈(∖s)∗s=∘~p(~). [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s def= _ subarrayc [rgb]0.8633,0.1953,0.5508s∈( [rgb]0.8633,0.1953,0.5508S \ [rgb]0.8633,0.1953,0.5508s\)^*\\ [rgb]0.8633,0.1953,0.5508s = [rgb]0.8633,0.1953,0.5508s subarrayp_ θ( [rgb]0.8633,0.1953,0.5508s). (33) Since p_ θ is a unigram model, the probability of this replacement token-string is p(srep)=∏s~∈srepp(s~). p_ θ( [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s)= _ [rgb]0.8633,0.1953,0.5508s∈ [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508sp_ θ( [rgb]0.8633,0.1953,0.5508s). (34) After replacement, each expected occurrence therefore contributes −logp(srep) - p_ θ( [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s) (35) to the negative log-likelihood objective. Hence, the estimated increase in negative log-likelihood for one expected occurrence of s [rgb]0.8633,0.1953,0.5508s is −logp(srep)−(−logp(s)) - p_ θ( [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s)- (- p_ θ( [rgb]0.8633,0.1953,0.5508s) ) =logp(s)−logp(srep). = p_ θ( [rgb]0.8633,0.1953,0.5508s)- p_ θ( [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s). (36) Multiplying this per-occurrence increase by the expected number of occurrences nsDn_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD gives Δsll(⋅,)≈nsD(logp(s)−logp(srep)). _ [rgb]0.8633,0.1953,0.5508s [rgb]1,0.4688,0.0781 G_l(·,D)≈ n_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD ( p_ θ( [rgb]0.8633,0.1953,0.5508s)- p_ θ( [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s) ). (37) This proves the stated local approximation. ∎ Appendix E Proof of Lemma 4 See 4 Proof. Let [rgb]0.8633,0.1953,0.5508S be the current vocabulary, and suppose the corpus has already been segmented using the TopDownComp encoding rule: ⇒[]()=argmin∈∗=∘||. [rgb]1,0.4688,0.0781 tok_ [ [rgb]0.8633,0.1953,0.5508S]( [rgb]0.2734,0.4688,1c)= _ subarrayc [rgb]0.8633,0.1953,0.5508s∈ [rgb]0.8633,0.1953,0.5508S^*\\ [rgb]0.2734,0.4688,1c = [rgb]0.8633,0.1953,0.5508s subarray| [rgb]0.8633,0.1953,0.5508s|. (38) Now consider deleting a token s∈∖Σ [rgb]0.8633,0.1953,0.5508s∈ [rgb]0.8633,0.1953,0.5508S [rgb]0.2734,0.4688,1 . Before deletion, each current occurrence of s [rgb]0.8633,0.1953,0.5508s contributes exactly one token to the corpus token count. Therefore, the total contribution of all current occurrences of s [rgb]0.8633,0.1953,0.5508s before deletion is Cbefore(s)=nsD. C_before( [rgb]0.8633,0.1953,0.5508s)=n_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD. (39) After deleting s [rgb]0.8633,0.1953,0.5508s, the token s [rgb]0.8633,0.1953,0.5508s can no longer appear as a single token. Under the local replacement calculation, each current occurrence of s [rgb]0.8633,0.1953,0.5508s is independently replaced by its shortest decomposition under the reduced vocabulary ∖s [rgb]0.8633,0.1953,0.5508S \ [rgb]0.8633,0.1953,0.5508s\, denoted srep [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s: srep=argmin′∈(∖s)∗s=∘′|′|. [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s= _ subarrayc [rgb]0.8633,0.1953,0.5508s ∈( [rgb]0.8633,0.1953,0.5508S \ [rgb]0.8633,0.1953,0.5508s\)^*\\ [rgb]0.8633,0.1953,0.5508s = [rgb]0.8633,0.1953,0.5508s subarray| [rgb]0.8633,0.1953,0.5508s |. (40) Thus, under this local replacement calculation, each previous occurrence of s [rgb]0.8633,0.1953,0.5508s contributes |srep|| [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s| tokens instead of one token. The total contribution of these occurrences after deletion is Cafter(s)=nsD|srep|. C_after( [rgb]0.8633,0.1953,0.5508s)=n_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD| [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s|. (41) Therefore, the estimated increase in corpus length caused by locally replacing all current occurrences of s [rgb]0.8633,0.1953,0.5508s is Δscomp(⋅,) _ [rgb]0.8633,0.1953,0.5508s [rgb]1,0.4688,0.0781 G_comp(·,D) =Cafter(s)−Cbefore(s) =C_after( [rgb]0.8633,0.1953,0.5508s)-C_before( [rgb]0.8633,0.1953,0.5508s) (42a) =nsD|srep|−nsD =n_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD| [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s|-n_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD (42b) =nsD(|srep|−1). =n_ [rgb]0.8633,0.1953,0.5508s @scalerel@objD (| [rgb]0.8633,0.1953,0.5508s^rep_ [rgb]0.8633,0.1953,0.5508s|-1 ). (42c) which completes this proof. ∎ Appendix F Proof of Lemma 5 See 5 Proof. As in App. C, we write κ=defns1,s2Dκ def=n_ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD. Starting from Eq. 31, we have Δs1,s2l(⋅,)= _ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 [rgb]1,0.4688,0.0781 G_l(·,D)= (43) (ns1D−κ)log(ns1D−κ)−ns1Dlogns1D (n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD-κ ) (n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD-κ )-n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD +(ns2D−κ)log(ns2D−κ)−ns2Dlogns2D + (n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD-κ ) (n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD-κ )-n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD +κlogκ +κ κ −(ND−κ)log(ND−κ)+NDlogND. -(N @scalerel@objD-κ) (N @scalerel@objD-κ)+N @scalerel@objD N @scalerel@objD. Now, define f(a)=alogaf(a)=a a, which implies f′(a)=loga+1f (a)= a+1. A first-order Taylor expansion of f(a)f(a) around point x gives f(a) f(a) ≈f(x)+(a−x)f′(x) ≈ f(x)+(a-x)f (x) (44a) f(x−κ) f(x-κ) ≈f(x)+(x−κ−x)f′(x) ≈ f(x)+(x-κ-x)f (x) (44b) =f(x)−κf′(x) =f(x)-κ f (x) (44c) =xlogx−κ(logx+1) =x x-κ( x+1) (44d) This approximation is accurate whenever κ≪xκ x: the neglected remainder is 12κ2f′(ξ)=O(κ2/x) 12κ^2f (ξ)=O(κ^2/x), which is small relative to the retained term κ(logx+1)κ( x+1) exactly in that regime. Now, choosing x=ns1Dx=n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD, we get f(ns1D−κ) f(n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD-κ) =(ns1D−κ)log(ns1D−κ) = (n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD-κ ) (n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD-κ ) (45a) ≈ns1Dlogns1D−κ(logns1D+1). ≈ n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD-κ ( n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD+1 ). (45b) which implies (ns1D−κ)log(ns1D−κ)−ns1Dlogns1D (n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD-κ ) (n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD-κ )-n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD (46) ≈−κ(logns1D+1). ≈-κ ( n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD+1 ). With similar results for x=ns2Dx=n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD and x=NDx=N @scalerel@objD. Substituting these terms into Eq. 43, we get Δs1,s2l(⋅,) _ [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2 [rgb]1,0.4688,0.0781 G_l(·,D) ≈−κ(logns1D+1)−κ(logns2D+1) ≈-κ ( n_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objD+1 )-κ ( n_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD+1 ) +κlogκ+κ(logND+1) +κ κ+κ ( N @scalerel@objD+1 ) (47a) =κ(logNDκns1Dns2D−1) =κ ( N @scalerel@objD\,κn_ [rgb]0.8633,0.1953,0.5508s^1 @scalerel@objDn_ [rgb]0.8633,0.1953,0.5508s^2 @scalerel@objD-1 ) (47b) =κ(PMIadj(s1,s2)−1). =κ (PMI_adj( [rgb]0.8633,0.1953,0.5508s^1, [rgb]0.8633,0.1953,0.5508s^2)-1 ). (47c) which completes the proof. ∎ Appendix G Tokeniser Training Details 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: ByteLevel(add_prefix_space=True, trim_offsets=True, use_regex=True) ByteLevel(add_prefix_space=True, trim_offsets=False, use_regex=True) 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. Appendix H Hyperparameters and Architecture All language models follow a Llama-style decoder-only architecture. Table 4 summarises the per-size architectural settings. All models use SiLU activations, grouped-query attention with separate K/VK/V head counts, RMSNorm, and rotary positional embeddings (RoPE, θ=10,000θ=10,000). Size Hidden Intermediate Heads KV heads Layers Tied 100M 576 1,536 9 3 30 ✓ 300M 960 2,560 15 5 32 ✓ 500M 1280 3,456 16 4 26 ✓ 1B 2048 5,632 32 4 22 ✓ Table 4: Per-size architecture for the Llama-style language models. “Tied” denotes weight tying between input and output embeddings. Optimisation. We train models with AdamW using learning rate ×10−43\!×\!10^-4, β1=0.9 _1\!=\!0.9, β2=0.95 _2\!=\!0.95, weight decay 0.10.1, and a maximum gradient norm of 1.01.0. The learning-rate schedule is warmup–stable–decay with 2,0002,000 warmup steps, a stable phase, and 10,00010,000 linear-decay steps, ending with a final learning rate of 10%10\% of its peak value. Training setup. All models are trained at sequence length 2,0482,048 in bf16-mixed precision with FlashAttention 2. The per-device batch size is 3232, 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×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 open-source training stack. Appendix I Detailed Metric Definitions This section gives precise definitions for every metric used in the paper. Let D denote a held-out corpus, NbytesN_bytes its size in UTF-8 bytes, and NDN @scalerel@objD 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 −log2Pθ()/Nbytes- _2P_θ(D)/N_bytes: 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. Intrinsic. We evaluate models on 5 types of intrinsic metrics. Compression is comp=ND [rgb]1,0.4688,0.0781 G_comp=N @scalerel@objD, i.e., the corpus token count, where lower means more compact. Bytes per token (BPT) is defined as Nbytes/NDN_bytes/N @scalerel@objD, 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. (Unigram) Entropy is defined here as H=−∑sp(s)log2p(s)H=- _ [rgb]0.8633,0.1953,0.5508sp_ θ( [rgb]0.8633,0.1953,0.5508s) _2p_ θ( [rgb]0.8633,0.1953,0.5508s), where p(s)p_ θ( [rgb]0.8633,0.1953,0.5508s) is a unigram language model trained on token counts. Unigram log-likelihood objective is l=H⋅ND [rgb]1,0.4688,0.0781 G_l=H· N @scalerel@objD, 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. Vocabulary overlap. Finally, we also compute vocabulary overlap between tokenisers. For two tokenisers A and B, their overlap is measured as |A∩B|/|A| | [rgb]0.8633,0.1953,0.5508S_A∩ [rgb]0.8633,0.1953,0.5508S_B|| [rgb]0.8633,0.1953,0.5508S_A|, where A [rgb]0.8633,0.1953,0.5508S_A and B [rgb]0.8633,0.1953,0.5508S_B are their learned vocabularies. This measure is symmetric for tokenisers with equal vocabulary size. Appendix J English vs. Multilingual Intrinsic Comparison This appendix reports the multilingual counterpart of Tables 1 and 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. Table 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. Setting Tokeniser Objective Search comp [rgb]1,0.4688,0.0781 G_comp ↓ l [rgb]1,0.4688,0.0781 G_l ↓ Entropy Zipf α BPT ↑ Tok Len Vocab Util ↑ Coverage 50% English BPE comp [rgb]1,0.4688,0.0781 G_comp bottom-up 46,859,565 5.216×1085.216× 10^8 11.132 1.484 4.886 7.06 98.9% 204 TopDownComp comp [rgb]1,0.4688,0.0781 G_comp top-down 50,312,483 5.484×1085.484× 10^8 10.900 1.443 4.551 6.01 99.8% 149 BottomUpLL l [rgb]1,0.4688,0.0781 G_l bottom-up 47,111,733 5.203× 5.203× 10^8 11.044 1.574 4.860 7.48 96.8% 191 UnigramLM l [rgb]1,0.4688,0.0781 G_l top-down 55,546,423 5.552×1085.552× 10^8 9.996 1.717 4.122 6.46 97.1% 53 Multilingual BPE comp [rgb]1,0.4688,0.0781 G_comp bottom-up 172,372,100 2.262×1092.262× 10^9 13.122 1.247 4.675 6.96 99.92% 1,483 TopDownComp comp [rgb]1,0.4688,0.0781 G_comp top-down 217,983,502 2.678×1092.678× 10^9 12.286 1.266 3.696 5.52 99.94% 618 BottomUpLL l [rgb]1,0.4688,0.0781 G_l bottom-up 173,917,215 2.245× 2.245× 10^9 12.907 1.347 4.633 7.40 99.36% 1,114 UnigramLM l [rgb]1,0.4688,0.0781 G_l top-down 240,669,745 2.597×1092.597× 10^9 10.791 1.598 3.348 6.79 99.74% 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. Distributional shape changes with the evaluation corpus. Table 5 reports the full intrinsic statistics in both settings. All four token distributions flatten in the multilingual setting: Zipf α values 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 compression-based counterparts within each search family. 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. Table 6 is the multilingual counterpart of Figure 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. BPE TopDownComp BottomUpLL UnigramLM BPE — 37.0% 80.5% 32.3% TopDownComp 37.0% — 33.6% 63.6% BottomUpLL 80.5% 33.6% — 31.2% UnigramLM 32.3% 63.6% 31.2% — Table 6: Multilingual vocabulary overlap at 128k vocabulary size; the multilingual counterpart of Figure 3. Appendix K 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 used on its own. It only becomes wasteful when the absorbed token reduces in frequency enough to be considered not-useful any more. Metric BPE BottomUpLL BottomUpLL (Exact) (Approx) Total absorbed 34,224 41,599 41,751 Absorption rate (all) 26.8% 32.6% 32.7% Absorption rate (|s|≥5| [rgb]0.8633,0.1953,0.5508s|≥ 5) 21.7% 27.8% 27.9% Absorption rate (|s|≥10| [rgb]0.8633,0.1953,0.5508s|≥ 10) 4.5% 8.5% 8.8% Absorbed with zero usage 3.5% 9.2% 8.7% Absorbed with low usage (≤10≤ 10) 26.2% 36.9% 36.0% Not absorbed, zero usage .2% .4% .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. Table 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. 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. Appendix L Vocabulary Overlap Structure Figure 3 reports pairwise vocabulary overlap in English, but pairwise numbers cannot show how the five vocabularies intersect jointly. Figure 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 top-down methods retain the largest exclusive regions, and cross-family regions are comparatively small. Appendix M Qualitative Examples 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. Table 8 reports the total number of tokens produced across the 10 illustrative examples. The ordering broadly matches the full compression benchmark. Method # of Tokens ↓ BPE 156 TopDownComp 160 BottomUpLL (Exact) 154 BottomUpLL (Approx) 153 UnigramLM 173 Table 8: Total number of tokens produced across 10 illustrative test examples. Lower is better. Scientific and medical terminology. On examples such as: (i) Photosynthesis converts carbon dioxide and water into glucose and oxygen. or (i) Electroencephalography is used to diagnose neurological disorders. 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. Code and punctuation-heavy text. On code-like or SQL-like strings, BPE is usually strongest. For example, on: (i) 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. URL-like text. For URL strings such as: (iv) https://w.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 Table 3, where bottom-up 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. 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. Take away. Together, these examples illustrate the same qualitative biases seen in the aggregate analyses: BPE is robust on punctuation-heavy and 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. Appendix 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,38447,384 documents). In each of 10,00010,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. Table 9 reports point estimates and 95%95\% confidence intervals for the 128k-vocabulary models, using seed 42 for each configuration. Size Comparison Δ BPB 95% CI 300M BPE vs. TopDownComp −0.0031-0.0031 [−0.0032,−0.0029][-0.0032,-0.0029] BottomUpLL vs. UnigramLM −0.0080-0.0080 [−0.0082,−0.0078][-0.0082,-0.0078] 500M BPE vs. TopDownComp −0.0016-0.0016 [−0.0017,−0.0014][-0.0017,-0.0014] BottomUpLL vs. UnigramLM −0.0075-0.0075 [−0.0077,−0.0074][-0.0077,-0.0074] 1B BPE vs. TopDownComp −0.0025-0.0025 [−0.0027,−0.0023][-0.0027,-0.0023] BottomUpLL vs. UnigramLM −0.0039-0.0039 [−0.0041,−0.0037][-0.0041,-0.0037] Table 9: Paired document-level bootstrap (10,00010,000 resamples) of BPB differences between objective-matched 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 bottom-up 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. 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. Table 10 reports the per-seed BPB values. Both objective-matched orderings are preserved in the mean: BPE outperforms TopDownComp, and BottomUpLL outperforms UnigramLM. We note that BottomUpLL 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. Seed Tokeniser 42 43 44 Mean BPE 0.7795 0.7787 0.7787 0.7790 ± 4e-4 TopDownComp 0.7819 0.7817 0.7813 0.7816 ± 3e-4 BottomUpLL 0.7833 0.7789 0.7787 0.7803 ± 26e-4 UnigramLM 0.7872 0.7871 0.7873 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. Appendix 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%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%1\% and 0.1%0.1\% per round, and measure the vocabulary overlap with the corresponding 10%10\% tokeniser. For UnigramLM, the overlap is 97.3%97.3\% at a 1%1\% pruning rate and 97.1%97.1\% at 0.1%0.1\%; for TopDownComp it remains above 99%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,0005,000 lines of English FineWeb, we prune from a seed vocabulary of 3,0003,000 tokens down to 800800 with a pruning rate of 10%10\%, once using exact deletion costs and once using the local replacement approximation. The two procedures agree on 652652 of the 800800 resulting tokens, an overlap of 81.5%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.