Metraipolis › archive › dc_66f555eb4847

Dynamic-Programming-Guided Hierarchical BPE and Empirical Analysis of Vocabulary Pruning — arXiv:2609.06898

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.06898
License (as archived)
CC0-1.0
Archived
2026-10-16T12:45:22.964Z
SHA-256 of the archived text
2d8c6cd0a30431dab812442e30b6d05149768460ffcb7665f28726639f483ebf
Stable URL of this page
https://metraipolis.com/documento/dc_66f555eb4847

How to cite

Dynamic-Programming-Guided Hierarchical BPE and Empirical Analysis of Vocabulary Pruning — arXiv:2609.06898 — arXiv (en), https://arxiv.org/abs/2609.06898 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_66f555eb4847 (Metraipolis archive dc_66f555eb4847, sha256 2d8c6cd0a30431dab812442e30b6d05149768460ffcb7665f28726639f483ebf)
BibTeX
@misc{dc66f555eb4847,
  title = {Dynamic-Programming-Guided Hierarchical BPE and Empirical Analysis of Vocabulary Pruning — arXiv:2609.06898},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.06898},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_66f555eb4847; sha256 2d8c6cd0a30431dab812442e30b6d05149768460ffcb7665f28726639f483ebf},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.06898. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-09 in cs.CL).
Categorie arXiv: Computation and Language (cs.CL) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.06898 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T12:30:25.076Z dalla pagina https://arxiv.org/catchup/cs.CL/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).