Byte Pair Encoding: Subword Tokenization

In the previous chapter, we saw the fundamental tension in text tokenization: word-level models require a massive vocabulary and fail on unseen words, while character-level models sidestep vocabulary issues but produce sequences so long that models struggle to learn long-range dependencies. Both extremes have real costs in memory, compute, and modeling quality. This tension is not just theoretical. When researchers tried to train neural machine translation systems in the early 2010s, they were forced to choose between a fixed vocabulary that silently dropped unknown words and a character-level representation that made it nearly impossible for models to learn useful patterns over long contexts.

Byte Pair Encoding (BPE) threads this needle. It starts from individual characters and iteratively merges the most frequent adjacent pairs into new tokens. After enough merges, common words become single tokens while rare words decompose into smaller meaningful pieces. You get compact representations for frequent language patterns and graceful fallback for novel words, all without any manually curated vocabulary or linguistic knowledge. The algorithm learns what to represent as a single unit directly from the statistics of the corpus.

Think of BPE as building a dictionary by committee from the ground up. Start with every letter as its own word. Then repeatedly promote the most common two-word phrase into a single compound word. After enough promotions, your dictionary contains common syllables, morphemes, and whole words, all discovered without ever telling the algorithm what a morpheme is. The result reflects the actual patterns of the language rather than any preconceived notion of how language works.

BPE was originally a lossless data compression algorithm introduced by Philip Gage in 1994. Its application to neural machine translation by Rico Sennrich, Barry Haddow, and Alexandra Birch in their landmark 2016 ACL paper transformed it into the default subword tokenization method for the field. That paper demonstrated that BPE solved the unknown word problem in translation and improved translation quality compared to word-level models, by allowing the model to learn morphological patterns explicitly. Today, BPE or close variants power the tokenizers in GPT-2, GPT-3, GPT-4, RoBERTa, LLaMA, and dozens of other models. Understanding it is therefore essential background for anyone working with modern language models.

This chapter covers BPE end-to-end: the algorithm's design principles, the step-by-step training procedure, encoding and decoding new text, vocabulary size tradeoffs, byte-level extensions, and a complete from-scratch implementation. We will also look at where BPE falls short, because understanding its limitations helps you make better decisions when choosing or training tokenizers for practical systems.

Before diving into mechanics, it is worth understanding the intuition behind BPE's design. Every practical engineering decision in the algorithm reflects a deliberate choice about what matters in language representation, and seeing those connections early makes the later details much more natural.

Natural language has structure at multiple scales. Morphemes are the smallest units of meaning: prefixes like "un-" and "re-", roots like "walk" and "play", and suffixes like "-ing", "-tion", and "-er". These units appear repeatedly across thousands of different words. A tokenizer that represents them as single units needs far fewer tokens per sentence than one working character-by-character, yet far fewer vocabulary entries than one trying to enumerate every possible word form. Consider the word family "play", "plays", "player", "playing", "replayed", "unplayable". A character-level model treats each of these as a string of independent characters. A word-level model treats each as an atomic unit with no connection to the others. A subword model can represent all of them using shared tokens for "play", "-er", "-ing", "re-", and "un-", letting the downstream neural network learn that these shared tokens carry related meaning.

BPE discovers these units automatically from data. You do not specify that "ing" or "tion" are important; the algorithm notices they appear frequently and merges them. The result is a vocabulary that reflects the actual distributional patterns of the language it was trained on. For code, it discovers common keywords and operators. For German, it handles compounds. For multilingual corpora, it allocates tokens proportionally to the frequency of each language's patterns. This data-driven quality lets the same algorithm work for any language or domain without modification. You do not need a linguist's analysis of Turkish morphology or an engineer's understanding of Python syntax. You need only a large corpus.

