Greedy Byte-Pair Encoding Achieves at Least 0.3478 of the Optimal Compression

Byte-Pair Encoding (BPE) compresses a string by repeatedly replacing a most frequent adjacent pair of symbols with a new symbol. With a budget of k merges, Kozma and Voderholzer showed that this greedy rule always achieves at least a third of the optimal compression, and that it can fall to (1 − e^−2)/2 ≈ 0.4323 of it. We prove that BPE always achieves at least 0.3478 of the optimum, for every string, every budget and every tie-breaking rule, against the optimum that may replace any subset of occurrences. This is the first improvement of the lower bound 1/3. The new ingredient is rule determinism: all copies of a rule of the optimum have the same tree. When a greedy replacement destroys three of the optimum's merge points at once, we either move the destroyed central merge to a neighbouring gap, or leave a placeholder (a ghost) whose type is fixed by the optimum's rule. This gives the per-step inequality OPT ≤ 2.5 G_i + 2k gᵢ₊₁, where G_i is greedy's utility after i steps and gᵢ₊₁ the utility of its next merge; interleaving it with the per-step Kozma–Voderholzer inequality beats 1/3. We show that the pair-packing relaxation behind the old bound is tight at 1/3, which is why such a structural ingredient is needed. We also determine the ratio exactly for two merges (3/4), show that it is at most 7/12 for three, and isolate a single inequality that would raise the bound to (1 − e^−2)/2. The supplementary archive contains the finite check used in the proof (Appendix B) and an exact re-check of the explicit instances, with a README; code is MIT-licensed.