minbpe — minimal Byte-Pair-Encoding

The 600-line repo that turns "tokenization" from a black box into a thing you can read in one sitting and re-implement from scratch. If [[tokenization]] is the concept article — what BPE/WordPiece/Unigram are and why they bite you — minbpe is the lab bench: Andrej Karpathy's clean, heavily-commented Python implementation of byte-level BPE training and encode/decode, building all the way up to a tokenizer that reproduces GPT-4's output byte-for-byte. It is the companion code to his 2-hour lecture "Let's Build the GPT Tokenizer." This article walks the actual files and the actual mechanics, then maps it onto the OpenAlice Academy ladder.

What it is

minbpe↗ is a tiny, dependency-light Python package (MIT) that implements the Byte-Pair Encoding algorithm "commonly used in LLM tokenization." Where most people only ever call a tokenizer (tiktoken, HuggingFace tokenizers), minbpe makes you train one and run it yourself, in code short enough to hold in your head.

It ships three tokenizer classes, each a strict superset of the last:

1. `BasicTokenizer` (basic.py) — pure BPE straight on the UTF-8 bytes of the input text. No regex pre-split, no special tokens. The algorithm in its barest form.
2. `RegexTokenizer` (regex.py) — adds the GPT-style pre-tokenization regex (split text into letter/number/punctuation/whitespace chunks first, so merges never cross chunk boundaries) and special-token support. This is the one you'd actually train on real data.
3. `GPT4Tokenizer` (gpt4.py) — a thin wrapper over RegexTokenizer that loads OpenAI's pretrained cl100k_base merges out of tiktoken and reproduces GPT-4 tokenization exactly, byte-permutation quirk and all.

All three inherit from an abstract Tokenizer in base.py, which holds the shared state (merges, pattern, special_tokens, vocab) and the save/load plumbing. The repo also includes train.py (a demo that trains on the Taylor-Swift Wikipedia article in ~25 s on an M1), a tests/ pytest suite, an exercise.md step-by-step build guide, and lecture.md (a text version of the video).

The mental one-liner: minbpe is to the tokenizer what `nanoGPT` is to the transformer — the minimal, readable, hackable reference you learn from before you ever touch the optimized production library. (See [[nanogpt]] for the transformer counterpart; minbpe is referenced directly from the [[tokenization]] concept article as "the canonical next step up.")

Why it matters

Tokenization is the least glamorous and most under-appreciated stage of an LLM, and (per [[tokenization]]) the silent cause of a surprising fraction of "the model is dumb" failures — can't spell, can't reverse a string, flaky arithmetic, the SolidGoldMagikarp meltdown. You cannot reason about those failures if BPE is a black box to you. minbpe exists to un-black-box it:

• It is studyable. The whole thing is "very short and thoroughly commented." You can read every line that turns "aaabdaaabac" into [258, 100, 258, 97, 99] and back, and understand why.
• It is real, not a toy abstraction. GPT4Tokenizer matches tiktoken's cl100k_base output exactly — same token IDs on "hello123!!!? (안녕하세요!) 😉". Once you've built it, GPT-4's tokenizer is no longer magic; it's merges + a regex + a byte shuffle you've personally reconstructed.
• It is the missing *training* code. tiktoken is fast at inference but cannot train a new vocabulary; HuggingFace tokenizers can train but is a large, many-variant codebase. minbpe sits in the gap as the simplest thing that trains and runs. (This exact gap is why Karpathy later wrote rustbpe↗ — "the missing tiktoken training code" — a fast Rust version used in [[nanochat]]; see the ladder below. Note: `rustbpe` does not yet have its own article in this library — referenced in prose, not as a [[link]].)
• It is the bridge rung. Char-level toy tokenizers (one token per character) are trivial; production byte-level BPE feels intimidating. minbpe is the exact step in between — small enough to write, real enough to matter.

The honest framing: you do not need minbpe to ship a product (you'll use a provider's tokenizer). You need it to understand the layer that silently shapes cost, context budget, and a whole class of model failures.

How it works (the real mechanics)

base.py — the two functions everything rests on

BPE is, at its core, two ~10-line functions. minbpe puts them in base.py as module-level helpers, and everything else is built on top.

Count adjacent pairs (get_stats) — tally every neighbouring pair in a list of token IDs:

def get_stats(ids, counts=None):
    counts = {} if counts is None else counts
    for pair in zip(ids, ids[1:]):
        counts[pair] = counts.get(pair, 0) + 1
    return counts

Replace a pair with a new id (merge) — walk the list, and wherever the chosen pair appears adjacently, splice in the new token idx:

def merge(ids, pair, idx):
    newids = []
    i = 0
    while i < len(ids):
        if ids[i] == pair[0] and i < len(ids) - 1 and ids[i+1] == pair[1]:
            newids.append(idx)
            i += 2
        else:
            newids.append(ids[i])
            i += 1
    return newids

That's the whole engine. Training = repeatedly `get_stats` then `merge` the winner. The abstract Tokenizer base class then holds four pieces of state:

• self.merges: dict[(int,int) -> int] — the learned merge rules, in learned order (the dict insertion order is the priority).
• self.pattern: str — the pre-tokenization regex (empty for BasicTokenizer).
• self.special_tokens: dict[str -> int] — registered special tokens.
• self.vocab: dict[int -> bytes] — built from the merges by _build_vocab(): ids 0–255 are the raw single bytes, and each merged id's bytes are the concatenation of its two parents' bytes.

save()/load() write a human-readable .model file ("minbpe v1" header, the pattern line, the special-token table, then one idx1 idx2 merge per line) plus a pretty .vocab file for eyeballing (via render_token / replace_control_characters, which escape control chars so the dump is printable).

basic.py — BPE in its barest form

Train. Encode the training text to UTF-8 bytes (a list of ints 0–255), then loop num_merges = vocab_size - 256 times. Each iteration: get_stats(ids), pick the most frequent pair with max(stats, key=stats.get), mint it the next id (256 + i), merge it into ids, and record both merges[pair] = idx and vocab[idx] = vocab[p0] + vocab[p1].

Encode. Bytes → ids, then greedily replay the trained merges: repeatedly get_stats, and among the pairs present, pick the one with the lowest merge index (learned earliest) — min(stats, key=lambda p: merges.get(p, inf)) — and merge it; stop when no present pair has a rule.

Decode. Trivial lookup: concatenate vocab[idx] for every id, then bytes.decode("utf-8", errors="replace"). (The errors="replace" matters — a greedy/partial byte sequence may not be valid UTF-8, and you want a � rather than a crash.)

The toy run from the README: train on "aaabdaaabac" with 256 + 3 merges → encode gives [258, 100, 258, 97, 99], and decode round-trips exactly.

regex.py — the GPT pre-split and special tokens

Running BPE on raw text lets it learn dog., dog!, dog? as three different tokens — wasteful and entangling. GPT-2 fixed this with a pre-tokenization regex that first chops text into chunks (letters / numbers / punctuation / whitespace) and forbids any merge from crossing a chunk boundary. BPE then runs independently inside each chunk. minbpe ships both canonical patterns verbatim:

GPT2_SPLIT_PATTERN = r"""'(?:[sdmt]|ll|ve|re)| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+"""

GPT4_SPLIT_PATTERN = r"""'(?i:[sdmt]|ll|ve|re)|[^\r\n\p{L}\p{N}]?+\p{L}+|\p{N}{1,3}| ?[^\s\p{L}\p{N}]++[\r\n]*|\s*[\r\n]|\s+(?!\S)|\s+"""

Reading the GPT-4 pattern tells the whole story of what changed (compiled with the regex module, not stdlib re, for \p{L} Unicode classes):

• '(?i:[sdmt]|ll|ve|re) — case-insensitive contractions ((?i:…)), so HOW'S no longer splits badly the way GPT-2's lowercase-only pattern did.
• \p{N}{1,3} — numbers capped at runs of 1–3 digits, so the tokenizer can't mint a bespoke token for 2017 or 8675309. A deliberate band-aid for the arithmetic problem (see [[tokenization]]'s caveats).
• \s*[\r\n] and the trailing whitespace alternations — better newline / indentation handling for code.

RegexTokenizer.train simply applies re.findall(pattern, text) to chunk the text, encodes each chunk to bytes, and counts pair stats across all chunks at once (so a merge must be frequent overall, but is only ever applied within a chunk). encode_ordinary splits by the pattern and runs _encode_chunk (the same greedy min(stats, key=…merges.get…) replay) on each chunk separately.

