Tokenisation via Convex Relaxations
For NLP practitioners, this provides a principled alternative to greedy tokenisation algorithms like BPE, with certifiable optimality bounds.
The authors formulate tokeniser construction as a linear program solved via convex optimisation, producing ConvexTok, which improves intrinsic tokenisation metrics and bits-per-byte (BpB) by language models, and achieves within 1% of optimal at common vocabulary sizes.
Tokenisation is an integral part of the current NLP pipeline. Current tokenisation algorithms such as BPE and Unigram are greedy algorithms -- they make locally optimal decisions without considering the resulting vocabulary as a whole. We instead formulate tokeniser construction as a linear program and solve it using convex optimisation tools, yielding a new algorithm we call ConvexTok. We find ConvexTok consistently improves intrinsic tokenisation metrics and the bits-per-byte (BpB) achieved by language models; it also improves downstream task performance, but less consistently. Furthermore, ConvexTok allows the user to certify how far their tokeniser is from optimal, with respect to a certain objective, via a lower bound, and we empirically find it to be within 1\% of optimal at common vocabulary sizes.