ConvexTok: Rewriting Tokenization with Convex Optimization

> "You can know the name of that bird in all the languages of the world, but when you're finished, you'll know absolutely nothing whatever about the bird." > — Richard Feynman, recalling his father's teaching

This post is a deep-dive review of the paper *Tokenisation via Convex Relaxations* by Jan Tempus, Philip Whittington, and Craig W. Schmidt (2025). The core idea: instead of building subword vocabularies greedily (BPE, Unigram), formulate vocabulary selection as a convex optimization problem whose local optima are guaranteed to be global optima.

Key points

The problem with greedy tokenizers

• Tokenization splits text into subword units so a model can represent any sentence, including new words ("selfie", "COVID-19"), with a fixed vocabulary.
• BPE repeatedly merges the most frequent adjacent pair of symbols. Each merge is irreversible and based only on immediate frequency — like a restaurant that packs the day's two best-selling dishes into a combo without ever asking whether a different combination would be globally better.
• Unigram starts from a huge candidate set and iteratively prunes the least important subwords under a unigram probability model. Better informed, but still locally greedy, with a circular dependency between the model and the current vocabulary.
• Neither method can answer: *how far is my vocabulary from optimal?* The underlying selection problem is combinatorial and NP-hard, which is why heuristics dominated until now.

The convex relaxation

ConvexTok's recipe:

1. Variables: each candidate subword gets a continuous weight w_i ∈ [0,1] (relaxing the 0/1 in-or-out decision — like being allowed to "buy half a fruit"). 2. Objective: minimize the encoding cost of covering the corpus, related to self-information (-log p) — like paying a telegraph bill where common codewords are short. 3. Constraints: total vocabulary size stays within budget (e.g., equivalent to 32,000 subwords). 4. Convexity: objective and constraints are designed so the whole problem is convex — a bowl with a single lowest point, so hill-climbing reaches the global optimum.

Because vocabulary selection and segmentation decisions are interdependent, ConvexTok optimizes both inside one convex framework. After solving, a greedy projection/rounding step converts weights into a discrete vocabulary (rank by w_i, take the top ones, then recompute optimal segmentations). Experiments show this rounding loses less than 1% of optimality.

Experimental results

• Intrinsic metrics: ConvexTok consistently beats BPE, Unigram, and WordPiece on fertility (average tokens per text, lower is better) and coverage — its vocabularies are more compact and efficient.
• Language modeling: consistently lower bits-per-byte (BpB), meaning models trained on its tokenization compress and predict text better.
• Downstream tasks (GLUE, machine translation, code generation): improvements exist but are less consistent — evidence that tokenization is only one stage of the pipeline, and that the mapping between "encoding cost" and "downstream performance" remains an open research question.
• Provably near-optimal: via the duality gap (the gap between the primal objective and its rigorous dual lower bound), ConvexTok certifies its solution is within 1% of the theoretical optimum at typical vocabulary sizes. Greedy methods can never offer such a guarantee.

Costs and caveats

• Compute: solving a large convex program costs several to tens of times more than BPE training — acceptable since tokenizers are trained once. (Fast wooden bridge vs. carefully engineered steel bridge.)
• Rounding loss: with very small vocabularies, near-tied weights make the greedy projection more fragile.
• Surrogate objective: optimality is relative to the encoding-cost objective, which does not perfectly align with downstream task performance. "Mathematically optimal" is not automatically "practically best."

Philosophical and future directions

The author argues "optimal tokenization" is really a multi-objective problem: encoding efficiency, semantic learnability, generalization to new words, and cross-lingual consistency. ConvexTok optimizes the first nearly perfectly; aligning the rest is open. Promising extensions:

• Multilingual tokenization: one convex framework jointly balancing several corpora.
• Adaptive tokenization: online vocabulary updates as corpora drift.
• Joint optimization with the language model rather than separate pipeline stages.
• Interpretability: subword weights reveal which units matter most.

References

• Tempus, J., Whittington, P., & Schmidt, C. W. (2025). *Tokenisation via Convex Relaxations*. arXiv preprint. cs.CL, cs.LG.
• Sennrich, R., Haddow, B., & Birch, A. (2016). Neural Machine Translation of Rare Words with Subword Units. *ACL 2016*.
• Kudo, T. (2018). Subword Regularization. *ACL 2018*.
• Kudo, T., & Richardson, J. (2018). SentencePiece. *EMNLP 2018*.
• Bostrom, K., & Durrett, G. (2020). Byte Pair Encoding is Suboptimal for Language Model Pretraining. *Findings of the ACL: EMNLP 2020*.
• Garey, M. R., & Johnson, D. S. (1979). *Computers and Intractability*. W. H. Freeman.
• Boyd, S., & Vandenberghe, L. (2004). *Convex Optimization*. Cambridge University Press.

*"I read this paper three times. Not because it was hard, but because it was beautiful — what we thought was an 'engineering problem' is fundamentally a math problem, one mathematicians solved decades ago and we simply never used."*