Module 03: Tokenization

Introduction

A language model requires numbers, not text. Tokenization breaks text into tokens and maps each to an integer.

Tokenization converts raw text into integers the model can process. Modern LLMs use subword tokenization - they break text into pieces smaller than words but larger than characters.

Why subword tokenization?

  • Word-level: Cannot handle new words (OOV problem), huge vocabulary needed (millions for multilingual)
  • Character-level: Sequences become 4-5x longer, attention cost explodes O(n^2), model learns spelling from scratch
  • Subword: Best of both worlds - handles new words via decomposition, reasonable sequence length

BPE (Byte Pair Encoding) dominates modern tokenization. Philip Gage invented it for data compression in 1994; researchers adapted it for NLP in 2016:

  1. Start with individual characters as the initial vocabulary
  2. Count all adjacent token pairs in the training corpus
  3. Merge the most frequent pair into a new token
  4. Add the merged token to the vocabulary
  5. Repeat until vocabulary size reached

What You’ll Learn

After this module, you can:

  • Build a character-level tokenizer from scratch
  • Understand why subword tokenization outperforms alternatives
  • Implement the BPE algorithm for training and encoding
  • Build byte-level BPE that encodes any text with no <UNK>
  • Add GPT-2 regex pre-tokenization to keep merges linguistically clean
  • Handle special tokens (PAD, UNK, BOS, EOS)
  • Serialize a role-tagged conversation with a ChatML chat template
  • Recognize trade-offs in vocabulary size

Prerequisites

This module requires familiarity with:

First, build the simplest tokenizer from scratch.

The Simplest Tokenizer

The simplest approach treats each character as a token.

# Build vocabulary from text
text = "hello world"
chars = sorted(set(text))
print(f"Unique characters: {chars}")
print(f"Vocabulary size: {len(chars)}")
Unique characters: [' ', 'd', 'e', 'h', 'l', 'o', 'r', 'w']
Vocabulary size: 8
# The core of any tokenizer: two lookup tables
stoi = {ch: i for i, ch in enumerate(chars)}  # string to integer
itos = {i: ch for i, ch in enumerate(chars)}  # integer to string

print("stoi (encode):", stoi)
print("itos (decode):", itos)
stoi (encode): {' ': 0, 'd': 1, 'e': 2, 'h': 3, 'l': 4, 'o': 5, 'r': 6, 'w': 7}
itos (decode): {0: ' ', 1: 'd', 2: 'e', 3: 'h', 4: 'l', 5: 'o', 6: 'r', 7: 'w'}
# Encode: text -> integers
def encode(text):
    return [stoi[ch] for ch in text]

# Decode: integers -> text
def decode(ids):
    return ''.join(itos[i] for i in ids)

# Try it out
encoded = encode("hello")
print(f"'hello' -> {encoded}")
print(f"{encoded} -> '{decode(encoded)}'")
'hello' -> [3, 2, 4, 4, 5]
[3, 2, 4, 4, 5] -> 'hello'
# Round-trip test
original = "hello world"
reconstructed = decode(encode(original))
print(f"Original:      '{original}'")
print(f"Reconstructed: '{reconstructed}'")
print(f"Perfect round-trip: {original == reconstructed}")
Original:      'hello world'
Reconstructed: 'hello world'
Perfect round-trip: True

Ten lines of Python produce a complete tokenizer. Every tokenizer — no matter how sophisticated — has these same two operations:

  • encode: text to token IDs
  • decode: token IDs back to text

The Key Insight

Tokenization achieves compression and semantic grouping:

Tokenization Vocabulary Size Sequence Length Semantics
Character ~100 (ASCII) Very long None (individual letters)
Word ~1,000,000+ Short Strong (whole words)
Subword ~30,000-100,000 Medium Moderate (meaningful pieces)

Why Characters Aren’t Enough

Our character tokenizer works — but fails at scale.

Problem 1: Long Sequences

sample_text = "The transformer architecture revolutionized natural language processing."
char_tokens = list(sample_text)
print(f"Text length: {len(sample_text)} characters")
print(f"Token count: {len(char_tokens)} tokens")
print(f"Compression ratio: {len(sample_text) / len(char_tokens):.2f}x (no compression!)")
Text length: 72 characters
Token count: 72 tokens
Compression ratio: 1.00x (no compression!)

Since attention is O(n^2) in sequence length, doubling the sequence length quadruples the compute cost. Character-level tokenization produces the longest possible sequences.

Problem 2: No Semantic Units

# The model sees this:
word = "transformer"
char_view = list(word)
print(f"Characters: {char_view}")
print(f"Token count: {len(char_view)}")
Characters: ['t', 'r', 'a', 'n', 's', 'f', 'o', 'r', 'm', 'e', 'r']
Token count: 11

The model must discover on its own that t-r-a-n-s-f-o-r-m-e-r forms a meaningful unit. Character tokenization provides no semantic guidance. At word-level, “transformer” occupies one token with its own learned representation.

Problem 3: Vocabulary Explosion for Bytes

# If we go to byte-level (handling all Unicode)
text_with_emoji = "Hello! \U0001F60A"
byte_view = text_with_emoji.encode('utf-8')
print(f"Text: {text_with_emoji}")
print(f"Bytes: {list(byte_view)}")
print(f"Byte count: {len(byte_view)} (emoji = 4 bytes!)")
Text: Hello! 😊
Bytes: [72, 101, 108, 108, 111, 33, 32, 240, 159, 152, 138]
Byte count: 11 (emoji = 4 bytes!)

