acceptodds
Under review as a conference paper at ICLR 2027

Tokenization with Formal Guarantees: From Optimal Compression to Provable Bounds

Abstract

Tokenization maps text into sequences of tokens from a fixed vocabulary and is a core component of modern NLP pipelines. Recent complexity-theoretic work formalizes tokenization as selecting tokens that optimize a compression objective over a corpus, and shows that computing an optimal solution is NP-complete. This shows that widely used tokenization methods such as Byte-Pair Encoding (BPE) are inherently heuristic and do not guarantee optimality. While this line of work has largely remained theoretical, Lim et al. recently took a practical step by introducing a mixed-integer programming (MIP) formulation and a greedy approximation algorithm for this objective. However, their MIP formulation suffers from a parameter explosion that makes it impractical for modern solvers such as Gurobi, while the greedy algorithm provides no optimality guarantee. In this work, we introduce a new *graph-flow MIP formulation* for tokenization that substantially reduces the number of decision variables and constraints, making optimal compression-based token selection tractable for state-of-the-art solvers. This enables, for the first time at this scale, the computation of *provably optimal* compression of token vocabularies for large corpora. To further improve scalability, we introduce a *Lagrangian relaxation* based on a shortest-path selection formulation. Our experiments show that our exact MIP algorithms achieve provably optimal compression and substantially outperform existing compression-based tokenization schemes, even on corpora with millions of candidate tokens. Moreover, our Lagrangian relaxation scales to significantly larger corpora, substantially improving over the state of the art in compression, and providing *provable upper and lower bounds* on the optimal value. Overall, this work takes a significant step toward turning optimal token selection from a theoretical objective into a practical algorithmic tool for building highly compressed vocabularies for real-world data.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
tokenization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_s3LoOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

The paper proposes a new MIP formulation for the optimal compression for Tokenization problem. The previous paper provides a problem formulation and a MIP formulation of the problem, which requires Θ((∑w∈W∣w∣)⋅∣T∣)\Theta((\sum_{w \in \mathcal{W}} |w|) \cdot |\mathcal{T}|) variables and constraints. The paper introduces an alternative MIP formulation that uses Θ(∑w∈W∣w∣2)\Theta(\sum_{w \in \mathcal{W}} |w|^2) variables and constraints. Moreover, the paper introduces a Lagrangian relaxation approach that can derive both upper and lower bounds of the problem. The paper experimentally evaluated the proposed MIP formulation and its Lagrangian relaxation to show that the MIP formulation can improve the running time over the previous one when solved with Gurobi, and the Lagurangian relaxation can achieve a better compression ratio over previous GreedTok heuristics.

Critical strengths
  1. The proposed approach is simple and easy to understand. The proposed MIP formulation is simple but a clever idea for reducing the number of variables and constraints. Moreover, its Lagrangian relaxation method seems an reasonable way to improve the scalability of the proposed method, although its novelty is not so high since the Lagrangian relaxation is a well-known method for solving difficult MIP problems, which has been actively used in NLP tasks for more than a decade.

  2. The proposed approach can derive both lower and upper bounds for the tokenization task, which is not obtained by the previous greedytok algorithm.

Critical weaknesses

Although the proposed method is simple and interesting, experimental evaluations are weak to support its superiority over existing tokenization methods when used for language modeling.

  1. The results in Sec. 6.1 are interesting. However, its practical impact is questionable since the running time of the proposed method is evaluated with only the smallest Wikitext dataset. Although it is true that the proposed formulation can improve the running time and memory usage over previous MIP formulation, the scalability of both methods are not enough to be used in practical large scale datasets. Moreover, the exact results are only reported for a single dataset.

  2. Results in Sec. 6.2 also seems not enough. The authors say that the improvements in Fig. 6 are substantial. However, I cannot read out such a substantial improvement over GreedTok in many cases. For example, the improvement of the compression ratio for PubMed lies within 0.005 points for all kk. Moreover, the paper does not mention to the running time. While the GreedTok algorithm is a polynomial time algorithm, the proposed Lagrangian relaxation is not. In general, the running time and the quality of solutions are trade-off. Therefore, the paper must show that LRX provides a good balance in between the quality of solutions and running time.

  3. The language modeling experiments in Sec. 6.3 seems not strong enough. Firstly, Tab.3 does not contain results of the GreedTok. Since the proposed method is said to refine GreedTok, the paper should compare the ability of language modeling by comparing with GreedTok. Secondly, the difference of BPE-based methods and LRX-based methods in Tab.3 are not significant enough. For example, the difference of both methods are within 0.01 points for arXiv and UN, and they become smaller as the training data increases. Moreover, ±\pm std values are larger compared with the difference of average values. These results suggest that the difference of BPB scores are not significant enough.

Questions for authors
  1. Is it possible to compare the running time of BPE, GreedTok, and LRX? I think that this paper must provide that LRX achieves a good trade-off of running time and solution quality.

  2. Is it possible to compare the BPB scores of LRX and GreedTok?

  3. Why do you think the difference shown in Fig.6 are substantial?

6 comments

