Warmup Guide — Foundations: Text

Zero-to-expert primer for Phase 01. How raw bytes become the token IDs a language model consumes — Unicode, encodings, and the BPE algorithm you will implement from scratch — assuming only basic Python.

Table of Contents

Chapter 1: Text Is Not Strings — Bytes, Code Points, Graphemes

From zero: three distinct layers, conflated at your peril:

  • Bytes: what disks and networks carry. "é" is 0xC3 0xA9 in UTF-8 — two bytes.
  • Code points: Unicode's atomic units, U+0000–U+10FFFF. é is U+00E9 — or, equally validly, e (U+0065) + combining acute (U+0301): two code points that render identically. Normalization forms (NFC composes, NFD decomposes) exist to canonicalize this — and whether a tokenizer normalizes changes its output.
  • Graphemes: what a human calls "one character." 👩‍👩‍👧 is one grapheme, seven code points (three emoji + two zero-width joiners), eighteen UTF-8 bytes.

UTF-8, the encoding that won: variable-length (1–4 bytes per code point), ASCII is valid UTF-8 unchanged, no byte-order issues, self-synchronizing (continuation bytes are distinguishable from start bytes — you can find a character boundary from any offset). The practical law: all text at system boundaries is UTF-8 bytes; decode explicitly; never trust a default encoding (Phase 05 of the PMC track meets the same law as a SpotBugs pattern — it's universal).

Chapter 2: Why Models Need Tokens at All

A neural LM consumes a sequence of integers from a fixed vocabulary, each mapped to an embedding vector. The tokenizer is the bridge: text → [int]. The design tension:

  • Character/byte level (vocab ~256): no out-of-vocabulary problem ever — but sequences are ~4× longer than word-level, and attention cost grows quadratically with length (the model-accuracy track's Phase 07 math). Long sequences also dilute what each position can learn.
  • Word level (vocab ~1M): short sequences, but unbounded vocabulary — every typo, inflection, and new name is out-of-vocabulary (OOV); embedding tables explode; and morphology is invisible (run/running unrelated).
  • Subword (vocab 32K–256K): the resolution — frequent strings become single tokens (the, ing, tion), rare words decompose into pieces (tokenization → token|ization). No OOV (worst case: decompose to bytes), bounded vocab, morphology partially visible. Every modern LLM lives here.

The compression view is the deepest framing: a tokenizer is a learned compression codec for its training distribution — typical English compresses to ~0.75 tokens/word in GPT-class vocabularies. Everything about cost (context windows, API pricing, latency) is denominated in this codec's output.

Chapter 3: The Tokenization Design Space

The three families (know all; implement one):

  • BPE (Byte-Pair Encoding): bottom-up greedy merging of frequent pairs (Chapter 4). GPT-2/3/4, LLaMA, most modern models. Deterministic, simple, fast.
  • WordPiece (BERT): like BPE but merges the pair maximizing likelihood gain (score = pair_count / (left_count × right_count)) rather than raw frequency — favors pairs that are informative, not just common. Continuation pieces marked ##.
  • Unigram LM (SentencePiece's default mode): top-down — start with a huge candidate vocabulary, iteratively remove pieces whose removal least hurts corpus likelihood under a unigram model; tokenization is then the Viterbi-best segmentation. Probabilistic, supports sampling multiple segmentations (subword regularization).
  • SentencePiece the library (often confused with the algorithm): treats input as a raw code-point stream (no pre-splitting on whitespace — language-agnostic; spaces become ▁), and implements both BPE and Unigram.

Chapter 4: Byte-Pair Encoding — The Algorithm

Training (what your lab implements):

  1. Start with a base vocabulary (all bytes, or all characters in the corpus).
  2. Count all adjacent symbol pairs in the corpus.
  3. Merge the most frequent pair into a new symbol; add it to the vocab; record the merge rule (A, B) → AB in order.
  4. Repeat until vocab reaches target size (the merge list — ordered — is the model).

Encoding new text: split to base symbols, then apply the merge rules in training order (not greedy-longest-match!) — at each step, find the present pair that was learned earliest and merge all its occurrences. This ordering rule is the #1 implementation bug: greedy longest-match produces different (wrong) tokenizations that silently disagree with the reference.

Complexity reality: naive training recounts all pairs each merge — O(merges × corpus); fine for the lab. Production trainers maintain pair counts incrementally with priority queues. Encoding is near-linear with the right data structure (linked-list of symbols + a heap of candidate merges).

The pre-tokenization detail that matters: GPT-class BPE first splits text with a regex (on whitespace/letter/number/punctuation boundaries, keeping the leading space attached to the word: " world" is one pre-token). Merges never cross pre-token boundaries. This is why "world" and " world" are different tokens with different IDs — and why prompts that end with a trailing space produce subtly worse completions (you've stranded the model off its learned distribution).

Chapter 5: Byte-Level BPE — What GPT Actually Does

Character-level base vocabularies still have an OOV problem (a new Unicode character). GPT-2's move: run BPE over bytes. Base vocab = 256, every possible input is representable, full stop. One wrinkle: raw bytes include unprintable values that make merge files unreadable, so GPT-2 maps each byte to a printable Unicode proxy character (the famous Ġ is the proxy for the space byte 0x20). When you see Ġworld in a vocab dump, you're reading "space + world" through that proxy alphabet.

Cost of byte-level: non-Latin scripts pay heavily — a Chinese character is 3 UTF-8 bytes, and with few learned merges for it, tokens-per-character ratios for non-English text run 2–4× English's. This tokenizer tax is why multilingual models train larger vocabularies (LLaMA-3: 128K; Qwen: 152K) — more merges to amortize the world's scripts — and it's directly an inference-cost and context-budget issue you will own (Chapter 7).

Chapter 6: Vocabularies, Special Tokens, and the Embedding Contract

  • The tokenizer's output range [0, V) is the contract with the model's embedding table (V × d_model) and output head. Mismatch = garbage or crashes; this is why tokenizer files ship with checkpoints and why "I'll just use a different tokenizer" is never a thing.
  • Special tokens are IDs reserved outside BPE: <|endoftext|> / <s> </s> (BOS/EOS), padding, and — in chat models — role markers (<|im_start|> etc.). Two properties matter operationally: they must never be producible by encoding user text (else prompt injection by literally typing the marker — tokenizers have an explicit "special tokens are not encoded from text" path for this), and chat templates (the exact arrangement of role markers) are part of the model contract — a wrong template silently degrades quality with no error anywhere.
  • Vocab size trade-off: larger V = shorter sequences (cheaper attention) but a bigger embedding/output matrix (for small models, the embedding table can be >30% of all parameters) and rarer tokens train on fewer examples. 32K (LLaMA-2) → 128K (LLaMA-3) reflects multilingual pressure winning that argument at scale.

Chapter 7: Tokenization Pathologies Every Inference Engineer Meets

The debugging bestiary — each of these will be a production ticket someday:

  • Trailing-space prompts: "The answer is " ends mid-pre-token; the model sees a distribution it rarely trained on. Symptom: oddly worse completions; fix: end prompts at token boundaries.
  • Token-boundary string operations: truncating a prompt by characters can split a token (or a multi-byte character); always truncate in token space, decode, re-check.
  • Streaming partial-token display: a generated token can be half a multi-byte character; decoders must buffer incomplete UTF-8 sequences (every streaming API bug report eventually traces here).
  • Numbers: BPE chunks digits inconsistently (1234 may be 12|34, 7,000 three tokens) — part of why arithmetic is hard for LLMs; newer models force single-digit tokenization.
  • The SolidGoldMagikarp class: tokens present in the vocab but nearly absent from training data have untrained embeddings — feeding them produces erratic behavior. Vocab and training data must be curated together.
  • Counting: "how many tokens is this?" depends on the exact tokenizer+version; budget enforcement with the wrong tokenizer over/under-counts by 20%+ across languages. Use the model's own tokenizer, always.

Lab Walkthrough Guidance

Lab 01 — Tokenization from Scratch (build BPE end-to-end):

  1. Implement byte-level base splitting + the pre-tokenization regex first; unit-test against known pre-token boundaries (" world" stays whole).
  2. Training loop: pair counting → merge → repeat. Verify on a tiny corpus by hand (5 merges you can compute on paper) before scaling.
  3. Encoding with merge-order priority (not longest-match) — test: your tokenizer's output must match tiktoken/HF reference token-for-token on a sample corpus; any divergence is the ordering bug until proven otherwise.
  4. Decoding + round-trip property test: decode(encode(s)) == s for arbitrary Unicode (emoji, CJK, ZWJ sequences) — this catches byte-proxy and UTF-8 buffering mistakes.
  5. Then the analytics: tokens-per-word across English/code/CJK samples — reproduce Chapter 5's tokenizer-tax observation with your own numbers.

Success Criteria

You are ready for Phase 02 when you can, from memory:

  1. Distinguish bytes / code points / graphemes with the é and emoji examples, and state what NFC/NFD change.
  2. Argue subword tokenization from both failure modes it resolves (char-level length, word-level OOV).
  3. Write the BPE training loop in pseudocode and state the encode-time merge-ordering rule and why greedy-longest is wrong.
  4. Explain Ġ, why world ≠ world, and the trailing-space pathology.
  5. Name the special-token security property and why chat templates are model contract.
  6. Quantify the tokenizer tax and its two production consequences (cost, context budget).

Interview Q&A

Q: Why do all modern LLMs use subword tokenization? It's the only point in the design space that bounds the vocabulary (so embedding tables are trainable), eliminates OOV (worst case decomposes to bytes), and keeps sequences ~4× shorter than character-level — which matters quadratically because of attention. Frequent strings get dedicated capacity; rare strings get compositional treatment.

Q: Your user reports the API "cut off their prompt mid-word." What happened? Truncation done in token space (correct) but displayed expectations in character space — or worse, truncation in character space splitting a multi-byte character/token. The fix is truncating by tokens with the model's own tokenizer, decoding the kept prefix, and surfacing the token count to the user. Bonus point: leading-space attachment means the visible "word" boundary and the token boundary genuinely differ.

Q: Why is the same text 3× more tokens in Thai than English on GPT-2's tokenizer? GPT-2's merges were learned on overwhelmingly English bytes; Thai gets few merges, so text decomposes to near-raw UTF-8 bytes — 3 bytes/char × ~1 token/byte. Consequences: 3× cost, 3× context consumption, and worse modeling (fewer chars per attention span). That's why multilingual models retrain larger vocabularies rather than reuse GPT-2's.

Q: What breaks if a user can type <|im_start|> and it encodes to the real special token? Role injection: the user's message can impersonate the system/assistant turn, overriding instructions — prompt injection at the tokenizer layer, below any application filtering. Correct tokenizers only emit special-token IDs from explicit API parameters, never from encoding user text; verifying that property is part of deploying any new tokenizer.

References

  • Sennrich et al., Neural Machine Translation of Rare Words with Subword Units (2016) — arXiv:1508.07909 — BPE's introduction to NLP
  • Radford et al., Language Models are Unsupervised Multitask Learners (GPT-2, 2019) — §2.2 for byte-level BPE
  • Kudo & Richardson, SentencePiece (2018) — arXiv:1808.06226; Kudo, Subword Regularization (2018) — arXiv:1804.10959 for Unigram
  • tiktoken — read the educational _educational.py BPE implementation
  • Karpathy, Let's build the GPT Tokenizer — youtube.com/watch?v=zduSFxRajkE — the single best companion to this lab
  • Unicode Standard Annex #15: Normalization Forms
  • Rumbelow & Watkins, SolidGoldMagikarp (2023) — the glitch-token investigation