Byte-level tokenization can represent anything, but sequences become even longer. Byte-level tokenization splits a single emoji into 4 tokens.

The Tradeoff

This is the fundamental tradeoff in tokenization:

Characters: Small vocab, long sequences, no semantics
Words:      Huge vocab, short sequences, good semantics, can't handle new words
Subwords:   Medium vocab, medium sequences, some semantics, handles new words

BPE merges frequently co-occurring character sequences into single tokens — the sweet spot between characters and words.

Intuition: Learning Patterns Through Merging

Think of BPE as compression that learns common patterns:

For code, BPE learns patterns like:

  • def (function definition with space)
  • self. (common in Python classes)
  • return (return statement)
  • (4-space indent)

The BPE Training Algorithm

BPE learns to tokenize through this process:

The Math

BPE is simple - just counting and merging:

# Count pair frequencies
pairs = count_pairs(tokens)  # {'he': 50, 'el': 30, 'll': 80, ...}

# Find most frequent
best_pair = max(pairs, key=pairs.get)  # ('l', 'l')

# Merge everywhere
tokens = merge(tokens, best_pair, 'll')

Vocabulary size is a hyperparameter:

  • Too small: Sequences too long, less meaning per token
  • Too large: Many rare tokens, harder to learn
  • Typical: 8K-50K tokens for LLMs

Encoding New Text

Once trained, encoding applies merges in the order they were learned:

Handling Unknown Words

BPE can handle words it has never seen:

Byte-Level BPE: Tokenizing Any Text

Our character-level tokenizer has a hard limit: it can only encode characters it saw during training. Feed it an accented letter, an emoji, or a Chinese character it never met, and each one collapses to <UNK> — the information is gone, and decoding can never recover it. Real tokenizers (GPT-2, GPT-4’s tiktoken, SentencePiece) fix this once and for all with byte-level BPE.

The idea is a single change of alphabet. Instead of starting from the characters in the training text, start from the 256 possible UTF-8 bytes.

Intuition: 256 Bytes Cover Everything

Every string — English, café, 你好, 🚀, a tab, a newline — is stored as a sequence of bytes, and every byte is a number from 0 to 255. So a vocabulary that contains all 256 byte values can represent any text that has ever existed or ever will. A character the tokenizer has never seen is simply a byte sequence built from bytes it already knows.

# Any character is just UTF-8 bytes
for ch in ["A", "é", "☕", "好"]:
    b = ch.encode("utf-8")
    print(f"  {ch!r:6} → codepoint U+{ord(ch):04X} → bytes {list(b)}")
  'A'    → codepoint U+0041 → bytes [65]
  'é'    → codepoint U+00E9 → bytes [195, 169]
  '☕'    → codepoint U+2615 → bytes [226, 152, 149]
  '好'    → codepoint U+597D → bytes [229, 165, 189]

A one-byte ASCII letter stays one byte; é is two bytes; ☕ and 好 are three. The multi-byte characters fan out into several byte tokens — a little longer, but never unknown.

NoteKey Insight

Byte-level BPE has no <UNK> token by construction. There is no such thing as an unknown byte — all 256 are in the vocabulary from the start. This is the single reason production tokenizers are byte-level: every possible input is encodable and every round-trip is exact.

The bytes-to-unicode Trick

There is one wrinkle. BPE merges strings, but raw bytes include control characters — newline, tab, NUL — that are invisible or unsafe to handle as text. GPT-2’s solution (which we reuse) is to remap all 256 bytes to 256 distinct, printable Unicode characters before doing any BPE. Printable bytes map to themselves; the rest are shifted into a visible region starting at U+0100. The map is a bijection, so decoding recovers the exact original bytes.

from tokenizer import bytes_to_unicode

byte_map = bytes_to_unicode()
# Bytes that are normally invisible get a visible stand-in glyph
for b in [ord(" "), ord("\n"), ord("\t"), ord("A")]:
    print(f"  byte {b:3d} ({chr(b)!r:6}) → visible token {byte_map[b]!r}")

print(f"\n256 bytes → {len(set(byte_map.values()))} distinct printable glyphs")
  byte  32 (' '   ) → visible token 'Ġ'
  byte  10 ('\n'  ) → visible token 'Ċ'
  byte   9 ('\t'  ) → visible token 'ĉ'
  byte  65 ('A'   ) → visible token 'A'

256 bytes → 256 distinct printable glyphs

From Scratch: ByteLevelBPETokenizer

tokenizer.py implements this as ByteLevelBPETokenizer. It learns merges exactly like the character-level version — count adjacent pairs, merge the most frequent — but its base alphabet is the 256 byte tokens instead of the characters in the corpus. Watch it succeed on text a character-level tokenizer cannot handle:

from tokenizer import BPETokenizer, ByteLevelBPETokenizer, SPECIAL_TOKENS

# Train BOTH on the same ASCII-only corpus (no accents, no emoji, no CJK)
corpus = "the code returns hello world def class self " * 20

char_tok = BPETokenizer(vocab_size=400, verbose=False)
char_tok.train(corpus, show_progress=False)

byte_tok = ByteLevelBPETokenizer(vocab_size=400, verbose=False)
byte_tok.train(corpus, show_progress=False)

# Now encode a string full of characters neither one saw in training
text = "café ☕ 你好 — 42"

for name, tok in [("Character-level", char_tok), ("Byte-level", byte_tok)]:
    ids = tok.encode(text)
    unk = sum(1 for i in ids if i == SPECIAL_TOKENS["<UNK>"])
    ok = tok.decode(ids) == text
    print(f"{name:16}: {len(ids):2d} tokens, {unk} <UNK>, round-trip={ok}")
