# Should you marginalize over possible tokenizations?

arXiv: https://arxiv.org/abs/2306.17757 · HTML: https://mlsanity.com/paper/2306.17757/

## 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 (most cited first, 12 of 12)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [BLOOM: A 176B-Parameter Open-Access Multilingual Language Model](https://mlsanity.com/paper/2211.05100/) (2022)
- [No Language Left Behind: Scaling Human-Centered Machine Translation](https://mlsanity.com/paper/2207.04672/) (2022)
- [Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates](https://mlsanity.com/paper/1804.10959/) (2018)
- [BPE-Dropout: Simple and Effective Subword Regularization](https://mlsanity.com/paper/1910.13267/) (2019)
- [Dynamic Programming Encoding for Subword Segmentation in Neural Machine Translation](https://mlsanity.com/paper/2005.06606/) (2020)
- [You should evaluate your language model on marginal likelihood over tokenisations](https://mlsanity.com/paper/2109.02550/) (2021)
- [Neural Lattice Language Models](https://mlsanity.com/paper/1803.05071/) (2018)
- [Multiscale sequence modeling with a learned dictionary](https://mlsanity.com/paper/1707.00762/) (2017)

## Built on by (most cited first, 18 of 18)

- [Uncertainty in Natural Language Generation: From Theory to Applications](https://mlsanity.com/paper/2307.15703/) (2023)
- [Paloma: A Benchmark for Evaluating Language Model Fit](https://mlsanity.com/paper/2312.10523/) (2023)
- [Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo](https://mlsanity.com/paper/2504.13139/) (2025)
- [How to Compute the Probability of a Word](https://mlsanity.com/paper/2406.14561/) (2024)
- [From Language Models over Tokens to Language Models over Characters](https://mlsanity.com/paper/2412.03719/) (2024)
- [The Foundations of Tokenization: Statistical and Computational Concerns](https://mlsanity.com/paper/2407.11606/) (2024)
- [Where is the signal in tokenization space?](https://mlsanity.com/paper/2408.08541/) (2024)
- [Understanding and Mitigating Tokenization Bias in Language Models](https://mlsanity.com/paper/2406.16829/) (2024)
- [Broken Tokens? Your Language Model can Secretly Handle Non-Canonical Tokenizations](https://mlsanity.com/paper/2506.19004/) (2025)
- [On the Proper Treatment of Tokenization in Psycholinguistics](https://mlsanity.com/paper/2410.02691/) (2024)
- [Is Your LLM Overcharging You? Tokenization, Transparency, and Incentives](https://mlsanity.com/paper/2505.21627/) (2025)
- [Adversarial Tokenization](https://mlsanity.com/paper/2503.02174/) (2025)
- [Sampling from Your Language Model One Byte at a Time](https://mlsanity.com/paper/2506.14123/) (2025)
- [Auditing Pay-Per-Token in Large Language Models](https://mlsanity.com/paper/2510.05181/) (2025)
- [Language Models are not Equally Robust to Non-Canonical Tokenization across Languages](https://mlsanity.com/paper/2607.26831/) (2026)
- [Missingness Bias Calibration in Feature Attribution Explanations](https://mlsanity.com/paper/2603.04831/) (2026)
- [Tokenization Multiplicity Leads to Arbitrary Price Variation in LLM-as-a-service](https://mlsanity.com/paper/2506.06446/) (2025)
- [zip2zip++: Towards Inference-Time Token Compression with Minimal Quality Loss](https://mlsanity.com/paper/2610.13605/) (2026)

## 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.