Byte-pair encoding, and why tokenizers work on bytes

01Between words and characters

A tokenizer has to pick a unit. The two obvious choices each fail in an obvious way.

• Words. The vocabulary is huge and still never complete. Any word not seen in training has no id, and the model's embedding table grows with every inflection, typo and name.
• Characters. The vocabulary is small and complete, but a sentence becomes hundreds of tokens, the model has to spend its early layers reassembling words from letters, and attention cost grows with the square of sequence length.

Byte-pair encoding sits between them. It was a 1994 compression technique, adapted for machine translation in 2016, and the idea is to learn the unit from the data: frequent strings get their own token, infrequent strings are spelled out from smaller pieces. The vocabulary size becomes a knob you set, typically 32,000 to 200,000, and the algorithm decides what goes in it.

02The training algorithm

1. Initialise. Split the corpus into base units, characters or bytes, and mark word boundaries so that merges do not cross them. The original formulation appends an end-of-word symbol </w>; later ones attach the leading space to the word instead.
2. Count pairs. For every adjacent pair of units in the corpus, count how often it occurs.
3. Merge the top pair. Take the most frequent pair, create a new token for it, and replace every occurrence of the pair with the new token.
4. Repeat. Recount and merge until the vocabulary reaches the target size. Each merge adds exactly one token, so a 50,000-token vocabulary over a 256-byte base is about 49,700 merges.

The output of training is two things: the vocabulary, and the ordered list of merges. The order matters, because it is replayed at encoding time.

03A worked example

The standard illustration is a corpus of four words with their counts. Each is split into characters with an end-of-word mark.

l o w </w>          × 5
l o w e r </w>      × 2
n e w e s t </w>    × 6
w i d e s t </w>    × 3

Count every adjacent pair, weighting by word frequency. The pair e s appears in "newest" (6) and "widest" (3), so 9 times. So does s t, and t </w>. Ties are broken by whatever rule the implementation uses; take e s first.

After five merges the vocabulary holds the base characters plus es, est, est</w>, lo and low. "low" is now a single token. "newest" is n e w est</w>. A word the corpus never contained, "lowest", encodes as low est</w>, two tokens, both meaningful, with no unknown symbol anywhere. That is the whole point: the pieces generalise to words the vocabulary has not seen.

04Encoding new text with the merges

At inference time the tokenizer does not count anything. It splits the input into base units and applies the learned merges in the order they were learned, each one wherever it applies, until no merge applies. Because the merge list is ordered by training frequency, common strings collapse into single tokens quickly and rare strings stay in pieces.

Before the merges run, most implementations also pre-tokenize with a regular expression that splits on spaces, punctuation and digit runs, so that a merge never joins "the" to the comma after it, and numbers are not swallowed into words. The regex is a design choice with real consequences; GPT-2's, for instance, keeps the leading space attached to a word, which is why " the" and "the" are different tokens.

05Why not whitespace-separated words

Early neural models used words, and a vocabulary of the most frequent 30,000 to 100,000 of them. Three things break.

• Out-of-vocabulary words. Anything not in the list maps to a single [UNK] token. A product name, a rare surname, a misspelling or a new word all collapse to the same id, and the model loses whatever that word carried. Replacing one word in a sentence with "unknown" can change its meaning entirely.
• Morphological explosion. English has a modest number of word forms. Turkish, Finnish or Telugu attach suffix after suffix, so one stem produces hundreds of surface words, each needing its own vocabulary slot and its own embedding row, and most of them rare. Typos add an infinite tail on top.
• No spaces to split on. Chinese, Japanese and Thai do not separate words with whitespace. Word tokenization needs a language-specific segmenter before it can even begin, and that segmenter has its own errors.

06Why not Unicode characters

Characters fix the unknown-word problem for text in scripts the tokenizer has seen. They have two problems of their own.

• The alphabet is enormous. Unicode defines about 150,000 characters: every script, every emoji, mathematical and musical symbols, historic alphabets. A character-based tokenizer either reserves a base vocabulary that large, mostly for symbols it will almost never see, or it keeps a subset and is back to [UNK] for the rest.
• Unseen characters still fail. A new emoji, a rare CJK ideograph or a character from a script absent from training has no id. The failure is rarer than with words, but it is the same failure.

So character-level BPE has a large, still-incomplete base alphabet, and the merges built on it are spent partly on rare symbols rather than on frequent strings.

07Why bytes

GPT-2 made the move that most tokenizers since have followed: run BPE not on characters but on the bytes of the text's UTF-8 encoding.

text  ──►  UTF-8 bytes  ──►  base vocabulary of 256  ──►  learned merges  ──►  subword tokens

Three properties follow directly.

No unknown token, ever

UTF-8 encodes every string as a sequence of bytes, and a byte has 256 possible values. If all 256 are in the base vocabulary, any input at all, in any script, any emoji, source code, even binary garbage, has a valid tokenization. The worst case is one token per byte. There is no input the tokenizer cannot represent, so there is no [UNK] and no code path for it.

A base vocabulary of 256

Instead of tens of thousands of slots reserved for rare symbols, the base costs 256 slots. Everything above that is earned by frequency. A common Chinese character is three bytes in UTF-8; if it is common in the training corpus, BPE merges those three bytes into one token within the first few thousand merges. A rare one stays as three byte tokens. Vocabulary space goes to what the corpus actually contains, not to what Unicode defines.

One pipeline for everything

Because bytes are below the level of script, the same tokenizer handles English, Telugu, Python, JSON, tab-indented tables and strings of emoji without a language detector or a per-language segmenter in front of it. Mixed-script text, which is common in practice, needs no special case. Whitespace is just more bytes, so indentation and line breaks survive exactly, which matters for code.

08What bytes cost

The guarantee is coverage, not efficiency. BPE spends its merges where the training corpus is dense, and most corpora are dense in English and code. Text in other scripts gets fewer merges, and because those scripts are two to four bytes per character in UTF-8, the starting point is longer too.

The practical effect is that the same sentence costs different amounts in different languages. An English sentence might be one token per word. The same sentence in Telugu or Hindi, on a tokenizer trained mostly on English, can be three to five times as many tokens, sometimes one token per byte. That means higher cost per request, less of the context window per unit of meaning, and a model that has effectively seen less of that language per token during training. Newer tokenizers with larger vocabularies and more multilingual training data narrow the gap, but do not close it.

Two smaller costs: a byte-level tokenizer can split a multibyte character across tokens, so a model that stops generating mid-character emits an invalid byte sequence that has to be handled on decode; and numbers tokenize unevenly, with "1000" and "1,000" and "1 000" producing different token patterns, which is one reason arithmetic is harder for language models than it looks.

09Takeaways

1. BPE learns the unit from the data. Merge the most frequent adjacent pair, repeat, stop at the vocabulary size you chose.
2. Frequent strings become tokens; rare strings become pieces. "low" is one token, "lowest" is "low" plus "est", and nothing is unknown.
3. Encoding replays the merges in order. After a pre-tokenization regex that decides what merges may never cross.
4. Words fail on coverage and on languages without spaces. Characters fail on a 150,000-symbol alphabet that is still incomplete.
5. Bytes give a 256-entry base that covers every input. No unknown token, and one pipeline for every script and for code.
6. Coverage is not efficiency. Scripts the corpus is thin on cost several times the tokens, and that shows up in price, context and quality.