Atlas
kb://library/rustbpe2026-06-16

rustbpe — the missing tiktoken trainer (Rust BPE training)

tokenizationbperusttiktokennanochatkarpathytrainingpyo3rayon

rustbpe — the missing tiktoken trainer

One-line mental model: train the merges in Rust with `rustbpe`, run inference with `tiktoken`. rustbpe is the trainer that OpenAI's tiktoken never shipped.

What it is

rustbpe (Karpathy, MIT-licensed) is a small Rust library — with Python bindings — whose entire job is to train a GPT-style byte-pair-encoding (BPE) tokenizer: feed it a text corpus and a target vocabulary size, and it learns the ordered list of token-pair merges that define the tokenizer. Its own tagline is "The missing tiktoken training code."

The name says everything about where it sits in the ecosystem. There are three pre-existing options and each has a gap:

  • `tiktoken` (OpenAI) — "excellent for inference but doesn't support training." It can apply a tokenizer at very high speed, but it cannot learn one. There is no public OpenAI trainer.
  • HuggingFace `tokenizers` — can train, but "carries significant complexity from years of accumulated tokenizer variants" (many algorithms, configs, normalizers, and legacy formats).
  • `minbpe` (Karpathy's earlier teaching repo) — "handles both training and inference, but only in Python and not optimized for speed." Great to read, too slow to train a real vocab on a real corpus.

rustbpe is the fourth corner: a simple, fast, training-only BPE that learns the merges and then hands them off. The intended workflow is literally "Train your tokenizer with `rustbpe`, then export to `tiktoken` for fast inference." It is the same byte-level, regex-pre-tokenized algorithm OpenAI uses, so the vocab it produces is tiktoken-compatible by construction.

If you have never met BPE, read [[tokenization]] first (what a tokenizer is, why subwords, byte-level vs. char-level), and [[minbpe]] is the slow, readable Python sibling that rustbpe is a fast re-implementation of — start there if the algorithm below feels dense. (Note: at the time of writing the `minbpe` library article is referenced here in prose; if a `[[minbpe]]` slug does not yet exist in this library, treat the link as a forward pointer.)

Why it matters

For a project that needs its own tokenizer, the trainer is the missing third of the pipeline:

  1. Train the merges (learn the vocab) — this is what almost no public tool does well in a fast, dependency-light way. rustbpe.
  2. Encode/decode at training-and-serving time — fast, batched. tiktoken.
  3. Ship the vocab as a portable artifact (a list of (bytes, rank) pairs + a regex pattern + special tokens).

A custom tokenizer is not a luxury. Vocabulary choice changes the number of tokens per document, which directly changes training cost, context-window efficiency, and downstream perplexity. A tokenizer tuned to your corpus (your code, your language mix, your domain jargon) packs more meaning per token. But to get one you must be able to train it cheaply — and that is exactly the step that was awkward before rustbpe.

This matters concretely for OpenAlice, a Rust shop whose brain (alice-core) is Rust: rustbpe is the rare ML-infra component that is native to our stack rather than a Python dependency we tunnel into. See the OpenAlice section below.

How it works (real mechanics + code walkthrough)

The textbook algorithm (the slow truth)

BPE training, as the README states, is four steps:

  1. Start with 256 byte-level tokens (0x00–0xff). Working over raw bytes means every possible input is representable with zero "unknown token" problems — this is the byte-level trick.
  2. Count all adjacent token pairs in the corpus.
  3. Merge the most frequent pair into a single new token (the next ID, 256 + merges_done).
  4. Repeat until the vocabulary reaches the target size.

Naively, step 2 re-scans the whole corpus every iteration → roughly O(N × V) work (N = corpus size, V = vocab size). That's what minbpe does, and why it's slow. The interesting engineering in rustbpe is making the merge loop incremental so each merge touches only what changed.

Pre-tokenization: the GPT-4 split regex

Before counting anything, text is chopped into chunks by a regex so that merges never cross "obvious" boundaries (you don't want a token spanning the space between two words, or gluing a word to trailing punctuation). The default is the GPT-4 split pattern, used verbatim:

'(?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+

In English: split off contractions ('s, 'll, 've…), runs of letters (optionally with one leading non-letter like a space), runs of 1–3 digits, runs of punctuation, and whitespace. You can override it via the pattern argument; the default makes the output tiktoken/GPT-4 compatible. This is the same idea covered in [[tokenization]].

The core data structures (src/lib.rs)

type Pair = (u32, u32);

struct Tokenizer {
    merges: StdHashMap<Pair, u32>, // (a,b) -> new_id : the learned vocab
    pattern: String,               // the split regex (source)
    compiled_pattern: Regex,       // precompiled for speed
}

vocab_size() is simply 256 + merges.len(). Two internal helpers carry the algorithm:

struct Word { ids: Vec<u32> }      // one pre-tokenized chunk as a token sequence
//   .pairs(&self)                 -> adjacent pairs via windows(2)
//   .merge_pair(&mut self, pair, new_id) -> non-overlapping, left-to-right merge

struct MergeJob {
    pair: Pair,
    count: u64,
    pos: AHashSet<usize>,          // indices of the Words that contain this pair
}

MergeJob implements Ord to behave as a max-heap by frequency, with deterministic tie-breaking on the pair values (so two equally-frequent pairs always resolve the same way — reproducible vocabs).

The incremental merge loop — the actual speedup

This is the heart of it, in train_core_incremental(...):

  1. Parallel pair counting. count_pairs_parallel() uses `rayon` to count every adjacent pair across all Words at once, weighting each word by its corpus count (identical words are deduped to (Word, count), so a pair seen in a word that appears 10,000× is counted 10,000× via multiplication, not by reprocessing).
  2. Build the heap. Every pair becomes a MergeJob and goes into an `OctonaryHeap` — an 8-ary (d-ary) heap. A wider-branching heap trades a slightly more expensive sift for shallower depth and better cache behavior than a binary heap, which pays off when you push/pop millions of jobs.
  3. Merge `vocab_size - 256` times. Each iteration: - Pop the highest-count MergeJob. - Lazy-validation (lazy deletion). Compare the popped job.count against the live count for that pair. The loop never deletes stale entries from the heap eagerly; instead, when a pair's true count has dropped (because an earlier merge consumed some of its occurrences), the stale MergeJob is simply skipped on pop and the refreshed one is trusted. This "re-enqueue, validate-on-pop" pattern is what avoids O(N) bookkeeping per merge. - Assign the new id 256 + merges_done and record it in merges. - Apply `merge_pair()` — but only to the `Word`s in that job's `pos` set, not the whole corpus. This is the second half of the incrementality: the pos: AHashSet<usize> bounds the work to words that actually contain the pair. - Collect deltas. Each merge_pair() returns how pair-counts changed locally (merging AB→X destroys the pairs (left,A) and (B,right) and creates (left,X) and (X,right)). Multiply those deltas by the word's corpus count and fold them into the global pair-frequency table. - Re-enqueue the affected pairs (with updated counts and pos sets) back onto the heap.

So each merge does work proportional to the neighborhoods it disturbs, not the whole corpus — the difference between "re-count everything V times" and "patch the diff V times." This is the same family of optimization the GitHub engineering blog and the Rust-NLP write-up describe: keep eligible pairs in a priority queue, track positions, patch incrementally rather than rescan. (Both linked in Sources.)

Encoding and decoding

  • `encode(text) -> Vec<u32>`: split with the compiled regex → bytes (0–255) → repeatedly find the pair whose merged id is lowest (i.e. the earliest-learned merge — merges must be replayed in learning order to reproduce the vocab) and apply it, until no learned pair remains.
  • `decode(ids) -> String`: rebuild each token's byte string from base bytes + the sorted merges, concatenate, and UTF-8-decode with error handling (because an arbitrary id-slice can land mid-multibyte-character).
  • `batch_encode(texts)`: rayon-parallel encode across many strings.

The Python bridge and the hand-off to tiktoken

rustbpe exposes the Tokenizer to Python through `PyO3` (#[pyclass] / #[pymethods] / #[pymodule] fn rustbpe()), with pyo3_log wiring Rust logs into Python. train_from_iterator refills a buffer under the GIL, then releases the GIL to do the heavy regex+count work in parallel — the correct pattern for a CPU-bound Rust extension.

Two getters exist purely for the export step: get_pattern() and get_mergeable_ranks() -> Vec<(Vec<u8>, u32)>. The whole point of the library is this five-line hand-off:

import rustbpe, tiktoken

tok = rustbpe.Tokenizer()
tok.train_from_iterator(open("corpus.txt"), vocab_size=8192)

enc = tiktoken.Encoding(
    name="my_tokenizer",
    pat_str=tok.get_pattern(),
    mergeable_ranks={bytes(k): v for k, v in tok.get_mergeable_ranks()},
    special_tokens={},
)
ids = enc.encode("hello world")   # fast inference via tiktoken

Install is pip install rustbpe, or from source with maturin develop --release (the standard Rust-extension build via uv/maturin).

How nanochat actually uses it

[[nanochat]] — Karpathy's "$100 ChatGPT" full pipeline — is the real-world consumer. In nanochat/tokenizer.py, the RustBPETokenizer:

  • trains with tokenizer.train_from_iterator(text_iterator, vocab_size_no_special, pattern=SPLIT_PATTERN), where vocab_size_no_special = vocab_size - len(SPECIAL_TOKENS) (special tokens are not learned — they're reserved IDs appended after the learned merges);
  • exports to a tiktoken.Encoding via get_pattern() + get_mergeable_ranks() exactly as above;
  • registers chat special tokens separately: <|bos|>, <|user_start|>, <|user_end|>, <|assistant_start|>, <|assistant_end|>, <|python_start|>, <|python_end|> — the turn/role markers that make a base tokenizer chat-aware.

The division of labor is explicit and is the whole thesis: Rust (`rustbpe`) for the performance-critical training, `tiktoken` for high-throughput inference at serving time, with an algorithm "identical to the one used by OpenAI (regex splitting, byte-level BPE)."

Key ideas & tradeoffs

  • Training-only, on purpose. It does ship encode/decode (needed for tests and quick checks), but it does not try to be a fast inference engine. That job is delegated to tiktoken, which is faster and battle-tested. Doing one thing keeps the codebase tiny.
  • Byte-level base (256 tokens). No <unk>, every input is representable, language-agnostic. Standard modern practice (GPT-2 onward).
  • Incremental + parallel is the entire reason to exist. minbpe is the same algorithm; rustbpe is minbpe made fast via Rust + rayon + a d-ary heap with lazy deletion + position-bounded re-counting. The README is honest that this is "relatively efficient," not a benchmark-crowned speed king.
  • `tiktoken`-compatible output by default. The default GPT-4 pattern + byte-level merges mean the exported vocab drops straight into tiktoken.Encoding with no translation layer.
  • Deterministic. Tie-breaking in MergeJob::Ord makes the learned vocab reproducible across runs — important for caching and for "did my tokenizer change?" diffs.
  • Small dependency surface: rayon (parallelism), PyO3/pyo3_log (bindings), a regex engine, and ahash for fast hashing. No giant tokenizer framework.

Honest caveats

  • No published benchmark numbers. The README claims efficiency but ships no head-to-head timings against minbpe or HuggingFace. "Fast" here is "fast enough to train a real vocab without pain," asserted, not measured. The complexity intuition (incremental beats O(N×V) rescans) is sound and matches the broader literature, but treat specific speed claims as unverified.
  • It is young and small. Fewer knobs than HuggingFace tokenizers (no normalizers, no alternative algorithms like Unigram/WordPiece, limited config surface). That's the design — but if you need those, this is the wrong tool.
  • Author's own disclosure on provenance. Karpathy is unusually candid: "I wrote the Python reference code personally and from scratch and I am expert there and understand it fully. I then wrote the Rust code against this implementation with tests for equality. However, I am not a Rust developer by background so I had significant help from ChatGPT and Claude Code Opus 4.5." So: the algorithm is expert-authored and test-pinned against a reference; the Rust is LLM-assisted. The equality tests against the Python reference are what give it credibility — read tests/python/ before trusting it in production.
  • Encode/decode are for parity, not production. Use tiktoken for serving. The library's own README steers you there.
  • Fetch transparency for this article: the canonical src/lib.rs, the repo/README, and the nanochat tokenizer.py all fetched cleanly and corroborate each other. One attempt — the nanochat-vendored copy of rustbpe/src/lib.rs at a guessed path — returned HTTP 404 and was dropped; nothing from it is asserted here. The README on raw-githubusercontent returned a summary (it lacks an explicit benchmark/comparison-table section), and the comparison framing in this article comes from the rendered GitHub README, which is consistent across fetches. No numbers were invented.

OpenAlice + Academy ladder

Why OpenAlice cares. alice-core is Rust. Most ML infra reaches us as a Python dependency we have to wrap, host, or shell out to. rustbpe is the opposite: a tokenizer trainer that is already in our language, with a tiny dependency set (rayon, pyo3, ahash, a regex). If OpenAlice ever wants a domain-tuned tokenizer — one fit to our code corpus, our multilingual chat logs, our tool-call / special-token grammar — rustbpe is the reference design for the trainer, and it shows the exact pattern (get_pattern() + get_mergeable_ranks() → portable artifact) for shipping that vocab to any inference path. The nanochat special-token list (<|bos|>, <|user_start|>, role/turn markers, <|python_start|>) is also a clean template for how Alice's own turn/tool grammar would reserve IDs after the learned merges. It pairs naturally with our interest in small, controllable models — see [[nanochat]] and [[nanogpt]].

Academy ladder (beginner → builder → contributor):

  1. Concept. Read [[tokenization]] end to end: bytes → pairs → merges → vocab; why subwords; why byte-level. Know what "a merge" is before reading code.
  2. Read the slow version. Walk minbpe (the Python reference rustbpe is built against) — small enough to hold in your head. (prose link; verify the `[[minbpe]]` slug exists in this library before relying on the cross-link.)
  3. Train one. pip install rustbpe, train a 4k–8k vocab on a small corpus, export to tiktoken, and diff token counts before/after. Feel how vocab size trades against tokens-per-document.
  4. Read the fast version. Open src/lib.rs and find the four moving parts this article named: the GPT-4 split regex, count_pairs_parallel (rayon), the `OctonaryHeap` + `MergeJob` lazy-deletion loop, and the pos-bounded merge_pair re-counting. That quartet is the optimization.
  5. See it in a real pipeline. Trace [[nanochat]]'s tokenizer.py: how training (rustbpe) and inference (tiktoken) are deliberately split, and how special tokens are layered on after the learned merges.
  6. Build context. Pair this with [[llm-from-scratch]], [[microgpt-build-an-llm-from-scratch]], [[nn-zero-to-hero]], and [[embeddings]] (what those token IDs feed into). Tokenization is step zero of the whole stack.

See also: [[tokenization]] · [[nanochat]] · [[nanogpt]] · [[llm-from-scratch]] · [[microgpt-build-an-llm-from-scratch]] · [[nn-zero-to-hero]] · [[embeddings]]. (The minbpe slug is referenced in prose; promote to a [[minbpe]] link once that library page exists.)