Tokenization and the Noiseless Channel (2023)

Abstract: Subword tokenization is a key part of most NLP pipelines. However, little is known about why some tokenizer and hyperparameter combinations lead to improved downstream model performance over others. We propose that good tokenizers lead to efficient channel usage, where the channel is the means by which some input is conveyed to the model and efficiency can be quantified in information-theoretic terms as the ratio of the Shannon entropy to the maximum entropy of the subword distribution. Nevertheless, an optimal encoding according to Shannon entropy assigns extremely long codes to low-frequency subwords and very short codes to high-frequency subwords.Defining efficiency in terms of Rényi entropy, on the other hand, penalizes distributions with either very high or very low-frequency subwords.We posit that (1) extremely high-frequency subwords are problematic because their meaning is not distinct and (2) that low-frequency subwords may not appear frequently enough for their meaning to be learned properly; encodings that induce unigram distributions with either can harm model performance. In machine translation, we find that across multiple tokenizers, the Rényi entropy has a very strong correlation with BLEU: 0.82 in comparison to just -0.30 for compressed length.

## introduction tokenization, the practice of breaking up text into words or subword pieces, or more generally, tokens, 1 is often the first step in an nlp pipeline. a wide variety of tokenization functions have been proposed in the nlp literature @xcite @xcite . and, indeed, research on developing a good tokenization function continues because how one tokenizes may have a large impact on model performance in the downstream task. for instance, gowda and may (2020) note bleu ranges from 28 to 37 just by changing the size of the vocabulary in their machine translation (mt) pipeline. a direct extrinsic evaluation of a tokenization function, we release the tokenization-scorer package (app. b). 1 to avoid ambiguity, we eschew the common expressions word and subword and, instead, adopt the term token to mean an element of the vocabulary after tokenization. we formally define token in §2. however, is computationally intensive: one first has to retokenize the corpora (generally quick), but then retrain the nlp model (often computationally intensive) to evaluate the effect. for this reason, characterizing the intrinsic properties of a good tokenization function has practical benefits @xcite . our paper takes an information-theoretic approach to characterizing a good tokenization function. following @xcite , we contend that tokenization may be fruitfully viewed as determining a good dictionary code for a language. fortunately, dictionary codes are equipped with a natural intrinsic metric of utility (expected code length) whereas there are many ways to extrinsically measure the tokenization quality. for simplicity and in line with previous research, we choose a specific downstream task metric: bleu @xcite in the domain of mt. 2 we hypothesize that, ceteris paribus, downstream task metrics should correlate with the expected code length of the unigram token distribution. while not immediately intuitive, the motivation is that there is a theoretical connection between the expected code length (under an optimal encoder) of a token distribution and that distribution's shannon entropy: the latter gives us a lower bound on the former. and given a fixed vocabulary size, higher entropy token distributions are more desirable because they are more balanced, i.e., there are fewer tokens that occur too rarely or too frequently. this characteristic should in turn balance a model's ability to learn representations for the entire vocabulary, which requires exposure to enough instances of each token while also penalizing the use of very frequent character sequences as tokens, which is often inefficient due to their lack of distinct meaning. yet when using shannon entropy as our metric of a distribution's balance, the optimal token distribution may still include a large number of in-frequent tokens. this behavior may be undesirable for a number of reasons that we subsequently discuss. accordingly, we formulate the compression principle, which states that downstream task metrics, e.g., bleu, should correlate with the expected code length subject to a penalty for long codewords (which correspond to infrequent tokens). consequently, we introduce a more nuanced formulation of efficiency that employs rényi entropy @xcite , foot_1 whose hyperparameter α allows us to penalize the use of long codes to varying degrees. in the experimental portion of our paper, we predict the performance of mt models. we find that the channel efficiency with rényi entropy with α = 2.5 yields a pearson correlation of 0.78 with bleu on @xmath0. this stands in contrast to shannon entropy or expected sequence length, which yield pearson correlations of only 0.22 and -0.30, respectively. we also provide an easy-to-use package to score tokenizations. see app. b for usage instructions. ## tokenization tokenization is generally defined informally as the breaking up of text into a sequence of tokens which are then encoded into a machine-interpretable format. however, to proceed with our analysis, we require a more formal treatment. first, we assume that there exists an alphabet, a finite, non-empty set of characters σ. we call a string of characters σ = ⟨σ 1 σ 2 • • • σ n ⟩ ∈ σ * a text. in this formulation, we assume that the alphabet σ includes all characters, including punctuation and a distinguished white space character. finally, an unordered multiset of texts {σ 1 , . . . , σ m } ⊂ σ * is termed a corpus of size m . we denote the true distribution over all texts as p σ * . every p σ * induces a marginal distribution over σ, which we call the σ-unigram distribution: furthermore, for our purposes, it is useful to restrict tokenization functions to those that are invertible (bijections), i.e., rules where we can undo the tokenization. this way, the original text can be reconstructed and no information is lost during tokenization. example 2.1. any injective tokenization function, i.e., mapping different inputs δ ′ , δ ′′ to different outputs σ ′ , σ ′′ , satisfies our requirements. as a counter example, consider a tokenization function t 1 for which t 1 (two_cows) = ⟨two,_, [unk]⟩ and t 1 (two_birds) = ⟨two,_, [unk]⟩. the t 1 's lack of injectivity prevents us from recovering the original text from the token sequence ⟨two,_, [unk]⟩. because of our restriction to invertible tokenization functions, with a change of variable we can convert the distribution over texts in σ * into one over token sequences δ in d in a straightforward manner: p ∆ * (δ) = p σ * (t -1 (δ)). note that the pushforward p ∆ * (δ) induces a distribution over ∆ * but with support limited to d. in applied nlp, there is currently no widely accepted notion of the intrinsic quality of a tokenization function. rather, practitioners are generally interested in its extrinsic performance, i.e., the performance of a model trained on a corpus tokenized using a certain tokenization function. under such an evaluation, given two tokenization functions, the one that enables better performance on the downstream task is taken to be better. however, gauging the quality of a tokenizer function in this manner is computationally expensive. thus, we develop an information-theoretic intrinsic evaluation. ## communication in a noiseless channel our analysis of tokenization schemes relies on the following framing: our ultimate goal when tokenizing a text σ ∼ p σ * is the transmission of this text across a hypothetical channel. to perform this feat, we first tokenize σ into a sequence in d ⊆ ∆ * . we then encode each token in ∆ as a sequence of symbols from the set {1, . . . , b}, where b is determined by the channel. our goal is to analyze the properties of tokenization schemes that lead to models with good downstream performance. in the case of a noisy channel, we seek an encoding scheme that will help ensure that σ is resilient to noise in addition to efficiently encoding σ. however, in the noiseless case, we only care about efficiency. we can assume that we are working with a noiseless channel because, in the process of encoding data, no information is ever altered by a stochastic process. in this case, one can equivalently think of noiseless channel encoding as compression. thus, our analysis proceeds by considering the efficiency of different tokenization functions as if our goal is to use them to communicate over a noiseless channel. to this end, we first discuss the conditions for building such an encoding and then discuss the concept of efficient channel usage. definition 3.1. a token-level encoder enc ∆ is a function enc ∆ : ∆ → {1, . . . , b} * that maps every token δ ∈ ∆ to a string of symbols in base b, which we call a codeword. we can naturally lift the tokenlevel encoder to a sequence-level encoder using concatenation as enc ∆ (δ) = |δ| @xmath1. 4 in order to be able to uniquely decode a string δ, we further require that enc ∆ produces prefix-free foot_3 codes for all tokens in ∆. as an example, huffman encoding provides a fast and nearly optimal (in a sense to be discussed in the subsequent section) method to construct prefix-free codes @xcite . example 3.2 (one-hot encoding). consider a tokenization alphabet ∆. in nlp, when @xmath2, the most straightforward way of encoding the n th element of ∆ is a vector of zeroes with length |∆| with 1 on position n. ## rényi efficiency definition 3.8, the standard definition of efficiency, is based on shannon entropy. upon closer inspection, we see it linearly penalizes the use of long codes. to see why, consider a case where the distribution changes such that the entropy increases by one. then, the upper-bound for the expected code length provided by an optimal encoder also increases by one. however, in some cases, we may wish to assign a non-linear cost to code length, e.g., there may be a non-linearly higher cost for decoding longer codes. in the context of choosing the vocabulary for a model, this corresponds to our desire to avoid inducing tokens that occur very infrequently because there may not be enough examples of them in the training data for the model to learn. to add an additional degree of freedom to accommodate such preferences @xcite generalizes the measure of expected code length to discounted expected code length for a hyperparameter s as follows: 7 beyond the limiting cases, for @xmath3, ∞) \ {0}, we further note that l (s) enc ∆ (p ∆ ) is a monotonically increasing function of s. the larger our value of s, the more disproportionately l (s) enc ∆ (p ∆ ) increases as a function of the longest codeword, which often corresponds to the encoding of a low-frequency character in a good code because high-frequency tokens are assigned the shorter codes in order to minimize the expected code length. for large enough s, this has the effect of encouraging all codewords to be roughly of equal length. @xcite sought an analogue of shannon's coding theorem for l (s) enc ∆ (p ∆ ) where s ̸ = 0. as it turns out, there is a deep connection with the rényi entropy. definition 4.1. the rényi entropy of order α > 0 is defined as prima facie, rényi entropy bears some semblance to l (s) enc ∆ (p ∆ ). to see this, consider the limiting cases. at α = 0, we have finally, we have h 1 (p) = h(p), i.e., α = 1 corresponds to shannon entropy, another result which can be shown by l'hôpital's rule. these examples suggest the correspondence α = (1 + s) -1 , which fits the three cases considered, e.g., note that α = 0 when @xmath4. moreover, this is exactly the intuition we argued for above: when α = 0, we encode tokens with codewords of the same length which follows from minimizing the length of the longest codeword. on the other hand, when @xmath5, we encourage shorter codes for high-probability tokens. this case corresponds to α = ∞. we now prove that, similarly to how h(w ∆ ) provides bounds for l enc ⋆ ∆ (p ∆ * ) in theorem 3.7, h α (w ∆ ) provides bounds for l (s) enc s ∆ (p ∆ * ), where enc s ∆ is an encoder optimal with respect to a given @xmath6. we term such an encoder s-optimal. theorem 4.2 (generalization of @xcite ). let h α be the rényi entropy of order α and let l (s) 12 )) be the discounted expected code length for the encoder enc ∆ , where @xmath7. moreover, let w ∆ be a ∆-valued random variable with law p ∆ . then for an s-optimal tokenlevel encoder enc s ∆ , the following bound holds on the discounted expected code length: proof. proof in app. c. ■ note that we have further generalized campbell's (1965) result by allowing some negative values for s, namely, @xmath8. as a result, we can induce additional non-linear weight on too short codes as opposed to only long codes. now we generalize the efficiency with respect to shannon entropy to rényi entropy. let enc s ∆ be an s-optimal token-level encoder over token alphabet ∆. note that several terms from our prior notation can now be expressed in terms of enc s ∆ , i.e., enc ⋆ ∆ = enc 0 ∆ and enc u ∆ = enc ∞ ∆ . theorem 4.3. let α = (1 + s) -1 and p ∆ * be a distribution over ∆ * , and let p ∆ be the unigram distribution induced by p ∆ * (eq. ( 1 )). then, the following inequality holds for an s-optimal sequence-level encoder enc s ∆ based on token-level encoder enc ∆ : ∆ → {1, . . . , b} * . proof. proof in app. c. ■ definition 4.4. let p σ * be a distribution over σ * , let t : σ * → ∆ * be a tokenization function, and let p ∆ * be the distribution over ∆ * induced by t. the rényi efficiency of t at α is defined as the rényi efficiency can be easily upperbounded in a similar manner to the shannon efficiency. theorem 4.5. let p σ * be a distribution over σ * , let t : σ * → ∆ * be a tokenization function, and let p ∆ * be the distribution over ∆ * induced by t. then, for an s-optimal token-level encoder enc s ∆ lifted to the sequence-level, the rényi efficiency of t at α is upper-bounded by proof. proof in app. c. ■ to provide more intuition of why the non-linear penalization in rényi efficiency makes for a good measure of distribution balance, we offer a worked example in example e.1. ## the compression principle in previous sections, we discussed how different tokenizers lead to token distributions of varying properties. now, we add the last piece necessary to link the downstream performance of a system with the choice of a tokenizer. ## experiments we now seek empirical evidence for hyp. 5.1. we focus on mt, where a standard automatic evalu-ation metric is bleu @xcite . we use the @xmath9. the specifics of the mt system, data and evaluation are described in app. d. we consider two different experimental manipulations. first, we experiment with various modifications of the popular byte-pair encoding (bpe) tokenizer @xcite to control its compression rate. the details are discussed in §6.1. second, we experiment with a variety of tokenization schemes: unigram @xcite , wordpiece @xcite , @xcite and morfessor @xcite @xcite . the details are discussed in §6.2. note that throughout our experiments, we make the simplifying assumption of cov l enc s ∆ , @xmath10. it simplifies the upper bound of eff(p σ * , t) (from theorem 3.9) to ⌈h(w ∆ )⌉ log |∆| and the upper bound of eff α (p σ * , t) (from theorem 4.5) to ⌈hα(w ∆ )⌉ log |∆| . from our preliminary results, cov l enc s ∆ , l is negative and small. we leave its more accurate approximation, which requires a rényi analogue of huffman coding as in @xcite , to future work. ## conclusion our paper presents a new information-theoretic approach to characterizing a good tokenization scheme. we contend that the rényi efficiency of the unigram distribution that a tokenization scheme produces is a principled measure of the tokenization quality. to test this claim, we evaluate a large set of tokenization schemes, with varying vocabulary sizes and produced by different tokenization schemes. we observe how the rényi efficiency of these different tokenizations relates to the performance of a downstream mt model. we find that, for an appropriate choice of the parameter α, this new metric has a very strong pearson correlation with bleu: 0.78 in comparison to just -0.32 for baseline sequence length. from a theoretical perspective, this property can be connected to a penalization of token distributions that are too unbalanced, having, in particular, very high-frequency tokens. this finding is in line with the more general principle that compression is connected with learnability. our framework also has practical benefits as it allows for an intrinsic evaluation of tokenization functions.