Byte Pair Encoding: Compressing Text for LLMs

### The Mental Model Byte Pair Encoding (BPE) is a data compression algorithm that works like creating custom abbreviations for a text. It starts by treating every individual character as a token, then iteratively finds the most common adjacent pair of tokens and merges them into a new, single token. This process builds a vocabulary of not just characters, but also common sub-word units.

### How It Works BPE builds a vocabulary and encodes text in a few steps:

1. **Initialization**: The initial vocabulary consists of all unique characters (bytes) present in the training text. 2. **Iteration**: The algorithm scans the text to find the most frequently occurring pair of adjacent tokens. For example, in a large English text, this might be `('t', 'h')`. 3. **Merging**: This most frequent pair is merged into a single new token (e.g., `'th'`) which is then added to the vocabulary. 4. **Replacement**: All instances of the original pair in the text are replaced with the new merged token. 5. **Repetition**: Steps 2-4 are repeated for a predetermined number of merges. This number is a hyperparameter that defines the final vocabulary size. The process might later merge `'th'` and `'e'` into `'the'`.

### When to Use It * **LLM Tokenization**: This is the primary modern use case. It allows models to create a fixed-size vocabulary that includes common sub-words (`pre`, `ing`, `ly`). This lets the model handle words it has never seen before by breaking them down into known sub-word components. * **Data Compression**: Its original purpose was to compress files by replacing common sequences of bytes with shorter codes from a translation table.

### When NOT to Use It * **Non-Statistical Data**: BPE is ineffective on random or uniformly distributed data where no byte pairs appear more frequently than others. * **When Vocabulary Control is Not Desired**: For some tasks, a simple character-level or word-level tokenization might be sufficient and easier to implement and debug.

### One Canonical Example Imagine we want to encode the string `aaabdaaabac`.

1. **Initial Vocabulary**: `{'a', 'b', 'd', 'c'}` 2. **First Merge**: The most frequent pair is `aa`. We merge it into a new token, `Z`. * **New Vocabulary**: `{'a', 'b', 'd', 'c', 'Z'}` * **Updated String**: `ZabdZabac` 3. **Second Merge**: The most frequent pair in the new string is `ab`. We merge it into a new token, `Y`. * **New Vocabulary**: `{'a', 'b', 'd', 'c', 'Z', 'Y'}` * **Updated String**: `ZYdZYac`

After just two merges, the vocabulary now contains sub-string tokens, and the text representation is shorter.