We thank the reviewer for their helpful and constructive feedback and for acknowledging the importance of our work. Following the reviewer's comments, we have made the complexity of our Lagrangian relaxation (LRX) explicit (Section 5) and added its compression as a function of wall-clock time against the baselines (Appendix L), exact MIP results on arXiv and PubMed with a comparison to the prior formulation (Appendix P), GreedTok in the language-modeling experiments together with significance tests (Section 6.3 and Appendix N), and a discussion of Lagrangian relaxation in NLP (Section 7). In addition, we have analyzed the share of each baseline's optimality gap that LRX closes (Appendix O) and added a larger-scale language-modeling experiment (Appendix N), which further support our answers. We have also summarized the main results in the relevant sections of the main text, and summarize the additions below.

Running time of the Lagrangian relaxation, and whether it is polynomial

Following the reviewer's comment, we have made the complexity explicit in Section 5 and added running-time and memory measurements for all methods (Appendix L). Each iteration of Algorithm 1 runs in polynomial time, linear in the size of the corpus graph. Concretely, the shortest path in each word DAG GwG_w takes O(∣w∣2)O(|w|^2) time, since GwG_w has O(∣w∣2)O(|w|^2) edges; aggregating the token scores sλ(t)s_\lambda(t) and computing the subgradient take O(∣E∣)O(|E|); selecting the kk highest-scoring tokens takes O(∣T∣)O(|\mathcal{T}|) with linear-time selection; and the upper-bound paths take another O(∣E∣)O(|E|). Since ∣T∣≤∣E∣=Θ(∑w∣w∣2)|\mathcal{T}|\le|E|=\Theta(\sum_{w}|w|^2), one iteration costs Θ(∑w∣w∣2)\Theta(\sum_{w}|w|^2), and nn iterations cost O(n⋅∑w∣w∣2)O(n\cdot\sum_{w}|w|^2). The sum ranges over distinct words only, since repeated words enter as frequency weights f(w)f(w). With a fixed iteration budget, the algorithm is therefore polynomial. It is also anytime: it can be stopped at any iteration, and it then returns a feasible vocabulary together with a certified gap.

We agree with the reviewer that the right comparison is solution quality against running time. Since our method starts from a poor vocabulary and improves monotonically, a single running time does not characterize it. We have therefore added plots of the compression ratio of our Lagrangian relaxation as a function of wall-clock time, against the final compression ratios of GreedTok and BPE, for every dataset and budget of Figure 6 (Appendix L), and summarize them in Section 6.2.

The heuristics are fast, but they settle at a worse compression ratio. Our method improves monotonically and overtakes both of them on every corpus and for every budget; for example, at k = 25K, it does so on UN after about 15 minutes, on arXiv after about 75 minutes, and on PubMed, the largest corpus, after about 10 hours (excluding data loading). This budget is spent only once: vocabulary construction is an offline procedure carried out before training and inference, so it does not affect those runtime-sensitive stages, while the improved compression benefits every subsequent training run and inference call, so a longer construction time is much less of a limitation. A user with a smaller budget can stop the algorithm earlier and keep the best vocabulary obtained so far. We thank the reviewer for this suggestion, which we believe makes the practical cost of our method considerably clearer. The running time and peak memory of all methods under matched hardware are reported in Appendix L.

Why we consider the improvements in compression substantial

We agree that our wording should be more precise, and have revised it in Section 6.2. We have also added an analysis of how much of each baseline's remaining optimality gap LRX closes (Appendix O). Two points matter here. First, since the compression ratio is measured in tokens per word over the whole corpus, small absolute differences correspond to large token counts: on PubMed, which contains about 4.1B words, an improvement of 0.005 tokens per word amounts to roughly 20M fewer tokens. Second, as k grows, the compression ratio of every method approaches 1 and the room for improvement shrinks, so the natural yardstick is the fraction of the remaining optimality gap that a method closes, which our certified lower bound makes measurable for the first time. Measured this way, LRX closes 47–72% of GreedTok's certified gap on UN, 14–46% on arXiv and 4–23% on PubMed, and 51–90% of BPE's gap across all three datasets (Appendix O).

DatasetBudgets kShare of GreedTok's gap closed by LRXShare of BPE's gap closed by LRX
UN10K, 15K, 20K, 25K, 30K47%, 57%, 64%, 72%, 67%80%, 85%, 88%, 90%, 89%
arXiv10K, 15K, 20K, 25K, 30K14%, 36%, 41%, 35%, 46%51%, 63%, 66%, 66%, 67%
PubMed20K, 25K, 30K, 35K, 40K4%, 14%, 15%, 23%, 16%53%, 60%, 66%, 64%, 64%

The share of a baseline's gap closed is (baseline − LRX) / (baseline − certified lower bound); the largest value per row is in bold.

Where the margin over GreedTok is small, most notably on PubMed, our bounds explain why: they certify that GreedTok is already within 1.05–2.42% of the optimum there, so no method can improve on it by more than that. We view this certification as a contribution in itself, since without a lower bound one cannot tell whether a heuristic is near-optimal or simply unbeaten. We thank the reviewer for this question, which helped us make this point explicit.

The role of the exact MIP, and exact results beyond WikiText

We agree with the reviewer that, as for any exact method for an NP-hard problem, exact solving alone is computationally hard to scale. This is precisely why we also introduce the Lagrangian relaxation: built on the same flow encoding, it scales to large corpora while still providing provably certified lower and upper bounds on the optimum. The exact MIP remains valuable on relatively smaller corpora, where it provides ground truth for the scalable method: on new slices of arXiv and PubMed, LRX's certified lower bound is within 0.15–0.62% of the true optimum wherever the optimum is known. Moreover, as the reviewer notes, our encoding is substantially faster and more memory-efficient than the previous MIP formulation, so it can solve significantly larger instances. MIP solvers have scaled rapidly in recent years, and the reach of our exact formulation will continue to grow as they continue to scale. We now state this explicitly in Section 4.

