Part I — Basics

Tokenization — BPE from raw bytes

Lesson 00 fixed the budget: a fixed pile of FLOPs, C ≈ 6·N·D, and a mandate to buy the most capable model it can. But a neural net does not consume text — it consumes a tensor of integers indexed into an embedding table. Before a single FLOP can be spent, raw bytes have to become a sequence of token ids, losslessly and compactly. This lesson builds that map from the ground up: byte-level BPE, the encoder that sits between the disk and the model. It is CS336 Assignment 1.

1 · Why not characters, why not words

The two encodings everyone reaches for first both break, and the way they break maps directly onto the budget.

Characters (or Unicode code points). Map every character to an id. The vocabulary is small and there is no out-of-vocabulary problem for a fixed script. The fatal cost is sequence length. A 1,000-word English document is ≈ 6,000 characters but only ≈ 1,500 subword tokens. Attention is O(T²) in the sequence length T, so a 4× longer sequence is roughly 16× the attention compute and memory, and the model must learn long-range structure across far more positions. You would burn most of the C = 6·N·D budget re-deriving that "t-h-e" is a word. Characters waste FLOPs on spelling.

Words. Map every whitespace-delimited word to an id. Sequences get short, but the vocabulary becomes unbounded: every typo, URL, hashtag, product code, and rare proper noun is a new "word." You cap the table at, say, 50,000 entries and everything past the cap collapses to a single <UNK> token — information destroyed, and the model is blind to exactly the long tail where most of language's surprise lives. Worse, the table does not transfer across languages or even across domains (medicine vs. code). Words waste the vocabulary on a tail it can never finish, and lose data at the cap.

We want the short sequences of word-level encoding and the losslessness of character-level. Subword tokenization gets both: common strings become single tokens (short sequences), rare strings decompose into smaller known pieces, and — the key move — the pieces bottom out at raw bytes, so the encoder can represent any string at all.

2 · UTF-8 bytes: a base vocabulary of exactly 256, and no OOV ever

Unicode assigns every character a code point — an integer like U+0041 ('A', 65) or U+4E16 ('世', 19,990) or U+1F30D ('🌍', 127,757). There are ~150,000 assigned code points and room for over a million, so a code-point vocabulary is huge and mostly empty. The trick is to not tokenize code points at all — tokenize their UTF-8 byte encoding.

UTF-8 writes each code point as 1–4 bytes: ASCII fits in 1 byte (so English is byte-for-character), most Latin/Greek/Cyrillic and common symbols take 2, most CJK takes 3, and emoji and rarer scripts take 4. A byte is just an integer in [0, 255]. So:

  "A"   U+0041   ->  [ 65 ]                       1 byte
  "é"   U+00E9   ->  [ 195, 169 ]                 2 bytes
  "世"  U+4E16   ->  [ 228, 184, 150 ]            3 bytes
  "🌍"  U+1F30D  ->  [ 240, 159, 140, 141 ]       4 bytes

This single decision pays off enormously. The base vocabulary is exactly 256 tokens — one per possible byte value — and it covers every string that can exist on a computer. No character, no language, no emoji, no binary blob can ever be out-of-vocabulary, because any input is, at worst, a sequence of its raw bytes. The <UNK> token simply does not need to exist. That is the structural advantage byte-level tokenizers (GPT-2 onward) have over the older word-piece tokenizers that fell back to <UNK>.

The price is that we have re-created the character problem in a worse form: a byte stream is even longer than a character stream (a CJK document is 3× its code-point length in bytes). So 256 byte-tokens are only the floor. We now learn merges on top of them to claw the sequence length back down.

3 · The BPE training algorithm — with a worked example

Byte-Pair Encoding (Sennrich et al., 2016, adapting a 1994 compression scheme) is greedy and almost embarrassingly simple. Starting from the 256 byte tokens, you repeat one move until the vocabulary hits the target size V:

Run it on a toy corpus — the string low low low low low lower lower newest newest (the classic BPE example), looking only inside words for clarity. Write each word as its letters; the counts are the per-word frequency. After step 2 the remaining pairs all tie at count 2, so we break ties by earliest first occurrence in the corpus (the same rule the widget below uses), which is why lower is completed before the newest pairs are touched.

