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

build a byte-level BPE tokenizer from scratch

In this lab you write a byte-level BPE tokenizer in about 60 lines of Python, the same kind that GPT-2, GPT-4, Llama 3 and Qwen use. You train it on a chapter of Alice in Wonderland, check that encode then decode gives back the same text, compare it with tiktoken and Hugging Face, measure how many tokens other languages need, and read a real chat template token by token.

Time: 3 to 4 hours (mostly hands-on)Level: Beginner · hands-on labBefore this: Sessions 8 and 9, Python

What you will learn

  • Why byte-level tokenizers start from the 256 UTF-8 bytes, and why they never need an UNK token
  • The BPE training loop: count pairs, merge the most frequent, repeat; tie-breaking and overlapping pairs
  • Encoding by merge rank, decoding, and the round-trip test decode(encode(s)) = s
  • Why GPT-2 and GPT-4 split text with a regex before BPE, and how GPT-4 groups digits
  • How your tokenizer compares with tiktoken (gpt2, cl100k_base, o200k_base) and Hugging Face tokenizers, and what vocabulary size costs
  • How to measure tokens per word and the token premium of a language such as Farsi or Arabic
  • How chat templates use special tokens, and how to keep user text from becoming special tokens

Why this matters

A language model never sees text. It sees a list of integers, the token IDs. The tokenizer is the program that turns text into these integers and back. In this lab you write one yourself, in about 60 lines of Python: a byte-level BPE tokenizer, the same kind that GPT-2, GPT-4, Llama 3 and Qwen use.

Why build it when libraries exist? Because many strange model behaviors start in the tokenizer, and you can only debug what you understand. Some examples you will see with real numbers on this page:

  • Cost. APIs charge per token, and the context window is counted in tokens. The same sentence costs 15 tokens in English but 50 tokens in Farsi with the GPT-2 tokenizer, and 16 with GPT-4o’s tokenizer.
  • Odd splits. GPT-2 splits " HELLO" into " HELL" + "O", and Llama 3 writes the year 2023 as "202" + "3". Models then find spelling and arithmetic harder.
  • Chat formats. A chat model only works well if the prompt uses the exact special tokens it was trained with. You will read a real chat template and find them.

Sessions 8 and 9 (session 8 and session 9) explained the ideas. This lab makes them concrete. You will (1) train BPE on a small corpus and check that encoding then decoding gives back the same text, (2) compare it with tiktoken and a Hugging Face tokenizer, (3) measure tokens per word in English and in another language, and (4) read a real chat template.

Setup

You need Python 3.9 or newer. The tokenizer itself uses only the standard library plus the regex package (Python’s built-in re does not understand \p{L}, “any letter”). The comparison part uses tiktoken (OpenAI’s fast BPE library) and transformers (Hugging Face).

pip install regex tiktoken transformers torch
curl -o alice.txt https://www.gutenberg.org/cache/epub/11/pg11.txt

Our corpus (the training text) is Chapter 1 of Alice’s Adventures in Wonderland (public domain), with line breaks inside paragraphs joined: 11,229 characters, 11,455 bytes and 2,141 words. It is tiny on purpose, so every figure on this page can train the tokenizer again in your browser in a fraction of a second. Real tokenizers train on many gigabytes.

Everything in this lab is deterministic: there is no randomness in BPE training. If two runs give different merges, the cause is a different corpus, a different pre-tokenization rule, or a different rule for breaking ties between pairs with the same count. We use the rule from minbpe: on a tie, the pair that was seen first wins.

Step 1: text is bytes

A string is a list of Unicode code points: one integer per character, from 0 to 1,114,111. “A” is 65, “س” (Farsi “s”) is 1,587, and “🙂” is 128,578. A vocabulary with one entry per code point would need about 150,000 entries, most of them rare.

UTF-8 solves this. It writes every code point as 1 to 4 bytes (integers from 0 to 255). ASCII characters stay 1 byte; most other scripts use 2 or 3; emoji use 4:

\[ \text{bytes}(u) = \begin{cases} 1 & u \lt 2^{7} = 128 \\ 2 & 128 \le u \lt 2^{11} = 2048 \\ 3 & 2048 \le u \lt 2^{16} = 65536 \\ 4 & 65536 \le u \lt 1{,}114{,}112 \end{cases} \tag{10.1} \]
Read the symbols
\(u\)
the code point of one character (its Unicode number)
\(\text{bytes}(u)\)
how many bytes UTF-8 uses to store that character

This is the key idea of byte-level BPE: start from the 256 possible bytes. Then every string in every language, including emoji and broken text, can be written with the base vocabulary. There is no “unknown” token (UNK) ever. The cost: non-Latin text starts with 2 or 3 tokens per character, and BPE must learn merges to make it shorter.