Character-level : 14 tokens, 7 <UNK>, round-trip=False
Byte-level      : 23 tokens, 0 <UNK>, round-trip=True

The character-level tokenizer riddles the output with <UNK> and cannot reconstruct the original. The byte-level tokenizer produces zero <UNK> and a perfect round-trip — the whole string survives as bytes. The convenience function demonstrate_byte_level() prints this comparison along with the full UTF-8 breakdown.

# The round-trip is exact, byte for byte
decoded = byte_tok.decode(byte_tok.encode(text))
print(f"Original:      {text!r}")
print(f"Reconstructed: {decoded!r}")
print(f"Exact match:   {decoded == text}")
Original:      'café ☕ 你好 — 42'
Reconstructed: 'café ☕ 你好 — 42'
Exact match:   True

Text → Bytes → Tokens → IDs

Here is the full byte-level pipeline. Step through it to watch each character fan out into its UTF-8 bytes, and each byte become an in-vocabulary token — so nothing is ever unknown.

Interactive: Byte Explorer

Type anything — accents, emoji, other scripts, code with tabs — and watch it expand into UTF-8 bytes. However exotic the input, the byte count is finite and every byte is a known token, so the “unknown bytes” count stays at zero.

TipTry This
  1. Emoji fan out: type 🚀 — one character becomes 4 bytes (highlighted), yet it is still fully encodable and reversible.
  2. Accents cost two: compare e (1 byte) with é (2 bytes). ASCII is cheap; everything else costs a little more length in exchange for universal coverage.
  3. Other scripts: paste 你好 or مرحبا. The “unknown bytes” count never moves off zero — that’s the guarantee a character-level tokenizer can’t make.
  4. Whitespace is bytes too: a tab and a newline are single bytes (9 and 10), so code indentation tokenizes cleanly.
WarningSplitting Bytes Mid-Character

Because one character can span several bytes, cutting a byte sequence in the middle of a multi-byte character leaves a partial, invalid UTF-8 fragment. ByteLevelBPETokenizer.decode() follows GPT-2 and decodes with errors="replace", turning any such fragment into the replacement character `` rather than crashing. This is why streaming decoders buffer bytes until a full character is available before showing text to the user.

Pre-tokenization: Bounding the Merges

There is a step that runs before BPE ever counts a pair, and it quietly decides the quality of every merge you learn: pre-tokenization. BPE only merges pairs that sit inside one pre-token — it never merges across a boundary. So the rule you use to chop text into pre-tokens is the rule that says which byte sequences are even allowed to become a single token.

Intuition: Why a Naive Split Hurts

Our byte-level tokenizer above split on the simple (\s+|\S+) rule — runs of whitespace or non-whitespace. That lets ugly things merge. Consider "don't": the naive split keeps it as one chunk, so BPE can learn a token that fuses the apostrophe into the word. Numbers are worse — "GPT2" as one chunk invites a "GPT2" token, and "2024" might partly merge into a neighbouring word. And because "the" and " the" (with a leading space) are different chunks that never share structure, the model wastes vocabulary learning both.

GPT-2 fixed this with a hand-crafted regex that pre-splits text into linguistically clean pieces before BPE runs. Its rules, in plain English:

  • Contractions come apart: "don't" → "don", "'t"; "I'll" → "I", "'ll".
  • Letters, digits, and punctuation never mix: "GPT2" → "GPT", "2".
  • A leading space rides with its word: " the" is one piece, so the model learns a single ” the” token and reuses it everywhere a word follows a space.
  • Whitespace runs stay intact (so code indentation survives).

The Pattern

Here is GPT-2’s regex, written for Python’s standard-library re (no third-party dependency). The original uses the Unicode classes \p{L} (letters) and \p{N} (numbers); the standard library spells a letter as [^\W\d_] — a word character that is neither a digit nor an underscore — and a digit as \d:

's|'t|'re|'ve|'m|'ll|'d| ?[^\W\d_]+| ?\d+| ?[^\s\w]+| ?_+|\s+(?!\S)|\s+
  └── contractions ──┘   └letters┘  └digits┘ └symbols┘ └_┘  └─ whitespace ─┘

The alternatives are tried left to right, and the pattern is total — every character lands in exactly one piece — so joining the pieces rebuilds the input byte-for-byte. That totality is what preserves the byte-level round-trip guarantee: pre-tokenization changes which merges are possible, never what text comes back.

From Scratch: gpt2_pretokenize

tokenizer.py compiles that pattern once and applies it with a single findall. ByteLevelBPETokenizer now uses it by default (pretokenizer="gpt2"); pass pretokenizer="simple" to fall back to the naive split.

from tokenizer import gpt2_pretokenize

print(gpt2_pretokenize("Don't merge GPT2 across_words!"))
print(gpt2_pretokenize(" the café costs €5.50"))

# Totality — the pieces rejoin to the original, so the round-trip is safe:
text = "café ☕ 你好\n\t42"
assert "".join(gpt2_pretokenize(text)) == text
print("round-trip-safe:", "".join(gpt2_pretokenize(text)) == text)
['Don', "'t", ' merge', ' GPT', '2', ' across', '_', 'words', '!']
[' the', ' café', ' costs', ' €', '5', '.', '50']
round-trip-safe: True

Now watch pre-tokenization change what BPE learns. Train two byte-level tokenizers on the same text — one with each split — and compare the merges:

from tokenizer import ByteLevelBPETokenizer

corpus = "don't stop. I'll pay $20. don't wait. I'll go. " * 40