To address the evaluation on a single dataset, we have added these exact MIP results on slices of arXiv and PubMed, with budgets that bind (Appendix P). On the slices where Gurobi does not prove optimality, LRX's lower bound is 0.5–1.0% below Gurobi's best proven bound. Its certificates therefore remain informative on the large corpora where only bounds are available.

DatasetDocumentsTrue optimumLRX lower boundLRX
arXiv501.57881.5765 (−0.15%)1.6241 (+2.87%)
arXiv1001.83131.8200 (−0.62%)1.9115 (+4.38%)
arXiv2001.9696–1.97331.95142.0577
arXiv4002.0064–2.01451.98962.0997
arXiv8002.0242–2.05562.00492.1092
PubMed101.47021.4636 (−0.44%)1.5231 (+3.60%)
PubMed151.5574–1.56281.54991.5975
PubMed251.7014–1.70951.68861.7813
PubMed501.7762–1.81401.76121.8478

The table reports compression ratios (tokens per word) at k = 1,000; ranges give Gurobi's proven bound and best solution where it stopped at its 12-hour or memory limit, and percentages are relative to the optimum.

The same slices also extend our comparison with the prior formulation beyond WikiText: ours has 3.3–3.7× fewer variables, proves optimality on instances where the prior one does not, and reaches a smaller gap on every other slice, while on the largest arXiv slice the prior formulation cannot even be built within 128 GB (Appendix P).

Finally, exact solving can be extended further through hybrid approaches that preserve exactness: the vocabulary of our Lagrangian relaxation can warm-start the exact solver, and its multipliers can prove that certain tokens cannot appear in any optimal solution, removing them from the MIP. We have added this discussion to the Future Work section.

Language-modeling comparison with GreedTok

As suggested, we have added GreedTok to the language-modeling experiments, both in the original 22M-parameter setting (Table 3) and in a new larger-scale experiment with a 109M-parameter GPT-2 model on ClimbMix (Appendix N, summarized in Section 6.3).

CorpusBPEGreedTokLRX (ours)
arXiv1.1691 ± .0061.1719 ± .0191.1687 ± .012
WikiText2.0390 ± .0191.9995 ± .0141.9768 ± .018
UN0.9647 ± .0040.9613 ± .0110.9630 ± .004
ClimbMix (109M)1.1461 ± .0031.1414 ± .0031.1365 ± .006

The table reports the final-checkpoint validation BPB (mean ± std) of the 22M-parameter models over five seeds, and of the 109M-parameter GPT-2 model on ClimbMix over three seeds; results at 25/50/75% of training are in Appendix N, and we discuss the significance of these differences in the next answer.

Significance of the BPB differences

We agree with the reviewer's reading, and have added significance tests for all BPB differences (Appendix N). We would also like to clarify the goal of these experiments, which we now state more explicitly in Section 6.3. Our claim is not that our method yields a significantly better BPB, although it does attain a slightly better mean BPB in most settings. Rather, our claim is that its substantially better and certifiably near-optimal compression, which shortens sequences and can thereby improve aspects such as the number of decoding steps and the KV-cache memory at inference, does not come at the expense of language-modeling quality. To test this, we compared our method with each baseline at every checkpoint using a two-sided Welch's t-test over the five seeds, at a significance level of 0.05.

On WikiText, the BPB improvement is statistically significant. Against BPE, it is significant at every checkpoint (p ≤ 0.002), amounting to about 0.06 BPB at the end of training. Against GreedTok, LRX has the lower mean at every checkpoint; the difference is significant at 50% of training (p = 0.043) and borderline at 75% and 100% (p = 0.051 and 0.055), so LRX is better, but only marginally. On arXiv and UN, all three tokenizers are on par, and none of the differences is significant (p ≥ 0.37). On ClimbMix, our method again attains the lowest mean BPB at every checkpoint; with three seeds, the differences are not significant, but the p-value against BPE decreases steadily during training, reaching 0.076 at the end, close to the 0.05 threshold. Taken together, our substantially better compression does not come at the expense of language-modeling quality, and in some cases it even improves it. The p-values for every corpus and checkpoint appear in our response to Reviewer N7jY.

The use of Lagrangian relaxation in previous NLP works

We thank the reviewer for pointing us to this line of work, which we have added to the Related Work section. We fully agree that Lagrangian relaxation is a well-known technique that has been used in NLP in the past, notably through dual decomposition for structured prediction [1, 2]. Our contribution is not the technique itself, but a novel formulation of optimal-compression tokenization, a problem studied in several recent works [3, 4, 5], under which the problem decomposes into independent shortest-path problems plus a single top-k selection. This yields both feasible vocabularies and certified bounds on the optimal compression, making our method, to the best of our knowledge, the first to formally certify how close the compression of a tokenizer is to optimal at scale. We believe this is an important first step toward designing tokenizers with formal guarantees.

References

[1] Rush et al. On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing. EMNLP, 2010.

[2] Rush and Collins. A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing. JAIR, 2012.

[3] Lim et al. A Partition Cover Approach to Tokenization. NeurIPS, 2025.

[4] Whittington et al. Tokenisation is NP-Complete. ACL, 2025.

