In this paper the authors investigate the near-optimality of Byte-Pair Encoding (BPE), a widely used greedy tokenization algorithm, in minimizing the number of tokens required to represent natural language corpora under a fixed vocabulary budget. The authors consider three optimization formulations: Direct Vocabulary Selection (DVS), Optimal Pair Encoding (OPE), and Optimal Merge Sequences (OMS), which progressively impose additional constraints on vocabulary construction and tokenization. They formulate all three problems as integer linear programs (ILPs), establishing a hierarchy of optimal token counts.
The main contribution is a scalable optimization framework based on dual decomposition for DVS and OPE. By exploiting the separability of string segmentation through Viterbi dynamic programming and coordinating vocabulary selection using Lagrangian multipliers, the proposed approach computes lower bounds on the optimal token count and feasible upper bounds. This enables the authors to certify how close BPE is to the optimal vocabulary without solving the underlying combinatorial optimization problem exactly. The framework also incorporates an active-set strategy to improve memory efficiency and scalability.
The authors evaluate their approach on the ClimbMix corpus across vocabulary budgets ranging from 4,096 to 65,536 optional tokens. The results show that BPE's token count is at most 3.45% above the DVS optimum under the evaluated candidate restrictions, with the certified gap decreasing to 1.80% at the largest vocabulary budget. The proposed dual-decomposition methods also demonstrate substantially better memory scalability than a monolithic LP solver, although BPE remains 2.5–5.3 times faster. Additional experiments examine solver correctness on smaller instances, held-out compression performance, and the effect of vocabulary size. Overall, the paper provides theoretical and empirical evidence that BPE achieves near-optimal token-count compression under the studied conditions, while introducing a scalable framework for certifying tokenization quality.