Byte-Pair Encoding Explained: How LLMs Turn Text Into Tokens

A language model has never seen your text. It receives a list of integers and nothing else. Byte-pair encoding is the algorithm that produces that list, and it finishes its work before a single model weight is touched. It is also responsible for a surprising share of the failures people file under “the model cannot reason”.

This is Part 2 of Inside the Inference Stack. Part 1 followed a prompt through the whole system, from characters typed in a box to a token streamed back. This part opens the first box on that path and shows what is inside it.

By the end you will have run the training algorithm by hand on a four-word corpus, small enough that you can check every number yourself. You will be able to say exactly why a model miscounts the letters in “strawberry”, why the same sentence costs three times more in Urdu than in English, and why nobody swaps a tokenizer after training. There is a short snippet near the end for inspecting your own strings.

What a tokenizer is, and the one choice inside it

A tokenizer is two data files and one procedure. The vocabulary is a fixed list of byte strings, each owning exactly one integer ID. The merge list is an ordered set of rules that decides how an arbitrary input string gets cut into entries from that vocabulary. Both files are produced once, before pretraining begins, and neither one changes for the life of the model.

The design question is what a single vocabulary entry should be. Three answers are available: a character, a whole word, or a fragment in between. The first two are the ones people reach for first, and each fails in a way that surfaces as an infrastructure bill rather than as an error message.

Characters give you a tiny vocabulary: about a hundred symbols for English, or 256 if you work in raw bytes. Nothing is ever unrepresentable. The cost lands on sequence length instead. Attention work grows with the square of the sequence, so spending seven tokens on “unhappy” instead of one costs 49 times the attention arithmetic across that span. The KV cache, the per-token memory a model keeps for every position it has already processed, grows linearly with the same sequence, and on a real GPU that cache is what runs out first. Longer sequences also push you deeper into the regime where decode is memory-bound, so you pay again on every token generated.

Words give you short sequences and the mirror-image problem. The vocabulary is unbounded, because new product names, typos, URLs, function names and inflections arrive forever. Anything outside the fixed list becomes an out-of-vocabulary token, usually a single <unk> placeholder, which destroys the information before the model gets a chance to use it. Word units also break the relationship between related strings: “happy” and “unhappy” receive unrelated integers and therefore unrelated embedding rows, sharing nothing at all.

Subword units are the compromise that wins. A subword is a frequent fragment of text, which may be a whole common word, a prefix, a suffix, or a single byte for anything rare. Two properties follow. Vocabulary size becomes a dial you set rather than a fact about the language, and fragments are shared across words that look alike, so morphology survives into the integer representation.

Vocabulary size is not a free parameter, because the vocabulary appears twice inside the model as a matrix of shape vocab by d_model. Once as the input embedding table, which turns each token ID into a vector, and once as the output projection, which turns the final hidden state back into one score per vocabulary entry. Many models tie those two matrices to share the weights. At our running d_model of 8,192, the arithmetic settles the argument on its own.

Read the last column first. A word-level vocabulary would spend more parameters on the embedding table alone than a 7B model spends on everything it has. A character-level vocabulary is almost free in parameters and ruinous in sequence length, which is the resource that actually constrains serving. Subword sits between the two: 128,256 by 8,192 comes to just over a billion parameters, a real and knowingly accepted cost that buys short sequences and universal coverage at the same time.

Training a tokenizer: a four-word corpus, merge by merge

Training a tokenizer has nothing in common with training a model. There is no gradient, no loss function and no randomness. It is a counting loop over a corpus that runs a fixed number of rounds and writes out a file. The whole algorithm fits on one line: count every adjacent pair of symbols, fuse the most frequent one into a new symbol, repeat.

Start: every symbol on its own

Here is the entire training corpus, expressed as word types with frequencies: “low” appears 5 times, “lower” 2 times, “newest” 6 times, “widest” 3 times. That is 16 word occurrences over four distinct words. BPE works on this frequency table rather than on the running text, which is why a corpus of billions of words still trains in minutes. Every word starts split into its base symbols.

Nothing has been learned at this point. The vocabulary is ten symbols, “low” is three tokens, and “newest” is six. Every improvement from here comes from the counting loop.

