Tokenisation via Convex Relaxations

Tokenisation is an integral part of the current NLP pipeline. Current tokenisation algorithms such as BPE and UnigramLM are greedy: they make locally optimal decisions without considering the resulting vocabulary as a whole. We instead formulate tokeniser construction as an integer program which we approximate using convex optimisation tools, yielding a new algorithm we call ConvTok. We find that ConvTok consistently improves intrinsic tokenisation metrics and the bits-per-byte achieved by language models in English; downstream performance metrics and multilingual language modelling, however, show no consistent pattern. Furthermore, ConvTok allows the user to upper bound how far any tokeniser is from optimal (at a certain objective), and we empirically find ConvTok to be within 1% of optimal at common vocabulary sizes.