Figure 1. From characters to bytes. Each box is one code point: the character, its number in hexadecimal (U+…), and its UTF-8 bytes. Type anything, or pick an example.
How to read Figure 1

Count the green byte boxes: that is the length of the text for a byte-level tokenizer before any merges. “hello” is 5 bytes; “سلام” (“hello” in Farsi) is 4 characters but 8 bytes; “你好” is 2 characters and 6 bytes; the emoji alone is 4 bytes. The readout also shows JavaScript’s .length, which counts UTF-16 units: it says 2 for one emoji. Python’s len() counts code points. Three tools, three different “lengths”: always ask which one is meant.

Step 2: train BPE (count, merge, repeat)

Byte Pair Encoding (BPE) was a data-compression method; Sennrich et al. (2015) used it to build subword vocabularies for translation. Training is a simple loop:

  1. Write the corpus as a list of byte IDs (0 to 255).
  2. Count every pair of neighbors.
  3. Take the most frequent pair, give it a new ID (256, then 257, …), and replace every occurrence of the pair with the new ID.
  4. Repeat until you have done \(M\) merges.

In formulas, with the corpus split into chunks \(w\) (words, explained in Step 3) that appear \(f(w)\) times:

\[ c(a,b) = \sum_{w} f(w)\, \Big|\big\{\, i : x^{w}_i = a,\ x^{w}_{i+1} = b \,\big\}\Big| \tag{10.2} \]
\[ (a^*, b^*) = \argmax_{(a,b)}\ c(a,b), \qquad \text{id}_t = 256 + t, \qquad |V| = 256 + M + S \tag{10.3} \]
Read the symbols
\(x^{w}_i\)
the token ID at position \(i\) inside chunk \(w\) (at the start, a byte)
\(c(a,b)\)
how many times token \(a\) is directly followed by token \(b\) in the whole corpus
\((a^*, b^*)\)
the most frequent pair; on a tie, the one seen first
\(t\)
the merge number, starting at 0; merge \(t\) creates token \(256 + t\)
\(M, S\)
the number of merges, and the number of special tokens added at the end
\(|V|\)
the vocabulary size

GPT-2’s vocabulary is \(256 + 50{,}000 + 1 = 50{,}257\): 256 bytes, 50,000 merges and one special token, <|endoftext|> with ID 50256. [Certain] The ordered list of merges is the trained tokenizer. Keep the order: you need it for encoding.

Each merge makes the corpus shorter. If the corpus has \(n_t\) tokens before merge \(t\):

\[ n_{t+1} = n_t - r_t, \qquad r_t \le c(a^*, b^*) \tag{10.4} \]

Here \(r_t\) is the number of replacements actually made. It is usually equal to the count, but it can be smaller when the pair overlaps itself, as in “aaa”: the pair \((\mathtt{a}, \mathtt{a})\) is counted twice, but we can only replace it once, left to right.

A worked example: “aaabdaaabac”

Start: 11 bytes. Pair counts: \((\mathtt{a}, \mathtt{a}) = 4\), \((\mathtt{a}, \mathtt{b}) = 2\), and \((\mathtt{b}, \mathtt{d})\), \((\mathtt{d}, \mathtt{a})\), \((\mathtt{b}, \mathtt{a})\), \((\mathtt{a}, \mathtt{c})\) once each.

Merge 0: \((\mathtt{a}, \mathtt{a}) \to\) token 256 = “aa”. Replacing left to right gives [aa] a b d [aa] a b a c: 9 tokens. The count was 4, but only 2 replacements happened, because each “aaa” holds two overlapping pairs: \(r_0 = 2 \lt c = 4\).

Merge 1: now \((\mathtt{aa}, \mathtt{a}) = 2\) and \((\mathtt{a}, \mathtt{b}) = 2\): a tie. \((\mathtt{aa}, \mathtt{a})\) was seen first, so it wins: token 257 = “aaa”, giving [aaa] b d [aaa] b a c: 7 tokens.

Merge 2: \((\mathtt{aaa}, \mathtt{b}) = 2 \to\) token 258 = “aaab”, giving [aaab] d [aaab] a c: 5 tokens. Three merges took the text from 11 tokens to 5.

Figure 2 runs the same loop on the classic small example from the BPE paper: the words “low” (5 times), “lower” (2), “newest” (6) and “widest” (3).

Figure 2. BPE training, one merge per step, on four words with their counts. Left: how each word is split now. Bars: the four most frequent pairs, with counts weighted by word frequency (formula 10.2). The highlighted bar is the next merge.
How to read Figure 2

