# Tokenization algorithms

> A tokenizer maps text to ids from a fixed vocabulary: normalize, pre-tokenize, segment, add special tokens. Subword algorithms (BPE, WordPiece, Unigram) sit between characters (long sequences) and words (unknown words). Byte-level bases remove <unk>, and fertility measures tokens per word.

Source: https://www.mlfoundry.in/learn/tokenization-algorithms  
Section: Deep Learning › Large Language Models (LLMs)  
Level: core · 14 min read · updated 2026-10-13

**Tokenization:** is the fixed, deterministic map from a string to a sequence of integer ids drawn from a vocabulary of size $V$, together with its inverse. A **language model** only ever sees those ids (see **Language modeling**). Its embedding table has $V$ rows, its softmax has $V$ outputs, and its context window is counted in tokens. Modern LLMs use **subword** vocabularies learned from data. They include **Byte-pair encoding (BPE)** (Sennrich, Haddow and Birch, ACL 2016), **WordPiece** (Schuster and Nakajima, ICASSP 2012) and the **Unigram** language-model tokenizer (Kudo, ACL 2018). They are usually trained with tools like **SentencePiece** (Kudo and Richardson, EMNLP 2018) or Hugging Face's `tokenizers` library.

Every tokenizer trades **vocabulary size** against **sequence length**. Word-level vocabularies, as in early neural translation and word2vec, give short sequences. But any word missing from the list becomes one `<unk>` token, and real text has an endless tail of names, numbers, typos, inflections and compounds. A 50,000-word vocabulary still misses words, and every new word costs a full embedding row. Character-level models never meet an unknown word, but sequences get 4–5 times longer. Attention cost grows quadratically with length, and the model must spend capacity learning to spell.

Subword tokenization was the compromise that won. Frequent words get one token (`Ġthe`, `Ġmodel`), and rare words are split into reusable pieces (`Ġtoken` `izer` `s`), so nothing is unknown when the base symbols cover every character or byte. The idea came from speech recognition and translation: WordPiece for Japanese and Korean voice search (2012) and Google's neural translation system (Wu et al., 2016), and BPE for translating rare words (2016). GPT-2 (2019) made BPE byte-level. Since then every major LLM has used a subword vocabulary of 32k–256k tokens.

## The pipeline

A tokenizer is more than its vocabulary. The Hugging Face `tokenizers` library makes the stages explicit, and most tokenizers fit the same mould:

**From string to ids**

1. **Normalization.** Clean the string with Unicode normalization (NFC or NFKC, which folds "ﬁ" to "fi" and full-width letters to ASCII), optional lowercasing and accent stripping (BERT-uncased does both), and whitespace cleanup. Whatever is normalized away cannot be recovered by decoding.
2. **Pre-tokenization.** Split the text into chunks that merges will never cross. Options are whitespace and punctuation (BERT), GPT-2's regex of letter runs, digit runs, symbol runs and contractions, splitting every digit (Llama 1 and 2), or none at all. SentencePiece treats the input as a raw stream and turns spaces into a visible `▁` (U+2581).
3. **Model.** Segment each chunk with the learned vocabulary: replay BPE merges, take the greedy longest WordPiece match, or find the most probable Unigram segmentation with Viterbi.
4. **Post-processing.** Add special tokens such as `[CLS]`/`[SEP]` (BERT), `<s>`/`</s>` (Llama, T5) or chat-template markers, then map pieces to ids.
5. **Decoding.** Invert the steps: ids to pieces, join, then undo the space marker (`Ġ`, `▁` or `##`). Byte-level and SentencePiece tokenizers are lossless. With BERT-uncased the case and accents are gone for good.

