byte pair encoding bpe

**Byte-Pair Encoding (BPE)** is **the dominant subword tokenization algorithm that iteratively merges the most frequent character pairs to build a vocabulary balancing coverage and granularity** — enabling neural language models to handle open-vocabulary text without out-of-vocabulary tokens while maintaining manageable sequence lengths. **Algorithm Mechanics:** - **Character Initialization**: Start with a base vocabulary of individual characters or bytes (256 entries for byte-level BPE) - **Frequency Counting**: Count all adjacent token pairs across the training corpus - **Greedy Merging**: Merge the most frequent adjacent pair into a single new token and add it to the vocabulary - **Iterative Expansion**: Repeat the counting and merging process until the target vocabulary size is reached (typically 32K–100K tokens) - **Deterministic Encoding**: At inference time, apply learned merge rules in priority order to segment new text into subword tokens - **Handling Rare Words**: Rare or novel words decompose into known subword units, ensuring zero out-of-vocabulary tokens **Variants and Implementations:** - **Original BPE**: Character-level merges based purely on frequency counts, used in GPT-2 and GPT-3 tokenizers - **WordPiece**: Selects merges that maximize the language model likelihood rather than raw frequency, employed in BERT and related models - **Unigram Language Model**: Starts with a large candidate vocabulary and iteratively prunes low-probability tokens, used in T5, XLNet, and ALBERT - **SentencePiece**: A language-agnostic library that treats input as a raw byte stream, removing the need for pre-tokenization rules specific to any language - **Byte-Level BPE**: Operates directly on UTF-8 bytes rather than Unicode characters, guaranteeing coverage of all possible inputs without unknown tokens - **TikToken**: OpenAI's optimized BPE implementation written in Rust, offering significantly faster encoding and decoding speeds for production workloads **Impact on Model Performance:** - **Vocabulary Size Tradeoff**: Larger vocabularies produce shorter token sequences (better context utilization) but require bigger embedding tables consuming more memory - **Multilingual Tokenization**: BPE naturally handles scripts lacking explicit word boundaries such as Chinese, Japanese, and Thai - **Tokenizer Fertility**: The average number of tokens per word varies by language — approximately 1.2 for English but 2–3 for morphologically rich languages like Finnish or Turkish - **Context Window Efficiency**: Compression ratio directly determines how much raw text fits within a model's fixed context length - **Downstream Task Sensitivity**: Tokenization granularity affects tasks like named entity recognition, where splitting entities across subwords complicates span detection - **Training Corpus Dependency**: The tokenizer's merge rules reflect the statistical properties of the training data, meaning domain-specific text may be poorly compressed **Practical Considerations:** - **Pre-tokenization**: Most implementations split text on whitespace and punctuation before applying BPE merges to prevent cross-word merges - **Special Tokens**: Tokenizers reserve IDs for control tokens like [PAD], [CLS], [SEP], [BOS], [EOS], and [UNK] - **Normalization**: Unicode normalization (NFC, NFKC) applied before tokenization ensures consistent encoding of equivalent characters - **Vocabulary Overlap**: When fine-tuning, using the same tokenizer as pretraining is critical to avoid embedding mismatches BPE tokenization represents **the critical preprocessing bridge between raw text and neural computation — its design choices in vocabulary size, merge strategy, and byte-level versus character-level operation fundamentally shape model efficiency, multilingual capability, and effective context utilization across all modern language model architectures**.