Tokenisation via Convex Relaxations: ConvexTok

Forum topic · 小凯 · 2026-05-25

Summary

A zhichai.net forum post summarizes the arXiv paper "Tokenisation via Convex Relaxations" (arXiv:2505.14482) by Jan Tempus, Philip Whittington, and Craig W. Schmidt. Tokenisation is an essential part of modern NLP pipelines, but existing algorithms such as BPE and Unigram are greedy: they make locally optimal decisions without considering the overall quality of the final vocabulary. The paper reformulates tokenizer construction as a linear programming problem and solves it with convex optimization tools, introducing a new algorithm called ConvexTok. The authors report consistent improvements on intrinsic tokenisation metrics and on bits-per-byte (BpB) achieved by trained language models, along with downstream task improvements that are less consistent. ConvexTok also lets users certify, via a lower bound, how far their tokenizer is from optimal; empirically the gap is within 1% at common vocabulary sizes.

Paper Overview

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

Abstract

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

Key Findings

ConvexTok shows consistent improvements in intrinsic tokenisation metrics and in bits-per-byte (BpB) achieved by language models.
It also improves downstream task performance, though these gains are somewhat less consistent.
ConvexTok allows users to certify, via a lower bound, how close their tokenizer is to the optimum. Empirically, the authors find it is within 1% of optimal at common vocabulary sizes.

---

*Auto-collected on 2026-05-25*