BPE Tokenizer From Scratch
Bytes in, ids out, ids back to the same bytes. Build the tokenizer that every modern text model still starts from.
Learning Objectives
- Train a Byte-Pair Encoding vocabulary from a raw text corpus by repeatedly merging the most frequent adjacent symbol pair.
- Implement a deterministic merge table and apply it to fresh text to produce a stream of subword ids.
- Round-trip arbitrary UTF-8 input to ids and back without information loss.
- Reserve and protect special tokens (
<|endoftext|><|pad|>) so they survive training and decoding. - Reason about why a byte-level alphabet is the right floor for a general-purpose tokenizer.
The frame
A language model never sees text. It sees integers. The map from a string to a list of integers and back is the tokenizer. Get this layer wrong and every loss curve in the training run is measuring the wrong thing.
The dominant family of subword tokenizers for general text models is Byte-Pair Encoding. The idea is small. Start from a known alphabet. Find the adjacent symbol pair that appears most often in the training corpus. Merge it into a new symbol. Repeat until the vocabulary reaches the target size. Encoding new text reuses the same merge list in the same order.
We will build the byte-level variant. The alphabet is the 256 raw bytes, not Unicode code points. That choice is what lets the tokenizer handle any UTF-8 input without falling back to an unknown token.
The pipeline
The training side and the inference side share the merge table. That sharing is the contract. If you change the merge order at inference, you decode a different stream of ids.
The byte alphabet
The first 256 ids are reserved for the raw bytes 0x00 through 0xFF. That guarantees every input string can be expressed in the vocabulary before any merge happens. After the byte block we reserve a small range for special tokens. The training loop never proposes those ids as merge targets because we keep them out of the pretokenized stream entirely.
The pretokenizer splits the corpus on whitespace and punctuation boundaries before training sees it. Without that split the BPE merge step would happily learn merges that cross word boundaries and the vocabulary fills up with whole common phrases. With the split, merges stay inside a word and the result generalizes.
The training loop
For each training step the loop does three things. It walks every word in the corpus and counts how often each adjacent pair of current symbols appears, weighted by how often the word itself appears. It picks the pair with the highest count. It rewrites every occurrence of that pair into a single new symbol whose id is the next free slot in the vocabulary. Then it records the merge.
The cost of each step is linear in the size of the corpus expressed as a list of symbol sequences. For a million words and a target vocabulary of ten thousand ids the loop runs to completion in seconds because the symbol sequences shrink as merges land.
Encoding fresh text
Inference does not call the merge counter. It applies the merge table in the same order it was learned. For a fresh word the encoder starts from the byte split. It scans the current sequence for the lowest-ranked merge (the earliest one that applies). It performs that merge. It scans again. The loop ends when no merge in the table applies to the current sequence.
The ordering by rank is the property that makes encoding deterministic and matches the training behavior on the same input. A merge that was learned first sits at the top of the table and gets applied first. If two merges could apply at the same position, the lower-rank one wins.
Special tokens
Special tokens are ids that the byte stream can never produce. We reserve them by hand. Two are enough for this lesson.
<|endoftext|>separates documents during pretraining. It tells the model "a new document starts here, do not let the previous one's context leak in."<|pad|>fills out short sequences so a batch can be a rectangular tensor. The loss mask hides it during training.
The encoder accepts a flag to allow special tokens in the input. With the flag off, the strings <|endoftext|> and <|pad|> get tokenized as the bytes that spell them out. With the flag on, the literal strings get mapped to their reserved ids and are not subject to any merge.
Round-trip guarantee
Encoding then decoding must return the input bytes exactly. The decoder concatenates the byte expansion of every id in order. Since every id is either a raw byte or the concatenation of two previously known ids, the recursive expansion always terminates in raw bytes. Decoding then returns the UTF-8 string that those bytes spell.
The test suite in this lesson checks that property on an unseen sentence, on a sentence with a Unicode emoji, and on a sentence that contains a literal <|endoftext|> token.
What this lesson does not do
It does not build a regex-driven pretokenizer in the style of the largest production tokenizers. The pretokenizer here is a small whitespace and punctuation split. It is enough to produce sensible merges on a small training corpus and the contract with the rest of the lesson chain stays the same. The next lesson treats the tokenizer as a black box and builds the sliding-window dataset on top of it.
It does not parallelize the pair counter. A loop in Python over a corpus of a few thousand words finishes in well under a second. For larger corpora the obvious move is to count pairs per word in parallel and reduce.
How to read the code
main.py defines four objects. BPETokenizer holds the vocabulary, the merge table, and the special-token table. train is the training loop. encode is the inference path. decode is the byte concatenation. The demo at the bottom trains a small tokenizer on a built-in corpus, encodes a held-out sentence, decodes the ids back, and prints both. The tests in code/tests/test_bpe.py pin the round-trip property, the special-token reservation, and the merge ordering.
Run the demo. Then change the target vocabulary size in the demo from 300 to 600 and watch how the encoded length of the held-out sentence drops. That curve is the BPE compression curve.
Check what you learned
6 questions. Answer each one to see why.
Why does a byte-level BPE tokenizer start from a 256-symbol alphabet?
The full code
Every file for this lesson. Copy it, run it, then change it.
"""Byte-Pair Encoding tokenizer from scratch.
Trains a byte-level BPE vocabulary on a small built-in corpus, encodes a
held-out sentence, decodes it back, and prints both.
Stdlib + nothing else. Run: python3 code/main.py
"""
from __future__ import annotations
import json
import re
from collections import Counter
from dataclasses import dataclass, field
from typing import Iterable
BYTE_ALPHABET_SIZE = 256
DEFAULT_SPECIALS = ("<|endoftext|>", "<|pad|>")
WORD_SPLIT_RE = re.compile(r"\S+|\s+")
@dataclass
class BPETokenizer:
"""Byte-level BPE tokenizer.
The first 256 ids map to raw bytes. Special tokens occupy a small block
above that. Learned merges fill the rest of the vocabulary.
"""
vocab: dict[int, bytes] = field(default_factory=dict)
inv_vocab: dict[bytes, int] = field(default_factory=dict)
merges: dict[tuple[int, int], int] = field(default_factory=dict)
special_to_id: dict[str, int] = field(default_factory=dict)
id_to_special: dict[int, str] = field(default_factory=dict)
@property
def vocab_size(self) -> int:
return len(self.vocab)
def _add_token(self, token_bytes: bytes) -> int:
if token_bytes in self.inv_vocab:
return self.inv_vocab[token_bytes]
token_id = len(self.vocab)
self.vocab[token_id] = token_bytes
self.inv_vocab[token_bytes] = token_id
return token_id
def initialize(self, specials: Iterable[str] = DEFAULT_SPECIALS) -> None:
"""Lay out the byte alphabet and reserve special-token ids."""
self.vocab.clear()
self.inv_vocab.clear()
self.merges.clear()
self.special_to_id.clear()
self.id_to_special.clear()
for i in range(BYTE_ALPHABET_SIZE):
self._add_token(bytes([i]))
for s in specials:
token_id = len(self.vocab)
self.vocab[token_id] = s.encode("utf-8")
self.inv_vocab[s.encode("utf-8")] = token_id
self.special_to_id[s] = token_id
self.id_to_special[token_id] = s
def _pretokenize(text: str) -> list[str]:
"""Split text on whitespace/non-whitespace runs.
Each chunk becomes one BPE training unit. Merges never cross chunk
boundaries. Whitespace runs are preserved as their own chunks so the
decoder can rebuild the original string by concatenation.
"""
return WORD_SPLIT_RE.findall(text)
def _word_to_byte_ids(word: str) -> list[int]:
return list(word.encode("utf-8"))
def _count_pairs(corpus_units: dict[tuple[int, ...], int]) -> Counter:
pairs: Counter = Counter()
for symbols, count in corpus_units.items():
for i in range(len(symbols) - 1):
pairs[(symbols[i], symbols[i + 1])] += count
return pairs
def _apply_merge(symbols: tuple[int, ...], pair: tuple[int, int], new_id: int) -> tuple[int, ...]:
if len(symbols) < 2:
return symbols
out: list[int] = []
i = 0
a, b = pair
while i < len(symbols):
if i < len(symbols) - 1 and symbols[i] == a and symbols[i + 1] == b:
out.append(new_id)
i += 2
else:
out.append(symbols[i])
i += 1
return tuple(out)
def train(
tokenizer: BPETokenizer,
corpus: str,
target_vocab_size: int,
specials: Iterable[str] = DEFAULT_SPECIALS,
) -> None:
"""Train BPE merges on `corpus` until the vocabulary reaches `target_vocab_size`.
The training loop is deterministic given the corpus. Ties on pair counts
are broken by sorting on the pair itself so two runs over the same input
produce the same merge table.
"""
tokenizer.initialize(specials)
units = _build_initial_units(corpus)
while tokenizer.vocab_size < target_vocab_size:
pairs = _count_pairs(units)
if not pairs:
break
max_count = max(pairs.values())
candidates = sorted(p for p, c in pairs.items() if c == max_count)
best = candidates[0]
if pairs[best] < 2:
break
new_id = tokenizer._add_token(
tokenizer.vocab[best[0]] + tokenizer.vocab[best[1]]
)
tokenizer.merges[best] = new_id
units = _apply_merge_to_corpus(units, best, new_id)
def _build_initial_units(corpus: str) -> dict[tuple[int, ...], int]:
chunks = _pretokenize(corpus)
units: dict[tuple[int, ...], int] = {}
for chunk in chunks:
symbols = tuple(_word_to_byte_ids(chunk))
units[symbols] = units.get(symbols, 0) + 1
return units
def _apply_merge_to_corpus(
units: dict[tuple[int, ...], int],
pair: tuple[int, int],
new_id: int,
) -> dict[tuple[int, ...], int]:
new_units: dict[tuple[int, ...], int] = {}
for symbols, count in units.items():
merged = _apply_merge(symbols, pair, new_id)
new_units[merged] = new_units.get(merged, 0) + count
return new_units
def _encode_chunk(tokenizer: BPETokenizer, chunk: str) -> list[int]:
symbols: list[int] = _word_to_byte_ids(chunk)
if len(symbols) < 2:
return symbols
ranked_merges = {pair: rank for rank, pair in enumerate(tokenizer.merges.keys())}
while True:
best_rank = None
best_index = -1
best_pair: tuple[int, int] | None = None
for i in range(len(symbols) - 1):
pair = (symbols[i], symbols[i + 1])
rank = ranked_merges.get(pair)
if rank is None:
continue
if best_rank is None or rank < best_rank:
best_rank = rank
best_index = i
best_pair = pair
if best_pair is None:
break
new_id = tokenizer.merges[best_pair]
symbols = symbols[:best_index] + [new_id] + symbols[best_index + 2:]
return symbols
def encode(
tokenizer: BPETokenizer,
text: str,
allow_special: bool = False,
) -> list[int]:
"""Encode `text` to a list of token ids.
When `allow_special` is True, literal special-token strings in the input
are mapped to their reserved ids and skipped by the merge loop.
"""
if not allow_special:
return _encode_pretokenized(tokenizer, text)
if not tokenizer.special_to_id:
return _encode_pretokenized(tokenizer, text)
specials_sorted = sorted(tokenizer.special_to_id.keys(), key=len, reverse=True)
pattern = "(" + "|".join(re.escape(s) for s in specials_sorted) + ")"
parts = re.split(pattern, text)
out: list[int] = []
for part in parts:
if part == "":
continue
if part in tokenizer.special_to_id:
out.append(tokenizer.special_to_id[part])
else:
out.extend(_encode_pretokenized(tokenizer, part))
return out
def _encode_pretokenized(tokenizer: BPETokenizer, text: str) -> list[int]:
out: list[int] = []
for chunk in _pretokenize(text):
out.extend(_encode_chunk(tokenizer, chunk))
return out
def decode(tokenizer: BPETokenizer, ids: list[int]) -> str:
"""Decode `ids` back to a string. Inverse of `encode` for round-trip safe input."""
pieces: list[bytes] = []
for token_id in ids:
if token_id in tokenizer.id_to_special:
pieces.append(tokenizer.id_to_special[token_id].encode("utf-8"))
continue
if token_id not in tokenizer.vocab:
raise KeyError(f"unknown token id: {token_id}")
pieces.append(tokenizer.vocab[token_id])
return b"".join(pieces).decode("utf-8", errors="replace")
def save(tokenizer: BPETokenizer, path: str) -> None:
"""Serialize the tokenizer to a JSON file."""
payload = {
"vocab": {
str(token_id): list(token_bytes)
for token_id, token_bytes in tokenizer.vocab.items()
},
"merges": [
[list(pair), new_id]
for pair, new_id in tokenizer.merges.items()
],
"specials": tokenizer.special_to_id,
}
with open(path, "w", encoding="utf-8") as f:
json.dump(payload, f, indent=2)
def load(path: str) -> BPETokenizer:
"""Restore a tokenizer previously written with `save`."""
with open(path, "r", encoding="utf-8") as f:
payload = json.load(f)
tokenizer = BPETokenizer()
for token_id_str, byte_list in payload["vocab"].items():
token_id = int(token_id_str)
token_bytes = bytes(byte_list)
tokenizer.vocab[token_id] = token_bytes
tokenizer.inv_vocab[token_bytes] = token_id
for pair, new_id in payload["merges"]:
tokenizer.merges[(pair[0], pair[1])] = new_id
for s, token_id in payload["specials"].items():
tokenizer.special_to_id[s] = token_id
tokenizer.id_to_special[token_id] = s
return tokenizer
DEMO_CORPUS = """\
the quick brown fox jumps over the lazy dog
a journey of a thousand miles begins with a single step
the only way to do great work is to love what you do
the best time to plant a tree was twenty years ago
the second best time is now
practice is the bridge between intention and skill
small daily actions compound into large outcomes
read more than you write, write more than you talk
the map is not the territory and the menu is not the meal
what gets measured gets managed if the measurement is honest
the quick brown fox runs across the meadow at dawn
a small step today is better than a perfect plan tomorrow
courage is not the absence of fear it is action despite fear
the lazy dog sleeps under the old oak tree
every expert was once a beginner who refused to quit
focus is saying no to a hundred good ideas
the river that you cannot cross today will be easier tomorrow
practice the basics until the basics become invisible
""" * 6
def _print_section(title: str) -> None:
bar = "-" * len(title)
print(f"\n{title}\n{bar}")
def _format_byte_token(token_bytes: bytes) -> str:
try:
return token_bytes.decode("utf-8").replace("\n", "\\n").replace(" ", "·")
except UnicodeDecodeError:
return token_bytes.hex()
def main() -> int:
target = 320
tokenizer = BPETokenizer()
train(tokenizer, DEMO_CORPUS, target_vocab_size=target)
_print_section("Vocabulary summary")
print(f"target size : {target}")
print(f"final vocab size : {tokenizer.vocab_size}")
print(f"merges learned : {len(tokenizer.merges)}")
print(f"special tokens : {list(tokenizer.special_to_id)}")
held_out = "the fox is quick and the dog is lazy"
ids = encode(tokenizer, held_out)
roundtrip = decode(tokenizer, ids)
_print_section("Encoding a held-out sentence")
print(f"input : {held_out!r}")
print(f"encoded ids : {ids}")
print(f"id count : {len(ids)} (vs {len(held_out.encode('utf-8'))} raw bytes)")
print(f"decoded back : {roundtrip!r}")
assert roundtrip == held_out, "round trip must be lossless"
_print_section("Highest-rank learned merges")
for rank, (pair, new_id) in enumerate(list(tokenizer.merges.items())[:8]):
left = _format_byte_token(tokenizer.vocab[pair[0]])
right = _format_byte_token(tokenizer.vocab[pair[1]])
merged = _format_byte_token(tokenizer.vocab[new_id])
print(f" rank {rank:>2}: ({left!s:>8}, {right!s:>8}) -> {merged}")
_print_section("Special-token handling")
with_specials = "doc one<|endoftext|>doc two"
ids_special = encode(tokenizer, with_specials, allow_special=True)
assert tokenizer.special_to_id["<|endoftext|>"] in ids_special
print(f"input : {with_specials!r}")
print(f"encoded ids : {ids_special}")
print(f"decoded back : {decode(tokenizer, ids_special)!r}")
print("\nDemo OK.")
return 0
if __name__ == "__main__":
raise SystemExit(main())