# The Foundations of Tokenization: Statistical and Computational Concerns

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 66 references that are in the map.
- First posted on arXiv 16 Jul 2024.

## Builds on (most cited first, 30 of 33)

- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation](https://mlsanity.com/paper/1609.08144/) (2016)
- [Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates](https://mlsanity.com/paper/1804.10959/) (2018)
- [ByT5: Towards a token-free future with pre-trained byte-to-byte models](https://mlsanity.com/paper/2105.13626/) (2021)
- [CANINE: Pre-training an Efficient Tokenization-Free Encoder for Language Representation](https://mlsanity.com/paper/2103.06874/) (2021)
- [BPE-Dropout: Simple and Effective Subword Regularization](https://mlsanity.com/paper/1910.13267/) (2019)
- [Byte Pair Encoding is Suboptimal for Language Model Pretraining](https://mlsanity.com/paper/2004.03720/) (2020)
- [Between words and characters: A Brief History of Open-Vocabulary Modeling and Tokenization in NLP](https://mlsanity.com/paper/2112.10508/) (2021)
- [Fast WordPiece Tokenization](https://mlsanity.com/paper/2012.15524/) (2020)
- [On Using Very Large Target Vocabulary for Neural Machine Translation](https://mlsanity.com/paper/1412.2007/) (2014)
- [Efficient Transformers with Dynamic Token Pooling](https://mlsanity.com/paper/2211.09761/) (2022)
- [Superbizarre Is Not Superb: Derivational Morphology Improves BERT's Interpretation of Complex Words](https://mlsanity.com/paper/2101.00403/) (2021)
- [Tokenization and the Noiseless Channel](https://mlsanity.com/paper/2306.16842/) (2023)
- [Addressing the Rare Word Problem in Neural Machine Translation](https://mlsanity.com/paper/1410.8206/) (2014)
- [A Formal Perspective on Byte-Pair Encoding](https://mlsanity.com/paper/2306.16837/) (2023)
- [Greed is All You Need: An Evaluation of Tokenizer Inference Methods](https://mlsanity.com/paper/2403.01289/) (2024)
- [A Call for Prudent Choice of Subword Merge Operations in Neural Machine Translation](https://mlsanity.com/paper/1905.10453/) (2019)
- [You should evaluate your language model on marginal likelihood over tokenisations](https://mlsanity.com/paper/2109.02550/) (2021)
- [Analyzing Cognitive Plausibility of Subword Tokenization](https://mlsanity.com/paper/2310.13348/) (2023)
- [Toward a Theory of Tokenization in LLMs](https://mlsanity.com/paper/2404.08335/) (2024)
- [A Better Way to Do Masked Language Model Scoring](https://mlsanity.com/paper/2305.10588/) (2023)
- [How Much Does Tokenization Affect Neural Machine Translation?](https://mlsanity.com/paper/1812.08621/) (2018)
- [Differentiable Weighted Finite-State Transducers](https://mlsanity.com/paper/2010.01003/) (2020)
- [How do different tokenizers perform on downstream tasks in scriptio continua languages?: A case study in Japanese](https://mlsanity.com/paper/2306.09572/) (2023)
- [Improving Tokenisation by Alternative Treatment of Spaces](https://mlsanity.com/paper/2204.04058/) (2022)
- [Achieving Open Vocabulary Neural Machine Translation with Hybrid Word-Character Models](https://mlsanity.com/paper/1604.00788/) (2016)
- [Should you marginalize over possible tokenizations?](https://mlsanity.com/paper/2306.17757/) (2023)
- [Neural Lattice Language Models](https://mlsanity.com/paper/1803.05071/) (2018)
- [Effects of sub-word segmentation on performance of transformer language models](https://mlsanity.com/paper/2305.05480/) (2023)
- [Spell Once, Summon Anywhere: A Two-Level Open-Vocabulary Language Model](https://mlsanity.com/paper/1804.08205/) (2018)

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

- [From Language Models over Tokens to Language Models over Characters](https://mlsanity.com/paper/2412.03719/) (2024)
- [Tokenizing Single-Channel EEG with Time-Frequency Motif Learning](https://mlsanity.com/paper/2502.16060/) (2025)
- [On the Proper Treatment of Tokenization in Psycholinguistics](https://mlsanity.com/paper/2410.02691/) (2024)
- [Grammar-based Ordinary Differential Equation Discovery](https://mlsanity.com/paper/2504.02630/) (2025)
- [Date Fragments: A Hidden Bottleneck of Tokenization for Temporal Reasoning](https://mlsanity.com/paper/2505.16088/) (2025)
- [Tokenization as Finite-State Transduction](https://mlsanity.com/paper/2410.15696/) (2024)
- [Ensembling Language Models with Sequential Monte Carlo](https://mlsanity.com/paper/2603.05432/) (2026)
- [DateLogicQA: Benchmarking Temporal Biases in Large Language Models](https://mlsanity.com/paper/2412.13377/) (2024)
- [Bio-Inspired Self-Supervised Learning for Wrist-worn Accelerometer Data](https://mlsanity.com/paper/2603.10961/) (2026)
- [Phonemes to the Rescue: Multilingual Tokenization Based on International Phonetic Alphabet](https://mlsanity.com/paper/2606.20993/) (2026)
- [Zero-Shot Attribution for Large Language Models: A Distribution Testing Approach](https://mlsanity.com/paper/2506.20197/) (2025)
- [Train It and Forget It: Merge Lists are Unnecessary for BPE Inference in Language Models](https://mlsanity.com/paper/2508.06621/) (2025)
- [Small Vocabularies, Big Gains: Pretraining and Tokenization in Time Series Models](https://mlsanity.com/paper/2511.11622/) (2025)
- [Say Anything but This: When Tokenizer Betrays Reasoning in LLMs](https://mlsanity.com/paper/2601.14658/) (2026)
- [Token Inflation: How Dishonest Providers Can Overcharge for Large Language Model Usage](https://mlsanity.com/paper/2605.30040/) (2026)
- [Prompting Complexity: Shortest Prompts for Texts and Behaviors in LLMs](https://mlsanity.com/paper/2607.06145/) (2026)
- [Tokenization Multiplicity Leads to Arbitrary Price Variation in LLM-as-a-service](https://mlsanity.com/paper/2506.06446/) (2025)
- [A Family of LLMs Liberated from Static Vocabularies](https://mlsanity.com/paper/2603.15953/) (2026)
- [Domain Adapted Large Language Models for Additive Manufacturing](https://mlsanity.com/paper/2603.22017/) (2026)
- [Probing for Reading Times](https://mlsanity.com/paper/2604.18712/) (2026)
- [How Far Should Tokenization Go? Predictive Effectiveness and Relational Losslessness](https://mlsanity.com/paper/2608.18025/) (2026)
- [Removable and Irreducible: A Token-Cost Ledger for the Multilingual Tokenization Tax](https://mlsanity.com/paper/2609.00378/) (2026)

## Abstract (arXiv)

Tokenization - the practice of converting strings of characters from an alphabet into sequences of tokens over a vocabulary - is a critical step in the NLP pipeline. The use of token representations is widely credited with increased model performance but is also the source of many undesirable behaviors, such as spurious ambiguity or inconsistency. Despite its recognized importance as a standard representation method in NLP, the theoretical underpinnings of tokenization are not yet fully understood. In particular, the impact of tokenization on language model estimation has been investigated primarily through empirical means. The present paper contributes to addressing this theoretical gap by proposing a unified formal framework for representing and analyzing tokenizer models. Based on the category of stochastic maps, this framework enables us to establish general conditions for a principled use of tokenizers and, most importantly, the necessary and sufficient conditions for a tokenizer model to preserve the consistency of statistical estimators. In addition, we discuss statistical and computational concerns crucial for designing and implementing tokenizer models, such as inconsistency, ambiguity, finiteness, and sequentiality. The framework and results advanced in this paper contribute to building robust theoretical foundations for representations in neural language modeling that can inform future theoretical and empirical research.