Byte-level BPE, merge by merge

The character tokenizer had two problems it just couldn't fix, unknown characters, and one position per character. Byte pair encoding fixes the first one by starting from bytes instead of characters, and the second one by learning which runs of bytes show up together often enough to deserve their own token.

This is the tokenizer every octlm model since Day 1 has used, and the Day 4 model uses it at 8,192 entries.

Bytes, an alphabet with no unknowns

Every string is stored as UTF-8 bytes, and a byte has 256 possible values. So if the base vocabulary is those 256 values, every possible text has an encoding. An emoji is 4 bytes, so it becomes 4 byte tokens. A Japanese character is 3 bytes. Nothing maps to "unknown", so there's no unknown token at all.

octlm's BPE vocabulary starts like this:

The two tool tokens are reserved now so their IDs never move. If you change a special-token ID after training, you silently change what a checkpoint means, and nothing will warn you.

The cost of bytes is length. Plain bytes make sequences even longer than characters for non-ASCII text. That's what merges fix.

Pre-tokenization decides where merges can't cross

Before learning merges, octlm cuts the text into chunks at every change of character type. There are four types, whitespace, word characters (letters, combining marks and _), digits, and everything else.

So what happened ?

• x_1 splits into x_ and 1. The underscore counts as a word character, so it stays with the name, and the digit starts a new chunk.
• Whitespace runs like \n\t and \r\n each stay one chunk, byte for byte, so indentation and Windows line endings round-trip.
• In the Unicode preset, é written as e plus a combining accent stays one word chunk, because a combining mark counts as a word character. Nothing gets normalized.
• The literal text <|eos|> splits into <|, eos, |>. It's ordinary text made of ordinary bytes, never ID 258.

Why cut at all ? Without boundaries, the most frequent pairs in English include a letter followed by a space or a period, so BPE would learn tokens like e. and d that mix a word with punctuation. The GPT-2 tokenizer cuts at similar boundaries for the same reason. Chunks also keep each document separate, octlm never merges across two documents.

def _kind(character: str) -> int:
    if character.isspace():
        return 0
    category = unicodedata.category(character)
    if character == "_" or category[0] in {"L", "M"}:
        return 1
    if category[0] == "N":
        return 2
    return 3

Training glues the most frequent pair, then repeats

Training starts with each chunk as a list of byte IDs, and counts each distinct chunk once with its frequency. Then it loops:

1. Count every adjacent pair of IDs inside every chunk, weighted by how often that chunk occurs.
2. Pick the pair with the highest count. On a tie, pick the one with the smallest left ID, then the smallest right ID.
3. Give the pair the next free ID, starting at 261.
4. Replace every occurrence of the pair with the new ID.
5. Stop when the vocabulary hits its target size, or when the best pair occurs fewer than 2 times.

The tie rule matters more than it looks. Two runs over the same text have to learn the same merges in the same order, otherwise two tokenizers with the same settings would disagree on what ID 400 means. Picking by (-count, pair) makes the order total, so the result never depends on dictionary iteration order.

The stop rule matters too. A pair that shows up once teaches the tokenizer nothing it could reuse, so a merge for it just wastes a vocabulary slot.

So what happened ?

• The first merge is two spaces, and the third is two of those. Indentation repeats on every line, so whitespace pairs have the highest counts.
• Later merges build on earlier ones. Both sides of a merge can be learned tokens, so total gets built as ot, then tot, then total, and total_number shows up near the end.
• Some merges look weird, like a fragment of two words. BPE counts pairs, not meaning. A later merge usually swallows the weird piece into a full name.
• The token count falls with each merge and bytes per token goes up. At some step the best pair occurs once, and training stops before the target size.

Here's the actual training loop:

@classmethod
def train(
    cls, texts: Iterable[str], vocab_size: int, min_frequency: int = 2
) -> ByteBPETokenizer:
    documents = tuple(texts)
    base_size = 256 + len(BPE_SPECIALS)
    if vocab_size < base_size or min_frequency < 1:
        raise ValueError(f"vocab_size must be at least {base_size}")
    sequences = Counter(tuple(chunk) for text in documents for chunk in pretokenize(text))
    merges: list[tuple[int, int, int]] = []
    while base_size + len(merges) < vocab_size:
        counts: Counter[tuple[int, int]] = Counter()
        for sequence, frequency in sequences.items():
            counts.update({pair: count * frequency for pair, count in _pairs(sequence).items()})
        if not counts:
            break
        pair = min(counts, key=lambda item: (-counts[item], item))
        if counts[pair] < min_frequency:
            break
        token_id = base_size + len(merges)
        merged: Counter[tuple[int, ...]] = Counter()
        for sequence, frequency in sequences.items():
            merged[_merge(sequence, pair, token_id)] += frequency
        sequences = merged
        merges.append((*pair, token_id))
    corpus_hash = _document_hash(documents)
    return cls(tuple(merges), corpus_hash, vocab_size, min_frequency)

min(counts, key=lambda item: (-counts[item], item)) is the tie rule in one line. The loop recounts every pair after every merge. That's simple to check and slow at scale, which comes back below.

Encoding replays the merges in the order they were learned

To encode new text, octlm pre-tokenizes it, turns each chunk into bytes, and then applies merges by rank. Among the pairs present in the chunk, it merges the one learned earliest, and keeps going until no pair in the chunk has a merge.

def encode_chunk(self, chunk: bytes) -> tuple[int, ...]:
    ranks = self.merge_ranks
    sequence = tuple(chunk)
    while len(sequence) > 1:
        candidates = (pair for pair in _pairs(sequence) if pair in ranks)
        pair = min(candidates, key=lambda item: ranks[item][0], default=None)
        if pair is None:
            break
        sequence = _merge(sequence, pair, ranks[pair][1])
    return sequence

Rank order is what makes encoding match training. The merges were learned in that order, so applying them in that order rebuilds the same tokens the training text produced. Decoding is simpler, every ID maps to a fixed byte string and you just concatenate the bytes.

Twenty merges traced by hand

Day 1's reading plan asked for 20 merges traced on a Python function. The note has the first 20 on one repeated function, using the same code path. IDs start at 261 because 256 to 260 are specials.

Merge 5 is 109 + 264, byte m plus token 264, which is be from merge 4. Merges 6 to 8 grow that into _number. Merge 16 creates btotal, a piece that spans the end of one name and the start of another inside the same chunk. The table is parsed from notes/day1.md when this site builds.

What we measured

Problem, the character tokenizer gave one token per byte on English and 77.8 percent unknowns on Unicode.

Hypothesis, a byte-level BPE trained on the same PLAN.md compresses the held-out text and represents every sample byte.

• The 1,024-entry tokenizer encoded the 13,939-byte held-out file in 7,319 tokens, so 1.90 bytes per token against 1.00 for characters.
• A Python sample went from 49 tokens to 35.
• Every byte of the Unicode sample was represented. The unknown rate is 0 by construction.
• A 2,048-entry request stopped at 1,708 entries, because no remaining pair occurred twice. PLAN.md was just too small to earn more merges.

Decision, keep the 1,024-entry tokenizer for the Day 1 model. The note is clear that this didn't choose the final vocabulary. Day 2 trained a 2,048-entry tokenizer on a bigger corpus, and Day 4 an 8,192-entry one on TinyStories.

A full recount per merge

Recounting every pair after every merge costs time proportional to the number of distinct chunks times the number of merges. On Day 1's 111 KB that took seconds. Day 2 measured it before training on 7 MB, 2.7 seconds for 142 KB at 512 entries, and 57 seconds for 702 KB at 2,048 entries. The cost tracked the 11,665 distinct chunks in that sample, not the raw bytes. So Day 2 trained on every tenth document. Day 4 trained on the first 10 million characters of TinyStories, which took 303 seconds, and then added a chunk cache to make encoding fast.

What we didn't build, and why

• Incremental pair counting. Production trainers only update the counts a merge touched. The measured cost never blocked a run, so the simple loop stayed.
• GPT-2's regex pre-tokenizer. It also splits contractions like 's and keeps a leading space on words. The four-type rule is shorter to state and test, and it keeps code whitespace intact.
• A pretrained tokenizer. AGENTS.md requires merges learned from our own training data. The one exception is Qwen on Day 6, whose tokenizer ships with its weights.