ConvexTok: Convex Optimization for Tokenization Closes the Gap to Optimal Within 1%
The overlooked first stage of NLP
Tokenization sits at the very front of every language model pipeline. The quality of the split directly shapes how the model perceives language. Yet tokenization is fundamentally an NP-hard combinatorial problem: finding the optimal segmentation across all possibilities requires exponential computation. In practice, the field has long relied on greedy heuristics such as Byte-Pair Encoding (BPE), which iteratively merges the most frequent adjacent token pairs until a target vocabulary size is reached.
The well-known weakness of greedy merging is the proliferation of redundant "intermediate tokens" (e.g., the morpheme un being kept in the vocabulary because of how merges unfold). These intermediates consume vocabulary slots and drag down compression efficiency.
From greedy merging to mathematical programming
ConvexTok's central idea is to cast vocabulary selection as an Integer Program (IP) and then relax it into a Linear Program (LP) that can be solved exactly with off-the-shelf solvers.
- Integer Program layer: binary decisions on whether to include each candidate token.
- LP relaxation layer: allow each decision variable to take any value in
[0, 1]. The LP can be solved efficiently, and its objective value serves as a certifiable lower bound on compression. - Det: deterministic round-to-nearest, fast and simple.
- Bias: weighted randomized rounding that preserves more information from the LP.
- Top-k: keep only the
ktokens with the highest fractional values. - Compression rate: the Bias rounding scheme beats BPE at every vocabulary size tested.
- Vocabulary utilization: ConvexTok uses its vocabulary slots more efficiently, producing less waste.
- Rényi entropy: information-theoretic measures also favor ConvexTok.
- Paper: Tokenisation via Convex Relaxations
- Code: github.com/JanTempus/tokenisation_lp
Because fractional solutions (e.g., a token assigned 0.7) are not directly usable, ConvexTok proposes three rounding strategies:
After rounding, the resulting vocabulary is assembled into a standard tokenizer.
Certifying optimality: the 1% gap
The most striking empirical finding is that the LP lower bound enables optimality certification: any tokenizer's compression rate can be compared against the LP bound to measure how far it is from the theoretical optimum.
Across standard vocabulary sizes, both BPE and ConvexTok fall within ~1% of the LP bound. In other words, the room left for improving raw compression efficiency is much smaller than previously assumed.
ConvexTok nonetheless leads on several intrinsic metrics:
Downstream: progress, but not stable
On language modeling, the deterministic rounding variant of ConvexTok consistently improves bits-per-byte (BpB) over BPE. On the CORE benchmark, however, results are mixed: ConvexTok sometimes wins clearly and sometimes ties. This is consistent with the fact that compression and downstream task performance are not strictly linearly correlated: a tokenizer that compresses better can occasionally cut semantic boundaries in ways that interfere with the model.
Why this paper matters
ConvexTok contributes three conceptual upgrades beyond a better tokenizer:
1. Exact optimization is feasible for tokenization; convex optimization tools deliver a global view that greedy methods cannot. 2. Optimality is now certifiable: the LP lower bound makes it possible to state *how far* a tokenizer is from the best possible, rather than only comparing two candidates side by side. 3. The compression ceiling is close: a ~1% gap suggests future gains may require optimizing objectives other than compression rate.