The greediness is a feature, not a limitation. Each merge targets the pair that provides the greatest compression gain at that moment. This greedy schedule produces vocabularies that are empirically close to optimal for downstream tasks, and its simplicity makes training fast and deterministic. Running BPE on a corpus of billions of words takes hours rather than days. The algorithm always produces the same result for the same corpus and target vocabulary size, which is important for reproducibility. And the output, an ordered list of merge rules, is a compact artifact that can be saved, shared, and applied to any new text with no further training.

The key insight is that language compression and language modeling are deeply aligned. The patterns that compress text efficiently, common morphemes, frequent word endings, recurring prefixes, are exactly the patterns that carry consistent meaning across contexts. By optimizing for compression, BPE is indirectly optimizing for linguistic structure. This is why it works better than arbitrary segmentation schemes and why it generalizes so cleanly to languages the algorithm designers never anticipated.

BPE has two distinct phases: training (learning merge rules from a corpus) and encoding (applying those rules to new text). These phases are conceptually separate and use different procedures. Training reads the entire corpus and learns statistical patterns. Encoding applies those learned patterns to individual strings, one at a time. Let us trace through each carefully.

The full algorithm can be described in a few sentences, but each step has subtleties that matter in practice. Training starts by splitting every word in the corpus into characters, counting how often adjacent character pairs appear, merging the most frequent pair everywhere it occurs, and repeating. Encoding starts with a character-split word and replays the learned merge rules in order. Decoding simply concatenates the tokens back into a string.

Understanding where edge cases arise, particularly around word boundaries, merge ordering, and out-of-vocabulary characters, requires working through concrete examples. We will do that in detail in the worked example section after covering the algorithm itself.

Training starts by splitting every word in the corpus into individual characters. A special end-of-word marker (commonly </w>) is appended to each word. This marker serves a critical purpose: it lets BPE distinguish between the substring "est" inside "estimated" and the standalone suffix "est" at the end of "smallest". Without word boundaries, merges can bleed across word edges in ways that corrupt the vocabulary.

The initial vocabulary is the set of all unique characters that appear in the training corpus, plus the </w> symbol. For ASCII English text, this is roughly 60-70 tokens. For Unicode corpora covering hundreds of languages, it may be thousands. Character-level coverage is the foundation of BPE's guarantee that any input can always be tokenized: as long as every character that ever appears in new text appeared at least once in training, the vocabulary can represent it.

Each word is now represented as a sequence of character tokens separated by spaces. The </w> marker appears as a distinct token. Notice that "low" (freq=4) and "new" (freq=4) both appear frequently because they recur across multiple sentences. This frequency weighting is important: every adjacent pair in a word that appears four times contributes four to the pair count. Words that appear more often exert proportionally more influence on which merges happen first.

With the corpus represented as character sequences, the algorithm counts how many times each adjacent pair of tokens co-occurs across all word occurrences. If a word appears 4 times in the corpus, each of its adjacent pairs contributes 4 to the count. This weighting by word frequency means the pair counts reflect how often each pattern appears in running text, not just how many word types contain that pattern.

The counting step is the computational heart of BPE training. For large corpora, this step must be performed efficiently because it runs once per merge iteration and there may be tens of thousands of iterations. In practice, optimized implementations maintain a priority queue of pair frequencies rather than recomputing counts from scratch each iteration, updating only the entries affected by the most recent merge.

The pair with the highest count wins the first merge. With our small corpus, you will likely see ('e', 'w') at the top because it appears in every occurrence of "new", "newer", and "newest", accumulating a high count. This is a good example of how BPE discovers morphological structure: "ew" is part of a productive root ("new") that appears across many word forms, so the algorithm merges it early.

The winning pair is merged into a single token everywhere it appears. The merge rule is recorded in an ordered list, which will be replayed later during encoding. This is important: the order matters. If you learned "e w" before "ew s", you must apply those rules in the same sequence when encoding new text. The ordering is not arbitrary but reflects the dependency structure of the merges: later rules often depend on tokens created by earlier rules.

