Part 2:Tokenization - Byte Pair Encoding Training | Gopikrishna Pavuluri

Part 2:Tokenization - Byte Pair Encoding Training

• • 28 min read

In the previous post we talked about subword tokenization and using Byte Pair Encoding (BPE) to train on a large corpus of data. Don’t get confused by the word “training” here — it’s not training a neural network. You’re running an algorithm that produces a vocabulary and a set of merge rules, which a BPE tokenizer then uses to encode and decode text before it ever reaches the transformer.

Contents

Before jumping into the algorithm, let’s clarify BPE’s inputs and outputs.

Input

Imagine the vast range of languages and vocabulary GPT has to handle. BPE training takes a large corpus of raw text as input. For this walkthrough I’ll be using OpenWebText and TinyStories combined — about 15 GB of raw text.

Output

BPE produces two things: a fixed vocabulary (a dictionary of tokens the model knows) and an ordered list of merge rules. GPT-2 has ~50k tokens; GPT-4 uses ~100k. I’ll explain what merge rules mean as we get into the algorithm. Later, when we build and train the transformer, every sentence in the corpus will be broken down using this vocabulary.

Question: What is the scale of the data GPT/Claude models actually train on?

Petabytes. Here we’re working with a few GB — enough to understand and implement the same algorithm that powers tiktoken (the tokenizer behind GPT-2/4), just at a smaller scale.

Starting the implementation

My machine is a Mac M3 with 8 GB of RAM. The training data is 15 GB, so reading the entire corpus into memory at once isn’t an option. The solution is pre-tokenization.

Here’s the full pipeline at a glance — each section below walks through one of these boxes:

BPE training pipeline — from raw text corpus to vocabulary and merge rules

Pre-tokenization

Read the data in parallel chunks (a few MB at a time) using multiprocessing, apply the GPT-2 regex to split each chunk into pieces, and count the frequency of each resulting word piece across the full corpus.

GPT-2 Regex

The GPT-2 regex is a pre-tokenization pattern. Before BPE sees any text, this regex splits it into chunks so that BPE merges never cross certain boundaries — like between a word and its punctuation, or between two different words.

Here’s the pattern:

import regex as re

GPT2_SPLIT_PATTERN = r"""'(?:[sdmt]|ll|ve|re)| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+"""

It’s an alternation — Python’s re.findall returns the first branch that matches at each position. Breaking it apart:

Branch Matches Example
'(?:[sdmt]\|ll\|ve\|re) English contractions after the apostrophe 's, 't, 're, 've, 'm, 'll, 'd
' ?\p{L}+' An optional leading space followed by one or more letters ' Hello', 'world'
' ?\p{N}+' An optional leading space followed by one or more digits ' 42', '2024'
' ?[^\s\p{L}\p{N}]+' An optional leading space followed by punctuation/symbols '.', ', ', '!!'
'\s+(?!\S)' Whitespace that is not immediately followed by a non-whitespace character (trailing whitespace) spaces at end of line
'\s+' Any remaining whitespace newlines, tabs

Why does this matter?

Without pre-tokenization, BPE is free to merge across any character boundary. That leads to unwanted tokens like " dog." (space + word + punctuation as a single unit), or merges that bleed across word boundaries. The regex enforces three key constraints:

  1. Contractions stay intact. "don't" splits into ["don", "'t"], not ["do", "n't"] or something worse.
  2. Punctuation is always separate from words. "hello," → ["hello", ","]. BPE will never create a token that fuses letters and punctuation.
  3. Numbers are isolated. Digits form their own chunks and won’t merge with letters.

The leading-space design ( ?\p{L}+) is deliberate: in most text, words appear with a preceding space ( Hello), and by including that space inside the token, the tokenizer can distinguish "Hello" at the start of a sentence from " Hello" in the middle — without a special whitespace token.

A concrete example:

Input: "don't run 3 times."

After GPT-2 regex split:
["don", "'t", " run", " 3", " times", "."]

BPE then trains on these pieces, never merging across them.

This is why the pre-tokenization step happens before counting frequencies: you count the frequency of each regex-produced chunk, and BPE operates within those chunks only.

Setup: Imports and Constants

import os
import time
from typing import BinaryIO
from concurrent.futures import ProcessPoolExecutor, as_completed
from collections import Counter
import regex as re
from tqdm import tqdm
import pickle

