Thank you for taking the time to review our work and for the thoughtful and constructive feedback. We address your questions and comments below.

Comparison with [WBP24]

We 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.

However, 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.

Pre-processing and relation to BPE

GreedTok 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.

Comparison with SuperBPE [1]

SuperBPE [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.

Comparison against PathPiece [SRZ+24]

PathPiece [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.

Performance insights and Figure 2b

Thank 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.

Notation concerns

Below, we clarify our notation and we will add a version of this discussion to our revision.

• 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.

• 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}$.

• $\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.

Runtime complexity

Our 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).

References

[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.

Thank you for taking the time to review our work and for the thoughtful and constructive feedback. We address your questions and comments below.

Comparison with VOLT [1]

We 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.

In 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.

Lazy evaluation and computational cost

Thank 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.

In 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|$.

Stochastic greedy algorithm of [2]

We 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.

On the absence of Unigram in Section 5.2

We 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.

As 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.

As 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.

Given 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.

References

[1] Jingjing Xu, Hao Zhou, Chun Gan, Zaixiang Zheng, and Lei Li. Vocabulary Learning via Optimal Transport for Neural Machine Translation. ACL, 2021.

[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.

[3] Craig W Schmidt, Varshini Reddy, Haoran Zhang, Alec Alameddine, Omri Uzan, Yuval Pinter, and Chris Tanner. Tokenization Is More Than Compression. ACL, 2024.

[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.

Thank you for taking the time to review our work and for the thoughtful and constructive feedback. We address your questions and comments below.

Error bars and statistical significance

We 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.

Comparison with other variants of BPE

Thank 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.

BPE-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.

PickyBPE [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.

Boundless 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.

Overall, 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.

Analysis of token quality

We 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.

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.

Table: Number and % of relevant suffixes/prefixes found

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:

Chinese

平方公里 - square kilometre (12 bytes) (12 way merge from bytes) #123

华人民共和国 - People’s Republic of China (18 bytes, 6 way merge) #551

洛杉磯 - Los Ángeles (9 bytes) (7 way merge; first token merged before, rest from bytes) #4229

迪士尼 - Disney (9 bytes; 3 way merge) #6684

Japanese

プログラム - program (15 bytes, 3-way merge) #2844

ロンドン - London (12 bytes, 3-way merge) #2857

ロサンゼルス - Los Ángeles (18 bytes) (4-way merge) #7066

ディズニー - Disney (15 bytes, 3-way merge) #7980

Korean

로스앤젤레스 - Los Ángeles (18 bytes, 6-way merge) #1630

엔터테인먼트 - entertainment (18 bytes, 6-way merge) #1740

디즈니 - Disney (9 bytes, 3-way merge) #6606

References

[1] Craig W Schmidt, Varshini Reddy, Haoran Zhang, Alec Alameddine, Omri Uzan, Yuval Pinter, and Chris Tanner. Tokenization Is More Than Compression. ACL, 2024.

[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,

[3] Mayank Mishra. Dolomite Engine: A Hyper-Optimized Library for Pretraining and Finetuning. Github, 2024.

[4] Ivan Provilkov, Dmitrii Emelianenko, Elena Voita. BPE-Dropout: Simple and Effective Subword Regularization. ACL, 2020.

[5] BPE Gets Picky: Efficient Vocabulary Refinement During Tokenizer Training Pavel Chizhov, Catherine Arnett, Elizaveta Korotkova, Ivan Yamshchikov. BPE Gets Picky: Efficient Vocabulary Refinement During Tokenizer Training. ACL, 2024

[6] Craig W. Schmidt, Varshini Reddy, Chris Tanner, Yuval Pinter. Boundless Byte Pair Encoding: Breaking the Pre-tokenization Barrier. arXiv, 2025.

Thank you for taking the time to review our work and for the thoughtful and constructive feedback. We address your questions and comments below.

On the absence of Unigram in Table 4

We 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.

As 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.

As 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.

Given 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.

Robustness to adversarial attack

From 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. Thus, 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.

Limitations

We appreciate your observations and agree with both points.

While 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.

Regarding 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.

References

[1] Craig W Schmidt, Varshini Reddy, Haoran Zhang, Alec Alameddine, Omri Uzan, Yuval Pinter, and Chris Tanner. Tokenization Is More Than Compression. ACL, 2024.

[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.

Thank you for the response. I appreciate your detailed reply regarding the challenges of a unigram model, and comments on low-resource evaluation. I have kept my scores and still recommend an accept of this paper.