ConvexTok: Rewriting Tokenization with Convex Optimization Instead of Greedy Heuristics

A forum deep-dive into the paper "Tokenisation via Convex Relaxations" by Jan Tempus, Philip Whittington, and Craig W. Schmidt (arXiv, 2025), framed around the question: what happens if we hand subword vocabulary construction to a mathematician instead of a greedy algorithm?

Key points

The problem with greedy tokenizers

• BPE (Byte Pair Encoding) works like a greedy matching game: start from characters, repeatedly merge the most frequent adjacent pair, until reaching a vocabulary size limit (e.g., 32,000). Every merge is irreversible and only locally optimal — "today's most popular combo is not necessarily the globally best menu."
• Unigram starts from a huge candidate set and iteratively prunes the least important subwords under a unigram probability model. Slightly more global, but still locked into a circular dependency: pruning order depends on the current model, which depends on the current vocabulary.
• Neither method can answer: "How far is my vocabulary from the true optimum?" The underlying combinatorial problem (choosing k subwords from n candidates) is NP-hard, which is why heuristics dominate.

The convex relaxation idea

ConvexTok replaces the 0/1 "select or not" decisions with continuous weights:

1. Variables: each candidate subword gets a weight w_i ∈ [0,1]. 2. Objective: minimize the encoding cost of covering the corpus, related to self-information (-log p), jointly optimizing both which subwords are selected and how each text is segmented. 3. Constraint: a budget on total vocabulary size. 4. Convexity: the objective and constraints are crafted so the whole problem is convex — any local optimum is the global optimum, so no local traps exist.

The continuous solution is then converted to a discrete vocabulary by greedy rounding/projection: sort by weight, fix the top-scoring subwords as selected until the budget is reached, then recompute optimal segmentations. Because the soft assignment is already near-optimal, rounding loss is tiny.

Experimental results

• Intrinsic metrics: ConvexTok consistently beats BPE and Unigram on fertility (average tokens per corpus unit — lower is better) and coverage (higher is better), producing more compact and efficient vocabularies.
• Language modeling: consistently lower bits-per-byte (BpB) — models trained on ConvexTok tokenization compress and predict text better.
• Downstream tasks (GLUE, machine translation, code generation): improvements exist but are less consistent, revealing that tokenization is only one stage of the NLP pipeline and that the mapping between "encoding cost" and downstream performance remains an open problem.
• Optimality certificate: via the duality gap, ConvexTok proves its solution is within less than 1% of the theoretical optimum at common vocabulary sizes (e.g., 32,000). Greedy methods cannot offer any such guarantee.

Costs and caveats

• Compute: solving a large convex problem over hundreds of thousands of candidates is several to tens of times slower than BPE — acceptable since tokenizers are trained once and reused.
• Rounding: with very small vocabularies, near-tied weights make the rounding step more sensitive.
• Surrogate objective: optimality holds with respect to encoding cost, not necessarily downstream accuracy. "Mathematically optimal" ≠ "empirically best" on every task.

Deeper questions and future directions

The author argues "optimal tokenization" is really a multi-objective problem — encoding efficiency, semantic learnability, generalization to new words, cross-lingual consistency — and ConvexTok optimizes only the first. Promising extensions include:

• Multilingual tokenization: jointly optimizing vocabularies across languages in one framework.
• Adaptive tokenization: online vocabulary updates as corpora evolve.
• Joint optimization with the language model itself.
• Interpretability: subword weights expose which units matter most, potentially revealing linguistic structure.

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. *Proceedings of the 54th Annual Meeting of the ACL*.
• Kudo, T. (2018). Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates. *Proceedings of the 56th Annual Meeting of the ACL*.
• Kudo, T., & Richardson, J. (2018). SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing. *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: A Guide to the Theory of NP-Completeness*. W. H. Freeman and Company.
• Boyd, S., & Vandenberghe, L. (2004). *Convex Optimization*. Cambridge University Press.