4. Text as numbers: tokenizers and embeddings

A model predicts IDs, not text

A language model is a function from a sequence of integers to a probability distribution over the next integer. A tokenizer is the contract that connects those integers to text. It splits text into units from a fixed vocabulary, maps each unit to an ID, and maps IDs back to text.

The contract is part of the model. A checkpoint’s embedding row 22670 was trained to mean whatever text the tokenizer maps to 22670. Feed it IDs from a different tokenizer and the model receives nonsense, even if every shape is right. When you load real models (Chapters 9 and 18), you’ll always use the checkpoint’s own tokenizer files.

Characters, words or something in between?

Characters are the simplest option: the vocabulary is every character in your training text, and each character gets an ID. It never meets an unknown word. But sequences get long. “tokenization” is 12 tokens, and attention’s cost grows with sequence length (Chapter 5).

Words give short sequences, but the vocabulary explodes (every name, typo, number and inflection is a separate entry) and any word not in it is unrepresentable.

Subwords split the difference: frequent words are single tokens (" the"), rare words are built from pieces (" token" "ization"). A good subword vocabulary of 50k-250k entries covers any text in a few tokens per word. The standard way to build one is byte-pair encoding.

Bytes first

Text in a computer is bytes. UTF-8 encodes ASCII characters as one byte each and other characters as two to four: "é" is the bytes 195 169, and "✓" is 226 156 147. If a tokenizer starts from the 256 possible byte values, every possible string is representable, with no unknown tokens ever. That’s byte-level BPE, used by GPT-2, Llama 3 and Qwen.

Byte-pair encoding, by hand

BPE builds the vocabulary bottom-up from a training text:

1. Start with the 256 single-byte tokens.
2. Count every adjacent pair of tokens in the training text.
3. Merge the most frequent pair into a new token everywhere it occurs, and record the merge.
4. Repeat until the vocabulary is as large as you want.

Here it is on a tiny corpus: “low” five times, “lower” twice, “newest” six times and “widest” three times. Before counting, a pre-tokenizer splits text into chunks (roughly: words with their leading space, punctuation and numbers), and pairs are never counted across chunk boundaries. These are the first eight merges the reference implementation learns:

Now encoding a word it never saw works by applying the learned merges, earliest first:

"lowest"  -> ['low', 'est']        IDs [259, 257]
" newer"  -> [' new', 'e', 'r']     IDs [263, 101, 114]
" lowly"  -> [' low', 'l', 'y']     IDs [260, 108, 121]

Unknown words fall back to smaller pieces, down to single bytes if necessary. The order matters: encoding must apply merges in the order they were learned (lowest new-ID first), because later merges were learned on text where earlier merges had already happened.

The two core helpers are short in every language:

def pair_counts(ids, counts=None):
    counts = Counter() if counts is None else counts
    for pair in zip(ids, ids[1:]):
        counts[pair] += 1
    return counts

def merge_pair(ids, pair, new_id):
    out, i = [], 0
    while i < len(ids):
        if i + 1 < len(ids) and (ids[i], ids[i + 1]) == pair:
            out.append(new_id)
            i += 2
        else:
            out.append(ids[i])
            i += 1
    return out

inline std::vector<int> merge_pair(const std::vector<int>& ids, std::pair<int, int> pair, int new_id) {
    std::vector<int> out;
    for (size_t i = 0; i < ids.size();) {
        if (i + 1 < ids.size() && ids[i] == pair.first && ids[i + 1] == pair.second) { out.push_back(new_id); i += 2; }
        else out.push_back(ids[i++]);
    }
    return out;
}
inline std::map<std::pair<int, int>, int> pair_counts(const std::vector<int>& ids) {
    std::map<std::pair<int, int>, int> counts;
    for (size_t i = 0; i + 1 < ids.size(); ++i) ++counts[{ids[i], ids[i + 1]}];
    return counts;
}

