Byte pair encoding from scratch

Every explanation of tokenization in this topic has treated the tokenizer as given: text goes in, tokens come out, and the mapping looks arbitrary. It is not arbitrary, and the algorithm behind it fits on a page. Writing it is the fastest way to stop being surprised by token counts, and it is the stage the from-scratch GPT project explicitly defers.

The idea#

Start with a vocabulary of single characters, which can represent anything. Count every adjacent pair in the corpus, merge the most frequent pair into a single new symbol, and repeat until the vocabulary is the size you wanted. Frequent sequences — common words, common word endings, common indentation — become single tokens because they were merged early; rare ones stay as several.

The output of training is not a list of tokens. It is an ordered list of merges, and the order is load-bearing: encoding replays the merges in the order they were learned, so a saved tokenizer is that list plus the character inventory it started from.

Splitting before merging#

Real tokenizers do not let merges cross word boundaries, because a token spanning two words would be learned from one corpus and useless in another. Text is first cut into chunks by a regular expression, and merges happen within a chunk. The convention every modern tokenizer follows is to keep a word's leading space attached to it, which is why " the" and "the" are different tokens and why a token count changes when you strip whitespace.

import re
from collections import Counter


def words(text):
    # a word with its leading space, or a run of whitespace on its own
    return re.findall(r" ?[^\s]+|\s+", text)


def merge_pair(symbols, pair):
    a, b = pair
    out, i = [], 0
    while i < len(symbols):
        if i + 1 < len(symbols) and symbols[i] == a and symbols[i + 1] == b:
            out.append(a + b)        # the two symbols become one
            i += 2
        else:
            out.append(symbols[i])
            i += 1
    return tuple(out)

Training#

Count pairs weighted by how often the word containing them appears, rather than walking the raw text, which is the difference between a loop that finishes and one that does not. Ties are broken deterministically, because a tokenizer that trains differently on two runs of the same corpus is a tokenizer you cannot ship.

def train(text, n_merges):
    freqs = Counter(words(text))                 # word -> how many times it occurs
    split = {w: tuple(w) for w in freqs}         # every word starts as its characters
    merges = []

    for _ in range(n_merges):
        pairs = Counter()
        for w, f in freqs.items():
            s = split[w]
            for pair in zip(s, s[1:]):           # every adjacent pair in the word
                pairs[pair] += f                 # weighted by the word's frequency
        if not pairs:
            break

        # most frequent, ties broken on the pair itself so training is reproducible
        best = max(pairs, key=lambda p: (pairs[p], p))
        if pairs[best] < 2:
            break                                # nothing left worth merging

        merges.append(best)
        split = {w: merge_pair(s, best) for w, s in split.items()}

    return merges

corpus = (
    "the cat sat on the mat. the cat sat on the hat. "
    "a cat and a hat and a mat. the rat sat on the cat. "
    "the fat cat sat. the fat rat sat. the mat and the hat."
)

for i, (a, b) in enumerate(train(corpus, 20)):
    print(i, repr(a), "+", repr(b), "->", repr(a + b))

# 0 'a' + 't'    -> 'at'
# 1 't' + 'h'    -> 'th'
# 2 'th' + 'e'   -> 'the'
# 3 ' ' + 'the'  -> ' the'
# 4 'at' + '.'   -> 'at.'
# 5 ' ' + 'a'    -> ' a'
# ...
# 8 ' c' + 'at'  -> ' cat'
# 11 ' s' + 'at' -> ' sat'

Encoding and decoding#

Encoding replays the merge list against a fresh word. Decoding is concatenation and nothing else, which is the property that makes the leading-space convention work: the spaces are inside the tokens, so joining them reproduces the input exactly with no rules about when to insert a space.

def encode(text, merges):
    out = []
    for w in words(text):
        s = tuple(w)
        for pair in merges:          # in the order learned - this is the whole model
            if len(s) == 1:
                break
            s = merge_pair(s, pair)
        out.extend(s)
    return out


def decode(tokens):
    return "".join(tokens)           # the spaces are already in the tokens


merges = train(corpus, 20)
tokens = encode("the fat cat sat on a mat.", merges)
print(tokens)
# ['the', ' ', 'fat', ' cat', ' sat', ' on', ' a', ' mat.']

assert decode(tokens) == "the fat cat sat on a mat."

That split of " fat" into a space and "fat" is the algorithm's whole character in one line. Nothing decided that "cat" deserves its space and "fat" does not; " cat" appeared more often in the training corpus and got its merge before the budget ran out. Every oddity in a real tokenizer has the same shape.

Unseen text, and why bytes#

A word the tokenizer has never seen still encodes: the merges that apply are applied, and whatever is left stays as single characters. Nothing fails.

t = encode("the elephant sat on a submarine.", merges)
print(t)
# ['the', ' ', 'e', 'l', 'e', 'p', 'h', 'a', 'n', 't', ' sat', ' on', ' a',
#  ' s', 'u', 'b', 'm', 'a', 'r', 'i', 'n', 'e', '.']

assert decode(t) == "the elephant sat on a submarine."

That guarantee only holds if the starting inventory covers every possible input, and a character-level start does not: the corpus above has no vocabulary for an emoji or a Cyrillic letter. Real tokenizers start from the 256 possible bytes rather than from characters, so every conceivable input is representable and an unknown token never has to exist. The cost is that one character outside ASCII is several bytes, and so potentially several tokens, before any merges apply.

Turning tokens into ids#

The model needs integers. The vocabulary is the starting inventory followed by the merge results, in merge order, so ids are assigned once at training time and the mapping is part of the saved tokenizer.

vocab = sorted(set(corpus)) + [a + b for a, b in merges]
ids = {t: i for i, t in enumerate(vocab)}

print(len(vocab))                    # 34
print([ids[t] for t in tokens])      # [16, 0, 31, 22, 25, 27, 19, 33]

What this explains#

• Code costs more tokens per character than prose, because indentation, brackets and camel-case identifiers were a smaller share of the training corpus and earned fewer merges. Some tokenizers add explicit merges for runs of spaces, which is why the same code costs different amounts across models.
• Non-English text costs several times more, because byte-level starts mean a character outside ASCII is two to four bytes before merging, and those sequences were rare enough to earn few merges.
• Numbers tokenize unevenly, because "2023" may be one merged token while "2024" is two. This is a documented contributor to arithmetic errors, and it is why several tokenizers now force digits to split into fixed groups.
• A trailing space changes the token count and sometimes the output, because it becomes part of the next word's token rather than a token of its own.
• The same string tokenizes differently under different models, so a token count is only meaningful alongside the tokenizer that produced it.