Round 1: count every pair, merge the winner

Count every adjacent pair across the corpus, weighting each occurrence by its word frequency. The pair e + s appears inside “newest” (6) and “widest” (3), so it scores nine. The pair s + t scores nine as well, from the same two words for the same reason. The pair l + o and the pair o + w each reach seven, five from “low” and two from “lower”. Counting the rest by hand takes a minute, and that minute is the entire algorithm.

The winning pair gets fused everywhere it occurs. “newest” becomes n e w es t and “widest” becomes w i d es t, dropping both from six symbols to five. The vocabulary is now eleven entries, and es is a token that will exist for the entire life of any model trained on this tokenizer.

That indifference is the point worth holding onto. Nobody told the algorithm that es is a meaningful English fragment. It won on frequency alone, and it would have won just as decisively on a corpus of chemical formulae or Base64 blobs if the counts had come out the same way. Every property people later attribute to the tokenizer, good or bad, traces back to what was in the corpus.

The tie at nine also has to be broken by a rule, and every implementation has one, usually first-seen order or a lexicographic comparison. The specific rule matters less than the fact that it is deterministic, because whichever pair wins gets baked into an artifact that a model will then train against for months.

Rounds 2 to 4: merges build on merges

This is the property that makes byte-pair encoding more than a compression trick: a merged symbol is itself a candidate for further merging. Round 1 created es. Round 2 can therefore merge es + t into est at count 9. Round 3 takes l + o at count 7. Round 4 takes the new symbol lo plus w at count 7 and produces low.

Four rounds in, the algorithm has bootstrapped from single letters to a complete English word, with no dictionary involved at any point. “low” is now one token where it was three. “newest” is n e w est, four tokens where it was six. That recursion is what lets 50,000 rounds produce tokens as long as ” unfortunately” from a base of individual bytes.

You stop whenever you like, and the stopping point is the whole vocabulary-size decision. GPT-2 ran 50,000 rounds. More merges buys shorter sequences and a fatter embedding table. Fewer merges does the reverse. There is no correct answer here, only a tradeoff picked for a particular deployment, which is why a code-heavy model and a multilingual model land on different numbers.

The merge list is the trained artifact

Training produced two files, and the second one is the interesting half. A vocabulary lists what exists. A merge list records in what order things came to exist, and encoding depends entirely on that order.

Order is also what separates byte-pair encoding from greedy longest-match, which people frequently assume is the same algorithm. It is not, and the two disagree on real inputs.

Take a merge list that learned n + i as rule 5 and u + n as rule 12, and encode the string “unit”. BPE replays in rank order, so rule 5 fires first and gives u ni t. Rule 12 can then never fire, because the n it needs is already sealed inside ni. The result is u, ni, t. Greedy longest-match starts at position 0, finds un in the vocabulary and uni absent from it, and returns un, i, t. Same token count, completely different integers, and the model has only ever been trained on one of the two.

This is why a tokenizer is frozen the moment a model starts pretraining on it. Token 8,921 carries meaning only because the model saw that integer a billion times in a consistent role. Change the merge order and a different string now maps to that integer, so every embedding row is attached to the wrong thing. There is no migration path and no adapter you can bolt on. You retrain.

Encoding a word that was never in the corpus

The training corpus contained “low”, “lower”, “newest” and “widest”. It never contained “lowest”. Encoding it shows the payoff for everything above: split into base symbols, then replay the merge list in rank order.

• start: l o w e s t
• rule 1 (e + s): l o w es t
• rule 2 (es + t): l o w est
• rule 3 (l + o): lo w est
• rule 4 (lo + w): low est

The unseen word resolves into two tokens, both learned from other words, both carrying meaning the model has practised with millions of times. Nothing was unrepresentable, no unknown-token fallback was involved, and the model can generalise from “low” and from the superlative marker “est” to a word it never encountered. That generalisation is the entire reason the subword compromise won.

Production implementations add two things to this picture. They do not rescan the whole text once per rule, because that would be 50,000 passes; they keep a priority queue of candidate merges keyed by rank, which yields an identical answer far faster. And before any merging happens, they run a regular expression over the raw text to cut it into pre-tokens.

