Tokens and byte-pair encoding: write a tokenizer

A language model never sees text. It sees integers. The tokenizer is the translator, and it quietly shapes cost (you pay per token), context length, multilingual quality and strange failures such as models struggling to count letters. In this lesson you will write one.

#Why not characters or words?

Byte-pair encoding (BPE) builds a sub-word vocabulary from data: start with single bytes and repeatedly merge the most frequent adjacent pair into a new token.

#The algorithm

1. Convert text to bytes (0–255). The initial vocabulary is these 256 values.
2. Count every adjacent pair of tokens in the training text.
3. Merge the most frequent pair into a new token id (256, 257, ...), replacing it everywhere.
4. Repeat until the vocabulary has the target size.
5. To encode new text: start from its bytes and apply the learned merges, earliest first.
6. To decode: concatenate each token's bytes and decode as UTF-8.

#The code

from collections import Counter

def get_pairs(ids):
    return Counter(zip(ids, ids[1:]))

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

class BPE:
    def __init__(self):
        self.merges = {}                                  # (a, b) -> new id, in training order
        self.vocab = {i: bytes([i]) for i in range(256)}

    def train(self, text, vocab_size):
        ids = list(text.encode("utf-8"))
        for new_id in range(256, vocab_size):
            pairs = get_pairs(ids)
            if not pairs: break
            pair = max(pairs, key=lambda p: (pairs[p], -p[0], -p[1]))     # most frequent, deterministic tie-break
            if pairs[pair] < 2: break
            ids = merge(ids, pair, new_id)
            self.merges[pair] = new_id
            self.vocab[new_id] = self.vocab[pair[0]] + self.vocab[pair[1]]
        return ids

    def encode(self, text):
        ids = list(text.encode("utf-8"))
        while len(ids) >= 2:
            pairs = get_pairs(ids)
            pair = min(pairs, key=lambda p: self.merges.get(p, float("inf")))   # earliest-learned merge first
            if pair not in self.merges: break
            ids = merge(ids, pair, self.merges[pair])
        return ids

    def decode(self, ids):
        return b"".join(self.vocab[i] for i in ids).decode("utf-8", errors="replace")

#Try it

text = "low lower lowest low low newer newest wider widest wide " * 20
t = BPE(); ids = t.train(text, 280)
print(len(text.encode()), "bytes ->", len(ids), "tokens, merges:", len(t.merges))
for s in ["lowest widest", "naïve café 🙂"]:
    e = t.encode(s); assert t.decode(e) == s
    print(repr(s), len(s.encode()), "bytes ->", len(e), "tokens")
print([t.vocab[i] for i in list(t.merges.values())[:8]])

Output when run:

1120 bytes -> 82 tokens, merges: 24
'lowest widest' 13 bytes -> 4 tokens
'naïve café 🙂' 17 bytes -> 17 tokens
[b'lo', b'low', b' low', b' w', b'de', b'ide', b'st', b' wide']

Read this carefully:

• 1,120 bytes compressed to 82 tokens (13.7× fewer) because the toy text is extremely repetitive.
• The first merges are the most frequent pairs: lo, then low, then low. The vocabulary discovered that "low" is a unit without being told.
• 'lowest widest' (13 bytes) becomes 4 tokens, because these words appeared in training.
• 'naïve café 🙂' stays at one token per byte (17 tokens for 17 bytes): none of those bytes appeared in the training text, so there are no merges. Decoding still round-trips perfectly, which is the point of working at byte level: no unknown tokens, ever.

#What real tokenizers add

• Pre-tokenisation: split text with a regular expression first (words, numbers, punctuation, whitespace) so merges never cross word boundaries awkwardly; GPT-style tokenizers use such patterns.
• Special tokens: markers like end-of-text, chat-role delimiters and tool-call tokens, which are never produced by merges.
• Huge training corpora: hundreds of gigabytes, with optimised implementations (this one is quadratic-ish and only suitable for toy data).
• Other algorithms: WordPiece (BERT), Unigram/SentencePiece (many multilingual models), and byte-fallback variants.

#Why this matters in practice

• Cost and context are measured in tokens, not words. English averages roughly 1.3 tokens per word with common tokenizers; other languages and code can be 2–4× worse if the tokenizer was not trained on them (tokens and context).
• Letter-level tasks (counting letters, reversing words) are hard because the model sees tokens, not letters.
• Numbers: tokenisation of digits affects arithmetic (some tokenizers split digits individually to help).
• Whitespace and case change tokens: "Hello" and " hello" are different tokens, so prompt formatting matters, and chat templates must match training exactly (chat templates).
• Vocabulary size sets the embedding table: a 128k vocabulary at width 4,096 is 524M embedding parameters.
• Mismatched tokenizers between a draft and target model break speculative decoding (speculation).

#Exercises

1. Train the tokenizer on a paragraph of your own writing with vocab_size=400. How many tokens does it need compared with bytes? What are the first five merges?
2. Encode a sentence in another language. How many tokens per byte do you get?
3. Change the tie-break rule in train. Does encoding of your text change? (It may. Different tie-breaks give different but equally valid vocabularies.)
4. Why does encode have to repeat the pair search each round instead of doing one pass?

Answers: (1) Roughly 1.5 to 3 times fewer tokens than bytes on natural text with a small corpus; merges like th, t, e appear first. (2) Close to 1.0 token per byte for unseen scripts, which is why tokenizers trained mostly on English are expensive for other languages. (3) Possibly yes: ties between equally frequent pairs are arbitrary. (4) A merge creates a new token that can itself form pairs with its neighbours, so each applied merge changes what can merge next.

#Next

Turn token ids into batches the model can learn from: datasets, batches and embeddings.