Understanding Byte-Pair Encoding

Byte-pair encoding is the least glamorous component of a language model and the one most likely to silently ruin your results. Both Polaris and Zenith ship from-scratch BPE implementations; this note covers what building them taught me.

The core algorithm

BPE starts from a base vocabulary (characters or bytes) and repeatedly merges the most frequent adjacent pair into a new token:

def train_bpe(corpus: list[str], num_merges: int) -> list[tuple[str, str]]:
    words = [tuple(w) + ("</w>",) for w in corpus]
    merges = []
    for _ in range(num_merges):
        pairs = count_adjacent_pairs(words)
        if not pairs:
            break
        best = max(pairs, key=pairs.get)
        words = apply_merge(words, best)
        merges.append(best)
    return merges

Training produces an ordered merge table. Tokenization replays those merges, in order, on new text. That ordering is the whole tokenizer: two implementations with the same vocab but different merge order produce different token sequences.

Why bytes, not characters

Character-level BPE needs an unknown-token escape hatch for anything outside the training alphabet. Byte-level BPE (GPT-2 style) starts from all 256 bytes, so every string is representable — emoji, typos, other scripts — with zero out-of-vocabulary tokens. The cost is that rare scripts fragment into many byte tokens, which is a real fairness and cost issue for non-English text.

What implementation taught me

• Naive BPE training is slow. The straightforward implementation is O(merges × corpus) — painful even on a 1 MB corpus. Zenith's byte-level BPE is vectorized specifically because the naive version was the bottleneck.
• Pre-tokenization is policy. What you split on before BPE determines what merges are even possible. GPT-2's regex is a design decision, not a detail.
• Subwords are not free wins. In Polaris's IMDB benchmarks, switching from a whitespace tokenizer to BPE lowered sentiment accuracy (≈0.856 → 0.839): the signal lives in common whole words like "great" and "terrible", and BPE splits them into subwords while lengthening sequences so more of each review is lost to truncation. BPE pays off for out-of-vocabulary and morphology problems — not every problem.

The takeaway

A tokenizer is a compression codec that the model is forced to think in. If you can't explain your tokenizer's failure modes, you can't fully explain your model's — and sometimes the honest benchmark says the fancier tokenizer is the wrong choice.