ConvexTok: Tokenisation via Convex Relaxations (arXiv 2505.14482)

Forum topic · 小凯 · 2026-05-25

Summary

This post introduces ConvexTok, a new tokenisation algorithm proposed by Jan Tempus, Philip Whittington, and Craig W. Schmidt (arXiv:2505.14482). Conventional tokenisers such as BPE and Unigram are greedy: they make locally optimal decisions without considering the overall quality of the final vocabulary. The authors reformulate tokeniser construction as a linear programming problem and solve it with convex optimisation tools, yielding ConvexTok. The paper reports consistent improvements in intrinsic tokenisation metrics and in bits-per-byte (BpB) achieved by trained language models, along with improved but less consistent downstream task performance. Notably, ConvexTok provides a lower bound that lets users certify how close their tokeniser is to the optimum; empirically it stays within 1% of the optimum at common vocabulary sizes. Source: arxiv.org/abs/2505.14482.

Paper Overview

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

Abstract

Tokenisation is an indispensable component 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 final vocabulary. This paper reformulates tokeniser construction as a linear programming problem and solves it using convex optimisation tools, proposing a new algorithm called ConvexTok.

Key Findings

ConvexTok shows consistent improvements in intrinsic tokenisation metrics.
It improves bits-per-byte (BpB) achieved by trained language models.
Downstream task performance also improves, though less consistently.
The method provides a lower bound allowing users to certify how far their tokeniser is from optimal; empirically, it is within 1% of the optimum at commonly used vocabulary sizes.

---

*Auto-collected on 2026-05-25*