Byte-Pair Encoding: the tokeniser you inherited

Sennrich, Haddow & Birch, 2015

The one component of your model that nobody trained and everybody blames.

Download tokenization_from_scratch.py — everything below runs from it. Pure Python and NumPy.

On the attention page I said what actually separates AI engineers isn't research maths — it's tokenisation edge cases, KV-cache maths, eval design. This is the tokenisation page. I owed it to you.

The thing I wish someone had told me earlier: the tokeniser is not part of the model. It's a lookup table fitted once on somebody else's corpus, then frozen and shipped alongside the weights — you cannot swap it without retraining. And almost every baffling LLM behaviour you've filed a ticket about traces straight back to it.

A lossy codec you did not choose

You already ship codecs. You know what happens when one sits in the middle of a pipeline: everything downstream inherits its assumptions. 

raw_bytes = open("photo.jpg", "rb").read()
# the JPEG encoder already decided what detail was worth keeping.
# your image pipeline doesn't get a vote. it gets the artefacts.

A tokeniser is that, for text — tuned to compress mostly English web text, and everything else pays for the mismatch: 

ids = tokeniser.encode(prompt)   # your string is gone now
out = model(ids)                 # the model has never seen a character
text = tokeniser.decode(out)     # and back, through the same frozen table

The model lives entirely on the right-hand side of that first line. It has no access to your letters. It has integers.

TermMeansProgrammer's analogy
Merge listOrdered rules: glue this pair into one symbolA migration file. Order is the schema.
VocabularySymbol → integer idA frozen dict, shipped with the weights
TokenOne entry in that dictA file handle. Opaque contents.
Pre-tokenisationWhere merges are forbidden to crossRecord boundaries before you compress

It came from translation, not from language models

Worth getting right, because it's an interview question. BPE was a 1994 compression algorithm. Sennrich, Haddow and Birch pointed it at words in 2015 to solve a machine-translation problem: a fixed vocabulary means an unseen word becomes <unk>, and you cannot translate <unk>. Their title says it — "Neural Machine Translation of Rare Words with Subword Units".

The fix is the one you'd reach for: if you can't store every word, store frequent pieces and spell the rest out. Open vocabulary. GPT inherited it years later because it happened to be the right tool.

The one formula, which is a for loop

merges = argmax(a,b) count(a,b)  →  merge  →  repeat n times

Read it as pipeline stages:

StepDataWhat it does
pre_tokenisetext → chunksSplit into units merges may not cross. Space stays glued to the word.
to_symbolschunk → tupleStart from single bytes. 256 of them, so nothing is unencodable.
count_pairscorpus → CounterEvery adjacent pair, weighted by word frequency.
merge_pairmost common pairGlue it everywhere. One new symbol, one new id.
repeatn timesn is your vocab-size budget minus 256. That's the only hyperparameter.

That's the paper: Counter.most_common(1) in a loop. No gradient, no objective function, no training in the sense you mean it.

Watch the vocabulary grow

The script trains on the toy corpus from the paper's own worked example, and prints every merge in order. Read it top to bottom: characters become fragments, fragments become stems, stems become whole words.

Don't take my word for it. Here's the actual output:

starting vocabulary: 11 characters -> ' deilnorstw'

merges, in the order they were learned:
  merge  1: 'e' + 's' -> 'es'       seen  9x, vocab 12
  merge  2: 'es' + 't' -> 'est'      seen  9x, vocab 13
  merge  3: 'l' + 'o' -> 'lo'       seen  7x, vocab 14
  merge  4: 'lo' + 'w' -> 'low'      seen  7x, vocab 15
  merge  5: ' ' + 'low' -> ' low'     seen  6x, vocab 16
  merge  6: ' ' + 'n' -> ' n'       seen  6x, vocab 17
  merge  7: ' n' + 'e' -> ' ne'      seen  6x, vocab 18
  merge  8: ' ne' + 'w' -> ' new'     seen  6x, vocab 19
  merge  9: ' new' + 'est' -> ' newest'  seen  6x, vocab 20  ← a whole word
  merge 10: ' ' + 'w' -> ' w'       seen  3x, vocab 21
  merge 11: ' w' + 'i' -> ' wi'      seen  3x, vocab 22
  merge 12: ' wi' + 'd' -> ' wid'     seen  3x, vocab 23   ✓

Now encode with those 12 rules. Frequency decides everything: how often a string appeared during tokeniser training is exactly how cheap it is for you at inference time, forever. 

        word  tokens                             count
