BPE

BPE

The BPE is a subword tokenization algorithm, it’s efficient for encoding iteral to tokens for LM processing. It breaks up the input text to bytes and assemble them pair by pair.

This gives two benefits:

1. No out-of-vocabulary problem cause every string can be reporesented as utf-8 bytes.
2. Shorter sequences than pure byte-level tokenization, because frequent byte sequences become single tokens.

Note: Merges are performed inside pre-token boundaries only. We never merge across two pre-tokens or across special tokens.

How to implement the BPE tokenizer

First, get the pre-token list.

"hello hello ab" -> [bytes["h","e","l","l","o"], bytes["h","e","l","l"]， bytes["a","b"]]

record the count table

[
    "h,e,l,l,o": 1,
    "h,e,l,l": 1,
    "a,b" :1,
]

Now let’s start the merge step.

1. traverse the count table and calculate pairs

[
    (h,e),
    (e,l),
    (l,l),
    (l,o),
],
[
    (h,e),
    (e,l),
    (l,l),
],
[
    (a,b),
]

2. record them to the pair_count table and pair_affected table: pair_count table:

[
    (h,e): 2,
    (e,l): 2,
    (l,l): 2,
    (l,o): 1,
    (a,b): 1,
]

pair_affected table:

[
    (h,e): {"h,e,l,l,o,","h,e,l,l"},
    (e,l): {"h,e,l,l,o,","h,e,l,l"},
    (l,l): {"h,e,l,l,o,","h,e,l,l"},
    (l,o): {"h,e,l,l,o,"},
    (a,b): {"a,b"},
]

3. (merge loop start here) pick the most prvious pair by its occurrences times(pair_count table’s value), if tied, take the lexicographically greater pair.

[
    (h,e): 2,
    (e,l): 2,
    (l,l): 2,
] # tied
->
(l,l) # lexicographically

4. allocate a vocab id for the new token “ll” and append it to the vocab.

vocab[new_token_id] = "ll"

then, let’s process the old tables: count, pair_count, pair_affected. first: find which tokens are affected by this pair by pair_affected table.

"ll" -> {"h,e,l,l,o","h,e,l,l"}

loop: first process “h,e,l,l,o”, then process “h,e,l,l”

calculate old pairs and remove old oairs in pair_affected:

{"h,e,l,l,o","h,e,l,l"} -> [(h,e),(e,l),(l,l),(l,o)]
[
    (h,e): {"h,e,l,l,o,","h,e,l,l"},
    (e,l): {"h,e,l,l,o,","h,e,l,l"},
    (l,l): {"h,e,l,l,o,","h,e,l,l"},
    (l,o): {"h,e,l,l,o,"},
    (a,b): {"a,b"},
] ->
[
    (a,b): {"a,b"},
]

Note: “h,e,l,l,o,” will be removed at first loop, “h,e,l,l” second.

update the old tokens:

{"h,e,l,l,o","h,e,l,l"} -> {"h,e,ll,o","h,e,ll"}

update pair_affected table using old pairs with new tokens

[
    (a,b): {"a,b"},
] ->
[
    (h,e): {"h,e,ll,o,","h,e,ll"},
    (e,ll): {"h,e,ll,o,","h,e,ll"},
    (ll,o): {"h,e,ll,o,"},
    (a,b): {"a,b"},
] ->

update pair_count table:

[
    (h,e): 2,
    (e,l): 2,
    (l,l): 2,
    (l,o): 1,
    (a,b): 1,
] ->
[
    (h,e): 2,
    (e,ll): 2,
    (ll,o): 1,
    (a,b): 1,
]

update count table

[
    "h,e,l,l,o": 1,
    "h,e,l,l": 1,
    "a,b" :1,
] ->
[
    "h,e,ll,o": 1,
    "h,e,ll": 1,
    "a,b" :1,
]

Note:

1. pair_affected is necessary for incremental udpate, it act as the index of looking up to what will be affected from current pair.
2. pair_count and count record pair count and token count, their prodect is the real number of a pair shows.
3. Incremental update:
   • counts[token_seq] is the number of times this current token sequence appears.
   • pair_count[pair] is the weighted total count of this pair across all token sequences.
   • pair_affected[pair] is the set of token sequences that currently contain this pair.

Tokenizer

The tokenizer has two main responsibilities.

1. it should split normal text into pre-tokens before applying BPE merges.
2. it should preserve user-provided special tokens as atomic tokens. Special tokens must not be split or merged with surrounding text.

During initialization, we store the vocabulary, merge ranks, and special-token IDs. If the special tokens are provided, they should already exist in the vocabulary, or we should assign them new IDs after the existing vocabulary IDs.

Encode

Before encoding normal text, we first split the input around special tokens while keeping the special tokens in the result.

"content-1 <special-token1> content-2"
->
["content-1",<special-token1>,"content-2"]

For each normal text segment, we apply regex-based pre-tokenization. Each pre-token is encoded as UTF-8 bytes, and each bytes starts as an individual token. Now lets’s encode the “content-1”

loop: content-1

[content-1]
->
["hello", content-1-remain]
->
"hello"
->
["h","e","l","l","o"]

Then we repeatedly apply the learned BPE merges. find the adjacent pair with the best merge rank and replace ecery occurrence of that pair with the merged token. in loop:

["h", "e", "l", "l", "o"]
->
["he", "ll", "o"]
->
["hello"]

we can find a unique token_id from the BPE vocabulary we have built.

"hello" -> 100
["hello"] -> [100]

keep the while until a content is exhausted. if the next segment is a special token, we append its special-token ID directly without applying pre-tokenization or BPE.

"special-token1" -> vocab_size + 1
[100, 827, ...] -> [100, 827, ..., vocab_size + 1]

Decode

Decoding reverses this process. We map each token ID bacj to its byte sequence, concatenate all byte sequences, and decode the result as UTF-8 if the byte sequence is not valid UTF-8, we can decode with “replace” and replace this invalid character.

Find the code at here

bpe.py

tokenizer.py