[5] Zouhar et al. A Formal Perspective on Byte-Pair Encoding. Findings of ACL, 2023.

Reviewer_TaUtOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies vocabulary selection for compression-based tokenization: given a corpus and a vocabulary budget, the goal is to minimize the number of tokens needed to encode the corpus. The authors represent each possible segmentation of a word as a path in a directed acyclic graph and use this representation to develop a compact flow-based mixed-integer program. Compared with a prior exact formulation, the new formulation is substantially smaller and enables a solver to certify optimal solutions on instances that were previously intractable. For larger corpora, the paper introduces a Lagrangian relaxation that decomposes into parallel shortest-path problems and produces feasible vocabularies together with certified lower and upper bounds on the optimum.

Overall, the paper makes a valuable algorithmic contribution by bringing formal optimality guarantees closer to practical tokenizer construction. Whether these gains translate into meaningful training or inference benefits for modern, larger language models remains an open question.

Critical strengths
  • A clear optimization objective. The paper defines tokenizer vocabulary selection as minimizing corpus token count under a fixed vocabulary budget. This makes the quality of a solution measurable against an optimum, rather than only against other heuristics.
  • A substantially more compact exact formulation. Representing word segmentations as paths in a DAG leads to a flow-based MIP with fewer variables and constraints than the prior exact formulation. The experiments show both faster solving and improved memory scalability.
  • Formal guarantees at two scales. The MIP can certify optimality when it finishes. For larger instances, the Lagrangian method provides a feasible solution and certified lower and upper bounds, making its remaining optimality gap explicit.
  • Relevant compression baselines and controls. The paper compares against BPE and GreedTok and additionally checks BPE with dynamic-programming encoding. The latter helps distinguish gains from vocabulary selection from gains obtained simply by changing the encoding algorithm.
Critical weaknesses
  • The paper does not measure tokenizer encoding throughput, model generation latency, request throughput, or peak KV-cache memory usage. An end-to-end evaluation should also account for the potential CPU overhead of dynamic-programming encoding.
  • The language-model experiments use only 22M-parameter models with a 256-token context window, trained for one epoch. Given that the tokenizers produce different sequence lengths, are the training budgets for LRX and BPE comparable in terms of computational cost?
  • Larger-scale experiments are needed. Results on larger models and longer contexts would help determine whether the observed BPB advantage persists as model scale increases.
  • At the final checkpoint, the BPB differences are small: 1.1691 versus 1.1687 on arXiv and 0.9647 versus 0.9630 on UN. The authors should report confidence intervals from paired runs or conduct significance tests to establish whether these improvements are reliable.
  • The evaluation would be stronger with comparisons against additional tokenizer construction methods beyond BPE and GreedTok.
Questions for authors
  • Could the authors report vocabulary-construction wall-clock time, peak memory usage, and online encoding throughput for BPE, GreedTok, and LRX under matched hardware, corpora, and vocabulary budgets?
4 comments

We thank the reviewer for their helpful and constructive feedback and for acknowledging the importance of our work. Following the reviewer's comments, we have added the vocabulary-construction time and memory of all methods, together with online encoding throughput (Appendix L), the exact training budgets of the language models (Appendix D), a larger-scale language-modeling experiment together with significance tests (Appendix N), and a UnigramLM baseline (Appendix M). In addition, we have added plots of the compression of our Lagrangian relaxation (LRX) as a function of wall-clock time (Appendix L), which further support our answers. We have also summarized the main results in the relevant sections of the main text, and summarize the additions below.

Encoding throughput, inference latency, KV-cache memory, and the cost of DP encoding

To address this, we have added encoding-throughput measurements and a discussion of inference cost (Appendix L). Our methods select the vocabulary offline, so their cost at inference time is that of the online encoder. With DP encoding, segmenting a pretokenized word ww takes O(∣w∣⋅L)O(|w|\cdot L) time, where LL is the maximum token length, and the segmentation of each distinct word can be cached. We measured online encoding throughput on arXiv, with all vocabularies trained on a 90% split and throughput measured on the remaining 10% (36.03 MB, 3.77M words), excluding vocabulary construction and corpus loading. We compare BPE with its standard merge-rank encoding, in two implementations (the optimized Rust implementation of Hugging Face, and a faithful Python port in the same environment as our DP implementation), with DP encoding over either the BPE vocabulary or ours:

MethodMB/sTokens/sSpeed relative to BPE + DP
BPE + merge-rank encoding (Hugging Face, Rust)30.803.74M3.07×
BPE + merge-rank encoding (Python)12.261.49M1.22×
BPE + DP encoding10.041.21M1.00×
LRX (ours) + DP encoding10.121.22M1.01×

The two merge-rank rows differ only in their implementation, so the gap of about 2.5× between them is not algorithmic; against the like-for-like Python implementation, DP encoding costs a further factor of about 1.2. This cost is a property of the online encoding scheme, not of our vocabulary: BPE with DP encoding is as fast as our method with DP encoding. Faster online encoding over merge-free vocabularies is an orthogonal direction for future work.

Beyond the encoder, a better-compressed vocabulary shortens sequences, and for a fixed amount of text, KV-cache memory and the number of decoding steps both scale linearly with the number of tokens. At k = 25K, our vocabularies shorten sequences relative to BPE by 0.8% on UN, 1.1% on arXiv and 2.3% on PubMed (Figure 6), which can translate into proportional savings at inference. We thank the reviewer for raising this important practical point.

