Byte-pair encoding was born as a data-compression technique (Gage, 1994): replace the most frequent pair of bytes with a new byte, and repeat. Sennrich et al. (2016) adapted it to word segmentation for machine translation: start with a vocabulary of characters, count the adjacent symbol pairs in a corpus, merge the most frequent one into a new symbol, and repeat; the number of merges is the only hyperparameter (2016, p. 1717). The learned merges are then applied, in order, to any word, even an unseen one: the unknown lower gets segmented as low + er (2016, p. 1718).
Tiny example. Corpus: canta ×4, cantan ×3, canto ×2, manta ×1 (Spanish “sings”, “they sing”, “I sing”, “blanket”). The most frequent pair is a n (13 times), merged into “an”; then an t (10) → “ant”; then c ant (9) → “cant”; then cant a (4) → “canta”. After four merges, canta is a single token, cantan = cant + an, canto = cant + o, and manta = m + ant + a.
The example shows what a linguist cares about. cant|o matches a morphological analysis; cant|an isolates the root but fuses the theme vowel with the person ending; m|ant|a is not morphological at all. BPE looks for compression, not morphemes, and finds morphemes only when they are frequent. There is a distant kinship with the distributional procedures by which Harris (1955) proposed to find morpheme boundaries, but here the criterion is frequency alone.
GPT-2 introduced a byte-level variant: the base vocabulary has only 256 symbols, so any Unicode string can be represented with no “unknown” token. To avoid wasteful merges such as dog., dog! and dog?, merging across character categories was forbidden (Radford et al., 2019, sec. 2.2); the final vocabulary had 50,257 tokens (Alammar & Grootendorst, 2024, p. 49). GPT-4, Llama 2 and StarCoder2 also use BPE (Alammar & Grootendorst, 2024, pp. 50–54); BERT uses WordPiece, a related algorithm (Alammar & Grootendorst, 2024, p. 43). See tokenization.