You should evaluate your language model on marginal likelihood over tokenisations (2021)

Abstract: Neural language models typically tokenise input text into sub-word units to achieve an open vocabulary. The standard approach is to use a single canonical tokenisation at both train and test time. We suggest that this approach is unsatisfactory and may bottleneck our evaluation of language model performance. Using only the one-best tokenisation ignores tokeniser uncertainty over alternative tokenisations, which may hurt model out-of-domain performance. In this paper, we argue that instead, language models should be evaluated on their marginal likelihood over tokenisations. We compare different estimators for the marginal likelihood based on sampling, and show that it is feasible to estimate the marginal likelihood with a manageable number of samples. We then evaluate a pretrained language model on both the one-best-tokenisation and marginal perplexities, and show that the marginal perplexity can be significantly better than the one best, especially on out-of-domain data. We link this difference in perplexity to the tokeniser uncertainty as measured by tokeniser entropy. We discuss some implications of our results for language model training and evaluation, particularly with regard to tokenisation robustness.

## introduction neural end-to-end language models have largely done away with traditional pipeline approaches towards building nlp systems. however, one component which stubbornly remains is the tokenisation step, used right at the start of preprocessing. at the time of writing, the most widely used tokenisers, such as bpe @xcite and unigram @xcite , break up the input text into subword units, potentially backing off to character-level segmentation if necessary. this allows for coverage of every possible input sequence; on the downside, a single input sequence may now have multiple possible tokenisations. typically, language models are trained and evaluated using a single canonical tokenisation out of the multitude of possible ones, but this tokenisation may be suboptimal @xcite ) for many reasons. for example, different tokenisations -that is, different surface segmentations -can reveal different morphological analyses of the word in question (think un-ion-izeable vs. union-izable), and committing to a particular analysis can discard useful information, particularly if the best analysis from the tokeniser is erroneous @xcite . further, tokenisers themselves are trained using an objective which optimises the likelihood of the data. this can be explicit (the unigram tokeniser of @xcite optimises a unigram language modelling objective) or implicit (bpe aims to minimise the description length of the training data, which has close connections to probabilistic methods; @xcite . in this sense they are also language models, albeit far less powerful than the neural language models we train on their outputs. this raises a difficult question: to what extent are our large language models bottlenecked by the tokenisers that we use to train them? we argue that rather than evaluating language models using the one-best tokenisation from the tokeniser, one should evaluate language models using the marginal likelihood over all possible tokenisations of an input. this divorces language model performance from the performance of the tokenisation model, and we believe this gives a better indicator of the intrinsic quality of the language model. in this paper, we take a language model pretrained using a single tokenisation, and estimate the marginal likelihood of the model on test data, taking multiple tokenisations of each input into account. while summing exactly over exponentially many tokenisations is intractable, we can estimate the marginal likelihood using importance sampling. one contribution of this paper is to show-case low-variance estimators of the marginal likelihood based on sampling without replacement. we cast the tokeniser as the proposal distribution for our importance sampling estimator, which clearly delimits the role of the tokeniser. indeed, as the number of samples we consider increases, the language model becomes less and less coupled to the tokeniser, and our evaluation becomes more intrinsic to the language model itself, rather than the language model + tokeniser combination. we demonstrate that there can be a significant difference -which we call the marginal gap -in marginal likelihood compared to one-best tokenisation likelihood, especially on out-of-domain evaluation sets. this suggests that the tokeniser is failing to generalise well to out-of-domain data, and is therefore a significant bottleneck to the generalisation capability of the language model. thus, taking the one-best tokenisation likelihood is a poor proxy for the true language model performance. we next show that there is a correlation between the uncertainty of the tokeniser (as measured by the entropy of the segmentation lattice) and the marginal gap. we give an efficient dynamic program to calculate the entropy of the segmentation lattice, and show that this entropy is predictive of how poorly the tokeniser fails to generalise. this suggests that measuring tokeniser entropy can be a useful signal for adding additional samples to our estimate of the marginal likelihood. we also use our sampled tokenisations to demonstrate that language models are particularly sensitive to variations in tokenisation, a challenge that must be mitigated for marginal likelihood evaluation. finally, we investigate how many samples are necessary to obtain an accurate estimate of the marginal likelihood. we show that many samples are necessary, but only relatively few samples contribute significantly to this estimate. this shows that the tokeniser distribution over tokenisations differs significantly from the language model posterior distribution over tokenisations -indeed, taking only the best tokenisation from the samples can recover most of the performance increase obtained by marginalisation. this gives weight to our finding that tokenisers generalise poorly, and that the one-best tokenisation can often be suboptimal. we conclude by discussing some implications of our results, particularly for languages with richer morphology than english. finally, we sketch potential future directions to bridge this gap by using sampled tokenisations at training time, and how this might improve language model robustness. ## taking multiple tokenisations into consideration we denote by d (for document) a string of text whose score we would like to calculate. given a vocabulary v of sub-word tokens (which is usually induced by the tokeniser), we denote by t i potential tokenisations of d -i.e. sequences of tokens t 1 t 2 . . . t n i such that each t @xmath0. an autoregressive neural language model (with parameters θ) is a model which decomposes the probability of the full sequence into a series of left-to-right predictions: crucially, neural language models p θ do not score d directly, but rather token sequences p θ (t, d). for any input document d, a tokeniser will define a canonical tokenisation t * , and one usually approximates p θ (d) with p θ (t * , d). we believe, on the other hand, that it is more principled to marginalise over all possible tokenisations; that is, calculate t p θ (t, d) directly. there could be significant tokeniser uncertainty over the correct tokenisation; we can view the uncertainty as either caused by ambiguity in local context imposed by the strong independence assumptions made by tokenisers, or because of inherent tokeniser uncertainty when confronted with out-of-domain input. in either case, incorporating additional analyses in the form of extra tokenisations can give the language model extra information compared to the one-best tokenisation. we believe that the marginal likelihood better represents the true capability of the language model, without the constraint of the tokeniser. however, exactly calculating the marginal likelihood is infeasible, as the number of possible tokenisations is exponential in the length of the input text. whenever calculating a marginal exactly is infeasible, the classical approach is to approximate it using samples. the best distribution to sample from would be the model posterior distribution over tokenisations given text, as this gives the lowest variance estimator; unfortunately, we are unaware of any methods that would let us sample directly from this distribution. therefore, to estimate the marginal language model likelihood, we turn to importance sampling. given some proposal distribution q(t |d) of possible tokenisations, we can use the importance sampling estimator now, it remains to find a suitable proposal distribution q(t |d). in this paper, we use the unigram tokeniser of @xcite , as this is the only probabilistic tokeniser that we are aware of. this tokeniser first constructs a lattice of all possible tokenisations given an input and a lexicon of word pieces. distinct tokenisations of the input correspond to paths through this lattice, and the score of a tokenisation is the sum of the scores of the tokens along the path. as the score decomposes along lattice segments, many interesting quantities, such as q(d) (the marginal likelihood of an input text under the tokeniser), are exactly calculable. this allows not only for sampling from the lattice of possible tokenisations, but also calculating the score of a given tokenisation (i.e. estimate q(t |d) = q(t, d)/q(d)), which is necessary to estimate the importance weight. tokenising consistently there is prior evidence @xcite to suggest that transformer language models are able to effectively leverage memory, and that perplexities of repeated words in a document can be much lower than the perplexity of the first occurrence of that word. we show in section 4.3 that this copying ability is tied to the exact tokenisation of that word: if a word reoccurs in a document with a different tokenisation, its perplexity is much higher than if it reappears with the same tokenisation. armed with this insight, we design an alternative proposal distribution which samples a single tokenisation for each unique whitespace-delimited type in a document, and then shares that tokenisation for each token of that type in the document. we note that it is possible to adapt a pre-trained unigram tokeniser to do this, by passing in only the unique whitespace types in a document to the tokeniser and reconstructing the document from the sampled tokenisations. this is possible because the unigram tokeniser does not consider context when tokenising, and whitespace tokens are tokenised independently. we note that this two-stage word generation process, where first we generate the vocabulary for a document, and then generate the document from that vocabulary, has close connections to the two-stage language models proposed in @xcite . the problem of tokenising consistently only arises when sampling from the tokeniser; the one-best tokenisation of an input from the unigram tokeniser will always tokenise each occurrence of a type identically. ## measuring segmentation lattice entropy we believe that the entropy of the tokeniser segmentation lattice is an important quantity to measure. the entropy quantifies the uncertainty of the tokeniser, and has a nice interpretation as the (logarithm of the) size of the set of alternatives the tokeniser is choosing uniformly over. while the entropy over hidden states of other structured models like hmms and crfs have previously been published @xcite @xcite , and a uniform treatment in terms of expectation semirings is given in @xcite , we are unaware of previous elementary derivations of the entropy of a segmentation lattice. we give the algorithm in algorithm 1. note that the recursion has a particularly nice interpretation in terms of information theory. recall that the entropy of a random variable can be thought of as the necessary number of bits to transmit the random variable. the recursion states that, to transmit the lattice up to position i (which takes h i bits), we can transmit a prefix of the lattice (using h j bits), and then transmit the token w that goes from j to i (using log p (w) bits). the total number of bits necessary is then the weighted sum of all possible ways of doing this, where the weights are given by the probability of that particular decomposition. ## experiments for our experiments, we first pretrain language models using one-best tokenisations from a tokeniser using wmt news shared task data @xcite . we train models on both english and german data up to september 2017, reserving the rest of the 2017 data for validation and model selection. we use a transformer-xl @xcite model with 18 layers and a hidden size of 1024. during evaluation time, we do not use transformer-xl memory, due to the interaction of batching and sampled tokenisation. while this may depress our results, we are not interested in absolute model performance per se, but rather in the relative performance of the marginal likelihood vs. the one-best likelihood. the tokeniser we use at both training and evaluation time is a unigram tokeniser as implemented in the sentencepiece package @xcite , with a vocabulary size of 50529. we train the tokeniser on the same training set, with a random sample of 100 million sentences for english, and 10 million documents for german. ## conclusion in this paper, we argue for using model marginal likelihood over tokenisations as an evaluation metric for language models, rather than one-best tokenisation likelihood. we introduce practical lowvariance estimators for measuring the marginal likelihood, and demonstrate that there can be significant difference between the marginal and the onebest likelihoods, particularly on strongly out-ofdomain evaluation sets. evaluating with marginal likelihood thus goes some way toward loosening the bottleneck imposed by tokeniser quality in the currently dominant language modelling paradigm, and our results suggest that the field may be underestimating the generalisation capability of modern language models. we further demonstrate that tokeniser entropy is a good predictor of this "marginal gap", suggesting that tokeniser entropy, especially when out-of-domain, can be a guide to the number of samples needed for evaluation. more broadly, our experiments suggest that the field should continue seeking better ways to incorporate tokenisation into end-to-end language modelling. sampling from the tokeniser during training is an obvious possibility; alternatively, one could incorporate the segmentation lattice into the model directly, which has been beneficial for parsing morphologically rich languages @xcite . further, developing more contextual tokenisers which make fewer independence assumptions can also result in both better language models trained on their onebest tokenisation, and better evaluation estimates of the marginal likelihood with fewer samples. we conduct experiments on german and english corpora in this paper. however, these two languages are only a small sample in the full space of language typology. english is a morphologically impoverished language, and while german compounding and inflection offer some additional challenges, many languages have more complex patterns of word formation and inflection. we believe that estimating marginal likelihood will be important for morphologically richer languages, where tokenisation makes a bigger difference @xcite . finally, improved understanding of the interaction between tokenisation and language modelling has implications for evaluating language models on both downstream tasks and language generation tasks. evidence has shown that gains in language modelling, as measured in perplexity, often lead to improvements in downstream task performance @xcite . it would be instructive to extend our marginal likelihood approach to downstream task evaluation. on generation tasks, since the tokeniser affects language model training but is only implicitly used when sampling (via the tokeniser vocabulary), the effect of tokenisation algorithms requires careful investigation.