gpt2 = ByteLevelBPETokenizer(vocab_size=300, pretokenizer="gpt2")
simple = ByteLevelBPETokenizer(vocab_size=300, pretokenizer="simple")
gpt2.train(corpus, show_progress=False)
simple.train(corpus, show_progress=False)

print("gpt2 merges:  ", gpt2.training_stats["num_merges"])
print("simple merges:", simple.training_stats["num_merges"])
# Both still round-trip perfectly — only the learned vocabulary differs:
print("gpt2 round-trip:  ", gpt2.decode(gpt2.encode("don't")) == "don't")
print("simple round-trip:", simple.decode(simple.encode("don't")) == "don't")
gpt2 merges:   22
simple merges: 22
gpt2 round-trip:   True
simple round-trip: True

Interactive: The Pre-token Splitter

Type any text and watch GPT-2’s regex carve it into pre-tokens, each coloured by category. A leading space is drawn as · so you can see it ride onto the next word. Every character belongs to exactly one chip — that is the totality that keeps the round-trip exact.

TipTry This
  1. Break a contraction: type wouldn't've — it splits into wouldn, 't, 've, three units BPE keeps separate.
  2. Numbers stay pure: type Route66 costs $1,024 — letters, digits, and punctuation never share a chip, so no Route66 or 1,024 token can form.
  3. The leading space: type the the the — every word after the first is ·the (space + word), one reusable token, distinct from a sentence-initial the.
  4. Switch to pretokenizer="simple" in the code above and retrain: the merges change, but decode(encode(x)) == x still holds — totality guarantees it.

Special Tokens

Before examining the code, understand special tokens - reserved tokens with specific meanings in the LLM pipeline:

Token Purpose When Used
<PAD> (ID 0) Padding Batch processing requires same-length sequences. Padding fills shorter sequences.
<UNK> (ID 1) Unknown Characters not seen during training. Production tokenizers avoid this with byte-level BPE.
<BOS> (ID 2) Beginning of Sequence Signals the start of text. Helps model distinguish context boundaries.
<EOS> (ID 3) End of Sequence Signals text completion. Model generates this to stop. Critical for generation.

The vocabulary reserves these tokens before training begins, ensuring consistent IDs across all tokenizers.

Chat Templates: Encoding a Conversation

When you chat with an assistant, you think in messages with roles — a system instruction, your question, the model’s reply. The model sees none of that structure. It consumes exactly one flat stream of token IDs, the same as any other text. So how does it know where your turn ends and its turn begins, or which words are the (trusted) system prompt versus the (untrusted) user input?

The answer is a chat template: an agreed convention for flattening a structured conversation into a single stream, using reserved control tokens to mark who is speaking and where each turn starts and stops. The most common one is ChatML, introduced with the OpenAI Chat API and adopted (with variants) by Qwen, Yi, and others. It wraps every turn in two control tokens — <|im_start|> and <|im_end|> — with the role name on the first line:

<|im_start|>system
You are a helpful assistant.<|im_end|>
<|im_start|>user
What is 2+2?<|im_end|>
<|im_start|>assistant
4<|im_end|>

Those <|im_start|> / <|im_end|> markers are not typed characters — they are single, atomic tokens, exactly like <BOS>/<EOS>. The model learns during training that “text after <|im_start|>user is a user turn” and “I should generate until <|im_end|>.” Roles are just tokens; the structure is entirely a tokenization convention.

NoteKey Insight

A chat model has no built-in concept of “messages” or “roles.” A chat template is pure tokenization: it serializes a list of {role, content} turns into one flat ID stream, marking the boundaries with reserved control tokens the model was trained to recognize. Change the template and the model gets confused — the format is part of the contract.

From scratch. tokenizer.py builds this directly. render_chatml flattens the messages; encode_chat keeps each control token atomic and runs the rest through BPE; chatml_segments returns the typed spans the visualizer below draws.

from tokenizer import render_chatml, encode_chat, chatml_segments, CHAT_TOKENS, BPETokenizer

conversation = [
    {"role": "system", "content": "You are a helpful assistant."},
    {"role": "user", "content": "What is 2+2?"},
]

# 1. Flatten the structured conversation into one string
templated = render_chatml(conversation, add_generation_prompt=True)
print("Rendered ChatML (add_generation_prompt=True):\n")
print(templated)
print("Control tokens:", CHAT_TOKENS)
Rendered ChatML (add_generation_prompt=True):

<|im_start|>system
You are a helpful assistant.<|im_end|>
<|im_start|>user
What is 2+2?<|im_end|>
<|im_start|>assistant

Control tokens: ['<|im_start|>', '<|im_end|>']

The trailing <|im_start|>assistant\n is the generation prompt — a dangling, open turn with no content and no end marker. That is what turns a transcript into a prompt: it primes the model to speak next, in the assistant role. Ask for a completion without it and the model has no signal that it is its turn.

# 2. Encode to a flat ID stream — control tokens stay atomic (one ID each)
tok = BPETokenizer(vocab_size=300)
tok.train("you are a helpful assistant what is 2 + 2 system user", show_progress=False)

ids = encode_chat(tok, conversation, add_generation_prompt=True)
print(f"Flat token IDs ({len(ids)} tokens):")
print(ids)

