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.

本文研究自回归语言模型中计算字符序列概率的方法，提出了一种基于重要性采样的算法估计边缘概率，并在一系列尖端模型和数据集上进行比较，结果表明在大多数情况下，对边缘化的忽略导致的对数似然差异小于 0.5％，但对于长且复杂的数据则更加明显。