# A Formal Perspective on Byte-Pair Encoding

Vilém Zouhar, Clara Meister, Juan Gastaldi, Li Du, Tim Vieira, Mrinmaya Sachan, Ryan Cotterell

July 2023

### Abstract

Byte-Pair Encoding (BPE) is a popular algorithm used for tokenizing data in NLP, despite being devised initially as a compression method. BPE appears to be a greedy algorithm at face value, but the underlying optimization problem that BPE seeks to solve has not yet been laid down. We formalize BPE as a combinatorial optimization problem. Via submodular functions, we prove that the iterative greedy version is a 1σ(μ⋆)(1−e−σ(μ⋆))-approximation of an optimal merge sequence, where σ(μ⋆) is the total backward curvature with respect to the optimal merge sequence μ⋆. Empirically the lower bound of the approximation is ≈0.37. We provide a faster implementation of BPE which improves the runtime complexity from O(NM) to O(NlogM), where N is the sequence length and M is the merge count. Finally, we optimize the brute-force algorithm for optimal BPE using memoization.

Publication

*Findings of the Association for Computational Linguistics: ACL 2023*

Add the **full text** or **supplementary notes** for the publication here using Markdown formatting.