Certifying The Near-Optimality Of Byte-Pair Encoding On Natural Language Corpora

Language models operate on tokens, contiguous strings of bytes drawn from a finite token alphabet. The token alphabet is typically chosen so that a training corpus is represented with as few tokens as possible. Byte-pair encoding (BPE) is the most widely used procedure for inducing a token alphabet from data. It greedily merges tokens until a pre-determined vocabulary size is reached. The goal of this paper is to construct a scalable optimization algorithm that certifies how close to optimal a token alphabet, such as the one BPE learns, is on training corpora of realistic size. Our algorithm is based on dual decomposition, and it bounds the gap between standard tokenizers and the optimal token alphabet. To do so, we cast three previously proposed, declaratively specified tokenization objectives—direct vocabulary selection, optimal pair encoding, and optimal merge sequences—as integer linear programs (ILPs). For the first two formulations, dual decomposition allows us to exploit the fact that subproblems of the ILPs can be solved with dynamic programming. On ClimbMix—a common LM pretraining dataset—BPE's token count on held-out data is at most $3.45\%$ above the DVS optimum, with the gap shrinking to $1.80\%$ as vocabulary size increases, and BPE remains $2.5\times$ to $5.3\times$ faster. These results show that, under the evaluated constraints, BPE achieves near-optimal compression at substantially lower computational cost.