The merge operation itself is a simple string replacement on the space-separated token representation. Every occurrence of the space-delimited bigram "(a) (b)" becomes the single token "ab". The total number of tokens in the corpus decreases by exactly the frequency of the merged pair.

After the merge, every occurrence of the old bigram has been replaced by a single token. The total number of tokens in the corpus decreases by one for each occurrence of the merged pair. BPE is a compression algorithm: each merge reduces the total length of the encoded corpus. The merge operation is also why the algorithm is fast to implement: it requires only string operations on the space-separated word representations, not any complex data structure manipulation.

The algorithm repeats steps 2 and 3 until the vocabulary reaches the desired size. If we start with $|C|$ unique characters and want a vocabulary of size $V$, we perform exactly $V - |C|$ merges. Each merge adds exactly one new token to the vocabulary (the merged bigram becomes a new type), so the number of merges maps directly to the vocabulary size increase.

The stopping condition is simple but consequential. If you stop too early, with too few merges, the vocabulary will be small and sequences will be long, requiring many tokens to represent each word. If you stop too late, with too many merges, the vocabulary grows large with tokens that appear rarely in training data and may not transfer well to new text. Finding the right stopping point is the primary hyperparameter decision in BPE, and we will discuss it in depth in the vocabulary size section.

The merge rules reveal meaningful linguistic patterns. The algorithm discovers that common character combinations like "ew", "lo", "ow" appear frequently in our small corpus and merges them early. With more training data, it would discover suffixes like "ing", "tion", "er", and "est" as stable patterns. The fact that these linguistically meaningful units emerge without any explicit linguistic knowledge is one of BPE's most elegant properties.

Two properties of BPE training are worth seeing directly. First, pair frequencies follow a Zipf-like distribution: a few pairs are very common while most are rare. Second, each merge reduces the total token count in the corpus, and the rate of reduction decreases over time as less-frequent pairs are targeted. Both of these properties have practical implications for how you configure BPE training.

The Zipf-like distribution of pair frequencies is important because it tells you that the first merges provide much more compression benefit than later merges. Roughly speaking, doubling the number of merges does not double the compression: early merges capture highly frequent patterns, while later merges target increasingly specialized patterns. This is why small vocabulary sizes, achieved with fewer merges, are surprisingly effective: the first few hundred merges capture the bulk of the linguistic structure in the corpus.

The left chart confirms the Zipf-like shape: the top three pairs (shown in red) are much more frequent than the rest. This is why greedy selection works well in practice. By capturing the most common pattern first, BPE maximizes compression gain at every step.

The right chart shows the compression payoff. The curve is steepest at the start, when high-frequency pairs are being merged, and flattens out as the algorithm moves to less common pairs. This diminishing-returns behavior is typical and helps practitioners decide when to stop training: once the curve flattens significantly, additional merges provide minimal compression benefit and the vocabulary grows with increasingly rare tokens.

Training produces an ordered list of merge rules. Encoding new text applies these rules in order to a character-split word. The procedure is straightforward, but the ordering constraint makes it subtly different from a simple dictionary lookup. You cannot look up the best segmentation independently; you must apply rules sequentially, because each rule may enable the next.

The formal encoding procedure works as follows. For each word in the input text, split the word into individual characters. Then iterate through the merge rules in the order they were learned. For each rule $(a, b)$, scan the current token sequence from left to right and replace every adjacent occurrence of the pair $(a, b)$ with the merged token $ab$. Continue until all rules have been applied or the token sequence contains only a single token.

This procedure has an important efficiency property: you apply each rule exactly once per word, in a single left-to-right scan. You do not need to restart from the beginning after each merge. The result is that encoding a word with $R$ merge rules takes $O(R \cdot L)$ time, where $L$ is the initial length (number of characters) of the word.

1. Start with the word split into individual characters.
2. For each merge rule $(a, b)$ in the order it was learned: scan the token sequence left-to-right and replace every occurrence of the adjacent pair $(a, b)$ with the merged token $ab$.
3. Continue until all rules have been applied.

