Byte-pair encoding can lose more than half of the optimal compression

Yang, Hanyu

doi:10.5281/zenodo.23207123

Byte-pair encoding can lose more than half of the optimal compression

The worst-case approximation ratio of byte-pair encoding is at most (1−e⁻²)/2 ≈ 0.4323, and against encodings whose tokens have length at most three that constant is exact.

DOI 10.5281/zenodo.23207123 · PDF · alphaXiv · code and data · CC BY 4.0 · preprint, 7 Oct 2026 · ORCID 0009-0005-0419-4070

Kozma and Voderholzer showed that BPE recovers between 1/3 and 5/8 of the optimal pair-encoding utility in the worst case. An explicit family of strings brings the upper bound down to (1−e⁻²)/2 ≈ 0.4323. Against the best encoding whose tokens have length at most three, BPE always gets at least that fraction, so the constant is exact there.

Abstract

Byte-pair encoding (BPE) merges the most frequent adjacent pair of symbols, k times. Kozma and Voderholzer proved that, in the worst case, it achieves between 1/3 and 5/8 of the best compression utility. We lower the upper bound to (1−e⁻²)/2 ≈ 0.4323. In our strings the boundaries between the tokens of a good encoding come in L levels, with frequencies decaying by a factor 1−2/L, and BPE spends its budget on them. Against the best encoding whose tokens have length at most three, the constant is exact: one replacement by BPE destroys at most two of its savings. Our strings need an alphabet that grows with k.

Results

Worst-case bounds on BPE divided by the optimum. OPT_flat is the best encoding whose tokens have length at most three.

comparison	lower bound	upper bound	alphabet of the upper bound
OPT, before	1/3 (Kozma–Voderholzer)	5/8 = 0.625 (Kozma–Voderholzer)	five letters
OPT, this paper	1/3 (Kozma–Voderholzer)	(1−e⁻²)/2 ≈ 0.4323 (Theorem 2)	grows with k
OPT_flat, this paper	(1−e⁻²)/2 (Theorem 1)	(1−e⁻²)/2 (Corollary 1)	grows with k

Ratio against merge budget k on a log scale: the lower bound c_k falls from 1/2 toward 0.4323, and the upper bound on the construction falls from about 0.455 toward 0.4323 from above. — The lower bound c_k of Theorem 1 against OPT_flat, and the upper bound of Theorem 2 on MT(L, L², 3), whose budget is k = L(2L+1), against the merge budget k.

Why one replacement costs at most two savings

A greedy merge destroys savings of the comparison encoding next to the ones it takes. Kozma and Voderholzer charge each replacement for at most three of them; if every token has length at most three, only two can go. That gives the recurrence G_t ≥ (1−2/k)G_t−1 + U/k for the gain of BPE after t steps, and with it the constant.

Tokens ab, cde, fg with four glues; BPE replaces bc and two glues are crossed out. — A flat comparison solution with tokens ab, *cde*, fg and its four glues (dots). BPE replaces bc (arc). The crossed glues are no longer alive.

The construction

The strings MT(L, F, β) place the boundaries between the tokens of a good encoding on L levels, with frequencies decaying by the factor 1−2/L. BPE merges the boundaries level by level and spends its whole budget there.

Three boxed tokens x y z separated by boundaries labelled level 1, level 2, level 1. — A stretch of MT. Boxes are the tokens of the witness. Arcs mark boundaries between tokens, labelled by level.

Pair counts over 16 phases: the level-l boundary count stays just above the largest internal pair count, and both stay above the repair and level-0 bounds. — Pair counts at the start of each phase of BPE on MT(16, 256, 3), with the bounds for repair and level-0 pairs.

Computations

On each of these strings BPE equals the closed form of Lemma 4 exactly. The ratio is BPE divided by an explicit witness encoding of utility 2DF, an upper bound on BPE/OPT.

L	F	β	letters \|s\|	k	BPE	witness	BPE/witness
16	320	4	259,777	528	76,593	168,960	0.4533
16	640	2	510,049	528	150,018	337,920	0.4439
16	640	4	513,217	528	151,074	337,920	0.4471
16	640	8	519,553	528	153,186	337,920	0.4533
16	1280	4	1,020,097	528	300,201	675,840	0.4442
24	640	4	1,143,073	1,176	334,474	752,640	0.4444
24	1280	4	2,272,033	1,176	664,146	1,505,280	0.4412
32	1280	4	4,018,561	2,080	1,170,780	2,662,400	0.4397

The Zenodo record has the code that builds these strings, checks the hypotheses of Lemma 4 in exact arithmetic and reruns BPE (reproduce.sh).

What it does not establish

A better lower bound against the unrestricted optimum: it is still 1/3. Theorem 1 needs tokens of length at most three.
Anything over a fixed alphabet: the construction uses about 7L² distinct letters, and over a fixed alphabet the best upper bound we know of is 5/8.
That the witness is optimal: the ratios in the table are BPE/witness.
Anything about practical tokenisers with pre-tokenisation; the model is the abstract one of Kozma and Voderholzer.

The constant (1−e⁻²)/2 also appears in Zouhar et al. (2023) as their curvature bound at an estimated curvature of 2 on English text. The paper is AI-assisted; its disclosure section says how. It has not been peer reviewed.