Byte-Pair Encoding

Byte-Pair Encoding (BPE) is a data-compression algorithm adapted for NLP that iteratively merges the most frequent adjacent token pairs in a corpus to build a subword vocabulary of a fixed target size. It matters because virtually every major language model — GPT, LLaMA, Mistral, CLIP — relies on BPE or a close variant to balance vocabulary coverage against sequence length without requiring a character-level or word-level extremes. The counterintuitive fact: BPE was originally invented in 1994 as a lossless text compression scheme with no connection to NLP; the entire modern LLM ecosystem rests on a compression trick repurposed two decades later.

The core insight

Every natural language contains far more unique word-forms than any fixed vocabulary can hold, yet character-by-character modeling loses the rich structure of morphology. BPE resolves this by learning a vocabulary of subword units — fragments like `un-`, `-ing`, `##tion` — that can compose into any word, seen or unseen. The algorithm is purely data-driven: start from individual bytes or characters, count adjacent pair frequencies, merge the most common pair into a new token, repeat until you hit your target vocabulary size. The "aha moment" is realizing that BPE simultaneously handles rare words (decomposed into known subwords), common words (absorbed as single tokens), and multilingual scripts — all from one greedy frequency-counting loop.

How It Works

Training Phase: Learning Merge Rules

Begin with a pre-tokenized corpus split into words (or Unicode code-points, or raw bytes for byte-level BPE). Each word is represented as a sequence of its constituent characters plus a special end-of-word marker. Count all adjacent character/token pairs across the entire corpus.

\quad \text{freq}(a, b) = \sum_{w \in \mathcal{C}} \text{count}(w) \cdot \mathbb{1}[(a,b) \subseteq w]

Explanation: The frequency of a pair $(a,b)$ is the total number of times that pair appears as adjacent tokens across all word occurrences in corpus $\mathcal{C}$ , weighted by each word's count. Here $\mathcal{C}$ is the corpus as a multiset of pre-tokenized words, $\text{count}(w)$ is how many times word $w$ occurs, and $\mathbb{1}[(a,b) \subseteq w]$ indicates whether the pair appears consecutively anywhere in $w$ 's current token sequence. Select the pair $(a^*, b^*)$ with maximum frequency and merge it into a new token $ab$ :

\quad (a^*, b^*) = \underset{(a,b)}{\arg\max}\ \text{freq}(a, b)

Explanation: This greedy selection picks the single most compressive merge at each step — the pair that, if fused, eliminates the most individual tokens from the corpus representation. Repeat equations [1]–[2] for $K$ steps. Each step appends one rule to the merge list and adds one new token to the vocabulary. The final vocabulary size is:

\quad |\mathcal{V}| = |\mathcal{V}_0| + K

Explanation: The vocabulary grows exactly by one token per merge step, so choosing $K$ directly controls final vocabulary size given the initial character/byte inventory $|\mathcal{V}_0|$ . Typical values: $|\mathcal{V}_0| \approx 256$ (bytes) or $\approx 6{,}000$ (Unicode characters), $K$ chosen so $|\mathcal{V}| \in [30\text{k}, 100\text{k}]$ .

Inference Phase: Encoding New Text

Given a new string, apply each merge rule from the ordered list greedily in rank order, scanning left-to-right. The encoding complexity for a word of length $n$ over $K$ merge rules is:

\quad T_{\text{encode}} = O(n \cdot K)

Explanation: In the naive implementation, each of the $K$ merge rules requires a linear scan over the current token sequence, giving quadratic cost in the worst case — motivating the priority-queue implementation used in production tokenizers. In practice, HuggingFace `tokenizers` uses a heap-based approach that reduces average complexity closer to $O(n \log n)$ .

Byte-Level BPE

GPT-2 introduced byte-level BPE: the initial vocabulary is exactly the 256 possible byte values. Every possible string is representable with zero unknown tokens:

\quad \forall s \in \Sigma^*,\ \text{BPE}(s) \neq \langle \text{UNK} \rangle

Explanation: Because any string decomposes into bytes and every byte is a valid token, byte-level BPE eliminates the out-of-vocabulary problem entirely, which is why GPT-2 onward never needs a special `[UNK]` token. --- ```python

# Minimal BPE training in pure Python (educational, not production) from collections import Counter, defaultdict import re def get_pairs(vocab: dict[str, int]) -> Counter: pairs = Counter() for word, freq in vocab.items(): symbols = word.split() for i in range(len(symbols) - 1): pairs[(symbols[i], symbols[i + 1])] += freq return pairs def merge_vocab(pair: tuple[str, str], vocab: dict[str, int]) -> dict[str, int]: new_vocab = {} bigram = re.escape(" ".join(pair)) pattern = re.compile(r"(? list[tuple[str, str]]:

# Initialize: split every word into characters + end marker vocab: dict[str, int] = Counter( " ".join(list(w) + [""]) for line in corpus for w in line.split() ) merges = [] for _ in range(num_merges): pairs = get_pairs(vocab) if not pairs: break best = max(pairs, key=pairs.get) vocab = merge_vocab(best, vocab) merges.append(best) return merges

# Usage corpus = ["low lower newest widest", "low low lower newest"] merges = train_bpe(corpus, num_merges=10) print(merges[:5])

# [('l', 'o'), ('lo', 'w'), ('e', 'r'), ('low', ''), ('n', 'e')] ``` ```python

# HuggingFace tokenizers — train a BPE tokenizer from scratch from tokenizers import Tokenizer from tokenizers.models import BPE from tokenizers.trainers import BpeTrainer from tokenizers.pre_tokenizers import Whitespace tokenizer = Tokenizer(BPE(unk_token="[UNK]")) tokenizer.pre_tokenizer = Whitespace() trainer = BpeTrainer( vocab_size=30_000, min_frequency=2, special_tokens=["[UNK]", "[CLS]", "[SEP]", "[PAD]", "[MASK]"], ) tokenizer.train(files=["my_corpus.txt"], trainer=trainer) tokenizer.save("bpe_tokenizer.json")

# Encode output = tokenizer.encode("Tokenization is surprisingly powerful!") print(output.tokens) # ['Token', 'ization', 'is', 'surprising', '##ly', 'powerful', '!'] print(output.ids) # [432, 8921, 23, 5671, 99, 1203, 38] ```

