ConvexTok: Optimal Tokenization Through Linear Programming

Paper: 2605.22821 Authors: Jan Tempus, Philip Whittington, Craig W. Schmidt, Dennis Komm, Tiago Pimentel Categories: cs.CL, cs.LG

The Gap

Current tokenization algorithms like BPE (Byte Pair Encoding) and Unigram make greedy, locally optimal decisions. They build vocabularies by iteratively selecting the next best token without considering the global quality of the final vocabulary. This means they can get stuck in local optima—the vocabulary they produce might be good, but there’s no way to know how far it is from the best possible vocabulary for a given objective.

The gap: No existing tokenization method can certify optimality or provide bounds on how suboptimal the result is.

Problem: Greedy tokenizers make local decisions
    |
    v
Assumption: Tokenization can be formulated as global optimization
    |
    v
Method: Linear program with convex relaxation
    |
    v
Evidence: 1% from optimal, better BpB, improved metrics
    |
    v
Conclusion: Global optimization beats greedy heuristics

The Increment

One sentence: Before this paper, tokenizers were greedy algorithms with unknown optimality gaps; after, we have a method that provably gets within 1% of optimal and can certify that distance.

Core Mechanism

ConvexTok formulates tokenizer construction as a linear program. The key insight is treating token selection as a binary decision problem: for each possible token (substring from the training corpus), decide whether to include it in the vocabulary (1) or not (0). The objective function measures vocabulary quality—typically minimizing the total encoding length of the training corpus.

The challenge is that this is a combinatorial optimization problem (NP-hard). ConvexTok solves it by relaxing the binary constraints: instead of forcing each decision to be exactly 0 or 1, it allows fractional values between 0 and 1. This turns the problem into a linear program that can be solved efficiently using convex optimization. After solving the relaxed problem, ConvexTok rounds the fractional solutions back to binary decisions, selecting the top-k tokens by their fractional values to fill the vocabulary.

The relaxation also provides a lower bound on the optimal objective value. By comparing the achieved objective (after rounding) to this lower bound, ConvexTok can certify how close the solution is to optimal—something no greedy algorithm can do.

Training Corpus
    |
    v
[Extract all possible substrings]
    |
    v
[Formulate LP: minimize encoding cost]
    |  Variables: x_i in [0,1] for each token i
    |  Objective: sum of costs weighted by x_i
    |  Constraints: coverage, vocabulary size
    v
[Solve relaxed LP] --> Lower bound (optimal cost)
    |
    v
[Round: select top-k by x_i values]
    |
    v
Final Vocabulary + Optimality Certificate

Think of it like portfolio optimization. A greedy tokenizer is like picking stocks one at a time—you choose the best-looking stock right now, then the next best given what you already have, and so on. You never look at the portfolio as a whole. ConvexTok is like modern portfolio theory: you define what “good” means for the entire portfolio (minimize risk for a given return), formulate it as an optimization problem, and solve for the globally optimal allocation. The relaxation is like allowing fractional shares—you can hold 0.7 shares of a stock in the mathematical solution, then round to whole shares at the end. The gap between the fractional solution and the rounded solution tells you how much you lost by rounding, giving you a certificate of near-optimality.

Key Concepts

• Convex Relaxation: Imagine you’re trying to pack a suitcase with items that either fit completely or don’t fit at all (binary: in or out). This is hard because you have to try many combinations. Convex relaxation says: “What if items could be partially packed?” You solve this easier problem where an item can be 40% in the suitcase, get an answer, then round back to whole items. The “partial packing” solution gives you a lower bound on the best possible packing—you know the real answer can’t be better than this, because you gave yourself extra flexibility. In tokenization, tokens are either in the vocabulary (1) or out (0). Relaxing to [0,1] makes the problem solvable, and the relaxed solution bounds the optimal binary solution.

