Assessing the Importance of Frequency versus Compositionality for Subword-based Tokenization in NMT (2023)

Abstract: Subword tokenization is the de-facto standard for tokenization in neural language models and machine translation systems. Three advantages are frequently put forward in favor of subwords: shorter encoding of frequent tokens, compositionality of subwords, and ability to deal with unknown words. As their relative importance is not entirely clear yet, we propose a tokenization approach that enables us to separate frequency (the first advantage) from compositionality, thanks to the use of Huffman coding, which tokenizes words using a fixed amount of symbols. Experiments with CS-DE, EN-FR and EN-DE NMT show that frequency alone accounts for approximately 90% of the BLEU scores reached by BPE, hence compositionality has less importance than previously thought.

## introduction tokenization into subwords has become an unchallenged standard used in virtually all nmt systems and language models. since the proposal by @xcite to use byte-pair encoding (bpe) @xcite to create subword vocabularies, followed by the use of a unigram language model and the sentencepiece implementation @xcite , no alternative models have taken over. while subwords have been empirically demonstrated to outperform character and wordlevel tokenization @xcite @xcite , the factors contributing to their success have not been fully understood yet. some studies have investigated the performance of subwords with regard to compression @xcite , suggesting that better compression may be associated with improved performance. however, other factors such as compositionality have yet to be thoroughly explored. in this paper, we use an alternative algorithm for creating subword vocabularies, which retains only one of the features that have been invoked to explain the effectiveness of bpe, namely the fact that frequent words are encoded as unique subwords, while less frequent ones are encoded using several subwords, possibly up to the character level. the algorithm is based on huffman coding @xcite , a different text compression method than the one used by bpe. the algorithm differs from bpe in two key aspects: while certain bpe subwords convey compositional linguistic properties (e.g., meaning or morphology), huffman coding is fundamentally non-compositional, and cannot tokenize words not seen during training. when using huffman coding to tokenize data for transformer-based mt, we reach scores that are within 10-12% of those obtained using bpe when measured by bleu and within 4-8% when measured by comet, for vocabulary sizes of 32k symbols. this demonstrates that the main factor accounting for the success of bpes is word frequency, and not subword compositionality. our main contributions are: ## subword tokenization based on huffman coding we now introduce an alternative subword tokenization method which decouples compositionality from frequency, and implements only the second aspect. this method will enable us to understand which of these aspects has the largest impact on the performance of nmt. just as bpe was originally inspired by a text compression algorithm, we transform here input and output texts into series of symbols using an adaptation of @xcite frequency-based compression algorithm. ## nmt using huffman coding: results in this section, we show that huffman coding is a viable tokenization method, we study the impact of the number of available symbols on the translation quality, and compare the method with a purely frequential baseline. we first investigate how translation quality changes according to the vocabulary size, which is the main hyper-parameter of the method. if many symbols are available, then many frequent words will be encoded with a single symbol. conversely, fewer symbols result in most of the words being encoded with two or more symbols. figure 2 below illustrates this property for huffman codes with respect to bpe. the scores obtained with huffman coding on cs-de nmt with various numbers of symbols, shown in the first five lines of we studied the influence of several hyperparameters on the cs-de bleu scores when using 1,000 symbols for huffman coding. as shown in ## huffman coding versus bpe in order to compare bpe with huffman models, we tokenize source and target sides jointly for each pair using bpe from the sentencepiece toolkit (see footnote 1) with an increasing number of merges: 2k, 4k, 8k, 16k, and 32k. we compare first the vocabularies resulting from bpe with those from huffman coding in terms of the number of symbols per token. the histograms of the numbers of tokens having respectively 1, 2, 3, and up to 10 symbols / subwords are shown in figure 2 , side-by-side for huffman coding (left) and for bpe (right), for each vocabulary size. as the vocabulary size (or number of symbols) grows, tokenization results become more similar across the two methods, with more than 3/4 of the tokens being kept as unique symbols. while two is the maximum number of symbols per token for huffman coding, by construction, we see that for bpe some tokens are segmented into 3 or more subwords (up to 10, although their number is too small to be seen in the figure). these observations support our claim that huffman coding captures similar frequency-related information as bpe, while by design it does not capture compositionality. turning now to nmt scores, finally, unknown words are also likely to limit the performance of huffman coding, although their number is very small in the test data. there are 0.55% unknown tokens in the cs source for cs-de, 0.46% in the en source for en-de, and none in the en source for en-fr. interestingly, on the decoding side, the vast majority of symbol combinations generated by our nmt models correspond to actual leaves of huffman trees: the percentages of unknown combinations of symbols among the total output tokens are respectively 0.07%, 0.04% and 0.02% for cs-de, en-de, and en-fr. such combinations cannot be decoded and are therefore skipped. ## conclusion in this paper, we have presented an original method for text tokenization, which exploits the text compression property of huffman trees, and therefore takes into account the frequencies of subwords, but does not rely on their compositionality. we have framed these notions and, based on the comparison of scores obtained with huffman coding with those obtained with bpe, we have defended the claim that most of the gains brought by bpe are due to the appropriate consideration of subword frequency, and comparatively much less to compositionality. these results tend to downplay the importance of compositionality, which is often mentioned as an advantage of bpe, and contribute to the understanding of the remarkable effectiveness of this method. we hypothesize that text compression methods might provide inspiration, in the future, for even more effective tokenization methods, given that the state-of-the-art in compression has made significant progress since bpe. especially, prediction by partial matching seems a promising candidate, but awaits a principled solution to relate tokens to coding symbols.