Your Daily Tokenizer Has Been 'Making Do' — ConvexTok Uses Convex Optimization to Prove It's Only 1% from Optimal
Imagine packing a suitcase for a business trip. BPE is like an impatient packer: it grabs whatever items most frequently appear together, stuffs them into a bag, and keeps going until it's full. Whether the suitcase ends up optimally packed? It doesn't care — it only looks one step ahead.
That's how all current mainstream tokenizers (BPE, Unigram) work: greedy algorithms, locally optimal, globally left to chance. A team from ETH Zurich asks: can we use mathematical programming to find the globally optimal tokenization?
Tokenization: The Most Underrated Stage of the NLP Pipeline
The tokenizer is the first gate for every language model: it splits your text into tokens before the model can process anything. How well it splits directly determines how clearly the model 'sees' the world.
But tokenization is fundamentally NP-hard — finding the best segmentation among all possibilities takes exponential computation. So everyone has settled for greedy algorithms, with BPE as 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' when 'un' alone 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 (IP), then relax it into a Linear Program (LP).
Each variable is a 0/1 choice of whether to include a token — that's integer programming, which is hard to solve. ConvexTok relaxes the constraint: variables can take any value between 0 and 1 (e.g., 0.7), turning the problem into an LP that mature solvers can handle efficiently.
Relaxed solutions may contain 'half-selected' tokens (e.g., a token chosen at 0.7), which aren't meaningful in practice. ConvexTok therefore proposes three rounding schemes:
- Det (deterministic rounding): straightforward thresholding — simple and blunt
- Bias (biased rounding): weighted randomized rounding based on fractional values, preserving more information
- Top-k: keep the k highest-scored tokens
- Compression rate: the Bias rounding scheme beats BPE at all vocabulary sizes
- Vocabulary utilization: ConvexTok uses the vocabulary more efficiently, with less waste
- Rényi entropy: also superior on this information-theoretic metric
After rounding, building a complete tokenizer from the LP solution follows naturally.
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 do better), it can be used to certify how far existing tokenizers are from optimal.
The results are striking: at common vocabulary sizes, both BPE and ConvexTok are less than 1% worse than the theoretical optimum! This means that in terms of compression rate, the room for improvement in tokenization is actually quite small.
But don't rush to conclude 'BPE is good enough' — ConvexTok still leads across several intrinsic metrics:
Downstream Results: Improved but Inconsistent
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 fluctuates — sometimes clearly ahead, sometimes roughly on par.
This isn't contradictory. Tokenizers optimize compression, and the relationship between compression and downstream performance isn't strictly linear. A better-compressing tokenizer may split some semantic boundaries too finely, interfering 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 greedy limitations; convex optimization gives us a global view 2. We can certify optimality: LP lower bounds let us say, for the first time, 'this tokenizer is X% from optimal' rather than just 'this one beats that one' 3. The tokenizer ceiling may be near: the 1% gap means future breakthroughs in compression may require a different optimization objective
It's like GPS navigation — before, we could only follow one road to the end; now we have a global map that not only finds better routes but also tells you 'this road is already 99% optimal.'
---
Paper: Tokenisation via Convex Relaxations
Open-source code: github.com/JanTempus/tokenisation_lp