mlsanityData to 14 Oct 2026

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

arXiv 2609.06898 ↗First posted 7 Sep 2026cs.CL cs.LGcited by 0

Not on the map. Why?

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.

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

18 of 23 references.

References · 18

  1. 2015Neural Machine Translation of Rare Words with Subword Unitscited by 2,918
  2. 2022Pile of Law: Learning Responsible Data Filtering from the Law and a 256GB Open-Source Legal Datasetcited by 113
  3. 2024Tokenization Is More Than Compressioncited by 89
  4. 2020Dynamic Programming Encoding for Subword Segmentation in Neural Machine Translationcited by 38
  5. 2024Greed is All You Need: An Evaluation of Tokenizer Inference Methodscited by 34
  6. 2024BPE Gets Picky: Efficient Vocabulary Refinement During Tokenizer Trainingcited by 31
  7. 2022Incorporating Context into Subword Vocabulariescited by 11
  8. 2024When Every Token Counts: Optimal Segmentation for Low-Resource Language Modelscited by 8
  9. 2024An Analysis of BPE Vocabulary Trimming in Neural Machine Translationcited by 7
  10. 2025A Partition Cover Approach to Tokenizationcited by 5
  11. 2026MinGram: A Minimalist Unigram Tokenizer with High Compression and Competitive Morphological Alignmentcited by 5
  12. 2026Tokenisation via Convex Relaxationscited by 4
6 more
  1. 2026AdaptBPE: From General Purpose to Specialized Tokenizerscited by 3
  2. 2026LiteToken: Removing Intermediate Merge Residues From BPE Tokenizerscited by 3
  3. 2026Tokenization with Split Treescited by 2
  4. 2025Train It and Forget It: Merge Lists are Unnecessary for BPE Inference in Language Modelscited by 1
  5. 2026Writing-System-Level Tokenizer Adaptation for Byte-Level BPEcited by 1
  6. 2026Pruned BPE: Post-training Visibility Pruning and Token Reallocation for Byte Pair Encodingcited by 1

Built on by

Not cited yet.