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

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 k merges? Kozma and Voderholzer proved that greedy achieves at least one third of the optimal shortening; the best known upper bound is (1-e⁻²)/2 ≈ 0.432. We show that one third is a barrier for their method, which sees the optimum only through a pair packing; we then prove that greedy achieves at least 0.391 of the optimum on every input, with any tie-breaking. The key idea is rule determinism: all copies of a rule of the optimal merge sequence spell the same letters, so when a greedy replacement destroys three of the optimum's merge points, half a unit is refunded on each side. A weaker bound, 0.374, has a short computer-free proof; the full bound uses a computer-checked certificate. We state one per-step inequality that would give the tight constant, and prove it for the first three steps and for optimal tokens of length at most five. The record includes the paper, its LaTeX source, and the code and certificates that reproduce every computed result.