Tokenization & BPE

Byte-pair encoding builds a subword vocabulary by repeatedly merging frequent adjacent symbols in a training corpus. At inference, the tokenizer applies the learned merge rules to turn new text into token IDs.

Separate learning the vocabulary from tokenizing a string with that vocabulary. A merge that looks useful inside one word may have a different priority in the full corpus. Byte-level variants start with bytes, which helps represent unfamiliar text.

Training: look at a big corpus as sequences of characters. Find the most frequent adjacent pair (say t + h → th), merge it into a new symbol, and add it to the vocabulary. Repeat. Frequent sequences like ing, tion, or whole common words get absorbed into single tokens; rare words stay split into subwords.

Encoding new text just replays the learned merges in the order they were learned. The result: "tokenization" might be one token, while "antidisestablishmentarianism" becomes several subwords, with coverage determined by the base alphabet. Complete byte coverage avoids unknown text bytes; character-based vocabularies can still encounter unseen characters.

BPE is an algorithm rather than a closed-form equation. Training to a target vocabulary size $V$:

1. Initialize the vocabulary with all base symbols (characters, or the 256 bytes for byte-level BPE).
2. Count the frequency of every adjacent symbol pair across the corpus.
3. Merge the most frequent pair $(a, b) \to ab$; add $ab$ to the vocabulary and record the merge rule.
4. Repeat steps 2–3 until $|\text{vocab}| = V$ (e.g. 50,257 for GPT-2).

Encoding a new string: greedily apply the learned merge rules in learned order until no more apply. The number of tokens for a piece of text is what counts against a model's context window and per-token API pricing, so tokenization efficiency directly affects cost and how much you can fit in context.

Key takeaway: BPE = greedy frequency-based merging from characters up to a target vocab size. Subwords balance vocabulary size and sequence length. No-unknown-token coverage requires a complete base alphabet or fallback, such as byte-level BPE. Token-priced services count tokens rather than words.

A small merge-learning example only. It joins strings with spaces and permits merges across word boundaries; production tokenizers additionally define normalization, pre-tokenization, special tokens, and unknown-character handling.

1from collections import Counter
2
3def get_pairs(tokens: list[str]) -> Counter:
4    return Counter(zip(tokens, tokens[1:]))
5
6def train_bpe(corpus: list[str], num_merges: int) -> list[tuple[str, str]]:
7    tokens = list(" ".join(corpus))          # char-level start
8    merges: list[tuple[str, str]] = []
9    for _ in range(num_merges):
10        pairs = get_pairs(tokens)
11        if not pairs:
12            break
13        best = pairs.most_common(1)[0][0]    # most frequent adjacent pair
14        merges.append(best)
15        merged, i = [], 0
16        while i < len(tokens):               # apply the merge in one pass
17            if i < len(tokens) - 1 and (tokens[i], tokens[i + 1]) == best:
18                merged.append(tokens[i] + tokens[i + 1])
19                i += 2
20            else:
21                merged.append(tokens[i])
22                i += 1
23        tokens = merged
24    return merges
25
26merges = train_bpe(["lower", "lowest", "newer"], num_merges=5)
27print(merges)   # tie-breaking follows first occurrence in this example

1. Conceptual: Why use subword tokenization instead of words or characters? (Words explode the vocabulary and hit OOV; characters make sequences too long. Subwords balance vocabulary size and sequence length; OOV behavior depends on base-symbol coverage and fallback.)
2. Implementation: What does one BPE training step do? (Count adjacent symbol-pair frequencies and merge the most frequent pair into a new vocabulary symbol.)
3. Applied: Why does token count, not word count, matter for context limits and cost? (The model and pricing operate on tokens; a rare word may be several tokens, so token count determines how much fits in context and what you pay.)
4. Systems-level: What is byte-level BPE and what problem does it solve? (BPE over raw bytes instead of characters: it can represent any Unicode text, including emoji and rare scripts, with no unknown tokens.)
5. Failure modes: How does BPE vs. WordPiece differ? (Both use subwords. BPE encoding follows ranked merge rules; common WordPiece tokenizers use longest-match-first lookup in a vocabulary. Training objectives and fallback handling are implementation-specific.)

Without looking: describe the BPE training loop in three steps, explain why subword beats word- and character-level, and say why token count drives cost and context. Check against Stage 3.

Sources and further reading

• Sennrich et al., Neural Machine Translation of Rare Words with Subword Units: subword BPE training.
• Google Research BERT tokenizer implementation: WordPiece longest-match-first lookup and unknown-token handling.