Byte-Pair Encoding from Scratch

Byte-Pair Encoding (BPE), originally a data compression algorithm published by Philip Gage in 1994, was adapted in 2016 by Sennrich, Haddow, and Birch for subword tokenization in neural machine translation. The algorithm builds a subword vocabulary by iteratively merging the most frequent adjacent byte pairs in a corpus, enabling models to handle rare and unseen words without a fixed vocabulary. BPE remains a foundational technique in modern NLP tokenizers.

Byte-Pair Encoding from Scratch Unicode, Bytes, and What Text Actually Is /blog/unicode-and-bytes How do you turn a sentence into numbers? A neural network operates on tensors of floating-point values. You can't feed it the string "The cat sat on the mat" directly. At some point there has to be a mapping from text to integers, and from integers to vectors. We covered the raw byte representation of text in the previous post /blog/unicode-and-bytes . Now we need the next piece: how to chop that text into tokens , and build the vocabulary that maps each token to an ID. The obvious approach is to split on whitespace and punctuation. Every unique word gets an ID. This blows up immediately. English alone has hundreds of thousands of word forms once you count conjugations, plurals, possessives, and compound words. German is worse. Agglutinative languages like Turkish or Finnish are catastrophic. Any word not seen during training becomes an UNK token, a black hole in the model's understanding. What about going the other direction? Characters. The English alphabet is 26 letters plus some punctuation. Tiny vocabulary, no UNK problem. But now the model has to learn everything from scratch: that c-a-t means something, that -ing is a suffix, that spaces separate words. Sequences get absurdly long. A single paragraph might be 500 characters, and the model has to attend over all of them with quadratic cost. Subword tokenization is the compromise that won. Split common words into single tokens, break rare words into pieces, and give the model a vocabulary that's big enough to be useful but small enough to be manageable. Byte-Pair Encoding is the algorithm that kicked off this whole line of work, and it's what we're going to build from scratch. BPE as compression The algorithm actually comes from data compression, not NLP. Philip Gage published it in the C Users Journal in 1994. The idea is almost comically simple: - Start with a sequence of bytes. - Find the most frequent adjacent pair of bytes. - Replace every occurrence of that pair with a new byte a symbol that didn't exist before . - Repeat until you've done enough replacements or no pair appears more than once. Each step reduces the total length of the sequence by replacing two symbols with one. The "merge table" you accumulate along the way is the compression dictionary. To decompress, you just apply the merges in reverse. Gage's original application was compressing files. But in 2016, Sennrich, Haddow, and Birch realized that the same algorithm could solve the vocabulary problem for neural machine translation. Instead of compressing bytes, you compress a corpus of words. Instead of a compression dictionary, you get a tokenizer. From compression to tokenization The key insight of Sennrich et al. is that BPE's merge table is a subword vocabulary. Here's how it works: Training phase: You take your training corpus, split every word into individual characters plus a special end-of-word marker , and then run the BPE algorithm. Count all adjacent pairs across the entire corpus, merge the most frequent one, update the corpus, repeat. After merges you have a vocabulary of base characters + merged tokens. Encoding phase: Given a new word at inference time, you start with its character sequence and apply the learned merges greedily, in the order they were learned during training. Merge 1 first, then merge 2, and so on. When no more applicable merges remain, whatever tokens you're left with are the segmentation. The order of the merges matters at encoding time. You don't just look for the longest possible token; you replay the merge sequence. We'll come back to why. Let me make this concrete. Here's the BPE algorithm running on a small corpus. Click through the steps and watch how the vocabulary grows. BPE merge algorithm on a toy corpus. Each step merges the most frequent adjacent pair. Notice how the first merges tend to grab common character pairs like e, r or l, o . These aren't linguistically meaningful morphemes. The algorithm doesn't know what a morpheme is. It's just counting frequencies. The token er appears because newer and wider both end in -er , and those words are common enough that the pair e, r rises to the top. The algorithm also merges lo, w into low pretty quickly, because the word "low" appears five times. By the end, frequent whole words like low and new are single tokens, while rarer words stay partially segmented. Building a BPE trainer Let's implement this properly. The trainer needs to: - Take a corpus and split it into character sequences with word frequencies for efficiency . - Count pair frequencies across the whole corpus, weighted by word frequency. - Merge the top pair everywhere. - Repeat to a target vocabulary size. The core data structure is a dictionary that maps each word as a tuple of tokens to its frequency in the corpus. We never re-scan the raw text after the initial pass. Let me walk through a concrete run. We'll train on a small corpus where word frequencies are realistic enough to see interesting behavior: Look at what happens. Merges 1-2 collapse e + r + </w into the token er</w , because both newer and wider end in -er . That's 9 occurrences 6 from newer , 3 from wider . Merges 3-4 build new from characters. Merges 5-6 build low . Then merge 7 collapses newer</w into a single token because the full word newer appears 6 times. Merge 8 fuses low</w the standalone word "low" shows up 5 times . Merges 9-10 start assembling wider from characters but run out of budget before the full word collapses. After 10 merges, the word newer is a single token and so is low . The word lowest is segmented as low + e + s + t + </w because est wasn't frequent enough to get its own merge yet. And wider is still several tokens because the budget stopped before the final merges. This is the core thing to understand: the vocabulary emerges from frequency statistics of the training data, not from any linguistic knowledge. Common words become single tokens. Rare words get split at whatever boundaries the frequency patterns dictate. Building the encoder Training gives you a merge list. Now you need an encoder that applies those merges to new text. The encoder takes a word, splits it into characters, and applies each merge rule in order. This is the greedy left-to-right application. The loop walks through every merge in training order, and at each merge it scans the current token list for occurrences of that pair and fuses them. When all merges have been tried, you have your segmentation. That "in training order" bit is doing a lot of work. Let's watch it run. | | Pair | Produces | Fired | |---|---|---|---| | 1 | e, r | er | next | | 2 | er, </w | er</w | · | | 3 | l, o | lo | · | | 4 | lo, w | low | · | | 5 | n, e | ne | · | | 6 | ne, w | new | · | | 7 | new, er</w | newer</w | · | | 8 | w, i | wi | · | | 9 | wi, d | wid | · | | 10 | wid, er</w | wider</w | · | Encoding is a replay: the merge list is applied in training order, and each rule collapses every occurrence of its pair. A word the tokenizer never saw during training still gets segmented cleanly by composing known subwords. A few things to look at while you play with it. The word lower was never in training. It still collapses to low + er</w because both of those subwords were learned. Composition is the whole point: the tokenizer doesn't need to have seen a word to handle it, as long as it has seen the pieces. The word newest partially collapses. The new token is there, but est</w never became a merge in our 10-step run, so the tail stays as characters. Training longer would eventually fuse the est sequence. And watch lowering . The e, r merge fires on a position where the </w marker is not adjacent, because the r is followed by an i . That's the one to sit with. The encoder doesn't look for the longest matching token. It replays merges in training order, and each rule sees whatever pairs exist at the moment it runs. That ordering is what makes the segmentation stable and deterministic. Rerun the same word against the same merge list and you get the same tokens every time. It also means two tokenizers with the same final vocabulary can produce different segmentations if their merge orders differ. The merge list is the tokenizer, not just its vocabulary. Byte-level BPE: the GPT-2 variant Sennrich's original BPE starts with Unicode characters. But which characters? There are over 150,000 Unicode code points. Putting them all in the base vocabulary is wasteful since most never appear. Filtering to only characters seen in training puts us back at the UNK problem for unseen scripts. Radford et al. solved this in GPT-2 with a neat trick: start from raw bytes. Every possible input can be represented as a sequence of bytes values 0-255 . The base vocabulary is exactly 256 tokens, and from there you run BPE merges as before. on top of this fixed base, turning common byte pairs like t, h or the two-byte sequence for é into single tokens. The 256-byte base vocabulary. ASCII printable bytes show as their glyphs, high bytes show in hex. Click a preset to see how a non-ASCII character expands into UTF-8 bytes that all already live in the grid. The base alphabet never grows; only the merge table does. This gives you a universal tokenizer. Any UTF-8 text, any language, any emoji, any binary garbage, can be tokenized without ever producing an UNK token. The base vocabulary is tiny and fixed. All the expressiveness comes from the learned merges. But there's a wrinkle. If you run BPE on raw bytes naively, you'll learn merges that span across word boundaries. The bytes for the space character will get merged with adjacent word bytes, and you'll end up with tokens like " the" space-t-h-e absorbing into multi-word chunks. GPT-2 prevents this with a pre-tokenization step: a regex pattern that splits the input into chunks before BPE runs. The GPT-2 regex looks something like this: Each chunk becomes an independent unit for BPE. Merges happen within chunks but never across chunk boundaries. So you'll get tokens like " learning" space attached to the word but never tokens that span two words. The leading space is part of the token, which is why you'll sometimes see tokenizer outputs like " Hello", " world" with those leading spaces. Pre-tokenization seems minor and has real consequences. It determines the maximum size of any single token bounded by the longest pre-token chunk , and it affects which merges the algorithm learns. Different regex patterns lead to different vocabularies even from the same corpus. Vocab size is a cut on the merge list One more piece of intuition before we hit the misconceptions. When a tokenizer says "32k vocabulary" or "200k vocabulary," what that number actually controls is how deep into the frequency-ranked merge list we cut. The first few thousand merges grab very common substrings in the training corpus. Later merges grab rarer things, including whole words and multi-character subwords in less-represented scripts. Pick a vocab size and you pick a cut point on this ordered list. Everything above the cut survives as a dedicated token. Everything below gets decomposed at encoding time into smaller pieces that did make the cut. Slide the cut line by picking a vocab size. Tokens to the left of the cut are dedicated entries in the vocabulary. Tokens to the right fall below the cut and get broken into smaller pieces. Moving from 32k to 200k is mostly buying more coverage for non-Latin scripts and long domain words. This reframing is useful for the most common argument about tokenizers, which is whether to make them bigger. A bigger vocab does not add "capacity" in any mysterious sense. It just moves the cut further down the merge list, letting more mid-frequency patterns live as single tokens instead of sequences. For English the returns diminish quickly past 50k. For Korean, Hindi, and Russian the returns keep coming for much longer, which is why the trend in frontier models has been to push vocabularies up into the 128k–256k range. Misconceptions "BPE finds linguistically meaningful morphemes." It doesn't. It finds frequent byte-pair patterns. Sometimes those patterns line up with morphemes like un- or -ing , because morphemes tend to be frequent substrings. BPE will happily merge arbitrary character sequences if they're frequent enough. The token " th" space + t + h exists in GPT-2's vocabulary not because "th" is a meaningful unit, but because it's an absurdly common byte pair in English. The algorithm is frequency-driven, not linguistics-driven. "The merge order doesn't matter at inference." It does. The encoder applies merges in training order, and this creates an implicit priority. If merge 47 combines a, b and merge 203 combines ab, c , the encoder always tries a, b first. Scramble the merge order and you get different segmentations. Two tokenizers with the same final vocabulary but different merge orderings are functionally different tokenizers. "Larger vocabulary is always better." More merges means more tokens in the vocabulary, which means shorter sequences good for attention cost but a larger embedding table more parameters, more memory . There's a real tradeoff. GPT-2 used 50,257 tokens. GPT-4 used 100,256. GPT-4o uses 200,019 the o200k base encoding . The trend is toward larger vocabularies, partly because they compress multilingual text better, but each doubling of vocab size adds millions of parameters to the embedding and unembedding layers. What's next BPE is a simple algorithm. Count pairs, merge the most frequent, repeat. From that trivial loop you get a subword vocabulary that handles any language, any script, and any word you throw at it. Statistically principled rather than linguistically principled. And it turns out that's enough. The next post covers WordPiece, Unigram, and SentencePiece , the two main alternatives to BPE and the framework that wraps them for multilingual use. Additional reading and watching - Gage, P. 1994 . A New Algorithm for Data Compression https://www.derczynski.com/papers/archive/BPE Gage.pdf . C Users Journal , 12 2 . - Sennrich, R., Haddow, B., & Birch, A. 2016 . Neural Machine Translation of Rare Words with Subword Units https://arxiv.org/abs/1508.07909 . ACL 2016. - Radford, A., et al. 2019 . Language Models are Unsupervised Multitask Learners https://cdn.openai.com/better-language-models/language models are unsupervised multitask learners.pdf . OpenAI. - OpenAI. tiktoken https://github.com/openai/tiktoken — fast BPE tokenizer implementation in Rust. - OpenAI. 2024 . GPT-4o System Card https://openai.com/index/gpt-4o-system-card/ — includes details on the o200k base tokenizer. - Karpathy, A. 2024 . minbpe https://github.com/karpathy/minbpe — minimal BPE implementation for educational purposes. - Zouhar, V. & Meister, C. 2023 . A Formal Perspective on Byte-Pair Encoding https://arxiv.org/abs/2306.16837 . ACL Findings 2023. Formalizes BPE as a greedy approximation to a compression objective and shows why the merge list not just the vocabulary is the tokenizer.