The ordering constraint is essential. Rules learned later may only apply once earlier merges have combined characters into their expected inputs. If rule 5 merges "lo" into a single token, rule 15 might merge "lo" and "w" into "low". Rule 15 can only fire after rule 5 has already created the "lo" token.

BPE handles novel words gracefully by decomposing them into the subword units it knows. "slowest" is never in the training corpus, but BPE breaks it into recognizable pieces using whatever merges apply. This is the essential advantage over word-level tokenization, which would assign each unknown word the same [UNK] token and lose all information. With BPE, the model receives the subword pieces as input and can potentially reason about the word's structure based on those pieces, even if the full word was never seen during training.

The ordering of merge rules is a fundamental property of BPE encoding, and it creates a dependency chain that must be respected. Consider a simple example with two rules: rule 1 merges e and w into ew, and rule 2 merges ew and s into ews. When encoding the word "news":

• Start: ['n', 'e', 'w', 's']
• After rule 1: ['n', 'ew', 's']
• After rule 2: ['n', 'ews']

If we applied rule 2 before rule 1, there would be no ew token for it to act on, and we would get ['n', 'e', 'w', 's'] instead. The rules form a dependency chain, and the training order captures those dependencies.

This property has a subtle implication: BPE encoding is not the same as finding the "best" segmentation of a word according to the vocabulary. It is specifically the segmentation that results from applying the learned rules in order. For the same vocabulary, different orderings of the merge rules would produce different encodings. The training order and the vocabulary together define the model.

Decoding is trivial: concatenate all tokens, removing the </w> marker (or using the boundary marker to infer where spaces belong). There is no ambiguity in reconstruction because BPE encoding is a deterministic, lossless transformation. Every encoding step can be reversed by joining the characters that were separated, so the original text is always perfectly recoverable.

This losslessness is a property BPE inherits from its data compression origins. In compression, you need to be able to reconstruct the original input exactly. In tokenization, this means that no information is lost during the encode-decode cycle, which is important for tasks like text generation where the model's output tokens must be converted back to readable text.

In production tokenizers, word boundary information is encoded using a prefix convention rather than an end-of-word marker. GPT-2 uses a special Unicode character ($\text{Ġ}$, U+0120) prepended to any token that begins a word. This lets the decoder reconstruct spaces: wherever a $\text{Ġ}$ appears, insert a space before that token. SentencePiece uses the underscore prefix $\text{▁}$. These conventions are equivalent in function; they differ only in how boundary information is attached to tokens.

The choice of prefix-based rather than suffix-based boundary marking matters for one practical reason: it affects how token IDs cluster in the embedding space. When the word "cat" appears at the beginning of a sentence (preceded by a space) and in the middle of a sentence, it gets the same token if you use prefix marking. With suffix marking, the "cat" in both positions gets the same token. The difference matters at sentence boundaries and after punctuation, where spacing conventions interact with the tokenization.

Let's trace BPE from start to finish on a tiny corpus to make every step concrete. We will use a corpus of six words: "low", "lower", "lowest", "new", "newer", "newest", each appearing once. Working through this example by hand is the single best way to build an accurate mental model of what the algorithm does.

Before running the code, it helps to reason about what we expect to happen. The corpus has six words sharing two roots: "low" and "new". Both roots appear in bare form and with the suffixes "-er" and "-est". The pairs "l+o", "o+w", "n+e", "e+w" should appear frequently because they occur in every word of their respective families. The suffix pairs "e+r" and "e+s", "s+t" should also appear in three words each. We should see the algorithm discover these patterns in roughly this order.

Working through this trace teaches you to see BPE from the algorithm's perspective. In the first step, it finds the highest-count pair across all words weighted by frequency. Notice how words that share character sequences contribute their full frequency counts to those pairs. Common character bigrams like "ew" (appearing in "new", "newer", "newest") merge early because they appear in three distinct words. Shared root sequences like "low" get consolidated as more rules accumulate. By step 8, familiar morphological units like "er", "est", "new", and "low" have emerged as single tokens, without any explicit knowledge of English grammar.

