Research map / Architectures and efficiency / Attention and transformers
An Analysis of Tokenization: Transformers under Markov Data
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.
Studies why transformers fail to learn kth-order Markov sources without tokenization (collapsing to unigram) but succeed with tokenization, and proves LZW and a sequential BPE variant yield tokenizers whose best unigram model is near-optimal in cross-entropy.
Problem
Transformers trained on kth-order Markov character sequences without tokenization learn only unigram-like predictions and have high cross-entropy; the paper asks why tokenization helps and how tokenizer choice affects end-to-end loss.
Approach
Frames tokenization as a statistical problem: end-to-end cross-entropy of a unigram model over tokens. Shows a toy fixed-length tokenizer needs exponential dictionary size, while LZW and a sequential BPE variant achieve near-optimal unigram loss with polynomial dictionaries, via a heavy-hitter dictionary argument.
Key results
- Transformers trained on order-2 switching Markov data without tokenization plateau at the best unigram loss, while with BPE (dictionary size 10) they approach the optimal cross-entropy.
- Theorem 3.6: LZW tokenizer with dictionary size d yields best unigram loss within a factor 1/(1-ε) of optimal, ε = log(1/δ)/(0.99 log d)^... with dictionary size near 1/δ^2 needed for factor 2 versus exponential e^{1/δ} for the toy tokenizer.
- Table 1: best unigram models on pretrained tokenizers (BERT, TinyLlama, GPT-NeoX, Mistral, Phi-2) achieve cross-entropy 1.45-1.84 nats versus 2.38-2.46 for the character-level ByT5 with a bigram model.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Phi-2 BPE unigram instead of ByT5 character bigram | unigram likelihood modeling · Rotten Tomatoes (RT) | cross-entropy loss: 2.40 vs 1.54 | Helped |
| use BERT Wordpiece unigram instead of ByT5 character bigram | unigram likelihood modeling · Wikitext-103-v1 (Wiki) | cross-entropy loss: 2.45 vs 1.55 | Helped |
| use BERT Wordpiece unigram instead of ByT5 character bigram | unigram likelihood modeling · Yelp review | cross-entropy loss: 2.46 vs 1.60 | Helped |
| use Phi-2 BPE unigram instead of ByT5 character bigram | unigram likelihood modeling · GLUE | cross-entropy loss: 2.38 vs 1.45 | Helped |
| add BPE tokenization (ablation) | transformer on order-1 switching Markov chain · order-1 switching Markov chain | training time to target test loss | Helped |
| add BPE tokenization (ablation) | transformer on order-1 switching Markov chain with the same architecture · order-1 switching Markov chain | limiting test loss | Hurt |
| add BPE tokenization (ablation) | transformer on order-2 switching Markov process · order-2 switching Markov process | test cross-entropy loss | Helped |
Surprising findings
- Without tokenization, transformers on simple kth-order Markov sources empirically predict according to a unigram model, failing to learn the optimal distribution.
- Tokenized models with fewer parameters reached a target loss in less wall-clock time than untokenized models, though the tokenized models had more parameters.
Limitations
- Theory assumes every transition has nonzero probability (Assumption 3.2), which excludes some Markov chains.
- Analysis of standard BPE is incomplete; only a sequential variant with sample splitting is analyzed, with a factor-of-2 gap.
- Experiments are on simple synthetic Markov sources and small transformers, not large language models.
Experimental setup
Datasets: Wikitext-103-raw-v1 GLUE Rotten Tomatoes Yelp review Wikitext-103-v1
Benchmarks: Rotten Tomatoes Wikitext Yelp review GLUE
Metrics: cross-entropy loss test loss vs. training time cross-entropy vs. dictionary size
Baselines: character-level tokenizer Unigram tokenizer Wordpiece BPE
Builds on: Makkuva et al. 2024 Edelman et al. 2024 LZW (Zouhar et al. 2023) BPE (Sennrich et al. 2016)
Closest papers by meaning
- The Foundations of Tokenization: Statistical and Computational Concerns (ICLR 2025 · similarity 0.92)
- Effective Context in Transformers: An Analysis of Fragmentation and Tokenization (NeurIPS 2026 · similarity 0.91)
- Exact Byte-Level Probabilities from Tokenized Language Models for FIM-Tasks and Model Ensembles (ICLR 2025 · similarity 0.89)
- Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling (ICML 2025 · similarity 0.89)
- Hierarchical Autoregressive Transformers: Combining Byte- and Word-Level Processing for Robust, Adaptable Language Models (ICLR 2025 · similarity 0.89)
- From Language Models over Tokens to Language Models over Characters (ICML 2025 · similarity 0.89)
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.