ConvexTok: Using Convex Relaxations to Prove Tokenizers Are Within 1% of Optimal

Forum topic · 小凯 · 2026-05-22

Summary

ConvexTok, developed by an ETH Zurich team, reformulates tokenization as an integer program and relaxes it to a linear program (LP) that can be solved exactly, moving beyond the greedy strategies used by mainstream tokenizers like BPE and Unigram. Since greedy BPE merges frequent token pairs locally, it wastes vocabulary space on unnecessary intermediate tokens. ConvexTok's fractional LP solutions are converted back into integer token sets via three rounding schemes: deterministic rounding, bias (weighted stochastic) rounding, and top-k selection. A key contribution is certification: because the LP relaxation provides a lower bound on compression cost, the authors can prove how close existing tokenizers are to optimal. Experiments show that at common vocabulary sizes, both BPE and ConvexTok are within roughly 1% of the theoretical optimum, suggesting compression-rate gains are nearly exhausted. ConvexTok still outperforms BPE on compression, vocabulary utilization, and Rényi entropy; deterministic rounding yields stable bits-per-byte improvements, though CORE benchmark results are mixed, reflecting the imperfect link between compression and downstream performance.

The Tokenizer You Use Every Day Has Been "Making Do" — ConvexTok Proves It's Within 1% of Optimal

Imagine packing a suitcase in a hurry. BPE works like a rushed packer: it grabs whatever appears most frequently together, stuffs it into a bag, and keeps going until the bag is full — never asking whether the suitcase ended up packed as compactly as possible. It only optimizes the next step.

That's how all mainstream tokenizers (BPE, Unigram) operate: greedy algorithms with 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 of the NLP Pipeline

Tokenizers are the first gate for all language models. They cut input text into tokens before the model ever sees it, and how well they cut directly shapes how clearly the model perceives its "world."

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

The catch is that BPE's greedy strategy produces many "intermediate tokens" — e.g., "un" and "able" merge into "unable," but "un" itself may not be an optimal choice. These unnecessary byproducts waste vocabulary space and reduce 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).

In the integer version, each token is either chosen (1) or not (0). Integer programs are hard to solve, so ConvexTok applies a clever relaxation: variables may take any value between 0 and 1 (say, 0.7). This yields an LP that mature solvers can handle efficiently and exactly.

Of course, the relaxed solution may contain "half-selected" tokens (a token selected at 0.7), which is meaningless in practice. ConvexTok therefore proposes three rounding schemes to convert fractional selections back to integers:

Det (deterministic rounding): straightforward rounding — simple and direct
Bias (biased rounding): weighted stochastic rounding based on fractional values, preserving more information
Top-k: keep the k tokens with the highest scores

Once rounded, constructing 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 beat it), it can be used to certify how far existing tokenizers are from optimal.

The experimental result is striking: at common vocabulary sizes, both BPE and ConvexTok fall within 1% of the theoretical optimum! This means the headroom for improvement in compression rate is actually quite small.

But don't conclude that "BPE is good enough" — ConvexTok still dominates on multiple intrinsic metrics:

Compression rate: the Bias rounding scheme beats BPE across all vocabulary sizes
Vocabulary utilization: ConvexTok uses the vocabulary more efficiently, with less waste
Rényi entropy: also better on this information-theoretic metric

Downstream Results: Progress, but Not Consistent

On language modeling downstream tasks, the Det rounding scheme stably outperforms BPE on bits-per-byte (BpB). But on the CORE benchmark, ConvexTok's results are mixed — sometimes clearly ahead, sometimes on par.

This isn't contradictory. Tokenizers optimize compression, and the relationship between compression and downstream task performance is not strictly linear. A tokenizer with better compression may split certain semantic boundaries too finely, interfering with model learning.

Why This Paper Matters

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

1. Tokenization can be exactly optimized: we no longer need to accept greedy limitations; convex optimization tools give us a global view 2. We can certify optimality: the LP lower bound lets us say, for the first time, "how far this tokenizer is from optimal" rather than merely "this one beats that one" 3. The tokenizer ceiling may already be near: a 1% gap suggests future breakthroughs in compression may require a different optimization objective

It's like GPS navigation — previously we could only follow one road to the end; now we have a global map, not only finding better routes but also telling us "this road is already 99% optimal."

---

Paper: Tokenisation via Convex Relaxations

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