Building GPT from Scratch — Part 2: Tokenization

The Problem

Neural networks operate on numbers. They can't process the string "Hello, world!" directly. We need a way to convert arbitrary text into a sequence of integers from a fixed vocabulary — and convert back.

This is tokenization, and it's the first decision that shapes everything downstream:

• Too few tokens (word-level): the vocabulary explodes. Millions of unique words, most appearing rarely. The embedding table becomes enormous and most entries barely get trained.

• Too many tokens (character-level): sequences become very long. Attention is O(n²) — doubling sequence length quadruples compute cost.

• The sweet spot (subword-level): common words are single tokens, rare words split into recognizable pieces. This is what all modern LLMs use.

Byte Pair Encoding (BPE)

BPE is the algorithm behind GPT's tokenizer. It was originally a compression algorithm (1994), repurposed for NLP. The idea is beautifully simple:

Training the tokenizer:

1. Start with 256 base tokens (one per byte value — covers all UTF-8 text)

2. Scan the corpus. Count every adjacent pair of tokens.

3. Find the most frequent pair. Merge it into one new token.

4. Repeat until you reach your desired vocabulary size.

Using the tokenizer (encoding):

1. Convert text to bytes

2. Apply the learned merges in order (lowest merge first)

3. Output: a sequence of token IDs

Let's trace through a concrete example:

Corpus: "low lower lowest"

Step 1: Start as bytes
  ['l','o','w',' ','l','o','w','e','r',' ','l','o','w','e','s','t']

Step 2: Most frequent pair? ('l','o') appears 3 times
  → Merge into token 256: "lo"
  ['lo','w',' ','lo','w','e','r',' ','lo','w','e','s','t']

Step 3: Most frequent pair? ('lo','w') appears 3 times
  → Merge into token 257: "low"
  ['low',' ','low','e','r',' ','low','e','s','t']

Step 4: Most frequent pair? ('low','e') appears 2 times
  → Merge into token 258: "lowe"
  ['lowe','r',' ','lowe','s','t',' ','low']

...and so on until we hit vocab_size.

The result: common words compress into single tokens. Rare words gracefully decompose into subword pieces. The system never hits an "unknown token" — it can always fall back to raw bytes.

Why BPE and Not Something Else?

GPT-2/3/4 all use BPE. It's simple, effective, and fast enough.

The Implementation

Here's the full BPE tokenizer. Let's walk through each part.

Training: Learning the Merges

def train(self, text, vocab_size=512):
    # Split text into words using a regex pattern
    # This prevents merges across word boundaries
    words = self.pattern.findall(text)

    # Convert each word to a list of byte values
    # "Hello" → [72, 101, 108, 108, 111]
    token_sequences = [list(word.encode("utf-8")) for word in words]

    # Start with 256 byte-level tokens
    self.vocab = {i: bytes([i]) for i in range(256)}
    next_token = 256

    # Iteratively merge the most common pair
    while next_token < vocab_size:
        # Count every adjacent pair across all sequences
        pair_counts = self._get_pair_counts(token_sequences)
        if not pair_counts:
            break

        # The most frequent pair becomes our next token
        best_pair = max(pair_counts, key=pair_counts.get)

        # Replace every occurrence of this pair with the new token
        token_sequences = self._merge_pair(
            token_sequences, best_pair, next_token
        )

        # Record the merge rule and the new token's bytes
        self.merges[best_pair] = next_token
        self.vocab[next_token] = self.vocab[best_pair[0]] + self.vocab[best_pair[1]]
        next_token += 1

Why the regex pattern? We split on word boundaries before counting pairs. Without this, BPE would merge across words — "the end" might produce a "e e" token that spans two words, which is linguistically nonsensical and hurts downstream performance. GPT-2's original regex:

pattern = r"""'s|'t|'re|'ve|'m|'ll|'d| ?\w+| ?\d+| ?[^\s\w]+|\s+"""

This handles contractions, words, numbers, punctuation, and whitespace as separate units.

Encoding: Applying Merges

def encode(self, text):
    words = self.pattern.findall(text)
    token_ids = []

    for word in words:
        # Start with raw bytes
        tokens = list(word.encode("utf-8"))

        # Apply merges in priority order (lowest merge ID first)
        while len(tokens) >= 2:
            # Find which mergeable pairs exist in this sequence
            pair_counts = {}
            for i in range(len(tokens) - 1):
                pair = (tokens[i], tokens[i + 1])
                if pair in self.merges:
                    pair_counts[pair] = self.merges[pair]

            if not pair_counts:
                break

            # Apply the EARLIEST merge (lowest ID = most frequent in training)
            best_pair = min(pair_counts, key=pair_counts.get)
            new_token = self.merges[best_pair]

            # Merge all occurrences of this pair
            new_tokens = []
            i = 0
            while i < len(tokens):
                if i < len(tokens) - 1 and (tokens[i], tokens[i + 1]) == best_pair:
                    new_tokens.append(new_token)
                    i += 2
                else:
                    new_tokens.append(tokens[i])
                    i += 1
            tokens = new_tokens

        token_ids.extend(tokens)

    return token_ids

Why apply merges in priority order? The merge with the lowest ID was learned first — meaning it was the most frequent pair in training. Applying merges in this order ensures consistent tokenization: the same text always produces the same tokens, regardless of input.

Decoding: Tokens Back to Text

def decode(self, token_ids):
    byte_seq = b"".join(self.vocab[t] for t in token_ids)
    return byte_seq.decode("utf-8", errors="replace")

Decoding is trivial: each token ID maps to a byte sequence. Concatenate them all and decode as UTF-8.

Running It

python download_data.py    # Get training corpus
python tokenizer.py        # Train BPE tokenizer

Output:

Trained tokenizer: 512 tokens
Original:  Hello, world! This is a test.
Encoded:   [72, 455, 111, 44, 464, 316, 33, 508, 104, 271, 360, 258, 256, 412, 46]
Decoded:   Hello, world! This is a test.

13 characters → 15 tokens with vocab_size=512. With a larger vocabulary (GPT-2 uses 50,257), "Hello, world!" would be 4 tokens. The tradeoff: larger vocab = shorter sequences = faster attention, but larger embedding table.

The Data

For training data, we use public domain books from Project Gutenberg plus Shakespeare — about 5.7MB total, roughly 2.7 million tokens after BPE encoding. This is tiny by modern standards (GPT-3 was trained on 300 billion tokens), but sufficient to learn basic English structure.

The choice of training data matters more than you'd think:

• Train on code → the tokenizer creates tokens like def, return, self.

• Train on English prose → tokens like the, tion, ing

• Train on mixed data → balanced subwords that handle both

Our tokenizer is trained on the same corpus we'll pretrain on. In production, you'd train the tokenizer on a much larger, more diverse dataset.

Key Takeaways

1. Tokenization is compression. BPE finds the most efficient encoding of your corpus given a fixed vocabulary size.

2. The vocab_size is a fundamental tradeoff. Larger = shorter sequences (cheaper attention) but larger embedding table. GPT-2 uses 50K. Our toy model uses 512.

3. BPE guarantees no unknown tokens. It can always fall back to individual bytes — unlike word-level tokenizers that need an <UNK> token.

4. Tokenization is separate from the model. The tokenizer is trained once and frozen. The model never modifies it.

Full code: github.com/the-last-programmers/gpt-from-scratch

Next: building the transformer architecture.