# Added special tokens extend the vocab: they get fresh IDs at the end
from tokenizer import chat_token_ids
print("\nAppended control-token IDs:", chat_token_ids(tok))
print(f"(regular tokens occupy 0..{len(tok.vocab)-1}; the two control tokens sit just past them)")
Flat token IDs (66 tokens):
[24, 18, 22, 18, 19, 8, 13, 1, 1, 15, 20, 4, 7, 17, 8, 4, 7, 4, 10, 8, 12, 16, 9, 20, 12, 4, 7, 18, 18, 23, 19, 7, 14, 19, 1, 25, 1, 24, 20, 18, 8, 17, 1, 1, 10, 7, 19, 4, 23, 4, 6, 5, 6, 1, 25, 1, 24, 7, 18, 18, 23, 19, 7, 14, 19, 1]

Appended control-token IDs: {'<|im_start|>': 24, '<|im_end|>': 25}
(regular tokens occupy 0..23; the two control tokens sit just past them)

Each <|im_start|> / <|im_end|> is a single ID in that stream — never a run of <, |, i, m… characters. A real tokenizer protects its special tokens from BPE exactly this way (our split_on_special does the same), and appending them to a pretrained vocabulary gives them fresh IDs at the end so they can never collide with a learned token.

Interactive: Chat-Template Builder

Pick a conversation and toggle the generation prompt. Watch the structured turns flatten into one stream, with the control tokens and role labels highlighted — this is precisely the byte sequence the model reads. (The builder below mirrors chatml_segments from tokenizer.py, whose spans you saw printed above.)

TipTry This
  1. Toggle the generation prompt off. The trailing <|im_start|>assistant disappears — you now have a transcript, not a prompt. Toggle it back on to prime the model to reply.
  2. Switch to the multi-turn conversation. Notice the assistant’s earlier reply is wrapped and closed just like any other turn — the model’s own past outputs are fed back to it inside the same template.
  3. Count the control tokens. Two per closed turn (<|im_start|> … <|im_end|>) plus one for the open generation turn. Every one is a single ID, not the characters you see.
WarningThe template is part of the contract

A model is trained with one specific chat template. Feed it a conversation formatted with a different one — wrong control tokens, a missing <|im_end|>, the role label in the wrong place — and quality collapses, because the boundaries it learned to rely on are no longer where it expects. When you use a pretrained chat model, always apply its template, not a generic one.

Code Walkthrough

Explore tokenization interactively:

# Import our BPE tokenizer
from tokenizer import BPETokenizer, SPECIAL_TOKENS

print("Special tokens:", SPECIAL_TOKENS)
print("\nThese tokens are reserved at IDs 0-3 before training begins.")
Special tokens: {'<PAD>': 0, '<UNK>': 1, '<BOS>': 2, '<EOS>': 3}

These tokens are reserved at IDs 0-3 before training begins.

Training a BPE Tokenizer

The BPETokenizer class has key parameters:

  • vocab_size: Target vocabulary size (including special tokens)
  • min_frequency: Minimum times a pair must appear to be merged (default: 2). This prevents rare pairs from being merged — if a pair only appears once, it’s likely noise rather than a useful pattern. Higher values create more conservative, generalizable vocabularies.
  • verbose: Print detailed training progress
# Simple text to train on
simple_text = "ab cd ab cd ab cd ab cd " * 20

# Create and train tokenizer
# vocab_size includes the 4 special tokens, so effective learned tokens = vocab_size - 4
tokenizer = BPETokenizer(vocab_size=30, verbose=False)
stats = tokenizer.train(simple_text, show_progress=True)

print(f"\nVocab size: {stats['vocab_size']}")
print(f"Merges learned: {stats['num_merges']}")
print(f"Special tokens: {stats['num_special_tokens']}")
============================================================
BPE TOKENIZER TRAINING
============================================================
Text length: 480 characters
Target vocab size: 30


Training complete!
  Final vocab size: 11
  Merges learned: 2


Vocab size: 11
Merges learned: 2
Special tokens: 4
# See what patterns were learned
print("Learned merges:")
for i, ((a, b), merged) in enumerate(list(tokenizer.merges.items())[:10]):
    print(f"  {i+1}. {repr(a)} + {repr(b)} -> {repr(merged)}")
Learned merges:
  1. 'a' + 'b' -> 'ab'
  2. 'c' + 'd' -> 'cd'

Encoding and Decoding

Encoding applies merges in their learned order. This is crucial - the merge order determines how text is split.

# Encode some text
test_text = "ab cd"
ids = tokenizer.encode(test_text)
tokens = [tokenizer.id_to_token(i) for i in ids]

print(f"Text: '{test_text}'")
print(f"Token IDs: {ids}")
print(f"Tokens: {tokens}")

# Decode back
decoded = tokenizer.decode(ids)
print(f"Decoded: '{decoded}'")
print(f"Round-trip successful: {test_text == decoded}")
Text: 'ab cd'
Token IDs: [9, 4, 10]
Tokens: ['ab', ' ', 'cd']
Decoded: 'ab cd'
Round-trip successful: True
# With special tokens (used during actual LLM training/inference)
ids_with_special = tokenizer.encode(test_text, add_special_tokens=True)
print(f"\nWith special tokens: {ids_with_special}")
print(f"Tokens: {[tokenizer.id_to_token(i) for i in ids_with_special]}")

# Decoding skips special tokens by default
decoded = tokenizer.decode(ids_with_special, skip_special_tokens=True)
print(f"Decoded (skip special): '{decoded}'")

With special tokens: [2, 9, 4, 10, 3]
Tokens: ['<BOS>', 'ab', ' ', 'cd', '<EOS>']
Decoded (skip special): 'ab cd'

Training on Python Code

