Tokenisation via Convex Relaxations
AuthorsJan Tempus, Philip Whittington, Craig W. Schmidt, Dennis Komm, Tiago Pimentel
Resources
This paper turns tokenization from a greedy heuristic into a convex optimization problem, producing a tokenizer that can be near-optimal and often slightly better for language models.
Key results
ConvexTok was trained and evaluated on the ClimbMix400B corpus using this many documents.
The experiments sweep vocabulary budgets from 8k up to 256k, in power-of-two increments.
The LP relaxation was empirically certified to be within 1% of the optimum at common vocabulary sizes.
At 128k and 256k, over 90% of colour variables were fixed to 0 or 1, indicating a highly integral relaxation.
The Det rounding scheme achieved 0.7033 validation bits-per-byte at 32k and depth 24, compared with BPE's 0.7042.
The Det rounding scheme achieved 0.6951 validation bits-per-byte at 128k, compared with BPE's 0.6968.
What the paper found
Tokenisation via Convex Relaxations reframes subword vocabulary construction as a shortest-path optimisation problem on a tokenisation graph, then converts that problem into a large linear program solved with NVIDIA CuOPT PDLP. The resulting method, ConvexTok, replaces greedy BPE merges with a global objective over 593,920 ClimbMix400B documents and vocabularies from 8k to 256k. The LP relaxation is remarkably tight: across common vocabulary sizes, the certified gap to optimum is within 1%, and the relaxed solutions become increasingly integral as vocabulary size grows, with over 90% of colour variables fixed to 0 or 1 at 128k and 256k. After rounding, the deterministic scheme Det gives the best language-model compression, improving bits-per-byte over BPE on all 12-layer models and usually remaining ahead at deeper settings; for example, at 32k and depth 24, Det reaches 0.7033 BpB versus BPE’s 0.7042, and at 128k it reaches 0.6951 versus 0.6968. On intrinsic tokeniser metrics, the Bias rounding scheme is strongest overall, consistently improving vocabulary utilisation, type-token ratio, and tokens per line, while Det is more stable for downstream LM training. The paper’s central novelty is not a new merge heuristic but a certified convex optimisation formulation that can quantify how close any tokeniser is to compression optimality on a dataset, turning tokeniser design into a problem with explicit lower bounds rather than heuristic search.
Original abstract
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.
Read the original paperMore in Natural Language Processing
Browse all 26 papers →AdaTutoRank: Learning to Rerank Document Sets via Adaptive Tutoring Optimization for RAG and Deep Research
Kailin Jiang, Lei Liu, Jian Xi, Yangqi Chen, Hui Xu, Hongwei Zhao, Bin Li, Yu Lu, Haibo Shi
AdaTutoRank teaches rerankers to assemble complementary evidence sets rather than merely picking individually relevant documents, improving RAG and deep-research retrieval with fewer calls.
Computation Over Geometry: Meaning Identity Is Computed, Not Shipped in the Embeddings
Jiaqi Deng
The paper argues that sentence meaning equivalence is not reliably stored in separate embeddings but is computed when models process both sentences together.
SlopShape: Identifying AI-Generated Commercial Web Content
Jochen Madler
SlopShape detects and identifies AI-written commercial content by recognizing its underlying organizational style, even after the text has been reworded.