Byte $n$-gram Encoding

Byte pair encoding BPE is the most popular tokenization algorithm to date, and most modern large language models use tokenizers built by this algorithm. Given a dataset, BPE works in a fairly simple way: for $K$ time steps, it greedily merges the most frequently co-occurring pair of tokens in a dataset to form a new token. Notably, BPE was originally proposed as a compression algorithm and ported into language modeling with only minor modifications. Pairwise merging is a reasonable default for general-purpose compression; for language modelling, we argue it is an arbitrary (and actively harmful) constraint. We thus lift this constraint and propose byte $n$-gram encoding B$n$E, a new method which greedily merges $n$ symbols at a time to produce new tokens. Experimentally, B$n$E shows significantly better compression than BPE, while avoiding the creation of unnecessary intermediate tokens. Further, LLMs trained on both tokenizers achieve similar performance.