# Dynamic-Programming-Guided Hierarchical BPE and Empirical Analysis of Vocabulary Pruning

arXiv: https://arxiv.org/abs/2609.06898 · HTML: https://mlsanity.com/paper/2609.06898/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 23 references that are in the map.
- First posted on arXiv 7 Sep 2026.

## Builds on (most cited first, 18 of 18)

- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [Pile of Law: Learning Responsible Data Filtering from the Law and a 256GB Open-Source Legal Dataset](https://mlsanity.com/paper/2207.00220/) (2022)
- [Tokenization Is More Than Compression](https://mlsanity.com/paper/2402.18376/) (2024)
- [Dynamic Programming Encoding for Subword Segmentation in Neural Machine Translation](https://mlsanity.com/paper/2005.06606/) (2020)
- [Greed is All You Need: An Evaluation of Tokenizer Inference Methods](https://mlsanity.com/paper/2403.01289/) (2024)
- [BPE Gets Picky: Efficient Vocabulary Refinement During Tokenizer Training](https://mlsanity.com/paper/2409.04599/) (2024)
- [Incorporating Context into Subword Vocabularies](https://mlsanity.com/paper/2210.07095/) (2022)
- [When Every Token Counts: Optimal Segmentation for Low-Resource Language Models](https://mlsanity.com/paper/2412.06926/) (2024)
- [An Analysis of BPE Vocabulary Trimming in Neural Machine Translation](https://mlsanity.com/paper/2404.00397/) (2024)
- [A Partition Cover Approach to Tokenization](https://mlsanity.com/paper/2501.06246/) (2025)
- [MinGram: A Minimalist Unigram Tokenizer with High Compression and Competitive Morphological Alignment](https://mlsanity.com/paper/2606.27019/) (2026)
- [Tokenisation via Convex Relaxations](https://mlsanity.com/paper/2605.22821/) (2026)
- [AdaptBPE: From General Purpose to Specialized Tokenizers](https://mlsanity.com/paper/2601.21665/) (2026)
- [LiteToken: Removing Intermediate Merge Residues From BPE Tokenizers](https://mlsanity.com/paper/2602.04706/) (2026)
- [Tokenization with Split Trees](https://mlsanity.com/paper/2605.22705/) (2026)
- [Train It and Forget It: Merge Lists are Unnecessary for BPE Inference in Language Models](https://mlsanity.com/paper/2508.06621/) (2025)
- [Writing-System-Level Tokenizer Adaptation for Byte-Level BPE](https://mlsanity.com/paper/2608.00582/) (2026)
- [Pruned BPE: Post-training Visibility Pruning and Token Reallocation for Byte Pair Encoding](https://mlsanity.com/paper/2608.00837/) (2026)

## Abstract (arXiv)

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.