Where byte-pair encoding leaks into model behaviour

The four behaviours below get filed as reasoning failures and are nothing of the kind. Each one is a direct consequence of a boundary decision made during tokenizer training, before the model saw a single training example. Recognising them saves you from trying to fix them with prompting.

Arithmetic

Numbers are chunked by frequency like everything else, so “380” may be one token while “381” is two, 38 followed by 1. There is no positional digit system anywhere in the token IDs, which means the model cannot line up columns the way you were taught to. It has to learn addition over a chunking of numbers that is inconsistent by construction. Several newer tokenizers cap digit runs at three characters in the pre-tokenizer regex, and some force every digit onto its own token. Both help a great deal, and neither makes arithmetic free.

Spelling and counting characters

“strawberry” comes apart into roughly str, aw, berry. The model never receives letters. It receives three opaque integers with learned vectors attached, and the internal structure of each chunk is not visible to any layer. Asking how many r’s the word contains asks the model to report on structure it has never directly observed. It often answers correctly anyway, because a great deal of internet text spells words out letter by letter and large models absorb those descriptions, though that is recall rather than reading.

Whitespace and the leading space

Whitespace is text, so it costs tokens like text does. GPT-2 turns four spaces into four separate tokens, which makes one level of Python indentation cost four times what it should. Later tokenizers added merges for runs of spaces, and that single change is a large part of why code became cheaper to process. It is worth checking before you build a product that ships a lot of indented text.

The leading space matters more than people expect, and it follows directly from the pre-tokenizer definition above. Because a space is attached to the word after it, " the" and "the" are two different tokens with two different IDs and two unrelated embedding rows. The model spends nearly all of its training seeing the space-attached variant in mid-sentence positions.

Fertility outside English

The merge list was trained on a corpus, and for most widely deployed tokenizers that corpus was overwhelmingly English. English words therefore earned long, efficient tokens. Other scripts did not. Characters in Devanagari, Arabic or Thai also occupy multiple bytes each in UTF-8, so thin merge coverage over those byte sequences means paying several tokens per single character.

What fertility does to your bill and your context window

Fertility is the number you actually budget against, so it helps to carry rough ratios in your head before you size anything. The figures below are the typical spread for a modern English-trained tokenizer such as cl100k_base.

Treat those as approximate ratios rather than measurements. They move with the tokenizer version, the domain and the specific text in front of you. The shape of the spread is the durable part, and your own corpus is the only source for a number you plan to put in a spreadsheet.

Three consequences follow directly, and the first is the bill. Providers charge per token in both directions, so a 3x fertility ratio is a 3x input bill for the same sentence. Prompt caching removes a chunk of that for repeated prefixes and routing cheap requests to smaller models removes another, though neither one changes the underlying ratio.

The second is the context window, which is measured in tokens and therefore holds a variable amount of meaning. A 32,000-token window holds roughly 24,000 words of English and perhaps 8,000 words of a high-fertility language. If you are chunking documents for retrieval, a chunk size expressed in words is not portable across languages, and a config tuned on English will silently truncate elsewhere.

The third is GPU memory, which is where the tokenizer quietly makes a hardware decision for you. Take the running Llama-3-70B class model: 80 layers, 8 KV heads, head_dim 128, bf16. Per token that is 2 (for K and V) times 8 times 128 times 2 bytes times 80 layers, which comes to 327,680 bytes, about 320 KB. A 1,000-token conversation therefore holds roughly 320 MB of cache. Serve the same conversation in a language with 3x fertility and you are holding close to 1 GB for identical meaning. Multiply that by concurrent users and the merge list has just set your GPU count, which is a number worth having before you move a demo into production.

The neighbours: WordPiece, Unigram, SentencePiece and tiktoken

BPE is the most common approach and not the only one. Four names come up constantly in tokenizer configs, and knowing which is an algorithm and which is a library saves a lot of confusion when reading model cards.

The practical distinction hides in the last two rows. WordPiece and Unigram are genuinely different training and encoding algorithms, so their outputs differ from BPE on the same text. SentencePiece and tiktoken are implementations, so a config naming either of them still leaves the algorithm question open, and you have to read further to find out which one is running underneath.

