BPE Gets Picky: Efficient Vocabulary Refinement During Tokenizer Training (2024)

Abstract: Language models can greatly benefit from efficient tokenization. However, they still mostly utilize the classical Byte-Pair Encoding (BPE) algorithm, a simple and reliable method. BPE has been shown to cause such issues as under-trained tokens and sub-optimal compression that may affect the downstream performance. We introduce PickyBPE, a modified BPE algorithm that carries out vocabulary refinement during tokenizer training by removing merges that leave intermediate “junk” tokens. Our method improves vocabulary efficiency, eliminates under-trained tokens, and does not compromise text compression. Our experiments show that this method either improves downstream performance or does not harm it.

## introduction tokenization is a relatively understudied area, but it can greatly impact model performance and efficiency @xcite @xcite @xcite @xcite @xcite . vocabularies should be efficient, as every additional token in the vocabulary increases the number of embedding parameters, and thus the model size. each vocabulary item should contribute enough to model performance to justify the use of parameters. in this paper, we focus on byte-pair encoding (bpe; @xcite ) tokenizers. bpe tokenization works by breaking the text down into each of its characters or bytes and then building tokens in the vocabulary through a series of merges. the result of each merge must be stored as a token in the vocabulary. tokens which are used only to execute merges are sometimes referred to as intermediate "junk" tokens @xcite . an example is shown in figure 1 . interme-*equal contribution figure 1 : an example of a series of merges to produce the token kentucky. pre-merge token frequencies are shown in circles. in the vanilla bpe algorithm, entucky should also be stored in the vocabulary, whereas it is redundant after the merge. in this example, intersection over self (ios) effectively captures the intermediate token, as ios(entucky) ≥ @xmath0.9. in addition to efficiency, we consider other model behaviors that may be driven by tokenization. @xcite recently showed that very low-frequency tokens in the vocabulary may be under-trained by a model. this leads to worse downstream performance and unwanted outputs, such as hallucinations. under-trained tokens -also called "glitch tokens" @xcite @xcite -can also potentially be exploited to circumvent safety measures through the use of these out-of-distribution items. vocabulary trimming, which entails removing items from a tokenizer's vocabulary, has been proposed as a method of decreasing the number of unnecessary tokens, e.g., language-or domainspecific tokens. trimming has been shown to reduce the number of embedding parameters without degrading downstream performance @xcite . under-trained token indicators were shown to be correlated with token frequency in the training corpus, where less frequent tokens are more likely to be under-trained @xcite . vocabulary trimming, thus, is well suited to address the issue of under-trained tokens. vocabulary trimming has mostly been implemented as a procedure taking place after tokenizer training @xcite . as a result, it is difficult to determine the vocabulary size in advance, as it is not known beforehand how many tokens will be removed by the trimming procedure. setting a fixed vocabulary size might be important, for example, for increasing training throughput @xcite . in this paper, we introduce pickybpe foot_0 -a modified bpe tokenizer that implements vocabulary refinement during tokenizer training. unlike other trimming procedures, pickybpe effectively removes intermediate tokens once they become useless and seamlessly creates a vocabulary of the desired size without data-specific heuristics. our method leads to more efficient usage of a limited vocabulary and, thus, of the embedding parameters. we show that our method leads to equal or better performance on a downstream translation task compared to standard bpe (section 4). furthermore, we reduce the number of tokens that are likely to be under-trained (section 5). this frees up space for higher-quality tokens. due to the improved quality of the fixed-size vocabulary, pickybpe does not compromise text compression (section 6) unlike other trimming methods, which makes it a good candidate for practical use. ## related work several common alternatives to bpe tokenization implicitly address the issue of intermediate lowfrequency tokens. for instance, wordpiece tokenization @xcite is based on a series of merges akin to bpe, but along with the frequency of the token pair being merged, it also takes individual token frequencies into account. thus, the tokenizer is less likely to add merges that would result in redundant tokens. however, this does not guarantee that the tokenizer adds merges in an optimal order, nor does it facilitate the retrospective removal of intermediate tokens that might eventually appear. another popular algorithm is unigram tokenization @xcite used in sentencepiece @xcite . the core of this algorithm is different from bpe-like solutions. unigram works by creating a large vocabulary and iteratively pruning it until it reaches the desired size. the pruning is performed according to how much the token removal affects the likelihood of the subword sequence, and takes into account individual token frequencies. intermediate tokens are also less likely to appear in such a scenario, which might suggest that unigram tokenization implicitly performs a form of vocabulary trimming. there also exist several proposed modifications to bpe, which address the issues raised in section 1. bpe-dropout was proposed to mitigate the issue of rare subwords by dropping merges randomly during tokenizer training @xcite . this method regularizes bpe training to expose the model to alternate tokenizations of the same strings, making it more robust to noisy input, such as misspellings. bpe-dropout also helps in reducing the under-training of low-frequency tokens. while it may lead to better training for low-frequency or intermediate tokens, those tokens are never used during model inference. therefore, this method still leads to unused embedding parameters and ultimately does not improve vocabulary efficiency. @xcite use an absolute frequency cut-off to prevent very low-frequency tokens from being added to the vocabulary. similarly, @xcite propose a stopping criterion in order to select the optimal vocabulary for bpe. the authors propose a maximum likelihood constraint, a point at which bpe stops adding merges during training if a merge decreases the overall likelihood of the token sequence. building on this work, @xcite implement a vocabulary trimming method for bpe. the authors propose removing low-frequency tokens after tokenizer training by manually choosing an absolute threshold value. the choice of threshold, therefore, is specific to a given dataset and vocabulary size. their method reduces the vocabulary size without significantly reducing downstream translation performance. in some cases, when they show the greatest task improvement, they find an increase of over 13% in sequence length, i.e., text length in number of tokens. better compression has been shown to correlate with better model performance @xcite @xcite and lead to faster inference time @xcite @xcite . we argue that a major drawback of the method proposed by @xcite is worse compression. e ← e + {remove, x 2 } ▷ new event 14: end if 15: update c based on events from this iteration 16: return v, c, e tify the issue of intermediate ("scaffold") tokens and introduce scaffold-bpe. the authors propose to identify intermediate tokens when they are below the current range of frequencies during the tokenizer training. their method does not allow regulating the strength of scaffold-bpe, unlike our method, which uses a threshold hyperparameter (see section 3). additionally, scaffold-bpe functions by first tokenizing the input text with both the vocabulary and scaffold tokens, then later splitting the scaffold tokens into the minimal valid token sequence. since this method is a post-processing technique and the final result does not reflect the training process, this inference strategy leads to inaccuracies in tokenization and worse compression (see appendix a). another contemporaneous work by bauwens and delobelle (2024) also proposes a method of pruning merges that lead to undesired segmentation and underused vocabulary items. this method differs in two key ways from previous approaches. it allows merges of more than two tokens and uses a semi-supervised method to determine which merges to remove based on manually annotated language-specific morphological segmentations. the latter makes it hard to generalize this method to other languages, especially in multilingual settings. ## pickybpe our method is a modification of the original bpe algorithm @xcite . the intuition behind pickybpe is that we can iden- here x 1 and x 2 are the tokens being merged, f t is token frequency, and f p is pair frequency. ios(x 1 | x 1 , x 2 ) shows how often token x 1 occurs as part of a pair {x 1 , x 2 } compared to all occurrences of x 1 . if this value is high, i. e., close to 1, x 1 is highly likely an intermediate token, an integral part of a longer, more meaningful token x 1 + x 2 . adding x 1 + x 2 to the vocabulary makes x 1 redundant and we can consider removing it. ## machine translation experiments to evaluate the downstream performance of our algorithm, we conduct several machine translation (mt) experiments. we train mt models for three translation directions: english-german (en-de), german-estonian (de-et), and ukrainian-estonian (uk-et). 2 with this choice of language pairs, we aim to cover diverse mt tasks of varying difficulty. german and english are related languages and share the same script. this language pair represents an easier translation task. german and estonian use the same script, but are much less closely related, belonging to different language families. translation for this pair should be more difficult. finally, ukrainian and estonian represent the most difficult translation pair in our experiments. these languages are not only distant but also use different scripts. to train the en-de models, we use the training corpus from the wmt16 news translation task @xcite , with newstest2016 corpus for evaluation. for de-et and uk-et, we use the mixtures of parallel corpora assembled by @xcite . we test our method with several thresholds: 0.6, 0.7, 0.8, and 0.9. we did not consider lower thresholds as they would remove too many useful tokens. for the baseline, we chose vanilla bpe, which we obtained by training our pickybpe with @xmath1. we use the transformer-iwslt model from fairseq @xcite for all mt tasks. the architecture and training details can be found in appendix b. for generation, we use beam search with beam size 5 in all our experiments. we use bleu @xcite from sacrebleu @xcite and comet @xcite ) scores for automatic evaluation. we compute paired t-test with bootstrapping foot_2 to test for statistical significance on performance metrics @xcite . smaller vocabularies. first, we conduct experiments on all three language pairs with a small vocabulary size of 8192. we chose such a restrictive setting to make sure all the tokens are sufficiently trained, as the relatively small training datasets we used (∼1-4m sentence pairs) do not necessitate large vocabularies @xcite . the results are presented in larger vocabularies. we also tested pickybpe with larger vocabularies for the en-de task. we used two settings: separate vocabularies for input and output, and joint vocabularies. in both cases, we used total vocabulary sizes 16384, 32768, and 65536. the results for these experiments are presented in ## under-trained tokens we also test whether pickybpe decreases the number of tokens likely to be under-trained. these tokens can be identified by looking for very low l 2 norm of the token embeddings @xcite . we plot l 2 norms for @xmath2.9 in figure 3 and those for the remaining thresholds in appendix d. there are two groups of low-l 2 norm tokens: the first is the low-frequency tokens, which can be seen in the lower left of figure 3a . according to @xcite , this might indicate under-training. there is also a group of the highestfrequency tokens with low l 2 norms (top left of figure 3a ). we posit that these are general-purpose tokens that occur in a wide variety of contexts, and thus their representations are less specific. it has long been observed that high-frequency words are (a) pickybpe tokens when @xmath3.0. the tokens that are present when @xmath4.0 but removed when @xmath5.9 (orange) are generally infrequent and have low l 2 embedding norms, thus the majority of them are likely to be under-trained @xcite . a large portion of tokens removed by pickybpe (figure 3a ) are likely to become under-trained. by contrast, the new tokens added by pickybpe (figure 3b ) have higher l 2 norms and higher probability of occurrence. the high-frequency general tokens are not removed by pickybpe. we argue that pickybpe reduces the likelihood of under-trained tokens and thus the risks associated with them, such as increased hallucinations. we also find that as we lower the threshold for pickybpe, there is a decrease in the left tail of the token frequency distribution, which represents the low-frequency tokens (figure 4 ). trimming methods that involve an absolute frequency cutoff, such as the one used by @xcite , would completely eliminate the left tail and leave an abrupt drop in the distribution. we observe that pickybpe preserves the overall distribution and does not eliminate the left tail. this shows that pickybpe is fundamentally different from posttraining trimming of low-frequency tokens. ## features of pickybpe text compression. text compression is generally considered to be an important aspect of tokenizer evaluation @xcite , and language models that compress more have been shown to perform better @xcite . we use corpus token count (ctc; @xcite to measure compression. ctc, also called sequence length, is the number of tokens needed to represent a given text. the fewer tokens are needed, the better the compression. token qualities. in addition to the above metrics, we compare the tokens themselves. one quality of interest is the proportion of word-initial tokens, which are stored in the tokenizer with an underscore at the beginning to represent a space character. yehezkel and pinter (2023) also notice that their trimming procedure leads to an increased number of word-initial tokens. in upon inspection of the added tokens, we see that many of the word-initial tokens are also complete words, for example _renovated, _overcoat, _cognition, and _unconventional. increased rates of word-initial tokens may be indicative of improved token quality. many of the tokens removed by pickybpe were intermediate, much like entucky (figure 1 ). these tokens are relatively long and only occur in the context of a longer token that is also present in the vocabulary. often, these tokens are missing only one or two characters compared to the full word. we find word-initial and word-medial intermediate tokens, e.g., _chicag, _algorith, roprietary, omenclature (cf. @xcite . following @xcite , we also measure mean token length. they argue that longer mean token length is associated with gold-standard morphologically-aligned tokenization, and thus with better token quality. additionally, longer tokens on average will lead to increased compression, as a text of a fixed length can be represented with fewer longer tokens. we find that the mean token length slightly, but consistently, increases as we lower the ios threshold (see we also compare pickybpe with unigram tokenization in ## discussion we provide a series of experiments that illustrate key properties of pickybpe. to put these results into perspective, we wish to reiterate two core aspects of the provided experiments: first, there is no universal methodology that could assess tokenizer quality; second, the inefficiencies associated with under-trained tokens discussed by @xcite depend on the size of vocabulary relative to the size of training data. evaluating tokenizers. it is not always clear how to best compare different tokenizers @xcite . one approach is training models for each tokenizer and evaluating downstream performance, e.g., @xcite . however, these results may be driven by confounding factors, such as differences in compression leading to the model effectively being trained on less text @xcite , and downstream results may also be taskspecific. the second general approach to evaluating tokenizers is to evaluate some quality of the tokenizer's output such as compression, similarity of tokenizer boundaries to morphological boundaries @xcite , or cognitive plausibility of tokens @xcite . there is no consensus about which metric(s) provide the best overall estimation of tokenizer quality. role of under-trained tokens. we achieved better or equal performance on machine translation with small vocabularies compared to the vanilla bpe, which suggests that removing under-trained tokens benefits downstream performance. with larger vocabularies, we also saw improvement from our method judging by the values of the comet metric. however, the largest vocabulary sizes we experimented with were too large for the rather small datasets we used, which led to degraded overall performance regardless of the tokenizer choice. to see the fair improvement with larger vocabulary sizes, one might consider testing pickybpe as a tokenizer for an llm, where vocabulary size will be significantly scaled up together with the size of the training data. in this scenario, we also expect to see the benefits of removing under-trained tokens, which were investigated by land and bartolo (2024) specifically on the example of llms. we leave this exploration for future work. ## conclusion in this paper, we propose pickybpe, a novel tokenization algorithm that refines the vocabulary during tokenizer training by removing intermediate tokens. our machine translation experiments show that this algorithm either matches or surpasses the downstream performance shown by vanilla bpe on the same data, which we can extrapolate to larger vocabularies and data given enough training. our method also mitigates the issue of under-trained tokens, efficiently removing them during tokenizer training, and improves token quality and text compression, filling the freed vocabulary space with higher-frequency and higher-quality tokens. these factors suggest that pickybpe can be considered for larger models, e.g., llms, to improve downstream performance and safety and avoid undesired behavior, e.g., hallucinations.