Paper Overview
Field: NLP Authors: Jan Tempus, Philip Whittington, Craig W. Schmidt Published: 2025-05-23 arXiv: 2505.17394
Summary
Tokenization is a core component of current NLP pipelines. Existing tokenization algorithms such as BPE and Unigram are greedy — they only make locally optimal decisions and never consider the overall effectiveness of the vocabulary. This paper reformulates tokenizer construction as a linear programming problem and solves it with convex optimization tools, proposing a new algorithm named ConvexTok.
Experiments show that ConvexTok achieves consistent improvements in intrinsic tokenization metrics and in language-model bits-per-byte (BpB). It also improves downstream task performance, though the gains are relatively less consistent. In addition, ConvexTok allows users to certify, via lower bounds, how far their tokenizer is from optimal — under common vocabulary sizes, experiments found it to be less than 1% away from the optimum.
Key Takeaways
- Existing tokenizers (BPE, Unigram) are greedy and locally optimal only.
- Tokenizer construction can be modeled as a linear program solved with convex optimization.
- ConvexTok improves intrinsic metrics and BpB consistently; downstream gains are positive but less stable.
- It provides optimality certificates: within <1% of optimal at common vocabulary sizes.