Inspect your own strings

Everything above is checkable in about a minute, and the checking is worth more than the reading. Install tiktoken and look at what your actual production text becomes.

import tiktoken

enc = tiktoken.get_encoding("cl100k_base")   # GPT-4 class encoding
text = "What is a quadratic equation?"

ids = enc.encode(text)
print(len(ids), "tokens")
for i in ids:
    print(i, enc.decode_single_token_bytes(i))

The running prompt from Part 1 comes to seven tokens. Two details in the output are worth pausing on. The tokens print as byte strings rather than as text, because byte strings are what they are underneath. And the leading spaces appear attached to the words that follow them, which is the pre-tokenizer behaviour showing up in your own terminal instead of in a diagram.

From here, Part 3 takes those integers into the first transformer block and follows what happens to them once they become vectors.

Key takeaways

• Characters and words both fail, in opposite directions. Subword units turn vocabulary size into a dial you set rather than a property of the language.
• Training is one counting loop: count every adjacent pair weighted by frequency, fuse the winner, repeat. In the toy corpus e + s wins round 1 with nine occurrences, six from “newest” and three from “widest”.
• Merged tokens are candidates for further merging, which is how four rounds get from single letters to the whole word “low”.
• The ordered merge list is the trained artifact. Encoding replays it in rank order, which is a different algorithm from greedy longest-match and gives different answers.
• Starting from the 256 byte values removes the out-of-vocabulary problem completely. Any input encodes, always.
• Arithmetic errors, letter-counting errors, whitespace waste and leading-space sensitivity are tokenization artifacts rather than reasoning failures.
• Fertility is an infrastructure number. Non-Latin scripts can cost 2x to 4x the tokens for the same meaning, which lands on your bill, your context window and your KV cache at once.

Frequently asked questions

Why do LLMs get “how many r’s are in strawberry” wrong?

The model never sees letters. Byte-pair encoding splits the word into a few opaque chunks such as str, aw and berry, and each chunk arrives as a single integer with no internal structure. Any answer about spelling is recalled from text that described the spelling rather than read off the word itself.

What is the difference between byte-pair encoding and tiktoken?

Byte-pair encoding is the algorithm and tiktoken is one fast implementation of it, written in Rust with Python bindings. tiktoken also ships specific pre-trained encodings such as cl100k_base and o200k_base, which are merge lists rather than algorithms.

What exactly is a merge list?

It is the ordered log of every merge rule the tokenizer learned during training, stored with its rank from first to last. Encoding a string means splitting it into base symbols and replaying that log in order, so two tokenizers with the same vocabulary but a different merge order produce different token IDs.

Why do non-English prompts cost more tokens?

The merge list was trained on a corpus that was mostly English, so English words became long efficient tokens and other scripts did not. Characters in scripts like Devanagari or Arabic also take multiple bytes each in UTF-8, so the same meaning can take two to four times as many tokens.

Can you change a model’s tokenizer after training?

Not without retraining. Every token ID carries meaning only because the model saw that integer in a consistent role billions of times, so changing the merge list detaches every embedding row from what it learned. Tokenizers are frozen before pretraining starts for exactly this reason.

How many characters are in a token?

For English prose the usual rule of thumb is about 4 characters per token, or around 1.3 tokens per word. That ratio gets worse for code and JSON, and considerably worse for non-Latin scripts, so measure your own text rather than relying on the average.

Does a trailing space at the end of a prompt matter?

It can. Most tokenizers attach a leading space to the word that follows it, so a word with its space and the same word without are different tokens with different embeddings. Ending a prompt with a space leaves the model predicting a continuation shape it saw rarely during training.

Sources and further reading

• Neural Machine Translation of Rare Words with Subword Units, Sennrich et al., the paper that brought BPE into NLP.
• Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates, Kudo, which introduces the Unigram language model tokenizer.
• SentencePiece: A simple and language independent subword tokenizer and detokenizer, Kudo and Richardson.
• Google’s Neural Machine Translation System, which describes WordPiece as deployed.
• openai/tiktoken, the reference fast BPE implementation and its named encodings.
• Hugging Face tokenizers documentation, for training and inspecting your own merge lists.