Tokenization

Tokenization: converting between strings and sequences of integers (tokens). It sits at the boundary between raw text and the model, and its choices ripple through vocabulary size, sequence length, and how gracefully a model handles rare words, numbers, and other languages.

Granularity: characters, words, subwords

The core tradeoff is between vocabulary size and sequence length.

Unit	Vocab size	Sequence length	Out-of-vocabulary (OOV)
Character	Tiny (hundreds)	Very long	None
Word	Huge (100k+)	Short	Frequent (unknown words)
Subword	Moderate (30k to 250k)	Moderate	None (falls back to pieces)

Character-level models never see an unknown token but must spend many steps assembling meaning, and self-attention cost grows with sequence length. Word-level models are compact but brittle: any word not seen in training becomes <unk>, and the vocabulary explodes across morphology and typos. Subword tokenization is the standard compromise: frequent words stay whole, rare words decompose into meaningful pieces.

Byte Pair Encoding (BPE)

Byte Pair Encoding (BPE)

• train the tokenizer on raw text to automatically determine the vocabulary
  • Intuition: common sequences of characters are represented by a single token, rare sequences are represented by many tokens
• GPT uses word-based tokenization to break up the text into initial segments and then run the original BPE algorithm on each segment
  • Start with each byte as a token and successively merge the most common pair of adjacent tokens

def train_bpe(string: str, num_merges: int) -> BPETokenizerParams:
    # start with the list of bytes of `string`
    indices = list(map(int, string.encode("utf-8")))
    merges: dict[tuple[int, int], int] = {} # index1, index2 => merged index
    vocab: dict[int, bytes] = {x: bytes([x]) for x in range(256)} # index => byte
 
    for i in range(num_merges):
        # count the num of occurrences of each pair of tokens
        counts = defaultdict(int)
        for index1, index2 in zip(indices, indices[1:]): # for each adjacent pair of tokens
            counts[(index1, index2)] += 1 
 
        # find the most common pair
        pair = max(counts, key=counts.get)
        index1, index2 = pair
 
        # merge that most common pair
        new_index = 256 + i
        merges[pair] = new_index
        vocab[new_index] = vocab[index1] + vocab[index2]
        indices = merge(indices, index1, index2, new_index)
 
    return BPETokenizerParams(merges=merges, vocab=vocab)

Byte-level BPE

Starting from the 256 possible bytes rather than Unicode characters guarantees that any string, in any language, with any emoji or control byte, can be encoded with zero OOV. This is what GPT-2 and its successors use. A pre-tokenization regex first splits on whitespace and punctuation so merges do not cross word boundaries in awkward ways.

WordPiece and Unigram

• WordPiece (BERT): like BPE, but instead of merging the most frequent pair it merges the pair that maximizes the likelihood of the training corpus under a unigram language model. Concretely it picks the pair maximizing $\frac{\text{count}(xy)}{\text{count}(x)\text{count}(y)}$, favoring pairs that co-occur more than chance would predict.
• Unigram (SentencePiece): starts from a large candidate vocabulary and iteratively prunes it, keeping the pieces that best explain the data under a probabilistic model. Tokenization then picks the segmentation maximizing likelihood via Viterbi, and it can sample alternative segmentations (subword regularization) for robustness.

Vocabulary size tradeoffs

• Larger vocab: shorter sequences (cheaper attention, more text per context window), but a bigger embedding matrix and softmax, and rarer tokens are undertrained.
• Smaller vocab: longer sequences and more compute per token of text, but denser gradient signal per embedding.
• Typical modern LLMs land between 32k and 256k. Multilingual and code models push higher because they must cover many scripts and identifiers efficiently.

Common pitfalls

• Numbers and dates fragment unpredictably, which is a known source of arithmetic errors; some models add digit-level splitting.
• Tokenizer and model must match exactly at inference; a mismatched vocabulary produces garbage silently.
• Whitespace handling (leading-space tokens like the) is easy to get wrong and changes results.