researcher · Philip Gage | b. 1964 | Original BPE Algorithm for Text Compression

Philip Gage was a software engineer who published the original byte-pair encoding scheme in Dr. Dobb's Journal (1994) as a compact lossless compression algorithm for arbitrary byte sequences. His contribution to this topic is foundational but entirely accidental — he designed BPE purely for file compression, with no thought of language modeling. The surprising historical fact is that Gage's paper was never formally peer-reviewed in an academic venue; it was a practitioner magazine article, yet it underpins essentially every modern large language model's tokenization pipeline.

researcher · Rico Sennrich | b. 1984 | BPE Adaptation for Neural Machine Translation

Rico Sennrich is an NLP researcher at the University of Edinburgh whose 2016 ACL paper "Neural Machine Translation of Rare Words with Subword Units" (with Haddow and Birch) introduced BPE to the NLP community. He recognized that the compression heuristic naturally produced linguistically meaningful subwords — morphemes, stems, affixes — without any linguistic supervision. A surprising fact: Sennrich's BPE codebase was originally a ~200-line Python script posted alongside the paper; that script, barely modified, was the reference implementation used by the community for years before production-grade libraries existed.

Figure

BPE Training Loop — Iterative Merge Process

Figure

Tokenization Example — Subword Decomposition

Intuition

The Mental Model

Imagine you're designing a shorthand writing system for a secretary who types millions of documents. You could give them a dictionary of every full word (fast lookup, but can't handle new words like "COVID-19"), or you could have them spell everything letter-by-letter (handles any word, but exhausting). BPE is the compromise your secretary naturally invents: keep letters as a fallback, but also add shorthand glyphs for common syllables and word-fragments — `tion`, `ing`, `un`, `pre` — because those sequences appear so often that coding them as single symbols saves enormous effort. The training algorithm is just systematically figuring out which shortcuts save the most strokes across all the documents you've seen. The key insight is that the "best" shortcuts tend to align with real morphemes (the meaning-carrying fragments of words), not because we programmed in linguistics, but because morphemes are exactly what gets reused most in natural language text.

Historical Development

Origins · 1 minhow this was discovered

History

1994

Philip Gage publishes "A New Algorithm for Data Compression" in Dr. Dobb's Journal, introducing byte-pair encoding as a lossless text compression scheme — no NLP connection whatsoever.

2015

Sennrich, Haddow, and Birch begin experimenting with subword segmentation for neural MT at Edinburgh; they recognize BPE's greedy merge produces linguistically coherent fragments.

2016

Sennrich et al. publish "Neural Machine Translation of Rare Words with Subword Units" (ACL 2016), formally introducing BPE to NLP and demonstrating BLEU gains on English↔German and English↔Russian by eliminating UNK tokens.

2018

OpenAI's GPT-1 (Radford et al.) adopts BPE with a 40,478-token vocabulary for unsupervised language model pretraining, establishing BPE as the default tokenizer for transformer language models.

2019

GPT-2 (Radford et al.) introduces byte-level BPE — initializing from 256 raw bytes rather than Unicode characters — achieving a truly universal tokenizer with zero unknown tokens across any language or binary content.

2019

Google releases SentencePiece (Kudo & Richardson, EMNLP 2018), a language-independent BPE implementation that operates directly on raw Unicode strings without whitespace pre-tokenization, enabling better multilingual tokenization.

2020

GPT-3 (Brown et al.) scales to 175B parameters on a BPE-tokenized corpus; the tokenizer's design choices (vocabulary size ~50,257, whitespace-prefix encoding) become a de-facto research standard.

2023

Llama 2 (Touvron et al., Meta) and Mistral-7B both use SentencePiece BPE with 32,000-token vocabularies; Llama 3 upgrades to a 128,256-token BPE vocabulary, demonstrating ongoing scaling of vocabulary size with model scale.

2024

Research like "Is Tokenization Needed?" and efforts such as MegaByte and BLT (Meta) challenge BPE by operating at the patch or byte level, spurring renewed analysis of BPE's limitations for long-context and multimodal settings.

Why It Matters

Real-World Impact

GPT-4 / ChatGPT (OpenAI)Uses the `cl100k_base` BPE tokenizer with a