BPE is a greedy approximation to an intractable combinatorial optimization problem: find the vocabulary of size that minimizes the total encoded length of a corpus. Solving this exactly is NP-hard, so BPE substitutes a simple, fast heuristic — always merge the single most frequent adjacent pair — that in practice gets close to optimal compression.
Layer 4 · Foundations
Tokenization
The formal objective BPE greedily approximates, entropy and compression bounds, and the hardware cost of vocabulary size.
12 min read180 XP