  Byte Pair Encoding (BPE) serves as a foundation method for text tokenization
in the Natural Language Processing (NLP) field. Despite its wide adoption, the
original BPE algorithm harbors an inherent flaw: it inadvertently introduces a
frequency imbalance for tokens in the text corpus. Since BPE iteratively merges
the most frequent token pair in the text corpus while keeping all tokens that
have been merged in the vocabulary, it unavoidably holds tokens that primarily
represent subwords of complete words and appear infrequently on their own in
the text corpus. We term such tokens as Scaffold Tokens. Due to their
infrequent appearance in the text corpus, Scaffold Tokens pose a learning
imbalance issue for language models. To address that issue, we propose
Scaffold-BPE, which incorporates a dynamic scaffold token removal mechanism by
parameter-free, computation-light, and easy-to-implement modifications to the
original BPE. This novel approach ensures the exclusion of low-frequency
Scaffold Tokens from the token representations for the given texts, thereby
mitigating the issue of frequency imbalance and facilitating model training. On
extensive experiments across language modeling tasks and machine translation
tasks, Scaffold-BPE consistently outperforms the original BPE, well
demonstrating its effectiveness and superiority.