#![allow(unused)]
fn main() {
/// Count adjacent pairs, remembering the order in which each pair first appeared (for ties).
pub fn pair_counts(ids: &[u32], counts: &mut HashMap<(u32, u32), (usize, usize)>, weight: usize) {
    for w in ids.windows(2) {
        let next_rank = counts.len();
        let entry = counts.entry((w[0], w[1])).or_insert((0, next_rank));
        entry.0 += weight;
    }
}

/// Replace non-overlapping occurrences of `pair`, scanning left to right.
pub fn merge_pair(ids: &[u32], pair: (u32, u32), new_id: u32) -> Vec<u32> {
    let mut out = Vec::with_capacity(ids.len());
    let mut i = 0;
    while i < ids.len() {
        if i + 1 < ids.len() && (ids[i], ids[i + 1]) == pair {
            out.push(new_id);
            i += 2;
        } else {
            out.push(ids[i]);
            i += 1;
        }
    }
    out
}

/// Learn `num_merges` merges from whitespace-separated words (a simplified pre-tokenizer).
pub fn train(text: &str, num_merges: usize) -> Vec<((u32, u32), u32)> {
    let mut words: Vec<(Vec<u32>, usize)> = {
        let mut freq: Vec<(String, usize)> = vec![];
        for word in text.split_inclusive(' ') {
            match freq.iter_mut().find(|(w, _)| w == word) {
                Some(entry) => entry.1 += 1,
                None => freq.push((word.to_string(), 1)),
            }
        }
        freq.into_iter().map(|(w, n)| (w.bytes().map(u32::from).collect(), n)).collect()
    };
    let mut merges = vec![];
    for step in 0..num_merges {
        let mut counts = HashMap::new();
        for (ids, n) in &words {
            pair_counts(ids, &mut counts, *n);
        }
        // Most frequent pair; ties go to the pair seen first.
        let Some((&best, _)) = counts.iter().max_by(|a, b| a.1 .0.cmp(&b.1 .0).then(b.1 .1.cmp(&a.1 .1))) else { break };
        let new_id = 256 + step as u32;
        for (ids, _) in words.iter_mut() {
            *ids = merge_pair(ids, best, new_id);
        }
        merges.push((best, new_id));
    }
    merges
}
}

Training on a real text

The book’s training corpus is Edith Wharton’s 1908 short story The Verdict: 20,479 characters and 3,634 words, public domain, and the same text BALLM uses. Training a 400-token vocabulary on it takes under a second (python run.py bpe --vocab 400):

first merges: [' t', 'he', ' a', 'in', ' h', ' s', ' w', ' o', ' the', 'ou', 're', 'it']
last merges:  ['est', 'elf', 'ce', 'qu', ' sh', 'ind', ' Str', ' Stroud']

The first merges are the most common English letter pairs and " the". The last ones already include a character’s name, “Stroud”. With a 1,024-entry vocabulary, the whole story becomes 6,926 tokens instead of 20,479 bytes, about 3 bytes per token. Production tokenizers trained on trillions of tokens of diverse text reach about 4 bytes per token on English with 100-250k entries.

Note

Real tokenizers differ from ours in the pre-tokenizer. GPT-2 and Qwen split text with a regular expression that uses Unicode classes (\p{L} for letters, \p{N} for numbers), which Python’s built-in re module doesn’t support. Ours is a simplified ASCII version. Qwen also splits numbers into single digits, so that arithmetic sees consistent pieces. The merge algorithm itself is the same.

Special tokens and chat templates

Some IDs don’t represent text at all. They mark structure:

• End of text (<|endoftext|>) separates documents during training, so the model learns where text ends.
• Role markers in chat models, such as Qwen’s <|im_start|> and <|im_end|> (the “ChatML” format), mark who is speaking and where a turn ends.

A chat template turns a list of messages into the exact token sequence the model was fine-tuned on. Qwen3’s looks like this:

<|im_start|>user
Explain what a GPU is in one sentence.<|im_end|>
<|im_start|>assistant

The final <|im_start|>assistant\n is the generation prompt: it tells the model that it’s now the assistant’s turn. Omit it and the model may continue the user’s message instead. When the model emits <|im_end|>, its turn is over and your engine should stop. Many “the model rambles forever” bugs are a missing generation prompt or a missing stop token.

Warning

Special tokens must be inserted as IDs, not tokenized as text. If <|im_end|> is typed into a prompt as ordinary characters and tokenized byte by byte, the model sees <, |, im, … instead of its trained marker. Tokenizer libraries handle this with an “allowed special tokens” option; your BPE encode has an allow_special flag.

From a token stream to training examples

A language model learns to predict the next token at every position. From one stream of IDs, a sliding window of length context creates input/target pairs whose targets are the inputs shifted by one:

ids:     10 11 12 13 14 15 16 17 18 19
input:   10 11 12 13        target: 11 12 13 14
input:         12 13 14 15  target:       13 14 15 16      (stride 2: windows overlap)
input:               14 15 16 17  target:   15 16 17 18

