Subword Tokenization and Byte-Pair Encoding

A word-level vocabulary assigns one embedding vector to each distinct word type seen during training and maps everything else to an out-of-vocabulary token, ``. This is catastrophic for morphologically rich languages (Turkish, Finnish), for domains with heavy neologism (biomedical text, social media), and for any deployed system that will eventually see words it never trained on — which is all deployed systems. Subword tokenization instead defines the vocabulary over substrings: a mix of whole common words, frequent word-pieces (prefixes, suffixes, stems), and individual characters as a universal fallback.

Byte-Pair Encoding is the dominant algorithm for learning such a vocabulary. It originates from a 1994 byte-level compression trick (replace the most common pair of adjacent bytes with an unused byte, repeat) and was repurposed for NLP by Sennrich, Haddow, and Birch in 2016 for neural machine translation. The key terminology: a symbol is any vocabulary unit (initially a character, later a merged subword); a pair is two adjacent symbols within a word; a merge rule records that a specific pair should be fused into one new symbol; and the merge table is the ordered list of all merge rules learned from a training corpus. Learning BPE means producing this merge table; encoding text means applying it. Crucially, BPE decouples training-time vocabulary construction from inference-time tokenization. The merges are learned once, offline, on a large corpus by repeatedly finding the globally most frequent adjacent symbol pair and merging every occurrence of it. At inference time, tokenizing a brand-new string does not recount frequencies — it replays the same merge rules in the same learned order, greedily, until no further merge applies. This makes encoding deterministic, fast, and consistent between training and deployment, which is exactly the property a production NLP pipeline needs.

BPE has two distinct phases: learning the merges (done once on a training corpus) and encoding text (done every time on new input, using the fixed merge table). Both operate on words pre-split into characters, typically with an explicit end-of-word marker so that suffix merges cannot silently bleed across word boundaries.

Phase 1 — Learning merges. Start by pre-tokenizing the corpus into words (usually by whitespace) and representing each distinct word as a sequence of characters, with a special end-of-word symbol appended (commonly written ``). Maintain a frequency table of these word-sequences. Repeat for `k` iterations (`k` is the target number of merges, i.e., the vocabulary-size hyperparameter): count the frequency of every adjacent symbol pair across all words (weighted by word frequency), pick the single most frequent pair, merge it everywhere it occurs, and record the rule. Stop after `k` merges or when no pair occurs more than once.

Phase 2 — Encoding text. To tokenize an unseen string: split it into words, split each word into characters plus the end-of-word marker, and then apply the learned merge rules in the order they were learned — at each step, scan for the earliest-learned rule whose pair currently appears anywhere in the word, apply it everywhere in that word, and repeat until no rule applies. The final symbol sequence is the token sequence fed to the model's embedding lookup. ```

# ---------- PHASE 1: LEARN MERGES ---------- function LEARN_BPE(corpus, num_merges):

# 1. Pre-tokenize into words, count word frequencies word_freq = {} # word (string) -> count for word in whitespace_split(corpus): word_freq[word] += 1

# 2. Represent each word as a list of symbols: chars + end marker vocab = {} # tuple(symbols) -> frequency for word, freq in word_freq.items(): symbols = list(word) + [""] vocab[tuple(symbols)] = freq merges = [] # ordered list of learned rules for i in range(num_merges):

# 3. Count all adjacent symbol pairs, weighted by word frequency pair_counts = {} for symbols, freq in vocab.items(): for j in range(len(symbols) - 1): pair = (symbols[j], symbols[j+1]) pair_counts[pair] = pair_counts.get(pair, 0) + freq if not pair_counts: break # no pairs left to merge best_pair = argmax(pair_counts, key=pair_counts.get) if pair_counts[best_pair] < 2: break # stopping rule: no repeated pair merges.append(best_pair) # record rule i

# 4. Apply the merge to every word containing this pair new_vocab = {} merged_symbol = best_pair[0] + best_pair[1] for symbols, freq in vocab.items(): merged = merge_pair_in_sequence(symbols, best_pair, merged_symbol) new_vocab[merged] = new_vocab.get(merged, 0) + freq vocab = new_vocab return merges # the learned merge table function merge_pair_in_sequence(symbols, pair, merged_symbol): out = [] j = 0 while j < len(symbols): if j < len(symbols) - 1 and (symbols[j], symbols[j+1]) == pair: out.append(merged_symbol) j += 2 else: out.append(symbols[j]) j += 1 return tuple(out)