The key insight from tracing these steps is that BPE is discovering statistical redundancy, and linguistic structure is a consequence of that statistical redundancy. The reason "er" and "est" emerge as tokens is not that the algorithm knows they are suffixes; it is that English uses those suffix patterns extremely frequently. The algorithm's blindness to linguistic concepts is exactly what makes it generalize: the same process that finds "er" in English will find "-chen" (diminutive) in German and "-tion" cognates across Romance languages.

Let's build a complete, self-contained BPE tokenizer class. This version handles the full pipeline: training, encoding to token strings, encoding to integer IDs, and decoding. Building a complete class is valuable because understanding every component makes it much easier to debug issues when you use production tokenizers.

The implementation follows the same algorithmic steps we traced above, packaged into a clean interface. The train method builds word frequencies, identifies the base character set, and runs the merge loop. The tokenize method applies merge rules to new text. The encode and decode methods handle the integer ID layer consumed by most models.

Even "unrecognized" decomposes into meaningful subpieces. The tokenizer has never seen this word, but it applies every merge rule that matches and falls back to individual characters for any remaining unseen bigrams. The decoding is always lossless: concatenating the tokens reconstructs the original lowercase text exactly. Notice that the integer IDs assigned to tokens are stable across calls, which is what makes it possible for a neural network to learn consistent embeddings for each token.

The main parameters to understand when using a BPE tokenizer are:

• vocab_size: The total number of tokens in the vocabulary, including base characters and all merged tokens. This is the single most important hyperparameter. Larger values produce shorter sequences but require more embedding parameters. Typical production models use 30,000 to 100,000 tokens.
• num_merges: Derived from vocab_size as $V - |C|$, where $|C|$ is the number of base characters. You rarely set this directly.
• Corpus size and domain: Merge rules reflect the statistical patterns of the training text. A code corpus produces different rules than a news corpus. Domain mismatch between the tokenizer's training text and the model's input text can hurt downstream performance.

Vocabulary size is where practitioners most often need to make a principled choice. The tradeoff operates along two axes simultaneously: sequence length and parameter count. Getting this balance right matters for training efficiency, inference cost, and downstream model quality.

Sequence length decreases as vocabulary size grows. A vocabulary of 1,000 tokens might encode a word like "computational" as 7 pieces, while a vocabulary of 50,000 might represent it as a single token. Shorter sequences are cheaper to process in transformers because attention is quadratic in sequence length. Every token you eliminate from the average sequence reduces inference cost. For models that process long documents, this effect is particularly significant: a 10% reduction in average sequence length translates directly to a roughly 20% reduction in attention computation.

Embedding parameters increase with vocabulary size. Each token requires a row in the embedding matrix. For a model with hidden dimension 4,096, a vocabulary of 50,000 tokens requires a 50,000 $\times$ 4,096 matrix with about 200 million parameters, just for the input embeddings. Doubling the vocabulary doubles this cost. For rare tokens that appear only a handful of times during training, these parameters may be poorly learned, effectively wasting capacity.

The practical sweet spot for most monolingual English models is 30,000 to 50,000 tokens. GPT-2 and RoBERTa both use approximately 50,000. BERT uses 30,522 (through WordPiece, a BPE variant). Models targeting multiple languages or code often use larger vocabularies. GPT-4's tokenizer uses over 100,000 tokens to accommodate the linguistic diversity of its training data.

The trend toward larger vocabularies in more recent models is not accidental. As models scale up and are deployed more broadly, the cost of a large embedding matrix becomes relatively smaller compared to the attention and feedforward layers, while the benefit of fewer tokens per sequence becomes relatively larger. LLaMA 3's jump to 128,256 tokens reflects both the model's multilingual ambitions and the practical observation that at billion-parameter scale, the embedding table is a small fraction of total parameters.