At step 1, \((\mathtt{e}, \mathtt{s})\) and \((\mathtt{s}, \mathtt{t})\) both have count 9 (“newest” 6 times plus “widest” 3 times). \((\mathtt{e}, \mathtt{s})\) was seen first, so it wins; right after, \((\mathtt{es}, \mathtt{t})\) has count 9 and becomes “est”. Watch the total number of tokens fall from 79 to 20 after 10 merges. Notice that “lower” is never fully merged: \((\mathtt{low}, \mathtt{e})\) has count only 2, so other pairs win first. Frequent words become single tokens; rare words stay in pieces.

Step 3: split into chunks first (pre-tokenization)

If we run BPE on raw text, it happily merges across word boundaries. On our Alice corpus, without any splitting, it learns tokens such as ", and ", "of the " and "she was ". These waste vocabulary on accidents of one text, and they make the same word look different depending on its neighbors.

So GPT-2 first splits the text into chunks with a regular expression, and BPE merges only inside a chunk. The GPT-2 pattern is:

GPT2_SPLIT = r"""'s|'t|'re|'ve|'m|'ll|'d| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+"""

Read it from left to right: common English contractions; an optional space followed by letters; an optional space followed by digits; an optional space followed by punctuation; then runs of white space. So "Hello world!! It's 2024." becomes Hello · ␣world · !! · ␣ · ␣It · 's · ␣2024 · . (␣ marks a space). The space goes at the start of the next word, which is why GPT-style vocabularies contain both “hello” and “␣hello” as different tokens.

Two details matter. First, the contraction rule only knows the ASCII apostrophe. Our Gutenberg text uses the curly one, so “Alice’s” splits as Alice · ’ · s. Second, GPT-4’s pattern (cl100k_base) changes the rules: contractions in any case, and numbers in groups of at most 3 digits. So "1234567" becomes 123 · 456 · 7 in GPT-4, but 123 · 45 · 67 in GPT-2, which learned whatever digit pairs were common. [Certain: checked with tiktoken]

Algorithm 1: train byte-level BPE
  1. input: text, pattern \(P\), number of merges \(M\)
  2. chunks \(\leftarrow\) regex_findall\((P, \text{text})\)
  3. ids \(\leftarrow\) [ list(utf8_bytes(ch)) for ch in chunks ]
  4. vocab \(\leftarrow \{ i : \text{bytes}([i]) \}\) for \(i = 0..255\);  merges \(\leftarrow\) empty ordered map
  5. for \(t = 0\) to \(M - 1\) do
  6. counts \(\leftarrow\) pair counts over all chunks // formula (10.2); never across chunks
  7. if counts is empty then break
  8. \((a, b) \leftarrow\) argmax counts // ties: first seen
  9. ids \(\leftarrow\) replace \((a, b)\) by \(256 + t\) in every chunk, left to right
  10. merges\([(a, b)] \leftarrow 256 + t\);  vocab\([256 + t] \leftarrow\) vocab\([a]\) + vocab\([b]\)
  11. return merges, vocab

Step 4: encode and decode

Decoding is easy: look up the bytes of every token, join them, and decode the bytes as UTF-8. Encoding new text must reproduce what training would have done. The rule: inside each chunk, start from bytes, and repeatedly merge the adjacent pair that was learned earliest (lowest rank):

\[ (a, b) = \argmin_{(x_i,\, x_{i+1})}\ \operatorname{rank}(x_i, x_{i+1}), \qquad \operatorname{rank}(a,b) = t \text{ if merge } t \text{ was } (a,b), \text{ else } \infty \tag{10.5} \]

Stop when no adjacent pair has a finite rank. Why earliest first? Because later merges were learned on text where earlier merges had already been applied. Token 265 = “␣the” was built from 256 = “␣t” and 257 = “he”; it can only appear after those two exist.

The property you must test is the round trip:

\[ \operatorname{decode}\big(\operatorname{encode}(s)\big) = s \quad \text{for every string } s \tag{10.6} \]

A byte-level BPE with no text normalization passes this for every string, because merges only group bytes and never change them. Tokenizers that normalize text (lowercasing, Unicode normalization such as NFKC, removing accents) can fail it on purpose. The other direction, \(\operatorname{encode}(\operatorname{decode}(\text{ids})) = \text{ids}\), is not guaranteed: several ID lists can decode to the same text (for example, raw bytes instead of a merged token), and encode always picks the canonical one.

We measure how well a tokenizer compresses with the compression ratio:

\[ \rho = \frac{\text{number of UTF-8 bytes}}{\text{number of tokens}} \tag{10.7} \]

On the 11,455-byte Alice corpus, our tokenizer gives 5,963 tokens after 100 merges (\(\rho = 1.92\)), 4,352 after 300 (\(\rho = 2.63\)) and 3,712 after 500 (\(\rho = 3.09\)). Large English tokenizers reach about 4 bytes per token on ordinary English text. [Likely]

