arXiv:2609.06898cs.CLcs.LG2026-09

用动态规划优化字节对编码的词表构建,提升压缩效率。

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

  • 结合动态规划与层级依赖关系,智能筛选最优词表
  • 在12K和16K词表规模下均优于标准BPE和多个基线方法
  • 适合需要高效词表分配的模型部署场景

字节对编码(BPE)通过贪心合并构建词表,但其合并顺序未必能为压缩目标提供最优的模型可见词表。本文提出动态规划引导的分层BPE(DH-BPE),将精确最小词元分割下的词元暴露度与BPE训练引发的层级依赖相结合。从略过量的初始候选词表出发,DH-BPE利用动态规划评估候选词元价值,并基于暴露度与依赖感知进行剪枝,选出固定大小的模型可见词表。在12K和16K目标词表规模下,与标准BPE、剪枝BPE、MinGram及MinGram-PP等近期优化基线对比,DH-BPE在共享精确最小词元动态规划编码器下持续提升整体压缩性能。尽管MinGram-PP在主实验中表现更优,但在跨语料库评估中,当溢出因子f=2.0和f=3.0时,DH-BPE反超;仅在更大候选池(f=4.0和5.0)下,MinGram-PP才在12K规模上逆转结果。定性分析表明,DH-BPE在后期完整合并与可复用子词组件间取得良好平衡,为固定词表预算下的词表分配提供了实用方案。

原文摘要 · Abstract (English)

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.

词表优化BPE动态规划压缩

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。