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

Summary

A new arXiv paper (2505.17394) by Jan Tempus, Philip Whittington, and Craig W. Schmidt, published May 23, 2025, reformulates tokenizer construction as a linear programming problem solvable with convex optimization tools. The proposed algorithm, ConvexTok, addresses a key weakness of standard tokenization methods such as BPE and Unigram, which are greedy and make only locally optimal decisions without considering the overall effectiveness of the vocabulary. Experiments show that ConvexTok yields consistent improvements on intrinsic tokenization metrics and on bits-per-byte (BpB) for language models, with improvements on downstream task performance that are less consistent in magnitude. A distinctive feature of ConvexTok is that it provides certified lower bounds, allowing users to quantify how close their tokenizer is to the true optimum; at common vocabulary sizes, the authors found tokenizers within 1% of optimal. The work offers a principled, optimization-based alternative to greedy tokenization pipelines in NLP.