- 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 variables and constraints. The paper introduces an alternative MIP formulation that uses 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
-
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.
-
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.
-
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.
-
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 . 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.
-
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, 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
-
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.
-
Is it possible to compare the BPB scores of LRX and GreedTok?
-
Why do you think the difference shown in Fig.6 are substantial?
6 comments
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).
| Dataset | Budgets k | Share of GreedTok's gap closed by LRX | Share of BPE's gap closed by LRX |
|---|---|---|---|
| UN | 10K, 15K, 20K, 25K, 30K | 47%, 57%, 64%, 72%, 67% | 80%, 85%, 88%, 90%, 89% |
| arXiv | 10K, 15K, 20K, 25K, 30K | 14%, 36%, 41%, 35%, 46% | 51%, 63%, 66%, 66%, 67% |
| PubMed | 20K, 25K, 30K, 35K, 40K | 4%, 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.
| Dataset | Documents | True optimum | LRX lower bound | LRX |
|---|---|---|---|---|
| arXiv | 50 | 1.5788 | 1.5765 (−0.15%) | 1.6241 (+2.87%) |
| arXiv | 100 | 1.8313 | 1.8200 (−0.62%) | 1.9115 (+4.38%) |
| arXiv | 200 | 1.9696–1.9733 | 1.9514 | 2.0577 |
| arXiv | 400 | 2.0064–2.0145 | 1.9896 | 2.0997 |
| arXiv | 800 | 2.0242–2.0556 | 2.0049 | 2.1092 |
| PubMed | 10 | 1.4702 | 1.4636 (−0.44%) | 1.5231 (+3.60%) |
| PubMed | 15 | 1.5574–1.5628 | 1.5499 | 1.5975 |
| PubMed | 25 | 1.7014–1.7095 | 1.6886 | 1.7813 |
| PubMed | 50 | 1.7762–1.8140 | 1.7612 | 1.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).
| Corpus | BPE | GreedTok | LRX (ours) |
|---|---|---|---|
| arXiv | 1.1691 ± .006 | 1.1719 ± .019 | 1.1687 ± .012 |
| WikiText | 2.0390 ± .019 | 1.9995 ± .014 | 1.9768 ± .018 |
| UN | 0.9647 ± .004 | 0.9613 ± .011 | 0.9630 ± .004 |
| ClimbMix (109M) | 1.1461 ± .003 | 1.1414 ± .003 | 1.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.
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 Gw takes O(∣w∣2) time, since Gw has O(∣w∣2) edges; aggregating the token scores sλ(t) and computing the subgradient take O(∣E∣); selecting the k highest-scoring tokens takes O(∣T∣) with linear-time selection; and the upper-bound paths take another O(∣E∣). Since ∣T∣≤∣E∣=Θ(∑w∣w∣2), one iteration costs Θ(∑w∣w∣2), and n iterations cost O(n⋅∑w∣w∣2). The sum ranges over distinct words only, since repeated words enter as frequency weights 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.