acceptodds
Under review as a conference paper at ICLR 2027

Tokenisation via Convex Relaxations

11 views

Abstract

Tokenisation is an integral part of the current NLP pipeline. Current tokenisation algorithms such as BPE and UnigramLM are greedy: they make locally optimal decisions without considering the resulting vocabulary as a whole. We instead formulate tokeniser construction as an integer program which we approximate using convex optimisation tools, yielding a new algorithm we call ConvTok. We find that ConvTok consistently improves intrinsic tokenisation metrics and the bits-per-byte achieved by language models in English; downstream performance metrics and multilingual language modelling, however, show no consistent pattern. Furthermore, ConvTok allows the user to upper bound how far any tokeniser is from optimal (at a certain objective), and we empirically find ConvTok to be within 1% of optimal at common vocabulary sizes.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Tokenisation, Linear Programming, Natural Language Processing

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_eBguOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies tokenization from the perspective of graphs and linear programming. The authors process input strings as a graph, formulate compression-optimal vocabulary selection as an integer program, and relax it into a linear program followed by three rounding schemes (Det, Bias, Int) and PathPiece segmentation to obtain a discrete tokenizer.

Critical strengths

I think the idea is interesting. Combining graphs, a integer program, and a linear program offers a new perspective on tokenizer construction, where the linear program yields a lower bound on the optimal compression.

