A Formal Perspective on Byte-Pair Encoding (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/sigma*(1-e(-sigma))-approximation of an optimal merge sequence, where sigma is the total backward curvature with respect to the optimal merge sequence. Empirically the lower bound of the approximation is approx0.37.We provide a faster implementation of BPE which improves the runtime complexity from O(NM) to O(N log M), where N is the sequence length and M is the merge count. Finally, we optimize the brute-force algorithm for optimal BPE using memoization.

## introduction byte-pair encoding (bpe) is a popular technique for building and applying an encoding scheme to natural language texts. it is one the most common tokenization methods used for language models @xcite @xcite as well as for various other conditional language modeling tasks, e.g., machine translation @xcite and chatbots @xcite . despite having been popularized by @xcite in nlp as a tokenization scheme, bpe has its roots in the compression literature, where @xcite introduce the method as a faster alternative to lempel-ziv-welch @xcite ). however, the ubiquity of bpe notwithstanding, the formal underpinnings of the algorithm are underexplored, and there are no existing proven guarantees about bpe's performance. the training and applying of bpe are traditionally presented as greedy algorithms, but the exact optimization problems they seek to solve are neither presented in the original work of @xcite nor in the work of @xcite . we fill this void by offering a clean formalization of bpe training as maximizing a function we call compression utility foot_0 over a specific combinatorial space, which we define in definition 2.3. unexpectedly, we are then able to prove a bound on bpe's approximation error using total backward curvature σ(µ ⋆ ) @xcite . specifically, we find the ratio of compression utilities between the greedy method and the optimum is bounded below by 1 σ(µ ⋆ ) (1e -σ(µ ⋆ ) ), which we find empirically ≈ 0.37 for σ(µ ⋆ ) = 2.5. our proof of correctness hinges on the theory of submodular functions @xcite . 2 indeed, we are able to prove that compression utility is a special kind of submodular function @xcite over a constrained space. and, despite the presence of the length constraint, which we expound upon formally in §3, we are able to prove a similar bound to 1-1 /e as in the unconstrained case @xcite . additionally, we give a formal analysis of greedy bpe's runtime and provide a speed-up over the original implementation @xcite . our runtime improvement stems from the development of a nuanced data structure that allows us to share work between iterations of the greedy procedure and that lends itself to an amortized analysis. specifically, given a string with n characters with a desired merge count of m (usually n ≫ m ), our implementation runs in o (n log m ), an improvement over the o (n m )time algorithm presented by @xcite and the o (n log n ) analysis presented by @xcite . finally, our formalism allows us to construct an exact program for computing an optimal solution to the bpe training problem. unfortunately, the algorithm runs in exponential time, but it is still significantly faster than a naïve brute-force approach. our work should give nlp practitioners confidence that bpe is a wise choice for learning a subword vocabulary based on compression principles. in general, such constrained submodular maximization problems are hard @xcite ). while we do not have a proof that the bpe problem specifically is np-hard, it does not seem likely that we could find an efficient algorithm for the problem. regarding the runtime, our implementation of greedy bpe runs nearly linearly in the length of the string which would be hard to improve unless we plan to not consider the entire string. ## formalizing byte-pair encoding we first provide a brief intuition for the bpe training problem and the greedy algorithm that is typically employed to solve it. then, we will develop a formalization of bpe using the tools of combinatorial optimization, rather than as a procedure. consider the string in example 1: picked pickled pickles. we wish to create a compact representation of this string, where compactness is quantified in terms of the number of symbols (i.e., vocabulary units) required to precisely encode the string. the free parameter is the vocabulary that we will use to construct this representation, albeit the total size of the chosen vocabulary is often a constraint. 4 in our example, let's assume we are allowed a maximum number of 13 symbols in the vocabulary foot_4 with which we can encode our string. the question is: "how can we select these symbols to achieve our goal of compactness under this constraint?" let us first consider the simple choice of using all the characters present in the string as our vocabulary: this scheme leads to a representation with a length of 22 units, including spaces. in order to decrease this length (while retaining all information present in the original string), we would need to add an additional symbol to our vocabulary: one with which we can replace co-occurrences of two symbols. but how should we choose this entry? one strategy-the one employed by the bpe algorithm-is to use the concatenation of the adjacent units a b that occur with the highest frequency in our string; all occurrences of these adjacent units could then be replaced with a single new unit ab. we refer to this as a merge, which we later define and denote formally as @xcite . in example 1, the first merge is @xcite , and leads to a representation of length 19 with vocabulary size of 9+1. we can iteratively repeat the same process; the application of 5 total merges results in the vocabulary units pick, pickl, ed, e, and s. these subwords foot_5 allow us to represent our original string using just 9+1 symbols. if we continued merging, the text representation would become shorter (in terms of number of symbols required to create the representation) but the merge count (and vocabulary size) would grow. therefore, the number of merges m , or also the merge count, is a hyperparameter to the whole procedure. the procedure outlined above is exactly the greedy algorithm for bpe proposed by @xcite . we provide a minimal implementation in python in code 1. we will define the compression gain of a merge at any given step of the algorithm, corresponding to the number of occurrences where a merge can be applied. the compression gain of a merge does not always correspond to the frequency of adjacent merge components in that string, due to possible overlaps. consider, for instance, the string aaa and the merge @xcite . the frequency of aa is 2, but the merge can be applied only once ([a, a]a). while @xcite and @xcite admit overlapping pair counts, @xcite 's popular implementation adjusts the algorithm to disregard the overlaps. we stick to the latter, which is more suitable from the optimization standpoint adopted here. ## a greedy approximation of bpe we demonstrate that, for any string @xmath0, the following bound holds ## a runtime speed-up we now introduce a speed-up of the greedy bpe algorithm. assuming constant-time comparison of strings, finding the maximum pair count over the whole string is o (n ), which is the same as applying one merge. therefore, this implementation has a runtime complexity of o (n m ). a large amount of time in the slow bpe implementation, algorithm 2 iterative greedy bpe (faster). inputs: string x, merge count m output: tokenized string x, merge sequence µ example 4.1. consider @xmath1. we can only apply the merge at the beginning of the string, which results in the forest [a, b]ba(cddc) n . however, alg. 2 still scans the entirety of the sequence to recalculate the pair frequencies of @xcite , [d , c] and [c , c ]. this additional work is unnecessary. our idea to speed up alg. 1 stems from the insight that we do not have to iterate over the entire sequence, an o (n ) operation, on each of the m iterations. 12 indeed, on the t th iteration, we show that one only has to do work proportional to the number of new nodes that are added to the forest (alg. 2, line 6). to achieve this, we introduce a more efficient data structure for bpe. 13 our first step is to treat the string as a linked list of subwords, initialized as a linked list of characters, that we destructively modify at each iteration. with each possible merge, we store a list of pointers where the merge operation could happen. the max heap is then sorted by the size of the sets. lines 6 to 14 in alg. 2 show the necessary operations needed to be performed on the linked list. notably remove- figure 2: visualization of linked list representation of the string and the associated priority queue (frequency values in dashed boxes) with merges. nodes in red will be removed in the next step, nodes in green were added in contrast to the previous step and nodes in purple were just added but will be removed. black lines from queue to the string show which nodes to merge. grey lines show which pairs in the priority queue will have reduced frequencies. position removes the specific pair position from the set in the max heap and addposition adds it. see fig. 2 for an illustration of applying a single merge in one place based on the introductory example in example 1. the possible merge pairs are stored with a priority queue with their frequency as the sort key. during one operation, we need to remove the top merge pair and add counts for the newly created possible merge. the cost of one merge then becomes o (r t log m ) where r t is the number of pairs in the string where the merge occurs and log m the complexity of adding and updating frequency of a new merge pair. note that it is not log n , because we are keeping only top-m possible pairs in the heap. at first glance, this suggests the overall runtime of o m @xmath2, therefore o (m n log m ). theorem 4.2. let n be the length of the string @xmath3. then, alg. 2 runs in o (n log m ) time. proof. let r t be the amount of work performed at each iteration modifying the data structure. we additionally do o (log m ) work updating the priority queue on lines 6 to 14 in alg. 2 since it has at most m elements. thus, alg. 2 clearly runs in o m @xmath4. we perform an amortized analysis. for this, we first make an observation about the upper bound on the number of merges and then show amortized analysis. however, for a string x of length n , there are at most n -1 merges that can be applied to x. this implies that m @xmath5. thus, o m @xmath6, which proves the result. ## an exact algorithm in this section, we turn to developing an algorithm for exactly solving the bpe problem, i.e., eq. ( 4 ). we change algorithmic paradigms and switch to memoization. while we are not able to devise a polynomial-time scheme, we are able to find an exact algorithm that is, in some cases, faster than the brute-force technique of enumerating all valid merge sequences. we first analyze the brute-force method of enumerating all valid merge sequences. proposition 5.1. the set of valid merges of length m over a string proof. the proof can be found in app. a. ■ a simple direct enumeration of all possible merge sequences with the time complexity of one merge o (n m ) gives us a brute-force algorithm that runs in o n m min |σ| 2m , n m time. the brute-force program explores all possible sequences of merges-including many that are redundant. for instance, both ⟨[p, o], [h, a]⟩ and ⟨[h, a], [p, o]⟩ induce the same partial bracketing when applied to another merge sequence, as in §2.2. luckily, we are able to offer an exact characterization of when two merge sequences induce the same bracketing. to this end, we provide the following definitions. we use the term transposition to refer to the swapping of items; i.e., a transposition (i, j) over a merge sequence µ refers to the swapping of µ i and µ j . definition 5.2. a pair of merges µ = [µ n , µ m ] and µ ′ = [µ n ′ , µ m ′ ] conflicts if for a symbol @xmath7, x ′ ∈ σ * , the yield of [µ n , µ m ] is xa and [µ ′ n , µ ′ m ] is ax ′ . definition 5.3. a transposition (i, j) is safe if and only if, for all @xmath8, µ k does not conflict with µ j and, for all @xmath9, µ k does not conflict with µ i . a permutation π = ⟨ρ 1 ρ 2 • • • ρ n ⟩, decomposed into transpositions, that maps one valid merge sequence µ to another valid merge sequence π(µ) = µ ′ is safe if and only if all transpositions are safe. informally, definition 5.3 says that for a permutation to produce a valid merge sequence, there should be no conflicts between the swapped merges and all merges in between. for example, given the merge sequence µ = ⟨[a, b], [d, d], [c, a]⟩, the permutation π = ⟨(1, 3)⟩ would not be safe. the reason for this definition is that safe permutations characterize when two merge sequences always give the same results. indeed, for @xmath10, applying the first merge sequence: apply µ (x) = @xcite [c, a]b. in contrast, applying the permuted one gives an alternative outcome: apply π(µ) (x) = @xcite . definition 5.4. two merge sequences µ and µ ′ are equivalent if and only if, for all @xmath11, apply µ (x) = apply µ ′ (x). symbolically, we write µ ≡ µ ′ if µ and µ ′ are equivalent. proposition 5.5. two valid merge sequences µ, µ ′ ∈ m υ σ are equivalent, i.e., µ ≡ µ ′ , if and only if there exists a safe permutation π such that π(µ) = µ ′ . proof. the proof can be found in app. a. ■ in contrast to synthetic examples with a constrained alphabet of, e.g., {a, b, c}, far fewer merge conflicts arise in natural language. we can leverage this to develop a faster algorithm that only explores paths that are not equivalent to each other. we first define the concept of partial ordering between merges. definition 5.6. the merge partial ordering µ ′ ⋗µ ′′ is defined as ¬conflicts all valid merge sequences are equivalent to some merge sequence which is partially ordered using ⋗ so that no neighbouring elements violate this partial ordering. the brute-force algorithm works as depth-first search through an acyclic graph: each state corresponds to a unique sequence of merges and each transition corresponds to appending a merge to the end of the current state's merges. for the improved version, we make sure that only sequences which are ordered using ⋗ are searched and the rest are pruned. the pseudocode for the program is shown in alg. 3. even though the runtime is still prohibitively slow for application, fig. 3 demonstrates how much speed is gained over the brute-force version which explores all states. algorithm 3 exact bpe with memoization guard. removing segments marked with x would result in the brute-force version. inputs: string x, merge count m output: tokenized string x, merge sequence µ ## conclusion in this paper, we developed the formalisms surrounding the training task of bpe, a very popular tokenization algorithm in nlp. this allowed us to prove a lower bound on the compression utility by greedy bpe as 1 -e -σ(µ ⋆ ) . we further analyzed the runtime of the naïve and faster greedy bpe algorithms and provided a speedup for finding an optimal bpe merge sequence. future works should focus on providing either formal guarantees for σ(µ ⋆ ) or studying σ(µ ⋆ ) ′ across natural languages. our work has focused strongly on the formal aspects of bpe. nlp practictioners should not be dissuaded from using bpe for subword tokenization, despite our presentation of examples where greedy bpe fails. indeed, in contrast to synthetic examples on toy alphabet, on real data we made an observation that greedy bpe may be close to optimal. however, it is easy to see that this approximation algorithm is not bounded. for a constant maximum yield width of w, consider @xmath12. the shortest possible output of this algorithm will be µ n . however, an optimal merge sequence can perform additional merge sequences, therefore producing ν n 2 k . the compressions are wn -n and wn -n 2 k and the ratio wn-n wn-n 2 k with lower bound of 0 as supremum. this means that we can construct adversarial example for which the compression given by this algorithm is arbitrarily suboptimal.