LLM & VLM courseBlog
8Track 1: Foundations · session 8 of 15

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.

Time: 2.5 to 3 hours (reading 2 hours, exercises 45 minutes)Level: BeginnerBefore this: Sessions 1, 3 and 6

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:

\[ \text{fertility} = \frac{n_{\text{tokens}}}{n_{\text{words}}}, \qquad \text{compression} = \frac{n_{\text{chars}}}{n_{\text{tokens}}} \tag{8.1} \]
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.

Figure 1. The same text cut into tokens by seven schemes. Each colored box is one token; ␣ marks a space and ↵ a newline that are part of the token. Hover a box (or tap it) to see its token ID. All splits come from the real tokenizer files of each model.
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:

  1. 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.
  2. Count every pair of neighbor symbols, weighted by how often the word appears.
  3. Take the most frequent pair, for example (e, s), and add the joined symbol es to the vocabulary. Replace that pair everywhere. This is one merge; write it down in a list.
  4. 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

\[ \operatorname{count}(a, b) = \sum_{w} f(w) \cdot \big|\{\, i : s_i = a,\ s_{i+1} = b \,\}\big| \tag{8.2} \]

and each merge picks the best pair and grows the vocabulary by one:

\[ (a^*, b^*) = \argmax_{(a, b)} \operatorname{count}(a, b), \qquad |\mathcal{V}_k| = |\mathcal{V}_0| + k \tag{8.3} \]
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 max does 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)
  1. input: word counts \(f(w)\), target size \(V\)
  2. \(\mathcal{V} \leftarrow\) base symbols; write each word as base symbols
  3. merges \(\leftarrow\) empty list
  4. while \(|\mathcal{V}| \lt V\):
  5. for each word \(w\): add \(f(w)\) to each of its pairs // (8.2)
  6. \((a^*, b^*) \leftarrow\) best pair; ties: first seen // (8.3) or (8.4)
  7. replace every \(a^*\, b^*\) by \(a^*b^*\) in all words
  8. append \((a^*, b^*)\) to merges; add \(a^*b^*\) to \(\mathcal{V}\)
  9. return \(\mathcal{V}\), merges
Merge list (the trained tokenizer)
Vocabulary
Figure 2. BPE training, computed live. Top left: every word of the corpus as its current symbols (the row being scanned is marked; merged symbols pop in green). Top right: the pair counts of (8.2) in the order the pairs are first seen; the orange “+f” marks the pairs that the current word just added to, and the bar shows the count. The winner of (8.3) is green, pairs tied with it are dashed. Bottom: the merge list and the vocabulary grow by one entry per merge.
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.

Worked example: the first three BPE merges

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.

Algorithm 1: BPE training
  1. input: word counts \(f(w)\), target vocabulary size \(V\)
  2. \(\mathcal{V} \leftarrow\) all base symbols (characters, or the 256 bytes); write each word as base symbols
  3. merges \(\leftarrow\) empty list
  4. while \(|\mathcal{V}| \lt V\):
  5.   count all neighbor pairs, weighted by \(f(w)\) // formula (8.2)
  6.   \((a^*, b^*) \leftarrow\) the pair with the highest count; break ties by first appearance // formula (8.3)
  7.   replace every \(a^*\, b^*\) by the new symbol \(a^*b^*\) in all words
  8.   append \((a^*, b^*)\) to merges; add \(a^*b^*\) to \(\mathcal{V}\)
  9. return \(\mathcal{V}\), merges
Algorithm 2: BPE encoding of one pre-token
  1. input: a piece of text \(x\) (one word with its leading space), merges with ranks \(r(a, b)\)
  2. \(s \leftarrow\) the base symbols of \(x\) (characters, or UTF-8 bytes)
  3. loop:
  4.   among all neighbor pairs in \(s\), find the one with the lowest rank \(r\)
  5.   if no pair has a rank: stop
  6.   merge every occurrence of that pair in \(s\)
  7. 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\)
  1. input: a word \(x\), merges with ranks \(r(a, b)\)
  2. \(s \leftarrow\) the characters of \(x\), then </w>
  3. loop:
  4. among the neighbor pairs in \(s\), find the lowest rank \(r\)
  5. if no pair has a rank: stop
  6. merge every occurrence of that pair in \(s\)
  7. return the IDs of the symbols in \(s\)
Figure 3. BPE encoding of one new word, computed live. Left: one row per round; the small labels between two symbols are the ranks of those pairs (lowest rank in orange, “–” for a pair that is not in the merge list), and the merged symbol pops in green on the next row. Red symbols are characters that never appeared in training. Right: the merge list; the pairs present in the word are tinted, and the one being applied is orange. Token IDs: the base symbols in sorted order with </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).