> Figure: The tokenization pipeline and the three subword families. Only the model stage is learned. BPE merges the most frequent pair, bottom-up. WordPiece merges the pair with the highest likelihood gain, c(ab)/(c(a)·c(b)), and encodes by greedy longest match with ## continuation pieces. Unigram starts from a large candidate set, prunes the pieces whose removal costs the least likelihood, and encodes with Viterbi. The axis at the bottom is the basic trade-off: bytes and characters give long sequences and never an unknown token, words give short sequences and many unknown words, and subword vocabularies of 32k–256k sit in between.

## The three subword algorithms

**BPE** builds up. It starts from characters or bytes and repeatedly merges the most frequent adjacent pair. The vocabulary is the base alphabet plus the merges, and encoding replays the merges in order. GPT-2/3/4, RoBERTa, Llama and Mistral use it. See **Byte-pair encoding (BPE)** for a step-by-step run.

**WordPiece** also builds up, but it scores a pair by how much merging it raises the likelihood of the training data under a unigram model. That reduces to the pair count normalised by the counts of its parts. It prefers pieces whose parts rarely occur apart, not just frequent ones. Encoding takes the **longest vocabulary match** from the left, marks word-internal pieces with `##`, and emits `[UNK]` for the whole word if a prefix cannot be matched. BERT's 30,522-entry vocabulary (`bert-base-uncased`) is WordPiece. See **WordPiece**.

$$
\text{BPE: }\arg\max_{(a,b)} c(a,b)\qquad\text{WordPiece: }\arg\max_{(a,b)}\frac{c(a,b)}{c(a)\,c(b)}\qquad\text{Unigram: }\max_{\mathcal V}\sum_{s}\log\sum_{\mathbf x\in S(s)}\prod_{i}p(x_i)
$$

- $c(a,b)$: count of the adjacent pair in the training words, weighted by word frequency
- $c(a)\,c(b)$: WordPiece's normaliser: a pair whose parts are common anyway scores lower
- $S(s)$: all segmentations of sentence $s$ into vocabulary pieces; Unigram treats the segmentation as a latent variable and fits $p(x)$ with EM
- $\mathcal V$: the vocabulary; Unigram starts large (e.g. all frequent substrings) and removes a fixed fraction per round (Kudo keeps the best 80%), always keeping single characters

**Unigram** works top-down. It assigns each piece a probability, models a word as a sequence of independent pieces, and fits the probabilities with EM over all segmentations. It then prunes the pieces whose removal lowers the corpus likelihood least, and repeats until it reaches the target size. Encoding picks the most probable segmentation with Viterbi. Because it is a real probabilistic model, it can also **sample** segmentations during training (subword regularization), which makes models more robust. T5, ALBERT, XLNet and mBART use Unigram through SentencePiece. See **Unigram tokenization** and **SentencePiece**.

**Vocabularies of real models**

- **BERT (2018):** WordPiece, 30,522 entries (`bert-base-uncased`), lowercasing and accent stripping, `##` continuation prefix
- **GPT-2 / GPT-3:** byte-level BPE, 50,257 tokens; regex pre-tokenization; a leading space is part of the token (`Ġthe`)
- **T5 (2020):** SentencePiece Unigram, 32,000 pieces, shared across English, German, French and Romanian
- **Llama 1 / 2:** SentencePiece BPE, 32,000 tokens, every digit a separate token, byte fallback for unknown characters
- **Llama 3 (2024):** tiktoken-based BPE, 128K tokens (128,256 with specials); Meta reported up to 15% fewer tokens than Llama 2's tokenizer
- **GPT-4 / GPT-4o:** tiktoken `cl100k_base` (about 100k) and `o200k_base` (about 200k); `cl100k_base` splits numbers into chunks of up to three digits
- **Gemma (2024):** SentencePiece with a 256k vocabulary, split digits and byte fallback

## Vocabulary size, fertility and fairness

