Research map / Large language models / Language, safety and interpretability
The Foundations of Tokenization: Statistical and Computational Concerns
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a formal framework for tokenizers based on the category of stochastic maps, proving necessary and sufficient conditions for tokenizer consistency of language model estimators and characterizing inconsistency, ambiguity, finiteness, and sequentiality.
Problem
Tokenization is widely used in neural language modeling but its theoretical underpinnings, particularly its effect on the consistency of language model estimation, are poorly understood.
Approach
Defines a tokenizer as a pair of stochastic maps (encoder, decoder) between character strings and token sequences, and shows a tokenized LM is consistent iff decoder∘encoder preserves the true distribution; known issues are cast as injectivity, multiplicativity, and bounded variation of these maps.
Key results
- Theorem (Fundamental Principle of Tokenization): a tokenized estimator {decoder(p_n)} consistently estimates the reference distribution iff decoder∘encoder preserves that distribution.
- Proposition: a tokenizer is exact iff it is consistent with respect to every probability distribution over the character strings.
- Proposition: for a multiplicative tokenizer with trivial decoder kernel, decoder(v)=t implies |v|≤|t|, so preimage sets of any text are finite.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| require the tokenizer to be exact (decoder after encoder equals identity) | tokenizer model · language-model estimation | estimator consistency | Helped |
| use a multiplicative decoder with a trivial kernel | tokenizer model · text decoding | number of token-sequence preimages per text | Helped |
| use a multiplicative mapping | string-to-string function · sequentiality analysis | bounded variation | Helped |
Surprising findings
- Consistency with respect to a single distribution does not imply exactness; only consistency with respect to all distributions is equivalent to exactness.
- Most commonly used tokenizers (BPE, WordPiece, Unigram) can be inconsistent when the encoder is non-injective, e.g. due to normalization or unknown-token handling.
Limitations
- Purely theoretical; no empirical experiments on actual language models.
- Assumes countable sets and does not treat neural estimation methods in detail.
Experimental setup
Builds on: byte-pair encoding WordPiece Unigram subword regularization
Closest papers by meaning
- An Analysis of Tokenization: Transformers under Markov Data (NeurIPS 2024 · similarity 0.92)
- Enhancing Large Language Models through Adaptive Tokenizers (NeurIPS 2024 · similarity 0.91)
- Exact Byte-Level Probabilities from Tokenized Language Models for FIM-Tasks and Model Ensembles (ICLR 2025 · similarity 0.90)
- From Language Models over Tokens to Language Models over Characters (ICML 2025 · similarity 0.89)
- Hierarchical Autoregressive Transformers: Combining Byte- and Word-Level Processing for Robust, Adaptable Language Models (ICLR 2025 · similarity 0.89)
- Broken Tokens? Your Language Model can Secretly Handle Non-Canonical Tokenizations (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.