Figure 4. BPE trained in your browser on chapter 1 of Pride and Prejudice. The curve shows tokens per word for the training chapter as merges are added. The default test sentence is the first sentence of chapter 2, which the tokenizer has not seen. Red boxes are characters that never appeared in training: a character-level BPE has no ID for them.
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

\[ \operatorname{score}(a, b) = \frac{\operatorname{count}(a, b)}{\operatorname{count}(a) \cdot \operatorname{count}(b)} \tag{8.4} \]

Why this ratio? If \(N\) is the total number of symbols, the probability of the pair divided by the probabilities of its parts is

\[ \frac{P(ab)}{P(a)\,P(b)} = \frac{\operatorname{count}(a, b)/N}{(\operatorname{count}(a)/N)\,(\operatorname{count}(b)/N)} = N \cdot \operatorname{score}(a, b) \tag{8.5} \]

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]

Algorithm 3: WordPiece encoding of one word
  1. input: a word \(w\) (spaces already removed), vocabulary \(\mathcal{V}\) with ## pieces
  2. start \(\leftarrow 0\); pieces \(\leftarrow\) empty
  3. while start \(\lt |w|\):
  4.   for end from \(|w|\) down to start + 1: candidate \(\leftarrow w[\text{start}:\text{end}]\), with ## in front if start \(\gt 0\)
  5.     if candidate \(\in \mathcal{V}\): append it, start \(\leftarrow\) end, and go back to the while
  6.   no candidate found: return [[UNK]] // the whole word is lost
  7. 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

\[ P(\mathbf{x}) = \prod_{i=1}^{m} p(x_i), \qquad \sum_{t \in \mathcal{V}} p(t) = 1 \tag{8.6} \]

Encoding picks the most likely segmentation among all segmentations \(S(w)\) of the word:

\[ \mathbf{x}^* = \argmax_{\mathbf{x} \in S(w)} P(\mathbf{x}) = \argmax_{\mathbf{x} \in S(w)} \sum_{i} \log p(x_i) \tag{8.7} \]

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\):

\[ \text{best}(i) = \max_{j \lt i,\ w_{j:i} \in \mathcal{V}} \Big( \text{best}(j) + \log p(w_{j:i}) \Big) \tag{8.8} \]
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:

\[ \mathcal{L} = \sum_{s} f(s) \, \log \sum_{\mathbf{x} \in S(s)} P(\mathbf{x}) \tag{8.9} \]

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]

Algorithm 4: Unigram training
  1. input: word counts \(f(s)\), target size \(V\), keep ratio \(\rho\) (for example 0.8)
  2. \(\mathcal{V} \leftarrow\) seed: all characters plus the most frequent substrings; \(p(t) \propto\) count of \(t\)
  3. repeat:
  4.   run a few EM steps: expected counts of each piece over all segmentations, then normalize // raises (8.9)
  5.   if \(|\mathcal{V}| \le V\): stop
  6.   for every piece that is not a single character, compute the loss in \(\mathcal{L}\) if it were removed
  7.   keep the \(\max(V, \rho|\mathcal{V}|)\) pieces with the largest loss (plus all characters)
  8. 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

\[ P_\alpha(\mathbf{x} \mid w) = \frac{P(\mathbf{x})^{\alpha}}{\sum_{\mathbf{x}' \in S(w)} P(\mathbf{x}')^{\alpha}} \tag{8.10} \]

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
\(P(\mathbf{x})\) relative to the best cutsampling probability (8.10)
Vocabulary and \(p(t)\)
Figure 5. A Unigram tokenizer trained on low ×5, lower ×2, newest ×6, widest ×3. Choose a training stage and a word. The table lists the most likely segmentations; the best one (bold) is what Viterbi returns, and the orange bars are the chances of each cut under subword sampling.
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]

BPEWordPieceUnigram
Builds the vocabularybottom-up: merge the most frequent pairbottom-up: merge the pair with the highest score (8.4)top-down: start big, prune the least useful pieces
Storesvocabulary + ordered merge listvocabulary only (with ##)vocabulary + a log-probability per piece
Encodes byapplying merges in rank ordergreedy longest matchViterbi: most likely segmentation
Unknown inputbyte-level: impossible; char-level: unknown characterthe whole word becomes [UNK]unknown character (or byte fallback)
Can sample cutswith BPE-dropoutnoyes, natively (8.10)
Used byGPT-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\):

\[ \text{params} = V d \ \ (\times 2 \text{ if the two are not tied}), \qquad \text{output FLOPs per token} = 2 V d, \qquad \text{logits memory} = B \, T \, V \cdot \text{bytes} \tag{8.11} \]
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
Worked example: Llama 2 7B (32K) versus Llama 3 8B (128K)

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.