Algorithm 2: encode and decode
  1. function encode(text):
  2. out \(\leftarrow\) [ ]
  3. for ch in regex_findall\((P, \text{text})\) do
  4. ids \(\leftarrow\) list(utf8_bytes(ch))
  5. while len(ids) \(\ge 2\) do
  6. \((a, b) \leftarrow\) adjacent pair with the lowest rank // formula (10.5)
  7. if \((a, b)\) not in merges then break
  8. ids \(\leftarrow\) replace \((a, b)\) by merges\([(a, b)]\), left to right
  9. out \(\leftarrow\) out + ids
  10. return out
  11. function decode(ids): return utf8_decode( join(vocab\([i]\) for \(i\) in ids), errors = "replace")
100
Figure 3. Your own byte-level BPE, trained in your browser on the Alice corpus. Move the slider to choose the number of merges; the text box is encoded with Algorithm 2 and decoded again. Each colored box is one token, with its ID underneath.
How to read Figure 3

At \(M = 0\) every byte is a token. With 100 merges, “Alice was very tired.” is already 8 tokens: frequent words in the corpus are whole tokens, but “tired” is still ␣t · i · r · ed. At 500 merges it is 5 tokens. Words the corpus never used, like “weather”, stay in pieces. Switch to “No split” and look at the learned merges: tokens that cross word boundaries appear. Type Farsi or emoji: you will see single-byte tokens with hex labels like ‹d8›, because no merge for those bytes was ever learned, yet the round trip still says OK.

The full program

This is the whole tokenizer, in the style of Karpathy’s minbpe. It is the reference solution: write your own first, then compare. The comments give the numbers it prints on the Alice corpus.

import regex as re
GPT2_SPLIT = r"""'s|'t|'re|'ve|'m|'ll|'d| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+"""

def get_stats(ids, counts=None):
    counts = {} if counts is None else counts
    for pair in zip(ids, ids[1:]):                   # neighbors only
        counts[pair] = counts.get(pair, 0) + 1
    return counts

def merge(ids, pair, idx):                          # replace pair by idx, left to right
    out, i = [], 0
    while i < len(ids):
        if i < len(ids) - 1 and (ids[i], ids[i + 1]) == pair:
            out.append(idx); i += 2
        else:
            out.append(ids[i]); i += 1
    return out

class BPETokenizer:
    def __init__(self, pattern=GPT2_SPLIT):
        self.pattern = pattern
        self.merges = {}                                # (a, b) -> new id, in training order
        self.vocab = {i: bytes([i]) for i in range(256)}
        self.special = {}                               # "<|endoftext|>" -> id

    def _chunks(self, text):
        return re.findall(self.pattern, text) if self.pattern else [text]

    def train(self, text, num_merges):
        ids = [list(ch.encode("utf-8")) for ch in self._chunks(text)]
        for t in range(num_merges):
            stats = {}
            for chunk in ids:
                get_stats(chunk, stats)                 # formula (10.2)
            if not stats:
                break
            pair = max(stats, key=stats.get)            # ties: first inserted wins
            idx = 256 + t                               # formula (10.3)
            ids = [merge(chunk, pair, idx) for chunk in ids]
            self.merges[pair] = idx
            self.vocab[idx] = self.vocab[pair[0]] + self.vocab[pair[1]]

    def add_special(self, tokens):                    # ids after all merges
        for s in tokens:
            self.special[s] = len(self.vocab)
            self.vocab[self.special[s]] = s.encode("utf-8")

    def _encode_chunk(self, b):
        ids = list(b)
        while len(ids) >= 2:
            stats = get_stats(ids)
            pair = min(stats, key=lambda p: self.merges.get(p, float("inf")))   # (10.5)
            if pair not in self.merges:
                break
            ids = merge(ids, pair, self.merges[pair])
        return ids

    def encode_ordinary(self, text):                  # special strings are treated as plain text
        out = []
        for ch in self._chunks(text):
            out += self._encode_chunk(ch.encode("utf-8"))
        return out

    def decode(self, ids):
        return b"".join(self.vocab[i] for i in ids).decode("utf-8", errors="replace")

text = open("alice_ch1.txt", encoding="utf-8").read()   # Chapter 1, paragraphs joined (see Setup)
tok = BPETokenizer()
tok.train(text, 500)
ids = tok.encode_ordinary(text)
print(len(text.encode("utf-8")), len(ids))               # 11455 3712
assert tok.decode(ids) == text                           # round trip, formula (10.6)
for s in ["Alice was very tired.", "امروز هوا خیلی خوب است.", "🙂"]:
    e = tok.encode_ordinary(s)
    assert tok.decode(e) == s
    print(len(s.encode("utf-8")), len(e))              # 21 5 | 41 41 | 4 4
print([tok.vocab[256 + i] for i in range(10)])
# [b' t', b'he', b' s', b' a', b'in', b' w', b'it', b' o', b'\xe2\x80', b' the']

