How does Byte-Pair Encoding (BPE) tokenization work?

How to think about it

Suppose a word-level tokenizer has never seen unbelievability: it may replace the whole word with [UNK], a special unknown marker. A character tokenizer can represent it, but it turns a 15-letter word into 15 model inputs. BPE solves the trade-off by starting with small symbols and repeatedly merging the most frequent adjacent pair, producing reusable subword tokens such as un, believ, or ability.

Why BPE exists

A language model does not receive words directly. It receives a sequence of integer token IDs. A vocabulary is the fixed collection of token strings that those IDs refer to. The tokenizer converts text into vocabulary entries before the model runs.

Word tokenization is compact when the word is common. It is brittle when the word is rare. A vocabulary containing playing may not contain playfully, a new product name, or a misspelling. Character tokenization has the opposite problem: it almost never encounters an unknown word, but sequences become long. Longer sequences consume context and increase computation.

BPE sits between those extremes. Common pieces become single tokens, while rare words can be assembled from smaller pieces. The model might have a token for play, another for ing, and several smaller pieces for an unfamiliar name.

The name comes from a 1994 data-compression algorithm. Sennrich and colleagues adapted the idea for neural machine translation in 2016. Modern GPT-family tokenizers often use byte-level BPE variants, but the central mechanism remains the same.

The training mechanism

BPE training learns a vocabulary and an ordered merge table, which is a ranking of pairs that may be joined. Training and encoding are separate operations.

1. Choose the base symbols.
   In the original NLP formulation, each word starts as characters plus an end-of-word marker such as </w>. A byte-level tokenizer instead starts from the possible byte values, typically all 256 byte values, so it can represent arbitrary ordinary UTF-8 text.

2. Count adjacent pairs.
   The algorithm counts how often two neighboring current symbols occur. The pair l o is one pair; o w is another. Counts include repeated occurrences, so a word appearing 10,000 times contributes 10,000 opportunities.

3. Merge the most frequent pair.
   If l o wins, the tokenizer creates a new symbol lo and replaces that pair wherever it occurs in the training representation.

4. Recount and repeat.
   The new symbol changes neighboring pairs, so the counts are updated. BPE keeps merging until it reaches the target vocabulary size. The final vocabulary contains base symbols, learned symbols, and usually special tokens such as beginning-of-sequence or padding markers.

With 256 byte bases and a target vocabulary of 32,000 entries, there are roughly 31,744 merge slots before special tokens are accounted for. The exact count depends on the tokenizer’s configuration.

The most frequent pair is not necessarily the most meaningful linguistic unit. BPE is learning compression from frequency. It does not know what a prefix, suffix, syllable, or word means.

A worked example

Take this tiny corpus:

low low low lower lowest

Ignore the end-of-word marker for a moment and represent each word as characters. The first pair counts include:

Pair	Occurrences
l o	5
o w	5
w e	2
w </w>	3
e r	1
e s	1
s t	1

The pair l o ties with o w at five occurrences. A real implementation must use a deterministic tie-breaking rule. Suppose it chooses l o.

The corpus now contains lo w five times, so the next merge can be:

lo w becomes low

The three standalone instances of low now contain the learned symbol low. The two longer words begin with the same symbol:

• low
• low e r
• low e s t

At this point, low e occurs twice, while e r occurs once. So the tiny corpus does not automatically justify the attractive story that lower becomes low + er. A later merge may create er, but frequency decides that, not our knowledge of English morphology.

This is an important interview detail: BPE often discovers pieces that look linguistic because common morphemes are frequent, but it can also produce awkward pieces. A token such as tion, a leading-space-plus-word fragment, or half of an emoji is still perfectly valid BPE output.

What happens when encoding new text

After training, the tokenizer does not recount the corpus. It uses the saved merge ranking.

Suppose the learned merges, in order, include:

1. l o becomes lo
2. lo w becomes low
3. e r becomes er
4. low er becomes lower

To encode lower, the tokenizer starts with:

l o w e r

It applies the available merges:

lo w e r
low e r
low er
lower

The resulting token or tokens are then converted into integer IDs for the model. A different input such as lowest can reuse low and leave the remaining characters as smaller pieces if no later merge has formed est.

