Byte Pair Encoding Algorithm

Byte pair encoding, also called digram coding, is an algorithm, first described in 1994, for encoding a string of text into a smaller string by repeatedly finding the most frequently occurring pair of adjacent symbols and replacing every occurrence of that pair with a single new symbol not otherwise present in the text, recording each substitution in a translation table so the original string can be reconstructed exactly; the process repeats, building longer symbols out of shorter ones, until no pair occurs often enough to be worth replacing or a set limit is reached. Philip Gage published the original version of the algorithm in 1994 in The C User Journal as a general-purpose data compression technique. A modified form of the same core idea was later adopted as a way to build a vocabulary for natural language processing systems, where it is used to merge the most frequent adjacent pairs of characters or existing subword tokens until a target vocabulary size is reached, an approach used in the tokenizers behind several modern large language models, including GPT-3.5 and GPT-4, whose combined vocabulary of ordinary byte pair encoding tokens and special symbols reaches slightly over one hundred thousand entries.