Tokenization and BPE

A transformer never sees letters. It sees integers - a sequence like [15496, 11, 995]. Tokenization is the pre-processing step that decides how a string is chopped into those integers, and it quietly shapes everything downstream: how long your prompt is, what the model can spell, even how it does arithmetic. The winning recipe, used by GPT, Llama, and almost every modern model, is byte-pair encoding - and its whole idea is embarrassingly simple: repeatedly glue together the most common adjacent pair.

From characters to integers

The job is to map text onto a fixed vocabulary - a numbered list of tokens. Every token has an id, and the id is all the model consumes. There are three obvious ways to slice, and each is a trap in a different direction:

Characters give a tiny alphabet but force the model to read t-o-k-e-n one letter at a time - long sequences waste compute and bury meaning. Whole words are the opposite: tokenization is one crisp unit, but the vocabulary explodes, and the first unseen word - a typo, a name, antidisestablishmentarianism - has no id at all. That is the dreaded out-of-vocabulary (OOV) problem. Subwords thread the needle: common words stay whole, rare words break into familiar fragments, and because the smallest fragments are single characters, nothing is ever unrepresentable.

Byte-pair encoding: merge the frequent pair

BPE learns the vocabulary from data instead of guessing it. Start with the raw alphabet - just the characters. Then repeat one move: scan the whole corpus, find the adjacent pair of symbols that occurs most often, and fuse it into a single new token. Do it again on the updated corpus. Each merge adds exactly one token to the vocabulary, and frequent letter-sequences - e+s+t → est, l+o+w → low - bubble up into their own units.

Below is a real BPE run on a nine-word toy corpus (the frequency after each word is how often it appears). Train it merge-by-merge and watch the amber pair - the current winner - fuse into a green token, growing the vocabulary. Then type into the tokenizer: it applies exactly the merges you have learned so far, so words collapse from characters into whole tokens as you train.

Vocabulary size is a dial you tune

The number of merges you run is the vocabulary size. Start with the base alphabet $\Sigma$, and every merge appends exactly one token, so after $m$ merges:

Our toy has $|\Sigma |=10$ characters; after all $17$ merges the vocabulary is $27$ tokens and every corpus word is a single id. Real tokenizers turn the same dial much further: GPT-2 stopped at $V=50,257$, GPT-4's cl100k_base at about $100,000$. Bigger $V$ means shorter sequences (cheaper to run) but a fatter embedding matrix $E\in {\mathbb{R}}^{V\times d}$ and rarer tokens seen less often during training. There is no free token.

The tokenizer, in ten lines

Applying a learned merge table to new text is a tight loop: start from characters, and repeatedly glue the surviving pair whose merge was learned earliest (lowest rank), until no adjacent pair is a known rule. This is exactly the logic running in the demo above.

def tokenize(word, ranks):            # ranks: {(a, b): merge_order}
    syms = list(word)                 # start from single characters
    while True:
        # every adjacent pair that is a known merge rule
        pairs = [(ranks[(a, b)], i)
                 for i, (a, b) in enumerate(zip(syms, syms[1:]))
                 if (a, b) in ranks]
        if not pairs:                    # nothing left to merge - done
            return syms                   # each survivor is one token id
        _, i = min(pairs)               # earliest-learned pair, leftmost
        syms[i:i+2] = [syms[i] + syms[i+1]]  # fuse the pair in place

Check yourself