🔤 Tokenization: Byte-Pair Encoding
Tokenization: Byte-Pair Encoding by Hand
Every transformer walkthrough in this section — [[bert-on-eeg]], [[autoregressive-transformer-encoder-decoder]], [[kimi-k3]], [[deepseek-v4]] — begins with a sequence of token IDs already in hand. This page is the step before that: how text becomes those integers.
It is not a detail. Tokenization decides how long your sequences are (and attention cost is quadratic or worse in that length), which words the model can never spell, why it struggles to count letters, and why the same sentence costs three times as much in one language as another.
The dominant method is Byte-Pair Encoding. It was a data compression algorithm from 1994, repurposed for NLP in 2015, and it is simple enough to run completely by hand — which is what this page does, merge by merge.
1. The problem BPE solves
Two obvious approaches, both bad:
One token per word. The vocabulary is unbounded — every name, typo, compound
and inflection is a new entry. Anything unseen becomes <UNK> and the model is
blind to it.
One token per character. The vocabulary is tiny and nothing is ever unknown,
but sequences become very long, and the model must rediscover that t-h-e is a
unit every single time.
BPE interpolates. Start from characters, then repeatedly merge the most frequent adjacent pair into a new symbol. Common words end up as single tokens; rare words survive as a handful of pieces; nothing is ever out-of-vocabulary. You choose where on that spectrum to sit by choosing how many merges to perform.
Display helpers ready: banner, step, check, expand, show_matrix, show_matmul, show_elementwise.
==============================================================================
THE TWO EXTREMES, ON A SMALL CORPUS
==============================================================================
corpus: 23 words, 10 distinct
"the cat sat on the mat the cat ate the rat a cat and a rat sat on a mat the rats ate"
Word-level
==============================================================================
vocabulary size : 10
sequence length : 23 tokens
vocab: ['a', 'and', 'ate', 'cat', 'mat', 'on', 'rat', 'rats', 'sat', 'the']
'rats' seen? True. But 'cats' would be <UNK>: True
Character-level
==============================================================================
vocabulary size : 12
sequence length : 84 tokens (3.7x longer)
nothing is ever unknown, but 'the' is 3 tokens every time it appears
and it appears 5 times = 15 tokens spent on one word.
The cost of sequence length in a transformer
==============================================================================
attention is O(n^2) in the sequence length, so:
representation n n^2
----------------------------------
word-level 23 529
char-level 84 7,056
----------------------------------
13.3x more attention work for the same text.
This is why tokenization is an efficiency decision, not just a
preprocessing one.
2. Training BPE, merge by merge
The training algorithm:
- Split every word into characters. Append an end-of-word marker
_so the algorithm can tellestat the end of a word fromestin the middle. - Count every adjacent symbol pair across the corpus, weighted by word frequency.
- Merge the most frequent pair into a single new symbol.
- Record the merge and repeat.
The merge list, in order, is the trained tokenizer. There is nothing else to it — no neural network, no probabilities. Applying it to new text means replaying those merges in the same order.
==============================================================================
TRAINING BPE, ONE MERGE AT A TIME
==============================================================================
Starting point: every word spelled out
==============================================================================
5 x t h e _
3 x c a t _
3 x a _
2 x s a t _
2 x o n _
2 x m a t _
2 x a t e _
2 x r a t _
1 x a n d _
1 x r a t s _
Merge 1
==============================================================================
most frequent adjacent pairs:
( 'a', 't') : 12 <- merging this
( 't', '_') : 9
( 'e', '_') : 7
new symbol: 'at'
words containing it now: ['c at _', 's at _', 'm at _', 'at e _', 'r at _']
Merge 2
==============================================================================
most frequent adjacent pairs:
( 'at', '_') : 9 <- merging this
( 'e', '_') : 7
( 't', 'h') : 5
new symbol: 'at_'
words containing it now: ['c at_', 's at_', 'm at_', 'r at_']
Merge 3
==============================================================================
most frequent adjacent pairs:
( 'e', '_') : 7 <- merging this
( 't', 'h') : 5
( 'h', 'e') : 5
new symbol: 'e_'
words containing it now: ['t h e_', 'at e_']
Merge 4
==============================================================================
most frequent adjacent pairs:
( 't', 'h') : 5 <- merging this
( 'h', 'e_') : 5
( 'c', 'at_') : 3
new symbol: 'th'
words containing it now: ['th e_']
Merge 5
==============================================================================
most frequent adjacent pairs:
( 'th', 'e_') : 5 <- merging this
( 'c', 'at_') : 3
( 'a', '_') : 3
new symbol: 'the_'
words containing it now: ['the_']
Merge 6
==============================================================================
most frequent adjacent pairs:
( 'c', 'at_') : 3 <- merging this
( 'a', '_') : 3
( 's', 'at_') : 2
new symbol: 'cat_'
words containing it now: ['cat_']
Merge 7
==============================================================================
most frequent adjacent pairs:
( 'a', '_') : 3 <- merging this
( 's', 'at_') : 2
( 'o', 'n') : 2
new symbol: 'a_'
words containing it now: ['a_']
Merge 8
==============================================================================
most frequent adjacent pairs:
( 's', 'at_') : 2 <- merging this
( 'o', 'n') : 2
( 'n', '_') : 2
new symbol: 'sat_'
words containing it now: ['sat_']
The trained tokenizer IS this ordered list
==============================================================================
1. 'a' + 't' -> 'at'
2. 'at' + '_' -> 'at_'
3. 'e' + '_' -> 'e_'
4. 't' + 'h' -> 'th'
5. 'th' + 'e_' -> 'the_'
6. 'c' + 'at_' -> 'cat_'
7. 'a' + '_' -> 'a_'
8. 's' + 'at_' -> 'sat_'
Final segmentation of each word
==============================================================================
5 x ['the_']
3 x ['cat_']
3 x ['a_']
2 x ['sat_']
2 x ['o', 'n', '_']
2 x ['m', 'at_']
2 x ['at', 'e_']
2 x ['r', 'at_']
1 x ['a', 'n', 'd', '_']
1 x ['r', 'at', 's', '_']
3. Applying the tokenizer to new text
Encoding replays the merges in training order. Order matters: a later merge may depend on a symbol that an earlier one created, so applying them out of order gives a different — and wrong — segmentation.
The important behaviour is what happens to a word the tokenizer has never seen.
It does not fail. It falls back to whatever pieces it does know, which is why BPE
has no <UNK> token at all.
==============================================================================
ENCODING NEW TEXT
==============================================================================
A word from the training corpus
==============================================================================
start: ['t', 'h', 'e', '_']
after a merge: ['t', 'h', 'e_']
after a merge: ['th', 'e_']
after a merge: ['the_']
'the' -> ['the_'] (1 token)
A word the tokenizer has NEVER seen
==============================================================================
'cats' -> ['c', 'at', 's', '_'] (4 tokens)
'chat' -> ['c', 'h', 'at_'] (3 tokens)
'strategy' -> ['s', 't', 'r', 'at', 'e', 'g', 'y', '_'] (8 tokens)
No <UNK> anywhere. Unseen words decompose into known pieces, and in
the worst case into single characters -- which are always in the
vocabulary because that is where training started.
Why merge ORDER matters
==============================================================================
merges applied in training order : ['the_']
merges applied in reverse order : ['th', 'e_']
same result? False
The list is a sequence of dependent rewrites, not a set of rules.
4. The consequences that show up in real models
Everything odd about how language models handle text traces back to this algorithm.
Counting letters is hard. If strawberry is three tokens, the model never
sees individual letters, so "how many r's" is a question about something it
cannot observe directly.
Arithmetic is fragile. Whether 1234 is one token, or 12+34, or
1+2+3+4, depends on which digit strings happened to be frequent in the
training corpus. Digit grouping is arbitrary, which is why many recent
tokenizers special-case digits.
Some languages cost far more. BPE merges are learned from a corpus. A language under-represented in that corpus gets few merges, so its text stays close to character-level — more tokens for the same meaning, more compute, and less context.
Whitespace attaches to words. Most modern tokenizers make " the" (with the
leading space) a different token from "the", which is why prompts ending in a
trailing space often behave strangely.
==============================================================================
THE CONSEQUENCES, MEASURED
==============================================================================
Fertility: tokens per word, for text the tokenizer knows well or badly
==============================================================================
in-corpus: 6 words -> 9 tokens (fertility 1.50)
out-of-corpus: 3 words -> 28 tokens (fertility 9.33)
Same tokenizer, 3 words each. The corpus the merges
were learned from decides the cost of the text you actually send.
How vocabulary size trades against sequence length
==============================================================================
Re-training with different merge budgets on the same corpus:
merges vocab size tokens for corpus tokens/word
------------------------------------------------------
0 12 85 3.70
4 16 52 2.26
8 20 39 1.70
16 28 26 1.13
32 31 23 1.00 (corpus exhausted)
64 31 23 1.00 (corpus exhausted)
------------------------------------------------------
More merges -> bigger vocabulary -> shorter sequences. That is the
entire design trade: embedding table size against attention cost.
Real tokenizers sit around 32k-256k merges; GPT-2 used 50,257
tokens, Llama 3 used 128k, and the trend is upward as context
windows grow and sequence length gets more expensive.
Counting letters, from the model's point of view
==============================================================================
'rat' -> ['r', 'at_']
the model sees 2 opaque symbols, not 3 letters
'rats' -> ['r', 'at', 's', '_']
the model sees 4 opaque symbols, not 4 letters
'strategy' -> ['s', 't', 'r', 'at', 'e', 'g', 'y', '_']
the model sees 8 opaque symbols, not 8 letters
Asking 'how many t's in strategy' requires information that was
discarded before the first embedding lookup.
5. What to take away
BPE is a compression algorithm, and the merge list is the whole model. No probabilities, no training objective — just "merge the most frequent adjacent pair, repeatedly". The ordered list of merges is the tokenizer.
It has no unknown words, because it can always fall back to characters. That single property is why it replaced word-level vocabularies.
Vocabulary size and sequence length are the same dial. More merges means longer tokens, shorter sequences, and a larger embedding table. Since attention costs $O(n^2)$ — see [[deepseek-v4]] for how far people go to beat that — the pressure has been steadily toward larger vocabularies.
Most "weird" LLM behaviour around letters, digits, and non-English text is a tokenizer artefact, not a reasoning failure. The information was destroyed before the model saw anything.
Verified in this notebook
- Eight merges performed by hand, each showing the pair counts that motivated it
- The resulting merge list applied to training words and to words never seen, with no
<UNK>produced - Applying the same merges in reverse order gives a different segmentation, showing the list is order-dependent
- Fertility measured on in-corpus vs out-of-corpus text
- Merge budget from 0 to 64 traded against vocabulary size and total tokens
Where this connects
This is the step immediately before every transformer page: [[autoregressive-transformer-encoder-decoder]] takes these IDs and embeds them, [[bert-on-eeg]] replaces them with signal patches, and [[kimi-k3]] and [[deepseek-v4]] are both largely concerned with making long token sequences affordable.
References
- Neural Machine Translation of Rare Words with Subword Units
- A New Algorithm for Data Compression
- SentencePiece: A simple and language independent subword tokenizer