Tokenisation via Convex Relaxations
arXiv:2605.22821v1 [cs.CL] 21 May 2026
Jan Tempus, Philip Whittington,1 Craig W. Schmidt,2 Dennis Komm,1 Tiago Pimentel1 1 ETH Zurich, 2 Kensho Technologies [email protected], [email protected] {philip.whittington,dennis.komm,tiago.pimentel}@inf.ethz.ch,
Abstract Tokenisation is an integral part of the current NLP pipeline. Current tokenisation algorithms such as BPE and Unigram are greedy algorithms—they make locally optimal decisions without considering the resulting vocabulary as a whole. We instead formulate tokeniser construction as a linear program and solve it using convex optimisation tools, yielding a new algorithm we call ConvexTok. We find ConvexTok consistently improves intrinsic tokenisation metrics and the bits-per-byte (BpB) achieved by language models; it also improves downstream task performance, but less consistently. Furthermore, ConvexTok allows the user to certify how far their tokeniser is from optimal (at a certain objective) via a lower bound, and we empirically found it to be within 1% of optimal at common vocabulary sizes. code in this link
1
tokenisers in this link
Introduction
Tokenisation is an integral part of every language modelling pipeline, taking sequences of bytes as input, and converting them into sequences of tokens, which serve as input to a language model (LM). Notably, while it is generally an open research question what makes a good tokeniser (Gowda and May, 2020; Cognetta et al., 2024b; Ali et al., 2024; Schmidt et al., 2024), a number of recent works show that a tokeniser’s compression correlates (at least to some extent) with its downstream performance in LLMs (Gallé, 2019; Zouhar et al., 2023a). Given these results, we might expect researchers to test how LMs would perform given a compression-optimal tokeniser. Unfortunately, finding such optimal tokenisers is NP-hard (Kozma and Voderholzer, 2024; Whittington et al., 2025; Lim et al., 2025; Kastreva et al., 2026). Hence, in practice approximate optimisation methods are employed. Currently, the de-facto standard tokenisation algorithm is byte-pair encoding (BPE; Gage, 1994; Sennrich et al., 2016), which originated as a compression algorithm. It is a simple greedy algorithm that iteratively merges the most frequent pair of tokens in a dataset into a new token until a desired vocabulary size is reached. BPE’s use of greedily chosen pair-wise token-merging means that unnecessary intermediate tokens are created and compressive ability is lost. Many approaches have been proposed as possible fixes to this problem (Cognetta et al., 2024a; Chizhov et al., 2024; Lian et al., 2025; Liu et al., 2025; Schmidt et al., 2025), but they all rely on relatively minor modifications or extensions to BPE, and do not consider optimising tokenisation beyond greedy solutions. The core technical contribution of this paper is showing how to solve tokenisation using polyhedral techniques.1 We first identify an integer program (IP) which is equivalent to the optimisation problem solved by tokenisation algorithms. Second, we relax this problem into a linear program (LP),2 for which we can efficiently compute exact (or near-exact) solutions using a common solver. Such an LP solution, however, includes ‘partial’ tokens, which need to be discretised before we can convert it 1 Polyhedral techniques are a branch of mathematics which translates combinatorial problems into studying the geometry of objects called polyhedra, or polytopes when the set is bounded. Polytopes are simply higher-dimensional version of polygons. 2 Integer programming optimises problems over discrete sets, while linear programming optimises problems over continuous sets. If an integer program requires a variable x ∈ {0, 1}, we can relax it into a linear program to allow x ∈ [0, 1].
Preprint.
into a functional tokeniser. To this end, we propose three simple rounding schemes. After rounding, constructing a tokeniser from this solution is trivial. Additionally, solving the LP provides a lower bound on the compression achieved by any tokeniser on the used dataset. Our method thus allows us to compute tight bounds on how close-to-optimal any tokeniser is. Empirically, we evaluate our proposed tokeniser’s performance in five parts, using BPE as a baseline. First, we natively analyse the behaviour of our constructed LP and the effect of different rounding techniques on its solutions’ quality. We see that even though the problem is NP-hard, the LP’s solution is not far from integral (especially at larger vocabulary sizes). Second, we use our LP’s solution to certify how close the various tokenisers are to being optimal compressors. We see that already at common vocabulary sizes the various tokenisers we consider are within 1% of optimal. Third, we study how stable tokenisers are to a specific choice of training dataset, finding that BPE is consistently more stable than ConvexTok. Fourth, we evaluate our tokenisers using common intrinsic metrics, including compression rate, vocabulary utilisation, and Rényi entropy. For these metrics, one of our rounding schemes (Bias) consistently outperforms all other tokenisers. Finally, we evaluate the effect of our tokenisers on downstream language modelling performance. In these experiments, a deterministic rounding scheme (Det) consistently performed best on bits-per-byte (BpB), and often (although not always) outperformed BPE on downstream (CORE) tasks (Li et al., 2024).
2
Tokenisation
Before we formally define the term tokeniser, we start with some preliminary definitions. First, let Σ be some alphabet, and define b ∈ Σ∗ to be a byte-string,3 which we can expand as b = b1 b2 · · · b|c| . Second, let a dataset be a multi-set of byte-strings, denoted by D = {b(n) }N n=1 . A tokeniser’s job is to segment these byte-strings into substrings, which will correspond to the tokens used as input for our model. As LMs require a finite set of tokens to compose their vocabularies, we introduce this constraint directly into the tokenisation step, defining the tokeniser’s vocabulary as a finite set of byte-substrings, i.e., T ⊂ Σ+ with |T | < ∞. Further, to guarantee that any byte-string has at least one possible valid segmentation, we also require all elements of the alphabet to be contained in the vocabulary, or formally, Σ ⊆ T . In practice, we then often fix the size of the vocabulary given a budget K to be |T | = |Σ| + K. Finally, we term t ∈ T ∗ as a token-string. def
Formally, we can now define a tokeniser as the 3-tuple T = ⟨T , tok, detok⟩, where tok : Σ∗ → T ∗ is an encoding function, which segments byte-strings into token-strings, and detok : T ∗ → Σ∗ is a decoding function, which maps token-strings back to byte-strings. As we say an encoding function segments a byte-string, we require that, whenever t = tok(b), we have that b = t1 ◦ t2 ◦ · · · ◦ t|t| . Further, the decoding function simply undoes the encoding mapping, being thus defined as def detok(t) =t1 ◦ t2 ◦ · · · ◦ t|t| . Notably, for a fixed vocabulary, many different encoding functions may successfully segment a byte-string; e.g., given the vocabulary T = {d, o, g, do, og}, we could segment byte-string dog as either tok(dog) = ⟨do, g⟩, tok(dog) = ⟨d, og⟩, or tok(dog) = ⟨d, o, g⟩. A tokeniser T thus represents both a choice of vocabulary (T ) and of segmentation strategy (tok). 2.1
What Do We Want from Our Tokeniser?
Given the description above, we are left with a question: how should we select a tokeniser? If f is an objective function, which, given a tokeniser, returns a score associated with it, we would ideally choose a tokeniser by computing a solution to the optimisation problem: argminT f (T). Unfortunately, there are two issues with this approach: (i) it is not obvious which objective function to use, and (ii) given an objective, we don’t know how to solve this optimisation problem efficiently. Several objective functions have been proposed in response to (i), including compression (Gallé, 2019), unigram log-likelihood (Kudo, 2018), or Rényi efficiency (Zouhar et al., 2023a). While we believe that more research should go into what optimisation function to use, we will focus on compression here, following a battery of prior work either proposing new tokenisers (Cognetta et al., 2024a; Chizhov et al., 2024; Lian et al., 2025) or theoretically analysing them (Zouhar et al., 2023b). Given a dataset (D), we write our compression objective function as X f (T) = length tok(b) , (1) b∈D 3 Formally, Σ∗ denotes the Kleene star of Σ (i.e., ∪∞ Σi ), and Σ+ denotes its Kleene plus (i.e., ∪∞ Σi ). i=0 i=1
2
where we note that the encoding function (tok) implicitly depends on the tokeniser’s vocabulary (T ). Even with an objective in hand, challenge (ii) remains: finding a tokeniser that optimises it, and doing so efficiently. Unfortunately, as mentioned above, this optimisation problem is NP-hard, meaning that we cannot solve it efficiently, unless P = NP. We thus focus on approximation algorithms instead. The most popular such method is byte-pair encoding (BPE), a greedy algorithm used in virtually all modern LLMs (OpenAI, 2023; Touvron et al., 2023; Biderman et al., 2023; Team Olmo et al., 2026). Notably, BPE is a greedy algorithm which iteratively chooses locally-optimal tokens to be merged a b which a a may a lead b toathe one at a time; in general, however, these tokens may not be optimal globally, choice of a suboptimal vocabulary. (See Section A for a more formal description of BPE.) As a small example, consider the dataset D = {abc, abd, abe, bc, bd, be} and K = 3. BPE would first choose to merge ⟨a⟩ and ⟨b⟩ into a new token ⟨ab⟩ for a saving of 3 symbols, and any a further b a merge a can a save b only a 1 symbol, so with two more arbitrary merges, BPE manages to save 5. It would however be optimal to choose the new tokens ⟨bc⟩, ⟨bd⟩, ⟨be⟩ to save 2 symbols three times, yielding a total saving of 6.
3
Tokenisation via Convex Relaxations
a b a a a b a Our paper’s main contribution is an LP-based tokenisation algorithm which directly approximates a globally-optimal tokeniser; thus, avoiding locally-optimal solutions. As our tokeniser relies on a convex relation, we term it ConvexTok. Before we get to our LP, however, we first express the problem as a shortest path problem in a directed acyclic graph, which will make the LP more Figure 1: Tokenisation graph conintuitive. More specifically, given a dataset (D), we construct structed from D = {abaa, aba}. a graph problem whose solutions can be easily translated into Black edges represent E byte and tokenisers, and then use this graph problem to build the LP. others represent E tok . We first define the graph. For each byte-string in our dataset, we introduce a vertex for every position in between two bytes in the string; we also introduce a vertex for the position before the first and after the last byte in the string. A string of length n thus contributes n + 1 vertices, with the first and last vertices designated as its start and end vertices, respectively. We then merge the last vertex of each byte-string with the the first vertex of the next, essentially making them a single vertex. Next, we connect each adjacent vertex within a byte-string with what we call a byte-edge. Finally, we connect each non-adjacent vertex within byte-strings with a token-edge; this is denoted formally as: def
V = {v ni | b(n) ∈ D, 0 ≤ i ≤ length(b(n) )},
∀b(n) ∈D : v nlength(b(n) ) = v n+1 0
(2a)
def
(2b)
def
(2c)
E byte = {⟨v ni , v ni+1 ⟩ | b(n) ∈ D, 0 ≤ i < length(b(n) )} E tok = {⟨v ni , v nj ⟩ | b(n) ∈ D, 0 ≤ i < length(b(n) ), i + 2 ≤ j ≤ length(b(n) )}
The set of edges in our graph is then defined as the union of byte- and token-edges: E all = E byte ∪ E tok . Finally, we colour the token-edges based on the bytes they represent. Formally, let the set of potential tokens in dataset D be denoted by T all . We can then define a colour-partition C as a partition of the token-edges E tok based on the bytes they represent: def
(n)
T all = {bij | b(n) ∈ D, 0 ≤ i < length(b(n) ), i + 2 ≤ j ≤ length(b(n) )} def (n) C = {⟨v ni , v nj ⟩ | ⟨v ni , v nj ⟩ ∈ E tok , bij = b′ } b′ ∈ T all | {z }
(3a) (3b)
edges representing token b′
This is exemplified in Fig. 1. Note that each set c ∈ C represents a potential token, containing all edges with a certain colour. Further, note that C partitions E tok ; we thus have that ∪c∈C c = E tok and that the sets of edges c ∈ C are disjoint. We can now recast tokenisation as a graph problem. Definition 3.1. We define a tokenisation graph to be the 3-tuple ⟨V, E all , C⟩. Further, we say that v 00 N and v N L are, respectively, its start and end vertices, where L = length(b ). Finally, given a budget K, we define a graph-vocabulary as a choice of K colours from C, and a graph-segmentation as a path from v 00 to v N L using only byte-edges, or token-edges from these K colours. Note that, by construction, there is a one-to-one correspondence between a graph-vocabulary and a (traditional) vocabulary T with budget K, as the tokens in a traditional vocabulary have a direct 3
mapping from the colours in a graph-vocabulary. There is also a one-to-one correspondence between a graph-segmentation and the segmentation of a dataset D by a tokeniser T; we can thus build an encoding function which segments each byte-string in D similarly to the graph. Given a graphvocabulary and graph-segmentation, we can thus construct an equivalent tokeniser T.4 Notably, the compression achieved by this tokeniser will be identical to the length of the graph-segmentation. Given this relationship between a tokeniser’s compression and a graph-segmentation’s path, we now define a graph problem equivalent to the problem of finding compression-optimal tokenisers. Definition 3.2. Consider a tokenisation graph ⟨V, E all , C⟩ and a budget K. The shortest tokenisation problem is to find the graph-segmentation in (V, E all ) with shortest path from v 00 to v N L using a graph-vocabulary of at most K colours.5 3.1
Generalising the Tokenisation Problem
The construction above creates a tokenisation graph that is equivalent to a typical tokenisation problem. We now mildly generalise this construction to allow for more flexibility in the tokeniser’s optimisation. Starting from the set of vertices V and edges E all as constructed above (in Eq. (2)), we select any subset of E all to form a set of free edges F ⊆ E all . These edges represent tokens which must always be included in a tokeniser’s vocabulary, and which are thus available for “free”; in the standard definition above, these would consist of the byte-edges E byte .6 We then define a set of priced edges as P ⊆ E all \ F; these edges represent the tokens which can be added to the vocabulary—and are thus “priced”—typically containing the entire set of token-edges. Whenever P = E tok , we have a graph with edges between all possible byte-sequences in the dataset as before. However, it could be reasonable to consider in P only edges that do not cross unicode, grapheme or morpheme boundaries (analogously to BoundlessBPE; Schmidt et al., 2025), or that represent tokens def with non-negligible frequencies.7 We then denote this (sub)set of “interesting” edges by E = F ∪ P. Definition 3.3. We define a generalised tokenisation graph as a 4-tuple ⟨V, F, P, C⟩, where (V, F ∪ P) represents a directed acyclic graph with free and priced edges, and C is a colour-partition of the priced edges. As before, a graph-vocabulary is any subset of the colours C in this graph, and a graphsegmentation is a path from v 00 to v N L using only edges from this graph-vocabulary or free edges. Note that the relationship discussed in the previous section (between compression and graphsegmentation length) is preserved when working with generalized tokenisation graphs. 3.2
Tokenisation as an Integer Program
The sections above build a graph problem which is, in a sense, equivalent to the problem of finding compression-optimal tokenisers. This graph problem, however, is not necessarily easier to solve than the original problem over strings. We now leverage it to build yet another equivalent problem using integer programming. While the resulting IP is still NP-hard, we will relax it into an LP which we can solve efficiently. Later we will rely on rounding schemes to recover an approximately globally-optimal tokeniser. Notably, relaxing the integral constraints to continuous ones is a design choice we take here. Please see Section B for an alternative approach. Furthermore, we note that linear programming has a long history of use in approximating algorithms for combinatorial problems (Williamson and Shmoys, 2011; Vazirani, 2010; Shmoys and Tardos, 1993; Papadimitriou and Steiglitz, 1982). Consider a generalised tokenisation graph ⟨V, F, P, C⟩. To convert it into an IP, we first define a free incidence matrix8 F ∈ {−1, 0, 1}V×F and a priced incidence matrix P ∈ {−1, 0, 1}V×P to have elements Fv,e and Pv,e which encode whether an edge (e ∈ F or e ∈ P, respectively) starts or ends at some vertex (v ∈ V). Second, we define an edge-colour matrix C ∈ {0, 1}P×C to have elements Ce,c encoding whether a priced edge e ∈ P has a specific colour c ∈ C. Formally: ( ( −1 if e = ⟨v, v ′ ⟩ −1 if e = ⟨v, v ′ ⟩ 1 if e ∈ c def def def ′ ′ 1 elif e = ⟨v , v⟩ , Pv,e = 1 elif e = ⟨v , v⟩ , Ce,c = Fv,e = (4) 0 else 0 else 0 else 4 For completeness, we also define the encoding function to encode byte-strings which are not in D using PathPiece (Schmidt et al., 2024), which is compression-optimal for a fixed vocabulary. 5We note that related variants of Theorems 3.1 and 3.2 have been studied before, as connectivity problems of labelled graphs, or coloured graphs (Broersma et al., 2005; Hassin et al., 2006; Zhang et al., 2011; Ghaffari et al., 2017). 6When we say “free” here, this is in terms of not occupying a part of the allowed budget K. These edges are still costly in terms of increasing a path’s length in a graph-segmentation. 7 Our method can in fact be used to solve tokenisation with any set of candidate tokens, as defined by Lim et al. (2025). 8We follow the convention that when a matrix is defined as {0, 1}V×F we may index it using elements of V and F .
4
Recall that each colour c ∈ C represents a potential token; Ce,c = 1 then means that an edge e represents an instance of c’s token. Notably, these matrices represent the structural constraints of a tokenisation problem. We now define three vectors which we will use to define a specific tokeniser: (i) a free token-instance vector f ∈ {0, 1}F ; (ii) a priced token-instance vector p ∈ {0, 1}P ; and (iii) a priced-colour vector c ∈ {0, 1}C . These vectors represent, respectively, which free and priced edges are being used to segment a tokenisation-graph (forming, together, a graph-segmentation) and which tokens are selected as colours (forming a graph-vocabulary). As we can choose at most K colours, we introduce the constraint ⟨1, c⟩ ≤ K. Further, a priced token-instance can only be used if its priced-colour is a part of the vocabulary, motivating the constraint p − Cc ≤ 0. Finally, we introduce flow-constraints (from Ford and Fulkerson, 1962; Dantzig, 1960) to guarantee that the solution p, f forms a valid path (or segmentation) over the graph. To this end, we define a flow-difference vector d ∈ {−1, 0, 1}V which is defined as dv00 = −1, dvN = 1 for the starting and ending vertices, L and as dv = 0 for other vertices. This vector can then be used to guarantee that the input-output flow difference in all vertices is zero, except for the starting vertex (with a −1 flow difference) and the ending vertex (with a +1 flow difference): Pp + Ff = d. Together, these constraints enforce that any choice of f , p, c corresponds to a valid graph-segmentation and graph-vocabulary. The length of this graph-segmentation can then be measured as ⟨1, p⟩ + ⟨1, f ⟩. We can now define the IP as: f ∈{0, 1}F Pp + Ff = d # valid segmentation min ⟨1, p⟩ + ⟨1, f ⟩ IP def P p − Cc ≤ 0 # token in vocabulary , where Q = : (5) p ∈{0, 1} s.t. f , p, c ∈ QIP C ⟨1, c⟩ ≤ K # vocabulary budget c ∈{0, 1} Note that, as mentioned above, any choice of f , p, c ∈ QIP corresponds to a valid graph-vocabulary and graph-segmentation, which, in turn, correspond to a valid tokeniser. We make two observations regarding this IP. Observation 3.4. Let f , p, c be any element of QIP (as defined in Eq. (5)). We can convert this instance into a tokeniser T with compression f (T) = ⟨1, p⟩ + ⟨1, f ⟩. Observation 3.5. Let T be any valid tokeniser with budget K. If F = E byte and P = E tok , we can convert this tokeniser into an instance of f , p, c ∈ QIP with path length ⟨1, p⟩ + ⟨1, f ⟩ = f (T). These observations guarantee that all elements in the space of solutions QIP correspond to valid tokenisers with equivalent compressions, and that all valid tokenisers correspond to elements in the non-relaxed polytope QIP with equivalent path-lengths. Please see Section C for a mapping between the integer program and token sequences. 3.3
Approximating the Integer Program via Convex Relaxations
As mentioned above, the IP in Eq. (5) is still an NP-hard optimisation problem. We can, however, use a convex relaxation to transform it into an LP, which can be solved efficiently. To this end, we simply relax all variables f , p, c from being optimised over the discrete space {0, 1} to be optimised over the continuous [0, 1] interval instead. The priced-colour vector, for instance, becomes c ∈ [0, 1]C , allowing for partial tokens to be selected for a tokeniser. Similarly, the priced token-instance vector allows for edges to be partially included in the solution. Formally, we write: F Pp + Ff = d # valid segmentation f ∈[0, 1] min ⟨1, p⟩ + ⟨1, f ⟩ def , where Q = p ∈[0, 1]P : p − Cc ≤ 0 # token in vocabulary (6) s.t. f , p, c ∈ Q C ⟨1, c⟩ ≤ K # vocabulary budget c ∈[0, 1] We term this relaxation of Q the tokenisation polytope.9 Notably, this problem can be solved efficiently (or near-exactly, up to numeric approximation). Tokenisers’ vocabularies, however, are discrete sets; thus, we cannot straightforwardly convert instances f , p, c ∈ Q of this LP that involve fractional variables into a tokeniser. Hence, we will need to discretise the output of this LP, a process typically known as rounding. We consider three rounding schemes here, noting that this is far from an exhaustive list: deterministic, biased, and integral-only rounding. Deterministic rounding (Det) rounds the K colours in c with the largest value to 1, and sets others to zero. Biased rounding (Bias), instead ranks each colour in c by its value divided by the length 9 A polytope is defined as the finite closed intersection of halfspaces.
5
def det_rounding(K, c): col= sort(c, by=c, ,→ ascending=False) c′ = 0 for c in col[0 : K] : c′c = 1 return c′
def biased_rounding(K, c): def integral_rounding(cc ): col = sort(c, c′ = 0 cc by= length(c) , for c ∈ C: if cc ≥ 0.999 : ascending=False) cc ′ = 1 c′ = 0 return c′ for c in col[0 : K] : c′c = 1 return c′
Figure 2: The Det (left), Bias (center), and Int (right) rounding schemes. of the token it represents (c/length(c), with a slight abuse of notation to let length(c) denote the length of the corresponding token), and then rounds these values (to 1 or 0) as before. This biases the selection towards shorter tokens when LP scores are comparable, and is motivated by the fact that shorter tokens are more likely to occur outside the training strings in D. Finally, integral-only rounding (Int) keeps only the colours c whose value is already essentially one, setting others to zero. This can be interpreted as selecting the tokens that the LP relaxation treats as forced, but it will typically return a vocabulary with fewer tokens than the allowed budget K. These rounding schemes are depicted in Fig. 2. Given a (rounded) choice of c, it is then trivial to compute optimal discrete values of p and f using a shortest path algorithm with the allowed colours.
4
Experimental Setup
Data. We used ClimbMix400B (Karpathy, 2025)10 for training both tokenisers and LMs. ClimbMix400B is a large-scale pretraining corpus derived from NVIDIA’s Nemotron-ClimbMix dataset (Diao et al., 2026). It has been optimised automatically using multiple techniques to get a highly curated dataset. As is common when tokenising, the text is first pre-tokenised using a regular expression that splits the input into linguistically and typographically meaningful chunks. This pre-tokenisation step prevents tokenisers from crossing these coarse boundaries, so the learned tokens are built within local text categories such as words, numbers, punctuation, or whitespace blocks. We use the same regular expression for pretokenisation as nanochat (Karpathy, 2025). Tokenisers. Throughout our experiments, we use BPE as a baseline. We compare it to ConvexTok with the three rounding schemes presented above: Bias, Det, and Int. Further, we train all tokenisers with 593,920 documents and with vocabulary sizes from 8k to 256k, in power-of-two increments. We note that we abbreviate powers of 2 in the vocabulary sizes below, e.g., 8k corresponds to 8192. Furthermore, in practice, we may want to include a number of special tokens Φ (e.g., end-ofsequence, padding, masking, or output-start) in our tokeniser. We thus enforce Σ ∪ Φ ⊂ T and define |T | = |Σ| + |Φ| + K, where |T | is our vocabulary size. Finally, at inference, our tokenisers use a standard shortest path algorithm (similar to UnigramLM’s; Kudo, 2018) to produce token-strings; ConvexTok thus has a similar runtime as UnigramLM and BPE. Solving the LP. We solve the LP using the PDLP method implemented in the NVIDIA CuOPT library (NVIDIA, 2025).11 We used the default stopping criteria of a primal dual gap of 10,000. We also merged identical subgraphs and adjusted the objective coefficients to preserve optimality. The final LP we solved has 99,168,445 constraints in total, 20,093,064 are equality constraints while 79,075,381 are inequality constraints. Furthermore, it has 105,997,943 variables corresponding to 79,075,380 priced edges and 18,096,951 free edges, with 8,825,612 different colour variables. Language Models. Following the nanochat standard, we trained GPT-style decoder-only transformer models. Although the overall structure follows the standard GPT design, nanochat upgrades it with modern architectural techniques. We also follow nanochat’s training configuration, whose hyperparameter choices are motivated by empirical scaling laws (Kaplan et al., 2020; Hoffmann et al., 2022). In our experiments, we fix these hyperparameters across tokenisers and vocabulary sizes. They do, however, vary with depth. They are chosen using the BPE baseline at vocabulary size 32k, and are then reused unchanged for Bias and Det, as well as for different vocabulary sizes. Model training time varied from roughly 17 minutes on 4 GH200s for the smallest models (with 135M parameters) up to 199 minutes on 16 GH200s for the largest models (with 3.5B parameters). Training ConvexTok takes about 4 hours on 1 GH200. We estimate that in total we needed about 200 GPU hours across all of our training runs. Please see Section I for loss curves across training. 10 Nanochat has an MIT license and is available at this GitHub repository. 11 NVIDIA CuOPT has an Apache-2.0 license and can be found in this link.
6
Table 1: Characteristics of the solutions for the LP. % of 1s (and of ¬ 0s) measures the ratio of c which are 1 (or not 0) divided by the vocabulary budget. Vocabulary Size 8k 16k 32k 64k 128k 256k
c
f
p
# steps
Time (sec)
LP Value
% of 1s
% of ¬ 0s
# of 1s
# of ¬ 0s
# of 1s
# of ¬ 0s
65,000 5,600 6,800 6,400 9,700 9,500
889.927 182.661 196.123 181.455 226.768 230.920
427,366,252 393,224,648 371,886,133 359,626,839 352,723,064 349,028,128
66.41% 73.22% 81.5% 84.39% 90.91% 90.53%
151.01% 142.31% 129.95% 126.26% 113.97% 114.59%
1,466,122 1,021,750 678,332 349,172 204,014 121,694
5,889,259 4,724,165 3,263,220 2,402,815 1,556,595 1,207,058
577,768 750,072 1,247,839 1,380,456 1,717,709 1,560,819
16,244,391 15,712,089 13,796,121 12,738,868 10,338,653 9,564,059
Table 2: Comparison between the LP relaxation value and the value obtained by each tokeniser. Vocabulary Size
Tokeniser
LP Value
Tokenised Value
Integrality Gap Ratio
Vocabulary Size
Tokeniser
8k
BPE Det Bias Int
427,366,252
441,669,198 431,045,026 448,151,069 524,085,422
103.347% 100.860% 104.863% 122.631%
64k
16k
BPE Det Bias Int
393,224,648
401,802,733 394,344,618 403,757,674 439,773,017
102.181% 100.285% 102.679% 111.838%
32k
BPE Det Bias Int
371,886,133
376,680,738 372,156,050 375,996,735 386,575,802
101.289% 100.073% 101.105% 103.950%
5
LP Value
Tokenised Value
Integrality Gap Ratio
BPE Det Bias Int
359,626,839
362,088,805 359,690,431 361,962,390 366,041,138
100.685% 100.018% 100.649% 101.784%
128k
BPE Det Bias Int
352,723,064
354,079,660 353,538,264 352,753,850 354,160,993
100.385% 100.231% 100.009% 100.408%
256k
BPE Det Bias Int
349,028,128
349,745,778 349,020,177 349,264,651 350,090,533
100.206% 99.997% 100.068% 100.304%
Results
Behaviour of Solving the Linear Programs. Table 1 reports several optimisation statistics obtained when solving the LP relaxation for different vocabulary sizes. Unsurprisingly, the primal objective (i.e., the LP value) decreases monotonically as the vocabulary size increases. More interestingly, the solution becomes more integral as the vocabulary size increases.12 This suggests that, at larger vocabulary sizes, the optimisation problem becomes less ambiguous, and therefore more tokens are already determined by the LP solution, leaving less work for the subsequent rounding procedure. Another thing to note is the relative stability of the running time, with the obvious exception of the much slower run with a vocabulary size of 8k. This could be due to the small vocabulary budget making the feasible region substantially more constrained, causing the solver to spend much longer resolving the trade-offs between competing token choices. Finally, we also note how small the number of non-zero entries are in comparison to how many variables exist. Performance of Rounding Schemes on Compression, and Certifying Optimality. Table 2 presents the LP’s solutions,13 as well as the compression obtained by our tokenisers. Interestingly, it shows that the various tokenisers are close to the LP’s corresponding solutions, especially Det. As the LP value provides a provable lower bound on the optimal compression, it follows that our tokenisers are close to optimal. Considering how close the various rounded tokenisers are to optimal, we may assume that the rounding step is not necessarily that critical. This is especially so at vocabulary sizes of 128k and 256k, where even Int (with fewer tokens) is close to optimal. This trend suggests a saturation effect; after the most compression-important tokens have been included, additional tokens have diminishing marginal value. Finally, it is worth noting how close BPE also is to being compression-optimal, despite being a greedy method. Stability of Tokenisers to Randomness on the Training Sample. In Figure 3, we study our tokenisers’ stability relating to a specific choice of training set. To this end, we train tokenisers using independently sampled subsets of our training data, and compare their vocabularies using 1 ∩T 2 | the Jaccard similarity, defined, for two vocabularies T 1 and T 2 , as |T |T 1 ∪T 2 | . Further, we repeat this procedure for different training dataset sizes. We say a tokeniser is more stable, if its Jaccard 12 In practice, we used 0.999 as an approximation for 1 and 0.001 as an approximation for 0, due to numerical imprecision. 13When reading Table 2, one should keep in mind that the LP values are obtained numerically and are therefore subject to
solver tolerances and numerical imprecision. The gap for Det at vocabulary size 256k is within that tolerance.
7
Figure 3: Average Jaccard similarity between vocabularies when retraining a tokeniser on independently sampled subsets of the same data (for different numbers of documents). Table 3: Tokenisers’ performances on intrinsic metrics. Vocabulary Size
Vocabulary Utilisation (↑)
Tokeniser
Type-Token Ratio (↑)
Rényi Entropy (α=1) (↑)
Rényi Entropy (α=2.5) (↑)
Avg Token Rank (↓)
Token Length
Tokens per Line (↓)
Compression Rate (↑)
8k
BPE Det Bias Int
98.6% 99.0% 99.0% 98.6%
0.0055 0.0056 0.0054 0.0031
10.61 10.61 10.69 9.31
7.09 7.02 7.10 6.90
1121.5 1141.3 1171.0 492.3
3.99 4.09 3.93 3.39
63.8 62.3 64.6 75.6
0.0014 0.0014 0.0013 0.0011
16k
BPE Det Bias Int
98.1% 98.8% 98.8% 98.8%
0.0120 0.0123 0.0120 0.0082
10.90 10.90 10.95 10.18
6.88 6.83 6.88 6.99
1780.4 1833.8 1860.9 1033.6
4.38 4.46 4.36 4.03
58.1 57.0 58.3 63.6
0.0015 0.0015 0.0015 0.0014
32k
BPE Det Bias Int
92.1% 92.4% 92.6% 93.4%
0.0240 0.0244 0.0242 0.0195
11.04 11.03 11.06 10.82
6.73 6.70 6.72 6.79
2516.8 2586.1 2609.1 1975.1
4.67 4.72 4.68 4.55
54.5 53.9 54.4 56.0
0.0016 0.0016 0.0016 0.0015
64k
BPE Det Bias Int
70.7% 71.2% 71.5% 73.8%
0.0384 0.0389 0.0388 0.0336
11.07 11.05 11.07 10.98
6.64 6.62 6.63 6.66
3138.0 3210.4 3226.2 2760.2
4.85 4.88 4.85 4.80
52.4 52.1 52.4 53.0
0.0017 0.0017 0.0017 0.0016
128k
BPE Det Bias Int
43.3% 43.8% 44.0% 45.8%
0.0481 0.0489 0.0490 0.0463
11.05 11.03 11.04 11.03
6.59 6.58 6.58 6.58
3504.5 3550.8 3566.7 3410.6
4.96 4.98 4.97 4.96
51.3 51.1 51.2 51.3
0.0017 0.0017 0.0017 0.0017
256k
BPE Det Bias Int
23.3% 23.6% 23.7% 25.2%
0.0525 0.0532 0.0534 0.0514
11.02 11.01 11.01 11.00
6.56 6.55 6.55 6.56
3635.4 3660.9 3671.1 3563.0
5.02 5.03 5.02 5.01
50.7 50.6 50.6 50.7
0.0017 0.0017 0.0017 0.0017
similarity is higher. Figure 3 shows that stability decreases as the vocabulary size increases. As this trend is consistent for both BPE and ConvexTok, it is likely due to larger vocabularies containing more low-frequency tokens, which are more sensitive to the sampled dataset. Another thing to note is that BPE is consistently more stable than ConvexTok tokenisers. This aligns with BPE being a local and frequency driven method; due to the power-law nature of natural language distributions, highfrequency merges are unlikely to change due to resampling. The higher stability of Int compared to Bias or Det is also to be expected, as Int includes only tokens which the LP deems “critical”. Performance of Tokenisers on Various Intrinsic Metrics. Table 3 shows how our tokenisers perform on a suite of classical intrinsic tokenisation metrics, computed using the library by Meister (2025) on a held-out set of ClimbMix that was not used to train the tokenisers. (See Table 5 and Table 6 in the Appendix for similar metrics computed on, respectively, a subset of the tokeniser’s training data and a multilingual dataset.) This table shows that ConvexTok variants tend to outperform BPE in vocabulary utilisation, type-token ratio, and tokens per line. In terms of Rényi Entropy, results are more mixed, with BPE often outperforming both Bias and Det. Finally, the difference in the performance of Int vs. other tokenisers is stark. Int is consistently outperformed on compression by tokenisers with a smaller vocabulary size, e.g., Int with a budget of 16k has worse compression than Det at 8k, even though (as can be verified using the % of 1s information in Table 1) this Int tokeniser still has about 11.7k tokens. 8
Table 4: Language model performances (as BpB and CORE metrics). For depth 12, we trained three models per tokeniser (with different random seeds) and report average scores (standard errors in parentheses). Other configurations have a single training run due to computational restrictions. Validation BpB (↓) Vocabulary Size
Tokeniser
CORE Metrics (↑)
Depth 12
Depth 18
Depth 24
Depth 12
Depth 18
Depth 24
8k
BPE Bias Det
0.8785(±0.0012) 0.8812(±0.0001) 0.8782(±0.0008)
0.7767 0.7793 0.7770
0.7145 0.7165 0.7154
0.1345(±0.008) 0.1318(±0.002) 0.1294(±0.005)
0.195 0.195 0.186
0.270 0.265 0.251
16k
BPE Bias Det
0.8648(±0.0006) 0.8655(±0.0001) 0.8645(±0.0003)
– – –
– – –
0.139(±0.020) 0.144(±0.002) 0.137(±0.008)
– – –
– – –
32k
BPE Bias Det
0.8536(±0.0002) 0.8531(±0.0003) 0.8525(±0.0006)
0.7616 0.7608 0.7560
0.7042 0.7040 0.7033
0.150(±0.0066) 0.148(±0.0087) 0.151(±0.0059)
0.232 0.220 0.220
0.279 0.287 0.278
64k
BPE Bias Det
0.8465(±0.0009) 0.8452(±0.0001) 0.8438(±0.0004)
– – –
– – –
0.158(±0.002) 0.164(±0.007) 0.165(±0.006)
– – –
– – –
128k
BPE Bias Det
0.8410(±0.0004) 0.8393(±0.0007) 0.8403(±0.0006)
0.7515 0.7510 0.7504
0.6968 0.6959 0.6951
0.161(±0.005) 0.156(±0.009) 0.170(±0.008)
0.233 0.238 0.229
0.296 0.296 0.302
256k
BPE Bias Det
0.8411(±0.0002) 0.8402(±0.0006) 0.8398(±0.0004)
– – –
– – –
0.159(±0.004) 0.163(±0.008) 0.158(±0.007)
– – –
– – –
Performance of Models on BpB. Table 4 shows the performance (both in terms of BpB and CORE metrics) of LMs trained with ConvexTok or BPE. (See Section J for a more comprehensive breakdown of these results.) This table shows that, for 12-layer models, the LP-based tokeniser outperforms BPE for all sizes, with the Det rounding scheme being the best at all vocabulary sizes but one. For larger depths, Det wins for 32k and 128k vocabulary sizes, and is only slightly behind BPE for 8k; Bias trails behind Det. Overall, in terms of BpB, Det thus seems to be the best performing tokeniser. Performance of Models on CORE. Table 4 also presents our model’s CORE performance in downstream tasks. (CORE is a benchmark of downstream tasks covering reasoning, multiple choice and common sense questions; Li et al., 2024.) For the CORE metric, there is no clear trend in results. At depth 12, ConvexTok is better on average, but the results are close and BPE outperforms ConvexTok for some vocabulary sizes. At depth 24, BPE is slightly better at 8k, while Bias is better at 32k with Det being the best at 128k. Overall, the CORE results suggest ConvexTok is at least competitive with BPE, but its advantage is less clear than for the BpB metric. A common trend across CORE and BpB, though, is that ConvexTok seems to be better at larger vocabulary sizes. Notably, at the largest vocabulary sizes, ConvexTok still always matches or outperforms BPE for both metrics and all depths.
6
Conclusion
In this paper, we reinterpreted tokenisation as a graph problem and formulated the resulting compression objective as an IP. We then studied its corresponding relaxed formulation (i.e., its LP) experimentally, including both its solvability and three rounding procedures for converting fractional LP solutions into discrete tokenisers. Our experiments show that the ConvexTok tokenisers are strong both in terms of intrinsic metrics and BpB; results on CORE metrics are more mixed, but suggest ConvexTok still at least matches BPE’s performance. Overall, our results suggest that globally optimised tokenisation is a promising alternative to locally greedy merge-based methods such as BPE. Limitations and Future Work. The focus of this paper is on compression; however, Table 2 shows that getting tokenisers with near-optimal compression on a dataset is not too hard, as at 128k and 256k our approach achieves results within 1 % of the LP lower bound. Significantly improving training-data compression is thus senseless under similar constraints. Recent approaches like SuperBPE (Liu et al., 2025), however, propose methods which partially ignore pretokenisation; it would be interesting to extend our analyses to those settings. Further, extending our LP-based approach to other objective functions f could also lead to novel and interesting tokenisers. 9
Acknowledgements We would like to thank Clara Meister, Gregor Bachmann, Dimitri von Rütte, Pietro Lesci, Louis Barinka, Marius Mosbach, Thomas Hofmann and Saibo Geng for feedback and comments they have brought at various stages of the project.
References Mehdi Ali, Michael Fromm, Klaudia Thellmann, Richard Rutmann, Max Lübbering, Johannes Leveling, Katrin Klug, Jan Ebert, Niclas Doll, Jasper Buschhoff, Charvi Jain, Alexander Weber, Lena Jurkschat, Hammam Abdelwahab, Chelsea John, Pedro Ortiz Suarez, Malte Ostendorff, Samuel Weinbach, Rafet Sifa, Stefan Kesselheim, and Nicolas Flores-Herr. 2024. Tokenizer choice for LLM training: Negligible or crucial? In Findings of the Association for Computational Linguistics: NAACL 2024, pages 3907–3924, Mexico City, Mexico. Association for Computational Linguistics. David L. Applegate, Robert E. Bixby, Vašek Chvatál, and William J. Cook. 2006. The Traveling Salesman Problem: A Computational Study. Princeton University Press. Stella Biderman, Hailey Schoelkopf, Quentin Anthony, Herbie Bradley, Kyle O’Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, Aviya Skowron, Lintang Sutawika, and Oskar Van Der Wal. 2023. Pythia: A suite for analyzing large language models across training and scaling. In Proceedings of the 40th International Conference on Machine Learning, ICML’23. Hajo Broersma, Xueliang Li, Gerhard Woeginger, and Shenggui Zhang. 2005. Paths and cycles in colored graphs. Australasian journal of combinatorics, 31(1):299–311. Pavel Chizhov, Catherine Arnett, Elizaveta Korotkova, and Ivan P. Yamshchikov. 2024. BPE gets picky: Efficient vocabulary refinement during tokenizer training. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 16587–16604, Miami, Florida, USA. Association for Computational Linguistics. Marco Cognetta, Tatsuya Hiraoka, Rico Sennrich, Yuval Pinter, and Naoaki Okazaki. 2024a. An analysis of BPE vocabulary trimming in neural machine translation. In Proceedings of the Fifth Workshop on Insights from Negative Results in NLP, pages 48–50, Mexico City, Mexico. Association for Computational Linguistics. Marco Cognetta, Vilém Zouhar, Sangwhan Moon, and Naoaki Okazaki. 2024b. Two counterexamples to tokenization and the noiseless channel. In Proceedings of the 2024 Joint International Conference on Computational Linguistics, Language Resources and Evaluation (LREC-COLING 2024), pages 16897–16906, Torino, Italia. ELRA and ICCL. George B. Dantzig. 1960. On the shortest route through a network. Management Science, 6(2):187– 190. Shizhe Diao, Yu Yang, Yonggan Fu, Xin Dong, Dan SU, Markus Kliegl, ZIJIA CHEN, Peter Belcak, Yoshi Suhara, Hongxu Yin, Mostofa Patwary, Yingyan Celine Lin, Jan Kautz, and Pavlo Molchanov. 2026. Nemotron-CLIMB: Clustering-based iterative data mixture bootstrapping for language model pre-training. In The Thirty-ninth Annual Conference on Neural Information Processing Systems Datasets and Benchmarks Track. L. R. Ford and D. R. Fulkerson. 1962. Flows in Networks. Princeton University Press. Philip Gage. 1994. A new algorithm for data compression. C Users Journal, 12(2):23–38. Matthias Gallé. 2019. Investigating the effectiveness of BPE: The power of shorter sequences. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 1375–1381, Hong Kong, China. Association for Computational Linguistics. 10
Mohsen Ghaffari, David R. Karger, and Debmalya Panigrahi. 2017. Random contractions and sampling for hypergraph and hedge connectivity. In Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1101–1114. ACM-SIAM. Thamme Gowda and Jonathan May. 2020. Finding the optimal vocabulary size for neural machine translation. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 3955–3964, Online. Association for Computational Linguistics. Refael Hassin, Jérôme Monnot, and Danny Segev. 2006. Approximation algorithms and hardness results for labeled connectivity problems. Journal of Combinatorial Optimization, 14:437–453. Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Oriol Vinyals, Jack W. Rae, and Laurent Sifre. 2022. Training compute-optimal large language models. In Advances in Neural Information Processing Systems. Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. 2020. Scaling laws for neural language models. Preprint, arXiv:2001.08361. Andrej Karpathy. 2025. nanochat: The best ChatGPT that $100 can buy. Violeta Kastreva, Philip Whittington, Dennis Komm, and Tiago Pimentel. 2026. Tokenisation over bounded alphabets is hard. In The Fourteenth International Conference on Learning Representations. Ed Klotz and Alexandra M. Newman. 2013. Practical guidelines for solving difficult mixed integer linear programs. Surveys in Operations Research and Management Science, 18(1–2):18–32. László Kozma and Johannes Voderholzer. 2024. Theoretical analysis of byte-pair encoding. Preprint, arXiv:2411.08671. Taku Kudo. 2018. Subword regularization: Improving neural network translation models with multiple subword candidates. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 66–75, Melbourne, Australia. Association for Computational Linguistics. Jeffrey Li, Alex Fang, Georgios Smyrnis, Maor Ivgi, Matt Jordan, Samir Yitzhak Gadre, Hritik Bansal, Etash Kumar Guha, Sedrick Keh, Kushal Arora, Saurabh Garg, Rui Xin, Niklas Muennighoff, Reinhard Heckel, Jean Mercat, Mayee F Chen, Suchin Gururangan, Mitchell Wortsman, Alon Albalak, Yonatan Bitton, Marianna Nezhurina, Amro Kamal Mohamed Abbas, Cheng-Yu Hsieh, Dhruba Ghosh, Joshua P Gardner, Maciej Kilian, Hanlin Zhang, Rulin Shao, Sarah M Pratt, Sunny Sanyal, Gabriel Ilharco, Giannis Daras, Kalyani Marathe, Aaron Gokaslan, Jieyu Zhang, Khyathi Chandu, Thao Nguyen, Igor Vasiljevic, Sham M. Kakade, Shuran Song, Sujay Sanghavi, Fartash Faghri, Sewoong Oh, Luke Zettlemoyer, Kyle Lo, Alaaeldin El-Nouby, Hadi Pouransari, Alexander T Toshev, Stephanie Wang, Dirk Groeneveld, Luca Soldaini, Pang Wei Koh, Jenia Jitsev, Thomas Kollar, Alex Dimakis, Yair Carmon, Achal Dave, Ludwig Schmidt, and Vaishaal Shankar. 2024. Datacomp-LM: In search of the next generation of training sets for language models. In The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track. Haoran Lian, Yizhe Xiong, Jianwei Niu, Shasha Mo, Zhenpeng Su, Zijia Lin, Hui Chen, Jungong Han, and Guiguang Ding. 2025. Scaffold-BPE: Enhancing byte pair encoding for large language models with simple and effective scaffold token removal. Proceedings of the AAAI Conference on Artificial Intelligence, 39(23):24539–24548. Jia Peng Lim, Shawn Tan, Davin Choo, and Hady W. Lauw. 2025. A partition cover approach to tokenization. In The Thirty-ninth Annual Conference on Neural Information Processing Systems. Alisa Liu, Jonathan Hayase, Valentin Hofmann, Sewoong Oh, Noah A. Smith, and Yejin Choi. 2025. SuperBPE: Space travel for language models. In Second Conference on Language Modeling. 11
Clara Meister. 2025. TokEval: A tokenizer analysis suite. NLLB Team, Marta R. Costa-jussà, James Cross, Onur Çelebi, Maha Elbayad, Kenneth Heafield, Kevin Heffernan, Elahe Kalbassi, Janice Lam, Daniel Licht, Jean Maillard, Anna Sun, Skyler Wang, Guillaume Wenzek, Al Youngblood, Bapi Akula, Loic Barrault, Gabriel Mejia Gonzalez, Prangthip Hansanti, John Hoffman, Semarley Jarrett, Kaushik Ram Sadagopan, Dirk Rowe, Shannon Spruit, Chau Tran, Pierre Andrews, Necip Fazil Ayan, Shruti Bhosale, Sergey Edunov, Angela Fan, Cynthia Gao, Vedanuj Goswami, Francisco Guzmán, Philipp Koehn, Alexandre Mourachko, Christophe Ropers, Safiyyah Saleem, Holger Schwenk, and Jeff Wang. 2024. Scaling neural machine translation to 200 languages. Nature, 630(8018):841–846. NVIDIA. 2025. NVIDIA cuOpt: GPU-accelerated decision optimization. OpenAI. 2023. GPT-4 technical report. Preprint, arXiv:2303.08774. Christos H. Papadimitriou and Kenneth Steiglitz. 1982. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc., USA. Craig W. Schmidt, Varshini Reddy, Chris Tanner, and Yuval Pinter. 2025. Boundless byte pair encoding: Breaking the pre-tokenization barrier. In Second Conference on Language Modeling. Craig W. Schmidt, Varshini Reddy, Haoran Zhang, Alec Alameddine, Omri Uzan, Yuval Pinter, and Chris Tanner. 2024. Tokenization is more than compression. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 678–702, Miami, Florida, USA. Association for Computational Linguistics. Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016. Neural machine translation of rare words with subword units. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1715–1725, Berlin, Germany. Association for Computational Linguistics. David B. Shmoys and Éva Tardos. 1993. An approximation algorithm for the generalized assignment problem. volume 62, pages 461–474. Team Olmo, Allyson Ettinger, Amanda Bertsch, Bailey Kuehl, David Graham, David Heineman, Dirk Groeneveld, Faeze Brahman, Finbarr Timbers, Hamish Ivison, Jacob Morrison, Jake Poznanski, Kyle Lo, Luca Soldaini, Matt Jordan, Mayee Chen, Michael Noukhovitch, Nathan Lambert, Pete Walsh, Pradeep Dasigi, Robert Berry, Saumya Malik, Saurabh Shah, Scott Geng, Shane Arora, Shashank Gupta, Taira Anderson, Teng Xiao, Tyler Murray, Tyler Romero, Victoria Graf, Akari Asai, Akshita Bhagia, Alexander Wettig, Alisa Liu, Aman Rangapur, Chloe Anastasiades, Costa Huang, Dustin Schwenk, Harsh Trivedi, Ian Magnusson, Jaron Lochner, Jiacheng Liu, Lester James V. Miranda, Maarten Sap, Malia Morgan, Michael Schmitz, Michal Guerquin, Michael Wilson, Regan Huff, Ronan Le Bras, Rui Xin, Rulin Shao, Sam Skjonsberg, Shannon Zejiang Shen, Shuyue Stella Li, Tucker Wilde, Valentina Pyatkin, Will Merrill, Yapei Chang, Yuling Gu, Zhiyuan Zeng, Ashish Sabharwal, Luke Zettlemoyer, Pang Wei Koh, Ali Farhadi, Noah A. Smith, and Hannaneh Hajishirzi. 2026. Olmo 3. Preprint, arXiv:2512.13961. Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023. LLaMA: Open and efficient foundation language models. Preprint, arXiv:2302.13971. Vijay V. Vazirani. 2010. Approximation Algorithms. Springer Publishing Company, Incorporated. Philip Whittington, Gregor Bachmann, and Tiago Pimentel. 2025. Tokenisation is NP-complete. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 28133–28153, Vienna, Austria. Association for Computational Linguistics. David P. Williamson and David B. Shmoys. 2011. The Design of Approximation Algorithms, 1st edition. Cambridge University Press, USA. Peng Zhang, Jin-Yi Cai, Lin-Qing Tang, and Wen-Bo Zhao. 2011. Approximation and hardness results for label cut and related problems. Journal of Combinatorial Optimization, 21:192–208. 12
Vilém Zouhar, Clara Meister, Juan Gastaldi, Li Du, Mrinmaya Sachan, and Ryan Cotterell. 2023a. Tokenization and the noiseless channel. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 5184–5207, Toronto, Canada. Association for Computational Linguistics. Vilém Zouhar, Clara Meister, Juan Gastaldi, Li Du, Tim Vieira, Mrinmaya Sachan, and Ryan Cotterell. 2023b. A formal perspective on byte-pair encoding. In Findings of the Association for Computational Linguistics: ACL 2023, pages 598–614, Toronto, Canada. Association for Computational Linguistics.
13
A
Formal description of BPE
Let merget′ ,t′′ be a function which, given a token-string, replaces all occurrences of the bigram def t′ , t′′ in it with the merged token tnew = t′ ◦ t′′ . The BPE algorithm then works as follows: it initialises a character-level tokeniser, T0 = ⟨Σ, id, detok⟩, where id is the identity function; for a pre-specified number of steps K, it then takes the current tokeniser Tk−1 = ⟨T k−1 , tokk−1 , detok⟩ and selects the pair of existing tokens t′ , t′′ ∈ T k−1 which, if merged, will lead to maximal compression, and adds it to the vocabulary, as T k = T k−1 ∪ {tnew }, and the encoding function as tokk (b) = merget′ ,t′′ (tokk−1 (b)).
B
Alternatives to Linear Programming for solving IPs
An alterative choice to linear programming is to use methods such as branch-and-bound methods to solve the IP directly. While branch-and-bound algorithms perform well in practice on highly structured IPs, such the travelling salesman problems (Applegate et al., 2006), they exhibit poor scaling behaviours. Hence, we decided to use linear programming with rounding, as this method scales better (Klotz and Newman, 2013). We hope future work explores other approaches to investigate this IP.
C
Mapping Between Vectors of the IP and the Token Sequence
In this section, we describe how to map an element of Q to a tokeniser T, and back. We give an informal sketch here, as the process is relatively simple and doing it formally would drown the reader with technical details which would obscure the idea. C.1
From an IP Solution to a Tokeniser
Consider some free token-instance vector, priced token-instance vector, and priced-colour vector f , p, c ∈ QIP . First, we can recover the vocabulary by taking the union of all elements of c which are equal to 1 and the alphabet. Formally, the vocabulary is {tc ∈ C | cc = 1} ∪ Σ, where we denote as tc the token corresponding to colour c. Second, with the free and priced vectors f , p one can recover a valid segmentation of the dataset D. Recall that each potential use of a token to encode a byte-string b ∈ D corresponds to exactly one edge in either f or p. As such, to recover the segmentation of b ∈ D by selecting a token if and only if its corresponding edge from f ∪ p is equal to 1. For completeness, given the extracted vocabulary, we use PathPiece (Schmidt et al., 2024) to define the encoding function’s behaviour on other byte-strings not in the dataset, computing: ∀b∈D / : tok(b) = argmin |t|, s.t.
◦
b=t
(7)
t∈T ∗
C.2
From a Tokeniser to an IP Solution
Now we sketch how to take a tokeniser T and convert it to vectors contained within the IP. This is simply the process described above, but in reverse. Given the tokeniser’s vocabulary, we set each element cc in vector c to 1 if and only if its corresponding token tc is included in the vocabulary. For the dataset D then, we consider each of its byte-strings b ∈ D and run it under the tokeniser’s encoding function to get a token-string. For each token in this token-string, we then find its correspondence in either f or p and set it to 1; the rest of these vectors are all zero.
14
D
Intrinsic Tokenisation Results on our Tokeniser’s Training Data
Table 5 presents intrinsic tokenisation metrics on a subset of the data used to train our tokenisers. The similarity between the compression results here and in Table 3 suggests that our tokenisers generalise to new samples of the same distribution. Table 5: Tokenisers’ performances on intrinsic metrics computed using a subset of our tokeniser’s training data. Vocabulary Size
Tokeniser
Vocabulary Utilisation (↑)
Type-Token Ratio (↑)
Rényi Entropy (α=1) (↑)
Rényi Entropy (α=2.5) (↑)
Avg Token Rank (↓)
Token Length
Tokens per Line (↓)
Compression Rate (↑)
8k
BPE Det Bias Int
98.4% 98.9% 98.8% 98.3%
0.0054 0.0056 0.0053 0.0031
10.59 10.59 10.66 9.34
7.08 7.00 7.09 6.93
1111.4 1135.9 1154.0 499.1
4.02 4.12 3.96 3.41
71.8 70.0 72.7 84.6
0.0013 0.0014 0.0013 0.0011
16k
BPE Det Bias Int
97.8% 98.7% 98.7% 98.7%
0.0118 0.0121 0.0118 0.0081
10.86 10.86 10.90 10.19
6.87 6.82 6.87 6.98
1747.9 1798.9 1814.4 1039.3
4.41 4.50 4.39 4.06
65.5 64.2 65.8 71.3
0.0015 0.0015 0.0015 0.0014
32k
BPE Det Bias Int
91.9% 92.2% 92.4% 93.3%
0.0236 0.0240 0.0238 0.0192
10.98 10.97 10.99 10.78
6.72 6.69 6.72 6.77
2438.0 2505.5 2520.8 1939.9
4.71 4.76 4.71 4.59
61.5 60.8 61.4 63.1
0.0016 0.0016 0.0016 0.0015
64k
BPE Det Bias Int
70.2% 70.6% 70.7% 73.4%
0.0375 0.0379 0.0377 0.0329
11.00 10.98 10.99 10.92
6.64 6.62 6.63 6.66
3009.4 3067.2 3073.3 2665.7
4.89 4.92 4.89 4.84
59.3 58.9 59.3 59.9
0.0016 0.0016 0.0016 0.0016
128k
BPE Det Bias Int
42.6% 43.2% 43.3% 45.3%
0.0464 0.0472 0.0473 0.0449
10.97 10.96 10.96 10.96
6.59 6.58 6.58 6.59
3317.1 3358.7 3368.9 3243.3
4.99 5.01 5.00 4.99
58.1 57.9 58.0 58.1
0.0017 0.0017 0.0017 0.0017
256k
BPE Det Bias Int
22.8% 23.1% 23.2% 24.7%
0.0504 0.0510 0.0511 0.0494
10.94 10.93 10.93 10.93
6.56 6.56 6.56 6.56
3415.6 3430.7 3437.6 3356.0
5.05 5.06 5.06 5.05
57.4 57.3 57.3 57.5
0.0017 0.0017 0.0017 0.0017
E
Intrinsic Tokenisation Results on a Multilingual Dataset
Table 6 presents intrinsic tokenisation metrics on the Flores+ dataset (NLLB Team et al., 2024). The difference between the compression results here and in Table 3 suggests that Bias generalises better to new out-of-distribution settings than Det. Table 6: Tokenisers’ performances on intrinsic metrics computed using the FLORES+ dataset. Vocabulary Size
Tokeniser
Vocabulary Utilisation (↑)
Type-Token Ratio (↑)
Rényi Entropy (α=1) ( ↑)
Rényi Entropy (α=2.5) (↑)
Avg Token Rank (↓)
Token Length
Tokens per Line (↓)
Compression Rate (↑)
8k
BPE Det Bias Int
67.7% 63.8% 69.2% 62.0%
0.0090 0.0085 0.0093 0.0051
6.75 6.73 6.79 6.41
4.34 4.31 4.29 4.54
131.1 127.8 156.7 57.6
1.91 1.93 1.96 1.52
123.5 123.4 121.9 136.7
0.0081 0.0081 0.0082 0.0073
16k
BPE Det Bias Int
46.5% 44.3% 48.1% 42.7%
0.0142 0.0138 0.0154 0.0084
7.25 7.29 7.37 6.76
4.90 4.86 4.84 4.80
192.2 196.3 233.9 89.1
2.11 2.16 2.19 1.77
107.9 105.8 102.9 124.4
0.0093 0.0095 0.0097 0.0080
32k
BPE Det Bias Int
28.7% 27.7% 29.4% 26.6%
0.0201 0.0200 0.0216 0.0132
7.71 7.76 7.85 7.22
5.27 5.25 5.27 5.13
272.5 285.4 322.5 153.1
2.30 2.36 2.39 2.06
93.5 91.0 89.4 108.8
0.0107 0.0110 0.0112 0.0092
64k
BPE Det Bias Int
16.7% 16.6% 17.5% 15.8%
0.0301 0.0313 0.0334 0.0195
8.79 8.84 8.91 7.82
6.68 6.33 6.37 5.55
432.4 475.6 519.6 245.6
2.57 2.63 2.65 2.30
72.7 69.9 69.1 90.1
0.0138 0.0143 0.0145 0.0111
128k
BPE Det Bias Int
9.4% 9.7% 10.0% 9.3%
0.0405 0.0442 0.0459 0.0321
9.52 9.70 9.74 8.72
7.25 6.83 6.85 6.37
632.3 742.1 779.8 469.7
2.83 2.91 2.92 2.66
61.0 57.9 57.6 69.6
0.0164 0.0173 0.0174 0.0144
256k
BPE Det Bias Int
5.4% 5.8% 5.9% 5.2%
0.0548 0.0608 0.0624 0.0391
10.28 10.41 10.46 9.09
7.71 7.56 7.60 6.74
951.0 1,107.0 1,140.2 590.3
3.10 3.19 3.19 2.80
51.9 49.8 49.9 63.9
0.0193 0.0201 0.0200 0.0157
15
F
Plots for Intrinsic Results on the FLORES+ Dataset
Figure 4: Compression by the different tokenisers. (Left) absolute and (Right) relative to BPE.
Figure 5: Vocabulary utilisation by different tokenisers. (Left) absolute and (Right) relative to BPE.
Figure 6: Type-token ratio by different tokenisers. (Left) absolute and (Right) relative to BPE.
Figure 7: Token length of different tokenisers. (Left) absolute and (Right) relative to BPE. 16
Figure 8: Tokens per line of different tokenisers. (Left) absolute and (Right) relative to BPE.
Figure 9: Shannon entropy of different tokenisers. (Left) absolute and (Right) relative to BPE.
Figure 10: Rényi entropy of different tokenisers. (Left) absolute and (Right) relative to BPE.
Figure 11: Average rank of different tokenisers. (Left) absolute and (Right) relative to BPE. 17
G
Plots for Intrinsic Results on a Subset of the Tokenisers’ Training Data
Figure 12: Compression by the different tokenisers. (Left) absolute and (Right) relative to BPE.
Figure 13: Vocabulary utilisation by different tokenisers. (Left) absolute and (Right) relative to BPE.
Figure 14: Type-token ratio by different tokenisers. (Left) absolute and (Right) relative to BPE.
Figure 15: Token length of different tokenisers. (Left) absolute and (Right) relative to BPE. 18
Figure 16: Tokens per line of different tokenisers. (Left) absolute and (Right) relative to BPE.
Figure 17: Shannon entropy of different tokenisers. (Left) absolute and (Right) relative to BPE.
Figure 18: Rényi entropy of different tokenisers. (Left) absolute and (Right) relative to BPE.
Figure 19: Average rank of different tokenisers. (Left) absolute and (Right) relative to BPE. 19
H
Plots for Intrinsic Results on a Held-out Set of ClimbMix
Figure 20: Compression by the different tokenisers. (Left) absolute and (Right) relative to BPE.
Figure 21: Vocabulary utilisation by different tokenisers. (Left) absolute and (Right) relative to BPE.
Figure 22: Type-token ratio by different tokenisers. (Left) absolute and (Right) relative to BPE.
Figure 23: Token length of different tokenisers. (Left) absolute and (Right) relative to BPE. 20
Figure 24: Tokens per line of different tokenisers. (Left) absolute and (Right) relative to BPE.
Figure 25: Shannon entropy of different tokenisers. (Left) absolute and (Right) relative to BPE.
Figure 26: Rényi entropy of different tokenisers. (Left) absolute and (Right) relative to BPE.
Figure 27: Average rank of different tokenisers. (Left) absolute and (Right) relative to BPE. 21
I
Loss across Training for the Various Models
(a) Val BpB for Depth 12 8k and 16k
(b) Train loss for Depth 12 8k, and 16k
(a) Val BpB for Depth 12 32k, and 64k
(b) Train loss for Depth 12 32k and 64k
(a) Val BpB for Depth 12 128k, and 256k
(b) Train loss for Depth 12 128k, and 256k
(a) Val BpB for Depth 18
(b) Train loss for Depth 18
22
(a) Val BpB for depth 24
(b) Train loss for depth 24
J
Detailed Results on Downstream Tasks
J.1
Plots for Robustness Experiments as well as for Various Depths
Figure 33: (left) BpB and (right) CORE vs. vocabulary size across models with different depths.
Figure 34: (left) BpB and (right) CORE vs. vocabulary size across three training seeds. All these models were trained with 12 layers. 23
Table 8: Downstream Performance (2/3) — Depth 12 [H] Vocabulary Size
Tokeniser
8k
OpenBook QA
LAMBADA OpenAI
Hellaswag
Winograd
Winogrande
BigBench Dyck Lang.
AGIEval LSAT-AR
BPE Bias Det
0.3180 0.3220 0.3200
0.2860 0.2700 0.2840
0.3320 0.3600 0.3400
0.5971 0.5604 0.5604
0.5520 0.5200 0.5300
0.0860 0.0980 0.1040
0.2304 0.2913 0.2348
16k
BPE Bias Det
0.3140 0.3240 0.3180
0.2900 0.2680 0.2840
0.3240 0.3540 0.3580
0.5531 0.5714 0.5824
0.5080 0.4920 0.5020
0.0920 0.1160 0.1180
0.2435 0.2435 0.1870
32k
BPE Bias Det
0.3160 0.3160 0.2860
0.3060 0.3080 0.3140
0.3680 0.3540 0.3780
0.5971 0.5714 0.5568
0.5160 0.5420 0.5300
0.1260 0.0400 0.0480
0.2435 0.2174 0.2174
64k
BPE Bias Det
0.3000 0.2900 0.3320
0.3040 0.3020 0.3080
0.3580 0.3680 0.3700
0.5897 0.5714 0.5824
0.5360 0.5360 0.5020
0.1300 0.1000 0.1080
0.2348 0.2391 0.2130
128k
BPE Bias Det
0.2680 0.3000 0.3040
0.3140 0.3040 0.3260
0.3700 0.3740 0.3640
0.5824 0.5897 0.5788
0.5200 0.5120 0.5060
0.1640 0.1260 0.1320
0.2043 0.2652 0.2261
256k
BPE Bias Det
0.2880 0.2880 0.2780
0.3060 0.2980 0.3140
0.3760 0.3820 0.3600
0.5861 0.5714 0.5788
0.5080 0.5200 0.4720
0.1440 0.1140 0.1180
0.2261 0.2217 0.2304
J.2
Depth 12
Table 7: Downstream Performance (1/3) — Depth 12 Vocabulary Size
Tokeniser
Hellaswag Zeroshot
Jeopardy
BigBench QA Wikidata
ARC Easy
ARC Challenge
COPA
Commonsense QA
PIQA
8k
BPE Bias Det
0.3260 0.3540 0.3300
0.0120 0.0080 0.0060
0.1080 0.1840 0.1460
0.4540 0.4520 0.4660
0.2580 0.2380 0.2500
0.5500 0.5700 0.5300
0.2660 0.3420 0.2960
0.6760 0.6840 0.6700
16k
BPE Bias Det
0.3400 0.3500 0.3620
0.0080 0.0060 0.0080
0.1900 0.2000 0.2300
0.5160 0.5240 0.5260
0.2700 0.2840 0.2680
0.5500 0.5600 0.5400
0.3180 0.3280 0.3140
0.6680 0.6780 0.6740
32k
BPE Bias Det
0.3660 0.3720 0.3860
0.0100 0.0120 0.0100
0.3380 0.2920 0.3060
0.5720 0.5560 0.5880
0.2720 0.2680 0.2820
0.5600 0.5600 0.6300
0.2560 0.3280 0.3760
0.6900 0.6820 0.6780
64k
BPE Bias Det
0.3660 0.3780 0.3740
0.0180 0.0100 0.0280
0.2900 0.3400 0.3080
0.6080 0.5840 0.5940
0.2860 0.3180 0.2940
0.5900 0.6200 0.5800
0.3380 0.3860 0.2540
0.6860 0.7000 0.7080
128k
BPE Bias Det
0.3840 0.3840 0.3720
0.0260 0.0140 0.0140
0.3760 0.3800 0.4180
0.6080 0.6060 0.6100
0.2660 0.3120 0.2960
0.5400 0.5700 0.6000
0.3680 0.2240 0.2280
0.6920 0.6940 0.6940
256k
BPE Bias Det
0.3960 0.3800 0.3800
0.0200 0.0220 0.0300
0.3520 0.3740 0.4060
0.6100 0.6080 0.6260
0.2880 0.2980 0.2880
0.6000 0.5200 0.6000
0.3320 0.3640 0.2580
0.6880 0.6920 0.6980
24
Table 9: Downstream Performance (3/3) — Depth 12 Vocabulary Size
Tokeniser
BigBench CS Alg.
BigBench Operators
BigBench Repeat Copy
SQuAD
CoQA
BoolQ
BigBench Lang. ID
8k
BPE Bias Det
0.4560 0.4340 0.4480
0.0905 0.1095 0.0762
0.0000 0.0000 0.0312
0.2120 0.1660 0.1660
0.1800 0.1600 0.2040
0.5620 0.4900 0.5140
0.2700 0.2660 0.2660
16k
BPE Bias Det
0.4740 0.4640 0.4680
0.1095 0.1095 0.0905
0.0000 0.0000 0.0312
0.1600 0.1080 0.1280
0.1520 0.1920 0.1960
0.4240 0.5540 0.5640
0.2760 0.2920 0.2740
32k
BPE Bias Det
0.4060 0.4240 0.4160
0.0857 0.0905 0.1333
0.0000 0.0000 0.0000
0.2000 0.1240 0.2340
0.1620 0.1500 0.2000
0.4960 0.5100 0.5000
0.2460 0.2640 0.2600
64k
BPE Bias Det
0.4440 0.4400 0.4440
0.1286 0.1143 0.1238
0.0000 0.0312 0.0000
0.1660 0.2760 0.2620
0.1880 0.2040 0.2100
0.5200 0.5120 0.5180
0.2860 0.2360 0.2560
128k
BPE Bias Det
0.3900 0.4060 0.4460
0.1190 0.0762 0.0667
0.0312 0.0000 0.0312
0.1520 0.2300 0.1780
0.2000 0.1700 0.1640
0.5200 0.5160 0.5600
0.2480 0.2420 0.2580
256k
BPE Bias Det
0.4280 0.4360 0.4440
0.1095 0.1048 0.0810
0.0000 0.0312 0.0000
0.1980 0.1960 0.1900
0.1620 0.1780 0.1600
0.5440 0.5040 0.5000
0.2500 0.2720 0.2440
J.3
Depth 18
Table 10: Downstream Performance (1/3) — Depth 18 vocabulary size
Hellaswag zeroshot
Tokeniser
Jeopardy
BigBench QA Wikidata
ARC Easy
ARC Challenge
COPA
Commonsense QA
PIQA
8k
BPE Bias
0.4560 0.4440
0.0320 0.0120
0.3620 0.3240
0.5860 0.5720
0.3460 0.3320
0.6300 0.6000
0.2120 0.2300
0.7040 0.7160
32k
BPE Bias
0.4680 0.4700
0.0460 0.0400
0.4100 0.3920
0.6660 0.6580
0.3700 0.3660
0.6700 0.6600
0.3140 0.3140
0.7420 0.7260
128k
BPE Bias
0.4980 0.4900
0.0780 0.0700
0.4680 0.4560
0.7080 0.7040
0.3980 0.3900
0.6400 0.6300
0.4140 0.3240
0.7480 0.7280
Table 11: Downstream Performance (2/3) — Depth 18 vocabulary size
Tokeniser
OpenBook QA
LAMBADA OpenAI
Hellaswag
Winograd
Winogrande
BigBench Dyck Lang.
AGIEval LSAT-AR
8k
BPE Bias
0.3620 0.3700
0.3600 0.4020
0.4440 0.4440
0.5971 0.6007
0.5260 0.5480
0.1260 0.1320
0.2391 0.2130
32k
BPE Bias
0.3740 0.3780
0.3940 0.3980
0.4600 0.4560
0.6630 0.6520
0.5340 0.5440
0.1320 0.0320
0.2565 0.2348
128k
BPE Bias
0.3420 0.3440
0.3740 0.3880
0.4940 0.4940
0.6044 0.6484
0.5400 0.5400
0.1320 0.1280
0.2652 0.2304
25
Table 12: Downstream Performance (3/3) — Depth 18 vocabulary size
Tokeniser
BigBench CS Alg.
BigBench Operators
BigBench Repeat Copy
SQuAD
CoQA
BoolQ
BigBench Lang. ID
8k
BPE Bias
0.4420 0.4280
0.1571 0.1810
0.0000 0.0312
0.3020 0.2900
0.2260 0.2640
0.5580 0.5580
0.2840 0.2580
32k
BPE Bias
0.4400 0.4320
0.1381 0.1476
0.0000 0.0000
0.3760 0.2500
0.2460 0.2420
0.5680 0.6020
0.2600 0.2660
128k
BPE Bias
0.4520 0.4660
0.1524 0.1429
0.0000 0.0000
0.3940 0.3520
0.2420 0.2980
0.4860 0.5900
0.2560 0.2480
J.4
Depth 24 Table 13: Downstream Performance (1/3) — d24
vocabulary size
Tokeniser
Hellaswag zeroshot
Jeopardy
BigBench QA Wikidata
ARC Easy
ARC Challenge
COPA
Commonsense QA
PIQA
8k
BPE Bias
0.5640 0.5840
0.0740 0.0660
0.4660 0.4760
0.6660 0.6600
0.4220 0.4000
0.7100 0.6800
0.3260 0.2260
0.7400 0.7700
32k
BPE Bias
0.5940 0.5860
0.1120 0.1280
0.5240 0.5160
0.7280 0.7200
0.4380 0.4300
0.6600 0.6300
0.2680 0.2600
0.7680 0.7560
128k
BPE Bias
0.5820 0.5840
0.1720 0.1640
0.5320 0.5280
0.7260 0.7540
0.4280 0.4200
0.6700 0.7000
0.3440 0.2820
0.7620 0.7820
Table 14: Downstream Performance (2/3) — d24 vocabulary size
OpenBook QA
LAMBADA OpenAI
Hellaswag
Winograd
Winogrande
BigBench Dyck Lang.
AGIEval LSAT-AR
BPE Bias
0.3780 0.3880
0.4460 0.4180
0.5560 0.5800
0.6813 0.6740
0.5280 0.5900
0.1160 0.1340
0.2652 0.2739
32k
BPE Bias
0.4040 0.4340
0.4760 0.4740
0.5900 0.5900
0.6703 0.6813
0.5540 0.5680
0.1360 0.0620
0.2522 0.2565
128k
BPE Bias
0.3760 0.3700
0.4620 0.4620
0.6000 0.5980
0.7436 0.6667
0.5760 0.5700
0.1300 0.1300
0.2522 0.2783
8k
Tokeniser
Table 15: Downstream Performance (3/3) — d24 vocabulary size
Tokeniser
BigBench CS Alg.
BigBench Operators
BigBench Repeat Copy
SQuAD
CoQA
BoolQ
BigBench Lang. ID
8k
BPE Bias
0.4320 0.4500
0.2048 0.1619
0.0312 0.0312
0.4220 0.4040
0.3020 0.2800
0.5820 0.5600
0.2820 0.2760
32k
BPE Bias
0.4340 0.4520
0.1619 0.2048
0.0000 0.0000
0.4740 0.5100
0.2880 0.3300
0.5840 0.6200
0.2400 0.2740
128k
BPE Bias
0.4380 0.4440
0.1952 0.1476
0.0000 0.0312
0.4580 0.4860
0.3220 0.2840
0.5960 0.6340
0.2420 0.2600
26