Beyond vocabulary size, a few other decisions shape how a BPE tokenizer behaves. These choices are often invisible when you use a pre-trained tokenizer, but they have significant effects on tokenization quality and downstream model performance. Understanding them is important both for evaluating existing tokenizers and for training new ones.

Production BPE tokenizers do not operate on raw Unicode streams. They first apply a pre-tokenization step that splits text into rough word-level chunks, then apply BPE within each chunk. GPT-2 uses a regex that splits on whitespace and punctuation while preserving contractions and common abbreviations. Pre-tokenization prevents BPE merges from bleeding across word boundaries, which would produce tokens like "the" + "cat" merged together, spanning two words.

Pre-tokenization decisions have cascading effects. The GPT-2 regex treats leading spaces as part of the word, so "cat" and " cat" (with a preceding space) produce different tokens. This means the token for "cat" at the start of a sentence is different from the token for "cat" in the middle of a sentence. While this seems like a quirk, it provides the model with information about word position that it might not otherwise have. However, it also means that prompts with and without a leading space can produce different token sequences, which has occasionally caused unexpected behavior in applications.

Think of pre-tokenization as drawing hard boundaries that BPE merges cannot cross. Without these boundaries, BPE might decide that merging the final "e" of "the" with the initial "c" of "cat" is beneficial, because "e c" is a common sequence in English. That merge would be semantically useless and would clutter the vocabulary with cross-word artifacts. Pre-tokenization prevents this by treating word boundaries as inviolable.

A significant design choice made by GPT-2 was to operate on bytes rather than Unicode characters. Instead of initializing the vocabulary with potentially tens of thousands of possible Unicode code points, byte-level BPE starts with exactly 256 base tokens (one per byte value). This guarantees that any sequence of bytes, regardless of encoding, can be represented without unknown tokens.

Byte-level BPE has become the standard for large language models precisely because it is universal: you can feed any text, including emojis, mathematical symbols, CJK characters, or arbitrary binary content, and the tokenizer will always produce a valid encoding. The tiktoken library used by OpenAI's models implements byte-level BPE. The tradeoff is that non-ASCII characters may require multiple bytes, and therefore multiple tokens, to represent. A single Chinese character encoded in UTF-8 typically uses three bytes, so it initially costs three tokens. However, common characters appear frequently enough that BPE learns to merge those bytes into single tokens, recovering efficiency for high-frequency characters.

The key insight behind byte-level BPE is that it separates the question of "what can be represented" from "what is represented efficiently". All byte sequences can always be represented (using individual byte tokens as a fallback), while frequently occurring patterns are represented compactly through learned merges. This is a more principled solution than Unicode-character BPE, which can encounter truly unknown tokens for rare Unicode code points that never appeared in the training corpus.

The merge rules learned by BPE reflect the language of the training text. A tokenizer trained on English news articles will tokenize source code inefficiently, spending many tokens on common keywords like "function" that would merit their own token in a code-focused vocabulary. A multilingual tokenizer trained on 100 languages must allocate vocabulary space across all of them, which typically means each language gets fewer dedicated tokens than a monolingual tokenizer would assign it.

In practice, this means that using a pre-trained tokenizer for a domain very different from its training data can noticeably increase inference cost. A model tokenizer trained on general English may require six tokens for a common SQL keyword that would be a single token in a code-specialized tokenizer. This inefficiency compounds when processing long documents: a 2,000-word legal contract might require 50% more tokens when processed by a general tokenizer versus a legal-domain tokenizer, directly increasing inference cost by 50%.

This mismatch problem has motivated a growing practice of training domain-specific tokenizers for specialized models. Code models like Codex use tokenizers trained predominantly on code repositories, which allocate vocabulary space to common code patterns like indentation sequences, common variable names, and language keywords. Medical models may train tokenizers on clinical notes and scientific papers to ensure that medical terminology gets efficient representation.