Special tokens are handled outside BPE. You register_special_tokens({...}) (e.g. {"<|endoftext|>": 100257}), and the full encode(text, allowed_special=…) first splits the text around the special strings with a capturing regex — "(" + "|".join(re.escape(k) for k in special) + ")" — emitting the special token's id directly and BPE-encoding everything between. allowed_special takes "all", "none", "none_raise", or an explicit set. This is the prompt-injection / token-smuggling control: on untrusted user input you must not pass "all", or attacker text containing the literal <|endoftext|> gets promoted to a real control token (a security note carried in [[tokenization]]).

gpt4.py — reproducing GPT-4 exactly (and one ugly historical quirk)

GPT4Tokenizer is a RegexTokenizer that, instead of training, borrows GPT-4's already-trained vocabulary from tiktoken's cl100k_base. Two non-obvious problems have to be solved:

1. Recovering the merge *pairs*. tiktoken exposes enc._mergeable_ranks — a bytes -> rank map where every token is already its fully merged byte string. It does not tell you which two parents produced it. recover_merges reconstructs that: for each multi-byte token it runs a small bpe() helper that greedily re-merges the token's bytes (always taking the lowest-ranked adjacent pair) until exactly two pieces remain — those two are the parents, and merges[(ix0, ix1)] = rank rebuilds the ordered merge dict. ("It is not trivial to recover the raw merges from the GPT-4 tokenizer.")

1. The byte permutation. GPT-4, "completely non-sensical and probably historical," shuffles the 256 single-byte tokens to different ids. minbpe captures the mapping self.byte_shuffle = {i: mergeable_ranks[bytes([i])] for i in range(256)}, applies it at the start of encode and inverts it in decode. Without this, every other token id would be off. It is a vivid lesson that production tokenizers carry irreducible historical cruft you simply have to replicate bit-for-bit.

The payoff: GPT4Tokenizer().encode("hello123!!!? (안녕하세요!) 😉") returns the identical id sequence as tiktoken.get_encoding("cl100k_base").

Key ideas & tradeoffs

• The merge *order* is the model. BPE training produces an ordered list of merge rules; encoding is just a deterministic greedy replay of that list by rank. There is no search, no probabilities (contrast WordPiece/Unigram in [[tokenization]]). The entire "learned" artifact is merges + the regex.
• Byte-level base = no unknowns, ever. Base vocab is exactly the 256 bytes, so any string in any script is representable (worst case byte-by-byte). The cost: a single emoji or rare CJK char is 3–4 UTF-8 bytes and, if those pairs never earned a merge, stays split into several tokens.
• Greedy ≠ minimal-token. minbpe's encode is greedy by merge rank; it does not guarantee the shortest possible token sequence. That's accepted everywhere — it's deterministic, fast, and matches how tiktoken behaves.
• Vocab size is the dial. train(text, vocab_size) with bigger vocab_size → more merges → shorter sequences but a larger embedding/softmax matrix and rarer, under-trained tokens. ids 0–255 bytes, 256 … vocab_size-1 merges, specials at vocab_size+.
• Clarity over speed, on purpose. The Python is unoptimized (its own TODO list asks for a faster Python pass and a C/Rust version). It's a teaching artifact; for real training throughput you reach for rustbpe/tokenizers, and for inference you reach for tiktoken.

Honest caveats

• It is intentionally slow and single-threaded. train.py on a few hundred KB takes ~25 s; minbpe is not built to train a 100k-token vocab on internet-scale data in reasonable time. The repo's own TODOs call out the need for optimized Python and a C/Rust port. Don't benchmark it against tiktoken/tokenizers; that's not the point.
• `GPT4Tokenizer` reproduces GPT-4's *output*, not its *training*. It loads pretrained cl100k_base merges from tiktoken; it does not (and cannot quickly) re-train GPT-4's vocabulary. And it inherits a quirk you'd never design on purpose — the byte shuffle — purely for compatibility.
• Not every tokenizer family is here. minbpe is BPE-only. WordPiece (BERT) and Unigram/SentencePiece (T5, LLaMA) are different algorithms it deliberately does not implement — the README lists a LlamaTokenizer (sentencepiece equivalent) and GPT-2/3/3.5 tokenizers as open TODOs. For the algorithm comparison, stay in [[tokenization]].
• The regex needs the `regex` module. The \p{L}/\p{N} Unicode property classes don't work with stdlib re; the patterns assume the third-party regex package. A common first-run gotcha.
• Doc-fetch note (this article): the source-file fetcher refused to echo full method bodies verbatim (a length guard), so the longer train/encode listings here are reconstructed from the README, exercise.md, the file structure, and the verbatim helpers (get_stats, merge) and regex patterns that were retrieved. The two helper functions and both split-pattern strings above are exact; the multi-line method walkthroughs are faithful paraphrase, not copy-paste. Read the files directly if you need the literal lines.

