Dynamic programming improves byte pair encoding vocabulary selection
Dynamic-Programming-Guided Hierarchical BPE and Empirical Analysis of Vocabulary Pruning
Computation and LanguageMachine Learning
Summary
When computers turn text into pieces to understand it better, they often use a method called Byte Pair Encoding (BPE). The order in which BPE chooses these pieces isn't always the best for compressing text efficiently. The authors came up with a new method, DH-BPE, that uses a smart planning technique called dynamic programming to pick a better set of pieces. Their tests show this method can compress text more efficiently than several existing methods, especially when carefully selecting how many pieces to consider at first.
What this means in practice
- •For natural language processing teams: Optimize vocabulary selection in language models to improve text compression and efficiency under fixed vocabulary size limits.
- •For machine translation developers: Enhance subword tokenization for better compression and consistency in translation models with limited vocabulary budgets.
Authors
Kenny Shao
Abstract
Byte Pair Encoding (BPE) constructs vocabularies through greedy pair merging, but the resulting merge order does not necessarily allocate a fixed model-visible vocabulary optimally for compression. We propose Dynamic-Programming-Guided Hierarchical BPE (DH-BPE), a vocabulary-construction method that combines token exposure under exact minimum-token segmentation with the hierarchical dependencies induced by BPE training. Starting from a modestly overshot BPE candidate vocabulary, DH-BPE uses dynamic programming to measure candidate utility and applies exposure-guided, dependency-aware pruning to select a fixed-size model-visible vocabulary. We compare DH-BPE against Standard BPE and recent vocabulary-optimization baselines, including Pruned BPE, MinGram, and MinGram-PP, in primary evaluations at 12K and 16K target vocabulary sizes, with an additional 18K evaluation against MinGram only. Across the primary 12K and 16K comparisons, DH-BPE consistently improves aggregate compression over Standard BPE, Pruned BPE, and MinGram under a shared exact minimum-token DP encoder. MinGram-PP achieves stronger aggregate compression in the primary comparisons, but DH-BPE outperforms it at overshoot factors f = 2.0 and f = 3.0 in cross-corpus evaluation; at 12K, MinGram-PP reverses this ordering only with the substantially larger candidate pools at f = 4.0 and f = 5.0. Qualitative analysis further shows that DH-BPE balances later, more complete BPE merges with reusable subword components, providing a practical approach to improving vocabulary allocation under a fixed model-visible vocabulary budget.