Your Daily Tokenizer Has Been 'Making Do' — ConvexTok Uses Convex Optimization to Prove It's Within 1% of Optimal
Imagine packing a suitcase for a business trip. A BPE tokenizer is like an impatient packer—it grabs whatever items most frequently appear together and stuffs them into a bag, repeating until the bag is full. Whether the suitcase ends up optimally packed? It doesn't care, because it only looks one step ahead.
That's how all mainstream tokenizers (BPE, Unigram) work: greedy algorithms aiming at local optima and leaving the global picture to chance. A team at ETH Zurich asks: can we use mathematical programming to find a globally optimal tokenization scheme?
Tokenization: The Most Underrated Step in the NLP Pipeline
The tokenizer is the first gate of every language model. It splits your input text into tokens before the model can process it, and how well it splits directly shapes the 'world' the model sees.
But finding the optimal segmentation among all possible splits is NP-hard—computationally exponential. So everyone settles for greedy algorithms, with BPE the typical example: repeatedly merge the most frequent token pair until the vocabulary reaches its target size.
The problem is that BPE's greedy strategy produces many 'intermediate tokens'—e.g., 'un' and 'able' get merged into 'unable', but 'un' itself may not be an optimal choice. 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 (LP).
In an integer program, variables must be 0 or 1 (select a token or not)—which is hard to solve. ConvexTok cleverly relaxes this by letting variables take any value between 0 and 1 (e.g., 0.7), turning it into an LP that mature solvers can solve efficiently and exactly.
The relaxed solution may contain 'fractional' tokens (a token selected at 0.7), which is meaningless in reality. So ConvexTok proposes three rounding schemes to convert fractional tokens back to integers:
- Det (deterministic rounding): straightforward rounding, simple and blunt
- Bias (biased rounding): weighted random rounding based on fractional values, preserving more information
- Top-k: keep the k tokens with the highest scores
- 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 better on this information-theoretic metric
After rounding, building 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 within 1% of the theoretical optimum! This means that on the compression dimension, tokenizers have very little room left to improve.
But don't conclude 'BPE is good enough' yet—ConvexTok still leads across multiple intrinsic metrics:
Downstream Performance: 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 is mixed—sometimes clearly ahead, sometimes on par.
This isn't contradictory. Tokenizers optimize compression, and the relationship between compression rate and downstream performance isn't strictly linear. A tokenizer with higher compression may fragment certain semantic boundaries in ways that interfere with model learning.
Why This Paper Matters
ConvexTok's significance goes beyond 'yet another better tokenizer'. It brings three cognitive upgrades:
1. Tokenization can be exactly optimized: we no longer need to accept greedy algorithms' limits—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 away from optimal' rather than just 'this one beats that one' 3. The tokenizer ceiling may already be reached: a 1% gap means future breakthroughs on 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 that not only finds better routes but tells you 'this road is already 99% optimal.'
---