Byte-pair encoding tokenization

Intermediate

Introduction

Before a large language model reads a single word, a tokenizer cuts the text into pieces and turns each piece into a number. Whole words are a bad choice: no vocabulary can list every name, typo and new word, and a word missing from it becomes an unknown token. Single characters always work but make texts very long. Sub-word tokenization sits in between: frequent words are one token, and rare words split into a few frequent pieces, such as "un", "believ" and "able". Byte-pair encoding (BPE) is the most widely used method; GPT models, Llama and many others use variants of it.

How it works

Training starts from a corpus of words with their frequencies. Each word is split into characters, plus an end-of-word marker (written _ here; papers often use a special symbol), so that "est_" at the end of a word can differ from "est" inside one. Then repeat:

  1. Count every pair of neighbouring symbols, weighting each by the frequency of its word.
  2. Take the most frequent pair (break ties by a fixed rule, such as alphabetical order).
  3. Merge it: replace that pair everywhere with a single new symbol, and record the merge rule.

Stop after a chosen number of merges. The vocabulary is the starting characters plus one new symbol per merge; real tokenizers use tens of thousands of merges.

Tokenizing a new word applies the merge rules in the order they were learned: split the word into characters plus the marker, apply merge 1 everywhere, then merge 2, and so on. A word seen often in training collapses into one token; an unseen word still splits into known pieces. Finally each token is looked up in the vocabulary to get its token id, the number the model actually sees. Characters the tokenizer never saw become an unknown token; byte-level BPE avoids this by starting from the 256 possible bytes instead of characters, so any text at all can be encoded.

The vocabulary size is a trade-off: more merges mean longer tokens and shorter sequences (cheaper for the model), but a bigger embedding table and rarer tokens. Tokenization also explains some odd model behaviour: a model that sees "strawberry" as two or three tokens does not directly see its letters, which is why counting letters can be hard for it.

Example

import re

words = {"l o w _": 5, "l o w e r _": 2, "n e w e s t _": 6, "w i d e s t _": 3}
merges = []


def merge(text, pair):
    return re.sub(r"(?<!\S)" + re.escape(pair) + r"(?!\S)", pair.replace(" ", ""), text)


for step in range(1, 7):
    counts = {}
    for text, freq in words.items():
        symbols = text.split()
        for a, b in zip(symbols, symbols[1:]):
            counts[a + " " + b] = counts.get(a + " " + b, 0) + freq
    top = max(counts.values())
    best = min(p for p in counts if counts[p] == top)
    merges.append(best)
    words = {merge(text, best): freq for text, freq in words.items()}
    print(f"merge {step}: {best} -> {best.replace(' ', '')} ({top})")
print("training words:", list(words))

for new_word in ["lowest", "newer"]:
    text = " ".join(new_word) + " _"
    for pair in merges:
        text = merge(text, pair)
    print(new_word, "->", text.split())
Open in compiler

Line by line

  1. Each training word is stored as its current split, space-separated symbols ending in _ such as "n e w e s t _", together with its frequency.
  2. Pair counts are weighted by word frequency: "e s" appears in "newest" (6 times) and "widest" (3 times), so it counts 9.
  3. Ties are broken by taking the alphabetically smallest pair; "e s" beats "s t" and "t _".
  4. merge uses a regular expression that only matches whole symbols, so merging "e s" never touches the "e" of "es".
  5. After six merges, "low" and "est_" are single tokens, and "lowest", never seen in training, becomes just "low" + "est_".
  6. "newer" is also new; it reuses the "ew" piece and falls back to single characters for the rest.

Expected result

merge 1: e s -> es (9)
merge 2: es t -> est (9)
merge 3: est _ -> est_ (9)
merge 4: l o -> lo (7)
merge 5: lo w -> low (7)
merge 6: e w -> ew (6)
training words: ['low _', 'low e r _', 'n ew est_', 'w i d est_']
lowest -> ['low', 'est_']
newer -> ['n', 'ew', 'e', 'r', '_']

In the real world

With Hugging Face's transformers library (shown, not run: it is not available in StepVioz's browser Python, and it downloads the tokenizer files):

from transformers import AutoTokenizer

tokenizer = AutoTokenizer.from_pretrained("gpt2")
print(tokenizer.tokenize("Tokenization is unbelievable"))
print(tokenizer.encode("Tokenization is unbelievable"))

GPT-2 uses byte-level BPE with about 50,000 merges, and marks a token that starts after a space with the character "Ġ". Other models use WordPiece (BERT) or SentencePiece's unigram model (T5), which differ in how they choose pieces but give similar results. API prices and context limits for language models are counted in these tokens, and languages that the tokenizer saw less during training need more tokens for the same text.

Common mistakes

  • Applying merges in the wrong order, or greedily by length, which gives different tokens from training.
  • Merging inside other symbols: replacing the text "e s" in "es s" by plain string replacement can join the wrong pieces; match whole symbols.
  • Forgetting the end-of-word marker, so endings like "est" cannot be told apart from the middle of words.
  • Training the tokenizer on different text from what the model will see, which wastes vocabulary on the wrong pieces.

Best practices

  • Fix the tie-breaking rule so training is reproducible.
  • Keep the merges and the vocabulary together; a model only works with the exact tokenizer it was trained with.
  • Check the average number of tokens per word on your own text, especially for other languages.
  • Use byte-level BPE when the text may contain any character, such as emojis or code.

Summary

Sub-word tokenizers keep common words whole and split rare words into frequent pieces, so every word can be represented. BPE trains by counting neighbouring symbol pairs, weighted by word frequency, and repeatedly merging the most frequent pair. New text is tokenized by applying the merges in their learned order and mapping the tokens to ids, which are what language models actually read.

Quick check

1. Why do language models use sub-word tokens instead of whole words?
2. What does one step of BPE training do?
3. How is a new word tokenized with learned BPE merges?
4. What is the main advantage of byte-level BPE?

Key takeaways

  • Sub-word tokenizers handle any word: common words become one token and rare words split into pieces.
  • BPE training is counting pairs and merging the most frequent one, over and over.
  • New text is tokenized by applying the learned merges in their original order.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.