python_code = '''
def fibonacci(n):
    """Calculate the nth Fibonacci number."""
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

def factorial(n):
    """Calculate n factorial."""
    if n <= 1:
        return 1
    return n * factorial(n - 1)

class Calculator:
    def __init__(self):
        self.result = 0

    def add(self, x):
        self.result += x
        return self

    def subtract(self, x):
        self.result -= x
        return self

# Main execution
if __name__ == "__main__":
    print(fibonacci(10))
    print(factorial(5))
'''

print(f"Training on {len(python_code)} characters of Python code")
Training on 562 characters of Python code
# Train tokenizer on code
code_tokenizer = BPETokenizer(vocab_size=200, verbose=False)
stats = code_tokenizer.train(python_code * 3, show_progress=True)

print(f"\nFinal vocab size: {stats['vocab_size']}")
print(f"Merges learned: {stats['num_merges']}")
============================================================
BPE TOKENIZER TRAINING
============================================================
Text length: 1,686 characters
Target vocab size: 200

  Merge 50: 'self.res' + 'ul' → 'self.resul' (count: 9, progress: 32.1%)
  Merge 100: 'sub' + 't' → 'subt' (count: 3, progress: 64.1%)

Training complete!
  Final vocab size: 177
  Merges learned: 133


Final vocab size: 177
Merges learned: 133
# Look at what code patterns were learned
print("Interesting tokens learned (longest first):")
print("=" * 40)

interesting_patterns = []
for token, id in code_tokenizer.vocab.items():
    if len(token) >= 2 and not token.startswith('<'):
        interesting_patterns.append((token, id))

# Sort by length (longer = more merged)
interesting_patterns.sort(key=lambda x: len(x[0]), reverse=True)

for token, id in interesting_patterns[:15]:
    print(f"  {id:3d}: {repr(token)}")
Interesting tokens learned (longest first):
========================================
  172: 'print(fibonacci(10))'
  176: 'print(factorial(5))'
  171: 'print(fibonacci(10'
  170: 'print(fibonacci(1'
  175: 'print(factorial(5'
  169: 'print(fibonacci('
  174: 'print(factorial('
  136: '__init__(self):'
  168: 'print(fibonacci'
  173: 'print(factorial'
  146: 'subtract(self,'
  110: 'fibonacci(n):'
  122: 'factorial(n):'
  123: 'factorial."""'
  135: '__init__(self'

Visualizing Tokenization

def visualize_tokens(tokenizer, text):
    """Show how text is split into tokens with colors."""
    ids = tokenizer.encode(text)
    tokens = [tokenizer.id_to_token(i) for i in ids]

    print(f"Original: {repr(text)}")
    print(f"Tokens ({len(tokens)}): {tokens}")
    print(f"IDs: {ids}")
    print(f"Compression: {len(text)/len(ids):.2f} chars/token")
    print()

# Try different code patterns
patterns = [
    "def fibonacci(n):",
    "self.result = 0",
    "return self",
    "    for i in range(10):",
]

for pattern in patterns:
    visualize_tokens(code_tokenizer, pattern)
Original: 'def fibonacci(n):'
Tokens (3): ['def', ' ', 'fibonacci(n):']
IDs: [64, 5, 110]
Compression: 5.67 chars/token

Original: 'self.result = 0'
Tokens (5): ['self.result', ' ', '=', ' ', '0']
IDs: [94, 5, 21, 5, 15]
Compression: 3.00 chars/token

Original: 'return self'
Tokens (3): ['return', ' ', 'self']
IDs: [60, 5, 52]
Compression: 3.67 chars/token

Original: '    for i in range(10):'
Tokens (18): ['    ', 'f', 'o', 'r', ' ', 'i', ' ', 'in', ' ', 'r', 'a', 'n', '<UNK>', 'e', '(', '1', '0', '):']
IDs: [45, 31, 37, 39, 5, 33, 5, 88, 5, 39, 26, 36, 1, 30, 8, 16, 15, 71]
Compression: 1.28 chars/token

Vocabulary Size Tradeoffs

Vocabulary size is one of the most important hyperparameters in tokenization:

Larger vocabulary: - (+) Shorter sequences = faster training, more context in fixed window - (+) Common words as single tokens = better semantic units - (-) Larger embedding table = more parameters, more memory - (-) Rare tokens get few training examples = poor representations

Smaller vocabulary: - (+) Smaller model, faster embedding lookups - (+) Every token well-trained on many examples - (-) Longer sequences = slower training, less context - (-) Words split into less meaningful pieces

test_text = "def calculate_fibonacci(number):\n    return fibonacci(number)"

vocab_sizes = [50, 100, 200, 500]

print(f"Text: {repr(test_text)}")
print(f"Text length: {len(test_text)} characters")
print()

for vocab_size in vocab_sizes:
    tok = BPETokenizer(vocab_size=vocab_size, verbose=False)
    tok.train(python_code * 5, show_progress=False)

    ids = tok.encode(test_text)
    tokens = [tok.id_to_token(i) for i in ids]

    print(f"Vocab size {vocab_size}:")
    print(f"  Tokens: {len(ids)}")
    print(f"  Ratio: {len(test_text)/len(ids):.1f} chars/token")
    print(f"  Sample: {[tok.id_to_token(i) for i in ids[:5]]}...")
    print()
Text: 'def calculate_fibonacci(number):\n    return fibonacci(number)'
Text length: 61 characters

Vocab size 50:
  Tokens: 54
  Ratio: 1.1 chars/token
  Sample: ['d', 'e', 'f', ' ', 'c']...

Vocab size 100:
  Tokens: 27
  Ratio: 2.3 chars/token
  Sample: ['def', ' ', 'c', 'al', 'c']...

Vocab size 200:
  Tokens: 27
  Ratio: 2.3 chars/token
  Sample: ['def', ' ', 'c', 'al', 'c']...

