Tokenization: BPE, Unigram, and Why It Breaks

Tokenization is often presented as a simple preprocessing step: split text into chunks. In Large Language Models (LLMs), this is a misunderstanding. Tokenization is a statistical compression algorithm. It maps variable-length text sequences to fixed-length integer IDs to fit within a model’s embedding space. This compression is lossy. By prioritizing frequency over semantic coherence, methods like Byte-Pair Encoding (BPE) and Unigram introduce structural artifacts known as "glitch tokens" and "fertility." These artifacts degrade model performance and increase computational cost in ways that are invisible at the API level but critical at the mechanism level. Understanding these mechanics is essential for optimizing context window usage and reducing inference latency.

As Part 6 of the Transformers Under the Hood series, we examine the mechanics that underpin modern NLP pipelines.

The Greedy Merge of BPE

Byte-Pair Encoding (BPE) was introduced to handle out-of-vocabulary (OOV) words by breaking them into subword units. It operates as a greedy, iterative merging algorithm. The complexity of the merge operations is typically O(N log N) or O(N) depending on the implementation of the priority queue used to track pair frequencies, where N is the number of unique pairs.

Consider a corpus where the word "low" appears frequently, and "lower" appears less frequently. BPE starts with a character-level vocabulary. It scans the corpus for the most frequent pair of adjacent symbols. If "l" and "o" co-occur often, they merge into "lo". This process repeats until the vocabulary reaches a predetermined size.

The mechanism works as follows:

1. Initialization: The vocabulary contains all unique characters and common words.
2. Statistics: Count all adjacent pairs in the training data.
3. Merge: Select the most frequent pair and replace all occurrences in the corpus with a new single symbol.
4. Repeat: Continue until the vocabulary limit is reached.

This creates a hierarchy. The string "unhappiness" might be tokenized as ["un", "happi", "ness"]. The key characteristic of BPE is determinism. Given the same model and input, BPE always produces the same token sequence. However, this determinism is brittle. If a word appears only once in training (e.g., "unhappily"), BPE may split it into arbitrary subwords based on the remaining high-frequency pairs, potentially creating fragments that do not align with human linguistic intuition.

For example, consider the word "apple". If "ap" and "pl" are high-frequency pairs but "app" is not, BPE might tokenize it as ["ap", "ple"] rather than ["apple"], depending on the exact merge history. This fragmentation is inherent to the greedy nature of the algorithm, which prioritizes global frequency over local semantic integrity.

Unigram: Probabilistic Segmentation

Unigram tokenization, popularized by SentencePiece, diverges from BPE’s greedy merging by treating tokenization as a probabilistic inference problem. Instead of building a vocabulary by merging, Unigram starts with a large candidate vocabulary (often including all possible subwords up to a certain length) and prunes it.

The core mechanism relies on the Unigram Language Model. Each candidate token $w$ is assigned a probability $P(w)$ based on its frequency in the corpus. The goal is to find a subset of tokens that minimizes the cross-entropy loss between the model’s predicted distribution and the actual data. The pruning step works by iteratively removing the token that causes the smallest increase in loss, effectively retaining the most statistically significant tokens.

Unlike BPE, which has one deterministic path, Unigram allows multiple valid segmentations for a single string. For example, "apple" might be tokenized as ["apple"] or ["ap", "ple"] with different probabilities. During training, the algorithm uses the Forward-Backward algorithm (similar to Hidden Markov Models) to estimate these probabilities. During inference, the most likely segmentation is chosen.

This approach offers two advantages:

1. Resilience: It handles rare words better by maintaining a diverse set of subword candidates.
2. Flexibility: It can adapt to languages with complex morphology (e.g., agglutinative languages) by preserving meaningful morphemes.

However, Unigram is computationally heavier. It requires a pre-trained model and cannot easily extend its vocabulary dynamically. If a new word appears that is not in the candidate set, Unigram falls back to character-level tokenization, which can be inefficient.

SentencePiece: Language-Agnostic Fragmentation

SentencePiece is a popular implementation that unifies BPE and Unigram under a single framework. Its defining feature is that it treats input as a raw stream of Unicode characters, ignoring space-based tokenization.

In traditional tokenizers, spaces are special tokens. In SentencePiece, spaces are treated as regular characters, often encoded as ▁. This means the tokenizer learns to segment text based on statistical patterns in the raw character stream, not linguistic rules.

For example, the phrase "hello world" might be tokenized as ["hello", "▁", "world"] or ["hell", "▁o", "▁world"] depending on the training data. This makes SentencePiece language-agnostic. It does not need separate rules for English, Chinese, or Japanese. It simply learns what constitutes a "word" in the given language.

The downside is fragmentation. To keep the vocabulary size manageable (e.g., 32k tokens), SentencePiece often breaks words into smaller pieces. A single English word might become 2-3 tokens. This increases the sequence length, which directly impacts the model’s context window usage and latency. Additionally, treating punctuation as part of the byte stream can lead to inconsistent handling of special characters across different languages, requiring careful post-processing in some pipelines.

Failure Modes: Glitch Tokens and Fertility

The primary risk of these compression schemes is the introduction of artifacts that do not correspond to semantic meaning.

Glitch Tokens

Glitch tokens are tokens that appear in the vocabulary but have no consistent semantic meaning across contexts. They often arise from:

1. Rare Substrings: A sequence of characters that appears frequently enough to be merged but rarely enough to not form a coherent concept.
2. Training Noise: Artifacts from the training data, such as HTML tags or markdown syntax, that are not stripped out.

For example, a token like ing might appear in English verbs but could be a glitch in another context. When the model encounters such tokens, it may assign them arbitrary weights, leading to hallucinations or nonsensical outputs. Glitch tokens are particularly dangerous because they are valid tokens, so the model processes them without error, but their semantic contribution is noise.

Fertility

Fertility refers to the phenomenon where a single word is split into multiple tokens. For instance, the word "unbelievable" might be tokenized as ["un", "believ", "able"], resulting in three tokens.

High fertility has two direct consequences:

1. Context Window Waste: The model’s context window is finite. If every word is split into 2-3 tokens, the effective vocabulary coverage drops, and the model runs out of context faster.
2. Latency Increase: Each token requires a forward pass through the model’s layers. More tokens mean more computation. For long documents, high-fertility tokenization can double the inference time.

Fertility is exacerbated by small vocabulary sizes. A 32k vocabulary will fragment words more aggressively than a 100k vocabulary. Developers must balance vocabulary size against computational cost.

Conclusion

Tokenization is not a neutral preprocessing step. It is a design choice that trades semantic integrity for statistical efficiency. BPE offers simplicity and determinism but struggles with rare words. Unigram offers robustness and diversity but requires complex training. SentencePiece provides language-agnostic flexibility but often at the cost of high fertility and glitch tokens.

Understanding these mechanisms allows developers to diagnose issues like unexpected latency or hallucinations. By monitoring token counts and analyzing glitch tokens, engineers can optimize their pipelines for better performance and reliability.