Are the training budgets of our method and BPE comparable?

We thank the reviewer for this careful question, and have clarified this point in Appendix D. Yes, the budgets are equal: all models are trained on the same training documents for the same number of optimizer steps, so they process the same number of tokens and use the same training FLOPs. We set this number to about one epoch of our method, which has the fewest training tokens: 4,774 steps on arXiv, 247 on WikiText and 3,679 on UN (39.1M, 2.02M and 30.1M tokens).

Larger models and longer contexts

Following the reviewer's comment, we have added a larger-scale language-modeling experiment (Appendix N, summarized in Section 6.3). We trained a GPT-2 model with 109M parameters (12 layers, about five times the original model) with a four times longer context of 1,024 tokens, on ClimbMix [1], a general-domain pretraining corpus, with BPE, GreedTok and LRX vocabularies (k = 30K). Similarly to ConvexTok [2], all vocabularies are learned on part of the corpus, here two ClimbMix shards, and the models are trained on seven (288.8M words), so five of the seven training shards are unseen by every tokenizer. All three vocabularies are encoded with the same shortest-path DP, so that only the vocabulary differs, and all models are trained for the same number of steps (343.9M tokens), with three seeds. The validation BPB (mean ± std) is:

Tokenizer25% of training50%75%100%
BPE1.4183 ± .02191.2410 ± .00751.1801 ± .00371.1461 ± .0025
GreedTok1.3929 ± .01121.2327 ± .00741.1759 ± .00471.1414 ± .0032
LRX (ours)1.3889 ± .01811.2288 ± .00871.1699 ± .00611.1365 ± .0055

As in the original experiments, the purpose of this experiment is to verify that the better compression of our method does not come at the expense of language-modeling quality, and it confirms this at a larger scale and with a longer context. Our method also attains the lowest mean BPB at every checkpoint, ending at 1.1365, compared with 1.1414 for GreedTok and 1.1461 for BPE, although with three seeds these differences are not statistically significant (p ≥ 0.076 against BPE and p ≥ 0.24 against GreedTok). We thank the reviewer for this valuable suggestion.

Confidence intervals and significance tests for the BPB differences

As requested, we have added significance tests for all BPB differences (Appendix N): two-sided Welch's t-tests over the five seeds at every checkpoint, at a significance level of 0.05. We would also like to clarify the goal of these experiments, which we now state more explicitly in Section 6.3. Our claim is not that our method yields a significantly better BPB, although it does attain a slightly better mean BPB in most settings. Rather, our claim is that its substantially better and certifiably near-optimal compression, which shortens sequences and can thereby improve aspects such as the number of decoding steps and the KV-cache memory at inference, does not come at the expense of language-modeling quality.

We agree with the reviewer's reading of the final-checkpoint differences on arXiv (1.1691 versus 1.1687) and UN (0.9647 versus 0.9630): there, the tokenizers are on par, and none of the differences is significant (p ≥ 0.37). On WikiText, the BPB improvement is statistically significant: against BPE, it is significant at every checkpoint (p ≤ 0.002), amounting to about 0.06 BPB at the end of training. On ClimbMix, with the larger model described above, our method again attains the lowest mean BPB at every checkpoint; with three seeds, the differences are not significant, but the p-value against BPE decreases steadily during training, reaching 0.076 at the end, close to the 0.05 threshold. Taken together, our substantially better compression does not come at the expense of language-modeling quality, and in some cases it even improves it. Since Reviewer N7jY raised the same point, the p-values for every corpus and checkpoint, including the comparison with GreedTok, appear in our response to them.

Additional tokenizer construction methods

We have added UnigramLM [3] as a baseline (Appendix M, summarized in Section 6.2). We trained it with SentencePiece's default settings on the same byte-level word counts as the other methods, with the same vocabulary size and 20-byte maximum token length, and evaluated it with its native Viterbi encoding. The compression ratio (tokens per word; lower is better) at k = 25K is below; Appendix M reports k = 10K–40K.

DatasetBPEUnigramLMGreedTokLRX (ours)Certified LB
arXiv1.17901.17731.16941.16571.1589
UN1.02351.16461.01741.01511.0142
PubMed1.14811.39871.12491.12211.1049

Our method achieves the lowest compression ratio at every vocabulary size on all three datasets. UnigramLM compresses worse than BPE on UN and PubMed, in line with prior findings [4], and slightly better on arXiv at most budgets. As in the other methods, all 256 bytes are kept in its vocabulary; plain SentencePiece differs by at most 0.003. In addition, the paper evaluates our vocabulary combined with online encoding algorithms, compared with other combinations of vocabularies and encoders (Appendices E and G).

Vocabulary-construction time and memory

We have added the vocabulary-construction time and peak memory of all methods, measured under matched conditions (the same type of 128-thread CPU node, the same corpora and the same budgets), together with plots of the compression ratio of our Lagrangian relaxation as a function of wall-clock time against the baselines (Appendix L, summarized in Section 6.2). Since our method is an anytime algorithm, the more informative comparison is its compression as a function of time: for example, at k = 25K, LRX surpasses both BPE and GreedTok after about 15 minutes on UN and about 75 minutes on arXiv (excluding data loading). Moreover, vocabulary construction is an offline stage that is run only once, before training, whereas the shorter sequences it produces reduce the cost of every subsequent training run and inference call, so a longer construction time is much less of a limitation. Online encoding throughput is reported in the first answer above.

