Byte Pair Encoding

large-language-models

Definition

Byte Pair Encoding

Byte pair encoding is an algorithm for encoding strings or text into smaller strings by creating and using a translation table.

Algorithm

Counting Pairs: For a given text corpus, count all adjacent pairs of symbol in every word. If we denote a word as a sequence of symbols

$$w=s_1{s}_2{s}_3\dots s_n,$$

then each pair $(s_i,s_{i+1})$ is counted over the entire corpus.

Merging: Identify the most frequent pair, say $(a,b)$. This pair is merged into a new token, which can be denoted as $ab$. Mathematically, if $f(a,b)$ is the frequency of the pair, choose the pair with the maximum frequency:

$$(a,b{)}^{\ast }=\arg \underset{(a,b)}{\max }f(a,b)$$

Replace every occurrence of $a$ followed by $b$ in the corpus with the new token $ab$.

Repeat: Repeat the counting and merging steps until a predefined vocabulary size is reached or no pair occurs more than once.