BytePair

Byte pair encoding (BPE) is a data compression and text processing technique that builds a vocabulary of subword units by iteratively merging the most frequent adjacent symbol pairs in a corpus. The process begins with the input text represented as a sequence of basic symbols, typically bytes or characters. In each step, the most frequent consecutive pair of symbols is replaced by a new symbol that represents that pair. The steps are repeated until a predefined vocabulary size or number of merges is reached. The resulting vocabulary consists of both the original symbols and the newly created merged symbols; text is encoded as a sequence of these tokens.

Origin and usage: The algorithm was introduced by P. Gage in 1994 as a data compression method. In the natural language processing community, BPE gained prominence after Sennrich, Haddow, and Birch (2016) demonstrated its effectiveness for subword tokenization in neural machine translation. Since then, BPE and its variants have become common in NLP; it is implemented in many tokenization toolkits such as Hugging Face’s tokenizers library, SentencePiece, and the WordPiece scheme used by some models.

Variants and notes: BPE can operate on bytes (byte-level BPE) or on characters; byte-level variants help handle rare or foreign characters and allow decoding of any text. The method is deterministic given the training data and the specified number of merges; it does not aim to minimize entropy like Huffman coding but to create a practical, fixed-size vocabulary of subword tokens. This approach reduces out-of-vocabulary issues by decomposing unseen words into known components.

Limitations: BPE depends on the training data; the same merges may not generalize across domains or languages; it can produce long tokens that are hard to interpret and may yield inconsistent tokenization in multilingual settings.