tokens per word on Pride and Prejudice, GPT-2 merges cut to sizeyour vocabulary size
Figure 6. The price of the vocabulary for real model shapes. Pick a model; its width \(d\), the size of everything else, and tying come from its config.json. Move \(V\) to see the parameters, output-layer compute and logits memory change. The curve is measured: the real GPT-2 tokenizer with only its first \(V - 256\) merges, run on the whole novel.
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.

\[ \text{BPB} = \frac{\sum_{t=1}^{n_{\text{tok}}} -\ln p(y_t \mid y_{\lt t})}{\ln 2 \cdot n_{\text{bytes}}} = \frac{n_{\text{tok}}}{n_{\text{bytes}}} \cdot \frac{\bar{\ell}_{\text{tok}}}{\ln 2} \tag{8.12} \]
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
Worked example: which model is better?

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

SystemTokenizerWhy it matters
GPT-2, GPT-4, Llama 3, Qwen2.5byte-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, ALBERTSentencePiece UnigramLanguage-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 tokensImage and text share one sequence and one context budget (session 9, session 183)
Video-LLMs, Video-RAG, video retrievaltext tokens for questions, transcripts and captions; frames become many visual tokensTranscripts (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 IDsThe same idea, a fixed vocabulary of pieces, applied to pixels (session 224)
API pricing and context limitswhatever the model usesYou 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
Words need a huge vocabulary and still miss new words (on Pride and Prejudice, a word list from the first half misses 3.8% of the words in the second half), which become [UNK]. Characters never miss anything but make sequences about 4 times longer than subwords, which costs attention compute and context, and forces the model to learn spelling. Subwords keep frequent words whole and spell rare ones from parts: a fixed vocabulary of 30K to 256K, no unknown words (with bytes as base), and about 1.3 to 1.5 tokens per English word.
Walk me through BPE training on a small example.basic
Write each word as characters plus an end marker, with its count. Count all neighbor pairs weighted by word count, merge the most frequent pair everywhere, add the new symbol to the vocabulary and record the merge. Repeat until the target size. On low ×5, lower ×2, newest ×6, widest ×3: merges are e+s (9), es+t (9), est+</w> (9), l+o (7), lo+w (7), and so on; the corpus shrinks from 95 to 68 symbols after 3 merges. Vocabulary size \(=\) base symbols \(+\) number of merges.
How does a trained BPE tokenizer encode a new word? Is it greedy longest match?core
No. It starts from the characters (or bytes) and repeatedly applies the merge with the lowest rank (learned earliest) among the pairs present, until none applies. This reproduces the order of training. Greedy longest match is WordPiece’s method, and it can give different splits. Text is first split into pre-tokens (words with leading space, digit groups, punctuation), and merges never cross those boundaries.
What is byte-level BPE and why does it have no unknown tokens?core
It runs BPE on the UTF-8 bytes of the text, with the 256 byte values as the base vocabulary. Any string is a sequence of bytes, so every input can be encoded; the worst case is one token per byte. GPT-2 has 256 bytes \(+\) 50,000 merges \(+\) <|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
Training: WordPiece merges the pair with the highest \(\operatorname{count}(ab)/(\operatorname{count}(a)\cdot\operatorname{count}(b))\), which ranks pairs by pointwise mutual information (formula 8.5), instead of the highest raw count. It prefers pairs whose parts rarely appear apart. Encoding: WordPiece stores only the vocabulary, marks word-internal pieces with ##, and uses greedy longest match from the left. If no piece fits, the whole word becomes [UNK]. BPE stores ordered merges and applies them by rank.
Explain the Unigram tokenizer. How does it train and how does it encode?core
Each piece has a probability; a segmentation’s probability is the product of its pieces (8.6). Encoding uses Viterbi dynamic programming (8.8) to find the most likely segmentation in \(O(L\,\ell_{\max})\). Training starts from a large seed vocabulary, runs EM (expected piece counts over all segmentations, then normalize) to maximize the corpus likelihood (8.9), then prunes the pieces whose removal lowers the likelihood least, keeping all single characters, and repeats until the target size. It works top-down, unlike BPE and WordPiece.
What is subword regularization, and why might it help?advanced
Instead of always using the best segmentation, sample one from \(P(\mathbf{x})^\alpha\), normalized (8.10), each time a sentence is seen in training. The model learns that “new+est” and “newe+st” mean the same thing, which acts as data augmentation and makes it more robust to rare words, typos and noisy input. Kudo showed gains in machine translation, mostly in low-resource settings. BPE-dropout does the same for BPE by randomly skipping merges. At test time you use the deterministic best segmentation.
Llama 2 had 32K tokens, Llama 3 has 128K. What did this change cost and buy?advanced
Cost: with \(d = 4096\) and untied matrices, the vocabulary parameters went from 262M to 1.05B (3.9% to 13.1% of the model), the output layer from 0.26 to 1.05 GFLOPs per token (about 2% to 7% of forward matrix work), and logits memory grew 4 times (33.6 GB for \(8 \times 8{,}192\) tokens in FP32). IDs no longer fit in 16 bits. Gain: about 10% fewer tokens on English (183,153 vs 164,167 on Pride and Prejudice; Meta reports \(3.17 \to 3.94\) characters per token), much better compression for other languages thanks to 28K extra multilingual tokens, more text per context window, and about 20% less attention-score work for the same text.
Why can you not compare perplexities of models with different tokenizers? What do you use instead?advanced
Perplexity is per token, and tokens of different tokenizers cover different amounts of text. A tokenizer with longer tokens gives a higher per-token loss for the same quality. Use bits per byte (or per character): total negative log-likelihood of the text in bits divided by its length in bytes, which equals \((\text{tokens per byte}) \times (\text{loss per token}) / \ln 2\) (8.12). Example: 2.0 nats/token at 3.934 bytes/token is 0.733 BPB; 2.2 nats/token at 4.284 bytes/token is 0.741 BPB.
Why do some tokenizers split numbers into single digits?core
With plain BPE, frequent numbers like “2024” become single tokens while others split in irregular ways (“366” could be one token, “367” two), so the model cannot see place value consistently, which hurts arithmetic. Llama 1/2 and Qwen split every digit; Llama 3 and GPT-4 split into groups of at most three digits, which keeps sequences shorter while staying regular. Figure 1 shows all three behaviors.
How would you choose the vocabulary size for a new model?advanced
Measure fertility on your target data (all languages, code) for several sizes, and weigh it against the cost: \(Vd\) (or \(2Vd\)) parameters, \(2Vd\) output FLOPs per token, logits memory, and undertrained rare tokens. Large models can afford big vocabularies (the vocabulary share is small, and shorter sequences save attention); small models cannot (Qwen2.5-0.5B already spends 28% of its weights on it). Round \(V\) to a multiple of 64 or 128 for efficient matrix kernels, and leave room for special tokens. [Likely]

Exercises

  1. Continue BPE on the toy corpus after the 10 merges of Figure 2. Which pair is merge 11, and what is its count?
  2. With the 10 merges, how would a character-level BPE encode “lowly”? What would a byte-level BPE do differently?
  3. With the WordPiece vocabulary of the code, encode “unable” and “tokens”. What happens to “unbelievablyy”?
  4. 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?
  5. 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?
  6. Show that the WordPiece score ranks pairs the same way as pointwise mutual information within one merge step.
Answerscheck
1. The words are now low</w> (5), low e r </w> (2), newest</w> (6) and wi d est</w> (3). The best counts are (wi, d) and (d, est</w>) with 3; (wi, d) is seen first, so merge 11 is “wid”, count 3. 2. “y” is not in the base vocabulary, so a character-level BPE has no ID for it. The merges give 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

\[ (a^*, b^*) = \argmax_{(a,b)} \operatorname{count}(a, b), \qquad \operatorname{score}_{\text{WP}}(a, b) = \frac{\operatorname{count}(a, b)}{\operatorname{count}(a)\operatorname{count}(b)} \]
\[ \text{best}(i) = \max_{j \lt i} \big(\text{best}(j) + \log p(w_{j:i})\big), \qquad \text{params} = Vd, \quad \text{FLOPs} = 2Vd, \quad \text{BPB} = \frac{n_{\text{tok}}}{n_{\text{bytes}}}\cdot\frac{\bar{\ell}_{\text{tok}}}{\ln 2} \]

References for this session

  1. Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, chapter 2: Words and Tokens
  2. Sennrich et al. (2015). Neural Machine Translation of Rare Words with Subword Units
  3. Kudo & Richardson (2018). SentencePiece: A simple and language independent subword tokenizer
  4. Kudo (2018). Subword Regularization
  5. Karpathy (2024). minbpe: minimal BPE tokenizer (code)
  6. Schuster & Nakajima (2012). Japanese and Korean Voice Search
  7. Wu et al. (2016). Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation
  8. Devlin et al. (2018). BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
  9. Radford et al. (2019). Language Models are Unsupervised Multitask Learners
  10. Touvron et al. (2023). Llama 2: Open Foundation and Fine-Tuned Chat Models
  11. Llama Team, Meta (2024). The Llama 3 Herd of Models
  12. Raffel et al. (2019). Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer
  13. Hugging Face (2024). LLM Course, chapter 6: the Tokenizers library (BPE, WordPiece and Unigram tokenization)
  14. Provilkov, Emelianenko & Voita (2019). BPE-Dropout: Simple and Effective Subword Regularization
  15. Xue et al. (2021). ByT5: Towards a token-free future with pre-trained byte-to-byte models
  16. Petrov et al. (2023). Language Model Tokenizers Introduce Unfairness Between Languages