The exact implementation may apply the highest-priority available pair using an efficient heap rather than literally scanning the string after every merge. That is an implementation detail. The important property is that the fixed merge ranking determines the result.

Whitespace and word boundaries are tokenizer-specific. In some displays, a marker such as Ġ indicates a preceding space. It is a display convention, not necessarily a character the user typed. End markers, byte-to-character mappings, normalization, and special-token rules are part of the tokenizer too.

Warning — common misconception: BPE does not always eliminate unknown tokens. Character-level BPE trained on a limited alphabet may encounter a character it never learned and emit [UNK]. Byte-level BPE avoids that problem because every byte has a base representation, but the model can still treat reserved special-token strings or malformed input according to its own tokenizer rules.

The trade-offs

BPE’s vocabulary size is a real engineering decision.

A smaller vocabulary creates more tokens per sentence. That increases sequence length, and standard full self-attention has roughly quadratic work in that length. Holding everything else constant, doubling the token count can approach four times as much attention interaction.

A larger vocabulary can turn frequent multi-character strings into one token, shortening sequences. It also increases the size of the embedding table and often the output projection. A 50,000-entry vocabulary and a 100,000-entry vocabulary are not interchangeable memory choices. Large vocabularies can also spend capacity memorizing chunks that are useful in one domain but rare in another.

BPE is therefore corpus-dependent. Change the training text, casing policy, Unicode normalization, whitespace handling, pre-tokenization rules, or target vocabulary size, and the same surface word may split differently. Token IDs have no portable meaning across models. ID 12,345 in one tokenizer is unrelated to ID 12,345 in another.

That is why a model and tokenizer must travel together. Replacing the tokenizer after training changes which embedding vector each piece receives. The model may still accept integers and produce output, with no helpful exception, but the integers now mean the wrong things.

BPE versus nearby methods

BPE selects pairs using raw frequency. WordPiece, used by BERT, uses a likelihood-oriented scoring rule rather than simply choosing the most frequent pair. Its resulting pieces can look similar, but the merge decisions and vocabulary are different.

Unigram tokenization takes a different route: it starts with a larger candidate set and removes pieces according to a probabilistic objective. SentencePiece is a tokenizer toolkit that can train BPE or Unigram models; it is not itself a third BPE variant.

The practical lesson is simple: seeing a familiar token such as play does not mean two models tokenize the surrounding text the same way. Always inspect the exact tokenizer attached to the model.

Production failure mode

A common failure appears after a tokenizer or preprocessing change: prompts that used to contain 220 tokens now contain 470, context truncation begins, and latency rises. The model may be unchanged. A different normalizer, whitespace rule, byte encoding, or merge file can cause the jump.

Another failure is a tokenizer mismatch between training and serving. It often produces no Python error because the new IDs are still valid integers. The first visible symptom is degraded quality, strange handling of punctuation or emoji, or a sudden shift in token-count distributions.

A production deployment should version the complete tokenizer artifact: normalization rules, pre-tokenizer, base encoding, vocabulary, merge ranks, special-token policy, and decoder. Keep golden tests for ordinary text, repeated whitespace, accents, emoji, code, and long rare strings. Test both token IDs and round-trip decoding. “It can tokenize the sentence” is not enough; it must tokenize it the same way the model expects.

What they’ll ask next

Does BPE understand word meaning or morphology?
No. It only uses the statistical structure of the training corpus. Meaning enters through model training, not through the merge rule. BPE may discover useful morphemes because they occur often, but that is an outcome of frequency rather than a linguistic guarantee.

Does byte-level BPE make every word one token?
No. It makes every byte representable, not every word compact. An unfamiliar word can still become many byte-derived pieces. Byte-level BPE removes the coverage problem, not the sequence-length problem.

Why can two GPT models count the same prompt differently?
They may use different vocabularies, merge rankings, special-token definitions, or preprocessing rules. Token count is a property of the exact model-tokenizer pair, not of the visible text alone.

Say this in the interview

“BPE starts from characters or bytes, repeatedly merges the most frequent adjacent pair to learn an ordered subword vocabulary, and then applies those fixed merges at inference; it shortens common sequences while letting rare words fall back to smaller pieces, with byte-level variants avoiding unknown characters.”