Notice merge 8: the bytes e2 80. They are the first two bytes of the curly quotes (“ ” ’ are all e2 80 xx), which are frequent in this text. That token is not a whole character. Decoding it alone gives the replacement character “�”, which is why decode uses errors="replace".

From IDs to a PyTorch dataset

The next session turns these IDs into vectors. Here is the bridge: a long tensor of IDs, a split, and (input, target) pairs shifted by one, exactly as in next-token prediction (session 6).

import torch
torch.manual_seed(0)
data = torch.tensor(tok.encode_ordinary(text), dtype=torch.long)   # shape (3712,)
n = int(0.9 * len(data)); train, val = data[:n], data[n:]
block, batch = 16, 4
ix = torch.randint(len(train) - block, (batch,))
x = torch.stack([train[i:i + block] for i in ix])            # (4, 16) input IDs
y = torch.stack([train[i + 1:i + block + 1] for i in ix])        # (4, 16) next-token targets
vocab_size = len(tok.vocab)                                         # 756 = 256 + 500

Step 5: compare with tiktoken and Hugging Face

Real tokenizers use the same algorithm, trained on far more data with far more merges. Check that your mental model matches them:

import tiktoken
from transformers import AutoTokenizer
gpt2 = tiktoken.get_encoding("gpt2")
print(gpt2.n_vocab, gpt2.encode("hello world"))            # 50257 [31373, 995]
print([gpt2.decode([i]) for i in gpt2.encode(" hello Hello HELLO")])
# [' hello', ' Hello', ' HELL', 'O']
cl100k = tiktoken.get_encoding("cl100k_base")                  # GPT-4
print(cl100k.n_vocab, cl100k.encode("hello world"))        # 100277 [15339, 1917]
qwen = AutoTokenizer.from_pretrained("Qwen/Qwen2.5-0.5B-Instruct")
enc = qwen("hello world", add_special_tokens=False)
print(enc.input_ids, qwen.convert_ids_to_tokens(enc.input_ids))   # [14990, 1879] ['hello', 'Ġworld']

The Hugging Face output shows Ġworld. GPT-2-style byte-level tokenizers store each byte as a printable character, so the vocabulary file can be plain text: the space byte is shown as Ġ and the newline byte as Ċ. [Certain] It is still the bytes “␣world”. Different tokenizers give different IDs for the same text, so IDs from one tokenizer mean nothing to a model trained with another.

TokenizerVocabulary size (as reported)Used by
Ours (this lab)256 + \(M\), here 756you
gpt2 (tiktoken)50,257GPT-2, GPT-3 [Certain]
cl100k_base (tiktoken)100,277 (n_vocab)GPT-3.5, GPT-4 [Certain]
o200k_base (tiktoken)200,019 (n_vocab)GPT-4o [Certain]
Llama 3.2 (Hugging Face)128,256 including special tokensLlama 3, 3.1, 3.2
Qwen2.5 (Hugging Face)151,665 including added tokensQwen2.5 models

Vocabulary size is a trade-off. A bigger vocabulary gives shorter sequences (cheaper attention, more text per context window) but a bigger embedding table and output layer:

\[ P_{\text{emb}} = |V| \cdot d \tag{10.8} \]

For Llama 3 8B, \(|V| = 128{,}256\) and \(d = 4{,}096\), so the input embedding alone has 525,336,576 parameters (about 525 million), and the untied output layer has the same number again. That is why vocabulary size is a real design decision (session 11).

Step 6: tokens per word in two languages

Tokenizers learn merges from their training data. If that data is mostly English, other languages get fewer merges and need more tokens for the same meaning. This is called the tokenization premium (Petrov et al., 2023):

\[ \text{premium}(L) = \frac{\text{tokens}(s_L)}{\text{tokens}(s_{\text{en}})} \tag{10.9} \]
Read the symbols
\(s_L\)
a sentence in language \(L\) that means the same as the English sentence \(s_{\text{en}}\)
\(\text{tokens}(\cdot)\)
the number of tokens one fixed tokenizer produces

We use one sentence, “The weather is very nice today, so we are going to the park.”, and its translations into German, Farsi and Arabic. Figure 4 shows tokens per word (words = parts between spaces). This is one sentence, not a benchmark, but the pattern is typical. [Likely]

Figure 4. Tokens per word for the same sentence in four languages, for five real tokenizers (counted with tiktoken and Hugging Face tokenizers) and for your tokenizer from Figure 3 (counted live, with the merges and split mode set there). The dashed line is the byte count per word: a byte-level tokenizer with no useful merges sits on it.
How to read Figure 4

