What is a token? Subword tokenization (BPE, WordPiece, Unigram)
A language model never sees letters or words. It sees token IDs: whole numbers that stand for pieces of text. This session explains why modern models use subword pieces, how BPE builds them by merging the most common pair again and again, how WordPiece and Unigram do it differently, and what the size of the vocabulary costs in memory, compute and sequence length.
What you will learn
- The trade-off between characters, words and subwords: vocabulary size against sequence length, and the unknown-word problem
- BPE step by step: count pairs, merge the most frequent, repeat; and how a trained BPE encodes new text by merge rank
- Byte-level BPE (GPT-2, Llama 3): why starting from 256 bytes means no unknown tokens
- WordPiece (BERT): the likelihood-style merge score and greedy longest-match encoding with ##
- Unigram (SentencePiece, T5): a probability for every piece, Viterbi segmentation, EM training and subword sampling
- What the vocabulary size V costs: V·d embedding parameters, 2·V·d output FLOPs per token, logits memory, and tokens per word, with real numbers for GPT-2, Llama 2, Llama 3, Qwen2.5 and Gemma 2
- How to compare models with different tokenizers fairly: bits per byte instead of per-token perplexity
Why this matters
A language model cannot read text. It reads a list of whole numbers. The tokenizer is the program that turns text into that list and back. Each number is a token ID, and each ID stands for one piece of text: a token.
In session 1 we saw that a model predicts the next token, and in session 6 we built models that do this for words or characters. But which pieces should the model use? This choice is made once, before training, and it can never be changed later without retraining the embedding table. It decides:
- How long every sequence is. The same text can be 59 characters or 9 tokens. Attention cost grows with the square of the length, and the context window is counted in tokens, not words.
- How big the first and last layers are. Every token in the vocabulary has a row in the embedding table and a row in the output layer. For Llama 3 8B these two tables hold about 1.05 billion parameters, 13% of the model. [Certain]
- What the model can see. If “2024” is one token, the model never sees its digits. Many strange failures in arithmetic, spelling and rare languages start here (session 9).
Almost every model you will meet uses one of three subword methods. GPT-2, GPT-4, Llama 3 and Qwen use byte-level BPE. BERT uses WordPiece. T5, ALBERT and many multilingual models use the Unigram model from the SentencePiece library. Llama 1 and 2 use SentencePiece too, but in BPE mode. [Certain] Gemma also uses SentencePiece. [Likely: in BPE mode] By the end of this session you will be able to run each algorithm by hand.
Characters, words or subwords?
There are three natural ways to cut text into pieces. Each one makes a different trade between the vocabulary size \(V\) (how many different tokens exist) and the sequence length \(n\) (how many tokens one text needs).
- Characters. A tiny vocabulary: the novel Pride and Prejudice uses only 86 different characters. But sequences are long: one token per character, about 5.7 tokens per English word. The model must spend its layers just to learn spelling, and the context window fills up fast.
- Words. Short sequences, one token per word. But the vocabulary explodes. The same novel has 6,298 different lower-case words, and 2,374 of them (38%) appear only once. Worse, new words keep coming: if we build a word vocabulary from the first half of the book, 3.8% of the words in the second half are not in it. Every such word becomes one useless unknown token
[UNK]. Words like “tokenization”, “COVID-19”, a typo, a URL or a name in another language would all be[UNK]. [Certain: measured on the Project Gutenberg text] - Subwords. The middle path. Common words stay whole (“the”, “ important”), rare words are split into common parts (“Token” + “ization”), and anything can be spelled with small pieces when needed. Vocabularies of 30K to 256K pieces give about 1.3 to 1.5 tokens per English word.
Two numbers describe a tokenizer on a text. The fertility is the number of tokens per word, and the compression is the number of characters (or bytes) per token:
- Read the symbols
- \(n_{\text{tokens}}\)
- how many tokens the tokenizer produces for the text
- \(n_{\text{words}}\)
- how many words the text has (here: pieces between spaces)
- \(n_{\text{chars}}\)
- how many characters the text has; use bytes instead for byte-level tokenizers
On the full text of Pride and Prejudice (694,457 characters, 122,410 words) the GPT-2 tokenizer needs 178,741 tokens: 1.46 tokens per word and 3.89 characters per token. The Llama 3 tokenizer needs 164,167 tokens: 1.34 tokens per word and 4.23 characters per token. [Certain: measured with the Hugging Face tokenizers]
Figure 1 shows four short texts cut into plain characters, into words, and by five real tokenizers. Look at how each one handles a rare word, numbers, French and code.
How to read Figure 1
Compare the counts on the left. On “Rare word”, GPT-2 keeps “ unbelievably” as one token, while BERT needs five pieces (un ##bel ##ie ##va ##bly): its vocabulary is smaller and built differently. On “Numbers”, Llama 2 splits every digit, Llama 3 groups up to three digits, and GPT-2 has “ 2024” as one token. On “French”, the English-centered GPT-2 needs 13 tokens, Llama 3 only 10. On “Code”, look at the four spaces of indentation: GPT-2 spends three tokens on them, Llama 3 one, and BERT and T5 drop them completely, which is fatal for Python.
Notice the leading spaces. In GPT-2 and Llama 3, “ is” (with a space) and “is” are different tokens with different IDs. The space belongs to the start of the next word. SentencePiece does the same with a visible marker, “▁is”. BERT throws spaces away and remembers word starts with ## on the pieces that are not at the start.
Byte-Pair Encoding, step by step
Byte-Pair Encoding (BPE) began as a data compression trick: replace the most common pair of bytes with a new byte, and repeat. Sennrich, Haddow and Birch (2015) used the same idea to build subword vocabularies for translation. [Certain] Training needs only a word list with counts. It goes like this:
- Start with a base vocabulary: all single characters (or, for byte-level BPE, all 256 byte values). Write every word as a list of these symbols.
- Count every pair of neighbor symbols, weighted by how often the word appears.
- Take the most frequent pair, for example (
e,s), and add the joined symbolesto the vocabulary. Replace that pair everywhere. This is one merge; write it down in a list. - Repeat steps 2 and 3 until the vocabulary has the size you want.
In symbols: let each word \(w\) appear \(f(w)\) times and currently be written as symbols \(s_1 s_2 \dots s_m\). The count of a pair is
and each merge picks the best pair and grows the vocabulary by one:
- Read the symbols
- \(f(w)\)
- how many times the word \(w\) appears in the training text
- \(|\{ i : \dots \}|\)
- how many positions in the word hold the pair \(a\) followed by \(b\)
- \(\mathcal{V}_0, \mathcal{V}_k\)
- the base vocabulary, and the vocabulary after \(k\) merges
- ties
- when two pairs have the same count, we take the pair seen first in the text (this is what
maxdoes in Python, and what Karpathy’s minbpe does)
Here is the toy example from the original paper: the words “low” 5 times, “lower” 2 times, “newest” 6 times and “widest” 3 times. A special end-of-word symbol </w> marks where each word ends, so that “est” at the end of a word can become a different token from “est” inside a word.
Figure 2 runs the training loop (Algorithm 1, written out below) in your browser, one operation at a time. First it scans the words one by one and adds \(f(w)\) to every neighbor pair it finds: this is the sum in (8.2), built term by term. Then it picks the winner (8.3), replaces that pair in every word, and appends it to the merge list. The program on the left highlights the line being run; the panel on the right writes that line with the live numbers. You can switch to a second corpus (the “hug” example of the Hugging Face course), change the target vocabulary size, or switch the rule to WordPiece.
Corpus: each word as its current symbols
Pair counts (8.2)
- input: word counts \(f(w)\), target size \(V\)
- \(\mathcal{V} \leftarrow\) base symbols; write each word as base symbols
- merges \(\leftarrow\) empty list
- while \(|\mathcal{V}| \lt V\):
- for each word \(w\): add \(f(w)\) to each of its pairs // (8.2)
- \((a^*, b^*) \leftarrow\) best pair; ties: first seen // (8.3) or (8.4)
- replace every \(a^*\, b^*\) by \(a^*b^*\) in all words
- append \((a^*, b^*)\) to merges; add \(a^*b^*\) to \(\mathcal{V}\)
- return \(\mathcal{V}\), merges
Merge list (the trained tokenizer)
Vocabulary
How to read Figure 2
Press Play on the first corpus. In the first round, “low” adds 5 to (l, o), (o, w) and (w, </w>); “newest” adds 6 to six pairs; after the four words, (e, s), (s, t) and (t, </w>) all have count \(9 = 6 + 3\). They tie, and (e, s) wins because it was seen first. The first three merges build est</w>, because “est” ends 9 of the 16 words. The corpus shrinks from 95 symbols to 68, and after 10 merges (\(V = 21\)) to 28: “newest” and “low” are single tokens. Use “Next merge” to jump one whole round. Now switch to WordPiece. Its first merge is i + d, a pair that occurs only 3 times, because i and d never appear anywhere else (score \(3 / (3 \times 3) = 0.3333\)). BPE prefers pairs that are frequent; WordPiece prefers pairs whose parts almost always appear together. On the “hug” corpus (149 symbols), BPE first merges (u, g) with count \(10 + 5 + 5 = 20\), while WordPiece first merges (g, s) with score \(5 / (20 \times 5) = 0.05\). If you set \(V\) high enough, the loop can also stop early: on the “hug” corpus every word is a single token after 11 merges, so there is no pair left to count.
At the start, the corpus is 95 symbols: “low” is 4 symbols with </w>, \(\times\, 5 = 20\); “lower” \(6 \times 2 = 12\); “newest” \(7 \times 6 = 42\); “widest” \(7 \times 3 = 21\). The base vocabulary has 11 symbols: d e i l n o r s t w and </w>.
Merge 1. The pair (e, s) appears once in “newest” (6 times) and once in “widest” (3 times): count 9. The pairs (s, t) and (t, </w>) also have 9, but (e, s) is seen first. Merging it saves 9 symbols: \(95 \to 86\). Vocabulary: 12.
Merge 2. Now (es, t) has count 9 and comes first: \(86 \to 77\). Merge 3: (est, </w>), count 9: \(77 \to 68\). Vocabulary: 14. Merges 4 and 5 then build “low” (count 7, from “low” and “lower”).
Encoding new text with a trained BPE
The trained tokenizer is just the base vocabulary plus the ordered list of merges. To encode a new word, start from its characters and keep applying the merge that was learned earliest (the lowest rank) among the pairs present, until no learned merge applies. With the 10 merges above, “lowest” (never seen in training) becomes low + est</w>: two known tokens. “newer” becomes new e r </w>: the end “er” was not frequent enough to earn a merge.
- input: word counts \(f(w)\), target vocabulary size \(V\)
- \(\mathcal{V} \leftarrow\) all base symbols (characters, or the 256 bytes); write each word as base symbols
- merges \(\leftarrow\) empty list
- while \(|\mathcal{V}| \lt V\):
- count all neighbor pairs, weighted by \(f(w)\) // formula (8.2)
- \((a^*, b^*) \leftarrow\) the pair with the highest count; break ties by first appearance // formula (8.3)
- replace every \(a^*\, b^*\) by the new symbol \(a^*b^*\) in all words
- append \((a^*, b^*)\) to merges; add \(a^*b^*\) to \(\mathcal{V}\)
- return \(\mathcal{V}\), merges
- input: a piece of text \(x\) (one word with its leading space), merges with ranks \(r(a, b)\)
- \(s \leftarrow\) the base symbols of \(x\) (characters, or UTF-8 bytes)
- loop:
- among all neighbor pairs in \(s\), find the one with the lowest rank \(r\)
- if no pair has a rank: stop
- merge every occurrence of that pair in \(s\)
- return the IDs of the symbols in \(s\)
Figure 3 runs Algorithm 2 on a word you choose, with the merges that BPE learned on the toy corpus. Each round lists every neighbor pair with its rank \(r\) (its position in the merge list; “–” means the pair was never learned), takes the lowest rank, and merges it. The rounds stack up as rows, so you can see the word shrink. Note that the order of the merges comes from the merge list, not from left to right in the word.
The word, one row per merge
Merge list with ranks \(r\)
- input: a word \(x\), merges with ranks \(r(a, b)\)
- \(s \leftarrow\) the characters of \(x\), then
</w> - loop:
- among the neighbor pairs in \(s\), find the lowest rank \(r\)
- if no pair has a rank: stop
- merge every occurrence of that pair in \(s\)
- return the IDs of the symbols in \(s\)
</w> last, then one ID per merge.How to read Figure 3
Play “lowest” with \(K = 10\). In round 1 the pairs (l, o) with rank 4 and (e, s) with rank 1 are both known; (e, s) wins although it is further right. Then (es, t) rank 2, (est, </w>) rank 3, (l, o) rank 4 and (lo, w) rank 5. Now the only pair is (low, est</w>), which is not a merge, so the loop stops: two tokens, IDs 15 and 13. Try “newer”: it stops at new e r </w> because no “er” merge was learned. Lower \(K\) to 2 and “lowest” stays in 5 pieces (l o w est </w>): with fewer merges, words are longer. Switch to the “hug” merges and try “puns”: it becomes p un s </w>. The merge list has (p, un</w>) but no (p, un), so “pun” is only a token at the end of a word. Type “Hugs”: the capital H never appeared, so it is red and no pair with it has a rank.
Training is fast in practice because counts are kept per distinct word, not per position in the text, and only the counts next to a merge change. Encoding is fast because each pre-token is short. Real libraries (tiktoken, Hugging Face tokenizers) do both in Rust.
Pre-tokenization, and BPE on a real text
Before BPE runs, the text is cut into pre-tokens, roughly words with their leading space, numbers and punctuation runs. Merges never cross a pre-token boundary, so no token can contain “dog. The”. GPT-2 does this with a regular expression; Llama 3 and GPT-4 use a refined one that also limits digit groups to three. [Certain] The lab session 10 builds this regex step by hand.
Figure 4 trains BPE live, in your browser, on the first chapter of Pride and Prejudice (4,442 characters and 847 words, without the picture captions). The pre-tokens are a space plus letters, digits or punctuation, as in GPT-2 (simplified).
How to read Figure 4
The first merge is “ t” (a space and t), exactly like the first merge of the real GPT-2 tokenizer (Ġ t). Then come “he”, “ a”, “ou”, “in”. Early merges give a big drop in tokens per word; later merges help less and less, because each new token covers rarer text. After 300 merges the chapter needs about 2 tokens per word (1.95). Look at the test sentence: “ Bennet” is a single token after 200 merges and “ Bingley” after 500, because the chapter talks about them a lot, while “earliest” stays in pieces. Near 200 merges you can watch BPE build “ neighbourhood” one letter group at a time: rare words are learned last, and only because they appear a few times in this tiny corpus. Type “Café” or “Queen”: the capital letters C and Q and the “é” never appear in this chapter, so they have no token. A byte-level BPE would fall back to bytes instead (next section).
Byte-level BPE: no unknown tokens
A character-level base vocabulary has a problem: there are about 150,000 Unicode characters, and any of them may appear one day. GPT-2 solved this by running BPE on bytes. Every text is first encoded as UTF-8, where each character becomes 1 to 4 bytes: “a” is 1 byte, “è” 2 bytes, most Chinese characters 3 bytes, an emoji 4 bytes. The base vocabulary is the 256 possible byte values, so every string can be encoded and an unknown token is impossible. [Certain]
GPT-2 has 256 base bytes, 50,000 merges and one special token <|endoftext|>: \(256 + 50{,}000 + 1 = 50{,}257\) tokens, the vocabulary size in its config. [Certain] To keep the vocabulary files readable, GPT-2 maps each byte to a printable character; that is why the space appears as Ġ and a newline as Ċ in its files. In Figure 1, the French “è” is two bytes; GPT-2 merges them into one token, but a rare character can stay as two or three byte tokens that are not valid text on their own.
SentencePiece BPE (Llama 2) reaches the same goal differently: it keeps a character vocabulary and uses byte fallback. A character that is not in the vocabulary is written as byte tokens such as <0x0A> (the newline in Figure 1). [Certain]
WordPiece: merge by score, encode by longest match
WordPiece was made at Google for Japanese and Korean voice search (Schuster and Nakajima, 2012), then used in Google’s translation system and in BERT. [Certain] Google never released the training code, so what follows is the standard description from the Hugging Face course. [Likely] It is BPE with two changes.
Change 1: the merge score. Instead of the raw count, WordPiece merges the pair with the highest
Why this ratio? If \(N\) is the total number of symbols, the probability of the pair divided by the probabilities of its parts is
The log of this ratio is the pointwise mutual information of \(a\) and \(b\): how much more often they appear together than chance would predict. \(N\) is the same for all pairs in a step, so WordPiece merges the pair with the highest mutual information. It is the merge that most improves the likelihood of the training text under a simple “independent pieces” model. Back in Figure 2: BPE first merges the frequent (e, s); WordPiece first merges (i, d), which is rare but always together.
Change 2: encoding by greedy longest match. WordPiece does not store merges. It stores only the vocabulary, with ## in front of pieces that continue a word. To encode a word, take the longest vocabulary piece that matches the start, then the longest ## piece that matches the rest, and so on. If at some point no piece matches, the whole word becomes [UNK]. BPE would mark only the missing character. [Certain]
- input: a word \(w\) (spaces already removed), vocabulary \(\mathcal{V}\) with
##pieces - start \(\leftarrow 0\); pieces \(\leftarrow\) empty
- while start \(\lt |w|\):
- for end from \(|w|\) down to start + 1: candidate \(\leftarrow w[\text{start}:\text{end}]\), with
##in front if start \(\gt 0\) - if candidate \(\in \mathcal{V}\): append it, start \(\leftarrow\) end, and go back to the while
- no candidate found: return [
[UNK]] // the whole word is lost - return pieces
BERT’s uncased vocabulary has 30,522 entries. [Certain] In Figure 1 it cuts “unbelievably” into un ##bel ##ie ##va ##bly. BERT also lower-cases and strips accents in its uncased version, and splits on spaces and punctuation first, so it loses all whitespace. That is fine for classification, and bad for generating code.
Unigram: a probability for every piece
BPE and WordPiece build the vocabulary from small to large, and encode with fixed rules. The Unigram language model (Kudo, 2018) turns this around. It starts with a very large vocabulary and removes pieces. And it treats tokenization as a probability question: every piece \(t\) has a probability \(p(t)\), and the pieces of a word are assumed independent. A segmentation \(\mathbf{x} = (x_1, \dots, x_m)\) of the word then has probability
Encoding picks the most likely segmentation among all segmentations \(S(w)\) of the word:
A word of length \(L\) has up to \(2^{L-1}\) segmentations, too many to list. But the best one can be found with dynamic programming, the Viterbi algorithm. Let \(\text{best}(i)\) be the best log-probability of the first \(i\) characters, with \(\text{best}(0) = 0\):
- Read the symbols
- \(w_{j:i}\)
- the characters of the word from position \(j\) up to (not including) \(i\)
- \(\text{best}(i)\)
- the log-probability of the best way to cut the first \(i\) characters; remember which \(j\) won, and walk back from the end to read the pieces
- cost
- \(O(L \cdot \ell_{\max})\) steps, where \(\ell_{\max}\) is the longest piece
Training: EM and pruning
Training needs the piece probabilities, but those depend on how words are cut, which depends on the probabilities. The EM algorithm (expectation maximization) breaks this circle. Start with a big seed vocabulary (for example all frequent substrings) and probabilities from raw counts. Then repeat: cut every word in all possible ways, weight each way by its probability (E-step), and set each \(p(t)\) to its expected count, normalized (M-step). This raises the likelihood of the corpus:
Then prune: for each piece, estimate how much \(\mathcal{L}\) would drop if the piece were removed, and remove the pieces that matter least (the paper keeps the best 80% each round; SentencePiece’s default keeps 75%) [Likely]. Single characters are never removed, so every word can still be spelled. Repeat EM and pruning until the vocabulary reaches the target size. [Certain]
- input: word counts \(f(s)\), target size \(V\), keep ratio \(\rho\) (for example 0.8)
- \(\mathcal{V} \leftarrow\) seed: all characters plus the most frequent substrings; \(p(t) \propto\) count of \(t\)
- repeat:
- run a few EM steps: expected counts of each piece over all segmentations, then normalize // raises (8.9)
- if \(|\mathcal{V}| \le V\): stop
- for every piece that is not a single character, compute the loss in \(\mathcal{L}\) if it were removed
- keep the \(\max(V, \rho|\mathcal{V}|)\) pieces with the largest loss (plus all characters)
- return \(\mathcal{V}\) and \(p\)
Subword regularization
Because Unigram has probabilities, it can also sample a segmentation instead of always taking the best one. During training of the language model, each word is cut in a random way, with probability
With \(\alpha = 1\) this is the model’s own distribution; smaller \(\alpha\) makes it flatter (more random cuts). The model sees “new + est” most times and “newe + st” sometimes, and becomes more robust to unusual splits and typos. Kudo found gains in translation, especially with little data. BPE-dropout (randomly skipping merges) gives BPE the same ability. [Certain] Large LLMs are usually pretrained with deterministic tokenization. [Likely]
Figure 5 runs the whole Unigram pipeline on the same toy corpus as Figure 2. The seed vocabulary is every substring of up to 4 characters (39 pieces).
Segmentations of the word
Vocabulary and \(p(t)\)
How to read Figure 5
At the seed stage, “newer” has three cuts with exactly the same probability: raw substring counts cannot decide. After EM, the probabilities reflect how pieces are really used, and the corpus log-likelihood rises from −83.83 to −54.25. Pruning removes 19 pieces such as “west” and “lo”, and the second EM round leaves 18 pieces. Now “newest” is cut as “new + est” 55% of the time and “newe + st” 44%: both are plausible. Lower \(\alpha\) and the sampling spreads over more cuts. “newer” and “wider” were never in the corpus, yet they get sensible cuts (“new + er”, “wid + er”).
SentencePiece: one library, raw text in
SentencePiece (Kudo and Richardson, 2018) is a library, not a new algorithm. It trains and runs either BPE or Unigram. Its main idea: treat the input as a raw stream of characters, including spaces. It replaces each space with the visible symbol “▁” (U+2581) and then tokenizes, so there is no language-specific word splitting. This matters for Chinese and Japanese, which do not put spaces between words. Decoding is exact: join the pieces and turn “▁” back into spaces. [Certain]
So when people say “a SentencePiece tokenizer”, ask which mode. T5 and ALBERT use Unigram. Llama 1 and 2 use SentencePiece BPE with all numbers split into single digits and byte fallback for unknown characters. Gemma uses SentencePiece with a 256K vocabulary. [Certain] Llama 3 moved to a tiktoken-style byte-level BPE with 128K tokens: 100K tokens from tiktoken plus 28K extra tokens for other languages. [Certain]
| BPE | WordPiece | Unigram | |
|---|---|---|---|
| Builds the vocabulary | bottom-up: merge the most frequent pair | bottom-up: merge the pair with the highest score (8.4) | top-down: start big, prune the least useful pieces |
| Stores | vocabulary + ordered merge list | vocabulary only (with ##) | vocabulary + a log-probability per piece |
| Encodes by | applying merges in rank order | greedy longest match | Viterbi: most likely segmentation |
| Unknown input | byte-level: impossible; char-level: unknown character | the whole word becomes [UNK] | unknown character (or byte fallback) |
| Can sample cuts | with BPE-dropout | no | yes, natively (8.10) |
| Used by | GPT-2/3/4, Llama 1/2/3, Qwen, Mistral [Certain]; Gemma [Likely] | BERT, DistilBERT, ELECTRA [Certain] | T5 (checked: its file stores a log-probability per piece); mT5, ALBERT, XLNet [Likely] |
What the vocabulary size costs
A bigger vocabulary shortens every sequence, but it is paid for in two places: the input embedding, a table with one row of \(d\) numbers per token, and the output layer (the “LM head”), a matrix that turns the final hidden vector into \(V\) scores, one per token. For a model width \(d\):
- Read the symbols
- \(V, d\)
- vocabulary size and model width (hidden size)
- tied
- input and output use the same matrix (GPT-2, Llama 3.2 1B, Qwen2.5-0.5B). Large models usually keep two separate matrices.
- \(2Vd\)
- one multiply and one add for each of the \(V \times d\) weights of the output layer. The input embedding is a table lookup and costs almost nothing.
- \(B, T\)
- batch size and sequence length: during training the scores of every position are kept for the loss
Both have \(d = 4096\) and separate input and output matrices. Llama 2: \(32{,}000 \times 4096 = 131.1\)M parameters per matrix, 262M for both, 3.9% of its 6.74B. Llama 3: \(128{,}256 \times 4096 = 525.3\)M per matrix, 1.05B for both, 13.1% of its 8.03B. The output layer costs \(2Vd = 1.05\) GFLOPs per token instead of 0.26: about 7.0% of the forward matrix work of Llama 3 8B, against 2.0% for Llama 2. [Certain: computed from the config.json files]
What does it buy? On Pride and Prejudice, the Llama 2 tokenizer needs 183,153 tokens and the Llama 3 tokenizer 164,167: 10.4% fewer. The 8,192-token window of Llama 3 holds about 34,700 characters of the novel instead of about 31,100. Attention-score work, which grows with the square of the length, drops by \(1 - 0.896^2 = 19.7\%\) for the same text. Meta reports \(3.17 \to 3.94\) characters per token on its English sample. [Certain]
The hidden cost is memory for logits: one batch of 8 sequences \(\times\) 8,192 tokens \(\times\) 128,256 scores in FP32 is \(33.6\) GB, against 8.4 GB with a 32K vocabulary. This is why training code computes the loss in chunks or with fused kernels (session 38).
Two more effects are easy to forget. First, with \(V \gt 65{,}536\) token IDs no longer fit in 16 bits: GPT-2 (50,257) can store its training data as uint16, Llama 3 needs 32-bit integers, which doubles the size of a tokenized dataset on disk. Second, the rarest tokens of a huge vocabulary are seen only a few times in training, so their embeddings stay poorly trained. Some become “glitch tokens” (session 9). Bigger is not always better, and the best \(V\) grows with model size. [Likely] For small models like Qwen2.5-0.5B, the vocabulary matrix is 27.6% of all weights.
How to read Figure 6
The curve falls fast and then flattens: 5.7 tokens per word with bytes only, 2.0 with 2,000 merges, 1.65 at 10K and 1.46 at 50K. Going from 10K to 40K merges saves 10% of tokens, but quadruples the vocabulary matrix. Choose “Llama 3.2 1B”: with \(d = 2048\) and a 128K vocabulary, the (tied) table is 21% of the model, and the output layer is 21% of the forward compute. Choose “Llama 2 7B” and slide \(V\) up to 128K: the share grows from 3.9% to about 14%. For large models the vocabulary is cheap; for small ones it is a big part of the budget.
Comparing models with different tokenizers
Perplexity and loss are averages per token (session 3). If model A uses short tokens and model B long ones, B has to predict more text per token, so its per-token loss is naturally higher, even if it is the better model. The fair measure is bits per byte (or per character): the total information cost of the text, divided by its length in bytes.
- Read the symbols
- \(\bar{\ell}_{\text{tok}}\)
- the usual average cross-entropy loss per token, in nats
- \(n_{\text{tok}} / n_{\text{bytes}}\)
- tokens per byte of this tokenizer on this text (1 / compression)
- \(\ln 2\)
- turns nats into bits
Suppose (made-up losses) model A has loss 2.0 nats per token with the GPT-2 tokenizer and model B has 2.2 nats per token with the Llama 3 tokenizer, both on Pride and Prejudice (703,237 bytes). Per token, A looks clearly better. But A needs 178,741 tokens (3.934 bytes per token) and B only 164,167 (4.284 bytes per token). A: \(2.0 / (\ln 2 \times 3.934) = 0.733\) bits per byte. B: \(2.2 / (\ln 2 \times 4.284) = 0.741\) bits per byte. A is only slightly better, by 1%, not by 10%.
In code: BPE, WordPiece, Unigram and the vocabulary cost
Everything above in about 80 lines. The output is deterministic; the comments show what it prints.
import math, torch torch.manual_seed(0) # 1) Train BPE (Algorithm 1) on the toy corpus of Sennrich et al. corpus = {"low": 5, "lower": 2, "newest": 6, "widest": 3} def merge_pair(symbols, pair): out, i = [], 0 while i < len(symbols): if i + 1 < len(symbols) and (symbols[i], symbols[i + 1]) == pair: out.append(symbols[i] + symbols[i + 1]); i += 2 else: out.append(symbols[i]); i += 1 return tuple(out) def train_bpe(corpus, num_merges): words = {tuple(w) + ("</w>",): f for w, f in corpus.items()} merges = [] for _ in range(num_merges): pairs = {} for w, f in words.items(): # formula (8.2) for p in zip(w, w[1:]): pairs[p] = pairs.get(p, 0) + f if not pairs: break best = max(pairs, key=pairs.get) # formula (8.3); ties: first pair seen merges.append(best) words = {merge_pair(w, best): f for w, f in words.items()} return merges merges = train_bpe(corpus, 10) print(merges[:4]) # [('e', 's'), ('es', 't'), ('est', '</w>'), ('l', 'o')] # 2) Encode with BPE (Algorithm 2): always apply the earliest-learned merge first rank = {p: r for r, p in enumerate(merges)} def encode_bpe(word): s = tuple(word) + ("</w>",) while len(s) > 1: r, pair = min((rank.get(p, math.inf), p) for p in zip(s, s[1:])) if r == math.inf: break s = merge_pair(s, pair) return list(s) print(encode_bpe("lowest"), encode_bpe("newer")) # ['low', 'est</w>'] ['new', 'e', 'r', '</w>'] # 3) WordPiece encoding (Algorithm 3): greedy longest match; "##" marks a piece inside a word wp_vocab = {"un", "##believ", "##able", "##ably", "token", "##ization", "##s"} def encode_wordpiece(word): out, start = [], 0 while start < len(word): for end in range(len(word), start, -1): # try the longest piece first piece = word[start:end] if start == 0 else "##" + word[start:end] if piece in wp_vocab: break else: return ["[UNK]"] # nothing fits: the whole word is unknown out.append(piece); start = end return out print(encode_wordpiece("unbelievably"), encode_wordpiece("tokenizations"), encode_wordpiece("tokenz")) # ['un', '##believ', '##ably'] ['token', '##ization', '##s'] ['[UNK]'] # 4) Unigram: Viterbi finds the most likely segmentation, formula (8.8) # (the 18-piece vocabulary of Figure 5, stage 4, rounded) p = {"low": .218, "est": .146, "st": .134, "new": .099, "newe": .088, "er": .062, "wid": .050, "wide": .044, "e": .019, "r": .016, "t": .016, "s": .016, "w": .016, "n": .016, "i": .016, "d": .016, "l": .016, "o": .016} def viterbi(word, max_len=4): best = [0.0] + [-math.inf] * len(word); back = [0] * (len(word) + 1) for i in range(1, len(word) + 1): for j in range(max(0, i - max_len), i): piece = word[j:i] if piece in p and best[j] + math.log(p[piece]) > best[i]: best[i], back[i] = best[j] + math.log(p[piece]), j pieces, i = [], len(word) while i > 0: pieces.insert(0, word[back[i]:i]); i = back[i] return pieces, round(best[-1], 2) print(viterbi("lowest"), viterbi("newest"), viterbi("wider")) # (['low', 'est'], -3.45) (['new', 'est'], -4.24) (['wid', 'er'], -5.78) # 5) What the vocabulary costs: input embedding and output layer (Llama 3 8B sizes) V, d = 128256, 4096 emb = torch.nn.Embedding(V, d, device="meta") # "meta": shapes only, no memory head = torch.nn.Linear(d, V, bias=False, device="meta") print(emb.weight.numel(), head.weight.numel()) # 525336576 525336576, formula (8.11) print(2 * V * d / 1e9, "GFLOPs per token for the output layer") # 1.050673152 ids = torch.randint(0, V, (2, 8)) # IDs above 65535 need more than 16 bits print(ids.dtype, math.ceil(math.log2(V)), "bits per ID") # torch.int64 17
To try real tokenizers, pip install tiktoken tokenizers, then tiktoken.get_encoding("cl100k_base").encode("Hello world") or tokenizers.Tokenizer.from_pretrained("gpt2"). The lab session 10 turns part 1 into a full byte-level tokenizer and compares it with these libraries.
Where this is used
| System | Tokenizer | Why it matters |
|---|---|---|
| GPT-2, GPT-4, Llama 3, Qwen2.5 | byte-level BPE; 50,257 / 100,277 / 128,256 / 151,665 tokens (Qwen pads its matrix to 151,936 or 152,064 rows) [Certain: from the tokenizer files] | No unknown tokens, handles code and any language; vocabulary sizes grew to cut sequence length |
| BERT and its family (search ranking, classifiers) | WordPiece, 30,522 (uncased) | Fine for understanding tasks; loses spaces and case, so not for code generation (session 33) |
| T5, mT5, ALBERT | SentencePiece Unigram | Language-independent, sampling of cuts possible (session 24) |
| Vision-language models (LLaVA, Qwen2-VL) | the LLM’s text tokenizer, plus image patches turned into “visual tokens” and placeholder tokens | Image and text share one sequence and one context budget (session 9, session 183) |
| Video-LLMs, Video-RAG, video retrieval | text tokens for questions, transcripts and captions; frames become many visual tokens | Transcripts (ASR text) of a 1-hour video are tens of thousands of tokens; fertility decides how much fits next to the frames (session 205) [Likely] |
| Image and video generation | “visual tokenizers” (VQ codebooks) that turn patches into discrete IDs | The same idea, a fixed vocabulary of pieces, applied to pixels (session 224) |
| API pricing and context limits | whatever the model uses | You pay and you are limited per token; languages with high fertility cost more (session 9) |
Common mistakes
- Thinking one token is one word. For English, 1.3 to 1.5 tokens per word is typical for modern tokenizers; for code, numbers and many other languages, far more. Always measure on your own data.
- Forgetting the leading space. “ Paris” and “Paris” are different tokens. Prompts that end with a space, or text glued without a space, produce unusual token sequences and worse outputs.
- Using a different tokenizer than the model was trained with. The IDs then point to the wrong embedding rows. The model still runs, without any error, and outputs garbage. Always load the tokenizer from the same checkpoint.
- Comparing perplexity across tokenizers. Per-token losses are not comparable; use bits per byte (8.12) or per character.
- Confusing training and encoding in BPE. At encoding time you do not count pairs in the new text. You apply the learned merges in their training order (Algorithm 2).
- Assuming WordPiece fails like BPE. One unknown character makes the whole word
[UNK]in WordPiece, not only that character. - Adding tokens without resizing the model. After adding new tokens, the embedding and output matrices need new rows (
resize_token_embeddings), and those rows must be trained (session 11). - Choosing a huge vocabulary for a small model. At 0.5B parameters, a 152K vocabulary already takes 28% of the weights; rare tokens also stay undertrained.
Interview questions
Why do LLMs use subword tokens instead of words or characters?basic
Walk me through BPE training on a small example.basic
How does a trained BPE tokenizer encode a new word? Is it greedy longest match?core
What is byte-level BPE and why does it have no unknown tokens?core
<|endoftext|> \(= 50{,}257\) tokens. The cost: some tokens are parts of a character and are not valid text alone, and languages whose characters take 2 to 3 bytes and appear less in training get more tokens per word.How is WordPiece different from BPE?core
Explain the Unigram tokenizer. How does it train and how does it encode?core
What is subword regularization, and why might it help?advanced
Llama 2 had 32K tokens, Llama 3 has 128K. What did this change cost and buy?advanced
Why can you not compare perplexities of models with different tokenizers? What do you use instead?advanced
Why do some tokenizers split numbers into single digits?core
How would you choose the vocabulary size for a new model?advanced
Exercises
- Continue BPE on the toy corpus after the 10 merges of Figure 2. Which pair is merge 11, and what is its count?
- With the 10 merges, how would a character-level BPE encode “lowly”? What would a byte-level BPE do differently?
- With the WordPiece vocabulary of the code, encode “unable” and “tokens”. What happens to “unbelievablyy”?
- With the final Unigram vocabulary (\(p(\text{low}) = 0.218\), \(p(\text{est}) = 0.146\), \(p(\text{e}) = 0.019\), \(p(\text{st}) = 0.134\)), compute \(P(\text{low}+\text{est})\) and \(P(\text{low}+\text{e}+\text{st})\). How many times more likely is the first?
- A model has \(d = 4096\), untied matrices and \(V = 64{,}000\). How many vocabulary parameters does it have, and how many output-layer GFLOPs per token?
- Show that the WordPiece score ranks pairs the same way as pointwise mutual information within one merge step.
Answerscheck
low + l + y + </w>, and y must be mapped to [UNK] (the merge low + </w> cannot apply, because “low” is followed by “l”). A byte-level BPE has all 256 bytes, so “y” is just the byte 0x79: no unknown token. 3. un ##able and token ##s. “unbelievablyy”: after un ##believ ##ably the last “y” needs ##y, which is not in the vocabulary, so the whole word becomes [UNK]. 4. \(0.218 \times 0.146 = 0.0318\); \(0.218 \times 0.019 \times 0.134 = 0.000555\); about 57 times more likely. 5. \(2 \times 64{,}000 \times 4096 = 524{,}288{,}000\) parameters; \(2 \times 64{,}000 \times 4096 = 0.524\) GFLOPs per token. 6. \(\log \frac{P(ab)}{P(a)P(b)} = \log N + \log \operatorname{score}(a, b)\) by (8.5). \(N\) is the same for every pair in one step, and log is increasing, so the order is the same.Key takeaways
- Tokenization trades vocabulary size against sequence length (8.1). Subwords keep common words whole and spell rare ones from parts; modern English fertility is about 1.3 to 1.5 tokens per word.
- BPE trains bottom-up: count pairs (8.2), merge the most frequent (8.3), repeat. It encodes by applying merges in rank order. Byte-level BPE starts from 256 bytes and never needs [UNK].
- WordPiece merges by \(\operatorname{count}(ab)/(\operatorname{count}(a)\operatorname{count}(b))\) (8.4), a mutual-information score (8.5), and encodes by greedy longest match with ##; an unmatched word becomes [UNK].
- Unigram gives each piece a probability (8.6), encodes with Viterbi (8.7, 8.8), trains top-down with EM and pruning (8.9), and can sample cuts (8.10). SentencePiece is the library that runs Unigram or BPE on raw text with “▁”.
- The vocabulary costs \(Vd\) parameters per matrix, \(2Vd\) FLOPs per token and \(BTV\) logits (8.11): small for Llama 3 8B (13%), large for small models. Compare models across tokenizers in bits per byte (8.12).
Key formulas
References for this session
- Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, chapter 2: Words and Tokens
- Sennrich et al. (2015). Neural Machine Translation of Rare Words with Subword Units
- Kudo & Richardson (2018). SentencePiece: A simple and language independent subword tokenizer
- Kudo (2018). Subword Regularization
- Karpathy (2024). minbpe: minimal BPE tokenizer (code)
- Schuster & Nakajima (2012). Japanese and Korean Voice Search
- Wu et al. (2016). Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation
- Devlin et al. (2018). BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
- Radford et al. (2019). Language Models are Unsupervised Multitask Learners
- Touvron et al. (2023). Llama 2: Open Foundation and Fine-Tuned Chat Models
- Llama Team, Meta (2024). The Llama 3 Herd of Models
- Raffel et al. (2019). Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer
- Hugging Face (2024). LLM Course, chapter 6: the Tokenizers library (BPE, WordPiece and Unigram tokenization)
- Provilkov, Emelianenko & Voita (2019). BPE-Dropout: Simple and Effective Subword Regularization
- Xue et al. (2021). ByT5: Towards a token-free future with pre-trained byte-to-byte models
- Petrov et al. (2023). Language Model Tokenizers Introduce Unfairness Between Languages