@inproceedings{chirkova-etal-2023-marginalize,
    title = "Should you marginalize over possible tokenizations?",
    author = "Chirkova, Nadezhda  and
      Kruszewski, Germ\'an  and
      Rozen, Jos  and
      Dymetman, Marc",
    editor = "Rogers, Anna  and
      Boyd-Graber, Jordan  and
      Okazaki, Naoaki",
    booktitle = "Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)",
    month = jul,
    year = "2023",
    address = "Toronto, Canada",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/build-pipeline-with-new-library/2023.acl-short.1/",
    doi = "10.18653/v1/2023.acl-short.1",
    pages = "1--12",
    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."
}