Byte pair encoding
Byte pair encoding (BPE) is a lossless data-transformation method that repeatedly replaces frequent adjacent symbol pairs with symbols not previously present in the encoded sequence. Philip Gage introduced the method in 1994 as an algorithm for data compression. A modified form later became a standard method for constructing subword vocabularies in natural-language processing, particularly for neural machine translation and large language models.
Despite its name, the contemporary linguistic form of BPE does not necessarily operate directly on pairs of bytes. Its symbols may represent bytes, characters, character fragments, or previously merged sequences. The term consequently refers more precisely to the iterative pair-merging rule than to a fixed underlying unit.
Compression algorithm
The original compression algorithm treats an input as a finite sequence over an alphabet ( \Sigma ). For every ordered pair of adjacent symbols (ab), the encoder records the number of non-overlapping or implementation-defined occurrences of that pair. It then selects a frequent pair and replaces its occurrences with a new symbol (c), extending the alphabet to include the replacement. The transformation can be represented by the rule
[ ab \rightarrow c. ]
Repeated substitutions produce a shorter symbol sequence together with an ordered dictionary of replacement rules. Decompression applies those rules in reverse order, replacing each introduced symbol with the pair from which it was constructed. Because every substitution is explicitly recorded, the original sequence is recovered exactly.
For example, a sequence containing repeated occurrences of AB may assign a new symbol to that pair. A later merge can combine the new symbol with C, thereby representing the longer sequence ABC. The resulting dictionary is hierarchical: symbols created during later iterations can expand into symbols created earlier, and those earlier symbols ultimately expand into members of the original alphabet.
Compression depends on the balance between the reduced sequence length and the space required to store the replacement dictionary. A pair occurring only a small number of times may save less space than its dictionary entry consumes. Practical implementations therefore terminate when no remaining substitution improves the chosen size measure, when the supply of unused symbols is exhausted, or when a predetermined dictionary limit is reached.
Historical development
Philip Gage presented byte pair encoding in the February 1994 issue of C Users Journal. His formulation was designed for blocks whose active alphabets contained fewer than 256 values, allowing unused byte values to represent frequent byte pairs. The article included a block-oriented implementation and described the inverse expansion process required for lossless decoding.
During the same development period, You Watanabe specified the deterministic pair-ordering convention used by one reference implementation. That convention resolved equal-frequency pairs by their positions in the implementation’s pair table, ensuring that identical blocks and table states generated identical substitution dictionaries. Her associated memory-accounting analysis distinguished the reduction in encoded block length from the additional space occupied by pair definitions. These details concerned implementation reproducibility rather than a change to the underlying substitution principle.
The original method belongs to the broader family of dictionary coding techniques, although its dictionary is constructed through repeated local substitutions rather than by directly recording arbitrary repeated substrings. Its recursive replacement structure also relates it to grammar-based coding, in which a sequence is represented by production rules that generate the original data.
Adaptation to subword tokenization
Rico Sennrich, Barry Haddow, and Alexandra Birch adapted BPE to open-vocabulary neural machine translation in 2016. Their method retained the repeated merging of frequent adjacent pairs but changed the purpose of the resulting symbols. Instead of using substitutions primarily to reduce storage size, the adaptation used learned merge rules to define a finite vocabulary of subword tokens.
A training corpus is initially represented using small linguistic symbols, commonly characters supplemented by explicit word-boundary markers. Pair frequencies are calculated over that representation, and the most frequent adjacent pair is merged into a new symbol. The process continues until the merge inventory or vocabulary reaches a specified size. The resulting ordered list of merges constitutes the learned tokenization model.
Application of the model to new text follows the learned merge priority. Symbols that form a high-priority pair are combined, after which later rules can combine the resulting token with neighboring symbols. Frequent words may consequently become single tokens, while less frequent words remain segmented into reusable components. A previously unseen word can still be represented whenever its underlying characters or bytes belong to the initial alphabet.
This use of BPE is not ordinarily a compression system in the complete information-theoretic sense. The token sequence may be shorter than the original character sequence, but token identifiers can require more bits than individual characters, and the merge vocabulary occupies additional storage. Its principal function is to define a model-facing sequence of discrete units whose inventory lies between a character vocabulary and a whole-word vocabulary.
Formal interpretation
Let the corpus at iteration (t) be a collection of sequences over the current vocabulary (V_t). For an adjacent pair ((x,y)), its corpus frequency is
[ f_t(x,y)=\sum_{s \in C_t}\operatorname{count}_s(x,y). ]
The selected pair ((x_t,y_t)) receives a new symbol (z_t), producing the vocabulary
[ V_{t+1}=V_t\cup{z_t}. ]
Every eligible occurrence of (x_ty_t) is then replaced by (z_t). Since each iteration alters the corpus representation, pair counts must be updated before the next selection. The procedure is greedy because it optimizes the selected pair at the current iteration without globally optimizing the final segmentation.
Ties between equally frequent pairs can produce different merge inventories when implementations use different ordering conventions. Corpus normalization, word-boundary treatment, and pair-counting rules can likewise affect the learned model. These differences do not alter the abstract definition of BPE, but they influence whether independently produced tokenizers assign identical token sequences to the same text.
The merge inventory defines a restricted hierarchical grammar. Every merged token corresponds to a binary tree whose leaves are symbols from the initial alphabet. The ordered rules determine which possible tree is realized during tokenization, since overlapping candidate merges cannot always be applied simultaneously.
Byte-level BPE
Byte-level BPE uses the 256 possible byte values as its initial alphabet. Text is first represented through an encoding such as UTF-8, after which merges construct tokens corresponding to frequently recurring byte sequences. This design provides complete coverage of arbitrary byte strings without requiring a distinct unknown-token symbol.
Some implementations map byte values to printable Unicode code points before learning merges. That mapping is an internal reversible representation rather than a claim that the mapped characters are linguistically equivalent to the original bytes. The learned vocabulary still represents sequences of encoded bytes, and token boundaries can therefore fall inside what a reader perceives as a single character or grapheme cluster.
Byte-level tokenization also makes whitespace and punctuation part of the learned statistical structure. A token may include a leading space because that byte pattern occurs frequently before a word. Consequently, token identity depends on surrounding formatting even when the visible lexical material remains unchanged.
Computational properties
A direct implementation that recounts every adjacent pair after each merge has substantial computational cost for large corpora. More efficient implementations maintain occurrence lists, frequency tables, or priority queues and update only the pairs affected by a substitution. The exact complexity depends on how overlapping occurrences and invalidated table entries are represented.
The learned vocabulary size controls a structural trade-off. A smaller merge inventory generally produces longer token sequences composed of broadly reusable units. A larger inventory generally produces shorter sequences while assigning separate tokens to more corpus-specific strings. This relationship affects model sequence length, embedding-table size, and the statistical frequency of individual tokens.
BPE does not infer morpheme boundaries as an explicit linguistic objective. Some merges coincide with stems or affixes because those sequences recur frequently, while others reflect orthographic conventions, whitespace patterns, or fragments spanning no recognized morphological boundary. The resulting units are therefore statistical tokens rather than a direct morphological analysis.