One window gives context training examples at once: position 0 learns “after 10 comes 11”, position 1 learns “after 10 11 comes 12”, and so on. The stride controls overlap: stride = context gives disjoint windows, and a smaller stride reuses text.

Warning

Split before you window. If you make overlapping windows first and then split them randomly into training and validation sets, nearly identical windows land in both. Validation loss then measures memorization, not generalization. Split the token stream (or better, whole documents) first, then window each part. split_then_window does this.

Embeddings: from IDs to vectors

The model’s first operation turns each ID into a vector by looking up a row of an embedding table of shape [vocab_size, D]:

emb = torch.nn.Embedding(3, 2)
emb.weight.data = torch.tensor([[1., 0.], [0., 1.], [1., 1.]])
print(emb(torch.tensor([[2, 0]])))       # rows 2 and 0 -> [[[1., 1.], [1., 0.]]]

A lookup is mathematically the same as multiplying a one-hot vector (all zeros except a 1 at the ID) by the table, which is why embeddings train like any other weight. The lookup just skips the multiplication by zeros. Before training, the rows are random; training moves rows of tokens that behave alike closer together.

Two observations matter for engines:

• The table is big. Qwen3-0.6B’s is [151936, 1024]: 156M of the model’s 600M parameters. Many small models tie the output projection to this table (they reuse it to turn the final hidden vector back into vocabulary scores), saving another 156M parameters.
• A lookup reads one row per token, not the whole table. That’s why Flash-Next can afford a 51-billion-parameter hashed n-gram embedding (Chapter 30): each token touches only a few rows of it.

Position

An embedding lookup gives the same vector for " GPU" wherever it appears, so the model can’t tell “dog bites man” from “man bites dog”. GPT-2 adds a second learned table indexed by position: x[t] = token_embedding[id[t]] + position_embedding[t]. That table has a fixed number of rows, which caps the context length. Modern models use rotary position embeddings instead (Chapter 17), which encode position inside attention and generalize better to long sequences.

Build it

pytest tests/test_ch04_text.py
python run.py bpe --vocab 512 --impl engine

Tip

Training is fast if you count each distinct pre-tokenized chunk once, weighted by how often it occurs. “the” appears hundreds of times but needs to be merged only once. In _encode_chunk, the pair to merge next is the one with the lowest merge ID among pairs that have a merge.

Stretch exercises

1. ★ Encode "Hello, world!", "hello world" and "HELLO WORLD" with your 512-token tokenizer. Count the tokens. Why do the counts differ so much? Where: experiments/ch04.py (create it), importing engine.tokenizer.BPETokenizer.
2. ★★ Plot bytes-per-token on The Verdict for vocabulary sizes 300, 500, 1,000, 2,000 and 4,000. Where do the returns diminish? Where: experiments/ch04.py (create it), training on data/the-verdict.txt.
3. ★★ Install tiktoken and compare GPT-2’s tokenization of a paragraph of The Verdict with yours. Which words does GPT-2 keep whole that yours splits? Where: experiments/ch04.py (create it).
4. ★★★ Make _encode_chunk fast: instead of rescanning all pairs after each merge, keep a priority queue of mergeable pairs keyed by merge rank. Measure the speed-up on the whole story. Where: BPETokenizer._encode_chunk in engine/tokenizer.py.

Check your understanding

1. Why can a byte-level BPE tokenizer encode any string, while a word tokenizer cannot?
2. Why must merges be applied in the order they were learned?
3. What goes wrong if a chat prompt omits the final <|im_start|>assistant\n?
4. Why does splitting overlapping windows into train and validation sets inflate validation scores?
5. Why does an embedding table, by itself, carry no information about word order?

Going deeper

• BALLM Chapter 2 (pp. 17-49): tokenizing text, special tokens, byte-pair encoding with tiktoken, sliding-window data loading, token and position embeddings. Our corpus and window examples follow it.
• Sennrich, Haddow and Birch, Neural Machine Translation of Rare Words with Subword Units (2016): the paper that brought BPE to NLP.
• Andrej Karpathy, Let’s build the GPT Tokenizer (video) and the minbpe repository: byte-level BPE in depth, including the GPT-2 and GPT-4 regex pre-tokenizers.
• The Hugging Face tokenizers documentation, for how tokenizer.json stores pre-tokenizers, merges and special tokens.