Where is the signal in tokenization space? (2024)

Abstract: Large Language Models (LLMs) are typically shipped with tokenizers that *deterministically* encode text into so-called *canonical* token sequences, to which the LLMs assign probability values.One common assumption is that the probability of a piece of text is the probability of its canonical token sequence.However, the tokenization of a string is not unique: e.g., the Llama2 tokenizer encodes ‘Tokens‘ as ‘[Tok,ens]‘, but ‘[Tok,en,s]‘ also represents the same text.In this paper, we study non-canonical tokenizations.We prove that, given a string, it is computationally hard to find the most likely tokenization for an autoregressive LLM, as well as to compute the marginal probability over all possible tokenizations.We then show how the marginal is, in most cases, indistinguishable from the canonical probability.Surprisingly, we then empirically demonstrate the existence of a significant amount of signal hidden within tokenization space.Notably, by simply aggregating the probabilities of non-canonical tokenizations, we achieve improvements across a range of LLM evaluation benchmarks for a variety of architectures, including transformers and state space models.

## introduction autoregressive large language models (llms) generate text by predicting the next word sequentially. a crucial yet often overlooked step in this process is tokenization, whereby each word is broken down into subwords. it allows the model to generate text beyond what it was trained on, enabling open-vocabulary generation. however, this approach also introduces a significant challenge: a given string can be tokenized in exponentially many ways (figure 1 ). for example, this paper's abstract can be tokenized in more than 10 267 ways under the llama2 vocabulary @xcite . while a given string can be tokenized in multiple ways, at inference time, almost all successful modern llms utilize a fixed, or canonical, tokenization: a deterministic, rule-based mapping from text to token sequences @xcite . consequently, it has become commonplace to use this token sequence as a proxy for the underlying text. in particular, the probability of the token sequence is often used in place of the probability of the text (e.g. for evaluation metrics like perplexity), even though these quantities are not necessarily equal. to complicate matters, some language models are pretrained with stochastic tokenizations @xcite , exposing them to multiple ways of tokenizing the same string, with the hope of obtaining models with a more developed understanding of the compositionality of words. in this paper, in the context of modern llms, we ask whether non-canonical tokenizations of a string can provide additional signal at inference time, which would be lost by considering just the canonical tokenization. to this end, we investigate two natural alternatives: finding the most likely tokenization and marginalizing over tokeniza-tions. for example, one natural way to answer a multiple-choice question is to choose the answer with the highest probability conditioned on the question @xcite ; instead of always assuming the canonical tokenizations of the answers, one could compare answers based on the probability of their most likely tokenizations, or alternatively the marginal probability of all possible tokenizations. we first study the problem of finding the most likely tokenization and show that it is np-hard under some mild assumptions. as such, we propose an anytime branch-and-bound algorithm to approximate the most likely tokenization. we find that, for text lengths where the branch-and-bound strategy is practical, the canonical tokenization is usually the most likely one. then we ask the question of whether there is a significant amount of probability mass concentrated on tokenizations other than the canonical. we first observe that as we sample token sequences of varying length from the llm distribution unconditionally, the proportion of canonical tokenizations decreases significantly as the sequence length increases. to further investigate this phenomenon, ideally one would need to compute the marginal probability of all tokenizations for a given string, which we show to be #p-hard. hence, we implement an importance sampling estimator for the marginal probability. surprisingly, despite the extremely large number of non-canonical tokenizations, we empirically find that the estimated marginal probability is usually very close to the canonical tokenization's probability. this raises our last question: does the complete tokenization space add any meaningful signal at all, in addition to the canonical tokenization alone? remarkably, we show that, even for the cases where there is little probability mass on non-canonical tokenizations, they seem to carry some meaningful signal. specifically, we show that for gemma-2b (gemma @xcite , llama2-7b @xcite and mamba-130m @xcite , by employing ensemble strategies for weighting different tokenizations at inference time, we achieve significant performance improvements on challenging llm evaluation benchmarks. contributions. in summary, we show that: (i) while it is tempting to consider computing the marginal probability of a string, this quantity is #p-hard to compute; (ii) in fact, even computing the probability of the most likely tokenization is np-hard; and (iii) while in most cases the marginal probability of a string is practically the same as the canonical probability, non-canonical tokenizations seem to provide some signal to downstream tasks, to the point that we achieve consistent improvement across a range of open source models on q&a datasets. ## related work many previous works have explored tokenization strategies within the llm pipeline, and the (often undesirable) inductive biases they may introduce: for example, in introducing unfairness between languages @xcite , gender bias @xcite , and in performing arithmetic @xcite . some recent works have avoided the many downsides of tokenization by employing byte-level models, but either suffer from slow decoding due to longer sequences @xcite , or rely on token-level models for more efficient generation @xcite . to overcome the limitations of tokenization, prior works have examined (approximately) marginalizing over the distribution of possible token sequences @xcite @xcite . in this work, we analyze modern llms and consider multiple strategies for extracting information from tokenization space; finding that, contrary to prior belief, the signal is present not in the most-likely tokenization or (approximated) marginals, but rather in a mixture of canonical and non-canonical tokenizations. ## an llm induces a distribution over tokenizations let @xmath0, x 2 , . . .) denote a string (a sequence of characters). a vocabulary v is a set of strings that represent subwords, or tokens. a token sequence definition 3.1 (induced tokenization distribution). let x be a string, v a token sequence, and p an llm over vocabulary v. then, the tokenization distribution induced by p is most modern llms make use of tokenizers based on byte-pair encoding (bpe) @xcite , whereby the token vocabulary is initialized with the character vocabulary, and a merge table is initialized to be empty. the method then iteratively counts all pairs of tokens and merges the most frequent pair into a new token. this new token is added to the vocabulary and the merge rule is added to the merge table. this process is repeated until the desired vocabulary size is reached. the resulting merge table specifies which tokens are to be merged into larger tokens, as well as the priority of these merges. in this way, it defines a canonical tokenization procedure as follows: first, a string is split into its constituent characters, then, the pair of adjacent tokens with the highest priority merge rule is combined. this is repeated until no further merge rules from the table are applicable. bpe dropout @xcite ) introduces an additional step during training: when tokenizing a word, merge rules are dropped with some probability. after this dropout phase, merges proceed the same way as bpe. this dropout phase acts as a regularization method that provides robustness to input noise. it also means that language models trained with bpe dropout should assign more mass to non-canonical tokenizations. algorithm 1 compile input string x, vocabulary v, last token v output mdd of all tokenizations of x 1: initialize memoization m : n × @xmath1: if x is empty then return nothing 3: initialize node n 4: for each token @xmath2: add edge from n to c labelled with t 9: memoize m(|x|, t) ← c 10: return n at inference time, for a string x, the tokenizer outputs the canonical tokenization v * (without any dropout), which is then evaluated by the llm to get the canonical probability p(v * , x). note that this probability is one of an exponential number of tokenization probabilities for a particular string. in fact, one can compile a multi-valued decision diagram (mdd) @xcite that represents this combinatorial space for a given string tractably by decomposing and reusing subsequences. this data structure allows one to compute the total number of tokenizations in linear time in the number of edges of the diagram. algorithm 1 shows how to compile an mdd from a string and figure 2 shows an example of an mdd compiled from the string bird. each node in the diagram corresponds to a position in the string, and edges from node i to node j are labelled with the corresponding token x i:@xmath3, x i+1 , . . . , x j ). every path going from the root to a terminal node is a tokenization of x. given what we know so far, a question naturally arises: since we can tractably represent all tokenizations as an mdd, and given that the number of possibilities is exponential, can we efficiently compute the most likely tokenization of a string? and perhaps more interestingly, is it the canonical one, as often is assumed in practice? for more complex autoregressive language models, however, we unfortunately show that computing the most likely tokenization is computationally hard. we formalize this as follows. problem 4.1 (most-likely tokenization). let v denote a token sequence. given a string x, an autoregressive llm p, and a threshold ϵ > 0, the most likely tokenization problem is deciding whether theorem 4.2. the most-likely tokenization problem is np-complete. proof. (sketch) the proof is by reduction from the 3-sat boolean satisfiability problem @xcite . we encode the boolean variables as possible tokenizations of substrings such that there is a correspondence between the probability of the most likely tokenization and the existence of a satisfiying assignment. the full proof is in appendix b. given the llm training regime, a reasonable assumption in practice is that the canonical tokenization is (close to) the most likely tokenization. to empirically verify this claim, we devise a branchand-bound algorithm to search through the mdd in order to find some tokenization whose probability is higher than the canonical. we do so by setting the initial lower bound as the canonical probability, and then pruning paths whose partial probability is below this bound. we set a time budget of 1-hour, after which the search returns the best tokenization at that point. as expected, we find that branchand-bound is quickly overwhelmed by the number of tokenizations as the string length grows. finding the most likely tokenization this way rapidly becomes intractable for longer strings. figure 3 shows the branch-and-bound search time across three llm architectures for the string "language models typically tokenize text into subwords, utilizing a learned deterministic set of merge rules to aggregate tokens." we gradually insert new words and re-run search to visualize its scalability. branch-and-bound always returns the canonical tokenization as the best candidate, despite the exponential number of possible candidates. not only does the canonical tokenization seem to be the most likely one for shorter text, but it also often is overwhelmingly so. figure 4 shows the tokenization distribution for the word tokens under the llama2 model; there are 52 tokenizations, with the canonical taking most of the mass. even though canonical seems to take up a majority of the probability mass in these cases, if we look at generated text from these llms, a sizable percentage of the (unconditionally) generated tokenizations are non-canonical. figure 5 shows canonicity as a function of the number of tokens generated by the language model. as generated text grows larger, the probability of generating non-canonical tokenizations also grows. this is surprising, as it is seemingly in contradiction to earlier evidence. it turns out that, if we investigate these non-canonical generated sequences in more depth, we find that a large majority of such cases are non-english, with a large portion consisting of code and languages that utilize unicode characters. it is nevertheless interesting that some non-canonical tokenizations are indeed more likely than their canonical counterparts, with some even in grammatically correct english. for example, the string @xmath4,uel,ess] by gemma, with p(v * |x) ≈ 0.474; however @xmath5,less] is a more likely tokenization according to the llm, with p(v|x) ≈ 0.518. this gap between the probability of the most likely tokenization and canonical tokenization can be even more extreme. for instance, @xmath6,no,patu,rist] is a much more likely tokenization p(v|x) = 0.9948 compared to the canonical tokenization v * = [hyp,nop,atu,rist], with the latter taking only p(v * |x) = 0.0004 of the total mass. this seems to suggest that there is some mass being attributed to non-canonical tokenizations, especially over longer text. we thus raise another question: instead of using a single tokenization, could we aggregate over all tokenizations, each weighted by their probability, effectively computing the marginal probability of a given string? ## ... and computing the marginal probability is also hard evaluating the probability of a string requires marginalizing over all its possible tokenizations. we now formally define this task and show it to be computationally hard. problem 5.1 (marginal string probability). let v denote a token sequence. given a string x and an autoregressive llm p, the marginal string probability problem is to compute theorem 5.2. the marginal string probability problem is #p-hard. proof. (sketch) the proof is by reduction from the counting version of the 3-sat boolean satisfiability problem (#3-sat), which is known to be #p-complete. we encode the boolean variables as possible tokens in a string, such that there is a correspondence between the number of satisfying assignments of the boolean formula and the marginal probability of the string under the llm. the full proof can be found in appendix b. ## non-canonical tokenizations in question answering in multiple-choice question answering, a model is given a question (possibly with context) and is asked to choose between a number of different answers to the question. typically, this is performed by evaluating the probability of each answer under the default canonical tokenization, and selecting the answer with the highest probability. formally, given a question c with canonical tokenization v * c and set of k answers {a i } k @xmath7, the classification is given by alternatively, we can compute these probabilities over other tokenizations, for instance, by computing an approximation to the marginal: from prior discussion, we expect the approximate marginal to gradually converge to canonical. however, we empirically find that, before convergence, there is a surprising increase in accuracy when weighting over non-canonical tokenizations compared to the canonical baseline. figure 7 shows accuracy for the marginal approximation as a function of the number of samples in three different question answering datasets: hel-laswag @xcite , socialiqa @xcite and openbookqa @xcite . due to computational constraints, we only evaluate on randomly sampled subsets of 1000 examples for each dataset. by parameter tuning the number of samples, we are able to achieve a consistent performance increase in accuracy, as to further understand how much non-canonical tokenizations play a role in this improvement, and find out where the signal in tokenization comes from, we construct a mixture of canonical and noncanonical tokenizations. we evaluate the improvement in accuracy, effectively measuring how much non-canonicity plays a role in the downstream task. more formally, we compute when α = 1, the equation above reduces to the standard canonical tokenization baseline, while α = 0 weighs only non-canonical tokenizations of the same answer. to make sure that both terms are on the same scale, we condition the distributions on the possible answers, yielding two classifiers over answers instead of tokenizations. we approximate p(ṽ a i |v * c , ṽa 1 ∨ . . . ∨ ṽa k ) by computing the (unbiased) marginal estimate over tokenizations that are not canonical, i.e., in practice, this amounts to zeroing-out all importance weights that are canonical. the first term of the mixture is computed by simply normalizing the standard canonical probability over the canonical tokenizations of possible answers the resulting mixture is then a weighted version of the marginal p(a i |v * c , a 1 ∨ . . . ∨ a k ) where we adjust the mass attributed to canonical according to parameter α. this allows us to inspect how the model behaves when mass is "shoveled" around from non-canonical to canonical and vice versa. figure 8 shows how this mixture behaves for different values of α downstream, while these experiments show that there is clear and significant signal in non-canonical tokenizations to the point that we are able to achieve a consistent increase in accuracy, suggesting that non-canonical tokenizations do indeed retain meaningful information in llms, and hopefully motivating further research in this direction. ## conclusion modern language models make the assumption that text is represented by a unique canonical tokenization equivalent to the text itself. we showed that not only is the space of possible tokenizations exponential, but prove that reasoning probabilistically about this space is hard. we then showed empirical evidence that suggests that, in practice, not only is the canonical tokenization the most likely tok-enization, but it is also very close to the probability of the text itself (i.e. the marginal probability of the text summed over tokenizations). despite this, we present surprising evidence of significant signal in non-canonical tokenizations, thus motivating further research on non-canonical tokenizations.