Understanding Byte Pair Encoding (BPE): A Greedy Subword Compression Algorithm for NLP

What is Byte Pair Encoding (BPE)?

Byte Pair Encoding (BPE) is a data‑compression‑inspired algorithm originally proposed by Philip Gage in 1994 and later adopted for subword segmentation in Natural Language Processing (NLP). By iteratively merging the most frequent adjacent symbols, BPE builds a vocabulary of subword units that reduces the out‑of‑vocabulary (OOV) problem and captures word morphology.

Algorithm Steps

Represent the corpus as a space‑separated token sequence.

Initialize the vocabulary with all individual characters and count their frequencies in the corpus.

Identify the most frequent pair of adjacent symbols (the "byte pair") and merge it into a new symbol, updating the corpus accordingly.

Repeat step 3 until a predefined vocabulary size is reached or the incremental gain becomes negligible.

Tokens not covered by the final vocabulary are mapped to the unknown token [UNK].

Concrete Example

Given the sentence the longest and widest pools are the best, the initial tokenization splits each word into characters with an underscore marking word boundaries, e.g., t h e _. The algorithm then counts character‑pair frequencies, merges the most common pairs such as t+h, h+e, e+_, and continues merging (e.g., e+s becomes es) across iterations. After several rounds, the sentence is represented as subword units like the_ long est_ and_ wid est_ pools_ are_ the_ best_, enabling the model to handle unseen words and capture morphological patterns.

Properties and Performance

The greedy nature of BPE yields a fast implementation with linear time complexity. Research (Gallé, EMNLP 2019) shows that BPE approaches optimal segmentation, while truly optimal algorithms have higher computational costs.

Limitations

Non‑linguistic merges: because BPE relies solely on frequency, it may combine characters in ways that ignore linguistic boundaries (e.g., merging the suffix “‑est” in unrelated contexts).

Limited morphological awareness: for languages with rich morphology (Arabic, Turkish, Finnish) the frequency‑based merges can be insufficient.

Approximate morphological splits: BPE and its variants may produce unintuitive segmentations such as splitting tokenization into to ken ization.

Alternative Subword Algorithms

WordPiece : Used by Google, it scores candidate merges with pointwise mutual information (PMI) rather than raw frequency, favoring merges that are unlikely to occur independently.

SentencePiece : Does not assume space‑separated words, making it suitable for East Asian languages; it performs subword segmentation directly on raw text without explicit token boundaries.

Research Directions

Current work explores combining morphological analysis or dictionaries with BPE‑style segmentation to achieve more precise language model inputs.