A BPE Tokenizer Is a Learned Rewrite Program

Tokenization, training, and inference

Training discovers useful joins. Encoding replays them. Decoding puts the bytes back together.

A Byte Pair Encoding tokenizer is a small rewrite program learned from a corpus. Its trainer discovers an ordered list of adjacent joins; its encoder runs that frozen program on new text; and its decoder performs a direct ID-to-bytes lookup.

The difficult direction is deciding how text should be joined. Once the token IDs exist, detokenization is only lookup, concatenate, and decode.

Most tokenizer explanations begin with a finished vocabulary. They show that a word such as tokenizer becomes two or three fragments, then move on to attention and matrix multiplication.

That skips the interesting machine.

A BPE tokenizer has three distinct jobs. Confusing them makes the algorithm feel arbitrary; separating them makes the whole system mechanical.

1 Train Read a representative corpus and learn a vocabulary plus an ordered history of useful merges.
2 Encode Begin with safe base symbols, replay the frozen merge priorities, and return integer token IDs.
3 Decode Map each integer ID to its stored bytes, join the bytes in order, and decode the resulting string.

Tokens Are IDs Before They Are Vectors

A tokenizer produces integers. The neural network turns those integers into vectors later.

The tokenizer ends at the integer ID. The embedding layer is where the neural model begins.

If token ID 7131 enters a model, the embedding layer retrieves row 7131 from an embedding matrix. That row is a learned vector. On the output side, a hidden vector is projected into one score, or logit, for every token in the vocabulary. Sampling or argmax selects another integer ID. Only then does the detokenizer look up the text piece belonging to that ID.

The detokenizer does not invert the embedding vector. It never needs to see it. Even when a model ties its input embedding and output weights, text reconstruction remains an ID-to-bytes operation.

The TinyStories Script Exposes The Lifecycle

Andrej Karpathy's tinystories.py makes the tokenizer's place in language-model training unusually visible.

The script first collects raw TinyStories text. It trains a custom SentencePiece BPE vocabulary on part of that corpus. It then loads the frozen tokenizer, encodes every story into integer IDs, and writes those IDs to binary files for language-model training.

The language model never participates in choosing BPE merges. Tokenizer training is a separate statistical pass over text.

Karpathy's configuration also exposes decisions hidden by many high-level APIs: BPE is selected explicitly; character coverage is complete; digits may be split; byte fallback is enabled; and normalization is set to identity. These choices determine what information reaches the model before the first Transformer weight is updated.

SentencePiece and byte-level GPT tokenizers differ in their exact starting symbols and boundary rules. SentencePiece normally begins from normalized Unicode symbols and represents spaces with a visible marker such as ▁, while byte fallback guarantees a route for characters outside the learned pieces. A pure byte-level BPE begins with all 256 possible byte values. The pair-merging heart is the same, but these are not identical implementations.

For the clearest mechanical example, we can use the byte-level version from Karpathy's minBPE.

Start With An Alphabet That Cannot Fail

Every Unicode string can be encoded as UTF-8 bytes, and every byte is an integer from 0 through 255. A byte-level tokenizer can therefore begin with a complete 256-token vocabulary.

The initial byte vocabulary is already complete. BPE training adds efficient shortcuts without losing the fallback alphabet.

Before any training, this is already a lossless tokenizer. It is simply inefficient. An English word may require one token for almost every character, and a non-ASCII character may require several UTF-8 byte tokens.

BPE training adds shortcuts. Each shortcut gives a new token ID to a pair of adjacent pieces that occurs often. Later shortcuts may join earlier shortcuts, so the learned vocabulary becomes hierarchical.

Training Learns One Merge At A Time

Use Karpathy's deliberately small training string:

aaabdaaabac

At the start, ASCII characters and UTF-8 bytes are the same visible units:

aaabdaaabac

The trainer counts every adjacent pair. The pair a a occurs four times, more than any other pair, so the trainer creates token 256 for the byte string aa. Call it Z for readability. It then replaces non-overlapping occurrences of that pair and repeats the count.

Each accepted pair becomes one new vocabulary item. The rewritten stream determines which pairs can exist in the next round.

There is a useful detail in the first round. The count includes overlapping candidates: aaa contains two adjacent aa pairs. A left-to-right replacement cannot use the middle a twice, so four counted candidates produce two non-overlapping replacements in this corpus.

The learned construction tree for token 258 Token 258 represents aaab and joins token 256 for aa with token 257 for ab. Those tokens are each built from base byte tokens. aaab token 258 · rank 2 aa token 256 · rank 0 ab token 257 · rank 1 a byte 97 a byte 97 a byte 97 b byte 98
Learned tokens are recursive constructions. Token 258 can exist only because tokens 256 and 257 were learned first.

