ConvexTok: Convex Optimization Shows Tokenizers Like BPE Are Within 1% of Optimal

Forum topic · 小凯 · 2026-05-25

Summary

ConvexTok, developed by researchers at ETH Zurich, reformulates text tokenization as an integer program relaxed into a linear program, enabling global optimization of vocabulary selection instead of the greedy pairwise merges used by BPE and Unigram. The method proposes three rounding schemes—deterministic, bias-based, and top-k—to convert fractional LP solutions back into discrete token vocabularies. Because the LP relaxation provides a provable lower bound, ConvexTok can certify how far existing tokenizers are from the true optimum. Experiments show that at common vocabulary sizes, BPE and ConvexTok are both within 1% of the theoretical optimum for compression rate, suggesting limited headroom in that dimension. ConvexTok still outperforms BPE on compression, vocabulary utilization, and Rényi entropy, with the bias rounding scheme beating BPE across all vocabulary sizes; the deterministic scheme improves bits-per-byte downstream, though results on the CORE benchmark are mixed. Paper: arxiv.org/abs/2605.22821; code on GitHub.

Your Everyday Tokenizer Has Been 'Making Do' — ConvexTok Proves It's Within 1% of Optimal

Imagine packing a suitcase for a business trip. BPE works like an impatient packer: it grabs the most frequently co-occurring items, stuffs them into a bag, and keeps going until the bag is full. It never asks whether the whole suitcase is packed as compactly as possible — it only looks one step ahead.

That's how all mainstream tokenizers (BPE, Unigram) work: greedy algorithms delivering local optima, leaving the global outcome to chance. A team at ETH Zurich asked: can we use mathematical programming to find a globally optimal tokenization?

Tokenization: The Most Underrated Stage in the NLP Pipeline

The tokenizer is the first gate for every language model. How text is split into tokens directly determines how clearly the model sees the 'world'.

But finding the optimal segmentation among all possible splits is NP-hard — the search space grows exponentially. So everyone has settled for greedy heuristics. BPE is the classic example: repeatedly merge the most frequent token pair until the vocabulary reaches its target size.

The problem is that BPE's greedy strategy creates many 'intermediate tokens' — e.g., merging 'un' and 'able' into 'unable', even when 'un' may not be optimal. These unnecessary byproducts waste vocabulary space and hurt compression efficiency.

Turning Tokenization into a Math Problem

ConvexTok's core idea is elegant: formulate tokenization as an Integer Program, then relax it into a Linear Program.

In the integer program, each candidate token is either selected (1) or not (0). Integer programs are hard to solve, so ConvexTok relaxes the variables to take any value between 0 and 1 (e.g., 0.7), producing a linear program that mature solvers can handle efficiently.

The relaxed solution may contain 'half-selected' tokens, which don't exist in reality. ConvexTok therefore proposes three rounding schemes to turn fractional selections back into integers:

Det (deterministic rounding): simple rounding, straightforward
Bias (bias rounding): weighted random rounding based on fractional values, preserving more information
Top-k: keep the k tokens with the highest fractional values

After rounding, constructing a full tokenizer from the LP solution is straightforward.

Within 1% of Optimal — And We Can Prove It

This is ConvexTok's most exciting finding. Because the LP relaxation provides a lower bound (no tokenizer can beat it), we can use it to certify how far existing tokenizers are from optimal.

The experimental result is striking: at common vocabulary sizes, both BPE and ConvexTok are less than 1% worse than the theoretical optimum! On the compression-rate dimension, tokenization's remaining headroom is small.

But don't conclude 'BPE is good enough' — ConvexTok still leads across several intrinsic metrics:

Compression rate: the Bias rounding scheme beats BPE at all vocabulary sizes
Vocabulary utilization: ConvexTok wastes less of its vocabulary
Rényi entropy: better on this information-theoretic metric as well

Downstream Results: Progress, but Not Always Consistent

On downstream language-model tasks, the Det rounding scheme consistently beats BPE on bits-per-byte (BpB). But on the CORE benchmark, ConvexTok's performance is mixed — sometimes clearly ahead, sometimes comparable.

This isn't contradictory. Tokenizers optimize compression, and the relationship between compression and downstream performance isn't strictly linear. A higher-compression tokenizer may split certain semantic boundaries into finer pieces, which can interfere with model learning.

Why This Paper Matters

ConvexTok's significance goes beyond 'yet another better tokenizer'. It brings three conceptual upgrades:

1. Tokenization can be exactly optimized: we no longer have to accept the limits of greedy algorithms — convex optimization tools give us a global view 2. We can certify optimality: the LP lower bound lets us say, for the first time, 'this tokenizer is X% from optimal' instead of only 'this beats that' 3. The tokenizer ceiling may be near: a 1% gap means future breakthroughs in compression may require changing the optimization objective itself

It's like GPS navigation — before, we could only follow one road to the end; now we have a global map, and can both find better routes and tell you 'this road is already 99% optimal.'

---

Paper: Tokenisation via Convex Relaxations

Open-source code: github.com/JanTempus/tokenisation_lp