Vocab size 500:
  Tokens: 27
  Ratio: 2.3 chars/token
  Sample: ['def', ' ', 'c', 'al', 'c']...

Real-world vocabulary sizes: - GPT-2: 50,257 tokens - GPT-4: ~100,000 tokens - Llama 2: 32,000 tokens - Claude: ~100,000 tokens

Saving and Loading

import tempfile
import os

# Save tokenizer
save_path = tempfile.mktemp(suffix='.json')
code_tokenizer.save(save_path)

# Load it back
loaded = BPETokenizer.load(save_path)

# Verify it works the same
test = "def test():"
original_ids = code_tokenizer.encode(test)
loaded_ids = loaded.encode(test)

print(f"\nOriginal encoding: {original_ids}")
print(f"Loaded encoding:   {loaded_ids}")
print(f"Match: {original_ids == loaded_ids}")

# Cleanup
os.unlink(save_path)
Tokenizer saved to /tmp/tmp9yrp_zt6.json
Tokenizer loaded from /tmp/tmp9yrp_zt6.json
  Vocab size: 177

Original encoding: [64, 5, 41, 30, 40, 41, 8, 71]
Loaded encoding:   [64, 5, 41, 30, 40, 41, 8, 71]
Match: True

Interactive Exploration

Watch BPE tokenization step by step. Type text and see how it gets broken into tokens through iterative pair merging.

WarningDemo Uses Pre-defined Merge Rules

This interactive demo uses a simplified, pre-defined set of common English merge rules — not dynamically computed merges. A real tokenizer learns merges from a training corpus, but the mechanism shown here is identical. The Python implementation above (BPETokenizer) demonstrates actual BPE training.

TipTry This

  1. Common words merge well: Type “the” or “and” - they become single tokens quickly due to high-frequency merges.

  2. Step through merges: Enable “Show step-by-step” and slide the merge steps from 0 to max. Watch how character pairs combine into larger tokens.

  3. Rare words stay split: Type “xyz” or uncommon words - they remain as characters because those patterns weren’t in the training data.

  4. Compression varies: Compare “the the the” (high compression) vs “qxz qxz qxz” (low compression). Common patterns compress better.

  5. Spaces are preserved: Notice that spaces remain as separate tokens (shown as ␣). This is typical BPE behavior.

Exercises

Exercise 1: Compression Efficiency

BPE achieves better compression on repetitive text. This matters because better compression = shorter sequences = more context in the model’s window.

# Train on repetitive vs varied text and compare compression

texts = {
    "repetitive": "the the the " * 100,
    "varied": " ".join([f"word{i}" for i in range(100)]),
    "code": python_code,
}

print("Compression comparison:")
print("=" * 40)

for name, text in texts.items():
    tok = BPETokenizer(vocab_size=200, verbose=False)
    tok.train(text, show_progress=False)
    ids = tok.encode(text)
    ratio = len(text) / len(ids)
    print(f"{name:12s}: {ratio:.2f} chars/token")

print("\nNote: Repetitive text compresses best because BPE learns")
print("common patterns. Code has structure but more variety.")
Compression comparison:
========================================
repetitive  : 2.00 chars/token
varied      : 2.38 chars/token
code        : 2.70 chars/token

Note: Repetitive text compresses best because BPE learns
common patterns. Code has structure but more variety.

Exercise 2: Analyze the First Merges

The first merges reveal the most frequent patterns in your data. For English text, you’ll often see common letter pairs like ‘th’, ‘he’, ‘in’.

# What patterns are learned first?

sample_text = "hello world hello world hello world " * 10
tok = BPETokenizer(vocab_size=50, verbose=False)
tok.train(sample_text, show_progress=False)

print("First 10 merges (most frequent patterns):")
for i, ((a, b), merged) in enumerate(list(tok.merges.items())[:10]):
    print(f"  {i+1}. '{a}' + '{b}' = '{merged}'")

print("\nNotice: Common substrings merge first, eventually")
print("forming complete words like 'hello' and 'world'.")
First 10 merges (most frequent patterns):
  1. 'h' + 'e' = 'he'
  2. 'he' + 'l' = 'hel'
  3. 'hel' + 'l' = 'hell'
  4. 'hell' + 'o' = 'hello'
  5. 'w' + 'o' = 'wo'
  6. 'wo' + 'r' = 'wor'
  7. 'wor' + 'l' = 'worl'
  8. 'worl' + 'd' = 'world'

Notice: Common substrings merge first, eventually
forming complete words like 'hello' and 'world'.

Exercise 3: Observe Unknown Character Behavior

Our simple tokenizer can only encode characters it saw during training. Characters not in the vocabulary become <UNK> tokens. This exercise demonstrates the problem — and why production tokenizers use byte-level BPE to solve it.

# What happens with characters not in training?

tokenizer = BPETokenizer(vocab_size=50, verbose=False)
tokenizer.train("hello world", show_progress=False)

# Try encoding text with emoji
test = "hello world"  # Safe text
try:
    ids = tokenizer.encode(test)
    print(f"'{test}' -> {ids}")
    print(f"Decoded: '{tokenizer.decode(ids)}'")
except Exception as e:
    print(f"Error: {e}")

# Now try with a character not in training
test2 = "hello 123"
ids = tokenizer.encode(test2)
tokens = [tokenizer.id_to_token(i) for i in ids]
print(f"\n'{test2}' -> {ids}")
print(f"Tokens: {tokens}")
print("\nNotice: '1', '2', '3' become <UNK> (ID 1) because they")
print("weren't in the training data.")
print("\nThe byte-level tokenizer we built above has no such failure mode.")
'hello world' -> [7, 6, 8, 8, 9, 4, 11, 9, 10, 8, 5]
Decoded: 'hello world'

