mlsanityData to 14 Oct 2026

Should you marginalize over possible tokenizations?

arXiv 2306.17757 ↗First posted 30 Jun 2023cs.CLcited by 18

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 18 papers in the map (data through 14 Oct 2026). Builds on 12 of its 21 references that are in the map. First posted on arXiv 30 Jun 2023.

Builds on

12 of 21 references.

References · 12

  1. 2020Language Models are Few-Shot Learnerscited by 32,419
  2. 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,599
  3. 2016Pointer Sentinel Mixture Modelscited by 3,096
  4. 2015Neural Machine Translation of Rare Words with Subword Unitscited by 2,918
  5. 2022BLOOM: A 176B-Parameter Open-Access Multilingual Language Modelcited by 1,984
  6. 2022No Language Left Behind: Scaling Human-Centered Machine Translationcited by 1,312
  7. 2018Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidatescited by 639
  8. 2019BPE-Dropout: Simple and Effective Subword Regularizationcited by 195
  9. 2020Dynamic Programming Encoding for Subword Segmentation in Neural Machine Translationcited by 38
  10. 2021You should evaluate your language model on marginal likelihood over tokenisationscited by 30
  11. 2018Neural Lattice Language Modelscited by 13
  12. 2017Multiscale sequence modeling with a learned dictionarycited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 6; 2025: 7; 2026: 3.

18 papers.

Sort:

By area:

  1. 2023Uncertainty in Natural Language Generation: From Theory to Applicationscited by 61
  2. 2023Paloma: A Benchmark for Evaluating Language Model Fitcited by 54
  3. 2025Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlocited by 46
  4. 2024How to Compute the Probability of a Wordcited by 36
  5. 2024From Language Models over Tokens to Language Models over Characterscited by 31
  6. 2024The Foundations of Tokenization: Statistical and Computational Concernscited by 22
  7. 2024Where is the signal in tokenization space?cited by 21
  8. 2024Understanding and Mitigating Tokenization Bias in Language Modelscited by 18
  9. 2025Broken Tokens? Your Language Model can Secretly Handle Non-Canonical Tokenizationscited by 17
  10. 2024On the Proper Treatment of Tokenization in Psycholinguisticscited by 13
  11. 2025Is Your LLM Overcharging You? Tokenization, Transparency, and Incentivescited by 13
  12. 2025Adversarial Tokenizationcited by 11
6 more
  1. 2025Sampling from Your Language Model One Byte at a Timecited by 7
  2. 2025Auditing Pay-Per-Token in Large Language Modelscited by 4
  3. 2026Language Models are not Equally Robust to Non-Canonical Tokenization across Languagescited by 2
  4. 2026Missingness Bias Calibration in Feature Attribution Explanationscited by 1
  5. 2025Tokenization Multiplicity Leads to Arbitrary Price Variation in LLM-as-a-servicecited by 0
  6. 2026zip2zip++: Towards Inference-Time Token Compression with Minimal Quality Losscited by 0