Tokenizer (Byte Pair Encoding)

Before any transformer can read a sentence, somebody has to chop the sentence into numbered chunks. That chopping is tokenization, and it is the quietly most important problem in NLP. Two obvious ways to do it both fail. Give every character its own token and a sentence turns into a parade — your sequence length balloons and the model burns attention on the letters in “the.” Give every word its own token and the first time someone types pseudohypoparathyroidism the model hits <UNK> and shrugs.

BPE is what sits in the middle, and the shape of it is almost cartoonishly simple. Think of it as the greedy compressor that grows its own alphabet. Start with just letters — the alphabet you were born with. Then scan the corpus, spot the most common pair of neighbors (t-h is everywhere), and glue that pair into a single new symbol. Now your alphabet is one symbol longer. Do that again. And again. Do it 50,000 times and you have a dictionary where the most common English chunks are each one token, rarer stuff decomposes into a handful of pieces, and nothing is ever truly unknown.

That is Byte Pair Encoding — the tokenizer GPT-2, GPT-3, GPT-4, Llama, and essentially every modern LLM runs on. It started life as Philip Gage's 1994 data-compression trick. Sennrich dusted it off for machine translation in 2015. Now it sits in front of every prompt you have ever typed to an LLM. This lesson builds one from scratch: train it on a tiny corpus, watch the merges happen, encode a sentence with the resulting merge list, then see why the GPT-2 authors swapped characters for bytes.

Back to the compressor image. We start with an alphabet — the smallest unit we are willing to see. For now, call it letters; in a minute we will swap letters for bytes. Every word in the corpus gets split down to that alphabet, so lower is just five atoms sitting in a row: l, o, w,e, r. Now count every adjacent pair across the whole corpus. Pick the pair that shows up most often. Glue those two atoms into a single new symbol — that new symbol joins the alphabet. Rewrite the corpus with the glue applied. Then do the whole thing again. And again.

That is the entire training algorithm. Count, pick, glue, repeat.

No gradients. No neural net. No loss function. Just counting pairs and gluing the winner. The output is a merge list — an ordered sequence of rewrite rules, one per step. The merge list is the tokenizer. To encode new text you replay the merges in the same order they were learned. To decode you run them in reverse. Everything else the libraries wrap around this is packaging.

Step through the training loop on a five-sentence corpus. Each click advances one merge. Watch the pair-frequency table, see the winning pair get highlighted, and notice the alphabet grow by exactly one new token per step.

The first few merges always feel boringly predictable, and that is the point. Step 1 almost always glues (t, h). Step 2 glues (h, e). Step 3 the compressor looks at the th it just minted, spots (th, e) everywhere, and glues those — and congratulations, the is now one token. Keep cranking. Frequent digrams like (e, r), (i, n), and (i, ng) light up next. After a few hundred merges the alphabet contains every common English word as a single symbol, and the remaining budget gets spent on suffixes (-tion, -ing), roots (pseudo), and the long tail of subwords you need to assemble anything stranger.

This is what lets a word like pseudohypoparathyroidism survive without any special handling. It never earned a single token — it was not frequent enough to win a merge round. But pseudo, hypo, para,thyroid, and ism each might have. The word decomposes into four or five familiar pieces. The model reads it as a sequence of known fragments, not a single alien blob. No <UNK>, no panic.

It is reasonable, at this point, to ask the obvious question: why not just use whole words as tokens and skip the merge dance entirely? Because of the math below. A word-level vocabulary has to memorize every inflection, every proper noun, every typo, every new word the internet coins next Tuesday. You either bloat the dictionary into the millions or you fall back to <UNK> the moment a user types something unexpected. BPE splits the difference — common words do become single tokens once the compressor merges their letters enough times, but the dictionary stays capped because rare words borrow pieces instead of demanding their own slot. Measure it.