You will rarely implement BPE from scratch in production. The Hugging Face tokenizers library provides a fast Rust implementation that handles byte-level BPE, special tokens, and all the edge cases. Here's how to train a tokenizer that matches the GPT-2 architecture:

The Hugging Face tokenizer produces the same algorithmic behavior as our implementation but with dramatically better performance: it can tokenize hundreds of megabytes per second on a single CPU core, making it practical for preprocessing large training datasets. For training a model on a hundred billion tokens, the difference between a Python tokenizer and the Rust-based implementation can mean the difference between preprocessing taking hours versus weeks.

Notice that the byte-level tokenizer represents some characters with multi-character tokens like "Ġ" (the Ġ prefix marks word-initial tokens). This is the GPT-2 convention: the Ġ character encodes the space that precedes a word, so " cat" becomes "Ġcat" as a single token. The decoder understands this convention and converts Ġ back to a space during decoding. Tokens without the prefix represent subword continuations that do not start at a word boundary.

Let's directly compare how BPE, character-level, and word-level tokenization handle the same inputs. This comparison makes concrete why BPE is the preferred choice and gives you intuition for when each approach might be suboptimal.

The key dimensions to compare are: sequence length (shorter is better for compute), handling of novel words (graceful decomposition versus hard fallback to UNK), and information preservation (what structural information survives tokenization). Character-level tokenization preserves all information but produces very long sequences. Word-level tokenization produces short sequences for known words but loses all information about unknown words. BPE provides a tunable tradeoff between these extremes.

The chart makes the tradeoffs tangible. Character-level tokenization scales linearly with character count: "antidisestablishmentarianism" requires 28 tokens. Word-level tokenization is compact for known vocabulary but assigns a fixed [UNK] penalty to any unseen word, losing all morphological information. BPE finds the middle ground: it produces more tokens than word-level for common words, but fewer than character-level for long words, while preserving structural information for unknown words instead of discarding it.

The "C19test" example is particularly instructive because it mixes uppercase letters, numbers, and alphabetic characters in a way that no word-level vocabulary would anticipate. Word-level tokenization collapses it to UNK. Character-level tokenization handles it correctly but expensively. BPE applies whatever merges apply (which will be limited for such an unusual string) and falls back to characters where necessary, naturally handling the edge case without any special treatment.

BPE's practical success should not obscure its limitations. Understanding where BPE falls short helps you make better decisions about when to use it as-is, when to modify it, and when to consider alternatives.

Greedy training is suboptimal. The algorithm always merges the single most frequent pair at each step. This local optimum may not be the global optimum: a pair that is moderately frequent now might enable many more merges in later steps if merged first. Think of it like building a house by always laying the single most available brick, regardless of where it will do the most structural good. The unigram language model tokenizer (covered in the next chapter) addresses this by framing tokenization as probabilistic inference, which allows globally better vocabulary selection. In practice, the gap between BPE and unigram vocabularies is small on standard benchmarks, but the theoretical limitation is real.

Tokenization is not universal. Vocabulary size calibrated for English may fragment other languages much more aggressively. Research has shown that some non-Latin-script languages require four to ten times as many tokens as English to express equivalent content using a BPE tokenizer trained predominantly on English text. Arabic, Thai, and many African languages are particularly disadvantaged because their morphological complexity and script differences mean that few of the learned merges apply. This has equity implications: models cost more to run on those languages and have been observed to perform worse on tasks requiring longer contexts, because the same semantic content occupies many more token positions.

Sensitivity to pre-tokenization. The decision of where to split before applying BPE merges significantly affects what gets tokenized as a single unit. Numbers, dates, URLs, and code all behave differently depending on how the pre-tokenization regex is written. The GPT-2 tokenizer's treatment of leading spaces has occasionally produced surprising tokenization behavior in downstream applications, particularly for sentence-initial tokens. More significantly, the way numbers are split affects arithmetic performance in language models: models that receive each digit as a separate token can more easily learn positional arithmetic than models where multi-digit numbers get fused into opaque tokens.