Critical weaknesses
  1. The presentation is not very good and is hard to follow. The framework is complicated, translating tokenization from strings to coloured graphs, then to incidence-matrix network flows in an IP and finally to an LP relaxation with rounding. A clear high-level overview and pipeline diagram of the algorithm are necessary. In addition, critical implementation steps that make the LP solvable on a 700 MB corpus are omitted.

  2. I feel this is a critical flaw of the framework, and the authors overclaim their contribution. The method relies entirely on PathPiece, an existing string-level shortest-path algorithm. Furthermore, because the corpus is pretokenised into regex chunks and priced edges in Eq. (2c) never cross string boundaries, the shortest-path problem itself decomposes strictly at the local string/pretoken level rather than globally across the corpus. This contradicts the "globally optimal" claim that the authors make as their major contribution. (Please correct me if I misunderstood this as I interpreted this from footnote #4). Meanwhile, claiming BPE makes "locally optimal" decisions is technically wrong. BPE actually collects statistics and counts token-pair frequencies globally across the entire corpus. It is greedy in search order, not "local" in data scope. I think this is the reason that why BPE is already within < 1% of the LP lower bound at standard vocabulary sizes.

Questions for authors

Please refer to Weaknesses

3 comments

We would like to start by thanking the reviewer for their feedback. We would like to respectfully push back on the reviewer’s score, though. The reviewer points out two weaknesses with our paper:

  • Paper is hard to follow. We agree that the methodology we present is not trivial to understand, as it requires knowledge of techniques that are not common in the machine learning community (e.g., linear programming). We, however, put a lot of effort into trying to simplify the presentation as best as we could and believe that we converged to a good solution which is at the same time formal and accurate, but as accessible as possible. We would be happy to further improve our paper’s presentation if the reviewer has concrete suggestions, but we believe that the paper will still be complex due to its use of techniques which are not the default of the ML community.
  • Authors overclaim their contribution. We believe that this point mostly comes from a misunderstanding regarding what we claim. We appreciate the reviewer highlighting this potential source of confusion in our paper, which we will make sure to clarify (see details below).

On the other hand, the reviewer highlights as strengths that:

the idea is interesting. Combining graphs, a integer program, and a linear program offers a new perspective on tokenizer construction, where the linear program yields a lower bound on the optimal compression.

Given these strengths, and that one of the weaknesses pointed out (overclaim) is a misunderstanding (which we will make sure to clarify), and the other (hard to follow) is an inherent property of the novelty of our approach, we believe that our paper is worth acceptance at ICLR. We thus respectfully ask the reviewer to reconsider their score.

We respond to the reviewer’s points in detail below.

W1. (Part 1.) The presentation is not very good and is hard to follow. The framework is complicated, translating tokenization from strings to coloured graphs, then to incidence-matrix network flows in an IP and finally to an LP relaxation with rounding. A clear high-level overview and pipeline diagram of the algorithm are necessary.

See above. We appreciate the reviewer’s suggestion to add a high-level overview diagram to our paper, though, and we will do so.

W1. (Part 2.) In addition, critical implementation steps that make the LP solvable on a 700 MB corpus are omitted.

We respectfully request a more concrete suggestion here so we can clarify this point, as it is not clear to us which steps are missing. Our pipeline is:

Read in text (700MB) -> Pretokenise -> Group pretokens and reweight their edges -> Build the graph -> Build the LP -> Solve the LP with PDLP from CUOPT using the default settings -> Round the solution.

W2. (Part 1.) I feel this is a critical flaw of the framework, and the authors overclaim their contribution. The method relies entirely on PathPiece, an existing string-level shortest-path algorithm. Furthermore, because the corpus is pretokenised into regex chunks and priced edges in Eq. (2c) never cross string boundaries, the shortest-path problem itself decomposes strictly at the local string/pretoken level rather than globally across the corpus. This contradicts the "globally optimal" claim that the authors make as their major contribution. (Please correct me if I misunderstood this as I interpreted this from footnote #4).

We believe there may indeed be a misunderstanding. Tokenisation is unfortunately an ambiguous term as within the same field it refers simultaneously to two things:

  • Tokeniser training. The process of, given some dataset, selecting a set of byte-strings to compose the model’s vocabulary.
  • Tokeniser inference. The process of, given a vocabulary, segmenting a dataset.

The key difference is that the first step (training) is NP-hard even for compression, while the second step (inference) is simply a shortest path problem. Notably, PathPiece is also an ambiguous term, as there are two PathPiece methods:

  • PathPiece Training. A method similar to UnigramLM for tokeniser training. This method starts with a large seed vocabulary and greedily trims it by iteratively deleting the tokens which will hurt compression the least.
  • PathPiece Inference. A method for tokeniser inference, and the default use of the term “PathPiece.” This is a shortest path method which, given a vocabulary, segments a sentence/dataset optimally for compression.

In our paper, PathPiece always refers to the latter (inference) method. Notably, as the reviewer notes, PathPiece Inference solves the tokenisation inference step directly and optimally. PathPiece Training, however, is a greedy (local-in-the-search-procedure) approach for finding a tokeniser. Our paper is the first to reformulate the tokeniser training step as a graph problem, as well as the first to solve it using linear programming (globally-in-the-search-procedure). See the answer to reviewer iVVv for a longer comparison to prior methods.

After using ConvexTok to select a vocabulary, we indeed use PathPiece Inference to apply it optimally to new strings; this is what footnote 4 refers to.

W2. (Part 2.) Meanwhile, claiming BPE makes "locally optimal" decisions is technically wrong. BPE actually collects statistics and counts token-pair frequencies globally across the entire corpus. It is greedy in search order, not "local" in data scope.

We again apologise for the confusion. Indeed, our intention with using the words “globally” and “locally” optimal was with respect to the search order, not the data scope. We agree that BPE is global in data scope. However, in terms of search order, it only scores tokens locally (by evaluating how much the given token improves the objective locally). Our linear programming approach, however, scores tokens globally (by evaluating how much this token improves the objective, jointly considering all other tokens and whether or not they are chosen). ConvexTok is thus global in both data and search scope.

W2. (Part 3.) I think this is the reason that why BPE is already within < 1% of the LP lower bound at standard vocabulary sizes.

Given the considerations above, we argue that the reason why BPE is so close to optimal actually remains a bit of a mystery. In fact, Kozma and Voderholzer (2024) show that there are datasets where it achieves arbitrarily bad compression.

References

Kozma and Voderholzer, Theoretical Analysis of Byte-Pair Encoding in arXiv 2024

Reviewer_eBguOpenReview ↗

Thank you for your feedback

Thank you for your clarification. Unfortunately, addressing these concerns requires substantial restructuring of the paper. Therefore, I have to keep my scores.

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

The paper formulates the construction of compression-optimal tokenizers as a problem on a directed acyclic graph. The goal is to minimize the total token count on a pretokenised corpus D given a vocabulary budget K. In the graph, vertices are byte positions, free edges are single bytes and priced edges are candidate multi-byte substrings, colored by the substring they represent. Thus building a tokenizer is a colour-budgeted shortest-path problem. We run experiments on English (ClimbMix) and multilingual data (FineWeb/FineWeb2) for K from 8k to 256k. The evaluation includes intrinsic metrics, vocabulary stability (Jaccard) and nanochat LMs at depths 12/18/24 with 3 seeds, scored on BpB and CORE. Also considered is a morphology/UTF-8 penalized objective.

Critical strengths
  1. The graph -> IP -> LP construction is well motivated, and Observations 3.3 and 3.4 give an exact correspondence between feasible IP points and tokenisers.
  2. The following tokenizers: BPE, UnigramLM and PathPiece are from optimal compression on real corpora that is useful to the field. Compression saturation is a valuable point.
  3. Experiments on the six vocabulary sizes, three depths, and three seeds. Language model hyperparameter tuning on BPE-32k, which favours the baseline.
Critical weaknesses
  1. ConvexTok and Freq segment with shortest path, while BPE applies merges in order. The paper lacks the obvious ablation: BPE’s vocabulary with shortest-path inference, and ConvexTok’s vocabulary with greedy or merge-like inference.
  2. The claim that ConvexTok “consistently outperform[s] BPE in BpB at ≥32k” is contradicted by Table 6.
  3. Neither information nor analysis is given of how the Det and BPE vocabularies differ at equal K, such as Jaccard overlap, length distributions, or frequency ranks.
  4. The multilingual LP value is about 9.2M tokens, roughly 40× smaller than English. This implies only tens of MB of multilingual training text, contradicting the statement that all tokenisers were trained on 593,920 documents.
Questions for authors
  1. Was Epric was grid searched in any experiment (by frequency, maximum length, or boundaries)?
  2. Was LM training matched on tokens or on bytes? How many bytes did each run see?
  3. What are the results for BPE’s vocabulary with shortest-path inference, and for ConvexTok’s vocabulary with greedy/merge-style inference?
2 comments

We would like to start by thanking the reviewer for their feedback, and to say we appreciate the time the reviewer has put into the report. We believe most of the criticisms pointed out above are due to slight ambiguities or oversights in our presentation, which should be easily fixable for publication. We thank the reviewer for highlighting these issues. We argue that one of the critiques, however, would be highly non-trivial to implement and thus constitute follow-up work. We hope our answers below will satisfy the reviewer.

W1. ConvexTok and Freq segment with shortest path, while BPE applies merges in order. The paper lacks the obvious ablation: BPE’s vocabulary with shortest-path inference, and ConvexTok’s vocabulary with greedy or merge-like inference.

We agree with the reviewer that these ablations are important. In fact, the baseline labeled as “PathPiece’’ in our tables is exactly BPE’s vocabulary with shortest-path inference. We would like to apologize for this not being clear in our original manuscript, and we will clarify it accordingly.

We also agree that ConvexTok’s vocabulary with a sequential merge-like inference would be very interesting. This, however, would require non-trivial implementation changes. The core issue is that our integer program does not consider token orderings—always applying them optimally to any string—and it would require non-trivial changes to add this constraint.

W2. The claim that ConvexTok “consistently outperform[s] BPE in BpB at ≥32k” is contradicted by Table 6.

We agree that ConvexTok did not always outperform BPE; ConvexTok with the Det rounding scheme outperforms BPE in 11 out of 12 settings, and with Bias rounding in 8 out of 12 settings. We used the term “consistently" to mean “in the majority of cases,” but we see that this is not adequate. We will thus qualify this claim appropriately, changing it to refer more specifically to Det, which does win in 11/12 cases. Furthermore, since submission, we extended our experiments using the morphology-aware objective (referred to as MorphDet and Morphbias in the paper) to other model and vocabulary sizes. The MorphDet variant of ConvexTok (with morphology-aware objective and deterministic rounding) outperforms BPE, PathPiece, and UnigramLM on BpB for all vocabulary sizes and depths studied.

W3. Neither information nor analysis is given of how the Det and BPE vocabularies differ at equal K, such as Jaccard overlap, length distributions, or frequency ranks.

We present these results here.

Jaccard overlap between the Det and BPE vocabularies. This is presented in the table below. In this table, we see that the similarity is relatively uniform across vocabulary sizes, fluctuating between 55% and 70%. Note as well that for the largest vocabularies, the Jaccard similarity here between BPE and Det is often larger than the ones presented in our Figure 4 (between Det and Det or BPE and BPE); this is because the similarities here are taken between two different tokenisers trained on the same data (and towards the same compression objective), while in that figure similarities are between the same tokeniser on different data. This implies that, for larger vocabularies, the choice of data seems to matter more than the choice of tokenisation algorithm, while for smaller vocabularies, the opposite is true. We will add these results, as well as the Jaccard similarities between different tokenisers trained on different datasets to our manuscript (the latter has not yet been computed, since it requires retraining more of our tokenisers).

Jaccard similarity between Det and BPE vocabularies. Columns represent vocabulary sizes, while rows represent sample sizes. Values represent the mean and standard deviation across 5 different non-overlapping samples of data from ClimbMix.

ss \ vocab8,19216,38432,76865,536131,072262,144
8,1920.5528 (± 0.0013)0.5827 (± 0.0020)0.6023 (± 0.0026)0.6066 (± 0.0013)0.5747 (± 0.0048)0.3642 (± 0.0029)
16,3840.5551 (± 0.0029)0.5854 (± 0.0018)0.6152 (± 0.0022)0.6270 (± 0.0025)0.6285 (± 0.0037)0.4600 (± 0.0029)
32,7680.5546 (± 0.0011)0.5893 (± 0.0027)0.6236 (± 0.0015)0.6439 (± 0.0018)0.6465 (± 0.0019)0.6129 (± 0.0035)
65,5360.5565 (± 0.0017)0.5907 (± 0.0019)0.6297 (± 0.0012)0.6602 (± 0.0021)0.6762 (± 0.0029)0.6339 (± 0.0009)

Length distributions. This is presented in the table below. ConvexTok, on average, selects longer tokens. This is sensible, as ConvexTok does not require intermediate tokens to produce longer ones.

Distribution over lengths of Det and BPE vocabularies. Main values in columns represent the average length, and one standard deviation is presented in parentheses.

Vocab SizeBPEDet
8,1925.53 (±2.63)6.07 (±3.03)
16,3846.12 (±2.75)6.64 (±3.02)
32,7686.54 (±2.84)7.03 (±3.05)
65,5366.85 (±2.93)7.36 (±3.20)
131,0727.09 (±3.04)7.65 (±3.32)
262,1447.23 (±3.17)7.92 (±3.29)

Frequency ranks. We do not fully understand what the reviewer meant by the frequency ranks. Could you clarify? We do have the Avg Token Rank of our tokenisers in Tables 4 and 5, defined as the average frequency rank (i.e., the rank of a token when ordered by raw frequency in the corpus) of the tokens used to encode a specific corpus.

W4. The multilingual LP value is about 9.2M tokens, roughly 40× smaller than English. This implies only tens of MB of multilingual training text, contradicting the statement that all tokenisers were trained on 593,920 documents.

We would like to apologize for this oversight from our side. Indeed, the correct statement should be: all English-only tokenisers were trained on 593,920 documents, while multilingual tokenisers were trained on 8,000 documents instead. We restricted the number of documents used in the multilingual setting due to the existence of more unique pretokens in it, which required more memory to represent and solve the LP.

Q1. Was Epric was grid searched in any experiment (by frequency, maximum length, or boundaries)?

At no point did we use grid search. We also did not tune any of the hyper-parameters to train our models or tokenisers, training our LMs with the default hyper-parameters optimised in nanochat for BPE.

Q2. Was LM training matched on tokens or on bytes? How many bytes did each run see?

It was matched on the number of tokens per model depth. For each depth, we fixed the number of tokens used for training to be 10.5 times the number of parameters in our model with a vocabulary size of 32k (using the same number of training tokens for other vocabulary sizes). We used 10.5 as this was the recommendation in nanochat (Karpathy, 2025), whose developers ran scaling-laws experiments specifically for their language modelling architecture.

Q3. What are the results for BPE’s vocabulary with shortest-path inference, and for ConvexTok’s vocabulary with greedy/merge-style inference?

As mentioned above, BPE’s vocabulary with shortest-path inference can be seen throughout the paper under the name PathPiece; we did not run experiments with ConvexTok using greedy/merge-style as they would be non-trivial to design.

References

  • Karpathy, nanochat: The best ChatGPT that $100 can buy in Github 2025
Reviewer_iVVvOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper addresses the problem of tokenization, proposing a new approach, ConvexTok, that formulates tokenization with a compression objective as an integer programming problem, which is then approximated using linear programming and rounding. The authors demonstrate that their approach improves the bits-per-byte (BpB) metric for language models trained on the English ClimbMix400B dataset, but does not show consistent improvements on the multilingual FineWeb/FineWeb2 dataset.

This paper addresses the problem of tokenization, proposing a new approach, ConvexTok, that formulates tokenization with a compression objective as an integer programming problem, which is then approximated using linear programming and rounding. The authors demonstrate that their approach improves the bits-per-byte (BpB) metric for language models trained on the English ClimbMix400B dataset, but does not show consistent improvements on the multilingual FineWeb/FineWeb2 dataset.

Critical strengths

The paper presents an optimization-based tokenization method that achieves statistically significant improvements in bits-per-byte (BpB) for English language models compared to established approaches such as BPE.

Critical weaknesses
  1. Insufficient discussion of related work and novelty

My main concern is the lack of a comprehensive related work section. While the paper references relevant studies throughout, it does not systematically discuss previous approaches and how the proposed method differs from them, making it difficult to assess its novelty.

Moreover, given the relatively modest empirical improvements in BpB, the absence of significant downstream gains, and the fact that existing methods already achieve near-optimal compression, a stronger literature review is needed to establish the importance of the problem and the significance of the proposed contribution.

  1. Limited evaluation across English datasets

The main positive empirical result is an improvement in BpB on ClimbMix400B. Although the authors evaluate multiple model depths and vocabulary sizes, all English experiments use the same dataset. Since the improvement does not consistently extend to the multilingual setting, I encourage the authors to evaluate several independent English datasets to establish whether the gains generalize.

Questions for authors
6 comments

We thank the reviewer for their time and their feedback on our paper. We appreciate both points raised by the reviewer: the need for a dedicated comparison with prior work, and the usefulness of experiments on an additional English dataset. Nonetheless, our paper offers a significantly novel way to perform tokenisation using convex programs, which is easily extendable and opens several avenues for future work. Our paper also performs a comprehensive battery of experiments with many hyperparameters, baselines, and in both an English and a multilingual setting. We hope that—given the new English experiments and the more detailed contextualisation of our contribution and its novelty below—our paper’s contributions will become clearer such that the reviewer can be confident to increase their score.

We respond to the reviewer’s points in more detail below.

W1. (Part 1) Insufficient discussion of related work and novelty

We appreciate this point. As the reviewer points out, while our paper already covers a lot of the related literature, it is missing a dedicated section specifically discussing how the proposed method differs from past approaches. We will add such a section to our paper for CR. More precisely, we intend to add the full section drafted in the comment block below to our paper (see below for full new section).

W1. (Part 2) given […] the fact that existing methods already achieve near-optimal compression, [...] [X] is needed to establish the importance of the problem and the significance of the proposed contribution.

We agree that existing tokenisers are close to compression-optimal at common vocabulary sizes. We respectfully note, however, that this is in itself one of our paper’s findings. As noted in our paper, finding compression-optimal tokenisers is NP-hard, and BPE can be arbitrarily far from optimal in the worst case (Kozma and Voderholzer, 2024). Before our paper, it was thus unknown whether room for improvement existed in practice. Our paper’s LP relaxation provides a lower bound on the objective, which allows us to show that compression is already saturated. In other words, our paper’s methodology is what allows one to know “that existing methods already achieve near-optimal compression.”

W2 Limited evaluation across English datasets

We also appreciate this point. We have now run experiments where we train 18-layers language models on FineWeb-Edu for: (i) BPE, PathPiece, and ConvexTok under both the Det and MorphDet variants (i.e., using the rounding scheme with either the compression or morphology-aware objectives); (ii) using vocabulary sizes of 32k, 64k, and 128k. As in our original experiments, the table below shows that ConvexTok variants still lead to the best bits-per-byte (BpB) for larger vocabularies (64k and 128k), while PathPiece gives the best results for 32k. On CORE, we find less of a pattern (again, as in our original experiments), with PathPiece dominating results on the smallest and largest vocabularies, but not on 64k. Beyond that, we also show below the integrality gap for the various tokenisers (i.e., the gap to the lower bound value achieved by the LP itself). In that table, we see that ConvexTok still presents the best compression throughout. We will extend these experiments to other vocabulary sizes and baselines before publication.

TokeniserVocab sizeBits per byte ↓CORE ↑
BPE327680.80520.1947
Det327680.80500.2043
MorphDet327680.80490.1989
PathPiece327680.80480.2090
----------------------:----------------:-------:
BPE655360.79870.2037
PathPiece655360.79800.2115
Det655360.79790.2137
MorphDet655360.79780.2143
----------------------:----------------:-------:
BPE1310720.79480.2140
PathPiece1310720.79360.2188
Det1310720.79290.2145
MorphDet1310720.79280.2108
TokeniserVocab sizeLP ValueTokenised ValueRatio to optimal
BPE32768377,267,795382,760,002101.5%
PathPiece32768377,267,795381,201,068101.0%
MorphDet32768377,267,795377,650,867100.1%
Det32768377,267,795377,542,662100.1%
----------------------:------------:----------------:-----------------:
BPE65536363,662,375366,718,710100.8%
PathPiece65536363,662,375365,718,212100.6%
MorphDet65536363,662,375363,803,242100.0%
Det65536363,662,375363,729,190100.0%
----------------------:------------:----------------:-----------------:
BPE131072355,914,902357,594,465100.5%
PathPiece131072355,914,902357,005,998100.3%
MorphDet131072355,914,902355,971,151100.0%
Det131072355,914,902355,937,472100.0%

As an aside, we note that we suspect ConvexTok performed less well in the multilingual setting than in English due to the smaller dataset we used to train these tokenisers; this was a restriction imposed by the memory requirements of training them, which are larger in the multilingual setting than in English due to the presence of more unique pretokens. We hope this limitation will be mitigated by future work; in fact, we know of two other teams of researchers who are already building on our approach to mitigate this issue.

We again thank the reviewer for their time and feedback.

AuthorsOpenReview ↗

New Comparison to Prior Methods Section

\section{Comparison to Prior Methods}

In this section we provide further details about how our method differs from previous tokenisation algorithms.

\paragraph{BPE and its variants.}
As described in Section 2.1, BPE—the method used in most modern LLMs—is a greedy algorithm: it starts from a small vocabulary $\mathcal{T}_0$, to which it iteratively adds new tokens $\mathcal{T}_{i+1} =  \mathcal{T}_i \cup \{\mathbf{t}_{{new}}\}$.
Importantly, this new token, $\mathbf{t}_{\mathtt{new}}$, is chosen based on which token will (locally) improve the objective the most when added to the current vocabulary $\mathcal{T}_i$.
This is a myopic search procedure which focuses on how a token is *locally* helpful, but not on how it will interact with future choices; further, once a suboptimal decision is made, the method is then stuck with it, and cannot change the selected tokens anymore.
Not surprisingly, Kozma and Voderholzer (2024) show that BPE can achieve arbitrarily bad compression values when compared to optimal solutions.
Notably, BPE’s optimisation operates under two constraints: (i) it creates new tokens by merging pairs of existing tokens, meaning that it requires ``intermediate tokens’’ to represent longer character sequences; and (ii) it applies its tokens to a dataset sequentially and in a fixed order.
Recent work tries to mitigate these two constraints.
For instance, one approach gets rid of the second constraint by taking a BPE-learned vocabulary and applying it optimally to tokenise a string (this method is termed PathPiece in Schmidt et al., 2024, and optimal pair encoding in Kozma and Voderholzer, 2024).
Other work, gets rid of the first constraint by allowing BPE to `unmerge’ tokens (Bauwens and Delobelle, 2024 ; Chizhov et al., 2024 ; Cognetta et al., 2024, Lian et al., 2025,)—thus letting it construct longer tokens and then release the unnecessary intermediary tokens.
Notably, when considering which token to add (or unmerge) to create the vocabulary, these works still only consider how this token will change the objective function locally.
ConvexTok thus differs from these works, as the LP solution forms a **globally** optimal “relaxed vocabulary” instead, jointly considering how all tokens interact within it (this optimal “relaxed’’ vocabulary then needs to be rounded into an approximately optimal actual vocabulary).

\paragraph{UnigramLM and its variants.}
Another popular approach to tokenisation is UnigramLM.
This algorithm operates in a manner inverse to BPE: it starts from a large seed vocabulary, and iteratively prunes tokens from it based on which will harm its optimised objective the least.\footnote{For a more detailed description, see (Meister, 2026).}
Similarly to BPE, however, UnigramLM’s pruning approach is greedy—again (locally) considering only the current vocabulary $\mathcal{T}_i$, but not considering how a pruning decision will interact with others in the long run.
Importantly, while UnigramLM was originally designed to optimise unigram log-likelihood, variants exist to handle compression (Yavuz et al., 2026 ; Schmidt et al., 2024).
As with BPE, ConvexTok thus differs from these methods in that its optimisation builds a vocabulary considering how tokens interact with one another.

\paragraph{Integer programming and tokenisation.}
The prior work closest to ours is Lim et al. (2025), who formulate tokenisation as a partition cover problem, for which they also define an integer program. Their integer program, however, descends from their partition cover view of the problem (and thus differs significantly from our program, which is derived from our tokenisation graph view). This makes their integer program significantly harder to solve than ours for any reasonably sized dataset, since it is much larger (in numbers of variables and constraints) and more complex (in number of types of constraints).
In fact, Lim et al. (2025) never actually solve this integer program themselves, instead using it simply to guide another greedy algorithm they propose (termed Greedtok), which greedily selects a vocabulary using a submodular-inspired search function with the requirements that the choices are subject to their integer program constraints.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.