paper

Greedy Byte-Pair Encoding Achieves 0.391 of the Optimum, Past the One-Third Barrier for Packing-Based Analyses

arXiv:2611.08671

Abstract

Byte-Pair Encoding (BPE) builds most language-model tokenisers by repeatedly merging a most frequent adjacent pair of symbols. How much shortening can this greedy rule lose against the best merges? Kozma and Voderholzer proved that greedy achieves at least one third of the optimal shortening; the best known upper bound is . We show that one third is a barrier for packing-based analyses, which see the optimum only through a pair packing, and we prove that greedy achieves at least of the optimum on every input, with any tie-breaking. The key idea is rule determinism: all copies of a rule of the optimum spell the same letters, so when one greedy replacement destroys three of the optimum's merge points, half a unit can be refunded on each side. A weaker bound, , has a short proof that needs no computer; adds a certificate in exact arithmetic. We also show that the worst-case ratio is exactly for two merges and at most for three.

arXiv comment40 pages, 7 figures. Restructured: the results on the re-typing inequality for short tokens moved to a companion paper; the compressed-length hardness moved to the authors' tokenisation-complexity paper. Code and certificates: https://doi.org/10.5281/zenodo.24023719