Tokenization Engineering & BPE Algorithm | AI & Machine Learning Engineering

Neural networks cannot process raw unicode text strings directly; they require discrete numerical integer IDs mapped to continuous dense embeddings.

The bridge between continuous language models and human text is Tokenization. Modern language models rely on Byte-Pair Encoding (BPE) to balance vocabulary size with sequence length, eliminating Out-Of-Vocabulary (OOV) failures.

Byte-Level BPENLP Engineering

Zero OOV

Initializing vocabulary with 256 raw bytes guarantees any valid UTF-8 unicode string can be tokenized.

1. Character vs Word vs Subword Tradeoffs#

Tokenization Scheme	Typical Vocabulary Size	Sequence Length	OOV Robustness	Expressive Semantics
Character-Level	Minimal ( $\approx 256$ )	Very Long ( $4\times$ )	Perfect ( $0$ OOV)	Poor (individual characters carry minimal semantic meaning)
Word-Level	Massive ( $500\text{k}+$ )	Minimal ( $1\times$ )	Catastrophic (any unknown word becomes `[UNK]`)	Excellent for known words; fails on typos and morphology
Subword (BPE)	Optimal ( $32\text{k} - 128\text{k}$ )	Balanced ( $1.3\times$ )	Perfect (decomposes unseen words into roots/suffixes)	Excellent (morphological compositionality)

Architecture Diagram

Rendering diagram...

2. The Byte-Pair Encoding (BPE) Algorithm#

Originally introduced by Philip Gage (1994) as a data compression heuristic, Sennrich et al. (2016) adapted Byte-Pair Encoding for neural language models.

Step 1: Base Vocabulary Initialization

Initialize vocabulary $V$ with all unique characters occurring in the training corpus, plus a dedicated end-of-word marker </w>:

V_0 = \{c \in \text{characters}\} \cup \{\text{</w>}\}

Every word in the corpus is represented as a sequence of space-separated characters:

"low" $\to$ l o w </w>
"lower" $\to$ l o w e r </w>
"newest" $\to$ n e w e s t </w>

Step 2: Compute Pair Frequencies

Count the occurrence frequency of all adjacent symbol pairs $(c_1, c_2)$ across the corpus, weighted by word frequencies:

\text{Freq}(u, v) = \sum_{w \in \text{Corpus}} \text{Count}(w) \cdot \text{Occurrences}( (u, v) \text{ in } w )

Step 3: Greedy Merge

Select the symbol pair $(u^*, v^*)$ that achieves the maximum frequency:

(u^*, v^*) = \arg\max_{(u, v)} \text{Freq}(u, v)

Create a new token by concatenating the pair: $t_{\text{new}} = u^* v^*$ .

Step 4: Vocabulary Expansion & Replacement

Add $t_{\text{new}}$ to vocabulary: $V_{k+1} = V_k \cup \{t_{\text{new}}\}$ . Replace all consecutive occurrences of u* v* across the corpus with atomic token u*v*.

Repeat Steps 2 through 4 until exactly $K$ merge operations have completed, reaching desired vocabulary size $|V| = |V_0| + K$ .

3. Byte-Level BPE (BBPE)#

Standard character BPE fails on non-Latin scripts, mathematical symbols, or emojis if those characters were missing from the training corpus.

Radford et al. (2019) introduced Byte-level BPE (BBPE) in GPT-2:

The base vocabulary is initialized strictly with the 256 possible bytes ( $0x00$ through $0xFF$ ).
Because any unicode character (including rare alphabets, specialized domain formulas, and emojis) is encoded as a sequence of 1 to 4 UTF-8 bytes, BBPE guarantees zero Out-of-Vocabulary (OOV) tokens.
Frequent words (e.g. " the") merge into single token IDs, while rare characters decompose into constituent byte sequences.

4. From-Scratch Implementation: Zero Dependencies#

The following implementations build a complete BPE Tokenizer (Training and Tokenization) from scratch in pure Python and pure Rust.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
from typing import List, Dict, Tuple
from collections import defaultdict