No natural token boundary at morpheme level. BPE optimizes for compression, not linguistic coherence. Morphologically meaningful units like "pre-", "-tion", and "-ness" emerge when they are frequent enough, but there is no guarantee. Rare morphemes may be split across tokens in ways that make morphological generalization harder for the downstream model. A word like "reconfiguration" might be split into "recon", "figur", "ation" rather than the morphologically meaningful "re", "config", "ur", "ation". The model must learn to combine these tokens into the right meaning, which requires more training examples than if the tokenization had respected morpheme boundaries.

Inconsistent handling of related words. Because BPE applies merges greedily and the order of merges depends on frequency, it is possible for morphologically related words to receive very different tokenizations. "play" might be a single token, "plays" might be "play" + "s", but "played" might be "play" + "ed" or "play" + "ed" or even "pla" + "yed" depending on what merges were learned. This inconsistency can make it harder for models to generalize morphological patterns.

Despite these limitations, BPE's contribution to modern NLP is hard to overstate. Before subword tokenization became standard, multilingual models required either enormous word-level vocabularies or per-language models. BPE made it practical to train a single model on text in dozens of languages, because any word in any language can always be expressed as a sequence of known subword tokens. The compression efficiency means models can use shorter sequences, reducing the quadratic cost of attention. And the stability of the algorithm, its speed, and its lack of linguistic assumptions made it easy to adopt widely.

The algorithms that followed, including WordPiece (BERT) and the unigram language model (SentencePiece), are refinements on BPE's core insight. They change the criterion for choosing which pairs to merge and the inference procedure for encoding, but the fundamental structure of a vocabulary built from increasingly larger subword units remains the same. BPE's lasting influence appears in the models that use it directly and in its role establishing subword tokenization as the universal standard for neural language modeling.

Byte Pair Encoding solves the vocabulary problem by iteratively discovering which character sequences are frequent enough to warrant their own token. Starting from individual characters and applying greedy merge operations, BPE constructs a vocabulary of subword units that provides compact representations for common patterns and graceful decomposition for rare or novel words. Its success comes from a fortunate alignment: optimizing for compression naturally recovers linguistic structure, because the patterns most worth representing compactly are the patterns that carry the most consistent meaning.

The key ideas to take away from this chapter are:

• Training runs in two steps: count adjacent pair frequencies, merge the most frequent pair, repeat until the vocabulary reaches the target size. Each merge captures one frequency pattern from the training corpus.
• Encoding applies merge rules in the order they were learned. The ordering encodes dependency: later rules can only fire after earlier rules have created their expected inputs.
• Decoding is trivial concatenation. BPE is lossless: encoding followed by decoding always reconstructs the original text.
• Vocabulary size is the primary hyperparameter. Larger vocabularies reduce sequence length (lowering compute cost) but increase embedding parameters and may include tokens with insufficient training signal.
• Byte-level BPE extends the approach to operate on raw bytes, guaranteeing universal coverage with no unknown tokens. This is the standard used in GPT-2, GPT-3, and GPT-4.
• Pre-tokenization defines boundaries that merges cannot cross, preventing cross-word artifacts and encoding word-position information in the token representations.
• Domain and language matter. A tokenizer trained on English news articles will tokenize code, medical text, or low-resource languages inefficiently. Specialized models often use specialized tokenizers.

In the next chapter, we will examine WordPiece, BERT's tokenizer. WordPiece modifies the merge criterion: instead of always merging the most frequent pair, it maximizes the likelihood of the training corpus under a unigram language model. This subtle change leads to different vocabulary choices and introduces the ## prefix convention for subword continuations, which you have likely seen when inspecting BERT tokenizer outputs.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about Byte Pair Encoding.