References

[1] Diao et al. CLIMB: Clustering-based Iterative Data Mixture Bootstrapping for Language Model Pre-training. arXiv:2504.13161, 2025.

[2] Tempus et al. Tokenisation via Convex Relaxations. arXiv:2605.22821, 2026.

[3] Kudo. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates. ACL, 2018.

[4] Schmidt et al. Tokenization Is More Than Compression. EMNLP, 2024.

We thank the reviewer again for their helpful review. As the discussion period ends soon, we wanted to kindly check whether our responses and additional experiments have addressed the reviewer’s concerns. We would be happy to clarify anything further.

Reviewer_N7jYOpenReview ↗
Rating
3
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper builds on recent work that has formulated tokenization as an integer linear programming problem. This paper extends the previous work by using Lagrangian relaxation - a textbook method for solving large linear/convex programming. In the context of this paper, the Lagrangian relaxation produces provably correct upper and lower bounds on the optimal solution. These bounds may never meet, so the algorithm is technically a heuristic; it does not solve every ILP because it relaxes the integrality constraints.

Critical strengths

S1. The approach is clean and straightforward. The Lagrangian for the tokenization problem decomposes cleanly into independent, shortest-path problems on segmentation lattices plus a top-k selection. This is simple to implement, highly parallelizable, and scalable to large corpora. [That said, I'm surprised the earlier papers didn't use Lagrangian relaxation immediately, since it came to mind when I first saw the ConvexTok and Lim et al. (2025) papers.]

S2. Upper and lower bounds seem valuable. Moreover, these same bounds can be used to relate the suboptimality of other vocabulary selection methods, meaning they are valuable for evaluating future methods produced by the tokenization community.

Critical weaknesses

W1. The downstream evaluation claims are only weakly supported. In Table 3, the arXiv and UN differences are within one standard deviation, so the evidence supports "it doesn't hurt" rather than "improvement." A statistical significance test should be able to clear this up.

W2. The theoretical contribution is modest. The main theoretical results are standard weak-duality and decomposition arguments. That’s fine for an algorithmic paper, but the contribution is mainly an encoding and an empirical one.

W3. The most crucial comparison missing is to ConvexTok (Tempus et al. 2026, "Tokenisation via Convex Relaxations"). This paper and ConvexTok use the exact same ILP formulation. And both methods solve the linear programming relaxation of this ILP, but use different techniques to do it. ConvexTok solves the LP relaxation at scale, rounds it to a vocabulary, and reports a certified lower bound showing their tokenizer within about 1% of optimal at common vocabulary sizes. It is critical that the authors discuss ConvexTok explicitly and clarify which contributions are new relative to it. Additionally, running a comparison of the methods. The ConvexTok code appears to be available on GitHub. All that said, I think that the Lagrangian relaxation approach is likely to scale to much larger datasets, but what I don't know is if the empirical gaps and solution quality are affected by the difference in how the methods solve their common optimization problem.

W4. It would be nice to see other baselines like PathPiece (Schmidt et al., 2024) and UnigramLM (Kudo, 2018).

W5. It would be great to get wall-clock times for all methods and baselines.

Questions for authors

Do all methods use the same pretokenizer? Can you experiment with multiple pretokenizers?

Do the optimality gaps vary with data size, vocab size, data type (e.g., code vs English vs German vs Chinese)?

5 comments

We thank the reviewer for their helpful and constructive feedback and for acknowledging the importance of our work. Following the reviewer's comments, we have added significance tests for the language-modeling results (Appendix N), the running time of all methods together with their compression as a function of wall-clock time (Appendix L), a formal and empirical comparison with ConvexTok (Appendix K), a UnigramLM baseline (Appendix M), an extended pretokenization ablation (Appendix H), and an analysis of the optimality gap across data size, vocabulary size and data type (Appendix O). In addition, we have obtained exact MIP results beyond WikiText (Appendix P), which further support our answers. We have also summarized the main results in the relevant sections of the main text, and summarize the additions below.

Statistical significance of the language-modeling results

We agree with the reviewer's reading of Table 3, and have added significance tests for all language-modeling results (Appendix N). We would also like to clarify the goal of these experiments, which we now state more explicitly in Section 6.3. Our claim is not that our Lagrangian relaxation (LRX) yields a significantly better BPB, although it does attain a slightly better mean BPB in most settings. Rather, our claim is that its substantially better and certifiably near-optimal compression, which shortens sequences and can thereby improve aspects such as the number of decoding steps and the KV-cache memory at inference, does not come at the expense of language-modeling quality. To test this, we compared our method with each baseline at every checkpoint using a two-sided Welch's t-test over the five seeds, at a significance level of 0.05.

On WikiText, the BPB improvement is statistically significant. Against BPE, it is significant at every checkpoint (p ≤ 0.002), amounting to about 0.06 BPB at the end of training. Against GreedTok, LRX has the lower mean at every checkpoint; the difference is significant at 50% of training (p = 0.043) and borderline at 75% and 100% (p = 0.051 and 0.055), so LRX is better, but only marginally. On arXiv and UN, all three tokenizers are on par, and none of the differences is significant (p ≥ 0.37).

