byte pair encoding bpe
**Byte Pair Encoding (BPE) Tokenization** is the **subword segmentation algorithm that iteratively merges the most frequent pair of adjacent tokens in a training corpus to build a vocabulary**, balancing the extremes of character-level tokenization (too fine-grained, long sequences) and word-level tokenization (too coarse, huge vocabulary, poor handling of rare words) — the foundation of tokenization in GPT, LLaMA, and most modern LLMs.
**BPE Training Algorithm**:
1. Initialize vocabulary with all individual bytes (or characters): {a, b, c, ..., z, A, ..., 0-9, punctuation}
2. Count all adjacent token pairs in the training corpus
3. Merge the most frequent pair into a new token: e.g., (t, h) → th
4. Update the corpus with the merged token
5. Repeat steps 2-4 until vocabulary reaches target size (typically 32K-128K tokens)
The result is a vocabulary of subword units ranging from single bytes to common words and word fragments.
**Encoding (Tokenization)**: Given input text, BPE applies learned merges in priority order (most frequent merges first). The text "unhappiness" might be tokenized as ["un", "happiness"] or ["un", "happ", "iness"] depending on learned merges. Greedy left-to-right matching is standard, though optimal BPE encoding algorithms exist.
**Vocabulary Design Considerations**:
| Parameter | Typical Range | Tradeoff |
|-----------|-------------|----------|
| Vocab size | 32K-128K | Larger → shorter sequences, more parameters in embedding |
| Training corpus | 10-100GB text | More diverse → better coverage |
| Pre-tokenization | Regex splitting | Affects merge boundaries |
| Special tokens | , , | Task-specific control |
| Byte fallback | Yes/No | Handles unknown characters |
**BPE Variants**:
- **Byte-level BPE** (GPT-2, GPT-4): Operates on raw bytes (256 base tokens), guaranteeing any input text can be tokenized without unknown tokens. Pre-tokenization splits on whitespace and punctuation using regex before applying BPE merges within each segment.
- **SentencePiece BPE** (LLaMA, Mistral): Treats the input as a raw character stream (including spaces as explicit characters like ▁). Language-agnostic — works identically for English, Chinese, code, etc.
- **WordPiece** (BERT): Similar to BPE but selects merges by likelihood ratio rather than frequency. Produces different vocabulary from BPE on the same corpus.
- **Unigram** (SentencePiece alternative): Starts with a large vocabulary and iteratively removes tokens, selecting the vocabulary that maximizes training corpus likelihood.
**Tokenization Quality Issues**: **Fertility** — how many tokens a word requires (high fertility = inefficient); English text averages ~1.3 tokens/word, non-Latin scripts can be 3-5× worse. **Tokenization artifacts** — semantically identical text can tokenize differently based on whitespace or casing. **Number handling** — numbers are often split unpredictably ("1234" → ["1", "234"] or ["12", "34"]), causing arithmetic difficulties. **Multilingual fairness** — vocabularies trained primarily on English allocate fewer merges to other languages, making them less efficient.
**Impact on Model Behavior**: Tokenization directly affects: **context length** (more efficient tokenization = more text per context window); **training efficiency** (fewer tokens = faster training); **model capabilities** (poor tokenization of code, math, or certain languages limits performance in those domains); and **output format** (models generate tokens, not characters — constraining possible outputs).
**BPE tokenization is the invisible infrastructure underlying all modern LLMs — a simple algorithm from data compression that became the universal interface between raw text and neural networks, with tokenizer quality directly impacting every aspect of model training and performance.**