Byte pair encoding, step by step: Tokens and tokenisation

How the vocabulary is built: start from bytes and keep merging the most common neighbouring pair.

Byte pair encoding (BPE)

A method for building a vocabulary. Start with single bytes, then repeatedly merge the pair of neighbouring pieces that occurs most often in the training text into one new token, until the vocabulary reaches the size you want.

Training (done once, before the model):

Turn the training text into bytes. The vocabulary starts with 256 entries, one per byte.
Count every pair of neighbouring pieces in the text.
Merge the most common pair into a new token: add it to the vocabulary and record the merge.
Replace that pair everywhere in the text, then go back to step 2.
Stop at the vocabulary size you want.

Encoding new text: turn it into bytes, then apply the recorded merges in the order they were learned, until none applies.

A tiny example by hand

Take the word banana. As bytes it is b a n a n a. Counting pairs: an appears twice, na appears twice, ba once. It is a tie, so the program needs a tie-break rule. The example code breaks ties by choosing the larger pair, which is na. Here is a real trace from the example code (the numbers are byte values: b is 98, a is 97, n is 110; new tokens start at 256):

start   [98, 97, 110, 97, 110, 97]      b  a  n  a  n  a
merge 1 (n,a) -> 256   [98, 97, 256, 256]     b  a  na na
merge 2 (na,na) -> 257 [98, 97, 257]          b  a  nana
merge 3 (b,a) -> 258   [258, 257]             ba nana

Six pieces became two. Decoding reverses it: each token number is replaced by the bytes it stands for, and the bytes are read as text, giving banana again. Another tie-break rule would give a different, equally valid result. That is why Easy 2 asks you to state your rule.

The code

The core of the example in code/mini-bpe is a few lines:

def pair_counts(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

def train(self, text, vocab_size):
    ids = list(text.encode("utf-8"))
    for new_id in range(256, vocab_size):
        counts = pair_counts(ids)
        pair = max(counts, key=lambda p: (counts[p], p))   # most frequent pair
        ids = merge(ids, pair, new_id)
        self.merges[pair] = new_id
        self.vocab[new_id] = self.vocab[pair[0]] + self.vocab[pair[1]]

Read it: pair_counts lists every neighbouring pair and counts them. merge walks along the list and replaces each occurrence of a pair with a new ID. train repeats "count, pick the most common, merge" and records each merge. (The real file also stops when no pair occurs at least twice.)

Training the example tokenizer on a short, repetitive English text (the ENGLISH string in demo.py) with vocabulary size 300 learns 44 merges. The first eight are: space+t, h+e, e+n, spacet+he, spacet+o, space+a, spaceto+k, spacetok+en. This is how a diagram of encoding "the tokens" goes, with ␣ marking a space:

A real trace from the example tokenizer. The common word-pieces were merged during training, so 10 bytes shrink to 3 tokens.

>>> t.encode("the tokens")
[116, 257, 264]
>>> t.pieces("the tokens")
['t', 'he', ' tokens']

This is a toy tokenizer

Real tokenizers first split the text into words, digits and punctuation, so merges never cross word boundaries, and they are written in fast compiled code and trained on huge amounts of text. The example trains on a very small, repetitive text, which is why it learned an odd piece such as the whole phrase agent reads the. It teaches the idea. Do not use it for counting real tokens.

Check yourself

In banana, why is there a tie, and what decides it?
When encoding, why must merges be applied in the order they were learned?