With GPT-2, the English sentence takes 15 tokens (1.15 per word) and the Farsi one 50 (5.56 per word): a premium of \(50/15 = 3.3\times\). GPT-4’s cl100k_base cuts Farsi to 28 and o200k_base to 16, almost the English cost. Our Alice tokenizer has never seen Farsi or Arabic, so it is close to the byte line: 77 tokens for 78 bytes at 500 merges. More merges only help languages that are in the training data.

Do this yourself for a language you speak: write one sentence, translate it carefully, and count with three tokenizers. The premium affects real systems: a user writing Farsi pays more per message, gets less text into the same context window, and waits longer for the same answer, because generation speed is measured in tokens per second.

Step 7: special tokens and a real chat template

A special token is a token that is never produced by splitting normal text. It is added to the vocabulary directly, usually after all merges, and it marks structure: the end of a document, the start of a message, whose turn it is. A chat template is the recipe (a Jinja template stored in tokenizer_config.json) that turns a list of messages into one string with these tokens.

msgs = [{"role": "system", "content": "You are a helpful assistant."},
        {"role": "user", "content": "What is BPE?"}]
s = qwen.apply_chat_template(msgs, tokenize=False, add_generation_prompt=True)
print(s)
# <|im_start|>system
# You are a helpful assistant.<|im_end|>
# <|im_start|>user
# What is BPE?<|im_end|>
# <|im_start|>assistant

add_generation_prompt=True adds the final <|im_start|>assistant line: it tells the model that it is now its turn. Without it, the model may continue the user’s message instead of answering.

Figure 5. The same two messages rendered with the real chat templates of Qwen2.5-0.5B-Instruct and Llama-3.2-1B-Instruct, then tokenized with their real tokenizers. Orange boxes are special tokens. ␣ is a space and ↵ a newline. Click any token.
How to read Figure 5

Qwen uses the ChatML format: each message is <|im_start|> role, newline, content, <|im_end|>. 5 of its 24 tokens are special. Llama 3.2 uses header tokens around the role name and <|eot_id|> (end of turn) after each message; it also starts with <|begin_of_text|> and its template adds a date block to the system message by default: 9 special tokens out of 46. Click “202” in the Llama version: Llama 3 splits numbers into groups of at most 3 digits, like GPT-4.

Special tokens need special care when encoding. If user text contains the string <|endoftext|>, should it become the single special token, or plain text? tiktoken refuses by default: gpt2.encode("<|endoftext|>") raises a ValueError. With allowed_special="all" you get [50256]; with disallowed_special=() you get seven ordinary tokens. For text from users, the safe choice is plain text, so that a user cannot inject a fake end of turn or a fake system message. [Certain: checked with tiktoken]

Algorithm 3: encode with special tokens
  1. input: text, special map \(S\) (string \(\to\) id), flag allow_special
  2. if not allow_special then return encode_ordinary(text)
  3. parts \(\leftarrow\) split text on the regex “\(s_1 | s_2 | \dots\)” of escaped special strings, keeping the separators
  4. for part in parts do
  5. if part \(\in S\) then out.append(\(S[\text{part}]\)) else out += encode_ordinary(part)
  6. return out

Where this is used

SystemWhat the tokenizer does there
GPT-2, GPT-3, GPT-4, GPT-4oByte-level BPE with a regex split, through tiktoken (gpt2, cl100k_base, o200k_base)
Llama 3 familyA tiktoken-style byte-level BPE with 128K tokens; Meta reports it combines 100K tokens from tiktoken with 28K extra tokens for non-English text [Likely]
Qwen2.5 and Qwen2-VLByte-level BPE; the VLM adds special tokens that mark where image and video features go in the sequence [Likely] (session 9)
API cost and context budgetsCount tokens with the model’s own tokenizer before sending; budgets differ by language (Figure 4)
Video-RAG and video retrievalASR transcripts and captions of video segments are chunked by token count to fit the embedding model and the LLM context; the same video in Farsi gives more tokens per minute than in English
Key-moment detection with timestampsTimes like “00:12:37” are split into digit groups; how a tokenizer splits numbers affects how well a model reads and writes timestamps [Speculation]
Training data pipelinesCorpora are tokenized once and stored as arrays of IDs (often uint16 when \(|V| \lt 65{,}536\), else uint32), as in the PyTorch bridge above