$$
\text{fertility}=\frac{\#\text{tokens}}{\#\text{words}},\qquad \text{compression}=\frac{\#\text{bytes}}{\#\text{tokens}},\qquad \text{embedding params}=V\cdot d\ \ (\times2\ \text{if the LM head is untied})
$$

- $\text{fertility}$: average subwords per word (Rust et al., "How Good is Your Tokenizer?", ACL 2021). It is 1.0 for a word tokenizer. Higher values mean longer sequences and more fragmented words
- $\text{compression}$: bytes (or characters) per token: about 4 for English with 50k–100k BPE vocabularies, and much lower for languages the tokenizer saw little of
- $V\cdot d$: Llama 3 8B: $128{,}256\cdot4096=525{,}336{,}576$ parameters per matrix, and it has two (untied input and output). With $V=32{,}000$ it would be $131{,}072{,}000$

A larger vocabulary shortens sequences, so the same context window holds more text and generation needs fewer steps. The costs are a bigger embedding table and softmax, and rarer tokens that each get fewer training updates. A vocabulary trained mostly on English also splits other languages into many more pieces, and more tokens means more compute, more API cost and less effective context for the same content. Rust et al. found that monolingual tokenizers with lower fertility helped downstream performance compared with multilingual ones. That is one reason recent multilingual models moved to 128k–256k vocabularies.

> Figure: One sentence, four tokenizers, all built from the same 131-word English corpus. A byte-level BPE is trained live on that corpus and stops at 120 merges, when no pair occurs twice. At the default 50 merges (vocabulary 306), 'the model reads the tokens' is 26 characters, 26 bytes, 5 words, and 8 BPE tokens: Ġthe|Ġmodel|Ġr|ea|ds|Ġthe|Ġtoken|s, fertility 1.60. With all 120 merges it drops to 6 tokens (1.20), and the corpus compresses from 1.0 to 2.90 bytes per token (1.86 at 50 merges). 'tokenizers split unseen wordz' shows the open-vocabulary win. The word tokenizer gives two [UNK], while BPE spells everything from pieces: 15 tokens at 50 merges and 10 at 120 (Ġtokenizer|s|Ġspl|it|Ġun|s|e|en|Ġword|z). The French sentence has two characters (é, è) missing from the character vocabulary, all 5 of its words are unknown to the word tokenizer, and BPE plateaus at 18 tokens (3.60 per word) from 50 merges on, because English merges barely apply. é and è cost two byte tokens each, but nothing is lost. The upper-case sentence stays at 27 BPE tokens (5.40 per word) at any merge count, with 22 unknown characters. Turn on the lowercase normalizer and it becomes identical to the first sentence.

## Worked example: one sentence, four tokenizers

Take the sentence "tokenizers split unseen wordz": 4 words, 29 bytes, all ASCII. Build every tokenizer from the 131-word corpus in the figure. The character vocabulary has 28 symbols, the word vocabulary 86 words (each +1 for `[UNK]`), and the BPE vocabulary has $256+m$ entries.

Token counts and fertility (computed with the figure's code and checked in Python)

| tokenizer | vocab | tokens | fertility | unknown | segmentation |
| --- | --- | --- | --- | --- | --- |
| character | 29 | 29 | 7.25 | 0 | t o k e n i z e r s ␣ s p l i t … |
| byte | 256 | 29 | 7.25 | 0 | same 29 bytes |
| word | 87 | 4 | 1.00 | 2 | tokenizers split [UNK] [UNK] |
| BPE, 0 merges | 256 | 30 | 7.50 | 0 | Ġ t o k e n … (bytes + prefix space) |
| BPE, 25 merges | 281 | 19 | 4.75 | 0 | Ġtoken i z er s Ġs p l i t Ġ u n s e en Ġwor d z |
| BPE, 50 merges | 306 | 15 | 3.75 | 0 | Ġtokenizer s Ġsp l i t Ġ u n s e en Ġwor d z |
| BPE, 120 merges | 376 | 10 | 2.50 | 0 | Ġtokenizer s Ġspl it Ġun s e en Ġword z |

**Reading the table**

1. The word tokenizer is shortest (4 tokens) but loses two of four words to `[UNK]`. The model cannot tell *unseen* from *wordz*, or from any other unknown word.
2. Characters and bytes are lossless but 7.25 tokens per word. For a 4,096-token context that is about 565 words, against 4,096 words for an idealised word tokenizer.
3. BPE with 120 merges keeps every byte of information in 10 tokens. *tokenizers* becomes `Ġtokenizer` + `s`, and the typo *wordz* becomes the known `Ġword` + `z`, so the model sees the word it resembles.
4. The prepended space costs one token at 0 merges (30 vs 29). Merges then absorb it into word-initial tokens like `Ġtoken`, which is why GPT-style tokens carry their leading space.
5. Scale check: at $d=4096$, going from 376 to 128,256 entries adds $(128{,}256-376)\cdot4096\approx524$M parameters per embedding matrix. That is the price of real-world fertility near 1.3.

```python
from tokenizers import Tokenizer, decoders, models, normalizers, pre_tokenizers, trainers

def build(kind, vocab_size=8000, files=("corpus.txt",)):
    if kind == "bpe":          # GPT-2 style: byte-level, lossless, no unknown token
        tok = Tokenizer(models.BPE())
        tok.pre_tokenizer = pre_tokenizers.ByteLevel(add_prefix_space=True)
        tok.decoder = decoders.ByteLevel()
        trainer = trainers.BpeTrainer(vocab_size=vocab_size, special_tokens=["<|endoftext|>"],
                                      initial_alphabet=pre_tokenizers.ByteLevel.alphabet())
    elif kind == "wordpiece":  # BERT style: lowercase, strip accents, ## continuations
        tok = Tokenizer(models.WordPiece(unk_token="[UNK]"))
        tok.normalizer = normalizers.BertNormalizer(lowercase=True)
        tok.pre_tokenizer = pre_tokenizers.BertPreTokenizer()
        tok.decoder = decoders.WordPiece()
        trainer = trainers.WordPieceTrainer(vocab_size=vocab_size,
                                            special_tokens=["[UNK]", "[CLS]", "[SEP]", "[PAD]", "[MASK]"])
    else:                      # T5 / SentencePiece style: NFKC, ▁ for spaces, Viterbi encoding
        tok = Tokenizer(models.Unigram())
        tok.normalizer = normalizers.NFKC()
        tok.pre_tokenizer = pre_tokenizers.Metaspace()
        tok.decoder = decoders.Metaspace()
        trainer = trainers.UnigramTrainer(vocab_size=vocab_size, unk_token="<unk>", special_tokens=["<unk>"])
    tok.train(list(files), trainer)
    return tok

text = "Tokenizers split unseen wordz, and le café est très bon."
n_words = len(text.split())
for kind in ("bpe", "wordpiece", "unigram"):
    tok = build(kind)
    enc = tok.encode(text)
    print(f"{kind:9s} V={tok.get_vocab_size():5d} tokens={len(enc.ids):3d} "
          f"fertility={len(enc.ids) / n_words:.2f} lossless={tok.decode(enc.ids) == text}")
    print("          ", enc.tokens)
```

Train BPE, WordPiece and Unigram tokenizers on the same corpus with Hugging Face tokenizers, then compare token counts, fertility and round-trips (not run here)

> **The tokenizer is part of the model:** A checkpoint is only valid with the exact tokenizer it was trained with: the same vocabulary, merges, normalizer, pre-tokenizer and special tokens. Change any of them and the ids no longer mean what the embeddings learned. Small inconsistencies also hurt. `"Hello"` and `" Hello"` are different GPT-2 tokens, so a prompt that ends in a space, or text glued to a chat template without the expected separator, gives the model token sequences it rarely saw in training.

> **Tokenization explains odd LLM failures:** A model that cannot count the letters in a word never saw the letters. It saw one or two opaque ids. Arithmetic suffers when numbers are chunked inconsistently ("1234" as `123` + `4` but "2341" as `23` + `41`), which is why Llama splits every digit and `cl100k_base` groups at most three. Unicode look-alikes, odd spacing and rare scripts all change the token sequence, and with it the behaviour.

> **Byte-level and tokenizer-free models:** Byte-level BPE keeps a 256-symbol base, so there is no `<unk>`, but it still learns merges. ByT5 (Xue et al., 2022) and CANINE (Clark et al., 2022) drop the learned vocabulary and work directly on bytes or characters. They are more robust to noise and spelling, but sequences are several times longer, so they need architectural changes (downsampling, local attention) to stay affordable.

**Strengths**

- Subword vocabularies cover any text with a fixed V and no unknown words (with a byte or byte-fallback base)
- Frequent words stay whole, so sequences are short where data is rich
- Rare and new words share pieces (Ġword + z), so the model can generalise from them
- Training a tokenizer takes minutes and is independent of the model

**Limitations**

- The vocabulary freezes the training-data mix: under-represented languages and domains get high fertility
- Tokens hide characters: spelling, counting letters and digit arithmetic get harder
- Large V costs V·d parameters in the embedding and LM head, and rare tokens are undertrained
- Brittle at the edges: leading spaces, Unicode normalization and special tokens must match training exactly

- **Pretraining:** Choosing V and the training mix of the tokenizer sets sequence lengths, and so the compute per document, for the whole run.
- **Multilingual models:** Fertility per language is the first thing to check; 128k–256k vocabularies and balanced tokenizer training data reduce the gap.
- **Code models:** Pre-tokenization of whitespace and indentation runs matters: merging runs of spaces shrinks Python files considerably.
- **Cost and context budgeting:** API prices and context limits are per token, so the same document costs different amounts with different tokenizers.

**Question:** A word-level tokenizer gives 'tokenizers split unseen wordz' as 4 tokens and BPE gives 10. Why is BPE still preferred?

- A. BPE sequences are shorter on average
- B. The word tokenizer maps 'unseen' and 'wordz' to [UNK], losing them; BPE represents every word from known pieces
- C. BPE uses a larger vocabulary than the word tokenizer
- D. Word tokenizers cannot handle spaces

**Answer:** B. The word tokenizer maps 'unseen' and 'wordz' to [UNK], losing them; BPE represents every word from known pieces — Word-level sequences are shorter, but every out-of-vocabulary word collapses to the same `[UNK]` id. BPE's base symbols cover every byte, so nothing is lost. The typo *wordz* even shares `Ġword` with the correct spelling.

**Question:** How does Unigram tokenization build its vocabulary, compared with BPE?

- A. Like BPE, it merges the most frequent pair, but with probabilities
- B. It starts from a large candidate set and prunes the pieces whose removal reduces corpus likelihood least, then encodes with Viterbi
- C. It uses a fixed list of English morphemes
- D. It keeps only whole words and falls back to bytes

**Answer:** B. It starts from a large candidate set and prunes the pieces whose removal reduces corpus likelihood least, then encodes with Viterbi — BPE and WordPiece grow a vocabulary bottom-up by merging. Unigram shrinks one top-down using an EM-trained unigram model over segmentations. Because it is probabilistic, it can also sample alternative segmentations for subword regularization (Kudo, 2018).

**Key points**

- Pipeline: normalize → pre-tokenize → segment with a learned model → add special tokens → ids; only the segmentation model is learned.
- Characters and bytes never meet unknown symbols but give 4–7 tokens per word; words give 1 but leave [UNK]s; subwords (32k–256k) sit in between.
- BPE merges by pair count, WordPiece by $c(ab)/(c(a)c(b))$ with greedy longest match, Unigram prunes a large vocabulary by likelihood and encodes with Viterbi.
- Fertility (tokens per word) and bytes per token measure tokenizer efficiency; the embedding table costs $V\cdot d$ (Llama 3 8B: 525M per matrix).
- A tokenizer trained mostly on one language splits others into many more tokens, so they pay more in compute, money and context.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
