Building a Minimal BPE Tokenizer from Scratch

A language model does not read text as whole sentences. It reads a sequence of tokens, and something has to decide where one token ends and the next begins. That something is the tokenizer. The choice of tokenizer affects how much text fits into a model's input, how common words and rare words are represented, and how the model handles spellings it has never seen before.

This article builds a clear mental model of one tokenization method, Byte Pair Encoding, usually abbreviated BPE. The goal is to understand what happens step by step, so that the implementations and interactive demonstrations you meet later make sense. The central idea is small enough to trace by hand, and you will do exactly that below.

The name points to the core operation. A BPE tokenizer works on pairs of adjacent symbols and combines frequent pairs into single units. Repeating that combination step gradually builds a vocabulary of units that are longer than one character and shorter than a whole word. Because the units are pieces of words, BPE belongs to the family of subword tokenization methods.

The method has a well-known origin in machine translation. The research paper that introduced this approach is titled Neural Machine Translation of Rare Words with Subword Units. It was published in 2015 by Sennrich et al. and is available on arXiv. Its title states the motivation directly: rare words are the hard case, and subword units are the proposed way to handle them.

There are two obvious ways to cut text into tokens, and both have costs. If a tokenizer treats every whole word as one token, it needs a huge vocabulary, and any word it has not seen during training has no entry at all. If it treats every character as one token, the vocabulary stays small, but the sequences become long and the individual units carry little meaning on their own.

Subword units resolve this tension. Common words can stay whole, while rare or unfamiliar words are assembled from smaller pieces that the vocabulary already contains. Subword units let a tokenizer represent a rare word by combining pieces it already knows, rather than needing a dedicated entry for that word.

The core of BPE is a single operation repeated many times: look at the current sequence of units, find the adjacent pair that occurs most often, and replace every occurrence of that pair with one new unit. Before looking at a real corpus, trace one merge on a tiny example. Start with the symbol sequence l o w l o w l o t, which is the word-like pattern low, low, lot written as single characters with no spaces.

Notice what did not change. The w and t symbols kept their positions in the sequence, and only the three occurrences of the pair lo were affected. This is the general pattern: a merge touches exactly the places where the chosen pair occurs, and everywhere else the sequence stays as it was. The new unit lo is now available, so a later merge can combine it with a neighbor, such as w, to form a longer unit.

Choosing which merge to make is a counting problem. Each pass looks at the current sequence of units, counts how often each adjacent pair occurs, and selects the pair with the highest count. The selection rule is simple and is the same at every step: the most frequent adjacent pair is the one that gets merged. Each merge then adds one new entry to the vocabulary.

The loop between counting and merging is the heart of the method. A single merge only produces a unit two symbols long. Because each merged unit is then available as a building block, a later pass can merge a unit with a neighbor and produce something longer. Over many passes, units grow from single characters into longer pieces, which is how the vocabulary ends up holding units that are longer than one character.

In round 2 of this example, the sequence lo w lo w lo t contains the pair lo followed by w twice, so the walkthrough merges that pair into low. The longer unit low is a piece of a word, not a full word, and it was built entirely from the earlier merged unit lo. Real training runs over a large body of text and performs many merges, but the rule at each step is the same: find the most frequent adjacent pair, merge it, and record the new unit.

A BPE tokenizer is best understood as a pipeline with two distinct stages. Training builds the vocabulary: it starts from a basic set of symbols and performs the merge loop, recording each merge as one entry. Application uses the vocabulary that training produced to split new text into tokens. These are separate jobs, and mixing them up is a common source of confusion.

The diagram shows the flow of data. Training takes raw text, works on its symbols, and produces a vocabulary with one entry per merge. Application takes that vocabulary and a new piece of text and cuts the text into tokens. The vocabulary is the link between the two stages, which is why it is the thing you save after training and reload later.

Once the mental model is clear, there are resources that let you go further. The source material points to three concrete resources, and each suits a different goal: moving from the concept to real code, or moving from the concept to a visual demonstration. The reading that started it all is the 2015 paper by Sennrich et al., available on arXiv, which explains why subword units were proposed for rare words in machine translation.