PAT = r"""'(?:[sdmt]|ll|ve|re)| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+"""
COMPILED_PAT = re.compile(PAT)

Step 1: Finding Chunk Boundaries

I cannot read 15 GB into 8 GB of RAM, so the file has to be processed in pieces — and those pieces have to be handed to separate processes. The naive approach is to divide the file size by the number of chunks and cut at those byte offsets, but a blind cut lands in the middle of a document, and often in the middle of a UTF-8 character.

So the boundaries are only a starting guess. From each guessed offset the function reads forward 4 KB at a time until it finds the next <|endoftext|> marker, and cuts there instead. Two things fall out of this: every chunk contains whole documents, and duplicate boundaries (which happen when two guesses land inside the same document) collapse away because the result is passed through sorted(set(...)).

Equal byte offsets pushed forward to the next end-of-text marker so no chunk splits a document

def find_chunk_boundaries(
    file: BinaryIO, desired_num_chunks: int, split_special_token: bytes
) -> list[int]:
    assert isinstance(split_special_token, bytes)
    file.seek(0, os.SEEK_END)
    file_size = file.tell()
    file.seek(0)

    chunk_size = file_size // desired_num_chunks
    chunk_boundaries = [i * chunk_size for i in range(desired_num_chunks + 1)]
    chunk_boundaries[-1] = file_size
    mini_chunk_size = 4096

    for bi in range(1, len(chunk_boundaries) - 1):
        initial_position = chunk_boundaries[bi]
        file.seek(initial_position)
        while True:
            mini_chunk = file.read(mini_chunk_size)
            if mini_chunk == b"":
                chunk_boundaries[bi] = file_size
                break
            found_at = mini_chunk.find(split_special_token)
            if found_at != -1:
                chunk_boundaries[bi] = initial_position + found_at
                break
            initial_position += mini_chunk_size

    return sorted(set(chunk_boundaries))

Note that this returns offsets, not data. Nothing large is in memory yet — each worker seeks to its own (start, end) and reads only its slice.

Step 2: Pre-tokenizing a Single Chunk

This is the function each worker runs, and it does four things in order: read the byte range and decode it, remove the special tokens, apply the GPT-2 regex to what’s left, and count the pieces.

Removing special tokens first is not cosmetic. <|endoftext|> is a control token — it must exist in the vocabulary as one indivisible unit, and BPE must never learn merges that reach across it or chew it into fragments. Splitting the text on those markers guarantees BPE never sees them. The split pattern is built longest-first and each token is passed through re.escape, so that a token like <|endoftext|> is matched before any shorter token that happens to be a prefix of it, and regex metacharacters like | are treated as literal text.

What comes back is a Counter of word pieces for this chunk only — a few thousand distinct keys instead of megabytes of text.

One chunk decoded, split on special tokens, run through the GPT-2 regex and counted

def pre_tokenize_text(file_path, start, end, special_tokens):
    with open(file_path, "rb") as f:
        f.seek(start)
        chunk = f.read(end - start).decode("utf-8", errors="ignore")

    # split out special tokens so they never reach BPE; longest-first + escaped
    if special_tokens:
        split_pat = "|".join(
            re.escape(s) for s in sorted(special_tokens, key=len, reverse=True)
        )
        segments = re.split(split_pat, chunk)
    else:
        segments = [chunk]

    counts = Counter()
    for seg in segments:
        counts.update(COMPILED_PAT.findall(seg))
    return counts

Step 3: Parallel Pre-tokenization

Now the two previous steps get wired together. find_chunk_boundaries produces 64 ranges, each range is submitted to a ProcessPoolExecutor, and every completed future returns a small Counter that the parent process folds into one table with counts_dict.update(...).

Three details are worth calling out:

  • max_workers=3 is a memory decision, not a CPU one. Each worker holds its own chunk plus its own counter; on an 8 GB machine three concurrent slices is the comfortable ceiling.
  • as_completed means results are merged the moment any worker finishes, so no chunk’s counter sits around waiting for a slower neighbour.
  • The counters shrink the data enormously. 15 GB of text collapses into roughly a million unique word pieces with counts, which fits in memory easily — and that table, not the corpus, is what BPE actually trains on.

Sixty-four chunk ranges submitted to three worker processes and merged into one word-frequency table

