Tokenization and BPE

Tokens are the interface

Every language model you build or deploy consumes tokens, not raw strings. Tokenization is the bridge between human-readable UTF-8 text and the integer sequences a neural network processes. Get tokenization wrong and you waste context window, mangle source code, inflate API costs, or silently break multilingual text.

When OpenAI charges per token, when your RAG chunker splits mid-word, when Python indentation disappears in model output — that is tokenization showing up in product behavior. Understanding it is not an academic side quest; it is step one of the real LLM algorithm you will implement in this module.

A token is an entry in a fixed vocabulary (vocab). The tokenizer maps text → list of token IDs, and the detokenizer maps IDs → text. The model sees only IDs; everything else is plumbing you own.

Callout — tokenization is lossy compression: Round-trip encode→decode usually recovers the original text, but the boundaries where you split affect what the model can learn. There is no universally perfect split — only tradeoffs.

Character vs word vs subword

Three families dominate. Each makes different tradeoffs between vocabulary size and sequence length.

Character-level

Split text into individual characters (or bytes).

• Vocab: ~100–256 entries (ASCII or UTF-8 bytes).
• Sequences: Very long — "hello" is 5 tokens.
• Pros: No unknown tokens; handles any language and emoji.
• Cons: Model must compose meaning from tiny units; long sequences mean slower training and less context for the same window.

Character models are great for learning and tiny demos; production LMs rarely stop at characters alone.

Word-level

Split on whitespace and punctuation rules.

• Vocab: Tens or hundreds of thousands of words.
• Sequences: Short.
• Pros: Each token carries semantic weight.
• Cons: Huge vocab; any word not in vocab becomes <UNK>; morphology wasted ("running" and "runs" are unrelated tokens).

Word tokenization fails on code, URLs, rare names, and agglutinative languages.

Subword (BPE, WordPiece, Unigram)

Split frequent words whole; split rare words into pieces.

• Vocab: Typically 32k–100k merges.
• Sequences: Moderate length.
• Pros: Industry default for GPT, LLaMA, Claude, etc.; no UNK for most text; shared subwords across related words ("play", "playing", "played" share "play").
• Cons: Same English word can tokenize differently in context; code and whitespace are painful edge cases.

Byte Pair Encoding (BPE) in plain language

BPE starts from a base vocabulary — usually bytes or characters — and iteratively merges the most frequent adjacent pair into a new token.

Training algorithm (simplified):

1. Start with every byte/character as a token.
2. Count all adjacent pairs in the corpus.
3. Merge the most frequent pair into a new token; add it to vocab.
4. Repeat until vocab reaches target size (e.g. 8,000 for a tiny LM, 50,257 for GPT-2).

Example intuition on a tiny corpus where "low" appears often:

Initial:  l o w   l o w e r
Merge "l"+"o" → "lo":  lo w   lo w e r
Merge "lo"+"w" → "low":  low   lo w e r
Merge "w"+"e" → "we":   low   lo we r
...

After training, "lower" might tokenize as ["lo", "wer"] while "low" stays one token. Frequent strings get short encodings; rare strings get longer ones.

GPT-2 uses byte-level BPE — the base unit is a byte, not a Unicode character. That guarantees every possible UTF-8 string can be encoded without UNK, at the cost of occasionally splitting multibyte characters across tokens.

Encode and decode

Encode: Greedy longest-match against the merge table (or vocab lookup). Scan left to right; take the longest substring that is a known token.

Decode: Concatenate token strings (with GPT-2 BPE, bytes are reconstructed into UTF-8). A broken decoder produces mojibake or spurious spaces.

Always test round-trip on: plain English, a rare name, emoji, Python code with indentation, and a non-Latin script.

Why tokenization affects LLM behavior

Context window is measured in tokens

A 4k context model fits ~3,000 English words but fewer if the text is code or Chinese (often more tokens per character). Chunking strategies for RAG must tokenize the same way the model will.

Cost scales with tokens

API billing, latency, and KV-cache memory all grow with token count. A tokenizer that splits efficiently for your domain saves real money.

Code and whitespace

Leading spaces in Python matter. Some tokenizers strip or merge whitespace aggressively; models trained on those tokenizers may struggle with indentation-sensitive languages. If you fine-tune on code, use a code-aware tokenizer or verify whitespace round-trips.

Multilingual text

Languages with large character sets may require more tokens per sentence than English. "Fair" multilingual evaluation must account for tokenization inequality — comparing perplexity across languages without normalizing by tokens misleads.

Practical tokenizer tooling

For learning, implement minimal BPE from scratch (~100 lines). For production:

• Hugging Face tokenizers — fast Rust backend, trains BPE/Unigram/WordPiece.
• tiktoken — OpenAI's BPE; matches GPT models exactly.
• sentencepiece — used by LLaMA, T5; handles whitespace differently (▁ marker).

When you train your tiny tokenizer in the project, prefer from-scratch once so merges are not a black box. Using a library is fine if you document each training step and can explain why a string split the way it did.

What you will build toward in this module

This module ends with your mini-LLM in the portfolio. Tokenization is step one of the real algorithm — not a side quest. The arc:

1. Tokenizer (this lesson) — text ↔ IDs
2. Bigram LM — count-based next-token prediction
3. MLP LM — neural next-token with fixed context
4. Self-attention — variable-length dependency
5. Tiny GPT — stack blocks, train, generate
6. Sampling — turn logits into readable text
7. Training stages map — pretrain, SFT, preference
8. Honest limits — what your tiny model is not

Each lesson adds one layer. The tokenizer you train here feeds directly into your tiny GPT training script.

Engineering problem (staff framing)

Models consume token IDs. Bad tokenization wastes context, breaks code, inflates cost, and mangles multilingual text.

Diagram — Text → tokens → model

flowchart LR
  UTF[UTF-8 text] --> Tok[Tokenizer BPE]
  Tok --> IDs[Token IDs]
  IDs --> EM[Embedding table]
  EM --> LM[Transformer LM]
  LM --> Out[Next-token logits]
  Out --> Detok[Detokenize]

Precise definitions & mental model

• Token — vocab entry; atomic LM input.
• BPE — iteratively merge frequent adjacent pairs from byte/char base.
• Compression tradeoff — larger vocab ⇒ shorter sequences ⇒ different cost/quality.
• Special tokens — BOS/EOS/pad/tool markers are product API surface.

Tradeoffs — when to use what

Failure modes (interview + on-call)

• Counting words as tokens for pricing.
• Chunking RAG mid-token / mid-codepoint.
• Leading-space token surprises (' hello' vs 'hello').
• Training tokenizer on different corpus than LM.

Production & OSS practices

Freeze tokenizer with model; store tokenizer.json; add encode/decode round-trip tests; measure tokens/request in prod metrics.

Interview cue card

Why might 'Python' be one token but a rare surname many? Impact on cost and multilingual fairness?

Deep dive (FAANG / OSS bar)

Why subword boundaries are a product bug class

Production incidents that look like "the model is dumb" are often tokenizer artifacts:

1. Leading-space tokens — GPT-family tokenizers often include a leading space in word tokens. Few-shot exemplars that inconsistently include spaces shift the entire continuation distribution.
2. Digit fragmentation — large numbers may become many tokens; math and invoice fields blow context and confuse arithmetic unless you preprocess.
3. Code indentation — spaces vs tabs; some tokenizers emit one token per two spaces, others per space. Formatters that rewrite indentation change token IDs under the model.
4. Multilingual fairness — languages underserved in the merge table pay more tokens per grapheme ⇒ higher cost and shorter effective context for the same UX budget.

BPE training vs encoding (do not conflate)

• Train merges on a corpus until vocab size N.
• Encode greedily (or with more advanced algorithms) using the frozen merge table.

If you train a toy BPE on Shakespeare then encode Python, you will see pathological fragmentation. Always ship tokenizer.json / tokenizer.model with the checkpoint digest.

Diagram — encode path detail

sequenceDiagram
  participant U as UTF-8
  participant N as NFC / pre-norm
  participant B as Byte/char base
  participant M as Merge table
  participant I as ID sequence
  U->>N: normalize
  N->>B: base symbols
  B->>M: apply merges
  M->>I: vocab IDs

Interview drill

Given vocab size V and sequence length T, embedding matrix is V × d. Explain how doubling V at fixed T changes memory, and how halving T via better compression changes attention FLOPs (~T²).

Micro-project: Train tiny tokenizer

In m3/tokenizer/:

1. Take a small text corpus (e.g. tiny Shakespeare, a few MB of public domain text, or your own markdown notes).
2. Implement or use a minimal BPE trainer (from-scratch preferred for learning; tokenizers library acceptable if you document every step).
3. Save vocab.json and merges.txt (or equivalent); show encode→decode round-trip on 5 strings:
   • A common English sentence
   • A rare or made-up word ("ShipAI-tokenizer-test")
   • A Python function with indentation
   • A string with emoji
   • A non-English phrase (if your corpus supports it)
4. Report vocab size and average tokens-per-word on a 100-word sample.

Write NOTES.md answering: what broke on code or Unicode? Which merge was surprising?

Checklist

• Round-trip tests pass on all 5 test strings
• Artifacts committed (vocab.json, merges file)
• Vocab size and tokens-per-word reported
• Short note on code/Unicode edge cases