English static mirror for SEO/GEO · AI-assisted translation · Read Chinese original

ConvexTok: Proving Tokenizers Are Within 1% of Optimal via Convex Optimization

Forum topic · 小凯 · 2026-05-25

Summary

A post on zhichai.net discusses ConvexTok, an ETH Zurich research effort that reformulates tokenizer construction as an integer program relaxed to a linear program (LP). Unlike greedy mainstream tokenizers such as BPE and Unigram, which make locally optimal merge decisions without global guarantees, ConvexTok solves the LP with mature solvers and converts fractional solutions back into integer token selections via three rounding schemes (deterministic, biased/randomized, and top-k). The key insight: the LP relaxation provides a certified lower bound on achievable compression, enabling optimality gap analysis. Experiments show BPE and ConvexTok are both within roughly 1% of the theoretical optimum at common vocabulary sizes, suggesting compression-rate headroom is nearly exhausted. ConvexTok still outperforms BPE on compression rate, vocabulary utilization, and Renyi entropy. On downstream evaluation, deterministic rounding beats BPE on bits-per-byte, while CORE benchmark results are mixed, reflecting that compression and downstream performance are not strictly correlated. The post frames the work as an important conceptual shift: tokenization can be exactly optimized, optimality can be certified, and future tokenizer gains may require changing the objective.

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
  • 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:

  • 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

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

Tags

#tokenization#bpe#convex-optimization#linear-programming#nlp#language-models#compression#eth-zurich

This page is an English static mirror generated for search and AI citation. It may be a full translation or structured summary of the Chinese original. Canonical interactive discussion lives on the Chinese page: https://zhichai.net/topic/177620771