def _get_pretokenized_word_count(input_path, special_tokens) -> dict[str, int]:
    start_time = time.time()
    with open(input_path, "rb") as f:
        boundaries = find_chunk_boundaries(f, 64, b"<|endoftext|>")

    num_chunks = len(boundaries) - 1
    print(f"Processing {num_chunks} chunks...")
    counts_dict = Counter()

    with ProcessPoolExecutor(max_workers=3) as pe:
        futures = {
            pe.submit(pre_tokenize_text, input_path, start, end, special_tokens): i
            for i, (start, end) in enumerate(zip(boundaries[:-1], boundaries[1:]))
        }

        with tqdm(total=num_chunks, desc="Tokenizing", unit="chunk") as pbar:
            for future in as_completed(futures):
                chunk_idx = futures[future]
                counts_dict.update(future.result())
                pbar.set_postfix(
                    {
                        "chunk": chunk_idx,
                        "unique_tokens": len(counts_dict),
                        "elapsed": f"{time.time() - start_time:.1f}s",
                    }
                )
                pbar.update(1)

    return counts_dict

Pre-tokenization ends here. Everything from this point on is the BPE algorithm itself.

Step 4: Counting Pair Frequencies

Each word piece is encoded to UTF-8 and treated as a list of single-byte tokens — this is why the base vocabulary is 256 entries: any text in any language is representable, so there is no such thing as an unknown character.

For every word, every adjacent pair of tokens is counted weighted by the word’s frequency. If ' low' appears 5 times, the pair (b'l', b'o') gets +5, not +1. The corpus is never scanned again after this; from here on BPE only ever reads and updates this table.

The second return value is the part that makes the whole thing tractable: pair_words is a reverse index from a pair to the set of words containing it. When a pair wins and gets merged, only those words need rewriting — a few thousand instead of a million.

Bytes of a word split into pairs, counted by word frequency, with a reverse index from pair to words

def _pair_frequency(
    pretokenized_word_count: dict[str, int],
) -> tuple[dict[tuple[bytes, bytes], int], dict[tuple[bytes, bytes], set[str]]]:
    byte_pair_count: dict[tuple[bytes, bytes], int] = {}
    pair_words: dict[tuple[bytes, bytes], set[str]] = {}

    for word, count in pretokenized_word_count.items():
        word_bytes: bytes = word.encode("utf-8")
        for i in range(len(word_bytes) - 1):
            pair = (word_bytes[i : i + 1], word_bytes[i + 1 : i + 2])
            byte_pair_count[pair] = byte_pair_count.get(pair, 0) + count
            pair_words.setdefault(pair, set()).add(word)

    return byte_pair_count, pair_words

Step 5: Merging the Top Pair

This is the heart of the algorithm, and the only function where a subtle bug can quietly corrupt the vocabulary.

Given the winning pair, it looks up the affected words in pair_words and, for each one, rewrites the token list greedily, left to right, without overlaps — so b'aaa' with the pair (a, a) becomes [aa, a], exactly as tiktoken behaves.

Then the pair counts have to be repaired, and the order of operations matters:

  • Pass 1 is arithmetic only. Subtract the word’s frequency from every pair in the old token list, add it to every pair in the new list. No key is deleted here, even if it momentarily reaches zero — the same pair may be added back a line later by a different position in the same word.
  • Pass 2 runs once the counts are final. The reverse index is updated (discard the word from pairs it no longer has, add it to the new ones), and only then are pairs whose count fell to zero or below popped from both dictionaries.

If you evict during pass 1, you delete pairs that were about to come back, and later merges silently pick the wrong winner.

Merging the winning pair inside one word, then the two-pass count update and eviction