'hello 123' -> [7, 6, 8, 8, 9, 4, 1, 1, 1]
Tokens: ['h', 'e', 'l', 'l', 'o', ' ', '<UNK>', '<UNK>', '<UNK>']

Notice: '1', '2', '3' become <UNK> (ID 1) because they
weren't in the training data.

The byte-level tokenizer we built above has no such failure mode.
# The same unseen text, encoded with the byte-level tokenizer we built
from tokenizer import ByteLevelBPETokenizer

byte_tokenizer = ByteLevelBPETokenizer(vocab_size=400, verbose=False)
byte_tokenizer.train("hello world", show_progress=False)

for probe in ["hello 123", "hello ☕", "你好"]:
    ids = byte_tokenizer.encode(probe)
    unk = sum(1 for i in ids if i == SPECIAL_TOKENS["<UNK>"])
    print(f"  {probe!r:12} → {len(ids)} tokens, {unk} <UNK>, "
          f"round-trip={byte_tokenizer.decode(ids) == probe}")

print("\nOperating on UTF-8 bytes (0-255) means any input is encodable —")
print("this is exactly how tiktoken and SentencePiece avoid <UNK>.")
  'hello 123'  → 9 tokens, 0 <UNK>, round-trip=True
  'hello ☕'    → 9 tokens, 0 <UNK>, round-trip=True
  '你好'         → 6 tokens, 0 <UNK>, round-trip=True

Operating on UTF-8 bytes (0-255) means any input is encodable —
this is exactly how tiktoken and SentencePiece avoid <UNK>.

Exercise 4: Whitespace Handling

Whitespace is tricky in tokenization. Our tokenizer preserves it, but notice how spaces can be part of tokens.

# Whitespace is significant in tokenization
code_tok = BPETokenizer(vocab_size=100, verbose=False)
code_tok.train("def foo():\n    return 1\ndef bar():\n    return 2", show_progress=False)

# See how indentation is tokenized
samples = [
    "def foo():",
    "    return",  # 4 spaces
    "        x",   # 8 spaces
]

for sample in samples:
    ids = code_tok.encode(sample)
    tokens = [code_tok.id_to_token(i) for i in ids]
    print(f"{repr(sample):20s} -> {tokens}")

print("\nIn production tokenizers, leading spaces often attach to")
print("the following word: ' hello' is one token, not ' ' + 'hello'")
'def foo():'         -> ['def', ' ', 'f', 'o', 'o', '():']
'    return'         -> ['  ', '  ', 'return']
'        x'          -> ['  ', '  ', '  ', '  ', '<UNK>']

In production tokenizers, leading spaces often attach to
the following word: ' hello' is one token, not ' ' + 'hello'

Tokenization in the LLM Pipeline

Tokenization occupies the first stage of the LLM pipeline:

Summary

Key takeaways:

  1. BPE learns subword units by iteratively merging the most frequent adjacent token pairs
  2. Vocabulary size is a tradeoff: larger = shorter sequences but more parameters and sparse token usage
  3. Special tokens (BOS, EOS, PAD, UNK) serve critical roles in the LLM pipeline
  4. Code patterns emerge naturally (def, self., return, indentation) when trained on code
  5. Round-trip guarantee: encode -> decode should perfectly reconstruct the original text
  6. Byte-level BPE starts from the 256 UTF-8 bytes instead of characters, so it encodes any text — emoji, accents, CJK — with no <UNK> and an exact round-trip. This is the layout GPT-2, tiktoken, and SentencePiece all use.
  7. Pre-tokenization runs before BPE and bounds every merge to one pre-token. GPT-2’s regex splits off contractions, keeps letters/digits/punctuation apart, and lets a leading space ride with its word — all while staying total, so the round-trip holds. Cleaner boundaries mean a cleaner learned vocabulary.
  8. Chat templates (ChatML) serialize a role-tagged conversation into one flat ID stream, using reserved <|im_start|>/<|im_end|> control tokens to mark turns. Roles are just tokens; the add_generation_prompt open turn is what primes the model to reply. The template is part of the model’s contract.

What We Simplified

Even the byte-level tokenizer we built still differs from production tokenizers in several ways:

Our Tokenizer Production Tokenizers
Byte-level BPE (built above) — plus a simpler character-level version Byte-level BPE (same core idea)
GPT-2 regex pre-tokenization (built above) GPT-2 regex pre-tokenization (same)
Python dict lookups Optimized Rust/C++ (tiktoken is 10x+ faster)
Trained on tiny corpora Trained on trillions of tokens

Pre-tokenization — which we built above with gpt2_pretokenize — is the step that keeps merges linguistically clean by bounding BPE to one pre-token at a time. The main gap that remains is speed: production tokenizers run the same regex and BPE in optimized Rust/C++ (tiktoken is 10×+ faster than our teaching Python) and cache merges aggressively, but the algorithm is exactly the one you just built.

Practical Implications

  • Context length: A 4096-token context window holds varying amounts of text depending on tokenization efficiency
  • Cost: API pricing is per-token, so tokenization directly affects cost
  • Multilingual: Tokenizers trained on English use more tokens for other languages (2-3x for some)
  • Code vs prose: Code often tokenizes inefficiently (many single-character tokens for syntax)

What’s Next

Module 04: Embeddings converts token IDs into dense vectors that capture meaning. Each token becomes a learnable vector in high-dimensional space.