Byte‑Pair Encoding (BPE) builds a tokenizer by repeatedly merging the most frequent adjacent pair of symbols; its utility is the total reduction in string length after $k$ merges. It was previously known that this greedy rule guarantees at least one‑third of the optimal reduction. We prove that, for any string, any merge budget $k$, and any tie‑breaking rule, the greedy BPE always achieves at least $0.361$ of the optimal reduction, marking the first improvement over the $\frac{1}{3}$ bound. We also explain why $\frac{1}{3}$ was a barrier: the pair‑packing relaxation underlying it is tight, so a better bound must exploit more of the optimal solution’s structure. When the greedy process destroys three optimal merge points at once, one of them can usually be shifted next door because all copies of an optimal rule look alike; the remaining cases are compensated later. Along the way we determine the exact worst‑case ratio for two merges, bound it for three merges, and isolate a single inequality whose proof would settle the problem completely.\n\nReview: This result substantially strengthens the theoretical guarantee for BPE, offering a more reliable compression bound for practical applications and highlighting avenues for further improvement.