------------  ---------------------------------- -----
         low  _low                               1
       lower  _low|e|r                           3
      newest  _newest                            1
      widest  _wid|est                           2
      lowest  _low|est                           2      ← never seen, still 2
    slowness  _|s|low|n|es|s                     6
  kubernetes  _|k|u|b|e|r|n|e|t|es               10     ← falls apart

lowest never appeared in the corpus. It still costs 2 tokens, because ' low' and 'est' both did. That is the 2015 paper's entire contribution, printed. kubernetes shares almost nothing with the corpus and degrades to characters — correct, just expensive. Your domain jargon is kubernetes.

Why it cannot count the r's in strawberry

The famous one. Here is the honest mechanical explanation, with the byte-level tokeniser the script trains on a slightly bigger English corpus: 

  strawberry: _strawberry
         ids: [361]
     letters: 10 characters -> 1 token

the model is asked 'how many r in strawberry'. What it received:
   [361]

One integer. There is no r in what the model received, the same way there's no filename inside a file descriptor. Asking it to count letters is asking it to introspect a symbol it only ever saw as an opaque id. Compare it to a task it's good at — reasoning about the meaning of token 361 — and the asymmetry stops being mysterious.

Be careful with this claim in an interview. Tokenisation is the main mechanical reason letter-counting is hard, not a proof that it's impossible. Spelling is discussed in the training text, so the mapping from token 361 to its letters can be memorised, and models often do get it right. "The model can't see letters" is right; "therefore it can never count them" is not.

The multilingual tax

This one costs money, and it will cost you money if your users write Tamil or Hindi. The same sentence, the same tokeniser, trained mostly on English: 

 language  chars  tokens   ratio
  English     45      21   1.00x  ✓
    Tamil     40     107   5.10x
    Hindi     39     101   4.81x

  English: 0.60 tokens per character
    Tamil: 3.06 tokens per character
    Hindi: 3.26 tokens per character

Every Tamil and Devanagari character is 3 UTF-8 bytes, and no merge ever learned to glue them, so each character costs roughly 3 tokens. Say that plainly: the same sentence in Tamil costs about five times as much and fits in a fifth of the context window. Not because Tamil is verbose. Because the codec was fitted on English.

My ratios are extreme — a toy tokeniser with 376 ids. Production tokenisers have merges for common Devanagari sequences and land closer to 2–3x. The direction is real and it's on your invoice.

The leading space is part of the token

Pre-tokenisation glues the space onto the following word. GPT-2 did this, everyone copied it, and it's the source of a whole family of "why did my prompt do that" bugs: 

  'the' -> the          ids [375]
 ' the' -> _the         ids [260]

same tokens? False

Two different integers for the same three letters. The model saw ' the' constantly (mid-sentence) and 'the' rarely (start of a line). End your prompt with a trailing space and you've handed it a token boundary it almost never trained on — then the next token it predicts has to be a word with no leading space, which is the rare branch. That's the whole trailing-space folklore, and it's just this.

Byte-level: the fallback that cannot fail

GPT-2's contribution here was small and enormous. Start from bytes, not characters. There are exactly 256 of them, so every possible input has an encoding and there is no <unk> token, ever — for any script, any emoji, any corrupted binary you accidentally pasted in. 

           '🍓' ->  4 utf-8 bytes,  4 tokens, unknown ids: 0
    round trip -> '🍓'
     'வணக்கம்' -> 21 utf-8 bytes, 21 tokens, unknown ids: 0
    round trip -> 'வணக்கம்' ✓

one strawberry emoji = 4 tokens: [172, 253, 235, 241]

Lossless round trip on all three. But look at the price: one emoji is four tokens, and to produce that one character the model must emit four correct ids in a row. Get one wrong and you have an invalid UTF-8 sequence in the middle of your JSON. That is why a single emoji breaks a schema you thought was safe — not a parser bug, a four-in-a-row bet.

SentencePiece solves a different half of this. Kudo and Richardson's system treats the input as a raw stream including spaces, writing the space as an ordinary symbol rather than applying language-specific whitespace rules first. So it needs no pre-tokeniser, it detokenises exactly, and it works for Japanese and Thai, which don't put spaces between words. It's a container for BPE and unigram, not a third algorithm.

The code