def _merge_top_pair(
    best_pair: tuple[bytes, bytes],
    byte_pair_frequency: dict[tuple[bytes, bytes], int],
    word_frequency: dict[str, int],
    word_token: dict[str, list[bytes]],
    pair_words: dict[tuple[bytes, bytes], set[str]],
) -> dict[tuple[bytes, bytes], int]:
    new_token = best_pair[0] + best_pair[1]
    affected_words = list(pair_words.get(best_pair, set()))

    for word in affected_words:
        old_tokens = word_token[word]
        freq = word_frequency[word]

        # rewrite this word's token list (greedy, left-to-right, non-overlapping)
        new_tokens: list[bytes] = []
        i = 0
        while i < len(old_tokens):
            if (
                i + 1 < len(old_tokens)
                and old_tokens[i] == best_pair[0]
                and old_tokens[i + 1] == best_pair[1]
            ):
                new_tokens.append(new_token)
                i += 2
            else:
                new_tokens.append(old_tokens[i])
                i += 1

        # PASS 1: arithmetic only -- subtract old pairs, add new pairs. No eviction yet.
        touched = set()
        for j in range(len(old_tokens) - 1):
            p = (old_tokens[j], old_tokens[j + 1])
            byte_pair_frequency[p] = byte_pair_frequency.get(p, 0) - freq
            touched.add(p)
        for j in range(len(new_tokens) - 1):
            p = (new_tokens[j], new_tokens[j + 1])
            byte_pair_frequency[p] = byte_pair_frequency.get(p, 0) + freq
            touched.add(p)

        # PASS 2: counts are final now -- fix reverse index, then evict zeroed pairs.
        old_pairs = {(old_tokens[j], old_tokens[j + 1]) for j in range(len(old_tokens) - 1)}
        new_pairs = {(new_tokens[j], new_tokens[j + 1]) for j in range(len(new_tokens) - 1)}
        for p in old_pairs - new_pairs:
            s = pair_words.get(p)
            if s is not None:
                s.discard(word)
                if not s:
                    pair_words.pop(p, None)
        for p in new_pairs - old_pairs:
            pair_words.setdefault(p, set()).add(word)
        for p in touched:
            if byte_pair_frequency.get(p, 0) <= 0:
                byte_pair_frequency.pop(p, None)
                pair_words.pop(p, None)

        word_token[word] = new_tokens

    byte_pair_frequency.pop(best_pair, None)
    pair_words.pop(best_pair, None)
    return byte_pair_frequency

Putting It All Together: train_bpe

The driver is short because the work is in the pieces above. It seeds the vocabulary with the 256 byte values, appends the special tokens, builds the word counts and the pair table, and then loops.

Each iteration does four things: pick the highest-count pair, add the merged token to the vocabulary, append the pair to merge_list, and call _merge_top_pair to update the counts. The loop ends when the vocabulary reaches vocab_size (or when there are no pairs left, which happens on tiny corpora).

Two details:

  • max(byte_pair_frequency, key=lambda k: (byte_pair_frequency[k], k)) breaks count ties by the pair itself. Ties are common, and without a deterministic rule two runs on the same data would produce different vocabularies.
  • merge_list is ordered, and the order is the rule. Merge 4 may depend on the token merge 1 created, so at encode time the merges must be replayed in exactly this sequence.

The vocabulary grows from 256 byte values to the target size, one token per merge

def train_bpe(
    input_path: str, vocab_size: int, special_tokens: list[str]
) -> tuple[dict[int, bytes], list[tuple[bytes, bytes]]]:

    vocabulary = {}
    for i in range(256):
        vocabulary[i] = bytes([i])

    for token in special_tokens:
        vocabulary[len(vocabulary)] = token.encode("UTF-8")

    word_frequency = _get_pretokenized_word_count(
        input_path=input_path, special_tokens=special_tokens
    )
    word_token = {}
    for key, value in word_frequency.items():
        word_token[key] = [bytes([b]) for b in key.encode("utf-8")]

    byte_pair_frequency, byte_pair_words = _pair_frequency(word_frequency)

    merge_list = []
    while len(vocabulary) < vocab_size:
        if not byte_pair_frequency:
            break
        highest_frequency = max(
            byte_pair_frequency, key=lambda k: (byte_pair_frequency[k], k)
        )
        new_token = highest_frequency[0] + highest_frequency[1]
        vocabulary[len(vocabulary)] = new_token
        merge_list.append(highest_frequency)
        byte_pair_frequency = _merge_top_pair(
            highest_frequency, byte_pair_frequency, word_frequency, word_token, byte_pair_words
        )

    return vocabulary, merge_list

Running the Training