# ---------- PHASE 2: ENCODE NEW TEXT ---------- function ENCODE_BPE(text, merges): merge_rank = { pair: idx for idx, pair in enumerate(merges) } # earlier = higher priority tokens = [] for word in whitespace_split(text): symbols = list(word) + [""] while len(symbols) > 1:

# find the pair with the smallest merge_rank (learned earliest) pairs = [(symbols[j], symbols[j+1]) for j in range(len(symbols)-1)] candidate = None for p in pairs: if p in merge_rank: if candidate is None or merge_rank[p] < merge_rank[candidate]: candidate = p if candidate is None: break # no learned merge applies; stop merged_symbol = candidate[0] + candidate[1] symbols = merge_pair_in_sequence(symbols, candidate, merged_symbol) tokens.extend(symbols) return tokens ``` Two design details matter in practice. First, the end-of-word marker `` prevents a merge learned inside one word (e.g., `"er"` at the end of "faster") from incorrectly firing across word boundaries (e.g., inside "erode"), since the marker makes suffix-position characters distinguishable from prefix-position characters. Second, at encoding time an unseen character (an emoji, a foreign script) simply never matches any merge rule and passes through as a singleton character token — this is precisely why BPE has no unknown-token problem: the character (or byte) inventory is a superset of anything that can appear.

Learning-phase complexity. Let `V` be the number of distinct words in the corpus, `L` the average word length, and `k` the number of merges to learn. A naive implementation recomputes all pair counts from scratch at every iteration: each pass over the vocabulary costs `O(V·L)`, and doing this `k` times gives `O(k·V·L)`. Production implementations avoid full recomputation by maintaining a priority queue of pair counts and only updating counts for words that actually contained the merged pair, reducing the practical cost substantially (close to `O((V·L + k)·log(V·L))` with an indexed heap), though the worst-case bound remains governed by how many words are touched per merge. Space is `O(V·L)` to hold the working symbol sequences plus `O(k)` for the merge table.

Encoding-phase complexity. For a single word of length `L`, encoding applies at most `L − 1` merges (each merge strictly reduces the symbol count by one, and a word of `L` characters can be merged down to 1 symbol at most `L−1` times). With a hash map from pair to rank, finding the best applicable pair among the (at most `L−1`) adjacent pairs costs `O(L)` per merge step in a naive scan, giving `O(L²)` per word; with a priority-queue-based implementation this drops to `O(L log L)`. Since real words are short (bounded by a small constant in practice), encoding is effectively linear in the length of the input text — this is why BPE tokenization is cheap enough to run at both training and serving time, including inside per-request inference pipelines.

Correctness argument. The central claim is that greedy frequency-based merging is a consistent, deterministic, total function from raw text to token sequences, and that it strictly reduces sequence entropy relative to characters while remaining strictly more expressive than a fixed word vocabulary. Three invariants support this: 1. Totality (no OOV). The base alphabet (characters, or bytes in byte-level BPE) is fixed and complete: every string is expressible as a sequence of base symbols before any merges are applied. Since merges only ever combine existing symbols and encoding falls back to leaving a symbol unmerged when no rule matches, every input string maps to some finite token sequence — the domain of the encoding function is all of Σ\*, never partial. This is the formal reason subword tokenization eliminates ``. 2. Determinism and training/inference consistency. Because merge rules are applied in a strict, fixed priority order (the order they were learned), encoding is a deterministic function of the merge table alone — the same string always tokenizes the same way, and the tokenization used at inference time exactly matches the statistical assumptions baked into the merge table during training. There is no separate "encoding heuristic" that could diverge from what was learned. 3. Monotonic frequency justification (why greedy is reasonable). BPE is a greedy approximation to the (NP-hard, in general) problem of choosing `k` merge operations to minimize the total number of tokens needed to represent the corpus — this is essentially a variant of the optimal grammar-based compression problem. Greedily merging the globally most frequent pair at each step is the natural local-search heuristic: it guarantees that the single largest possible reduction in symbol count is taken at each round, since replacing the `f`-frequent pair `(a,b)` with a new symbol removes exactly `f` adjacent-pair occurrences from the corpus (one merge event per occurrence). It does not guarantee global optimality — a different sequence of merges could in principle compress more — but it is efficient, incremental, and empirically close to optimal for natural-language statistics, which are heavily Zipfian (a small number of pairs dominate frequency at every step, so the greedy choice is usually also the dominant contributor to compression).