Common mistakes

  • Decoding one token at a time with strict UTF-8. A token can hold part of a character (our merge 8 is e2 80). Use errors="replace", and when streaming output, buffer bytes until they form complete characters.
  • Saving merges as an unordered set. Encoding needs the order (formula 10.5). Save an ordered list and rebuild ranks on load.
  • Encoding by longest match instead of by rank. Greedy longest-match gives different splits from the ones the model was trained on. The tokens are valid, but the model rarely saw them.
  • Treating special strings in user text as special tokens. This lets users inject <|im_end|> or a fake system turn. Encode user content as ordinary text.
  • Adding BOS twice. The Llama 3 template already writes <|begin_of_text|>. If you then call the tokenizer with add_special_tokens=True, you get two BOS tokens. Tokenize the rendered string with add_special_tokens=False, or let apply_chat_template(tokenize=True) do it.
  • Using the wrong chat template, or forgetting add_generation_prompt=True at inference. Quality drops quietly; nothing crashes.
  • Mixing up lengths. Characters, code points, UTF-16 units (JavaScript), bytes and tokens are five different numbers. Context limits are in tokens.
  • Comparing tokenizers on one language only. A tokenizer that looks great on English can be \(3\times\) more expensive on Farsi or Arabic.

Interview questions

Why does a byte-level BPE tokenizer never need an UNK token?basic
Its base vocabulary is all 256 byte values, and every string can be written as UTF-8 bytes. So any input, in any language, with emoji or even broken text, can always be encoded: in the worst case one token per byte. Merges only make common byte sequences shorter. Character- or word-level vocabularies need UNK for symbols they never saw.
Walk me through BPE training. What is the trained artifact?basic
Pre-tokenize the text into chunks, convert each chunk to bytes, then repeat: count all adjacent pairs (weighted by chunk frequency), take the most frequent pair, give it the next new ID (256, 257, …), and replace it everywhere. Stop after \(M\) merges. The artifact is the ordered list of merges (plus the vocabulary bytes derived from it, and any special tokens). The order matters for encoding.
When encoding new text, why do you apply merges in order of rank and not, for example, longest-match?core
Encoding must reproduce the segmentation the model saw during training. During training, merge \(t\) was learned on text where merges \(0..t-1\) were already applied, so later tokens are built from earlier ones. Applying the lowest-rank available pair first replays that history. Longest-match can produce different, valid-looking splits that the model rarely or never saw, which hurts quality.
Why do GPT-style tokenizers split text with a regex before BPE?core
Without it, BPE merges across word and punctuation boundaries and learns tokens like “, and ” or “of the ” that depend on neighbors, so the same word gets many different token forms (“dog.”, “dog!”, “dog?”). The regex keeps letters, numbers, punctuation and white space in separate chunks and merges only within them. This uses the vocabulary better and gives more consistent tokens. GPT-4’s pattern also limits numbers to groups of at most 3 digits.
Is decode(encode(s)) == s always true? And encode(decode(ids)) == ids?core
For byte-level BPE without normalization, the first holds for every string, because merges only group bytes. Tokenizers with normalization (lowercasing, NFKC, accent stripping, as in some WordPiece or SentencePiece setups) can break it on purpose. The second is not guaranteed: many ID sequences decode to the same text (for example, raw bytes instead of a merged token), and encode returns only the canonical one. This matters when you edit or splice token sequences.
Why can a single token decode to “�”?core
BPE merges bytes, not characters, so a token can contain only part of a multi-byte UTF-8 character (for example e2 80, the start of curly quotes). Decoding it alone is invalid UTF-8, and with errors="replace" you get U+FFFD. In streaming generation you must buffer bytes across tokens until they form complete characters before showing them.
How do you choose the vocabulary size?advanced
Larger \(|V|\) gives shorter sequences: less attention and KV-cache cost per sentence, more text per context window, faster generation in characters per second, and better coverage of many languages. But the embedding table and output layer grow as \(|V| \cdot d\): for Llama 3 8B that is about 525M parameters for the input embedding alone, plus the softmax cost over 128K entries at every step, and rare tokens get few training updates. Modern multilingual LLMs moved from 32K–50K to 100K–200K vocabularies. [Likely] Choose by measuring compression on your target languages and domains against model size.
A product team sees that Farsi users hit the context limit much sooner. Explain and suggest fixes.core
The tokenizer has a high premium for Farsi: its merges were learned mostly from English, so Farsi text stays close to 2 bytes per character. On one test sentence, GPT-2 needs 50 tokens for Farsi against 15 for English, while o200k_base needs 16. Fixes: use a model whose tokenizer covers Farsi well (measure it), extend the vocabulary and continue pretraining, or budget limits by tokens per language. Also check cost and latency, which scale with tokens.
What is a chat template, and what goes wrong if training and serving templates differ?core
It is a Jinja recipe in the tokenizer config that renders a list of messages into one string with role markers and special tokens (for example <|im_start|>/<|im_end|> in ChatML, or header tokens and <|eot_id|> in Llama 3). The model learned to respond after the exact assistant header and to stop by emitting the end-of-turn token. With a different template, it may not stop, continue the user turn, ignore the system prompt, or lose quality silently. Always use apply_chat_template from the same checkpoint.
How should user-supplied text containing “<|endoftext|>” be handled?advanced
As ordinary text, never as the special token. Otherwise a user can end a document, close their turn, or open a fake system turn: a prompt-injection path at the token level. tiktoken raises an error by default when it sees such strings, which forces you to choose: allowed_special for trusted template text, disallowed_special=() to encode them as plain text. Insert real special tokens only through the template, by ID.
Naive BPE training recounts all pairs after each merge. How do real implementations make it fast?advanced
The naive loop costs about \(\text{corpus length} \times \text{number of merges}\). Real trainers first count unique chunks with their frequencies (our corpus has 2,641 chunks but only 713 unique ones), keep a global pair-count table and a map from each pair to the chunks containing it, and after each merge update only the counts of pairs next to the merged positions. A priority queue (heap) gives the next best pair. Training then scales to gigabytes. Encoding is sped up with caches for frequent chunks and implementations in Rust (Hugging Face tokenizers, tiktoken).