After step 2, every one of the seven low occurrences (5 from "low", 2 inside "lower") is a single token. After step 4, the whole word lower is one token, shared by both "lower". The corpus that started as ~40 letter-tokens is now a dozen-ish chunky tokens, and the vocabulary learned the morphology of this corpus: the stem low, the word lower — without anyone labelling a single morpheme. That is the whole magic. Frequent strings get promoted to single tokens; the merge order records the priority.

Encoding new text replays the learned merges in order: split into bytes, then repeatedly apply the highest-priority merge whose pair is present, until none applies. Decoding is a pure table lookup — concatenate the byte expansion of each id — which is why BPE is exactly invertible (lossless). The compression ratio is the headline number: on English, mature BPE vocabularies land around ≈ 4 bytes per token (≈ 4 characters/token for ASCII). So T ≈ bytes / 4, and that ratio is what shrank the sequence by 4× versus raw bytes and bought back the attention cost.

# BPE training, sketched (counts over pre-tokenized "words")
vocab = {i: bytes([i]) for i in range(256)}      # 256 base byte tokens
merges = []                                       # ordered list (the tokenizer)
corpus = [list(word_bytes) for word_bytes in pretokenize(text)]

while len(vocab) < V:
    pairs = Counter()
    for word in corpus:
        for a, b in zip(word, word[1:]):
            pairs[(a, b)] += freq[word]           # weight by word frequency
    if not pairs: break
    best = max(pairs, key=pairs.get)              # most frequent adjacent pair
    new_id = len(vocab)
    vocab[new_id] = vocab[best[0]] + vocab[best[1]]
    merges.append(best)
    corpus = [merge_pair(word, best, new_id) for word in corpus]

4 · Pre-tokenization: don't let merges cross word boundaries

There is a subtlety the toy example hid by saying "inside words." If you run BPE on the raw byte stream with spaces included, the most frequent pair early on is often (space, t) or (e, space), and you start minting tokens that straddle word boundaries — "e the", ". The" — which is wasteful (the same word gets many spacing-dependent variants) and makes the vocabulary depend on punctuation accidents.

The fix, introduced with GPT-2, is pre-tokenization: before BPE runs, split the text with a regex into coarse chunks (roughly: words, runs of whitespace, numbers, punctuation), and only ever count and merge pairs within a chunk — never across chunk boundaries. GPT-2's regex (slightly paraphrased) is:

's|'t|'re|'ve|'m|'ll|'d| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+

Read it left to right: common English contractions get their own chunk; then "an optional leading space plus a run of letters" (so " the" is one chunk, keeping the leading space attached to the word — which is why GPT-2 tokens print the leading space as "Ġthe"); then runs of digits; then runs of symbols; then runs of whitespace. Merges happen only inside these chunks. This keeps the learned vocabulary about language units, not about where spaces happened to land, and it bounds how long any single token can get. The leading-space convention also means the tokenizer never has to choose between "the" and " the" as separate unrelated tokens for every word — the space is part of the chunk.

5 · The vocab-size trade-off: V is a budget knob

Target vocabulary size V is the one real hyperparameter, and it is a genuine trade-off — bigger is not simply better. Three quantities move with it.

Put numbers on the parameter cost. With model dimension d = 4,096, the input embedding is V·d parameters; the (untied) output head is another V·d. Going from GPT-2's V = 50,257 to a modern V = 128,000 adds about (128,000 − 50,257) × 4,096 ≈ 0.32 billion parameters per embedding matrix — real budget, taken straight out of the layers that do reasoning. The flip side: the larger vocab might cut the token count of a given corpus by ~15–20%, which means the same D bytes train in fewer steps and a fixed context window holds more text.

That tension is why the field has drifted upward over time but not to the moon. GPT-2 shipped V = 50,257 (50,000 BPE merges + 256 base bytes + 1 end-of-text token). Modern models sit in the 100k–256k range — GPT-4 / Llama-3 use ≈ 100k–128k, and some multilingual models push to 256k specifically to keep non-English compression from collapsing (§6). The sweet spot rises with model size (a bigger d amortizes the V·d cost) and with how multilingual the data is. The widget below lets you watch sequence length fall as you mint more merges.

