Subword Tokenization Algorithms

I merged byte pairs until "un" and "believable" became one token. Then I tried "un" and "fortunate." We don't talk about that.

Token, Compulsively Merging AI Agent

Overview of Subword Methods

You are about to learn the three algorithms that decide how every modern LLM reads text. If you have ever wondered why GPT tokenizes "ChatGPT" differently from "chatgpt," or why a simple Korean sentence consumes three times more tokens than its English translation, the answers lie in these algorithms. All subword tokenization algorithms solve the same problem: given a training corpus, learn a vocabulary of subword units that can represent any text efficiently. They differ in how they build the vocabulary and how they segment new text at inference time. The three dominant families are:

1. Byte Pair Encoding (BPE): a bottom-up, merge-based approach used by GPT-2, GPT-3, GPT-4, Llama, and most modern LLMs (Chapter 7).
2. WordPiece: a variant of BPE that uses a likelihood-based merge criterion, used by pretraining data and its derivatives.
3. Unigram Language Model: a top-down, pruning-based approach that assigns probabilities to all subword candidates and uses the Viterbi algorithm for segmentation, used by T5, ALBERT, and XLNet.

In addition, we will cover byte-level BPE (deep treatment in the Byte-level BPE section below: it eliminates the need for character-level preprocessing) and tokenizer-free models (which bypass discrete tokenization entirely).

Before the algorithms diverge, it helps to see the move they all start from. Figure 1.6.1 animates the bottom-up engine that drives BPE: split words into characters, count every adjacent pair across the corpus, merge the single most frequent pair into a new token, and repeat. Each pass adds exactly one entry to the merge table, and after a few hundred passes the common suffixes and whole words emerge on their own.

Byte Pair Encoding (BPE)

Both BPE and WordPiece build their vocabularies from the bottom up, starting with individual characters and merging upward. The Unigram model takes the opposite direction entirely. Proposed by Kudo (2018) and implemented in the SentencePiece (a Google-developed tokenization library), it starts from the top down. Instead of starting small and merging upward, it starts with a large initial vocabulary of candidate subwords and iteratively prunes the least useful ones.

Training Procedure

The Unigram model assigns a probability to each possible segmentation of a word. Given a word $x$, the probability of a particular segmentation $S = (t_{1}, t_{2}, ..., t_{m})$ is:

The overall corpus loss is the negative log-likelihood over all words:

The training procedure alternates between finding the best segmentation of the corpus and removing the least useful tokens from the vocabulary:

1. Begin with a large candidate vocabulary (for example, all substrings up to a certain length that appear in the training data).
2. Assign a probability to each subword based on its frequency in the corpus, forming a unigram language model: $P(token) = freq(token) / total_{freq}$.
3. For each word in the training data, find the most probable segmentation using the Viterbi algorithm (dynamic programming over all possible tokenizations).
4. Compute the overall log-likelihood of the corpus under the current model.
5. For each subword in the vocabulary, measure how much worse the model's predictions would become if that subword were removed.
6. Remove the subwords whose removal causes the smallest decrease (they are the least useful).
7. Repeat from step 2 until the vocabulary reaches the target size.

Figure 1.6.2: The Unigram model considers all possible segmentations and selects the one with the highest probability (lowest negative log-likelihood) using the Viterbi algorithm.

Comparison of the Three Methods

You need to know all three algorithms because you will encounter all three in production: GPT models use BPE, BERT uses WordPiece, and T5 uses Unigram. Understanding the differences helps you debug tokenization issues specific to each model.

WordPiece in Practice: Greedy MaxMatch Decoding

WordPiece (Schuster & Nakajima, 2012; Wu et al., 2016) differs from BPE in the training criterion that picks which adjacent symbols to merge. BPE merges the most frequent bigram; WordPiece merges the pair $(a,b)$ that maximizes the unigram-language-model gain

$$\text{score}(a, b) \;=\; \log \frac{P(ab)}{P(a)\,P(b)} \;\approx\; \log\!\Big(\tfrac{\text{count}(ab)}{\text{count}(a)\,\text{count}(b)} \cdot N\Big),$$

where $N$ is the total count of tokens in the corpus. The merge that maximizes this pointwise-mutual-information-like score is the one whose components are much more likely together than apart; this lets WordPiece prefer linguistically motivated splits over purely frequency-driven ones.

At inference time WordPiece does not replay a merge table the way BPE does. Instead it runs greedy longest-match (MaxMatch): for each whitespace-separated word, it tries to peel off the longest prefix that exists in the vocabulary, marks the remainder with the continuation prefix ##, and repeats on what is left. The diagram below traces the algorithm on the word unaffable.

The Hugging Face tokenizer used by BERT exposes exactly this algorithm:

from transformers import AutoTokenizer

tok = AutoTokenizer.from_pretrained("bert-base-uncased")
print(tok.tokenize("unaffable tokenization"))
# ['una', '##ffa', '##ble', 'token', '##ization']

# Manual MaxMatch on a single word, against the same vocabulary
def maxmatch(word, vocab):
    pieces, i = [], 0
    while i < len(word):
        j = len(word)
        while j > i and word[i:j] not in vocab and not (i > 0 and ("##" + word[i:j]) in vocab):
            j -= 1
        if j == i:                       # nothing matched -> unknown token
            return ["[UNK]"]
        piece = word[i:j] if i == 0 else "##" + word[i:j]
        pieces.append(piece); i = j
    return pieces