We also ran a larger-scale experiment with a 109M-parameter GPT-2 model (context 1,024) on ClimbMix, described in our response to Reviewer TaUt (Appendix N; last row of the table below). There, our method again attains the lowest mean BPB at every checkpoint. With three seeds, the differences are not statistically significant, but the p-value against BPE decreases steadily during training, reaching 0.076 at the end, close to the 0.05 threshold. Taken together, our substantially better compression does not come at the expense of language-modeling quality, and in some cases it even improves it.

Corpus25% of training50%75%100%
arXiv0.51 / 0.460.58 / 0.540.69 / 0.640.95 / 0.76
WikiText0.0019 / 0.110.0007 / 0.0430.0008 / 0.0510.0006 / 0.055
UN0.37 / 0.9950.61 / 0.970.48 / 0.820.52 / 0.76
ClimbMix (109M)0.15 / 0.760.14 / 0.580.081 / 0.250.076 / 0.27

Each cell gives the p-value of LRX against BPE / against GreedTok, from two-sided Welch's t-tests: 22M-parameter models with five seeds on arXiv, WikiText and UN, and a 109M-parameter GPT-2 model with three seeds on ClimbMix.

We thank the reviewer for this suggestion, which helps us state the scope of the language-modeling results more precisely.

Theoretical vs. algorithmic contribution

We agree with the reviewer that this is mainly an algorithmic paper and that the underlying optimization techniques are known. We would, however, like to clarify where we see its contribution: in a formulation under which these techniques become effective for tokenization, and in what this enables. Our flow-based encoding reduces the MIP from Θ(∑w∣w∣⋅∣T∣)\Theta(\sum_{w}|w|\cdot|\mathcal{T}|) to Θ(∑w∣w∣2)\Theta(\sum_{w}|w|^2) variables and constraints (Propositions 1 and 3), and both of our methods build on it. First, it makes exact solving feasible on instances where the previous formulation runs out of memory (Appendix P). Second, its Lagrangian relaxation decomposes into independent shortest-path problems, one per word, which run in parallel and scale to corpora with billions of words. As the reviewer notes (S2), the resulting certified bounds also make it possible to measure how far any tokenizer is from optimal. For example, they show that GreedTok is within 1.05–2.42% of the optimum on PubMed, and that at k=25k = 25K our vocabularies are within 0.09–1.56% of the optimum across the three datasets. To the best of our knowledge, no previous method provides such certificates at this scale. We view these capabilities, rather than the techniques themselves, as the main contribution of the paper.

Relation to ConvexTok [1]

We thank the reviewer for pointing us to this important recent work, which we were not aware of. We have added ConvexTok to the Related Work section and a detailed comparison in Appendix K. In the final version, we will expand this comparison and add it to the main text. ConvexTok was uploaded to arXiv a few months before the ICLR submission deadline and was developed concurrently with and independently of ours. Although ICLR's guidelines do not require comparisons with concurrent arXiv preprints, we fully agree with the reviewer that a discussion and a direct comparison are highly valuable.

The reviewer is right that both works start from a common path-based integer program and derive lower bounds on its optimal value, but they do so using different techniques. Overall, the two methods differ in three respects. (i) We additionally solve the exact integer program itself with Gurobi, which provably certifies the true optimum (Section 4 and Appendix P). (ii) Rather than solving the full LP, we decompose the problem into independent shortest-path problems, one per word, so the corpus graph can be split into segments that are processed in parallel. This makes our method highly parallelizable and substantially more scalable. It is also an anytime algorithm: every iteration yields both a valid lower bound and a feasible vocabulary, so it can be stopped at any point with a certified optimality gap. (iii) We construct vocabularies from the Lagrangian iterates rather than by rounding an LP solution, which yields different vocabularies, and hence different compression.

Regarding scalability, our method is indeed designed to scale substantially better, mainly because it requires far less memory. Since each segment of the corpus graph holds only its own part of the graph in memory, the segments can also be processed sequentially. ConvexTok's first-order LP solver does not allow this: it multiplies by the full constraint matrix at every iteration, so the entire LP must reside in memory at once. To test this empirically, we ran ConvexTok's public code on arXiv and PubMed, the two largest datasets in our study, under the same configuration as our method (the same machines and memory allocation). In both cases, ConvexTok failed with an out-of-memory error while building its LP, before its solver even started. This shows that ConvexTok does not scale to the larger settings in our study, whereas our method runs on all of them.

To compare the compression of the two methods, we evaluated both on WikiText, a smaller-scale corpus that allowed us to carry out a rigorous comparison within the rebuttal period, across several corpus sizes (slices of 2%, 10% and 20%) and vocabulary sizes (k = 500 to 8,000), to evaluate how both affect the comparison (Appendix K):

SlicekConvexTokLRX (ours)LRX vs. ConvexTok
2%5002.03382.0141−0.97%
2%1,0001.63671.6290−0.47%
2%2,0001.26971.2661−0.29%
10%5002.17952.1762−0.15%
10%1,0001.87751.8308−2.49%
10%2,0001.54231.5393−0.20%
10%5,0001.22121.2292+0.66%
10%8,0001.10601.1090+0.27%
20%5002.24942.1948−2.42%
20%1,0001.90241.8798−1.19%
20%2,0001.66401.5861−4.68%

The table reports the compression ratio (tokens per word; lower is better), with the better of ConvexTok and LRX in bold, and the last column gives LRX's token count relative to ConvexTok's (negative means LRX is better). LRX's vocabulary compresses better than ConvexTok's on 9 of the 11 instances, by up to 4.7%, while ConvexTok is better on the remaining two, both on the 10% slice at k ≥ 5,000, by at most 0.7%. Although our method compresses better in most cases in this setting, we consider its main advantage over ConvexTok to be scalability, which allows it to handle much larger datasets.

