Byte-level BPE, merge by merge

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

This is the tokenizer every octlm model since Day 1 has used, and the one the Day 4 model uses 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. If the base vocabulary is those 256 values, every possible text has an encoding. An emoji is 4 bytes and becomes 4 byte tokens. A Japanese character is 3 bytes. Nothing maps to "unknown", so there is no unknown token.

octlm's BPE vocabulary starts like this:

The two tool tokens are reserved now so their IDs never move. Changing a special-token ID after training would silently change what a checkpoint means.

The cost of bytes is length. Plain bytes make sequences even longer than characters for non-ASCII text. Merges fix that.

Pre-tokenization decides where merges may not 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.

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 such as \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 is normalized.
• The literal text <|eos|> splits into <|, eos, |>. It is 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, and 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 pair 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 reaches 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 must learn the same merges in the same order, or two tokenizers with the same settings would disagree about 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 occurs once teaches the tokenizer nothing it could reuse, and a merge for it would waste a vocabulary slot.

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. A merge's two sides can be learned tokens, so total is built as ot, then tot, then total, and total_number arrives near the end.
• Some merges look odd, like a fragment of two words. BPE counts pairs, not meaning. A later merge usually absorbs the odd piece into a full name.
• The token count falls with each merge and bytes per token rises. At some step the best pair occurs once, and training stops before the target size.

Here is 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 is 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 repeats 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 the bytes concatenate.

Twenty merges traced by hand

Day 1's reading plan asked for 20 merges traced on a Python function. The note records the first 20 on one function repeated, 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 produced 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, 1.90 bytes per token against 1.00 for characters.
• A Python sample shrank 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 too small to earn more merges.

Decision: keep the 1,024-entry tokenizer for the Day 1 model. The note is explicit that this did not choose the final vocabulary. Day 2 trained a 2,048-entry tokenizer on a larger 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, 57 seconds for 702 KB at 2,048 entries. The cost tracked the 11,665 distinct chunks in that sample, not the raw bytes. Day 2 therefore 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 did not build, and why

• Incremental pair counting. Production trainers update only 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.