byte pair encoding · a 137 character corpus
Every sentence you send a language model is cut into pieces and swapped for integers before a single calculation happens. This page builds that cutter from scratch, out of a corpus small enough to check by hand.
Type the cat sat on the mat into a chat box. You are looking at twenty two characters. The model is not.
By the time anything reaches the part of the system that does arithmetic, that sentence has become a short list of whole numbers. Something like six of them. Not letters, not words, not strings. Integers.
The pieces that get numbered are called tokens, and the number each one gets is its token ID. Every piece of text you have ever sent a model went through this swap first.
A printer's type case: a shallow drawer of compartments, each holding one metal sort. To set a line you do not write it, you fetch compartment 14, then 3, then 91. The compartment number is the only thing the press understands. Which pieces get their own compartment is a decision somebody made in advance, and it is the whole subject of this page.
So the real question is not whether text gets numbered. It is where the cuts fall. Cut in one place and the list is short but the drawer needs millions of compartments. Cut in another and the drawer is tiny but the list runs forever.
Start with the two obvious places to cut, because both of them fail in a way worth feeling.
Answer fast, gut reaction: if you had to give every piece of English its own number, what would you number? Individual letters, or whole words?
Both answers are defensible and both are wrong, in opposite directions. The drawer of compartments is called the vocabulary, and the two choices trade its size against the length of the list.
Letters give you a drawer of about thirty compartments and a list twenty two items long. Nothing is ever missing, because every English sentence is made of the same few letters. But the model now has to learn that c, a, t in that order means a small animal, and it has to relearn that from scratch for every word.
Words flip it. The list drops to six. The drawer needs a compartment for every word in the language, and English has a few hundred thousand of them before you count names, typos and slang. Worse, the day someone types a word that was not in your drawer, you have nothing to give them. That is an unknown word, and it is not a rare edge case: new words appear constantly.
Two ways to stock a hardware shop. Sell only raw steel and every customer can build anything, but they leave with a bar and a week of filing ahead of them. Sell only finished machines and one customer walks out happy while the next asks for something you have never made. What you want is a shelf of common parts.
The word walking shows the whole argument in seven letters. As letters it is seven separate things with no visible relationship to walked. As a word it is one thing with no visible relationship to walked either. Both cuts hide the same fact.
You heard walk four times. Three suffixes rode on top of it. Nobody taught you to hear that seam, and no dictionary of whole words would show it to you, because in a dictionary those are four unrelated entries.
A piece that is bigger than a letter and smaller than a word is called a subword. Give walk its own compartment and ing its own compartment, and suddenly walking costs two items instead of seven, while the drawer grew by two rather than by one entry per word form.
Lego against a model kit. A kit builds one castle beautifully and builds nothing else. Loose bricks build anything but you are placing them one at a time. Subwords are pre-assembled sections: a wall, a turret, a gate. New castle, same sections, and if a shape is genuinely new you can still fall back to single bricks.
Which leaves one question, and it is the hard one. Who decides that walk and ing deserve compartments and alki does not?
Not a linguist. Nobody sat down with a grammar of English and enumerated its suffixes. The pieces are found by counting, and the counting procedure is simple enough to run in your head.
Here is the corpus this page trains on. Seven words, repeated the number of times shown, 137 characters in total. Small enough that you can check every number below by hand.
Everything starts as single letters. Now look at every adjacent pair in the whole corpus and count how often each one occurs, remembering that a word repeated five times contributes its pairs five times. That number is the pair count.
Try the gap between a and l. It appears in walk, walked, walking, talked and talking, which with their repeats comes to nineteen. No other pair beats it.
So al wins. Glue it together everywhere it occurs, and treat the result as a single piece from now on. The corpus just got shorter and the drawer just gained one compartment.
A typesetter who notices she keeps reaching for t and h together, hundreds of times an hour. So she casts a single piece of metal with th on it and drops it in the case. She did not consult a grammar, she watched her own hands. That is the entire selection rule: whatever you reach for most, make it one piece.
One merge is not interesting. What makes this work is that you do it again on the result, and again, and the pairs that win the later rounds are made of pieces that won the earlier ones.
The loop is four lines long: count the pairs, take the most frequent, fuse it everywhere, write down what you did. Each fusion is a merge, and the record of it is a merge rule. Scroll through the first six.
Fourteen distinct letters, 137 tokens across the corpus. No piece is bigger than one character, and nothing yet connects walk to walked.
The first merge is not a word or a syllable. It is the fragment shared by walk and talk, and it wins on raw frequency alone.
The second round counts pairs again, and now al plus k is available because al exists. Two rounds later the whole stem walk is one piece.
Round four fuses e and d, nine occurrences. Nobody told this procedure that English marks the past tense with ed. It counted.
Rounds five and six do the same thing to the present participle. The suffix arrives as a single piece, built from a piece that arrived one round earlier.
The corpus has shrunk from 137 pieces to 59, and the drawer holds twenty compartments instead of fourteen. Walk, talk, ed and ing are now things.
Water finding a channel. No engineer chose where the stream runs, but repeat the flow enough times and a groove appears exactly where the most water passed. The merge rules are that groove, and the corpus is the water. Change the corpus and the grooves land somewhere else, which is why a tokenizer trained on English does badly on code.
Notice what did not happen. There was no dictionary, no list of suffixes, no rule saying past tense is special. The procedure discovered ed and ing because they are genuinely frequent, and frequency in real text is not random.
Six merges was an arbitrary stopping point. Stopping is the one decision left, and it turns out to be the only dial anybody actually turns.
The loop will happily run forever. Every extra turn adds one compartment to the drawer and removes some pieces from the list. When you stop, the number of compartments you have is the vocabulary size, and it is very nearly the only tokenizer setting anyone chooses.
Drag it. Everything else about the corpus is held still.
The two numbers move in opposite directions and neither is free. A big vocabulary means short sequences, which is what you want, because the work a model does grows with the square of sequence length. It also means a bigger table of learned vectors to store, and every rare compartment gets seen less often during training, so the model learns it worse.
Buying kitchen jars. Few jars means everything is loose in bags and finding the cumin takes a while. A jar per ingredient means instant cumin and a wall of jars, most of them touched twice a year and taking up shelf you needed. The right number is neither extreme, and it depends entirely on what you cook.
Now find merge eight on the slider. It fuses walk with ed, so walked becomes a single indivisible piece. Sequence length drops, which looks like a win. But the model can no longer see that walked and walking share a stem, because at that vocabulary size they no longer do share anything visible. The information was there at merge seven and gone at merge eight.
Every merge buys you a shorter sequence and sells a little bit of structure.
Real tokenizers stop somewhere between about fifty thousand and two hundred thousand merges, which is a judgement call, not a derivation. And once you have stopped, the merge rules are frozen. Which raises the practical question: what happens to a word the corpus never contained?
The corpus never contained walkable. The tokenizer has no compartment for it and never will. It still handles it, and the way it does so is the reason this whole approach won.
Split the new word into letters. Then walk the merge rules from first to last, and wherever a rule matches, apply it. That replay is called encoding, and it is what runs every time you press send.
walkable comes out as walk + a + b + l + e. Five pieces. The stem was recognised, the ending was not, so the ending fell back to letters. Nothing was dropped and nothing was marked unknown.
Setting a word in metal type with the case you already own. You reach for the walk sort because you cast one last year, then you spell out the rest letter by letter because nobody ever cast able. The line still gets set. It just takes five pieces instead of two.
That fallback is why this survives contact with real input. Names, typos, chemical formulas, a language the corpus barely contained: all of them get pieced together from whatever fragments exist, down to single characters in the worst case. There is no failure mode where the tokenizer refuses.
Try stalking in the figure and watch something less comfortable happen. Now the pieces are numbered, and it is worth being precise about what the model does with those numbers, because it is not what most people assume.
Token 4,102 is not larger than token 17. It is not more positive, more recent, or more anything. The number is a row index, nothing else.
Behind it sits a table with one row per compartment. Each row is a list of numbers that the model learned during training, and that row is the embedding row for that token. The ID's only job is to say which row to fetch.
A cloakroom ticket. Number 62 tells you nothing about the coat, and ticket 63 is not a slightly larger coat. The ticket is worthless without the rail it points at, and everything you care about is hanging on the rail. Tokenization hands out tickets. Training is what fills the rail.
Two consequences follow, and both surprise people. The first is that changing the tokenizer invalidates the model. Swap in a cutter that assigns different IDs and every row is now the wrong row, so the model is not degraded, it is scrambled.
The second is billing and limits. A context window measured in tokens is a limit on pieces, not characters or words. The same paragraph can cost noticeably different amounts depending on which cutter is running, and the difference is not evenly distributed across the world's languages.
Which is where the honest part of this starts.
Ask a model how many r's are in strawberry and it has a decent chance of getting it wrong. This is usually reported as a reasoning failure. It is mostly a tokenization failure, and once you have built the cutter you can see exactly why.
The model was never given the letters. It was given two or three pieces, each an opaque address, and asked a question about characters it cannot see inside those pieces. Counting the letters in a token is like counting the buttons on a coat from the cloakroom ticket.
The leading space one catches nearly everybody. In most modern tokenizers, walk at the start of a line and walk after a space are different compartments with different IDs and separately learned rows. Trailing whitespace in a prompt can therefore change the split of the word that follows it.
Digits are worse. A long number gets carved into chunks by frequency, so 1,024 and 1,025 may not even share a boundary. Arithmetic asks the model to line up place values it was handed in ragged pieces.
A shop that stocks parts for the cars people in one town actually drive. Bring in a common local model and everything is in stock. Bring in something from elsewhere and the mechanic builds it from raw stock, slowly and expensively. The shop is not biased against your car, it is stocked from a sample that did not contain many of them.
That last one is a real cost, not a curiosity. Because merges are learned from a corpus that is mostly English, text in scripts like Devanagari or Thai commonly needs several times more tokens to say the same thing. More tokens means more of the context window spent, more compute per sentence, and a larger bill for the same paragraph.
None of this is fixed by a smarter model. It is decided before the model runs, by a counting procedure over somebody else's corpus, frozen months earlier.
A tokenizer is a frozen record of what was frequent in one pile of text, and every prompt you write is priced and cut by it.
press s for the deeper cuts
The procedure was published in 1994 as a data compression method by Philip Gage, working on bytes rather than characters. Sennrich, Haddow and Birch repurposed it for machine translation in 2016. The name stuck even though the compression use case did not, and modern implementations really do run over bytes, which is how they handle any Unicode input without an unknown token.
If the tokenizer works over raw bytes, nothing can be truly unseen, because every possible byte value is in the base vocabulary. An unusual emoji simply costs several tokens, one per byte of its encoding, rather than failing. This is the main practical reason byte level BPE displaced character level.
No. Taking the most frequent pair at each step is a greedy heuristic and there is no guarantee it produces the shortest possible encoding for a given vocabulary size. It is used because it is cheap, deterministic and good enough. WordPiece, used by BERT, picks the pair that most increases corpus likelihood instead, which often gives slightly different splits.
Because later rules are built from the products of earlier ones. Rule six fuses in and g, which only exists if rule five already made in. Apply them out of order and the later rules find nothing to match. This is also why the merge list, not just the vocabulary, has to ship with the model.
Production tokenizers do not run BPE over an entire document. They first split on a regular expression that isolates whitespace, punctuation and digit runs, then run merges inside each fragment. This is what prevents merges from spanning word boundaries and producing a single token for the cat. It is also where the leading space behaviour comes from.
Some do. The tradeoff is sequence length: byte level sequences are roughly four to five times longer than subword sequences for English, and attention cost grows quadratically with length. Recent work on byte level and patch based models tries to recover that cost with a learned grouping layer, which is the same problem again in a different place.