OpenAlice + Academy ladder

minbpe slots cleanly into the from-scratch education path this library curates, one rung above char-level toys and one below a full model:

• The natural lab unit. Per [[tokenization]]: take the char-level tokenizer from a toy GPT, replace it with a trained minbpe BPE, and watch sequence length drop while the embedding matrix grows. That single swap makes the vocab-size ↔ sequence-length ↔ parameter-count tradeoff tangible. It pairs with [[nanogpt]] (the transformer counterpart), [[microgpt-build-an-llm-from-scratch]], [[llm-from-scratch]], and the [[nn-zero-to-hero]] / [[neural-network-from-scratch]] foundations one rung below.
• minbpe's own 4-step exercise *is* a ready-made Academy module (from exercise.md): (1) build BasicTokenizer (train/encode/decode) and test it on real text; (2) add the GPT-4 split regex to get RegexTokenizer, proving tokens never cross category boundaries; (3) load cl100k_base from tiktoken, implement recover_merges + the byte shuffle, and verify your GPT4Tokenizer matches tiktoken exactly; (4, optional) add special tokens with allowed_special semantics. A learner who finishes step 3 has, with their own hands, rebuilt GPT-4's tokenizer.
• Bridge to the capstone. The very next rung is [[nanochat]], whose tokenizer is rustbpe — Karpathy's "missing tiktoken training code", a fast Rust port of exactly this algorithm (regex split + byte-level BPE), training a 65,536-token vocab on ~2 B FineWeb-EDU chars (~4.8 chars/token) in ~1 minute and exporting to tiktoken for inference. minbpe is the readable Python you learn it in; rustbpe is the fast production version of the same idea. (rustbpe is not yet its own library article — prose link only.)
• Why it matters for Alice specifically. OpenAlice does not train its own vocabulary — it consumes the provider tokenizer (tiktoken via the Codex/OpenAI path). The value of minbpe here is diagnostic literacy: token counts are the unit of cost and context budget (load-bearing for [[model-routing]] and for retrieval pipelines like [[graphrag]] / [[agent-memory-systems]] / [[mempalace]] that pack knowledge into a finite budget), and the failure modes minbpe makes legible — spelling, counting, the non-English token tax, glitch tokens, special- token smuggling — are exactly what lets us attribute "Alice got it wrong" to input encoding vs. model vs. prompt. The allowed_special lesson maps directly onto Alice's untrusted connector surface (Telegram, web, embed widgets): never tokenize user text with allowed_special="all".

See also

• [[tokenization]] — the concept article minbpe is the reference implementation for (BPE vs WordPiece vs Unigram, byte-level, glitch tokens, the failure modes).
• [[nanochat]] · [[nanogpt]] — the model/capstone counterparts; [[microgpt-build-an-llm-from-scratch]] · [[llm-from-scratch]] · [[neural-network-from-scratch]] · [[nn-zero-to-hero]] — the from-scratch ladder.
• [[embeddings]] · [[positional-encoding]] · [[attention-and-transformers]] — where the token IDs minbpe produces go next.
• [[model-routing]] · [[graphrag]] · [[agent-memory-systems]] · [[mempalace]] — systems that budget against the token counts a tokenizer produces.

Primary sources

• Karpathy, minbpe — minimal byte-level BPE (train + encode/decode + GPT-4): <https://github.com/karpathy/minbpe> · source files: base.py↗ · regex.py↗ · gpt4.py↗ · exercise.md↗
• Karpathy, rustbpe — "the missing tiktoken training code" (Rust; used in nanochat): <https://github.com/karpathy/rustbpe>
• OpenAI tiktoken — fast byte-level BPE for inference (cl100k_base): <https://github.com/openai/tiktoken>
• fast.ai recap of Karpathy's "Let's Build the GPT Tokenizer": <https://www.fast.ai/posts/2025-10-16-karpathy-tokenizers>