# Toward a Theory of Tokenization in LLMs

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Apr 2024.

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

- [BPE Gets Picky: Efficient Vocabulary Refinement During Tokenizer Training](https://mlsanity.com/paper/2409.04599/) (2024)
- [Transformers on Markov Data: Constant Depth Suffices](https://mlsanity.com/paper/2407.17686/) (2024)
- [The Foundations of Tokenization: Statistical and Computational Concerns](https://mlsanity.com/paper/2407.11606/) (2024)
- [Understanding and Mitigating Tokenization Bias in Language Models](https://mlsanity.com/paper/2406.16829/) (2024)
- [From Pixels to Tokens: Byte-Pair Encoding on Quantized Visual Modalities](https://mlsanity.com/paper/2410.02155/) (2024)
- [Exact Byte-Level Probabilities from Tokenized Language Models for FIM-Tasks and Model Ensembles](https://mlsanity.com/paper/2410.09303/) (2024)
- [Tokenization is Sensitive to Language Variation](https://mlsanity.com/paper/2502.15343/) (2025)
- [Is Your LLM Overcharging You? Tokenization, Transparency, and Incentives](https://mlsanity.com/paper/2505.21627/) (2025)
- [The Strawberry Problem: Emergence of Character-level Understanding in Tokenized Language Models](https://mlsanity.com/paper/2505.14172/) (2025)
- [Unified Multimodal Understanding via Byte-Pair Visual Encoding](https://mlsanity.com/paper/2506.23639/) (2025)
- [LLM Cannot Discover Causality, and Should Be Restricted to Non-Decisional Support in Causal Discovery](https://mlsanity.com/paper/2506.00844/) (2025)
- [Date Fragments: A Hidden Bottleneck of Tokenization for Temporal Reasoning](https://mlsanity.com/paper/2505.16088/) (2025)
- [ReTok: Replacing Tokenizer to Enhance Representation Efficiency in Large Language Model](https://mlsanity.com/paper/2410.04335/) (2024)
- [Tokenization as Finite-State Transduction](https://mlsanity.com/paper/2410.15696/) (2024)
- [Why is prompting hard? Understanding prompts on binary sequence predictors](https://mlsanity.com/paper/2502.10760/) (2025)
- [Hippocampus: An Efficient and Scalable Memory Module for Agentic AI](https://mlsanity.com/paper/2602.13594/) (2026)
- [Qtok: A Comprehensive Framework for Evaluating Multilingual Tokenizer Quality in Large Language Models](https://mlsanity.com/paper/2410.12989/) (2024)
- [Adapting Language Models via Token Translation](https://mlsanity.com/paper/2411.00593/) (2024)
- [DateLogicQA: Benchmarking Temporal Biases in Large Language Models](https://mlsanity.com/paper/2412.13377/) (2024)
- [Syllabic Agglutinative Tokenizations for Indonesian LLM: A Study from Gasing Literacy Learning System](https://mlsanity.com/paper/2601.11643/) (2026)
- [Modelling the Morphology of Verbal Paradigms: A Case Study in the Tokenization of Turkish and Hebrew](https://mlsanity.com/paper/2602.05648/) (2026)
- [Phonemes to the Rescue: Multilingual Tokenization Based on International Phonetic Alphabet](https://mlsanity.com/paper/2606.20993/) (2026)
- [MultiTok: Variable-Length Tokenization for Efficient LLMs Adapted from LZW Compression](https://mlsanity.com/paper/2410.21548/) (2024)
- [Mathematical Reasoning in Large Language Models: Benchmarks, Architectures, Evaluation, and Open Challenges](https://mlsanity.com/paper/2605.19723/) (2026)
- [Tokenization Multiplicity Leads to Arbitrary Price Variation in LLM-as-a-service](https://mlsanity.com/paper/2506.06446/) (2025)
- [The Prompt Engineering Report Distilled: Quick Start Guide for Life Sciences](https://mlsanity.com/paper/2509.11295/) (2025)
- [Optimality and NP-Hardness of Transformers in Learning Markovian Dynamical Functions](https://mlsanity.com/paper/2510.18638/) (2025)
- [Training Language Models with homotokens Leads to Delayed Overfitting](https://mlsanity.com/paper/2601.02867/) (2026)
- [Removable and Irreducible: A Token-Cost Ledger for the Multilingual Tokenization Tax](https://mlsanity.com/paper/2609.00378/) (2026)
- [Design Choices for Multimodal Transformer Learning with Missing and Longitudinal Healthcare Data](https://mlsanity.com/paper/2610.14436/) (2026)

## Abstract (arXiv)

While there has been a large body of research attempting to circumvent tokenization for language modeling (Clark et al., 2022; Xue et al., 2022), the current consensus is that it is a necessary initial step for designing state-of-the-art performant language models. In this paper, we investigate tokenization from a theoretical point of view by studying the behavior of transformers on simple data generating processes. When trained on data drawn from certain simple kth-order Markov processes for k > 1, transformers exhibit a surprising phenomenon - in the absence of tokenization, they empirically fail to learn the right distribution and predict characters according to a unigram model (Makkuva et al., 2024). With the addition of tokenization, however, we empirically observe that transformers break through this barrier and are able to model the probabilities of sequences drawn from the source near-optimally, achieving small cross-entropy loss. With this observation as starting point, we study the end-to-end cross-entropy loss achieved by transformers with and without tokenization. With the appropriate tokenization, we show that even the simplest unigram models (over tokens) learnt by transformers are able to model the probability of sequences drawn from kth-order Markov sources near optimally. Our analysis provides a justification for the use of tokenization in practice through studying the behavior of transformers on Markovian data.