Read that table carefully. Every modern LLM is charged per token. Every context window is counted in tokens. When a Thai user and an English user type the same paragraph, the Thai user pays five times the tokens to say the same thing, gets five times less context, and runs up five times the latency. That asymmetry is not a bug in the math — it is a direct consequence of training the compressor on a corpus dominated by English web text. The frequent pairs that won merge rounds were English pairs. Everyone else pays the tax.

Now try it live. Type a sentence, watch it decompose into byte-pair tokens with the merges applied in the exact order they were learned. Notice how leading spaces travel with the word that follows them (a GPT-2 convention — more on that below) and how unusual words fragment into smaller pieces while common words survive as a single token. The merge list you trained is the dictionary; this widget is it running in reverse on your input.

Two things are worth staring at. First, "hello" and " hello" (with a leading space) are different tokens. Not a bug — the GPT-2 tokenizer deliberately binds the leading space to the token because it makes sentence-level encoding cheaper and decoding lossless. It means the word at position 0 in a sentence and the same word mid-sentence get different IDs. Get used to it.

Second, capitalization matters. "The", "the", and " the" are three separate tokens in the dictionary. They share zero parameters in the embeddings table. The model has to learn that they mean roughly the same thing — and it does, but only because it sees them in similar contexts a million times.

GPT-2 introduced one small, brilliant change to the Sennrich recipe: don't start the alphabet from characters, start it from bytes. A character-level compressor has to decide what a character even is. Does é count as one symbol or two (e plus a combining acute accent)? Which Unicode normalization form? If the user pastes a malformed UTF-8 sequence, do you crash? What about 🦀, or 中, or the weird zero-width joiner some emoji smuggle in?

A byte-level BPE sidesteps every one of those questions. The starting alphabet is just the 256 possible byte values. Every possible input — every Unicode character, every emoji, every binary blob — encodes to some sequence of bytes, which decomposes trivially into those 256 atoms. The merges then glue common byte sequences into larger tokens, and now the compressor can chew on anything — source code, Chinese, Python, a PDF — with the same 50K-entry dictionary, and decoding is a perfect inverse. No loss. No <UNK>. Ever.

Three implementations, each shorter than the last. First, pure Python on a tiny corpus so you can watch every pair, every merge, every rewrite. Second, a numpy-free encoder that applies a trained merge list to a new word. Third, the Hugging Face tokenizers library — what you would actually ship.

Twenty lines, the whole compressor. You can read the greedy logic off the page: the inner loop counts every adjacent pair, the most_common(1) call picks the winner, the glue step rewrites the corpus so the newly-minted token participates in the next round of counting. The first winning pair was (l, o). Five merges later, low and new are single tokens while er and est are reusable suffixes. A 300-entry dictionary would turn most of common English into single-token words. A 50K dictionary covers essentially all of it plus the interesting corners.

In production nobody writes the encoder by hand. You use a library that handles byte-level encoding, pre-tokenization (splitting on whitespace and punctuation), regex for the GPT-style space-handling, and a fast Rust implementation of the merge loop. That's Hugging Face tokenizers, or OpenAI's tiktoken. Same greedy compressor underneath — just with the inner loop rewritten in a language that does not stop to breathe. Here's what training looks like from the outside.

What to carry forward. BPE is a greedy compressor that grows its own alphabet. It starts from bare atoms — bytes, in practice — spots the most common pair, glues the pair into a new symbol, and repeats until the dictionary hits the size you asked for. That solves out-of-vocabulary by letting rare words borrow common pieces, caps vocabulary bloat by construction, and — in the byte variant — handles every Unicode corner the same way it handles ASCII. The merge list is the tokenizer: train once, apply forever. And the compression ratio is not uniform across languages, which is a genuine source of real-world model bias that most benchmarks quietly ignore.

Next up — Build Vocabulary. You have seen the compressor run on five words. Now point it at a real corpus, ship it, and watch what a 50K-entry dictionary actually contains. That is build-vocabulary — training a BPE vocab on real text, spelunking the result, and making sure the merge list you save matches the one you load.