Should you marginalize over possible tokenizations? (2023)

Abstract: Autoregressive language models (LMs) map token sequences to probabilities. The usual practice for computing the probability of any character string (e.g. English sentences) is to first transform it into a sequence of tokens that is scored by the model. However, there are exponentially many token sequences that represent any given string. To truly compute the probability of a string one should marginalize over all tokenizations, which is typically intractable. Here, we analyze whether the practice of ignoring the marginalization is justified. To this end, we devise an importance-sampling-based algorithm that allows us to compute estimates of the marginal probabilities and compare them to the default procedure in a range of state-of-the-art models and datasets. Our results show that the gap in log-likelihood is no larger than 0.5% in most cases, but that it becomes more pronounced for data with long complex words.

## introduction language models are probability distributions over text strings. in practice, these distributions are defined over a vocabulary of tokens, such as words, punctuation marks, and other special symbols @xcite . as long as a unique token sequence encodes any given string, the probability of a string according to the language model is equal to the probability of the corresponding token sequence. however, with today popular sub-wordlevel tokenizations this is not the case, as there are (exponentially) many possible tokenizations for any given string. for example, with the vocabulary @xmath0, ab, b, c, ca, cab}, the string "cab" can be tokenized into cab, c/a/b, ca/b, c/ab. therefore, the true probability that the language model assigns to the corresponding string is that obtained after marginalizing over all possible tokenizations. yet, the common practice disregards this fact, computing the string probability by scoring a single default tokenization (e.g., cab). the implicit assumption from the community is that the probability mass of non-default tokenizations is negligible. however, this assumption has not been adequately evaluated yet. in part, @xcite addressed this very same question, by conducting a pioneer study to quantify the gap between the default and marginalized probabilities. their experiments with transformer-xl pretrained on the wmt data (english and german) show negligible changes in perplexity with respect to using a single default tokenization for in-domain data and 0.9-1.9% improvement in perplexity for out-of-domain data, such as arxiv articles. because exact marginalization is intractable in practice, marginalized probabilities were estimated using importance sampling. importance sampling computes an unbiased estimate of the marginalized probabilities as an average over tokenizations sampled from a proposal distribution. @xcite exploited the probabilistic nature of the unigramlm tokenizer @xcite to define such a proposal. as a consequence, their results do not necessarily extend to the more popular language models like gpt-2 @xcite , gpt-3 @xcite , bloom @xcite , t5 @xcite , among others, trained using other tokenization schemes such as bpe @xcite , wordpiece @xcite , among others. 1 in this work, we devise a new proposal distribution that allows us to quantify the effect of marginalization for any given tokenizer. equipped with this algorithm, we inspect the effect of marginalization over tokenizations for two lms, gpt-2 (126m parameters, english) and the recently released bloom (1.7b parameters, multilingual), on various domains and languages. our importance sampling estimates show that in practice marginalization does not influence log-likelihood much (usually less than 0.5% improvement), the highest influence (1-2% improvement) being for data with long, complex words and distribution shift. because the results will vary for different models and data, we provide a tool for researchers and practitioners to measure the gap in their specific setting to decide whether the usual practice is warranted. to this end, we release our code 1 , which can be applied to models from the transformers library. ## related work stochastic tokenization or marginalisation over tokenizations were widely investigated in the context of model training @xcite @xcite @xcite or learning better tokenizers @xcite ; in contrast, we evaluate the effect of marginalization at the inference stage, when the tokenizer and the lm were trained in the default, commonly-used way. the closest study to ours is @xcite , which relies on the stochastic version of the unigramlm tokenizer as their proposal q, and thus their approach is inapplicable to lms with other tokenizers. they also had to introduce a set of heuristics such as imposing consistent tokenization of repeated words or enforcing the default tokenization to be included among the sampled tokenizations, to make this proposal closer to the posterior and to decrease the variance of importance sampling. ## conclusion in this work, we have studied the effect of marginalization over possible tokenizations in language modeling. for this, we introduced a novel proposal distribution over tokenizations, which is used in the importance sampling algorithm to obtain estimates of the marginalized probability, and that can be applied to any tokenizer and language model. our results show that the overall effect of marginalization over tokenizations is often smaller than 0.5%, although it becomes more pronounced for data with long complex words or distribution shift. we release our code to allow practitioners to check the effect of marginalization for their models of interest.