Tokenisation via Convex Relaxations: ConvexTok Formulates Tokenizer Training as a Linear Program

Forum topic · 小凯 · 2026-05-25

Summary

A new paper by Jan Tempus, Philip Whittington, and Craig W. Schmidt (arXiv:2505.14482) reframes tokenizer construction as a linear programming problem solvable with convex optimization, departing from greedy algorithms like BPE and Unigram that only make locally optimal decisions. The resulting algorithm, ConvexTok, shows consistent improvements in intrinsic tokenization metrics and in bits-per-byte (BpB) achieved by language models trained on its vocabularies, with weaker but still positive effects on downstream task performance. Notably, ConvexTok provides a lower bound that lets users certify how far their tokenizer is from the optimum; empirically, the authors find it stays within 1% of optimal at commonly used vocabulary sizes. This work from zhichai.net summarizes the paper's contributions for the NLP community.

Paper Overview

Field: NLP Authors: Jan Tempus, Philip Whittington, Craig W. Schmidt Published: 2026-05-25 arXiv: 2505.14482

Abstract

Tokenisation is an indispensable component of current NLP pipelines. Existing tokenisation algorithms such as BPE and Unigram are greedy — they make only locally optimal decisions without considering the overall quality of the final vocabulary. This paper reformulates tokenizer construction as a linear programming problem and solves it with convex optimization tools, proposing a new algorithm called ConvexTok.

Key Findings

ConvexTok shows consistent improvements over greedy baselines in intrinsic tokenisation metrics.
Language models trained with ConvexTok vocabularies achieve better bits-per-byte (BpB) scores.
Improvements on downstream tasks are also observed, though they are less consistent.
ConvexTok provides a lower bound allowing users to certify how far their tokenizer is from the optimal solution.
Empirically, ConvexTok is within 1% of the optimal solution at commonly used vocabulary sizes.

---

*Auto-collected on 2026-05-25*