A Partition Cover Approach to Tokenization
Authors: Jia Peng Lim
Shawn Tan
Davin Choo
Hady W. Lauw
Venue: NeurIPS 2025 poster ()
Keywords: tokenization
large language models
Primary area: deep_learning

Abstract: Tokenization is the process of encoding strings into tokens of a fixed vocabulary size, and is widely utilized in Natural Language Processing applications. The leading tokenization algorithm today is Byte Pair Encoding (BPE), which formulates the tokenization problem as a compression problem and tackles it by performing sequences of merges. In this work, we formulate tokenization as an optimization objective, show that it is NP-hard via a simple reduction from vertex cover, and propose a polynomial-time greedy algorithm GreedTok. Our formulation naturally relaxes to the well-studied weighted maximum coverage problem which has a simple $(1 - 1/e)$-approximation algorithm GreedWMC. Through empirical evaluations on real-world corpora, we show that GreedTok outperforms BPE and Unigram on compression and achieves a covering score comparable to GreedWMC. Finally, our extensive pre-training for two transformer-based language models with 1 billion parameters, comparing the choices of BPE and GreedTok as the tokenizer, shows that GreedTok achieves a lower bit per byte even when we control for either the total dataset proportion or total training tokens.

A Partition Cover Approach for Tokenization
Jia Peng Lim Singapore Management University
Shawn Tan
MIT-IBM Watson Lab
jiapeng 1im. 2021 @phdcs. hepppcs.suu.eeeeee.emmmoomom smu.edei edu. sg
shawntan@i Serrrtan@ibb..... com
Davin Choo
Hady W. Lauw"
Harvard University davinchoodseas. harvard. edu
Singapore Management University hady=lauv@smu. edu.sg
Abstract
Tokenization is the process of encoding strings into tokens of fixed vocabulary size, and is widely utilized in Natural Language Processing applications. The lead- ing tokenization algorithm today is Byte-Pair Encoding (BPE), which formulates the tokenization problem as a compression problem and tackles it by performing optimization
sequences of merges. In this work, we formulate tokenization objective, show that it is NP-hard via simple reduction from vertex cover, and propose a polynomial-time time greedy algorithm GREED Our formulation nat- urally relaxes to the well-studied weighted maximum coverage problem which algorithm GREED MC.. Through empir-
has a simple (1 -eee)-appoximaatee ical evaluations on real-world corpora, we show that GREEDTOK outperforms BPE and UNIGRAM on compression and achieves a covering score comparable to GREEDWMC. Finally, our extensive pre-traine pre-training for two transformer-baat language models with 1 billion parameters, comparing the choices of BPE and GREEDTOK as the tokenizer, shows that GREEDTOK achieves a lower bit per byte even when we control for either the total dataset proportion or total training tokens.
1 Introduction
Tokenization encodes text into tokens from fixed vocabulary and fundamental to Natural Lan- guage Processing (NLP) applications. With Large Language Models (LLMs) growing in prominence, understanding tokenization has become increasingly important, as it plays an integral role in their architectures and even modest gains in efficiency can yield substantial computational savings. Fur- thermore, LLMs such as LLaMA [TLI*23] 23] and Mistral [JSM 23) use fixed-length context windows, which will benefit from tokenizers with better compression utility that enables them fit more information within their context window. There are also prompt-based [WWS+ 22, YYZ+233 and fine-tuning [FTL+22] techniques that increase the number of processed tokens improve model performance.
A common way to formalize the tokenization problem is compression task that minimizes the ratio tokens produced when tokenizing the input data. The leading tokenization algorithm today is Byte-Pair Encoding (BPE) [Gag94, 36B16, KHM 23], which formulates the tokenization problem as a compression problem and tackles it by performing a sequence of pairwise merges. Due to its popularity, there have been multitude of recent works analyzing the theoretical properties of BPE (ZMG+23 23, KV24, WBP24J. Another approach frames tokenization as a pathing/sequence problem
'Equal Advising.
Part of the work was done while the author was affiliated with the National University of Singapore.
Singapore
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

[Kud18, SRZ Unigram [Kud18] is one such example and is favored by models with bidirectional contexts, i.e. [YDY+19] 19] and [RSR+20] Although UNIGRAM believed perform better pre- training tasks [BD20], its compression performance is weaker compared to BPE [SR7+244] 24], affecting its adoption for large-scale expensive pre-training in language modeling.
Contributions. In this work, we deviate from the usual path, sequence, and merge- tokenization formulations. Instead, we propose examine the tokenization problem as problem of covering.
C1. Partition cover formulation. We introduce a partition cover optimization formulation of the tokenization problem that goes beyond prior merge-base based approaches TZM+223, KV24]. These earlier methods rely on bottom-up pairwise merges from an existing token set. However, the idea of tokenization is simply to efficiently represent corpus with a judiciously selected set of tokens, whose construction is independent of such merge patterns. Our formulation subsumes these prior formulations in the following sense: all merge-based solutions valid solutions to our formulation, but a solution to our formulation need not be based on bottom-up pairwise merges.
C2. Simple NP-hardness proof. We provide simple and intuitive proof that tokenization is NP- hard in our optimization objective formulation via a reduction from vertex cover [Kar72]. Although there has been recent concurrent work [WBP24] that also showed that the tokenization problem is NP-hard, our proof is arguably simpler due to our formulation.
tokenizer. We propose polynomial timee greedy algorithm GREEDTOK that does not rely on a sequence of pairwise token merges or path construction. Evaluation on four real-world corpora shows that GREED outperforms BPE and UNIGRAM with a stronger compression of ~3% tokens per word. Our implementation and compression evaluations can be found at https: : //t/tttttb..... www.e/eeeeeeeert/paaaaaata
C3. New polynomial-ting
see supplementary materials.
C4. Downstream comparison. Preliminary analysis revealed that GREEDTOK' 's token sets si- multancously attain BPE's compressibility and UNIGRAM's ' token quality. To empirically validate downstream performance, we pre-trained two transformer- based LLMs with 1 billion parameters that differ only in the use of GREEDTOK or BPE as the tokenizer algorithm. Our results show that GREEDTOK outperforms BPE in both common benchmark tasks and in bits per byte, even after controlling for either the total dataset proportion or total training tokens.
C5. Empirical approximation of objective. Our partition cover formulation naturally relaxes to the well-studied weighted maximum coverage problem [Kar72, CK08] which has a simple (1 apprroioxiintooonn algorithm GREEDWMC MC [Hoc96]. We empirically show that GREEDTOK and MC achieve a comparable objective function value for large k. despite the latter being a relaxed problem. Although a formal approximation guarantee for GREED currently escapes us, our analysis holds for practical scenarios encountered by NLP practitioners and this empirical method of investigattin approximation guarantees may be of independent interest.
Related work. There has been a recent surge of interest in analyzing tokenization. [ZMG* 23] initiated formal study of BPE using bottom-up tokenization problem formulation that restricts token construction to sequential merges of two tokens from the existing vocubulary. [KV24) proved that this bottom-up tokenization problem, and its more general variant, is APX-complete using linear reduction [PY88] from maximum cut [Kar72] in cubic graphs. They also showed that BPE approximates worst-case factor of between 0.333 and 0.625 for their general variant. In a recent concurrent work, [WBP24] showed that both the bottom-up tokenization problem formulation and our partition cover formulation are NP-complete from the reduction of the maximum 2-satisfiability problem. Beyond theory, empirical studies such as [LBM23] and [SFWN23] have examined the practical downstream impact of tokenizer selection in NLP tasks. With regard to tokenizer-free free architectures [TTR 22, YSF+23, 23, PPR 24], our formulation draws the link to the fundamental binary decision problem of whether to merge adjacent characters, as one can view next-byte predictions as merging decisions.
Compared prior and concurrent works, our NP-hardness proof (Theorem 1) is arguably simpler due to our formulation, and we contribute a novel tokenizer that is competitive in real-world scenarios.
Outline of paper. We give our partition cover optimization formulation in Section 2, we prove that it is NP- hard in Section 3. GREEDTOK is designed in Section 4 and Section 5 contains our empirical evaluation against real world corpora. Finally, conclude with some discussions in Section 6.
Referred to optimal merge sequence and optimal pair encoding respectively in their work.

---

Notation. We use standard set notations such as |A| to represent the size of set A, and standard asymptotic notations such O()). Numbers are represented with small letters, strings/words with capital letters, and sets with bold letters. Unordered sets are denoted by {.) and ordered tuples are denoted by (.)- We describe words in plaintext, e.g., hello, or as tuple of singletons, e.g., (h.e.l...o).
A general optimization formulation for the tokenization problem
Let Σ be fixed alphabet, i.e., basic character set. This may be the 26 lowercase English letters or the full Unicode set, depending on the context. A corpus C = (W, COUNT) consists of a set of distinet words W C E+, and a count function COUNT W N that indicates word frequencies. Given a word W E Σ and a set of tokens S S Σ+, let PARTITION (RRTTTION(WW.... S) denote the minimum number of tokens from S that can be concatenated in sequence form W. For example, the word W = abc can be tokenized as abue but not as acub, despite both token sets covering the same characters.
The goal of minimizing the total number of tokens used to represent a corpus is often referred to as optimizing compression utility.
Problem (Tokenization search problem Tok). Let E be fixed alphabet and define the base token set {(w) : w E Σ} as all singleton characters. Given a corpus = (W, COUNT), token budget & E Nyo. and set of candidate tokens T C Σ+, the goal is to find subset S C T such that [S] S k and Ewew PARTITION(W; (UN SUB) COUNT(W)) is minimized. Note that tokens are candidate substrings drawn from E that may may not correspond to actual words.
As in standard practice, we consider the corresponding decision variant to establish NP-hardness. Once the decision variant is shown to be NP-hard, the search problem inherits this hardness, since solving the search version yields a solution to the decision version by evaluating different thresholds (in our case, the value f).
Problem 2 (Tokenization decision problem). With the same setup Problem 1, and given an additional integer threshold E No determine whether there exists subset C T such that |S| k and Wwew PARTITION (W, S B)- COUNT(W) S f.
Our formulation differs subtly but significantly from prior tokenization models, such as those in [ZMG+23, KV24]. Rather than viewing tokenization through the lens of string compression algo- rithms, we reduce tokenization to the following question: Are Iwo adjaceni singleton symbols within string covered by the same token? This perspective emphasizes that tokenization is fundamentally about selecting a compact vocabulary that fully covers the corpus without imposing algorithmic constraints such as bottom-up merge sequences, which are artifacts of specific approaches like BPE. We further elaborate on the implications of our formulation in Section 4.1.
3 Tokenization is NP-hard
In this section, we prove that the tokenization decision problem (Problem 2) NP-hard by a reduction from the vertex cover problem, which is known to be NP-hard [Kar72]. Given graph == (V, E) with vertex set V and edge set E, a vertex cover is a subset S C of vertices such that for every edge {U, VJ } E. The decision variant of the vertex cover problem asks whether there exists a subset S of size at most
[S (U VH
Theorem 1. The tokenization problem is Nardard.
Proof. We will prove this by reducing the vertex cover problem, which is known to be NP-hard [Kar72], to the tokenization problem. Given an arbitrary vertex cover problem instance, we show how to construct a corresponding tokenization instance. Then, we argue that the derived tokenization problem instance is a YES instance if and only if the original vertex cover problem instance is a YES instance. In this proof, for clarity, will write words W E W as tuple of singletons instead of usual plaintext, e.g. (h,e.I.I,o) instead of hello.
Construction. Consider an arbitrary vertex cover problem given by the graph g = (V, E) over n vertices V = (V,..... Vn and a positive integer E Ngo- To construct an instance of the tokenization problem, first define the alphabet as follows: Σ (Vi,... Vn, @) where @ is
3

---

an additional symbol which we will use later. So, we have B = (V1)..... (Va). (Q)). For each edge {V, V2} E with i < j. we create word W,; (a. V, @. V, @) and define the set of words as W = [Wa, [V, V E E] where each word has count 1, i.e. COUNT(W) 1 for all W E W. Then, we define the set of candidate tokens T { V, @) Vi E V). Finally, we set l = 3 [ 3|E] and associate the parameter k in the vertex cover problem instance to the corresponding parameter &o in the tokenization problem instance. One can check that this derived tokenization instance can be constructed in polynomial time.
Observation. Observe that every word W E W has length and each token in has length 3, so PARTITION(W, S U B) will either be 3, when there is some token in S that is contiguous subword of W. or otherwise. For instance, given the word W., PARTITION(W:) i.j: S U BB) = 3 if and only if at least one of (@, V,, @) or @0, Vj. @) chosen in S (both could in S). Furthermore, since all words have count 1, the tokenization problem becomes finding S C T such that |S| S k and Σ Weww PARTITION(W, S BUB) S t W/
(@, Vi, @, Vg. @), we have
YES instance of tokenization problem YES instance of vertex cover. Suppose there exists subset S _ T of tokens such that [S] S k and Wwew PARTITION(W, U B) S t = W| Then, from the observation above, we know that this can only happen when PARTITION W S SUSSU B =
for every W W. This implies that for each word Wa at least one of (@, V, @ @.. V @ is
chosen in S. Therefore, Sç = (V: E V : (@, Vi, @) E S} is a subset of size SSpl = S S k and corresponds to vertex cover of the original graph G.
YES instance vertex cover to YES instance of tokenization problem. Suppose the original vertex cover instance for graph G = (V, E) has vertex cover Sg of size [Syl k. Then, let us define = {(,, Vi, @) E + V, S as the set of chosen tokens of size [S] = |Sgl S k. Since Sg is set cover for G, by construction of W, we see that PARTITION(W, S U B) = 3 for all W E W. Therefore, Ewew PARTITION(W, S U B) = 3/W
Example 1. Consider vertex cover instance on a graph g = (V, E) with vertices V = (V..... V/3} and edges E = (1V,, V2), (V, Va), (Vi, Va), (12, V3), (V2, Va), (V3, V3}} where the subset S (Vi, V3, VaJ is a vertex cover of size [S] = = 3. Fig. illustrates the corresponding tokenization problem instance created according to the construction in the proof of Theorem 1.
(V., 16, 14 9)
B (VS), (V)), (G))
W [(0) Vi, 122 0), Vi 8). 8.V.
V/
(0), V2, V4 (8,
R.
(8. v).
COUNT(WW)
VW W T [ Vi, V..
V/S
VA
8 3/W| 3|F 18
Figure 1: An example tokenization problem instance construction according to the proof of Theorem 1. The tokens corresponding to the vertex cover S = (V1, V3, V.} are underlined in T. A possible tokenization of W using U B also given with tokens in being underlined, showing that each word in W only needs 3 tokens.
4 GREEDTOK: Our greedy tokenizer
Challenges in designing an efficient algorithm. In Section 3, we showed that the tokenization problem (Tok) is NP-hard. Developing efficient algorithms for NP-hard problems typically involves strategies that trade off between exactness, runtime, and solution quality. Since our focus is on scalable, real-world applications, we aim for polynomial-ting approximations and do not pursue fixed-parand saremmarrmeter tractable algorithms. Unfortunately. the common approximation strategies that are used to design efficient algorithms for Narhard problems with provable approximation guarantee are not applicable here. Firstly, while submodular functions admit efficient greedy (1 (1-12 (1-l approximations [NWF78], our objective is neither submodular nor supermodular (see Appendix A). Secondly, relax-and-roume methods, like those used for vertex cover [WS1 1], become impractical due to the sheer scale of real-world corpora which induces large numbers of variables and constraints.

---

4.1 An equivalent mixed integer program formulation
To design our algorithm GREEDTOK for Tok, we begin by reformulating the problem terms of a mixed linear program (MIP). This serves two purposes. First, the MIP provides straightforward and intuitive framework that simplifies the definition and implementation of our greedy algorithm. Second, it naturally relaxes to the well- weighted maximum coverage problem (WMC), which is submodular and admits greedy (1 - 1/e) a/e))-pproximmaton algorithm [Hoc96, Scction 3.9]. Although cannot formally establish approximation guarantees for GREED its connection to WMC enables empirical comparisons with GREEDWMC in TOK instances; see Section 5.3.
We define COVER S) as the maximum number of adjacent singletons in word W that can be grouped into tokens from S, with each character used at most once. For example, with W scaredy and S {care, edy), we have COVER W S) 3 from concatenating 3 adjacent singleton pairs in "care". constrained on the position of 'e" which can only be used once. Meanwhile, PARTITION(W, SU B) 4 via s s_care_duyy. Notice that [W] PARTITION COVER. This lets us rewrite the minimization objective from Problem as an equivalent maximization objective:
min
Σ COUNT(W) PARTITION(W, WU, SUB) max Σ COUNT(W) COVER(W,S) WeW
WeW
We refer to both forms ToK. Now, recall that W represents the set of words in the corpus where each word W = -W1, (W..... )( E W has length [W] and appears with frequency COUNT(W) 2
1. Although our formulation permits any candidate token set T, identifying optimal solution requires considering all substrings of length 2 2 within W, i.e. there a total number of (T) < Ewew (1W) - IW1) such substrings, where (W)
2 counts all start-end pairs, and we subtract [W] to exclude singletons. In the following, we the notation A C B to denote that A is substring of B, e.g. for C force, and adopt 1 I-based indexing in the MIP below.
To formulate Problem I as an MIP, our goal is to choose a subset S C T of size S < k such that the following objective is maximized, encoding max > Wwew CO) COVER (W, S), where cw = COUNT(W):
[ Σ
max Σ cW WeW
W mi++1
with the binary variables IT {0, for all tokens T T (Did we choose token T E T, i.e. T S?), m... m m W W.... E (0, 1}. for all words W W (Are the tt singleton W. and the W.T (i + 1)th singleton W++1 covered by the same token?), and m12 W.T ,...,m/WI11.. E {0, 1), for all words W E W and tokens T' E T (Did token T E S cover the ith singleton We and the (i + 1)th singleton Ws+1?), under the following constraints:
ΣT FT < k.
W.T if (W, 11+ CT
JT 2 m
W.T
T m
2 1,41
Er mi $1,
W.T
W. V {1.....
[ 1}.
m mi+1,1z if (W,, W1, Wx+2) CT
W.T W.T
VW W, VT E T, Vie {I....,
| 2).
T W.T
m, $ m. W.T if (W,, Ws+1) starts T, VW W, T, Vs (2....,
| -].
1.
W.T if (Wa-1, We) ends T, T mee+1 < m
WT
VW E W, E T, (2.....// -1}.
For a more thorough explanation of our MIP formulation with examples, please refer to Appendix B.
4.2 Relation to weighted maximum coverage
Like the vertex cover problem, the weighted maximum coverage problem (WMC) is NP-hard [Kar72, WS11, Hoc96]. Given a of elements L ......., L } with weights W (wi,... W collection of subsets U {UI...., } where each U, C L, and an integer budget k. the goal is to select U' C U. such that [U'] < k. to maximize the total weights of covered elements ΣLEUv w,
5

---

With some effort, one can show that WMC admits mixed integer program with the same objective as Eq. (1) but with fewer constraints. Details are provided in Appendix C.
Implication. Since WMC shares the same objective as ToK but under weaker constraints, its optimal value is at least that of Tok. As WMC admits (1 a/pproappoo greedy algorithm (GREEDWMC) MC)) this guarantee also applies to its performance in TOK instances, although the solution from GREEDW MC may violate tokenization constraints. Nevertheless, if GREEDTOK achieves objective values comparable to GREEDWMC, it suggests that GREEDTOK may offer similar approximation ratio for Tok despite lacking formal guarantees.
4.3 A polynomial-ting greedy algorithm
We now informally describe algorithm, GREEDTOK, which consists of two main steps: (I) selecting a token set S from candidate substrings T, and (2) tokenizing words W using S; see Appendix G for pseudocode and examples.
We begin by constructing the candidate token set T, considering all substrings of length 2 within the words W in the corpus. Then, for any S C T. let f(S) be the objective value in our MIP formulation (see Section 4.1). Starting with = 0, we iteratively add tokens to S by selecting argmaXTeTis f(S u (T)) S(S), subject to MIP constraints, to S until SS = k. This process induces a natural ordering within the tokens in S.
To tokenize word W E W using S, scan its singletons to identify possible matches to the tokens in S and sort these matches by the order in which the tokens were added to S. We then iterate through these candidate covers and, if the cover satisfies the MIP constraints, mark the corresponding positions in a bitmask W to cover the substring with the selected token.
A direct implementation yields a runtime of O([T] k. Ewew [WI) when selecting S and (([ log [W]) when tokenizing a word W. Note that this token ordering arises from the greedy nature of GREEDTOK but is not required for solving Tok, just as merge sequences are not fundamental to tokenization. Despite the higher asymptotic costs than BPE, we show in Section 5.1 that with implementation optimizations. GREEDTOK is practical for real-world NLP use.
Comparing to BPE. GREEDTOK's token order resembles the merge sequence in BPE, as both select one token per iteration. However, GREEDTOK operates without the constraints of pairwise merges, allowing more flexible token selection. BPE beats GREEDTOK in terms of computational complexity, with selection cost of O(k Σ Ewew [WI) and per-word tokenization cost of ((W when using the pairwise caching approach [Ope23]. However, this selection cost is a one-off cost that does not affect downstream applications. Additionally, we empirically show that the modest overhead of O(log [W]) in tokenization is worth the improvements in downstream tasks; see Section 5.
Comparing to UNIGRAM. UNIGRAM'S likelihood objective L can be interpreted
negative
log-weighted version of TOK; see derivation in Appendix D and example where optimizing L may yield unfavorable behavior. While both GREEDTOK and UNIGRAM freely select tokens from T, UNIGRAM prunes T to size [S] = k. while GREED TOK builds S up from 0. Computational complexity wise, UNIGRAM's selection cost of O(T)) log Ewew [W]) beats GREEDTOK's 's but its per-word tokenization cost of O(k |W]) exceeds GREEDTOK's 's when k >>> [W] [W With large k being common in practical real-world use cases, this is one reason why UNIGR AM is often not used in production systems despite being known produce higher-quality tokens [BD20, SRZ* 24].
Empirical evaluation of GREEDTOK on real-world datasets
Our implementation of GREEDTOK is on C++ and accessible using Python bindings or through HuggingFace's 's API via simple import line, enabling easy integration onto existing codebases.
5.1 Evaluating GREEDTOK's compression
We compared GREEDTOK against BPE and UNIGRAM by measuring compression performance across four real-world corpora at varying token budget levels [S] = k; see Table 1. We define the singleton set B as all 256 byte values, W as the set of space-delimited UTF-8 strings (byte sequences) extracted from each corpus, and introduce special token to mark the start of string following

---

Table 2: This table reports the compression performance of GREEDDOK/BPE/UIGGR. For UNIGRAM, we increase the input & by 75/84/1088/4 respectively to account for the compulsory character inclusion into T. GREEDTOK (GTK) outperforms BPE and UNIGRAM in larger corpora
algorithms.
(arXiv, PubMed, wiki), with mean improvement of 2.88% over BPE and 3.43% over UNIGRAM,
k
1000
2000
3000
4000
5000
2000
4000
6000
8000
10000
GTK Tokens/Word
1.607
1.374
1.268
1.205
1.163
1.603
1.397
1.301
1.244
1.206
BPE Tokens/Word
1.688
1.431
1.311
1.241
1.194
PubKed
1.650
1,431
1.328
1.266
1.225
GTK's 's Improvement (%)
4.86
3,99
3.33
2.92
2.54
2.85
2.38
2.02
1.75
1.52
UNIGRAM Tokens/Word
1.655
1,385
1,261
1.193
1.148
1,699
1,465
1,359
1.297
1.257
GTK's & Improvement (%)
2.90
0.78
-0.51
-0.97
-1.30
5.63
4.63
4.21
4.05
4.02
GTK Tokens/Word
1.742
1,475
1,349
1,275
1.226
1.692
1,489
1,389
1.326
1.283
BPE Tokens/Word
aryiv
1.837
1,551
1.407
1.320
1.263
1.731
1,519
1,413
1.347
1.301
GTK's 's Improvement (%)
5.12
4.94
4.15
3.41
2.89
2.26
1.98
1.71
1.53
1.37
UNIGRAM Tokens/Word
1.793
1,558
1.444
1.378
1.332
1.793
1.558
1.444
1.378
1.332
GTK's s Improvement (%)
6.74
4.92
4.30
3.96
3.88
5.62
4.43
3.84
3.75
3.70
space character. The function COUNT maps each W E W its frequency the corpus in UTF-8 format. The candidate token set T for GREEDTOK includes all substrings of words in W while UNIGRAM'S 's is at the character level. In contrast, BPE begins with an empty T and builds tokens incrementally from B, depending on the final [S] = k. Thus, both GREED and BPE produce final token sets of size [B] + k. However, in addition, we allow UNIGRAM to include frequent (possibly multibyte) characters in the final vocabulary due to the sentencepiece implementation, Le. it has a final token set size larger than B
Discussion. We see from Table 2 that GREED- ToK consistently uses fewer tokens on average to represent the same data. Since BPE relies on repeated applications of merge rules to build large tokens, this suggests that many intermedi- ate tokens created during merging may never be used in the final encoding, effectively wasting vocabulary capacity that could be allocated to more useful tokens. Meanwhile, our example in Appendix D that UNIGRAM can over-prion pver-prioritiie whole words the expense of informative subword tokens, and the empirical
Table 1: Dataset statistics and the time taken for compute with word counts as inputs, conducted with AMD EPYC 9654 @ 2.40GHz. Refer to Appendix F.I for additional dataset descriptions.
Dataset
[W]
Σw cw
TT
max [S]
Time
UN arxiv wiki PubMed
105K
37M
884K
5K
6s
know from
881K
366M
7,626K
5K
63s
8,769K
2,949M
93.5M
10K
11m
6,527K
4,149M
121M
10K
11m
results of Table 2 confirms suspicion that such suboptimal scenarios are not rare.
5.2 Evaluating GREEDTOK's language pre-training
In Appendix E, show empirical evidence that the token sets produced by GREEDTOK more closely resemble UNIGRAM than BPE, suggesting that they may inherit some UNIGRAM's 's favorable token characteristics. To test this hypothesis, we pretrain two IB --paramettr language models (details in Appendix F.2), differing only in tokenizer choice - GREEDToK versus BPE. Both models vocabulary size of 65,536 and are trained on approximately 20% of the DCLM Dedup dataset [TGD+24, LFS with their final token sets being 75% similar.
Table 3: The token count statistics for all three settings. GREEDTOK uses nearly 18% fewer tokens to represent the entire DCLM Dedup dataset. The total training tokens used around 629B tokens.
Experiment Name
Tokenizer
Full dataset tokens
Training tokens
Dataset %
BPEM
BPE
8.94
10t1
6.29 10
70.35%
Equal Tokens (GTET)
GREEDTOK
7.35 10
6.29 10"1
85.58%
Equal Proportion (GTEP)
GREEDTOK
7.35 10
5.03 10
68.47%
Wee use BPE the baseline, given its status the most widely adopted tokenizer for LLMs [KHM*23]
7

---

We compare the BPE-based model (BPEM) against two versions (GTET and GTEP) of the GREEDTOK-baud based model under different training constraints, summarized Table 3:
1. GREEDTOK Equal Tokens (GTET), Trained using the same number of tokens BPEM. This setting isolates the impact of denser token representations by fixing the token count.
GREEDTOK Equal Proportion (GTEP), Trained using the same proportion of the original dataset BPEM. Here, the number of training tokens differs, based on each tokenizer's com- pression ratio, allowing us to examine the effect of using fewer tokens from equivalent text coverage.
Evaluation. We use the popular Language Model Evaluation Harness [GTA 24] toolkit and their predefined evaluation settings to evaluate BPEM, GTET, and GTEP. Several popular bench- mark sets were used for evaluation, refer to Appendix F.3 for more information.
0.88
GreedTok
0.88
GreedTak
Byte-pair Encoding
Byte-pair Encoding
Bits litsgerbyle byte on Wikiext
0.86
Bits ger byte on Wikitoxt
0.86
0.84
0.84
0.82
0.82
0.80
0.76
0.76
0.74
0.74
5
0.0
0.2
0.4
0.6
0.8
Taken count
(a) Comparing along number of tokens trained.
(b) Comparing along amount of text trained.
Figure 2: We plot the bits/byte improvement across phase training for model using GREEDTOK and BPE on different scales. The bits/byte metric is independent of tokenization and reflects true compression performance on the underlying data, Since both GTET and GTEP are equivalent in phase for the first 100,000 steps, we examine bits/byte improvement on Wikitext with different scales on the x-axes.
Table 4: Evaluation results on popular benchmarks. GTET/GTEP obtained better scores than BPEM.
Accunacy (normalized)
Accuracy
bits/byte
Hella- Swag
LAMB- BADA
Wino- grande
ARC-c
ARC-e
OBQA
PIQA
SciQ
BoolQ
COPA
RACE
Aug.
Wikitext
BPEM
36.2
67.9
65.6
75.7
61.1
36.4
0.7066
GTEP
37.6
68.8
64.9
39.6
75.6
90.0
67.6
79.0
63.9
36.8
63.5
62.5
0,7028
GTET
38.3
70.0
65.7
40.6
75.8
90.5
67.7
82.0
64.6
37.7
62.6
63.2
0.6989
Discussion. Previous works report either similar or a decrease in performance stemming from better compression [Gal19, GCE+ 24, SRZ+24, AFT+244, One plausible explanation for these results is that, given any sentence, a tokenizer with a lower compression rate uses more tokens, which results higher number of total activations in transformer during inference. This increase in the effective width of the transformer's ' computation circuit can increase its expressive power [PMB24], resulting in better performance for poorer compression. However, the results in Table show that GREED ToK, compared to its BPE counterpart, has achieved better compression while still maintaining model performance. This suggests example of meaningful compression, with both GTET and GTEP outperforming BPEM on the evaluated benchmarks. From Fig. 2a, when training on equal token count, GREED Tok is ahead. While Fig. 2b shows that, when normalized and trained on equivalent byte-lengths of data, GREEDTOK performs comparably to BPE highlighting competitive modeling capacity of GREEDTOK, despite structural differences in tokenization. Our results suggest that the higher compression rate of GREEDTOK does not negatively affect downstream performance. Furthermore, it is even possible achieve the same results with GREEDTOR while using fewer tokens for training.
8

---

5.3
Towards understanding GREEDTOK's apprrxmmabbll
corpus
arXiv corpus
PubMed corpus
wiki corpus
0.975
0.975
0.950
0.950
0.950
0.950
0.925
0.925
0.925
0.925
0.900
0.900
0.900
0.900
0.875
0.875
0.875
0.875
0.650
0.850
0.850
0.850
GreedTak
Unigram
0.600
0.800
0.800
0.800
1000
2000 3000
4000
5000
1000
2000
3000
4000
5000
2000
4000
6000
800010000
2000 4000 6000 800010000
k
Figure 3: Plots showing exact dine of each problem instance at different |S k. As increases, the ratio of objectives dina between SORREDTOO/BPP/UNIICO
and GREED WCC closes to 1.
We reformulated Problem into MIP in Section 4.1 it relaxes naturally into the maximum coverage problem, which has a corresponding (1 1/e) approximate algorithm GREEDWMC. Using
calculate the ratio of objectives between GREEDTOR and GREED W MC and define dmss- = GREEDWMC for each instance. Therefore, GREEDTOK attains an objective value al least dins (1 1/e) times the optimal objective Eq. (2) by definition, with GREED MC's objective value is at least that of TOK; see Section 4.2.
GREEDWMC the same problem instances of similar k, GREEDTOR
Discussion. From Fig. for the four selected corpora. we plot dinst against k, observing that increases, dims climbs towards 1. In ad- dition, to ensure that the results are general- izable the wider internet corpus, we evalu- ate on Ref RefinedWeb corpus, and obtain simi- lar findings; see Fig. 4. Empirically, GREED- ToK achieves an objective value of at least 0.9(1 1/e) of the optimal for large k; relevant for practical NLP scenarios. With distt -> 1, this implies that the room for possible compression improvements narrows.
1.00
0.90
0.05
0.7
0.70
6 Conclusion
In this work, we showed that the tokenization problem is NP-hard and provided a greedy algo- rithm GREEDTOK that practical alternative over incumbents BPE and UNIGRAM, and may even better option for language pre-training. Although recent works [HKM*24 24, GT24] had pushed the limits of context length, plausibly re- ducing the importance of compression, GREED- ToK can still offer a flexible platform to ex- plore new alternate objectives, such as integrat- ing NLP downstream objectives [BD20] and faimess [LBG+24 constraints into its MIP formulation. Finally, recall that the tokenization problem has the confounding property of being neither super- modular nor submodular. Although we show that GREEDTOK achieves an approximation ratio of at least 0.9 1/e) for large k a formal proof is lacking. Nevertheless, this is intriguing theoretical problem. We hope that our formulation of the tokenization problem and the accompanying toolkit will be valuable for future research.
Figure 4: We sampled documents from RefinedWeD corpus a probability of 0.01 across 40 independent runs, then run GREED- Tok. Plotting mean dust shows it trending towards 1, empirically showing GREED is 0.9(1 1/e a/p)-approximmae algorithm.
Computational feasibility. While the theoretical runtime of GREEDTOK for selecting S is O k. Σ wwew [W]), key optimization is to update a token 7's marginal contribution only when it being evaluated for inclusion. Empirically, we observe that this lazy evaluation strategy scales like O[T Σ Eew [W]), making GREEDTOK practical for large-scale NLP workloads. Table I

---

summarizes the time for GREEDTOK to compute S at the largest tested size S max k (see
Section 5.1). In a larger experiment, with W 14.3M and |T] = 251M, GREEDTOK computed S in 34 minutes using 160GB of RAM. This cost can be reduced by reducing the search space, limiting max [W], filtering W, or pruning T by substring length or frequency. To benchmark encoding speed, we tokenize subset of the wiki corpus (70K articles, 97M words) using a vocabulary of |S] 100K (from c1100k_ base in TIKTOKEN [Ope23]). Our current implementation of GREEDTOK achieves 700K-800K words per second per thread, and we expect further optimization is possible. These results demonstrate that GREEDTOR is feasible for integration into modern NLP pipelines.
Future extensions. There are many tokenization techniques that augment an initial token set produced from core tokenization algorithms like BPE and UNIGRAM. Likewise, these methods could also be used to augment the token sets produced from GREEDTOK. For example. BPE-DROPOR introduces stochasticity by randomly dropping merge operations during training, yielding multiple possible segmentations per input. While GreedTTok is deterministic by default, it can be adapted in a similar fashion: at each step, we can randomly skip adding the top token and proceed with updating the graph accordingly. РATПPIЕCE 24], encoding algorithm, can be applied directly to any token set, including the ones generated by GreedTok. PICKY [CAKY24) refines BPE vocabulary by iteratively removing low-utility tokens, using a deletion criterion guided by hyperparameter. For encoding, relies on a naive greedy approach or PATHPIECE. GREED can likewise incorporate such retrospective pruning: after each token addition, evaluate and remove earlier redundant tokens to improve vocabulary efficiency. BOUNDLESSBPE [SRTP25] and SUPERB [LHH+25] are contemporaneous methods that allow token merging across whitespace boundaries by generating longer tokens from an initial BPE token set resulting in larger token sets. GREEDToK tokens could be used an initial set from which these whitespace-spanning merges constructed. VOLT [XZG+21] prunes an initial token set, generated via Unigram or BPE, by seeking to maximize the entropy of subword distributions. Again, GREEDTOK could serve as an upstream tokenizer to generate the initial candidate tokens for VOLT.
[PEV20]
Limitations. The purpose of this work is offer new perspective on tokenization, with empirical experiments to show that this theory is practical. Pretraining language models from scratch is expensive, hence, our comparisons are limited to BPE, since it is widely adopted in current practice, and we fixed our models to have a size of IB parameters. Although we believe that our insights and observed trends should generalize larger models, more empirical confirmation at scale is needed. Our experiments mainly use corpora that contain commonly used languages, and did not conduct evaluations low-resource languages, which is an important area for further exploration.
Acknowledgements
This research/project is supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: AISG3-PAD-2203-008-00
References
[AFT*24] 24] Mehdi Ali, Michael Fromm, Klaudia Thellmann, Richard Rutmann, Max Lübbering, Johannes Leveling, Katrin Klug, Jan Ebert, Niclas Doll, Jasper Schulze Buschhoff, Charvi Jain, Alexander Arno Weber, Lena Jurkschat, Hammam Abdelwahab, Chelsea John, Pedro Ortiz Suarez, Malte Ostendorff, Samuel Weinbach, Rafet Sifa, Stefan Kesselheim, and Nicolas Flores-Herr. Tokenizer choice for Ilm training: Negligible or crucial? arXiv preprint arXiv:2310.08754. 2024.
[ALTU++23] Joshua Ainslie, James Lee-Thorp. Michiel de Jong, Yury Zemlyanskiy, Federico Lebrón, and Sumit Sanghai. Gqa: Training generalized multi-query transformer models from multi-head checkpoints. arXiv preprint arXiv:2305. 13245, 2023.
[Att15] Giusepppe Attardi. Wikiextractor. httpa://github. wtw.ttthh..ooomeeee
wtmm//ttaardd/iiiieerrcccooooo 2015.
[BD20] Kaj Bostrom and Greg Durrett. Byte Pair Encoding is Suboptimal for Language Model Pretraining. Findings of the Association for Computational Linguistics: EMNLP 2020, pages 4617-4624, 2020.
10

---

[BZB+20) Yonatan Bisk, Rowan Zellers, Ronan Le Bras, Jianfeng Gao, and Yejin Choi. Piqa: Reasoning about physical commonsense in natural language. Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020.
[CAKY24] Pavel Chizhov, Catherine Arnett, Elizaveta Korotkova, and Ivan P. Yamshchikov. BPE gets picky: Efficient vocabulary refinement during tokenizer training. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, 2024.
[CCE*18] 18] Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. Think you have solved question answering? try arc, the ai2 reasoning challenge. (8X3:/000000555700 2018.
[CK08] Reuven Cohen and Liran Katzir. The generalized maximum coverage problem. Infor- mation Processing Letters, 108(1):15-22, 2008.
[C] Christopher Clark, Kenton Lee, Ming-We Wei Chang, Tom Kwiatkowski, Michael Collins, and Kristina Toutanova. Boolq: Exploring the surprising difficulty of natural yes/no questions. In NAACL, 2019.
[Com23] Common Crawl. Common crawl- open repository of web crawl data. web document. https:/ https////cmooncaa.lcccm org, 2023.
[3] Caoyun Fan, Jidong Tian, Yitian Li, Wenqing Chen, Hao He, and Yaohui Jin. Chain- Masked Language Models can also Think Step By Step in Natural Language Understanding. In Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 14774-14785, 2023.
of-Thought Tuning:
[Gag94] Philip Gage. A new algorithm for data compression. The Users Journal, 12(2):23-38. 1994.
[Gal19] Matthias Gallé. 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 Natural Language Processing (EMNLP-IJCNLP), 2019.
[GCE+24] Omer Goldman, Avi Caciularu, Matan Eyal, Kris Cao, Idan Szpektor, and Reut Tsarfaty, Unpacking tokenization: Evaluating text compression and its correlation with model performance. arXiv preprint arXiv:2403.06266 2024.
[GT24] Google Gemini Team. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context. arXiv preprint arXiv:2403.0553 000.00530, 2024.
[GTA+24] Leo Gao, Jonathan Tow, Baber Abbasi, Stella Biderman, Sid Black, Anthony DiPofi, Charles Foster, Laurence Golding, Jeffrey Hsu, Alain Le Noac h, Haonan Li. Kyle McDonell, Niklas Muennighoff, Chris Ociepa, Jason Phang, Laria Reynolds, Hailey Schoelkopf, Aviya Skowron, Lintang Sutawika, Eric Tang, Anish Thite, Ben Wang, Kevin Wang, and Andy Zou. The language model evaluation harness, 07 2024.
[HKM+24] Coleman Hooper, Sehoon Kim, Hiva Mohammadzadeh, Michael W. Mahoney, Yakun Sophia Shao, Kurt Keutzer, and Amir Gholami. KVQuant: Towards 10 Million Context Length LLM Inference with KV Cache Quantization. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
[Hoc96] Dorit S. Hochbaum. Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems. In Approximation algorithms for NP-hard problems, pages 94-143. PWS Publishing Co., 1996.
[JBD17] Slava Jankin, Alexander Baturo, and Niheer Dasandi. United Nations General Debate Corpus 1946-2023. /ttps:///oi... orto/.o.rg///// 10/g//...// 7910/DVV/OTJXXY, 2017.
[J3 Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Deven- dra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7B. arXiv preprint arX1v:2310.06825. 2023.
11

---

[JW17] Matt Gardner Johannes Welbl, Nelson F. Liu. Crowdsourcing multiple choice science questions. arXiv: (xXi::7777.0600v/, 2017.
[Krr72] Richard M. Karp. Reducibility among Combinatorial Problems. In Complexity of Computer Computations, pages 85-103. Springer, 1972.
[KHM*23] 23] Jean Kaddour, Joshua Harris, Maximilian Mozes, Herbie Bradley, Roberta Raileanu, and Robert McHardy. Challenges and applications of large language models. arXiv preprint vrXiv:2307.00166 2023.
[Kud18] Taku Kudo. Subword regularization: Improving neural network translation models with multiple subword candidates. Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Longg Papers), pages 66-75, 2018.
[KV24] László Kozma and Johannes Voderholzer. Theoretical Analysis of Byte-Pair Encoding. arXiv preprini arXiv:2411.06671, 2024.
(LBG*24) Tomasz Limisiewicz, Terra Blevins, Hila Gonen, Orevaoghene Ahia, and Luke Zettle- moyer. MYTE: Morphology-Drin Driven Byte Encoding for Better and Fairer Multilingual Language Modeling. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguisties (Volume I: Long Papers), pages 15059-15076, 2024.
[LBM23] Tomasz Limisiewicz, Jiřf Balhar, and David Mareček. Tokenization Impacts Multi- lingual Language Modeling: Assessing Vocabulary Allocation and Overlap Across Languages. In Findings of the Association for Computational Linguistics: ACL, 2023.
[LDM11] Hector J Levesque, Ernest Davis, and Leora Morgenstern. The Winograd schema challenge. In AAAI Spring Symposium: Logical Formalizations of Commonsense Reasoning, volume 46, page 47, 2011.
[LFS+24] Jeffrey Li, Alex Fang, Georgios Smyrnis, Maor Ivgi, Matt Jordan, Samir Yitzhak Gadre, Hritik Bansal, Etash Guha, Sedrick Scott Keh, Kushal Arora, et al. Datacomp-lm: In search of the next generation of training sets for language models. Advances Neural Information Processing Systems, 37:14200-14288 2024.
[LHH+25] Alisa Liu, Jonathan Hayase, Valentin Hofmann, Sewoong Oh, Noah A. Smith, and Yejin Choi. Superbpe: Space travel for language models, 2025.
[IXI++17] Guokun Lai, Qizhe Xie, Hanxiao Liu, Yiming Yang, and Eduard Hovy. RACE: Large- scale ReAding comprehension dataset from examinations. In Proceedings of the 2017 Conference Empirical Methods in Natural Language Processing, 2017.
[MCKS18] Todor Mihaylov, Peter Clark, Tushar Khot, and Ashish Sabharwal. Can suit of armor conduct electricity? new dataset for open book question answering. In EMNLP, 2018
[Mis24] Mayank Mishra. Dolomite Engine: A Hyper-Optimized Library for Pretraining and Finetuning, 2024.
[MXBS16] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv: 1709.0784, 2016.
[NWF78] G. L. Nemhauser, A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions-I. Mathematical Programming, 14(1):265-294, 1978.
[Ope23] OpenAl. tiktoken. httpee//ggthhb..mmmppppaaatttttt 2023.
[PEV20] Ivan Provilkov, Dmitrii Emelianenko, and Elena Voita. BPE-dropout: Simple and effective subword regularization. Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, 2020.
12

---

[PKL*10
Denis Paperno, Germán Kruszewski, Angeliki Lazaridou, Ngoc Quan Pham, Raffaella Bernardi, Sandro Pezzelle, Marco Baroni, Gemma Boleda, and Raquel Fernández. The LAMBADA dataset: Word prediction requiring broad discourse context. In Pro- ceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2016.
[PMB24] Jacob Pfau, William Merrill, and Samuel R. Bowman. Let's think dot by dot: Hid- den computation transformer language models. In First Conference on Language Modeling, 2024.
[33 Guilherme Penedo, Quentin Malartic, Daniel Hesslow, Ruxandra Cojocaru, Alessandro Cappelli, Hamza Alobeidli, Baptiste Pannier, Ebtesam Almazrouei, and Julien Launay. The refinedweb dataset for falcon Ilm: Outperforming curated corpora with web data, and web data only. arXiv preprint urXiv:2306.01 2023.
[4] Artidoro Pagnoni, Ram Pasunuru, Pedro Rodriguez, John Nguyen, Benjamin Muller, Margaret Li, Chunting Zhou, Lili Yu, Jason Weston, Luke Zettlemoyer, et al. Byte La- tent Transformer: Patches Scale Better Than Tokens. arXiv preprint (Xix:2442.00977/ 2024.
[PY88] Christos Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. In Symposium on Theory of Computing (STOC), pages 229-234. Association for Computing Machinery (ACM), 1988.
[RBG11] Melissa Roemmele, Cosmin Adrian Bejan, and Andrew S. Gordon. Choice of plausible alternatives: An evaluation of commonsense causal reasoning. In 2011 AAAI Spring Symposium Series, 2011.
[RSR+20] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with unified text-to-text transformer. J. Mach. Learn. Res., 21(1), 2020.
[SBBC19] Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: An adversarial winograd schema challenge at scale. arXiv preprint arXiv: 1907. 10641, 2019.
[SFWN23] Jimin Sun, Patrick Fernandes, Xinyi Wang, and Graham Neubig. A Multi-dimensional Evaluation of Tokenizer-free Multilingual Pretrained Models. In Findings of the Association for Computational Linguistics: EACL, 2023.
[Sha20] Noam Shazeer. Glu variants improve transformer. arXiv preprint arXiv:2002.05202. 2020.
[SHB16] Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural Machine Translation of Rare Words with Subword Units. In Proceedings of the 54th Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1715-1725, 2016.
[SRTP25] Craig W. Schmidt, Varshini Reddy, Chris Tanner, and Yuval Pinter. Boundless byte pair encoding: Breaking the mre-ookenization barrier. arXiv preprint arXiv:2504.00178, 2025.
[4] Craig W Schmidt, Varshini Reddy, Haoran Zhang, Alec Alameddine, Omri Uzan, Yuval Pinter, and Chris Tanner. Tokenization Is More Than Compression. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, 2024.
[SSM+24] Yikang Shen, Matthew Stallone, Mayank Mishra, Gaoyuan Zhang, Shawn Tan, Aditya Prasad, Adriana Meza Soria, David D Cox, and Rameswar Panda. Power sched- uler: A batch size and token number agnostic learning rate scheduler. arXiv preprint Stiv:2200.113599 2024.
[TGD+24) Yury Tokpanov, Paolo Glorioso, Ayush Dattagupta, Vibhu Jawa, Ryan Wolf, Vikranth Jeyakumar, Arham Mehta, Quentin Anthony, and Beren Millidge. Building Zyda-2, 5 Trillion Token
Dataset, with NVIDIA NeMo Curator, 2024.
13

---

[TLI*23] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Manie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 13971, 2023.
[TTR*22] Yi Tay, Vinh Q. Tran, Sebastian Ruder, Jai Gupta, Hyung Won Chung, Dara Bahri, Zhen Qin, Simon Baumgartner, Cong Yu, and Donald Metzler. Charformer: Fast character transformers via gradient- based subword tokenization. In International Conference on Learning Representations (ICLR), 2022.
[VSP+17] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. arXiv preprint arXiv:1706.037622 2017.
[WBP24] Philip Whittington, Gregor Bachmann, and Tiago Pimentel. Tokenisation is NP- Complete. arXiv preprint arXiv:2412. 2024.
[WS11] David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.
[WWS+22] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. Chain-of- Thhought Prompting Elicits Reason- ing in Large Language Models. In Advances Neural Information Processing Systems (NeurIPS), pages 24824-24837, 2022.
[XZG+21] Jingjing Xu, Hao Zhou, Chun Gan, Zaixiang Zheng, and Lei Li. Vocabulary learning via optimal transport for neural machine translation. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing ( (Volume I: Long Papers), 2021.
[YDY+19) Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Ruslan Salakhutdinov, and Quoe Le. Xlnet: generalized autoregressive pretraining for language understanding. In Proceedings the 33rd International Conference on Neural Information Processing Systems, 2019.
[YSF+23] Lili Yu, Dániel Simig, Colin Flaherty, Armen Aghajanyan, Luke Zettlemoyer, and Mike Lewis. MEGABYTE: modeling million-byte sequences with multiscale transformers. In Advances in Neural Information Processing Systems (NewrIPS), pages 78808-78823, 2023.
[YYZ Shunyu Yao. Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of Thoughts: Deliberate Problem Solving with Large Language Models. In Advances in Neural Information Processing Systems (NeurIPS), pages 11809-1 11822, 2023.
[7HB+19] Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. Hellaswag: Can a machine really finish your sentence? In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, 2019.
ZMG+233 Vilém Zouhar, Clara Isabel Meister, Juan Luis Gastaldi, Li Du, Tim Vieira, Mrinmaya Sachan, and Ryan Cotterell. A Formal Perspective on Byte-Pair Encoding. In Find- ings of the Association for Computational Linguistics: ACI. 2023, pages 598-614. Association for Computational Linguistics, 2023.
14

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Claims matches theoretical and experimental results. When possible, we try to generalize on larger experiments.
Guidelines:
The answer NA means that the abstract and introduction not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions made in the paper and important assumptions and limitations. No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation long as it is clear that these goals not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We note the limitations of our proposed algorithm, mainly worst-case runtime complexity for selecting and per-word tokenization, in Section 4.3. We note the limiations of our experiments in the conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those
discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images taken in low lighting. Or speech-to- to-ttttttttttttttee system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
Justification: The complete proof of tokenization being NP-hard can be found in Section 3, proof of neither submodular nor supermodular is in Appendix A, formulation of mixed-integer program is in Section 4.1 and Appendix B, relation to weighted maximum coverage is in Appendix C.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: We provide the code for our tokenization algorithm GREED ToK and its compression experiments in the supplementary materials. For large language model pre-training experiment, we detail the specifics in Appendix F22 Additional pseudocode information also provided in Appendix G.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility
also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in way (e.g., to registered users), but should he possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code
16

---

Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We had already open-sourced our algorithm GREEDTOK and its compression experiments/data, We made sure that easy to integrate GREEDTOK into existing codebases.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (https: pettps://hips.ccppbllic guides/CodeSubmii cetbbmisssioo wtt.imiiisiioooiiioiooiooii for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips.ao ctt.ccc/ppoo cccpublic/ ppulic/guides. Sraiides/CodeSubiii seniiisssiooooo ieeiinnoliioooo cy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Provided in Section and Appendix F.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance the experiments?
Answer: [No]
Justification: The algorithms are deterministic, hence for the compression experiment, we report multiple results of using different corpora and at different ie hyperparameter. For the pre-training experiment, we train three variants of IB parameter language model up 629B tokens. It is prohibitively expensive to train multiple of the same variants. Nevertheless, due to the large scale of the training, we do not expect out of range results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
17

---

The method for calculating the enror bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors). should be clear whether the error bar the standard deviation or the standard error the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative error rates). If error bars are reported tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [Yes]
Justification: For compression experiments, these details can be found in Section 5.1. For pre- pre-training experiments, these details can be found in Appendix F.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experi- mental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 'tt make into the paper).
Code of ethics
Question:
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neur/::
Answer: [Yes]
Justification: There is violation of the code.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consideration due laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our research is not tied to particular specific applications.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied to particular upplications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release models, providing defenses addition attacks, mecha- nisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recogmize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We properly credit the original owners of assets, licenses and terms of use are respected and mentioned, e.g. in Appendix F.I.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, inverswitccode www/cotoccccooc com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
19

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We release open-source code repository. The link was redacted for anonymity reasons. These documentation can be found in the supplementary materials.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/coodemmodlll as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include full text instructions given to participants and screenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country which research conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage LLMs if it is an important, original, or non- standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration not required.
20

---

Answer: [NA]
Justification: Core method development in this research does not involve LLMs as any important, original, non-standard components. We only pretrain LLMs evaluate the impact of proposed algorithm.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non non-standard components.
Please refer to our LLM policy (https:/ ptttps:/nneurips. cc/Confferences/2222 (LL05 for what should or should not be described.
21

---

A Example illustrating that Problem is neither submodular nor supermodular
In this section, we show that the objective Problem is neither submodular nor supermodular Using 2 to denote the powerset of T, submodular and supermodular set functions are defined as follows:
Definition 2 (Submodular Set Function). A real-valued set function f: + f {C}) - f(A) 2 (AU((C) - f(A) for all A S A S T and C T|A.
R is submodular if
Definition 3 (Supermodular Set Function). A real-valued set function f - R is supermodular f(A U (C)) - f(A) s f(Au (C)) f(A) for all C A T and C E A
In the context of the tokenization problem, the set T represents the candidate set of all possible tokens. Unfortunately for us, Problem 1 is neither submodular supermodular; see Table 5.
Table 5: The above table shows that the objective function of Problem is neither supermodular submodular. Suppose wish to tokenize the word W scaredy with candidate token set = {care, edy, scar, scared, dy} } and singletons {s.c.a.r.e.d.y), and the function f outputs the smallest possible number of final tokens used represent W, i.e. the objective function of Problem 1 on a single word corpus. Observe that S YYS T, Z E Y, Y S T, and Z' E T Y'. In case 1, using X tokenize W results in using 4 tokens (s, care, y) and can check that using X U 2} also results in 4 tokens. On the other hand, using Y results in 4 tokens (s, care, d. y) but using YUŞZ) results in 2 tokens (scar, edy). Therefore, f( (XU(Z)) (X) ((U ((Y) and thus / is not supermodular. On the other hand, in case 2, using Y' and Y' (2) to tokenize W results in 2 tokens (scared, y) while using X {Z'} results in 3 tokens (s, care, dy). Therefore.
f(X { f(X) < f(Y U ((Z))) f(Y') and thus f is not submodular.
Single word corpus W scaredy with COUNT(W)
Case
Case
X
(care)
f(X) f(XU
X (care)
((X)
Y
(care. edy)
f(Y) =4
Y (care. scared)
((Y)) f('' =2
Z
scar
(2Y =2
Z' = dy
((")))))
= f(x U (7)) - -((X) (() f(Y)=
-1 f(X U (77) ((X) ((
B Mixed integer program formulation
In this section, we give full details of our mixed integer program (MIP) formulation and provide examples for better understanding.
To formulate Problem an MIP, our goal choose a subset S T of size |S| < k such that the following objective is maximized, encoding max > Wwww COUNT(W) COVEROW S):
WI-1
max Σ ow
Σ
W mis+1
WEW
with the following binary variables, where Cw COUNT(W):
FT E 10, , for tokens 7
Did we choose token T T, i.e. T S?
m. m1......,
-1 m. E {0, 1), for all words W E W
Are the tth singleton W, and the (i 1)th singleton W covered by the same token?
W.T m122 ....,
W.T. WWI-L, {0, 1}. for all words W w and tokens T T Did token T S cover the ith singleton W; and the (i + 1)th singleton W
22

---

under the following constraints:
Σ JT S k TET
(3)
W.T FT 2 ,1++1
W(+1)
WEW. (L...., [M] 11
(4)
W.T 2 m,,41
WW W.EW,YEET,KE 11
(5)
Σ TeT
m 1++1 S 1
WEW.WEEWWW fL...
1
(6)
W.T W.T
W W.W.WTET.WC (1.........11. [M 2] iW, WH+ W1+2
1,141 14,444
(7)
mx=1, 2,041
W.T
<
W.T
T starts with W.-) VW E W, ET [W 1
TeT
(8)
Ma,41
W.
S - m.
m,
W.T T ends with (We-1,W, AW W. (2,... | -
TET
99)
We remark that the objective Eq. (2) can be re-expressed as max ΣTET Ewew E!W
W.T
cw-m..itt
making Eq. (5) redundant. However, this current formulation is useful for showing how to relax TOK to WMC later.
Now, let us interpret and explain the constraints. Eq. (3) models the constraint that we are choosing subset of size [S] S k. Eq. (4) models the constraint that we can only use T E T cover if is chosen in S. Eq. (5) models the constraint that if a cover happened between two adjacent singletons, then relevant
T must have been chosen in S. However, Eq. (6) models the constraint of only covering two adjacent singletons with single relevant T E S. Eq. (7) models the constraint of covering the entire substring T E or leave uncovered. Eq. (8) and Eq. (9) model the constraints preventing the chosen substring T E T from sharing the cover with another partially overlapping T.
In the following examples, (m.., m 2....... ,. W/ w and (m..7 m22.3 ..... m -w respectively, for any word W W and token T T.
succinctly write mW and W:T in the forms of W.T W.T
W.T
Example 2. Consider the word W ababa and the token T aba has Fy L.e T E SSCC S T. If we only use T to cover singletons in W with left-to-right priority, then the resultant tokenized
form of W is aba_bua. So, m w = (1, 1, O, 0), W.T (1, 1, O, 0), and m W.T" = (0. 0, 0, 0) for all T' E T (T). Observe that the bits in m precisely denote the partitioning positions within W. Furthermore, the constraints Eq. (6) and Eq. (7) ensure that T is the only token that occupies the first two adjacent singletons, while constraints Eq. (8) and Eq. (9) prevent an invalid overlap of T for the last two adjacent singletons. Now, suppose if we also have T" ba with I7 = 1. Using both T and T" to tokenize W results in aba_ ba with m W = 1,, 1), m WT = (1,1,0,0), m W.T" (0, 0,0, 1), and m W.T" = (0, 0, 0) for all T" E TT) (T,
Example 3. Tokenizing the word W abcdef using only tokens S = be and S2 = de yields dd.ff. This corresponds to m (0, 0, 1, 0), and m W,T = (0, 0, 0, 0) for all W abedef using only token Sy bode yields bede_f f, corresponding w (0, 1, 1, 1. 0). m W.S. (0, 1, 1, O), and m W.T (0, 0, 0, 0, 0) for all E T {5²}. Observe that using token Sy alone directly accomplishes what typical bottom-up up pairwise merge sequence from BPE would do: apply S to merge 'b' with 'c', S2 to merge 'd' with 'e', then S3 to merge 'be" with 'de'.
(0. 1, 0, 1, 0), m W.S: (0, 1, 0, 0, 0). m W.S, T S2). Mcanwhile, tokenizing the word
23

---

C Relation to the weighted maximum coverage problem
In this section, we provide details on how our MIP formulation in Section 4.1 naturally relaxes into the well known weighted maximum coverage problem (WMC).
Given of unique elements L [L....., L } and their corresponding weights W {wi...., ) collection of sets U = {U1,... Dju) where U E U S L, and number k. we want to find a subset U' S U such that |U'| Σ & and the total weights of covered elements Eneut Wa is maximized. Formulating WMC as a mixed integer program, we have the objective:
max
weli
(10)
L.EL
with the following variables:
L, E {0, 1]. for all L, E L Did we choose element L; L, i.e. is L; covered?
Mj {0, 13, for all Ui E U
Did we choose set Uy U. is U, E U
under the following constraints:
Σ
k
(11)
UJEU
U
Σ μグ 2
44, E L
(12)
LEEU;
Let interpret and explain the constraints. Eq. (11) limits the number of selected sets S k. Eq. (12) ensures that if an element is covered, at least one of the sets containing the element must be included in U'. To that WMC relaxation of TOK, we first establish a mapping between the variables between TOK and WMC:
m -
decision of covering adjacent singletons - decision of covering element
JT Mi decision of including T' S decision of including U U'
m L E.EU U, adjucent singletons in W and T element membership set
Ewew CW + W/
sum count of W with adjacent singletons - weight of element
Next, comparing the objectives, we can see that Eq. (2) and Eq. (10) have the exact same objective when utilizing the mapping between variables. Finally, we demonstrate a relaxation of Tok's constraints:
Eq. (3) and Eq. (11) equivalent
select at most number of T and U respectively
Combining Eq. (4) and Eq. (5) gives us Eq. (12). W.T
Σter TT 2 Erer m mi++1 m - EL.EV, Hj l
We remove the constraints Eq. (6), Eq. (7), Eq. (8), and Eq. (9).
Notice that for Tok, we disentangle Eq. (4) and Eq. (5) using the specification of m,,+1 to enable Eq. (6), limiting the covering of an element to one selected set.
W.T
24

---

D ToK's relation to UNIGRAM
Let T represent the of all possible subword sequences. The probability of subword sequence
W = (Ti,..., Tas) where 'T formulated as a product of subword probabilities:
P(W) 11
where ΣT p(T) 1. Since word W in corpus can be represented by different possible subword sequences SWW), let W* be the most probable segmentation:
W argmax P(W)
WeS(W)
Since S(Da), segmentation candidates sentence D,. will be individual words w (based on sentencepiece default implementation). Therefore, Unigram seeks to minimize the reduction in likelihood L amongst words in given corpus:
D
L
Σ
log W
WES(D,)
To map C to TOK's objective of min Vw COUNT(W) ppattttio(W)):
max L
Σ Σ
log W
==1
WES(D,)
W
COUNT(W) log W
(group by words)
W
W
Σ
COUNT(W) log W1W p(W))
(choose best subword segmentation)
W
W COUNT(W) (logr(W?)) + + log p W ((w.)))
(notice partition (W) (W'))
Notice that after grouping all similar words together, we get weighted partition (logp(W,) + +...- log p( WW ()). For Tok, it is (1+...5 1) = [W* Maximizing L is equivalent to minimizing negative log probability weighted partitions. Due the presence of log, max L is equivalent to min weighted Tok. We can see that Unigram favors frequently occurring subwords in non-linear fashion. This relation is also noted in [SRZ*24] 24], where their proposed PATHPIECE tokenization algorithm optimizes for TOK from top-down pruning of BPE/UNIGRAM shortlisted candidates.
We present scenario where top-down pruning is sub-optimal for compression. Given W ("random"; "randose", "rosey", "randy"), }. each with a COUNT of I, and T W " "ose"), we wish to select S T, where [S]
tokens.
Table 6 shows the token pruming process of UNIGRAM and Table shows the greedy approach of GREEDTOK. For this scenario, GREEDTOK obtained a better solution with 10 partitions compared to UNIGRAM's 12. This scenario highlights the skew to seleet whole words when approaching tokenization from pruning angle. If such scenarios common, then expect GREEDTOK to obtain a better tokens per word ratio in our experiments (Section 5.1).
25

---

Table Top-down pruning solution for the given example using UNIGRAM, removing tokens that results in the least decrease in L, ÅC, in each iteration. The same results will also be obtained when optimizing for ToK from top-down pruning approach. For iteration denotes the singletons which are omitted. Final S ("random", "randose").
w
log W
T
COUNT
p(T)
Removing results in segments
AC
random
-1.505
random
0.0312
random
random* p("rand") """"""""p""""" p((""") p("m")
-2.056
randose
-1.505
randose
0,0312
randose
randose = p( p("rand") -pl" pl"ose")
-0.727
Iteration
rosey -1.505
rosey
0.0312
rosey
randy "("t''''''s""""" p("oss") -pyy')
-1.806
randy -1.505
randy
0,0312
randy
rosye* p("rand") p('y")
-0.727
rand
0.0937
rand
None
0,0625
None
Decision after iteration remove "rand" and "ose". iteration:
Iteration 2
random -1,431
random
0.0370
random
random* boEw- p(6)
-4.646
randose
-1,431
randose
0,0370
randose
random* -BEW p(b)
-5.475
rosey -1,431
rosey
0,0370
rosey randy
rosey* dew- p(b)
-3.743
randy -1.431
randy
0.0370
randy* -se p(b)
-3.391
Decision after iteration 2: remove "rosey" and "randy". Total partitions ++
Table 7: GREEDTOK's solution for the given example, selecting tokens that results in the highest objective gain in each iteration. Final S {"rand"" "rosey") or {"rand", "ose").
Iteration
Iteration 2
W
T
obj. gain
T
obj. gain
random
random
5
random
2
randose
randose
6
randose
3
randy
rosey
4
rosey
4
rosey
randy
4
randy
1
ose
4
ose 9
4
rand
Decision
pick "rand"
pick "rosey" or "ose"
if pick "rosey": Total partitions 3 1
if pick "ose": Total partitions = =3+2+3+ 10
E Analyzing GREEDTOK's Characteristics
from our experiments (Section 5), along three dimensions: 1) proportion of common tokens in a pairwise comparison, 2) proportion of whole words and UNIGRAM's objective (Appendix D).
After obtaining the token sets of CREEDTOO/BPPEUUNII
UN corpus
arXiv corpus
PubMed corpus
wiki corpus
1.0
1.0
2.0
1.0
Num. common tokeens
0.8
0.6
X
0.6
X
0.6
X
0.6
Unigram GreedTok
0.2
0.2
0.2
0.2
Unigram 0 BPE
BPE GreedTok
3000
5000
1000
4000 6000 10000
4000 6000 8000 10000
Figure 5: Plots showing the ratio of common tokens between token sets from GREED- Tox/BPE/UNIGRAM. From the plots, we observe that while GREEDTOK and BPE are most alike, GREEDTOK shares more similarties to UNIGRAM, compared to BPE.
Common tokens. To probe GREEDTOK's token set, we analyze the common tokens from pairwise comparison of the tokenization methods investigated. From Fig, observe that BPE 0 GREED-
26

---

ToK share a large proportion of common tokens. The remaining difference can be observed in the greater proportion of UNIGRAM n GREEDTOK compared to UNIGRAM N BPE. The consistent results across the four corpora, and at different [S] k, implies that GREEDTOK contains the characteristics of BPE due to the high proportionality of common tokens. However, we require further investigation into whether GREEDTOR contains UNIGRAM's characteristics.
UN corpus
arXiv corpus
PubMed corpus
wiki corpus
0.55
0.35
0.55
0.55
GreedTok
Patio of wikk words in token
0.50
0.50
0.50
0.50
0.45
0.45
0.45
Unigram
0.40
0.40
0.35
0.35
X
X
0.30
0.30
0.25
0.25
1000
2000 3000
4000
5000
1000
2000
3000 400n 5000
2000 4300 6ooD 8000 1800n
2000 4000 6000 8000 10000
Figure 6: Plots showing the ratio of wiki words found in the token sets from GREED- TOK/BPE/UNIGRAN with different [S] = k. We select the top 40K frequently occuring words excluding stop words to approximate frequent word list. From the plots. UNIGRAM has the largest ratio of wiki words, followed by GREEDTOK and then BPE.
Whole words. As hypothesized in Appendix D, there are scenarios that will lead UNIGRAM to select whole words, skipping the intermediate tokens that BPE may require. To further investigate, we approximate 40,0000 common word list using the most frequent words appearing in wiki, and then use to compare the token sets obtained. From Fig. 6, across the four corpora and at different SS| = k, we observe that UNIGRAM has the highest proportion whole words, then followed by GREEDTOK and BPE respectively. With GREED TOK selecting more whole words, compared to BPE, suggests that GREED'TK may also exhibit the behaviour favored by UNIGRAM.
Table 8: In this table, we report L obtained by GRREDDOOK/BPE/UNCCRR under various |S] k settings. We observe that GREEDTOK, compared to BPE, achieving a closer L to UNIGRAM.
h
1000
2000
3000
4000
5000
2000
4000
6000
8000
10000
GREEDTOR (GT)
4,15HUX
-3855188
-3,69E08
-3,00138
-3.53HU8
-5.03E10
4.71K10
-4.66E10
4,47100
-441F10
BPF C
B
-4,77H08
40110
-38300
-3.71918
-3.63HUX
Tabbeed
-5.1910
43E30
-466E10
4.56E10
-4,49110
GT's Improvement (5))
5.08%
4.00%
3.48%
3.06%
2.71%
3.19%
2.61%
2.26%
2.01%
1.68%
UNIGRAM C
3.90E08
-3. -3600DS
-3,17008
-3,38008
-3.33E08
-187710
- 4.56E10
-1.13E10
-135E10
-4,31810
GT's Emprovement (8)
-6.29%
-6.77%
-6.54%
6.39%
-6.09%
-3.30%
-3.15%
-2.81%
-2.88%
-2.46%
GREEDTOK
-4,19509
-4.13809
-3,96009
-3,78009
-3,76110
-3.55E10
-3,ME10
-3,37E10
-3.32610
C.
-3.37810
GT's Improvement (9)
5.37%
4.91%
3.99%
3.37%
2.94%
2.34%
2.03%
1.84%
1.56%
1.41%
UNIGRAM C
-4,32509
-3.97809
-3,82009
-3. 3.74409
-3.68E09
-3.1EE0
-3.42600
-3.32E10
-3.26610
-3.22610
GT's Improvement (R)
-3.99%
-4.09%
-3.51%
-3.00%%
-2.59%
-4.13%
-3.70%
-3.57%
-3.35%
-3.12%
Unigram's 's objective. Finally, another way that we can investigate the closeness of UNIGRAM and GREEDTOK, is to examine the of their token sets. From Table 8, we observe that GREEDTOK's L is much closer to UNIGRAM'S L. relative to BPE's.
Conclusion of token set investigation. From the three analyses, there are two key findings. First, GREEDTOK's 's compression ability can be explained by selecting a large proportion of tokens that BPE selects, and further improving it by selecting what BPE could not select, i.e. some tokens selected by UNIGRAM. Second, there are indicators that GREEDTOK may display UNIGRAM'S pre-training quality. This is observed from GREEDTOK having a higher proportion of common tokens and closer L to UNIGRAV AM relative BPE. We investigate and confirm this in Section 5.2, where we conduct language pre- mre-trainin on similar models trained on BPE versus GREED TOK tokens.
27

---

F Additional Information
F1 Additional Corpora Information
In this subsection, we describe the corpora used in our compression experiments and detail any preprocessing steps.
United Nations General Debate Corpus (UN). UN [JBD17] a collection of statements made by various member states during the General Debate key geopolitical issues from 1946 to 2022. This corpus has a Creative Commons (CC) 0: Public Domain License.
arxiv. This corpus' is collection of abstracts of scientific publications and preprints from the popular e-Print archive. This corpus has CCO: Public Domain License.
Wikipedia-English (wiki). An extensive collection of English articles on a wide range of things, concepts, and people. We extract [Att15] the text from the database dump. 6 We also conduct performance ablation with articles containing Chinese, Japanese and Korean (CJK) languages. The texts belonging to these articles are under CC BY-SA 4.0 and GNU Free Documentation Licenses.
PubMed Central Open Access (PubMed). Similar to arxiv, PubMed is a repository of publica- tions and preprints, mainly related health, medicine, biotechnology. and pharmaceuticals. We select the Non-Commercial Use Only subset grouped by: CC BY-NC, CC BY-NC-SA, and CC BY-NC-ND licenses. We preprocessed the text minimally, removing citations and headers.
Rebi This corpus [PMH 23] is a filtered set CommonCrawl [Com23] with stringent filtering and extensive deduplication. It was used pretrain language models with 1B and 7B parameters. The corpus has ODC-By 1.0 license.
DCLM full-dedup. This corpus is built from DCLM 24] using deduplication process that was used to build Zyda-2 [TGD* 24]. This corpus licensed under CC-by-4.
IGG.+
F.2 Model Pre-training Information
Our pre-training corpus is DCLM full-deduped dataset. For model training,
the Dolomite
Engine [Mis24]. Our model architecture is a 40-layer Transformer [VSP* 17]. with embedding size 1536, MLP using SwiGLU activation [Sha20] with intermediate size of 4096, and GQA [ALTdJ+23 layers with 12 query heads and 4 pairs of KV-hedss We used a fixed context length of 4096 tokens and batch size of 2 4M tokens. We train GREEDTOK and BPE tokenizers on approximately 20% of the dataset, randomly selected. For BPE, we use the popular implementation from Huggingface's tokenizer API. $ During training, we follow the same learning rate schedule [SSM+24], training on the dataset in two phases: the Power Scheduler [SSM* 24] in phase and learning rate with exponential decay phase 2. However, our phases and use a similar data mixture, sampling the first 500M documents for phase 1, and the next 100M documents for phase 2, which always use 20% of the training iterations of phase We run our experiments using NVIDIA H100 80GB HBM3 cluster, with 96 logical CPU count, training at a rate of 4400 tokens/day.
Evaluating GTET is analogous setting where model training compute-constrained, and users can use more text data for training. Conversely, evaluating GTEP is analogous to a setting where model training is data-constrained, and
have limited amount of text for training. In the BPEM and GTET settings, we train the model for 125,000 and 25,000 iterations in phases I and respectively. For GTEP, we take the model checkpoint GTET the 100,000th training iteration step, followed by an additional 20,000 training iterations in phase 2.
AAaillable at: ottpaaaaa../tpp/p/p//./.aaaaaaoa org/
Available at: https://dumps http//duupsiiiikiiiiieeee wwkimedia.
7 Availlabl at: attps://pmc.nett ncbi nlm. nih. www.../g.o/oooeeppptttlteetet
Availlble at: https://githuu: www.tttu...mmmuuggggggeee http:///w///ggggggg///////ooeee.
28

---

F.3 Additional Benchmark Information
We use the default settings of Language Model Evaluation Harness [GTA*24] for our bench- mark evaluations.
ARC-Easy (ARC-e). A subset of easy questions from the Abstraction and Reasoning Corpus (ARC) dataset [CCE+18] 18] contains 2,376 grade school level multiple-choiee questions that answered correctly with retrieval-based algorithm and word co-occurrence algorithm. Each question has 4 answer options.
ARC-Ch CRC-Challenge (ARC-e). Another subset of questions from the ARC dataset, the test set comprises 1,172 grade school level multiple-choice questions that were incorrectly answered with retrieval- algorithm and word co-occurrence algorithm. Similar to the easy subset, each question has 4 answer options.
HellaSwag. This challenge set [ZHB*19] 19] evaluates sentence completion in a multiple-choice setting. Given 4 possible answers, the correct answer completes the given sentence best. The test set contains 10,003 question sets.
OpenBook QA (OBQA). This dataset [MCKS18] contains multiple-choice questions that require additional reasoning and knowledge in addition the information included in the question and its answer choices. We use the main set containing 500 test question sets.
Physical Interaction: Question Answering (PIQA). This dataset [BZB+2] contains binary-
choice physical commonsense questions. Additional knowledge of how physical materials interact required to successfully answer the questions. We use the validation set of 2,000 question sets.
SciQ. This dataset [JW17] contains multiple-choice science questions that were crowdscourced. Each question has answer choices. use its test subset of 1000 question sets.
BoolQ. This dataset [CLC+19) contains yes/no questions. Each question is accompanied by corresponding text passage. We use the validation set of 3,270 triplets of question, passage, and answer.
Choice of Plausible Alternatives (COPA). This dataset [RBGII] seeks to evaluate commonsense reasoning, where given a premise and two plausible causes or effects, the correct is the option that is more plausible than the other. We use the validation set of 500 question sets.
LAMBADA. This dataset [6KL+16], abbreviated from LAnguage Modeling Broadened to
Account for Discourse Aspects, contains text passages with the given task of predicting the last word of the target sentence. The task was crafted in manner that the target word cannot be predicted by the target sentence, requiring information from other parts of the given text passage. use its test set containing 5,153 text passages.
ReAding Comprehension dataset from Examinations (RACE). This dataset [LXL* 17] contains text passages with an associated multiple-choice question with four possible answer options. The questions collected from English examinations in China. We use the high school level test set containing 3,498 passage- sussage-ueesion sets.
This dataset [SBBC19] follows the Winograd schema [LDMI1], where the task is fill-n-a-blank for given sentence and two options, with additional commonsense reasoning required. We use its test set containing 1,767 questions.
Winogrande.
Wikitext bits/byte. We evaluate the bits/byte metric using Wikitex12 [MXBS16]. A lower value for this metrie implies that less information (bits) is required to make a correct next-token (byte) prediction.
29

---

G Additional Pseudocode
Previously, in our MIP (Section 4.1), 1-based indexing system was used. However, for implementa- tion convenience, we O-based indexing system for our pseudocodes instead. Given an ordered sequence S, such as array A, string W, and selected tokens S, we use S; to specify an element in the 7th index of S. However, for sequences, we use S.,j specify the elements from the 1th index up to, but excluding, the jth of S. For example, when S happy, we have S and S1.3 ap.
G.1 Computing S from T
Given the COUNT function, corpus W, candidate tokens T, and an integer k, Algorithm 1 finds set of tokens S that maximizes the objective function with the help of subroutines Algorithm 2 and Algorithm The algorithm Algorithm defines a couple of dictionaries M, P, R. and to track the problem state, then greedily picks the next best scoring token to cover words:
1. M maps each word W to its state of cover, similar to the definition in Section 4.1
2. maps each token the set of its occurrences in the given word W, for all W W, (n,,
i) pair, where i is the position index of the start of the token occurrence
R. stores the net objective gain of each T, which we use greedily select the next best token in Line 8
4. I maps each token T to index, which Line 18
update the state of cover for all W W
Algorithm 1 GREEDTOK: Computing S
Require: COUNT function, corpus words W where [W| > for all W W, candidate tokens T,
integer
I: Initialize dictionary M: W + N+ with
State of the algorithm
M(W) (m
m W
2,1-1-1 = (0....,0) 0) -00 for all W e W
2: Initialize dictionary P T + (W x NY* with P(T) {(W,)) W N W TI = 7 for
all T'
Positioning information of tokens in words N with R(T) for all T E Token scores given current
Initialize dictionary state
4: Initialize dictionary I - N where I(T) = for T
Token indices in
5: Initialize S as an empty sequence
6: Compute scores RT)) for each 7 E T using SCORE on current state M
>
Algorithm
7: Initialize as a priority queue of R
8: Pop next best token T = argmaXrer from Q and add to back of S > Skip checking first token
9: while IS| < & do
10:
Pop next best token candidate f = argmaxyer from Q
11: if new score R((7) * R(f) then
> Algorithm
12:
R(f)= +- R(+) Push 4, R(f) back into Q
13:
14:
else
15:
Append & to the back of S and then update I(f) for (W, P(r) do CANCOvER (M, T. W, then Update each entry of M(W)as+HH-1 25417/11 I(r)
16:
17:
Update states of M(7)
end if 19: end for
21: end if
22:
end while
23: return
30

---

Algorithm 2 CANCOVER: Check if W 1,1+/11-1 is coverable by T in current state M
Require: Current state M, token T, word W, position index
1: return (i = 0 or (( = 0) and (i + [7] = [W] or M(W)(+ITI-1 = 0)
Algorithm 3 SCORE: Calculate total number of possible covers
Require: Token T, token positions P(T), current state M, COUNT function
1: Make a copy M' of the state M
b The original state remains unchanged
2: Initialize token score
3: for (W, i) E P(T) do
4: if CANCOVER (M', T. W, then
5: Add COUNT(W) KÍ E fi,...,, + [T} M(W), = =0 to
> Only add score for
non-zero entries
6: Update each entry of M' M'() (W)WW, )1+ to
> Mark to avoid double counting; see
Example 5
7: end if
8:
end for
9: return
The subroutine Algorithm 2 encapsulates a check of the validity of using given token T to cover W at position i, primarily by observing the non-start/end endpoint positions i and + [T] were previously covered by some other token previously; if such token is present, then T cannot cover W at position i. Meanwhile, the subroutine Algorithm 3 calculates the score contribution by token T, given the current state M, while accounting for previous covers applied from chosen tokens in S.
Example 4 (Valid coverings and two sample traces). Consider the example where T (T
pa, To = ya, T3 = ap} and W = (Wi = papaya, W2 impact). Then, we have P(T.) = {(W,, (W,, 2), (W2, 2)}. indicating that the token T' appears Wi at positions 0 and 2, and in W2 at position 2. Using SCORE (Algorithm 3) to update R would yield R(pa) = 3, R(ya) = 1, and R(ap) 1, so the greedy step Line 8 of Algorithm would first select token Ti be included into S. Initially, we have M(W, papaya) = (0, O, 0, 0, 0). After selecting T₁ into S, we have M(W1) (1, 0, 1, 0, 0). Recalculating the scores using SCORE on the updated state M would yield R(pa) = 0, R(ya) = 1. and (ap)) = O, so the token T22 would be selected next. After selecting T2 into S, we have M(W)) = (1,0, 0, 2) because [ = pa)
and I(T;- ya) 2. One can see that the zero and non-zero locations in M indicate partition and coverage respectively. Now, ignoring the scoring function, let us instead suppose that we selected T3- = ap. Ti = pa, and finally T2 = ya. When we first selected T3- ap, the state of W = papaya will become (WF; = (0, 1, 0, 0) with I(T3- = ap) = 1. Next, consider the token Ti = pa that appears at positions and 2 of the word WT At position O, we see that M(W1) 11=
1 j 0. Meanwhile, at position 2, we = 1 # O. Since there is at least one non-start/end endpoint positions already
have M(W1); covered by token, we cannot further use Ti in Wi. Finally, let us consider using token T2 = ya, which appears at position 4 of W1. We see that >> 0, M(W1)
O. and i + [Tal < [Wi.. we can cover Wi with T2 at position 4, resulting in M ((;) ) = (0. 1, 0, 0, 2) with I(ya) = 2. Note that we do not need to check M(W
because + [Tg] < [W
Example 5 (State copying and overcounting). Here, explain why we require copy of the state in Algorithm 3 to avoid the overcounting of overlapping repeating substrings. Consider the example of Ti aya, W, = ayaya, and COUNT(W,) 1, where P(Ti) = {(W,, 0), (W1,2) and (0, 0, 0, initially. In this case, we see that Ti would obtain a score of either by covering W, at position 0 (i.e. ayaya) or position (i.e. ayaya), but not both positions simultancously (i.c. ayaya). To see how Algorithm 3 ensures this, let us suppose we considered
M(W1) = M')
(W.00) then (W1, 2) in the for loop iteration. As the endpoints of (W1, 0) are coverable, we update (W;) to 11, 0, 0). Note that M(W;) still remains unchanged as we have yet to confirm that T; is the next best token r. With the updated state M', we see that the next pair (W1.2) 2) P(T;) an invalid cover since ( = 1 + O, which prevents an overcounting. We remark that the choice of updating entries to 1 is arbitrary (i.e. any non-zero value will work) and that one can actually avoid explicitly making a copy of the state in implementation by performing checks in an appropriate manner.
31

---

Runtime complexity for computing S. Each call to CANCOVER (Algorithm 2) runs in ((1) time. Fix an arbitrary iteration of the while loop Algorithm 1. Each call to ScORE (Algorithm 3) with token 7' runs in O Wew [W]) time because it iterates through each position in P(T) once and considers if I' is a valid cover for that position. While we update M(W during the iteration, due CANCOVER (Algorithm 2), each index is updated at most once to non-zero value, i.e. Example 5, resulting in at most wWEwew [W]) total number of updates. Therefore, applied across all tokens T E T, k number of times, Algorithm takes O(TT) k Ewew [W]) time to compute S. Empirically, we observe that our lazy strategy scales like (([T) Lwew [W]). Scores can be greedily updated in small batches of next-best candidate tokens (Line 11 in Algorithm 1 is equivalent to batch size 1), which typically suffices to identify the next-best token to add; we do not need to perform ( score updates at every iteration. As result, the cumulative cost over iterations likely remains much smaller than the naive bound, Eie( [1.] #updates, E O([T).
Additional implementation remarks. In practice, it is possible to adopt alternative data represen- tations. For example, instead of a dictionary, one could represent M as a single contiguous array and define a given word W as a position in the array. One could also use a representation of length [W] for each word instead of the ([W) - 1)-sized representation discussed in Line I and Section 4.1. For example, covering the word W papaya by token Ti pa could be represented by 1,, 1, 1, 0) instead of (1, O, O, 0). However, in the (1, 1, 1, 1, 0, 0) representation, it is impossible to discern partition and one has to keep track of additional information regarding duplicates of tokens within the same word. Furthermore, one can avoid redundant calculations of P by tracking and only recalculating the affected T' in words covered by the current T.
G.2 Tokenizing a text W using S
In Algorithm 4, we describe how to encode given text W into its token representation using the token set S from Algorithm 1. First, in Line 1, we initialize a dictionary to map our tokens in S according to their order of inclusion sequence. Next, in Line 2, we find all possible token covers of W using tokens in S and sort them in Line 3 according to their priority and a left-to-right ordering in W. Using M to denote which token covers which position index of W, we iterate through (T, i) in the sorted P and update M whenever the token 7' can cover W at position given earlier decisions. Note that this may mean that a later token of longer length may overwrite the covering decision of an earlier shorter token; see Example 6. Finally, using M, we return the O-delineated token representation; see Example
S, and then place singleton tokens B at the back of the
Tokenizing given text W using S Require: Text W, singleton tokens B, chosen token sequence S I: Initialize dictionary I S BUB- + N with
Algorithm 4 GREEDTOK:
i
if is 8th chosen token in S
I(T)= = IS|] +i T is 8th token in B
> Fix an arbitrary ordering to singleton tokens 2: Initialize potential cover positions P ((T, T E S. -+
3: Sort P based on I(T'), then position i, with lower values having greater priority
4: Initialize state M {mo,...... m w - } 0|W1-1
5: for (T, E P in descending sorted order of Line 3 do
6: if CANCOVER M,, W, then
7:
Update each entry of M, to I(T')
8: end if
9: end for
10: return W delineated at positions of 0
> See Example 7
Example 6 (Overriding earlier shorter tokens). Consider the encoding of W1 = abedefg with s= (S = ab, S2 = cd, S3 = ef, S4 = abc, S₁ abed, Sa = efg, Sy = abedefg). In the first three iterations, we use SI, S2, and S3 to cover W, resulting in M = (1, 2, 0, 3, 0). Then, we see that Sa does not have any valid covers and so M remains unchanged. In the fifth and sixth iterations, notice that S S2 Ss and S3 C Sg. resulting in S₁ and Sg being valid covers and M being updated
32

---

to (5, 5, 5, 0, 6, 6). Finally, since S5. Sa C S7 and S7 is a valid cover with respect to the current
state. M becomes (7, 7, 7. 7. 7). Now, consider another scenario of encoding W2 abed using S = (Sa ab, Sg = abc, S10 abed), where Sg C S9 C S10- Covering W2 using Sş results in M = (1, 0, 0). Then, using Sg results in M = 22. 0). Finally, using S10 results in M = (3, 3, 3). In both examples, we see that covers are only overridden by proper supersets that appear later in the ordering of S, where the largest valid cover in S for is size [W Furthermore, recall that the token covers of any valid covering do not overlap so they jointly take up at most [W] positions in total. As such, we see that each position M. M is updated at most [W| times and thus, across all [W] positions, Algorithm 3 updates values in M maximum of O([W??) times.
Example 7 (Encoding the tokenized output). If W = abedef, S = {Si = bed, S2 = eft and M = (0, 1, 1, O, 2), then W's final tokenized output will be (a, bed, ef). to integers with respect to token indexing, simply apply to each token to get (I(a), [(bed), I(ef)).
wishes to convert the tokens
Runtime complexity for tokenizing W using Each call to CANCOVER (Algorithm 2) runs ((1) time. There are at most ( E O((W1²) substrings of W and so Line runs in O (*W time, [P| E O([W(3 and sorting P takes O[W12 lo'((W time. Since each index can only be overwritten when longer token covers it, in Line 7, we see that each position in M is only updated
at most | times, and therefore a maximum of |W|2 for all positions in Pl number of iterations;
Example 6. Thus, the entire for loop takes O [| + [W]3) C ?( time iterate through P and to update all O([WI) positions in M.
Additional implementation remarks. In practice, we limit the subsequence search the maximum token length = maxres [7], with early stopping. To reduce W even further, we have to go beyond regex and identify smaller local sections within W so that sections. This is possible as S inadvertently learns the regex pattern and more during its construction. This implies that we can also further infer natural separations within W where T overlaps with another.
independently tokenize these
33


Reviews:
[{"review_id": "zbDaEPwLBi", "reviewer": "Reviewer_9YQ1", "summary": "The authors introduce GreedTok, a polynomial-time greedy tokenization algorithm which draws on theory from the weighted maximum coverage problem. They show GreedTok outperforms byte pair encoding on compression while more closely resembling Unigram-like tokens, and run pretraining experiments that show models using GreedTok outperforms BPE accuracy when configured to use the same number of tokens as BPE.", "questions": "- There is some discussion of GreedTok having a more closely aligned tokenization to Unigram. Unigram is left out of the Table 4 evaluation on accuracy across popular benchmarks, presumably for computational reasons. However, it would be interesting to see how Unigram compares, even if on a smaller scale, to both BPE and GreedTok. This may further validate your hypothesis that performance gains are because GreedTok “may inherit some of UNIGRAM’s favorable token characteristics”\n- Any evidence of how this tokenization would do in terms of robustness to adversarial attacks? BPE is a strong defense against text perturbation attacks which attempt to produce out-of-vocabulary tokens. Presumably GreedTok achieves this as well due to its high compression rate, but it is never discussed explicitly.", "limitations": "- Limited to 1B parameter models, though due to computational costs this is reasonable\n- No exploration of low-resource languages", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- Clear writing and well structured paper\n- Experimental results comparing performance when using GreedTok vs BPE are compelling and interesting\n- The method is practically viable for full-scale modern NLP workloads\n- Appendix contains many important details for replicability as well as further interesting findings and analysis\n\nWeaknesses\n- While I am not an expert in theory and algorithms, the theoretical contribution appears sound to me and is backed up by empirical experiments\n- The algorithm is more computationally complex than BPE, although this is not too bad given it amounts to a one-time cost upfront that does not affect future model training runs", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our work and for the thoughtful and constructive feedback. We address your questions and comments below.\n\n### On the absence of Unigram in Table 4\n\nWe appreciate your interest in seeing Unigram included in our evaluation. There were several reasons why we ultimately chose not to include it in Table 4.\n\nAs noted in prior work [1, 2], HuggingFace's (HF) implementation of Unigram has some known limitations. For example, it deviates from the original SentencePiece implementation and exhibits certain biases (see footnote 17 in [1]). More critically, the HF Unigram tokenizer lacks support for byte-level fallback, resulting in rare or unknown inputs being mapped to `<unk>` tokens, rather than a more robust byte-level representation. This makes a fair comparison with BPE difficult, as BPE does offer byte-level fallback. We attempted to simulate byte-level fallback in HF Unigram by appending ASCII-escaped byte tokens to the vocabulary. However, this resulted in many tokens being encoded as escaped Unicode strings (e.g., `\\\\x...`), which degraded performance.\n\nAs for the original SentencePiece Unigram implementation, we encountered further difficulties. Training it on the full 20\\% DCLM corpus used for our tokenizer training exceeded our available memory capacity. Reducing the training data to fit memory constraints would have significantly weakened compression quality, further limiting the validity of the comparisons. Additionally, SentencePiece Unigram does not allow for precise control over vocabulary size as it tends to add extra characters as tokens after training. This resulted in differing token counts and thus models with different parameter sizes.\n\nGiven these challenges and our finite compute resources, we chose to focus on the BPE versus GreedTok comparison, which allows for cleaner and more reproducible evaluation. Moreover, BPE remains the most widely adopted method in current practice, making the comparison more directly relevant. That said, we agree that a comparison with Unigram would be interesting. If you are aware of better-supported or alternative implementations of Unigram with byte-level fallback, we would be very interested in exploring them. Thank you again for this suggestion.\n\n### Robustness to adversarial attack\n\nFrom our understanding, adversarial attacks in the context of tokenization often rely on producing non-canonical token sequences that attempt to evade alignment or safety filters.\nThus, the effectiveness of such attacks, and the robustness of a model against them, ultimately depend not just on the tokenizer but also on how the downstream model processes the resulting tokens. We believe that GreedTok confers similar robustness properties as BPE as long we consider the same adversarial setup, and adversarial robustness is an interesting angle to explore in future work.\n\n### Limitations\n\nWe appreciate your observations and agree with both points.\n\nWhile our experiments were limited to 1B-parameter models due to resource constraints, we believe the insights and trends observed should generalize to larger models, though we acknowledge that empirical confirmation at scale is needed. We will clarify this point in the revised paper.\n\nRegarding low-resource languages, we recognize this as an important area for further exploration. As we are not experts in low-resource languages, we refrained from making claims about generalization to other linguistic settings. We will explicitly acknowledge this limitation and note it as a valuable direction for future work, ideally in collaboration with domain experts in multilingual and low-resource NLP.\n\n### References\n\n[1] Craig W Schmidt, Varshini Reddy, Haoran Zhang, Alec Alameddine, Omri Uzan, Yuval Pinter, and Chris Tanner. Tokenization Is More Than Compression. ACL, 2024.\n\n[2] 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. Tokenizer Choice For LLM Training: Negligible or Crucial?. NAACL, 2024."}, {"review_id": "2vaHNSnebz", "reviewer": "Reviewer_58Hv", "summary": "The paper introduces a new optimization-based formulation for the tokenization problem in NLP, generalizing beyond the standard merge-based algorithms like Byte-Pair Encoding (BPE). The authors formulate tokenization in a more general form as a partition cover optimization problem and argue that optimal tokenization is NP-hard providing a clearer intuituve arguments. Then they propose GREEDTOK, a polynomial-time greedy algorithm for token selection, and empirically show it outperforms BPE and Unigram in terms of compression on real-world corpora.\n\nThe authors also try to demonstrate practical downstream impact but that part of the paper is less convincing to me. Based on the reported experiments, GREEDTOK achieves better compression and equal or improved language modeling performance on several benchmarks.", "questions": "Could you provide some futher analysis of token quality?\n\nCould you elaborate on why you only compare the proposed method with two relatively old ones (the inefficiencies and flaws of BPE and Unigram are well documented in the literature, after all)?", "limitations": "I generally like the paper, but I am very concered about statistical significance of the proposed results (especially for downstream tasks). I think that authors could have addressed the limitation quality themselves in a more comprehensive manner.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper has several good aspectes that clearly speak in its favour:\n\n1. The partition cover formulation is an interesting conceptual advance\n\n2 I found the NP-hardness discussion vetu elegant. The connection to weighted maximum coverage is both theoretically and practically valuable.\n\n3 The proposed GREEDTOK consistently achieves better compression than BPE and Unigram\n\n4 The paper provides detailed pseudocode, experimental protocols, and ablation studies, facilitating reproducibility.\n\nSince tokenization is a foundational problem for large language models improvements here have broad implications for efficiency and model capability.\n\nThere are also some of the issues I have with the presented paper.\n\nFirst and formost, error bars or statistical significance are not provided for downstream tasks, though this is understandable given the resource requirements, in my opinion it significantly undermines the practical importance of the proposed algorithm. This is further enhanced due to the absence of some comparison with various optimised versions of BPE, such as BPE-dropout (https://aclanthology.org/2020.acl-main.170/), PickyBPE (https://aclanthology.org/2024.emnlp-main.925/) or Boundless BPE (https://arxiv.org/abs/2504.00178). On top of that, while compression is shown to improve, the analysis of token quality (e.g., semantic coherence, impact on multilingual or morphologically rich languages) is less extensive than some recent studies.", "was_revised": true, "final_justification": "After reading authors' response I have decided to update my final evaluation to 5.", "rebuttal": "Thank you for taking the time to review our work and for the thoughtful and constructive feedback. We address your questions and comments below.\n\n### Error bars and statistical significance\n\nWe agree that reporting error bars or significance testing would further strengthen our results. However, as noted in prior works [1, 2], it is common practice in large-scale language modeling to train only one model per tokenizer variant due to the high computational cost. In our case, we followed a similar approach: rather than training many smaller models for variance estimates, we chose to allocate our compute budget to training a single strong model for each tokenizer using established best practices for BPE-based models [3], each on 500–600 billion tokens. We acknowledge this as a limitation of our study and will make this more explicit in the revised paper.\n\n### Comparison with other variants of BPE\n\nThank you for pointing out recent advances in BPE tokenization, such as [4,5,6]. We agree that these are important and relevant works and appreciate the opportunity to clarify their relationship to our method. \n\nBPE-Dropout [4] introduces stochasticity by randomly dropping merge operations during training, yielding multiple possible segmentations per input. While GreedTok is deterministic by default, it can be adapted in a similar fashion: at each step, we can randomly skip adding the top token and proceed with updating the graph accordingly.\n\nPickyBPE [5] refines the BPE vocabulary by iteratively removing low-utility tokens, using a deletion criterion guided by a hyperparameter. Encoding then proceeds using greedy decoding or PathPiece [1]. GreedTok can likewise incorporate such retrospective pruning: after each token addition, evaluate and remove earlier redundant tokens to improve vocabulary efficiency.\n\nBoundless BPE [6] allows token merging across whitespace boundaries by generating super tokens after an initial round of BPE training. While this results in larger token sets, this idea is complementary to GreedTok. In fact, GreedTok tokens could be used as an initial set from which whitespace-spanning merges are constructed. We consider this direction interesting and note that Boundless BPE appeared on arXiv in March 2025, contemporaneous with our own submission.\n\nOverall, we see GreedTok as a flexible base algorithm that could be extended in future work with ideas from these recent works. Hence, we compare GreedTok with other base tokenizer algorithms, BPE/Unigram, focusing on the core tokenizer algorithm implementations without extra features or extensions.\n\n### Analysis of token quality\n\nWe appreciate your request for a deeper analysis of token quality. While our main focus was on compression and downstream performance, we did conduct some additional investigations, which we summarize below and will expand in the revision.\n\n*Morphological coherence*: To assess whether GreedTok captures meaningful subword units, we compared token sets on the coverage of English prefixes and suffixes (using lists from Wikipedia-EN). We found that GreedTok performs comparably to BPE in capturing these meaningful affixes; see table below.\n\nTable: Number and \\% of relevant suffixes/prefixes found\n|    |GreedTok |  BPE | Unigram|\n| --- |:---: | :---: | :---: |\n|*Prefix* | 142 (36.1\\%) | 146 (37.2\\%) | 157 (39.9\\%)|\n|*Suffix* | 112 (26.0\\%) | 112 (26.0\\%) | 94 (21.9\\%)|\n\n*Multilingual performance*: We analyzed tokenization behavior on Wikipedia data in Chinese, Japanese, and Korean (CJK), both individually and jointly (experiment mentioned around line 352). We observed that GreedTok tends to introduce longer tokens, often corresponding to full nouns, earlier as compared to BPE which enforces pairwise merges. In CJK languages, phonetic loanwords from English are often translated into sequences of characters that do not carry individual semantic meaning. GreedTok naturally merges such sequences into single tokens, which can be desirable as the individual characters in such sequences do not carry semantic meaning. Below, we list some examples where pairwise merging is bypassed, with \\# indicating the order of inclusion in the token set:\n\n\n*Chinese*\n\n平方公里 - square kilometre (12 bytes) (12 way merge from bytes) \\#123\n\n华人民共和国 - People’s Republic of China (18 bytes, 6 way merge) \\#551 \n\n洛杉磯 - Los Ángeles (9 bytes) (7 way merge; first token merged before, rest from bytes) \\#4229\n\n迪士尼 - Disney (9 bytes; 3 way merge) \\#6684\n\n*Japanese*\n\nプログラム - program  (15 bytes, 3-way merge) \\#2844\n\nロンドン - London (12 bytes, 3-way merge) \\#2857\n\nロサンゼルス - Los Ángeles (18 bytes) (4-way merge) \\#7066\n\nディズニー - Disney (15 bytes, 3-way merge) \\#7980\n\n*Korean*\n\n로스앤젤레스 - Los Ángeles (18 bytes, 6-way merge) \\#1630\n\n엔터테인먼트 - entertainment (18 bytes, 6-way merge) \\#1740\n\n디즈니 - Disney (9 bytes, 3-way merge) \\#6606\n\n### References\n\n[1] Craig W Schmidt, Varshini Reddy, Haoran Zhang, Alec Alameddine, Omri Uzan, Yuval Pinter, and Chris Tanner. Tokenization Is More Than Compression. ACL, 2024.\n\n[2] 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. Tokenizer Choice For LLM Training: Negligible or Crucial?. NAACL, 2024,\n\n[3] Mayank Mishra. Dolomite Engine: A Hyper-Optimized Library for Pretraining and Finetuning. Github, 2024.\n\n[4] Ivan Provilkov, Dmitrii Emelianenko, Elena Voita. BPE-Dropout: Simple and Effective Subword Regularization. ACL, 2020.\n\n[5] BPE Gets Picky: Efficient Vocabulary Refinement During Tokenizer Training\nPavel Chizhov, Catherine Arnett, Elizaveta Korotkova, Ivan Yamshchikov. BPE Gets Picky: Efficient Vocabulary Refinement During Tokenizer Training. ACL, 2024\n\n[6] Craig W. Schmidt, Varshini Reddy, Chris Tanner, Yuval Pinter. Boundless Byte Pair Encoding: Breaking the Pre-tokenization Barrier. arXiv, 2025."}, {"review_id": "weze0YhRQM", "reviewer": "Reviewer_gs2o", "summary": "This paper proposes a novel method for tokenization. The authors first show that the tokenization problem can be reduced from the vertex cover problem, showing that it is an NP-hard optimization problem. They then propose a greedy optimization algorithm to address it. Since the relaxed version of the problem corresponds to the weighted maximum coverage problem, greedy algorithms are expected to yield good solutions. Through experiments on multiple datasets, the authors demonstrate that their method achieves higher compression rates than BPE and Unigram. Furthermore, when used for language model pre-training, the proposed method outperforms BPE on various downstream benchmarks.", "questions": "- While lazy evaluation strategies are well known to be fast in practice, I think their exact cost is unknown. How do you drive  $\\Theta(|T|\\sum_{W}|W|)$ in line 350?  If you aim to speed up the greedy algorithm, applying the stochastic greedy algorithm [2] may offer further speedups.\n\n- Why is the proposed method not compared against UNIGRAM in the experiments presented in Section 5.2?\n\n\n[2] Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. 2015. Lazier than lazy greedy. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI'15). AAAI Press, 1812–1818.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths\n- This paper reveals a connection between tokenization and the vertex cover problem and presents a novel tokenization method from a fresh perspective, distinct from existing approaches. The proposed method is original and also appealing in its simplicity.\n\n- The paper is clearly written and includes many illustrative examples, making it easy to follow.\n\n- Experimental results show the advantage of the proposed method over standard tokenization baselines.\n\n- While no theoretical guarantee is provided for the solution quality, the weighted maximum coverage problem is well known to admit good approximations with greedy algorithms. The proposed method empirically achieves strong performance in this regard.\n\n# Weaknesses\n- As a method for selecting an optimal token dictionary, VOLT [1] is known to be effective. VOLT has been reported to outperform SentencePiece and BPE on machine translation tasks. Although I appreciate the simplicity of the proposed method, it would be preferable to include a comparison with VOLT or a discussion of the advantages of the proposed method relative to it.\n\n[1] Xu et al. Vocabulary Learning via Optimal Transport for Neural Machine Translation, ACL-IJCNLP 2021. https://aclanthology.org/2021.acl-long.571.pdf", "was_revised": true, "final_justification": "The authors have adequately addressed my concerns during the discussion, so I will keep my initial score. I believe this paper presents a theoretically grounded, simple, and novel method that is also effective in practice.", "rebuttal": "Thank you for taking the time to review our work and for the thoughtful and constructive feedback. We address your questions and comments below.\n\n### Comparison with VOLT [1]\n\nWe appreciate your suggestion to consider VOLT [1] in our evaluation. VOLT is an effective method for selecting a token vocabulary by maximizing the entropy of subword distributions across a candidate set. It operates by selecting from an existing pool of tokens generated via Unigram or BPE, often with variable vocabulary sizes. While VOLT excels at vocabulary selection, it is complementary to token generation methods such as GreedTok.\n\nIn fact, GreedTok could serve as an upstream tokenizer to generate candidate tokens for VOLT, especially when the target vocabulary size is flexible and full character coverage is required. Our focus in this work was on building a standalone token generation method with strong compression and practical usability under fixed-size constraints. Nonetheless, we agree that exploring a GreedTok-then-VOLT pipeline could be an interesting direction for future work, and we will include this discussion in the revised paper.\n\n### Lazy evaluation and computational cost\n\nThank you for highlighting the need for a clearer explanation of the computational cost of our lazy evaluation strategy. Our bound of $|\\mathbf{T}| \\cdot \\sum_{W} |W|$ is not an actual analytical bound but an empirically observed one. We will make correct the phrasing and make it clear in our revision.\n\nIn practical scenarios, the target vocabulary size $k$ is much smaller than the number of candidate tokens $|\\mathbf{T}|$, which can be upwards of 100M. Despite this, we observe empirically that it is rarely necessary to evaluate all $|\\mathbf{T}|$ token scores in each iteration. In our implementation, we update scores in small batches of 100 candidate tokens, which typically suffices to identify the next best token to add. In some iterations, score updates can be entirely skipped due to caching from previous steps. As a result, the cumulative cost over $k$ iterations remains much smaller than the naive $k \\cdot |\\mathbf{T}|$ bound. That is, we observe that our lazy strategy scales *empirically* like $|\\mathbf{T}| \\cdot \\sum_{W} |W|$.\n\n### Stochastic greedy algorithm of [2]\n\nWe appreciate the suggestion to consider stochastic greedy algorithms, such as [2], as a potential speedup technique. This is indeed an intriguing direction since stochastic methods could further reduce evaluation overhead by sampling candidates rather than scanning deterministically. While not explored in our current work, this aligns well with the goals of GreedTok, and we are excited by the prospect of exploring such techniques. We will add this as a promising avenue for future research.\n\n### On the absence of Unigram in Section 5.2\n\nWe appreciate your interest in seeing Unigram included in our evaluation. There were several reasons why we ultimately chose not to include it in Section 5.2.\n\nAs noted in prior work [3, 4], HuggingFace's (HF) implementation of Unigram has some known limitations. For example, it deviates from the original SentencePiece implementation and exhibits certain biases (see Footnote 17 in [3]). More critically, the HF Unigram tokenizer lacks support for byte-level fallback, resulting in rare or unknown inputs being mapped to `<unk>` tokens, rather than a more robust byte-level representation. This makes a fair comparison with BPE difficult, as BPE does offer byte-level fallback. We attempted to simulate byte-level fallback in HF Unigram by appending ASCII-escaped byte tokens to the vocabulary. However, this resulted in many tokens being encoded as escaped Unicode strings (e.g., `\\\\x...`), which degraded performance.\n\nAs for the original SentencePiece Unigram implementation, we encountered further difficulties. Training it on the full 20\\% DCLM corpus used for our tokenizer training exceeded our available memory capacity. Reducing the training data to fit memory constraints would have significantly weakened compression quality, further limiting the validity of comparisons. Additionally, SentencePiece Unigram does not allow for precise control over vocabulary size as it tends to add extra characters as tokens after training. This resulted in differing token counts and thus models with different parameter sizes.\n\nGiven these challenges and our finite compute resources, we chose to focus on the BPE versus GreedTok comparison, which allows for cleaner and more reproducible evaluation. Moreover, BPE remains the most widely adopted method in current practice, making the comparison more directly relevant. That said, we agree that a comparison with Unigram would be interesting. If you are aware of better-supported or alternative implementations of Unigram with byte-level fallback, we would be very interested in exploring them. Thank you again for this suggestion.\n\n### References\n\n[1] Jingjing Xu, Hao Zhou, Chun Gan, Zaixiang Zheng, and Lei Li. Vocabulary Learning via Optimal Transport for Neural Machine Translation. ACL, 2021.\n\n[2] Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. 2015. Lazier than lazy greedy. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI'15). AAAI Press, 1812–1818.\n\n[3] Craig W Schmidt, Varshini Reddy, Haoran Zhang, Alec Alameddine, Omri Uzan, Yuval Pinter, and Chris Tanner. Tokenization Is More Than Compression. ACL, 2024.\n\n[4] 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. Tokenizer Choice For LLM Training: Negligible or Crucial?. NAACL, 2024."}, {"review_id": "bq47f70lZZ", "reviewer": "Reviewer_MQ49", "summary": "This paper studies the computational complexity of the tokenization problem and proves that it is NP-hard. The authors establish this result by reducing the original token search problem to a tokenization decision problem, which they show to be NP-hard via a reduction from the Vertex Cover problem. Constrainet optimization-based formulation is also introduced.\n\nTo address the intractability, the paper proposes a new approximation algorithm designed to improve compression quality while enjoying a polynomial time complexity. Experimental results on real-world datasets demonstrate that the proposed method outperforms existing approaches such as BPE and Unigram in terms of compression/perplexity performance.", "questions": "It would be helpful to clarify whether there is any meaningful distinction between the problem formulation presented in Problem 1 and Definition 2 in [WBP24], especially since this work aims to establish analogous results. A direct comparison or discussion would strengthen the exposition and help the reader appreciate the novelty or alignment of the proposed formulation with prior work.\n\nLine 261 notes that preprocessing is required to extract words from the corpus. Could the authors comment on whether their algorithm can be adapted to work without such preprocessing? This would align more closely with the setting considered by SuperBPE [1], which, to my understanding, also reflects the original BPE algorithm without additional preprocessing steps. Addressing this would help clarify the scope and flexibility of the proposed approach.\n\nLine 237-243, is it fair to say that GreedTok is an extension of BPE but without pairwise merge constraints, i.e., we are allowed to merge any $n$ tokens to create a new one? How optimal is the proposed algorithm compares to other recent tokenization scheme such as [SRZ+24]?\n\nIs there any insights why there is little difference in terms of performance in Figure 2b? For tokens/words $t$ that occurs in both vocabularies, is there any significant different in terms of the empirical next-token probability $P(t | prompt')$?\n\n[1] Liu, Alisa, et al. \"Superbpe: Space travel for language models.\" arXiv preprint arXiv:2503.13423 (2025).", "limitations": "The paper currently lacks clarity in several foundational definitions, making it difficult to follow. For example, in Section 2, the content of the alphabet $\\Sigma$ is not explicitly defined. Additionally, the notation $\\Sigma^+$ is used without explanation—what does it represent, and how does it relate to $\\Sigma$?\n\nIt is also unclear why $\\Sigma^+$ is assumed to contain \\emph{words}, and this assumption is neither justified nor motivated. Further confusion arises from inconsistent usage: $\\Sigma^+$ is described as containing \\emph{words} on line 89 and \\emph{tokens} on line 97. Are \\emph{tokens} and \\emph{words} considered equivalent in this context, or is there a meaningful distinction between them? Clarifying these points would significantly improve the precision and readability of the paper. In fact, I have to jump back and forth between Section 2,3,4 to better understand the notations.\n\nEmpirical/Theoretical runtime complexity should be included in the paper as a table of reference for practitioner.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper provides an alternative algorithmic viewpoint on the complexity of tokenization.\n- The proposed tokenization scheme outperforms the standard baseline\n\nWeakness:\n- [Major] The writing is confusing (see limitations). \n- [Minor] No approximation guarantee for GreedTok.", "was_revised": true, "final_justification": "This paper studies the cover problem of tokenization and provide some interesting theoretical contribution.", "rebuttal": "Thank you for taking the time to review our work and for the thoughtful and constructive feedback. We address your questions and comments below.\n\n### Comparison with [WBP24]\n\nWe appreciate the suggestion to clarify our relation to [WBP24]. Problem 1 in our paper is indeed equivalent to Definition 2 in [WBP24], up to notational differences. We will make this equivalence explicit in the revised version.\n\nHowever, our work differs from [WBP24] in two key aspects. Firstly, [WBP24] proves NP-hardness via a lengthy reduction from MAX-2-SAT while we offer a more concise 1-page reduction from vertex cover. Moreover, [WBP24] does not propose an algorithm or report empirical results, whereas our work introduces GreedTok and validates it through experiments on real-world NLP datasets. We believe this adds both theoretical and practical contributions beyond prior work.\n\n### Pre-processing and relation to BPE\n\nGreedTok is not an extension of BPE. It is a fundamentally different construction that does not rely on pairwise merges. While it is true that GreedTok allows more general n-wise merges, it does not inherit the inductive structure of BPE and therefore cannot operate without preprocessing. This behavior is more similar to Unigram tokenization, which also requires word-level frequency statistics prior to training. That said, GreedTok's preprocessing step can be accelerated by leveraging prior knowledge of high-quality token candidates (e.g., frequent substrings or n-grams), or by restricting candidate generation based on token length or frequency. We will clarify this in the paper.\n\n### Comparison with SuperBPE [1]\n\nSuperBPE [1] merges tokens across whitespace boundaries to form \"super tokens\" after an initial BPE pass. This approach leads to larger token sets and can complement GreedTok's output. For instance, GreedTok tokens can be used as the base vocabulary from which SuperBPE-style merges are subsequently applied. We consider this a promising direction for future work. Since SuperBPE appeared in March 2025 (contemporaneous with our submission), we did not include it in the initial comparison but will mention it in our revision.\n\n### Comparison against PathPiece [SRZ+24]\n\nPathPiece [SRZ+24] is a decoding algorithm that operates independently of how the vocabulary is constructed. It assumes a pre-defined token set and does not perform token selection or training. As such, PathPiece can be directly applied to any token vocabulary, including one generated by GreedTok. Our focus is on the vocabulary construction step, and we see PathPiece as a complementary technique rather than a competing one.\n\n### Performance insights and Figure 2b\n\nThank you for the insightful question regarding the results in Figure 2b. GreedTok produces a more compact representation of text (i.e., fewer tokens per sentence), which influences the average log-likelihood per token. For example, while the BPE-trained model may achieve an average negative log-likelihood of ~2.0 per token, GreedTok-trained models may show ~2.5, due to fewer, longer tokens. However, directly evaluating on this metric alone can be misleading. To fairly compare models with different token granularities, we evaluate performance in terms of bits-per-byte. This metric is independent of tokenization and reflects true compression performance on the underlying data. Figure 2b shows that, when normalized in this way and trained on equivalent byte-lengths of data, GreedTok performs comparably to BPE. This highlights the competitive modeling capacity of GreedTok despite structural differences in tokenization. We will add a version of this discussion in our revision.\n\n### Notation concerns\n\nBelow, we clarify our notation and we will add a version of this discussion to our revision.\n\n* Alphabet ($\\mathbf{\\Sigma}$) refers to the basic character set. This may be the 26 lowercase English letters or the full Unicode set, depending on context.\n\n* The star superscript is standard Kleene-star notation in Computer Science to mean \"0 or more times\", which is also commonly used in Regex expressions. In our context, $\\mathbf{\\Sigma}^*$ denotes the set of all finite strings formed from characters in $\\mathbf{\\Sigma}$.\n\n* $\\mathbf{W}$ refers to the set of distinct words in the corpus, which is why we have $\\mathbf{W} \\subseteq \\mathbf{\\Sigma}$. Menawhile, tokens $\\mathbf{T}$ are candidate substrings drawn from $\\mathbf{\\Sigma}^*$, that may or may not correspond to actual words.\n\n### Runtime complexity\n\nOur theoretical runtime analysis is presented in Section 6 (Page 9, Lines 347–358) and Appendix G. Meanwhile, our empirical timings are reported in Table 1 (Page 6).\n\n### References\n\n[1] Alisa Liu and Jonathan Hayase and Valentin Hofmann and Sewoong Oh and Noah A. Smith and Yejin Choi. SuperBPE: Space Travel for Language Models. arXiv, 2025."}]

Author rebuttal:

Meta-review: The reviewers and I are in unanimous agreement that the paper makes an insightful contribution to the theory and practice of tokenization. We especially find the approach of reducing tokenization to vertex cover novel and elegant, especially in contrast to the approach of the recently-posted paper "Tokenisation is NP-Complete" [wbp24] (as pointed out by Reviewer MQ49). The method, theory, and experimental results are a clear study on the topic.

The main concerns of the papers are 1) only comparing with base BPE/Unigram rather than other variations on these, and 2) "only" evaluating on a 1B LM (and the 1B LM gains in Figure 2 and Table 4 do not seem extremely significant). The response here seems reasonable, as the partition cover approach seems novel enough and possible to augment with other variations. We encourage you to continue exploring these.
Decision: Accept (poster)