• Optimality Certificate: Most algorithms give you an answer but no guarantee about quality. An optimality certificate is a mathematical proof of how good your solution is. ConvexTok provides two numbers: the cost of its vocabulary (upper bound) and the cost of the relaxed solution (lower bound). If they’re close—say, within 1%—you have a certificate that your vocabulary is within 1% of the best possible. It’s like a GPS telling you not just “you’ll arrive in 30 minutes” but “the absolute fastest possible route is 29.7 minutes, so you’re within 1% of optimal.”

• Greedy vs. Global Optimization: Greedy algorithms make the best local choice at each step. Climbing a hill, a greedy algorithm always steps upward—it reaches the nearest peak but might miss a higher mountain across the valley. Global optimization looks at the entire landscape and finds the true highest peak. BPE and Unigram are greedy: they merge the most frequent pair or select the token that most reduces cost right now. ConvexTok is global: it considers all tokens simultaneously and selects the set that minimizes total cost, even if some individual tokens wouldn’t be chosen greedily.

Framework Shift

Before (BPE/Unigram):                After (ConvexTok):

Start with characters                Define objective for entire vocab
    |                                     |
    v                                     v
Repeat:                              Formulate as LP over all tokens
  - Find best local merge/add            |
  - Update vocabulary                    v
  - Never reconsider                 Solve relaxed problem
    |                                     |
    v                                     v
Final vocab                          Round to binary + certificate
(unknown quality)                    (provably near-optimal)

Sequential decisions -->             Simultaneous optimization
No optimality guarantee -->          Certified 1% gap

[One sentence: From sequential local decisions to simultaneous global optimization, the core shift is treating tokenization as a solvable mathematical program rather than a greedy heuristic.]

Expert Assessment

Problem choice: Real gap. Tokenization is foundational to NLP, and the lack of optimality guarantees in BPE/Unigram has been a known limitation. This isn’t manufactured—it’s a natural question once you realize greedy algorithms dominate a critical pipeline component. The timing is right: convex optimization tools are mature, and the field is scrutinizing tokenization more carefully as models scale.

Method maturity: Elegant insight, not brute force. The convex relaxation is a standard technique from combinatorial optimization, applied cleverly to a new domain. The rounding strategy is simple (top-k by fractional value), which is both a strength (easy to implement) and a potential weakness (more sophisticated rounding might improve results). The lower bound from the relaxed LP is the key contribution—it’s what enables the optimality certificate.

Experimental integrity: Baselines are fair (BPE, Unigram, standard benchmarks). The improvements are modest but consistent: better intrinsic metrics (compression, fertility) and BpB, less consistent on downstream tasks. The 1% optimality gap is impressive and well-documented. One concern: the LP formulation requires defining an objective upfront, and the paper focuses on encoding length. If the true goal is downstream task performance, the mismatch might explain why downstream gains are inconsistent. The paper is honest about this.

Writing quality: Clear and well-structured. The LP formulation is explained carefully. The experimental section could be stronger—more ablations on different objectives, vocabulary sizes, and languages would solidify the claims. The discussion of why downstream improvements are inconsistent feels underdeveloped; this deserves a deeper investigation or at least more speculation.

Verdict: weak accept — Solid contribution with practical value and theoretical rigor, but the downstream task results are mixed and the method’s sensitivity to objective choice needs more exploration.

Takeaways

Steal the certificate idea: Even if you don’t use ConvexTok, the concept of providing optimality certificates for heuristic algorithms is broadly applicable. Any time you’re using a greedy or approximate algorithm, ask: can I formulate a relaxed version that gives a lower bound? This applies to neural architecture search, hyperparameter tuning, data subset selection, etc.

Rethink greedy pipelines: Tokenization isn’t the only NLP component built on greedy heuristics. Beam search, pruning strategies, and incremental training all make local decisions. This paper shows that reformulating as global optimization can be tractable and worthwhile. Look for similar opportunities in your pipeline.

Objective mismatch matters: ConvexTok optimizes for encoding length but is evaluated on downstream tasks. The inconsistent downstream gains suggest the objective doesn’t fully capture what makes a tokenizer good for language modeling. This is a reminder: when you optimize a proxy metric, measure the gap between proxy and true goal. If they diverge, either improve the proxy or accept the limitation.