if __name__ == "__main__":
    input_path = "data/owt_train.txt"
    vocab_size = 32000                       # CS336's OWT target
    special_tokens = ["<|endoftext|>"]
    out_dir = "artifacts"
    os.makedirs(out_dir, exist_ok=True)

    start_time = time.time()
    vocab, merges = train_bpe(
        input_path=input_path,
        vocab_size=vocab_size,
        special_tokens=special_tokens,
    )
    elapsed = time.time() - start_time
    print(f"Done: {len(vocab)} tokens, {len(merges)} merges in {elapsed / 60:.1f} min")

    vocab_path = os.path.join(out_dir, "owt_vocab.pkl")
    merges_path = os.path.join(out_dir, "owt_merges.pkl")
    with open(vocab_path, "wb") as f:
        pickle.dump(vocab, f)
    with open(merges_path, "wb") as f:
        pickle.dump(merges, f)

    print(f"Saved vocab  -> {vocab_path}")
    print(f"Saved merges -> {merges_path}")

The Output: Vocabulary and Merge Rules

Two pickled files, and that’s the entire tokenizer. owt_vocab.pkl is a dict[int, bytes] — ids 0–255 are the raw byte values, then the special tokens, then one entry per merge in the order they were learned. owt_merges.pkl is the ordered list[(bytes, bytes)].

The vocabulary maps ids to byte strings; the ordered merge list is replayed when encoding text

import pickle

with open("artifacts/owt_vocab.pkl", "rb") as f:
    vocab = pickle.load(f)
with open("artifacts/owt_merges.pkl", "rb") as f:
    merges = pickle.load(f)

print(len(vocab), len(merges))
# 32000 31743

# the base bytes
print({i: vocab[i] for i in (0, 65, 97, 255)})
# {0: b'\x00', 65: b'A', 97: b'a', 255: b'\xff'}

# the special token, right after the bytes
print(vocab[256])
# b'<|endoftext|>'

# the first merges BPE learned, and what they became
for i, pair in enumerate(merges[:8]):
    print(i + 1, pair, "->", pair[0] + pair[1])
# 1 (b'e', b' ') -> b'e '
# 2 (b' ', b't') -> b' t'
# 3 (b'h', b'e') -> b'he'
# 4 (b' t', b'he') -> b' the'
# 5 (b'i', b'n') -> b'in'
# 6 (b'e', b'r') -> b'er'
# 7 (b'a', b'n') -> b'an'
# 8 (b' ', b'a') -> b' a'

# the longest tokens are whole common words, with their leading space
longest = sorted(vocab.values(), key=len, reverse=True)[:5]
print(longest)
# [b' unfortunately', b' international', b' administration', b' organization', b' Nevertheless']

Notice merge 4: (b' t', b'he') only exists because merges 2 and 3 already created b' t' and b'he'. That dependency is why the list is ordered and why encoding replays it from the top.

Also notice what BPE spent its first merges on — spaces, the, in, er. Nothing here was designed; the ranking came entirely out of the corpus counts.

Sanity checks worth running

Before trusting a tokenizer, three checks catch almost every implementation bug:

  1. Round-trip. decode(encode(text)) == text for a few thousand random documents, including emoji and non-Latin scripts. Because the base vocabulary is all 256 bytes, this must hold exactly.
  2. Determinism. Train twice on the same file and diff the merge lists. Any difference means a tie is being broken non-deterministically.
  3. Compression ratio. Bytes divided by tokens on held-out text. For a 32k vocabulary on English, roughly 4 bytes per token is the expected neighbourhood — much lower and the merges aren’t being applied; much higher and the vocabulary is overfitting to the corpus.

What’s next

We now have a vocabulary and an ordered list of merges — everything needed to turn text into token IDs. In Part 3 I’ll implement the encoder and decoder on top of these two files, run the full corpus through them, and store the result as a flat array of IDs ready for the transformer.

Acknowledgments: Grammar and prose lightly edited with Claude (Anthropic) assistance.

References

  1. Hashimoto, T. & Liang, P. (2026). CS336 LLM from Scratch. Stanford University, Spring 2026.
  2. Karpathy, A. (2023). Let’s build the GPT Tokenizer. YouTube. — Hands-on walkthrough of BPE from scratch.
  3. Sennrich, R., Haddow, B., & Birch, A. (2016). Neural Machine Translation of Rare Words with Subword Units. ACL 2016. — The original BPE paper applied to NLP.
  4. Radford, A. et al. (2019). Language Models are Unsupervised Multitask Learners. OpenAI. — GPT-2 paper, source of the pre-tokenization regex.