Wall-clock time for all methods

We have added the running time and peak memory of all methods, measured on the same type of machine, together with plots of the compression ratio of our Lagrangian relaxation as a function of wall-clock time against the baselines (Appendix L), and summarize them in Section 6.2. Since our method is an anytime algorithm, the more informative comparison is its compression as a function of time: for example, at k = 25K, LRX surpasses both BPE and GreedTok after about 15 minutes on UN and about 75 minutes on arXiv (excluding data loading). Moreover, vocabulary construction is an offline stage that is run only once, before training, whereas the shorter sequences it produces reduce the cost of every subsequent training run and inference call, so a longer construction time is much less of a limitation. The running time and peak memory of all methods, and the plots for every dataset and budget, appear in Appendix L.

PathPiece and UnigramLM baselines

As suggested, we have added UnigramLM [2] as a baseline (Appendix M, summarized in Section 6.2). Regarding PathPiece [3], its core algorithm is an online segmentation algorithm that encodes text with a given vocabulary into the minimum number of tokens, so it is complementary to our method, which selects the vocabulary itself. In fact, our DP encoding is exactly PathPiece's segmentation, and the paper already compares this combination with other pairings of vocabularies and encoders (Appendices E and G), where the improvements of our method carry over.

UnigramLM, in contrast, constructs a vocabulary and is directly comparable. We trained it with SentencePiece's default settings on the same byte-level word counts as the other methods, with the same vocabulary size, and evaluated it with its native Viterbi encoding. The compression ratio (tokens per word; lower is better) at k = 25K is below; Appendix M reports k = 10K–40K.

DatasetBPEUnigramLMGreedTokLRX (ours)Certified LB
arXiv1.17901.17731.16941.16571.1589
UN1.02351.16461.01741.01511.0142
PubMed1.14811.39871.12491.12211.1049

LRX achieves the lowest compression ratio at every vocabulary size on all three datasets. UnigramLM compresses worse than BPE on UN and PubMed, in line with prior findings [3], and slightly better than BPE on arXiv at most budgets. As in the other methods, all 256 bytes are kept in its vocabulary; plain SentencePiece differs by at most 0.003.

Do all methods use the same pretokenizer, and how do results change with other pretokenizers?

Regarding the first question: yes. In all our main experiments, all methods operate on the same set of words W\mathcal{W}, obtained by splitting on whitespace into UTF-8 byte strings (Section 6), and use the same 256 singleton bytes.

For the second question, we have extended our pretokenization ablation to several vocabulary sizes (Appendix H, summarized in Section 6.2), comparing GreedTok and LRX on UN under the BERT and the regex-based GPT-2 pretokenizers. Each pretokenizer yields a different set of words, and both methods are run on the same words. The compression ratio (lower is better) is below. Since all pretokenizers cover the same text, we normalize every row by the same number of whitespace-delimited words, so the reported values are proportional to the total number of tokens and are directly comparable.

PretokenizerkGreedTokLRX (ours)
BERT20K1.33671.3291
BERT25K1.32361.3178
BERT30K1.31481.3105
GPT-2 regex20K1.30741.2997
GPT-2 regex25K1.29401.2880
GPT-2 regex30K1.28511.2808

LRX compresses better than GreedTok under both pretokenizers and at every vocabulary size, by 0.33–0.57% with BERT and 0.34–0.59% with GPT-2 regex. As with whitespace pretokenization, the improvement narrows as k grows, and it is in fact larger than under whitespace pretokenization on the same corpus. The advantage of our method is therefore not specific to whitespace pretokenization.

Do the optimality gaps vary with data size, vocabulary size, and data type?

We thank the reviewer for suggesting this analysis, which we have added in Appendix O. On WikiText slices of 2%, 10% and 20% of the corpus, the certified gap of our Lagrangian relaxation shrinks as k grows beyond 1,000 and grows mildly with corpus size at a fixed k. The same trends hold on the paper's datasets: at k = 25K, the certified gap of LRX is 0.09% on UN, 0.59% on arXiv and 1.56% on PubMed, growing with the size and diversity of the corpus, and it generally shrinks as k grows on every dataset (Figure 6).

For data type, we evaluated BPE, GreedTok and LRX on Korean and Japanese Wikipedia, to vary the language and script. These corpora use multi-byte UTF-8 characters, and Japanese does not separate words by whitespace. Due to the time constraints of the rebuttal period, we used random subsets of each corpus at the scale of UN (about 55K distinct words each, with their frequencies). The compression ratio (tokens per word; lower is better) at k = 10K is:

CorpusBPEGreedTokLRX (ours)LRX lower bound
Korean1.55541.39361.36821.3603
Japanese1.08321.05981.05451.0487

LRX improves on BPE by 12.0% on Korean and 2.7% on Japanese, and on GreedTok by 1.8% and 0.5%, closing 76% and 48% of GreedTok's certified gap, respectively. On both languages, the certified gap of LRX is below 0.6%.

References

[1] Tempus et al. Tokenisation via Convex Relaxations. arXiv:2605.22821, 2026.

[2] Kudo. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates. ACL, 2018.

[3] Schmidt et al. Tokenization Is More Than Compression. EMNLP, 2024.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.