Pure Python (NumPy is imported only to pin the seed). No torch, no downloads — a tokeniser is small enough to write completely, so this file is the tokeniser. Every function under 20 lines.

Download the full script — 436 lines including seven runnable demos. Then: 

python3 tokenization_from_scratch.py
def to_symbols(word, byte_level=True):
    """A word -> the tuple of starting symbols BPE will merge."""
    if byte_level:
        return tuple(BYTE_TO_CHAR[b] for b in word.encode("utf-8"))
    return tuple(word)          # character-level: one symbol per character

def pre_tokenise(text):
    return re.findall(r" ?[^\s]+|\s+", text)

def count_pairs(freqs):
    pairs = Counter()
    for symbols, n in freqs.items():
        for a, b in zip(symbols, symbols[1:]):
            pairs[(a, b)] += n            # weighted by how often the word occurs
    return pairs

def merge_pair(symbols, pair):
    """Glue every occurrence of `pair` in one word into a single symbol."""
    out, i = [], 0
    while i < len(symbols):
        if i < len(symbols) - 1 and (symbols[i], symbols[i + 1]) == pair:
            out.append(symbols[i] + symbols[i + 1])
            i += 2
        else:
            out.append(symbols[i])
            i += 1
    return tuple(out)

def train_bpe(freqs, n_merges, trace=0, base_size=0):
    """Return the ordered merge list. Order IS the model -- rank matters."""
    merges = []
    for step in range(n_merges):
        pairs = count_pairs(freqs)
        if not pairs:
            break
        # ties broken by the pair itself, so two runs give identical output
        best_count = max(pairs.values())
        best = min(p for p, c in pairs.items() if c == best_count)
        freqs = {merge_pair(w, best): n for w, n in freqs.items()}
        merges.append(best)
    return merges

def encode_word(word, merges, byte_level=True):
    ranks = {pair: i for i, pair in enumerate(merges)}
    symbols = to_symbols(word, byte_level)
    while len(symbols) > 1:
        candidates = [(ranks[p], p) for p in zip(symbols, symbols[1:])
                      if p in ranks]
        if not candidates:
            break
        symbols = merge_pair(symbols, min(candidates)[1])   # lowest rank first
    return list(symbols)

BYTE_TO_CHAR (the 256-entry byte alphabet) and the trace printing inside train_bpe are elided here. Both are in the file.

Now break it

Demo 7 runs most of these and prints the broken version next to the working one. Do them by hand anyway — reverse-engineering from broken behaviour is faster than re-reading a method section.

Break thisWatch for
Train with train_bpe(freqs, 0) instead of 400A 32-character sentence goes from 6 tokens to 32. Everything is bytes again. You pay that on every request, forever.
Pass byte_level=False, then encode TamilAll 4 symbols of பூனை have no id at all. Byte-level: 12 tokens, 0 unknown.
Train with word_freqs(ENGLISH, pretokenise=False)168 merges contain a space; 138 tokens span two words, e.g. _the_model. One id now means "the model".
Encode English with tamil_merges6 tokens becomes 32. No error, no warning, valid ids throughout — silently worse.
Drop the leading space: encode("continues…")First id flips from 220 to 66 and the whole sequence differs from the one the model trained on.
In encode_word, use max(candidates)Merges apply in reverse rank order. Splits stop matching the training-time splits, still with no error.
Then read the papers — Sennrich's method section and its worked low / lower / newest example, which is the corpus in demo 1. Skip the BLEU tables. For SentencePiece, read the design section on treating input as a raw stream; skip the benchmarks.

On the maths anxiety

There isn't any. This is the paper on the site with the least maths in it: counting pairs, taking the most frequent, and a dictionary from string to integer. If you can write a Counter, you can write a tokeniser, and you just read one.

The only quantity worth internalising is the ratio: tokens per character for your users' actual languages. That's arithmetic, and it's the number that turns into your bill and your context budget.

Skipped here: the unigram tokeniser (SentencePiece's other algorithm, which scores candidate segmentations probabilistically instead of replaying merges), BPE-dropout, the exact GPT-2 regex, how special tokens like <|endoftext|> get injected outside the merge process, and whether tokenisation should exist at all.

Where to go next

This page gave you one thing: BPE as a merge list you trained yourself and can break. Here's where the parts I skipped live.

Order I'd take them in: Tiktokenizer first, for five minutes, to see it's real → Karpathy → then the two papers, which will feel short. Then the GPT page for what happens to those ids downstream, and attention if you haven't.