6 · Pathologies — everything weird about LLMs that is really a tokenizer bug

Because the tokenizer is a frozen, statistics-driven layer the model cannot see around, its quirks leak into model behavior in ways that look like reasoning failures but are not.

And the famous one: "how many r's in strawberry?" The model often answers "2." Not because it cannot count — because it never sees the letters. "strawberry" arrives as a couple of subword tokens (something like " straw" + "berry"), each an opaque id. The character-level fact "there are three r's" was destroyed at the tokenizer before the model ever ran, exactly as the <UNK> cap destroyed information in §1 — only here the loss is silent. Any task that needs to operate below the token (counting letters, reversing strings, character-level edits) is fighting the encoder. It is a tokenization artifact, full stop, and it is the cleanest demonstration that the choices in this lesson propagate all the way to user-visible behavior.

7 · Interactive: BPE merge visualizer

Type text with repeated substrings, then press step merge to run one round of BPE: the widget finds the most frequent adjacent pair in the current segmentation, mints it as a new token, and re-segments. Watch the token count fall and the vocabulary rise with each merge — and watch bytes/token (the compression ratio) climb toward the ≈ 4 you would see on real English. This is the §3 algorithm in miniature; the only simplification is that it operates on characters rather than UTF-8 bytes so the chips stay readable.

Failure modes & checklist

Checkpoint

Where this points next

We now have a clean, lossless, frozen map from text to a sequence of integer ids x₁…x_T, with T ≈ bytes / 4 and a vocabulary V chosen against the budget. That is the input contract for everything downstream — and it immediately exposes the next wall. A sequence of ids is inert; the entire point (lesson 0's mandate) is to model p(x_t | x_<t) and lower its negative log-likelihood. We need a function that, in one parallel, differentiable pass, predicts the next id at every position at once — fast enough that the 6·N·D budget actually buys a model. That function is the decoder-only Transformer, built shape by shape in 02 · The Transformer, from scratch.

Interview prompts

• Why byte-level BPE instead of a word or character vocabulary? (§1–2 — characters make sequences 4–6× longer and attention is O(T²); words need a hard cap that forces lossy <UNK>. BPE over 256 base bytes is lossless, has no OOV, and gives a tunable compression ratio.)
• How is BPE trained, and what exactly is "the tokenizer" you ship? (§3 — repeatedly count adjacent pairs, merge the most frequent into a new token, repeat to size V; the artifact is the ordered list of merges plus the byte→id table. Encoding replays merges in order; decoding is a table lookup, so it is lossless.)
• Why does GPT-2 pre-tokenize with a regex before BPE? (§4 — to stop merges crossing word/space/punctuation boundaries, which would mint redundant spacing-dependent tokens; merges happen only within chunks, and the leading space stays attached to the word.)
• Walk through the trade-offs of raising the vocabulary size. (§5 — bigger V → shorter sequences (cheaper O(T²), more knowledge/token) but larger V·d embedding+softmax params and rarer, under-trained tokens. Sweet spot rises with d and with how multilingual the data is; 50k → 256k.)
• Why can't an LLM reliably count the r's in "strawberry"? (§6 — the word is a couple of opaque subword ids; the character-level information was destroyed by the tokenizer before the model ran. It is an encoding artifact, not a reasoning failure.)
• What is a glitch token and where does it come from? (§6, §5 — a string frequent in the BPE-training corpus but near-absent in the model-training corpus (e.g. " SolidGoldMagikarp"); its embedding row gets almost no gradient, so the model behaves erratically on it. A direct symptom of rare tokens at large V.)
• Roughly what compression ratio should you expect, and why does it matter to the budget? (§3, §5 — ≈ 4 bytes/token on English, so T ≈ bytes/4; the ratio sets how many tokens D bytes become, directly scaling training steps and attention cost. It degrades on non-English text, which is why multilingual models grow V.)