class BPETokenizerFromScratch:
    def __init__(self, target_vocab_size: int = 15):
        self.target_vocab_size = target_vocab_size
        self.merges: List[Tuple[str, str]] = []
        self.vocab: List[str] = []

    @staticmethod
    def _get_pair_counts(corpus: Dict[Tuple[str, ...], int]) -> Dict[Tuple[str, str], int]:
        counts: Dict[Tuple[str, str], int] = defaultdict(int)
        for word_tuple, freq in corpus.items():
            for i in range(len(word_tuple) - 1):
                pair = (word_tuple[i], word_tuple[i + 1])
                counts[pair] += freq
        return counts

    @staticmethod
    def _merge_pair(
        pair: Tuple[str, str],
        corpus: Dict[Tuple[str, ...], int]
    ) -> Dict[Tuple[str, ...], int]:
        first, second = pair
        new_corpus: Dict[Tuple[str, ...], int] = {}

        for word_tuple, freq in corpus.items():
            new_word = []
            i = 0
            while i < len(word_tuple):
                if i < len(word_tuple) - 1 and word_tuple[i] == first and word_tuple[i + 1] == second:
                    new_word.append(first + second)
                    i += 2
                else:
                    new_word.append(word_tuple[i])
                    i += 1
            new_corpus[tuple(new_word)] = freq

        return new_corpus

    def fit(self, texts: List[str]):
        # 1. Initialize corpus with word frequency counts
        raw_words = [w for text in texts for w in text.strip().split()]
        word_counts = defaultdict(int)
        for w in raw_words:
            # Append end-of-word indicator '</w>'
            word_tuple = tuple(list(w) + ["</w>"])
            word_counts[word_tuple] += 1

        # 2. Base character vocabulary
        vocab_set = set()
        for word_tuple in word_counts:
            vocab_set.update(word_tuple)
        self.vocab = sorted(list(vocab_set))

        # 3. Iterative merge until target size reached
        corpus = dict(word_counts)
        num_merges = self.target_vocab_size - len(self.vocab)

        for _ in range(max(0, num_merges)):
            pair_counts = self._get_pair_counts(corpus)
            if not pair_counts:
                break

            # Find most frequent pair
            best_pair = max(pair_counts, key=pair_counts.get)
            self.merges.append(best_pair)
            self.vocab.append(best_pair[0] + best_pair[1])
            corpus = self._merge_pair(best_pair, corpus)

    def tokenize(self, word: str) -> List[str]:
        # Start with individual characters + end marker
        tokens = list(word) + ["</w>"]

        # Apply learned merges in rank order
        for p1, p2 in self.merges:
            merged_token = p1 + p2
            i = 0
            new_tokens = []
            while i < len(tokens):
                if i < len(tokens) - 1 and tokens[i] == p1 and tokens[i + 1] == p2:
                    new_tokens.append(merged_token)
                    i += 2
                else:
                    new_tokens.append(tokens[i])
                    i += 1
            tokens = new_tokens

        return tokens

if __name__ == "__main__":
    training_data = [
        "low low low low low",
        "lower lower",
        "newest newest newest newest newest newest",
        "wider wider"
    ]

    tokenizer = BPETokenizerFromScratch(target_vocab_size=18)
    tokenizer.fit(training_data)

    print("Learned BPE Merges in Order:")
    for rank, pair in enumerate(tokenizer.merges):
        print(f"  Rank {rank+1}: {pair[0]} + {pair[1]} -> {pair[0]+pair[1]}")

    print("\nTokenizing novel word 'lowest':")
    tokenized = tokenizer.tokenize("lowest")
    print("  Tokens:", tokenized)

5. Active Knowledge Checks#

Concept check

What fatal failure of word-level tokenization is completely resolved by Byte-Pair Encoding (BPE) subword segmentation?

Concept check

Why does Byte-level BPE (BBPE) use the 256 byte values (0x00 to 0xFF) as its base vocabulary instead of unicode characters?