Honest tradeoffs. Vocabulary size `k` is a hyperparameter, not a discovered constant: small `k` (e.g., a few thousand) yields short vocabularies but long token sequences (more compute per sentence, since sequence length directly drives self-attention cost, which is quadratic in sequence length for a standard Transformer); large `k` (e.g., 50,000+) yields short sequences but a large embedding/softmax matrix and sparser statistics for rare subwords. There is no free lunch — practitioners tune `k` per model scale and language mix. BPE also has no notion of linguistic morphology; it merges by raw frequency, so it can split words in ways that are frequency-optimal but linguistically odd (see pitfalls below).

Take the toy corpus from the figure: `low` (freq 5), `lower` (freq 2), `newest` (freq 6), `widest` (freq 3), learning 5 merges.

The learned merge table, in order, is: `(e,s)`, `(es,t)`, `(l,o)`, `(lo,w)`, `(n,e)`.

Now encode an unseen word: "lowest". Split into characters: `l o w e s t `. Apply rules in learned order, checking at each pass which rule's pair is present anywhere in the sequence:

• Rule 1 `(e,s)` matches (`e`,`s` are adjacent) → `l o w es t `
• Rule 2 `(es,t)` matches → `l o w est `
• Rule 3 `(l,o)` matches → `lo w est `
• Rule 4 `(lo,w)` matches → `low est `
• Rule 5 `(n,e)` — no `n` in this word, skip.
• No further rules match.

Final tokenization: `low` + `est</w>` — two tokens, both of which were never seen as whole words in training with this exact combination ("lowest" itself never appeared), yet the model correctly recognizes it as "low" + superlative-like suffix "est," a linguistically sensible split that emerged purely from frequency statistics, with zero unknown tokens.

Contrast case: an out-of-corpus word with novel characters, "naïve" (with the accented ï). If the training corpus never contained "ï," the character still enters the base alphabet at encoding time as a singleton symbol (byte-level BPE guarantees this by operating over UTF-8 bytes rather than characters, so any Unicode input decomposes into known bytes). No rule in the table mentions `ï`, so it simply passes through unmerged: `n a ï v e ` might tokenize as `n`, `a`, `ï`, `v`, `e` — verbose, but never a failure. This is the totality invariant from the correctness section made concrete: coverage degrades gracefully to character-level granularity rather than failing outright.

Byte-Pair Encoding as a compression method predates its use in NLP by two decades. Philip Gage introduced it in 1994 as a simple, general-purpose data-compression scheme: repeatedly replace the most common byte pair with an unused byte. It was Rico Sennrich, Barry Haddow, and Alexandra Birch who, in 2016, recognized that the same greedy-merge idea — applied to characters rather than raw bytes, and stopped early rather than run to convergence — produced exactly the kind of open-vocabulary subword segmentation that neural machine translation systems desperately needed, since NMT models (like all neural sequence models before and since) require a fixed-size output vocabulary for the softmax layer.

Every major neural machine translation system since 2016 uses subword tokenization to sidestep the fixed-vocabulary bottleneck, and BPE (or a close variant) is the default choice in essentially all modern large language models: GPT-family models use byte-level BPE, BERT uses WordPiece, and T5, ALBERT, and many multilingual models use Unigram/SentencePiece. The technique is what allows a single trained model to gracefully handle misspellings, code, rare technical terms, emoji, and mixed-script text without ever emitting an unknown-token placeholder. It is also the tokenization layer that feeds directly into the embedding matrices consumed by transformer encoders, making it a load-bearing prerequisite for everything downstream, including the Contextual Embeddings produced by BERT-style masked language models and the Attention Mechanism layers that operate on the resulting token sequences. Production systems additionally rely on the determinism of BPE encoding for reproducibility: search engines, translation APIs, and chat assistants all depend on the guarantee that identical input text always tokenizes identically, both during training and at serving time.

Ask the tutor: How would BPE-learned subword boundaries change if trained jointly across multiple languages instead of one?