After three rounds, training has produced an ordered merge table:

rank 0: (97, 97)   -> 256     # a  + a  -> aa
rank 1: (97, 98)   -> 257     # a  + b  -> ab
rank 2: (256, 257) -> 258     # aa + ab -> aaab

It has also produced the reverse vocabulary needed for decoding:

256 -> b"aa"
257 -> b"ab"
258 -> b"aaab"

The essential training loop is:

  1. Represent the corpus as current token IDs.
  2. Count adjacent token pairs.
  3. Select the most frequent pair, with a deterministic tie rule.
  4. Assign its concatenation a new token ID.
  5. Replace non-overlapping occurrences of the pair.
  6. Record the merge's rank.
  7. Repeat until the vocabulary reaches its target size or no useful pairs remain.

The statistics must be recomputed because every accepted merge changes the neighborhood. Joining a a does not merely remove one possible pair; it creates new candidates involving aa.

This is why BPE training is fun to watch. A flat alphabet grows a construction tree in public. Common bytes become fragments, fragments become syllable-like pieces, pieces become words, and very common words may join surrounding spaces or punctuation. The trainer has no concept of a syllable, word, or meaning. It only rewards reusable adjacency.

Encoding New Text Replays The Learned History

Now give the frozen tokenizer text it did not train on:

aaabac

The encoder starts from bytes, just as the trainer did. It does not count which pairs are common in this new string. It consults the merge table learned earlier.

Start aaabac
Rank 0 Zaaabac
Rank 1 ZYabac
Rank 2 X258 / aaaba97c99
The unseen text becomes [258, 97, 99] by executing the old rules—not by learning new ones.

At each step, the encoder examines adjacent pairs that currently exist and chooses the applicable learned merge with the best priority. In a classic BPE table, that means the earliest training rank. It replaces the pair, checks the new neighbors, and continues until no learned rule applies.

This is not simply “take the longest vocabulary item that matches.” The vocabulary alone is insufficient when pieces overlap. If both ab and bc exist and the input is abc, the learned priority decides whether a+b or b+c happens first. The history that created the vocabulary is part of the tokenizer.

Karpathy's minimal encoder expresses the rule directly: among adjacent pairs, choose the pair with the lowest merge index. SentencePiece stores a score for each BPE piece and uses the highest-priority valid join. Production implementations use heaps and caches rather than repeatedly scanning the whole sequence, but they are executing the frozen tokenizer model, not learning from the prompt.

A Real Tokenization From One Of My Models

One of my own 8,192-piece SentencePiece BPE models encodes:

Tokenizer training is fun.

as these pieces and IDs:

The space marker belongs to the following piece; the numeric IDs are stable addresses in this tokenizer's vocabulary.

A different tokenizer could assign entirely different IDs and boundaries to the same sentence. The ▁ symbol is SentencePiece's visible representation of whitespace. It distinguishes training at a word boundary from the same letters in another position while keeping reconstruction mechanical.

The model did not discover an English grammar rule for tokenizer. It found reusable corpus fragments: T, ok, en, iz, and er.

Once language-model training begins, the tokenizer must be frozen. Changing the vocabulary afterward would change what every ID means. Embedding row 7131 cannot continue learning the same thing if 7131 suddenly names a different byte sequence.

Detokenization Is The Easy Direction

The merge order is needed to choose a segmentation while encoding. It is not needed to decode. Every ordinary token ID already points to its complete byte string.

Decoding never asks which merge happened first. The final token ID already names its full byte sequence.

In Python, the byte-level core fits on one line plus UTF-8 conversion:

def decode(ids, vocab):
    raw = b"".join(vocab[token_id] for token_id in ids)
    return raw.decode("utf-8", errors="replace")

Concatenating bytes before decoding UTF-8 is important. A Unicode character may have been split across several tokens, so decoding each token independently can corrupt text that is perfectly valid after the byte sequences are joined.

SentencePiece makes the same simplicity visible at the piece-string level:

text = "".join(pieces).replace("▁", " ")

Real implementations also decide what to do with control tokens such as beginning-of-sequence, end-of-sequence, roles, or padding. “Lossless” is relative to normalization: if a tokenizer normalizes two different Unicode spellings into one form before encoding, decoding reconstructs that normalized form. Karpathy's TinyStories configuration uses identity normalization, avoiding that particular transformation.

The Whole Educational Tokenizer

This complete byte-level implementation exposes training, inference-time encoding, and decoding without regex boundaries, special tokens, file formats, or performance optimizations:

from collections import Counter


