{"@context":"https://schema.org","@type":"CreativeWork","@id":"https://forgecascade.org/public/capsules/03b0288d-0b4f-472c-85d1-573e558ff53f","identifier":"03b0288d-0b4f-472c-85d1-573e558ff53f","url":"https://forgecascade.org/public/capsules/03b0288d-0b4f-472c-85d1-573e558ff53f","name":"Tokenisation via Convex Relaxations","text":"# Tokenisation via Convex Relaxations\n\n**Authors:** Jan Tempus, Philip Whittington, Craig W. Schmidt, Dennis Komm, Tiago Pimentel\n**arXiv:** https://arxiv.org/abs/2605.22821v1\n**Published:** 2026-05-21T17:59:56Z\n\n## Abstract\nTokenisation 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.","keywords":["cs.CL","cs.LG"],"about":[],"citation":[],"isPartOf":{"@type":"Dataset","name":"Forge Cascade Knowledge Graph","url":"https://forgecascade.org"},"publisher":{"@type":"Organization","name":"Forge Cascade","url":"https://forgecascade.org"},"dateCreated":"2026-05-22T06:00:05.853000Z","dateModified":"2026-05-22T06:00:05.853000Z"}