print(maxmatch("unaffable", set(tok.vocab)))
# ['una', '##ffa', '##ble']

['una', '##ffa', '##ble', 'token', '##ization']
['una', '##ffa', '##ble']

# pip install sentencepiece
import sentencepiece as spm
import tempfile, os
# Write sample training data to a temp file
corpus = "The cat sat on the mat.\nThe dog chased the cat.\nLanguage models learn from text."
tmp = tempfile.NamedTemporaryFile(mode="w", suffix=".txt", delete=False)
tmp.write(corpus); tmp.close()
# Train a small Unigram tokenizer
spm.SentencePieceTrainer.train(
    input=tmp.name, model_prefix="tiny_sp",
    vocab_size=50, model_type="unigram"
)
# Load and tokenize
sp = spm.SentencePieceProcessor(model_file="tiny_sp.model")
tokens = sp.encode("The cat chased the dog.", out_type=str)
print("Tokens:", tokens)
ids = sp.encode("The cat chased the dog.")
print("IDs:", ids)
print("Decoded:", sp.decode(ids))
os.unlink(tmp.name)

# pip install tokenizers
from tokenizers import Tokenizer
from tokenizers.models import BPE
from tokenizers.trainers import BpeTrainer
from tokenizers.pre_tokenizers import Whitespace
tokenizer = Tokenizer(BPE(unk_token="[UNK]"))
tokenizer.pre_tokenizer = Whitespace()
trainer = BpeTrainer(vocab_size=100, special_tokens=["[UNK]", "[PAD]"])
# Train on raw text (pass list of file paths for large corpora)
tokenizer.train_from_iterator(
    ["The cat sat on the mat", "The dog chased the cat"],
    trainer=trainer,
)
output = tokenizer.encode("The cat chased the dog")
print("Tokens:", output.tokens)
print("IDs:", output.ids)

Byte-Level BPE

Standard BPE operates on Unicode characters, which means the initial vocabulary must include all characters that appear in the training data. For multilingual models, this can mean thousands of distinct characters from Chinese, Japanese, Korean, Arabic, Devanagari, and other scripts before any merges even begin.

Byte-level BPE, introduced by the GPT-2 team (Radford et al., 2019), solves this by operating on raw bytes instead of Unicode characters. Since there are only 256 possible byte values, the initial vocabulary is always exactly 256, regardless of what languages or scripts appear in the data. Multi-byte Unicode characters (such as Chinese characters, which are typically 3 bytes in UTF-8) are initially represented as sequences of byte tokens, and BPE merges then learn to combine them into higher-level units.

Figure 1.6.4a: Byte-level BPE starts with 256 byte tokens and merges them upward. Common multi-byte characters become single tokens after training.

Tokenizer-Free Models

Byte-level BPE still requires a trained merge table and a fixed vocabulary. Could we go further and skip the vocabulary entirely? What if we eliminated the tokenizer altogether and let the model operate directly on raw bytes? This idea has gained traction with models like ByT5 (Xue et al., 2022) and MegaByte (Yu et al., 2023), which process byte sequences without any subword segmentation step.

ByT5: Bytes Are All You Need

ByT5 modifies the T5 architecture to accept raw UTF-8 bytes as input. It uses a vocabulary of only 259 tokens (256 byte values plus 3 special tokens). The obvious downside is that sequences become very long: a 100-word English sentence might be 400 to 600 bytes, compared to 120 to 150 subword tokens. ByT5 compensates with a deeper encoder (relative to the decoder) and achieves competitive performance on many NLP benchmarks while being more robust to noise, spelling errors, and cross-lingual transfer.

MegaByte: Hierarchical Byte Models

MegaByte addresses the long-sequence problem by introducing a hierarchical architecture. It divides the byte sequence into fixed-size patches (for example, P = 8 bytes each) and processes these patches with a large "global" transformer. Within each patch, a smaller "local" transformer predicts individual bytes. The global transformer processes N/P patches instead of N bytes, reducing the quadratic attention cost from O(N²) to O((N/P)² + P²). This two-level approach makes byte-level modeling practical for longer documents.

More recently, Meta's Byte Latent Transformer (BLT, 2024) dynamically allocates compute to complex byte sequences, achieving competitive performance with subword models while maintaining the benefits of byte-level input. This line of research suggests that the gap between tokenizer-free and subword-based models is narrowing.

Tradeoffs of Tokenizer-Free Models

Now that you understand how these algorithms work internally, Section 2.3 shows how they behave in practice: special tokens, chat templates, multilingual fertility, and cost estimation.

Exercises

from collections import Counter
def get_pairs(words): return Counter((w[i], w[i+1]) for w, c in words.items() for i in range(len(w)-1) for _ in range(c))
def merge(words, pair):
  new = {}; bg = "".join(pair)
  for w, c in words.items():
    nw = []; i = 0
    while i < len(w):
      if i < len(w)-1 and (w[i], w[i+1]) == pair: nw.append(bg); i += 2
      else: nw.append(w[i]); i += 1
    new[tuple(nw)] = c
  return new
words = {tuple(w): c for w, c in {"low":5,"lower":2,"newest":6,"widest":3}.items()}
for _ in range(3): pair = get_pairs(words).most_common(1)[0][0]; words = merge(words, pair); print(pair)