def merge_pair(ids, pair, new_id):
    """Replace non-overlapping occurrences of pair from left to right."""
    out = []
    i = 0
    while i < len(ids):
        if i + 1 < len(ids) and (ids[i], ids[i + 1]) == pair:
            out.append(new_id)
            i += 2
        else:
            out.append(ids[i])
            i += 1
    return out


def train_bpe(text, vocab_size):
    if vocab_size < 256:
        raise ValueError("A byte-level vocabulary needs the 256 base bytes")

    ids = list(text.encode("utf-8"))
    vocab = {i: bytes([i]) for i in range(256)}
    merges = {}  # adjacent pair -> new token ID; ID order is merge rank

    for new_id in range(256, vocab_size):
        counts = Counter(zip(ids, ids[1:]))
        if not counts:
            break

        # Highest frequency, then lexicographically smallest pair on a tie.
        pair = min(counts, key=lambda p: (-counts[p], p))
        ids = merge_pair(ids, pair, new_id)
        merges[pair] = new_id
        vocab[new_id] = vocab[pair[0]] + vocab[pair[1]]

    return merges, vocab


def encode(text, merges):
    ids = list(text.encode("utf-8"))

    while len(ids) >= 2:
        adjacent = set(zip(ids, ids[1:]))
        candidates = [(merges[pair], pair)
                      for pair in adjacent if pair in merges]
        if not candidates:
            break

        new_id, pair = min(candidates)  # earliest learned merge wins
        ids = merge_pair(ids, pair, new_id)

    return ids


def decode(ids, vocab):
    raw = b"".join(vocab[token_id] for token_id in ids)
    return raw.decode("utf-8", errors="replace")

The toy run is:

merges, vocab = train_bpe("aaabdaaabac", vocab_size=259)
ids = encode("aaabac", merges)

print(ids)                 # [258, 97, 99]
print(decode(ids, vocab))  # aaabac

This is enough to expose the invariant. A production tokenizer changes data structures and policy, not the central mechanism.

Production Tokenizers Add Policy Around The Core

The educational implementation permits merges across every neighboring byte, including spaces, punctuation, and document boundaries. Practical tokenizers add controls around that loop.

NormalizationChooses whether Unicode forms, case, and whitespace are preserved or mapped into a canonical input.
Boundary rulesDivide text into chunks so merges cannot cross selected letter, number, punctuation, or whitespace boundaries.
Byte fallbackGuarantees that characters outside the learned Unicode pieces still have a reversible representation.
Special tokensReserve atomic IDs for sequence boundaries, roles, padding, tools, or media without treating them as ordinary prose.
Deterministic tiesEnsure that equal pair counts produce the same later vocabulary on every repeatable training run.
Optional samplingCan vary segmentation during model training through techniques such as BPE dropout; ordinary inference remains deterministic.

GPT-style regex tokenizers separate categories before BPE so that a merge cannot cross a forbidden boundary. SentencePiece keeps whitespace visible as a normal symbol and can train directly from raw sentences. A byte-level vocabulary is complete by construction; a Unicode-piece tokenizer needs an unknown-token policy or byte fallback for characters outside its learned inventory.

BPE Optimizes Reusable Adjacency, Not Meaning

BPE often discovers pieces that resemble prefixes, suffixes, roots, words, or punctuation patterns. That is an effect of frequency, not linguistic understanding.

Each accepted merge reduces the number of symbols needed to represent occurrences of one adjacent pattern. Repeating that greedy choice tends to create a reusable codebook that shortens sequences on the training distribution. It is compression-like, but it is not a complete file-compression system: language models usually represent token IDs with fixed-width integers internally, and a larger vocabulary also enlarges the embedding table and output projection.

Vocabulary size is a direct engineering tradeoff:

Karpathy's TinyStories script captures the practical response: train a compact tokenizer on the kind of text the model will see, then measure the resulting story lengths before choosing the model's context and storage format.

Useful validation is concrete: test exact round trips, unseen Unicode, whitespace, malformed-input policy, atomic special tokens, determinism, and token counts on held-out prose, code, numbers, and every language the model must support. Tokens per word is not enough across languages; bytes per token and tokens per character expose different failure modes.

Keep The Four Machines Separate

A BPE tokenizer is not a dictionary of words, and it is not a neural network.

The trainer is a compiler. It reads a corpus and emits an ordered rewrite program plus a vocabulary.

The encoder is an interpreter. It begins with safe base symbols and executes every learned join that applies, in learned-priority order.

The embedding layer is a separate machine. It turns the encoder's integer IDs into vectors for the Transformer.

The decoder is a table lookup and a join. It does not need pair counts, merge ranks, gradients, or vectors.

Training discovers the joins. Inference obeys their history. Decoding simply puts the pieces back together.

Primary Sources And Implementations