How Byte Pair Encoding Builds AI Subword Vocabularies

Byte Pair Encoding (BPE) is a foundational tokenization algorithm used in modern artificial intelligence language models to bridge the gap between character-level and word-level text processing. Originally developed as a data compression technique, BPE builds a highly efficient subword vocabulary by starting with individual characters and iteratively merging the most frequently occurring adjacent pairs. This article explores the step-by-step mechanics of the BPE algorithm, demonstrating how it initializes vocabularies, calculates pair frequencies, executes iterative merges, and ultimately enables language models to process rare and unknown words without exhausting computational memory.

The Tokenization Challenge in Language Models

Language models cannot understand raw text; they require text to be broken down into numerical representations called tokens. Historically, models relied on word-level or character-level tokenization. Word-level tokenization assigns a unique ID to every word, which leads to massive vocabulary sizes and fails when the model encounters out-of-vocabulary (OOV) words. Character-level tokenization uses a tiny vocabulary of individual letters, solving the unknown word problem, but creates excessively long sequences that are computationally expensive to process and strip away the semantic meaning of words.

Byte Pair Encoding solves both problems by creating a subword vocabulary. Common words remain intact as single tokens, while rare words are broken down into meaningful subword units, such as prefixes, roots, and suffixes.

Step 1: Corpus Preparation and Base Initialization

The BPE algorithm begins with a large training corpus of text. Before counting any characters, the text is pre-tokenized into words, typically by splitting on whitespace and punctuation.

Next, the algorithm counts the frequency of every unique word in the corpus. To ensure the model knows where words end, a special end-of-word symbol (often represented as </w>) is appended to each word. This symbol is crucial because it distinguishes between a subword that appears at the beginning of a word (like "st" in "star") and one that appears at the end (like "st</w>" in "fast").

Finally, every word is split into its individual characters. The initial vocabulary—called the base vocabulary—consists solely of all the unique individual characters present in the text, plus the special end-of-word symbol.

Step 2: Counting Adjacent Character Pairs

Once the words are broken down into sequences of individual characters, the iterative process begins. The algorithm scans the entire pre-tokenized corpus and counts the frequency of every adjacent pair of symbols.

For example, if the word "low" appears 5 times in the corpus, it is represented as l o w </w>. The adjacent pairs within this word are (l, o), (o, w), and (w, </w>), and each of these pairs gets a count of 5 added to its total frequency across the entire dataset.

Step 3: Iteratively Merging the Most Frequent Pairs

After tallying all adjacent pairs across the corpus, BPE identifies the single pair with the highest frequency. The algorithm then takes two actions:

  1. It merges these two symbols together into a single, new subword symbol across all occurrences in the corpus.
  2. It adds this newly created subword symbol to the vocabulary.

This completes one iteration. In the next step, the algorithm recalculates the frequencies of all adjacent pairs, treating the newly merged subword as a single unit. If (e, s) was merged into es in the first round, the next round might find that (es, </w>) is now the most frequent pair, merging them into es</w>.

Step 4: Concrete Example of the BPE Loop

To visualize the iterative merging process, consider a simplified corpus containing only four words and their frequencies:

  • low </w> (5 times)
  • lower </w> (2 times)
  • newest </w> (6 times)
  • widest </w> (3 times)

Base Vocabulary: l, o, w, e, r, n, s, t, i, d, </w>

Iteration 1: The algorithm counts all adjacent pairs. The pair (e, s) appears 6 times in "newest" and 3 times in "widest", for a total of 9 occurrences. The pair (s, t) also appears 9 times. Assuming the algorithm picks (e, s) first, they are merged into es.

  • New Vocabulary Addition: es
  • Updated Corpus: n e w es t </w> (6), w i d es t </w> (3)

Iteration 2: The algorithm recounts the pairs. Now, the pair (es, t) appears 9 times (6 in "newest", 3 in "widest"). They are merged into est.

  • New Vocabulary Addition: est
  • Updated Corpus: n e w est </w> (6), w i d est </w> (3)

Iteration 3: The pair (est, </w>) now appears 9 times. They are merged into est</w>.

  • New Vocabulary Addition: est</w>
  • Updated Corpus: n e w est</w> (6), w i d est</w> (3)

Iteration 4: Looking at the remaining pairs, (l, o) and (o, w) both appear 7 times (5 in "low", 2 in "lower"). The algorithm merges (l, o) into lo.

  • New Vocabulary Addition: lo
  • Updated Corpus: lo w </w> (5), lo w e r </w> (2)

If the process stopped here, the model would know the base characters plus the subwords es, est, est</w>, and lo.

Stopping Conditions and Vocabulary Size

The iterative loop does not run forever. Before training begins, developers define a hyperparameter: either the maximum number of merge operations to perform or a target vocabulary size (e.g., 32,000 or 50,000 tokens).

The target vocabulary size is equal to the size of the base character vocabulary plus the number of merge operations. Once the algorithm reaches this predetermined limit, it stops merging. The final output is a fixed vocabulary list and an ordered list of merge rules.

Applying BPE to New Text

When a trained AI language model encounters new text during inference, it does not recount frequencies. Instead, it splits the new input words into individual characters and applies the learned merge rules in the exact order they were learned during training.

If the model encounters an unfamiliar word like "lowest", it breaks it into l o w e s t </w>. Using the rules from the example above, it merges e and s into es, then est, then est</w>, and finally l and o into lo (and eventually low if training had continued). The unknown word "lowest" is successfully tokenized into known subword components: low and est</w>. Because both tokens carry semantic weight—representing a root concept and a superlative suffix—the AI can deduce the meaning of the word despite never having seen it whole.

Byte-Level BPE in Modern AI

While standard BPE operates on Unicode characters, a modern variation used by models like GPT-2, GPT-3, and GPT-4 is Byte-Level BPE. Because there are over 140,000 Unicode characters across global languages and emojis, a character-level base vocabulary can still be too large or miss rare symbols.

Byte-Level BPE converts text into UTF-8 bytes before running the algorithm. Because a byte can only have 256 possible values, the base vocabulary is guaranteed to be exactly 256 tokens. The iterative merging process then runs on adjacent bytes rather than characters, ensuring that the language model can process any text string, in any language, without ever producing an "unknown token" error.