Subword Tokenization: Byte-Pair Encoding

LLMs

Chapter 2 · Subword Tokenization: Byte-Pair Encoding

nlp1-9 named a real, honest limitation of pretrained embeddings: a fixed vocabulary, with genuine gaps. This chapter shows how LLMs close that gap for good — not by building a bigger vocabulary, but by changing what the vocabulary is made of.

A Genuinely Different Philosophy From nlp1-1's Own Pipeline

nlp1-1's preprocessing pipeline split text into whole words, stripped stopwords, and reduced words to their lemma — a linguistically-informed process, built around what a word "means." Byte-Pair Encoding (BPE) abandons that framing entirely. It doesn't ask what a word means — it asks what sequences of characters appear together often enough, across a massive corpus, to be worth their own token. No stopword removal, no lemmatization: raw frequency statistics decide what counts as a unit.

The BPE Algorithm

BPE started life as a data-compression algorithm and was repurposed for tokenization. The core loop:

Start with a vocabulary of individual characters (or bytes).
Count every adjacent pair of symbols across the training corpus.
Merge the single most frequent pair into one new symbol; add it to the vocabulary.
Repeat, thousands of times, until the vocabulary reaches a target size.

# simplified BPE training loop
vocab = set(all_characters_in_corpus)
corpus = split_into_characters(training_text)

for step in range(num_merges):
    pairs = count_adjacent_pairs(corpus)
    best_pair = max(pairs, key=pairs.get)     # the single most frequent pair
    vocab.add(merge(best_pair))               # e.g. ("t", "ion") -> "tion"
    corpus = apply_merge(corpus, best_pair)    # replace every occurrence

Common fragments like "tion", "ing", or "un" earn their own token early, since they occur constantly across a large corpus. Rare words never get merged into single tokens at all — they stay broken into smaller, more common pieces.

A Worked Example

Input word	Likely subword tokens
`tokenization`	`token` + `ization`
`unbelievability`	`un` + `believ` + `ability`
`zzyxplorb` (invented, never seen in training)	`zz` + `y` + `x` + `plor` + `b` — falls back toward individual characters

Resolving nlp1-9's Own Gap, For Good

Not a bigger table — a different kind of table

nlp1-9's own GloVe vectors were a fixed table of whole words: a word either has an entry or it doesn't, and a missing entry means no meaningful vector at all. BPE's vocabulary reaches all the way down to individual bytes as its ultimate fallback — so literally any string, including gibberish nobody has ever typed before, can always be decomposed into some sequence of known vocabulary pieces. Nothing is ever truly out of vocabulary, because the smallest unit in the vocabulary is small enough to represent anything.

Byte-Level BPE

GPT-2 and its successors operate on raw UTF-8 bytes rather than Unicode characters — a further guarantee. Since every possible string, in every script, emoji included, is representable as a sequence of bytes, byte-level BPE never encounters a character it fundamentally cannot represent, even before any merges are learned. This is what makes the "no true out-of-vocabulary input" guarantee absolute rather than merely "very good in practice."

Vocabulary Size — A Real Trade-Off

Vocabulary size	Consequence
Too small	Text breaks into long sequences of tiny pieces — more tokens per sentence, more compute per input
Too large	Many tokens become rare and poorly trained, with diminishing returns on vocabulary growth

Real models settle in the tens of thousands to roughly one hundred thousand tokens — large enough that common words and word-fragments get their own single token, small enough that the vocabulary itself stays learnable.

An Honest Limitation: Tokens Aren't Meaning Units

A real, well-known practical quirk, explained mechanically

Unlike nlp1-1's own words or nlp1-5's own word embeddings, a subword token like "ing" or "plor" carries no meaning of its own — it's a compression-driven engineering choice, not a linguistic one. This is the actual, mechanical reason LLMs are famously unreliable at tasks like counting letters within a word: the model frequently never "sees" the word as individual characters at all — it sees one or two opaque subword chunks, with no direct access to what letters compose them.

Hands-On Exercises

Exercise 1

Explain, using this chapter's own BPE training loop, why common fragments like "ing" or "tion" become their own tokens while rare words stay broken into smaller pieces.

📄 View solution

Exercise 2

Explain specifically why BPE's own byte-level fallback resolves nlp1-9's out-of-vocabulary problem "for good" rather than just reducing how often it happens, contrasting BPE's vocabulary structure directly with GloVe's.

📄 View solution

Exercise 3

Explain the mechanical reason LLMs are often unreliable at counting letters within a word, using this chapter's own explanation of what a subword token actually represents.

📄 View solution

Chapter 2 Quick Reference

BPE — repeatedly merge the most frequent adjacent symbol pair, building a vocabulary from the bottom up by frequency, not linguistics
A genuinely different philosophy from nlp1-1's own word-level, linguistically-informed pipeline — no stopword removal, no lemmatization
The fallback: vocabulary reaches down to individual bytes, so any string can always be represented — resolving nlp1-9's OOV gap for good, not just reducing it
Byte-level BPE (GPT-2 onward) — operates on raw UTF-8 bytes, making the "no true OOV" guarantee absolute
Vocabulary size is a real trade-off between sequence length and token rarity — real models use tens of thousands to ~100k tokens
Honest limitation: subword tokens carry no inherent meaning, which is the real mechanical reason behind LLMs' own letter-counting unreliability
Next chapter: Embeddings & Positional Encoding at Scale