Exercises

  1. By hand, train 3 merges on “aaabdaaabac” but break ties by choosing the pair seen last. Do you still reach 5 tokens?
  2. How many bytes does “naïve” have in UTF-8? How many tokens does it have under our tokenizer with \(M = 0\)?
  3. Add save() and load() to the tokenizer (merges as an ordered list of pairs). Check that a loaded tokenizer gives identical IDs on the whole corpus.
  4. Implement Algorithm 3 (encode with allowed_special) and add <|endoftext|>. What is its ID if you trained 500 merges?
  5. Train on Chapter 1 and measure the compression ratio on Chapter 2. Is it lower than on Chapter 1? Why?
  6. Write one sentence in a language you speak, and count tokens with gpt2, cl100k_base, o200k_base and one Hugging Face tokenizer. Compute the premium (10.9) against English.
  7. Print the rendered chat template of any instruct model you use. List every special token and what it marks.
Answerscheck
1. Merge 0 is still \((\mathtt{a}, \mathtt{a})\), giving 9 tokens. Then \((\mathtt{aa}, \mathtt{a})\) and \((\mathtt{a}, \mathtt{b})\) tie at 2; choosing the last seen gives \((\mathtt{a}, \mathtt{b}) \to\) “ab”: [aa] [ab] d [aa] [ab] a c, 7 tokens. Then \((\mathtt{aa}, \mathtt{ab}) = 2 \to\) “aaab”: 5 tokens. Same length, different merges. 2. “ï” is U+00EF (239), which is 2 bytes, so 6 bytes and 6 tokens at \(M = 0\). 3. Rebuild merges with ids \(256 + t\) in file order and rebuild vocab from them. 4. \(256 + 500 = 756\), the next free ID. 5. It should be lower: words and names that are new in Chapter 2 have no merges. This is the same effect as Figure 4, on a smaller scale. 6. and 7. Depend on your language and model; use Figures 4 and 5 as a guide.

Key takeaways

  • Byte-level BPE starts from 256 bytes (10.1), so it can encode any string; there is no UNK.
  • Training: count pairs (10.2), merge the most frequent into a new ID (10.3), repeat. The ordered merge list is the tokenizer. Each merge shortens the corpus (10.4).
  • Encoding replays merges by rank (10.5); decode(encode(s)) = s must hold (10.6). A regex split keeps merges inside words.
  • Compression (10.7) and the language premium (10.9) decide cost: one sentence is 15 GPT-2 tokens in English and 50 in Farsi. Vocabulary size costs \(|V| \cdot d\) parameters (10.8).
  • Special tokens and chat templates are part of the tokenizer: use the model’s own template, and never let user text become special tokens.

Key formulas

\[ (a^*, b^*) = \argmax_{(a,b)} c(a,b), \quad \text{id}_t = 256 + t, \quad (a,b) = \argmin \operatorname{rank}(x_i, x_{i+1}), \quad \rho = \frac{\text{bytes}}{\text{tokens}}, \quad P_{\text{emb}} = |V|\, d \]

References for this session

  1. Karpathy (2024). minbpe: minimal BPE tokenizer (code)
  2. Raschka, Build a Large Language Model (From Scratch), chapter 2: Working with text data
  3. Sennrich et al. (2015). Neural Machine Translation of Rare Words with Subword Units
  4. Radford et al. (2019). Language Models are Unsupervised Multitask Learners (GPT-2)
  5. OpenAI (2023). tiktoken: a fast BPE tokenizer for OpenAI models (code)
  6. Hugging Face (2020). Tokenizers: fast state-of-the-art tokenizers (code)
  7. Petrov, La Malfa, Torr & Bibi (2023). Language Model Tokenizers Introduce Unfairness Between Languages
  8. Llama Team, Meta (2024). The Llama 3 Herd of Models
  9. Kudo & Richardson (2018). SentencePiece: A simple and language independent subword tokenizer