Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Byte Pair Encoding › The BPE Encoding Algorithm

Michael BrenndoerferUpdated January 24, 20265 min read

Language AI HandbookAll chapters

Part 5 of 67Subword Tokenization

Chapter 29Byte Pair Encoding › The BPE Encoding Algorithm

Reading section 4 of 14 · The BPE Encoding Algorithm · 5 minSection 4 of 14 · 5 min

Section 4 of 14 · 5 min read

Byte Pair Encoding › The BPE Encoding AlgorithmOne section · Sections in this chapter4 / 14 ↓

Sections in this chapter14

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

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.

Start with the word split into individual characters.
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$ .
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.

In[13]:

Code

def encode_word(word, merge_rules):
    """Apply BPE merge rules to a single word (without end-of-word marker)."""
    tokens = list(word)
    for pair in merge_rules:
        i = 0
        while i < len(tokens) - 1:
            if tokens[i] == pair[0] and tokens[i + 1] == pair[1]:
                tokens = tokens[:i] + [pair[0] + pair[1]] + tokens[i + 2 :]
                # Don't advance i: the merged token might form a new eligible pair
            else:
                i += 1
    return tokens


def encode_text(text, merge_rules):
    """Encode a full string by encoding each word."""
    return [
        tok
        for word in text.lower().split()
        for tok in encode_word(word, merge_rules)
    ]

Let's test encoding on both in-vocabulary words and words that were never in the training corpus:

In[14]:

Code

test_words = {
    "Known words": ["low", "lower", "newest"],
    "Novel words": ["renew", "slowest", "unlowest"],
}

Out[15]:

Console

Known words:
---------------------------------------------
  low           →  ['lo', 'w']
  lower         →  ['lowe', 'r']
  newest        →  ['newe', 'st']

Novel words:
---------------------------------------------
  renew         →  ['r', 'e', 'ne', 'w']
  slowest       →  ['s', 'lowe', 'st']
  unlowest      →  ['u', 'n', 'lowe', 'st']

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.

Why Merge-Rule Order MattersLink Copied

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.

Encoding Determinism

BPE encoding is fully deterministic: given the same merge rules in the same order, the same input always produces the same token sequence. This determinism is important for reproducibility and for ensuring that the model's training data and inference inputs are processed identically. Some tokenization schemes, such as SentencePiece's BPE with dropout, introduce randomness during training by stochastically sampling from multiple valid segmentations. This regularization technique prevents the model from memorizing specific token sequences and can improve generalization to varied segmentations. But standard BPE encoding is always deterministic.