PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Kenny Shao

arXiv:2609.06898v1cs.CLcs.LG

TL;DR

A greedy BPE merge order does not necessarily allocate a fixed model-visible vocabulary optimally for compression. DH-BPE combines exposure measured by exact minimum-token segmentation with BPE dependencies to prune an overshot candidate vocabulary. Across evaluated 12K and 16K settings, it improves aggregate compression over Standard BPE, Pruned BPE, and MinGram, while MinGram-PP can achieve stronger aggregate compression with substantially larger candidate pools.

  • Problem

    BPE’s greedy merge order does not necessarily allocate a fixed model-visible vocabulary optimally for compression.

    Source: §1 · p. 1

  • Method

    DH-BPE uses exact minimum-token segmentation to measure candidate exposure and combines that signal with BPE hierarchy to prune an overshot vocabulary.

    Source: §1 · p. 2, §3.1 · p. 5

  • Results

    Across evaluated 12K and 16K settings, DH-BPE improves aggregate compression over Standard BPE, Pruned BPE, and MinGram, while MinGram-PP can achieve stronger aggregate compression with substantially larger candidate pools.

    Source: §6 · p. 19

  • Takeaways & Limitations

    The qualitative analysis indicates that vocabulary construction balances highly specialized long tokens against reusable subword components.

    Source: §1 · p. 2, §6 · p. 19

    Compression alone does not establish improvements in language-model training or downstream performance.

    Source: §5.3 · p. 19

Abstract

from arXiv · show

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.

1 Introduction

BPE’s greedy merge order can leave a fixed model-visible vocabulary poorly allocated for compression, motivating a more direct measure of token utility. DH-BPE combines minimum-token exposure with BPE’s merge hierarchy to prune an overshot vocabulary to a fixed size.

1 Introduction

  • BPE can create tokens that serve mainly as intermediate merge components yet appear rarely in final encodings, leaving their model-visible utility uncertain.Pruned BPE addressed this mismatch through visibility pruning and token reallocation.Source: §1 · p. 1
  • Exact minimum-token segmentation identifies which competing vocabulary entries are selected to minimize encoded length, providing a direct signal of compression utility.BPE’s sequential merges also induce dependencies that can inform pruning decisions.Source: §1 · pp. 1–2
  • DH-BPE measures candidate exposure under exact minimum-token segmentation and uses BPE merge dependencies to guide pruning of an overshot vocabulary to a fixed visible size.Required lower-level tokens are protected during construction, even when they are not selected for the final encoder vocabulary.Source: §1 · p. 2
  • The study investigates two-space-token protection, overshoot, and pruning-ratio choices, alongside same-corpus and cross-corpus evaluation and qualitative analysis of retained tokens.The analysis examines allocation between longer corpus-specific tokens and shorter reusable components.Source: §1 · p. 2

2 Related Work

Related work addresses minimum-token segmentation, compression-oriented vocabulary construction, BPE pruning and adaptation, and dependency-aware modification. DH-BPE combines minimum-token exposure with the hierarchy inherited from BPE training.

2 Related Work

  • Fixed-vocabulary segmentation work studies probabilistic or minimum-token inference, while compression-oriented construction includes iterative deletion and broader optimization methods.PathPiece uses estimated token-count increase [3]; Greed-Tok [8], ConvexTok [9], and ToaST [10] use combinatorial or mathematical-programming approaches.Source: §2 · pp. 2–3
  • BPE pruning methods use contextual ablation, rarity, token-pair statistics, or intermediate-residue signals, while adaptation methods reallocate merges for target domains or writing systems.These selection signals differ from DH-BPE’s exact minimum-token exposure.Source: §2 · p. 3
  • Dependency-aware methods rewrite dependent merges, alternate pruning with new-merge discovery, or restrict removal to graph leaves; their pruning signals differ from DH-BPE’s compression exposure.BPE-knockout, ReBPE, and Purason et al. use BPE structure without combining it with minimum-token exposure.Source: §2 · p. 3
  • Table 1 compares selected methods across minimum-token construction, BPE pruning or reallocation, and explicit use of BPE structure.Pruned BPE and the MinGram variants are discussed separately rather than included in the table.Source: §2 · p. 3, Table 1 · p. 4

2.1 Pruned BPE

  • Pruned BPE [2] reallocates visible slots using final Standard BPE exposure while retaining internal-only merge tokens for encoding, unlike DH-BPE’s minimum-token exposure criterion.DH-BPE uses BPE hierarchy during construction and requires only the selected visible vocabulary for its encoder.Source: §2.1 · pp. 3–4

2.2 MinGram and MinGram-PP

  • MinGram [20] re-estimates Unigram scores from minimum-token paths and prunes by score, whereas MinGram-PP [20] iteratively removes tokens with low deletion impact.DH-BPE instead uses exposure as a pruning signal and combines it with BPE hierarchy; MinGram-PP’s final pruning is more expensive.Source: §2.2 · p. 4

3 Dynamic-Programming-Guided Hierarchical BPE

DH-BPE uses exact minimum-token dynamic programming to measure candidate exposure, then combines exposure eligibility with BPE merge order and dependency preservation. Overshoot and pruning thresholds control candidate availability and selection, with two-space tokens protected separately.

3.1 Minimum-Token Dynamic Programming

  • Exact minimum-token dynamic programming finds a valid segmentation with the fewest vocabulary tokens, and the same procedure supports candidate-exposure measurement and final encoding.Ties prefer the longer token at the earliest differing position, then the smaller token ID; exposure counts selections across training-corpus chunks.Source: §3.1 · p. 5

3.2 Hierarchical Vocabulary Pruning

  • BPE merge order encodes token dependencies, so DP exposure determines candidate eligibility while eligible candidates are selected in original merge order.Low-exposure tokens in the retained prefix remain temporarily available to preserve dependencies, then are excluded from the final encoder vocabulary.Source: §3.2 · pp. 5–6

3.3 Protection of Two-Space Tokens

  • DH-BPE exempts learned tokens beginning with two consecutive ASCII spaces from the exposure threshold because pretokenization isolates repeated-whitespace runs as whitespace chunks.The protected tokens consume positions in the target learned vocabulary, and the study evaluates this safeguard separately.Source: §3.3 · p. 6

3.4 Overshoot Factor and Pruning Ratio

  • The overshoot factor sets the size of the candidate pool, while the pruning ratio sets the minimum DP exposure required for ordinary candidates to qualify.The exposure threshold uses the BPE training frequency of the boundary token at the target-size point as its reference; a larger overshoot adds later merges and candidates to evaluate.Source: §3.4 · p. 7

3.5 Overall Vocabulary Construction Procedure

  • Construction trains BPE beyond the target size, measures candidate exposure, selects eligible tokens in merge order, and returns exactly the target number of visible tokens.The final vocabulary consists of 256 byte tokens, selected learned tokens, and reserved tokens; construction-only internal tokens are discarded for encoding.Source: §3.5 · pp. 7–8

4 Experiments

The experiments evaluate DH-BPE’s compression and vocabulary selection against baseline methods across primary 12K and 16K comparisons, examining how overshoot, pruning, and evaluation distribution relate to performance. They also characterize DH-BPE’s retained vocabulary as a selective balance between later BPE merges and reusable subword components.

4.1 Training and Evaluation Data

  • Corpus III is reserved for cross-corpus evaluation and parameter tuning, not tokenizer training or pruning; its five subsets range from related source types to strongly shifted English legal text.Corpus I and II contain approximately 640 MB and 1 GB, respectively; Corpus III is approximately 900 MB and includes Chinese medical, Weibo and Wikipedia data, plus English legal and Reddit text.Source: §4.1 · pp. 8–9

4.2 Compared Methods and Evaluation Methodology

  • All methods are compared at the same model-visible vocabulary size and use the same exact minimum-token DP encoder, so encoded-length differences reflect their constructed vocabularies.Pruned BPE's best aggregate pruning ratios under this evaluation are r = 0.70 at 12K and r = 0.65 at 16K.Source: §4.2 · pp. 9–10

4.3 Effect of Two-Space Token Protection

  • Two-space protection substantially improves English Legal under r = 0.80, reducing tokens by more than 1.5 million and driving the Corpus III total improvement, so it is used in subsequent DH-BPE experiments.Most other evaluation subsets change little, with smaller gains also appearing on Corpus I+II at r = 0.80.Source: §4.3 · p. 11, Figure 1 · p. 11

4.4 Effect of the Overshoot Factor

  • For same-corpus evaluation, f = 1.07 is best across tested pruning ratios; cross-corpus optima vary, while f = 1.15 is worst, and the preferred practical range is typically f = 1.07–1.08 when sufficient candidates exist.The low-overshoot preference also appears in the 12K Corpus II experiment; however, f = 1.07 cannot fill the 16K target at r = 0.75.Source: §4.4 · p. 12, Figure 2 · p. 12, Figure 3 · p. 13

4.5 Effect of the Pruning Ratio

  • Increasing r improves same-corpus compression, with r = 0.80 best, but cross-corpus optima favor r = 0.75 for f = 1.07–1.10 and r = 0.70 for f = 1.12–1.15; comparisons therefore use r = 0.70–0.75.The results indicate a trade-off between specializing to the training distribution and performance under distribution shift.Source: §4.5 · pp. 13–14, Figure 4 · p. 13

4.6 Comparison with Standard BPE, Pruned BPE, MinGram, and MinGram-PP

  • At 12K, DH-BPE reduces aggregate encoded length by 0.640% versus Standard BPE, exceeding Pruned BPE (0.480%) and MinGram (0.563%), while MinGram-PP achieves the strongest aggregate compression.On Corpus III, DH-BPE beats MinGram-PP at f = 2.0 and f = 3.0, but MinGram-PP reverses the ordering at f = 4.0 and f = 5.0; its subset advantage is not uniform across domains.Source: Table 2 · p. 14, §4.6 · p. 14
  • At 16K, DH-BPE beats Pruned BPE and MinGram in aggregate but not MinGram-PP; at 18K, DH-BPE produces 70,552 fewer tokens than MinGram across Corpus I+II and Corpus III.At 16K, DH-BPE beats MinGram-PP on Corpus III at both tested factors, f = 2.0 and f = 3.0; larger MinGram-PP overshoots were not evaluated at this size. At 18K, MinGram is better on Corpus I+II by 158,758 tokens, while DH-BPE is better on Corpus III by 229,310.Source: Table 3 · p. 15, §4.6 · pp. 15–16

4.7 Qualitative Analysis of Retained Tokens

  • DH-BPE and Pruned BPE share 11,755 of 12,000 tokens (97.96%), but DH-BPE retains more complete lexical units where Pruned BPE often retains stems or continuations.Examples include Arizona, Taylor, and YouTube for DH-BPE versus Ariz, Tay, and Tube for Pruned BPE.Source: §4.7 · pp. 16–17
  • Fewer than 2.1% of final entries differ between DH-BPE and Pruned BPE, as DH-BPE adds some later, more complete merges beyond the original target boundary.Examples include DH-BPE’s 流动性, 好莱坞, and 眼睛, alongside multi-character units such as 一方面 and 相当于.Source: §4.7 · p. 17
  • 11,572 tokens (96.43%) are shared with MinGram, which retains more complete lexical items while DH-BPE often keeps shorter reusable components.MinGram’s flat score-based pruning favors longer items on minimum-token paths; DH-BPE’s BPE-structured, DP-exposure criterion can preserve intermediate subwords useful across larger constructions.Source: §4.7 · p. 17
  • 10,070 tokens (83.92%) are shared with MinGram-PP at f = 5.0, while DH-BPE retains more reusable stems and continuations than lexicalized or corpus-specific strings.MinGram-PP’s much larger candidate pool makes very late merges available; DH-BPE uses f = 1.07, so the contrast reflects both candidate-pool breadth and pruning strategy.Source: §4.7 · pp. 17–18
  • DH-BPE balances useful later BPE merges with compositional units rather than uniformly favoring shorter or longer tokens.Its limited overshoot can extend useful merges while DP-guided exposure preserves reusable components, helping explain how it improves compression without MinGram-PP’s substantially expanded candidate pool.Source: §4.7 · p. 18

5 Discussion

DH-BPE’s compression gains depend on candidate-pool and pruning choices, and same-corpus performance does not fully predict cross-corpus results. Its evaluation is limited to encoded token count and a bounded range of experimental settings.

5.1 Vocabulary Construction and Parameter Selection

  • DH-BPE improves aggregate compression over Standard BPE, Pruned BPE, and MinGram across evaluated vocabulary sizes under the shared exact minimum-token DP encoder.Relatively small overshoot factors generally perform best; larger candidate pools can reduce compression quality.Source: §5.1 · p. 18
  • The smallest sufficient overshoot is preferred, while aggressive pruning can help same-corpus compression and moderate pruning can balance behavior across corpora.An undersized candidate pool may leave too few eligible tokens to fill the final vocabulary.Source: §5.1 · p. 18

5.2 Generalization Across Corpora

  • Same-corpus compression does not fully predict cross-corpus performance, and the relative ordering of DH-BPE, MinGram, and MinGram-PP varies across Corpus III domains.Vocabulary construction therefore involves allocating capacity between corpus-specific patterns and broader utility across distributions.Source: §5.2 · p. 18
  • DH-BPE can recover useful later merges while retaining reusable components more often than MinGram, especially heavily overshot MinGram-PP.Specialized long tokens can compress recurring patterns, whereas reusable components may remain useful across a broader range of distributions.Source: §5.2 · pp. 18–19

5.3 Limitations

  • Evaluation is limited to encoded token count and a bounded range of corpus scales, vocabulary sizes, and language distributions; DP-pass overhead and automatic parameter selection remain unquantified.Compression alone does not establish improvements in language-model training or downstream performance.Source: §5.3 · p. 19

6 Conclusion

Across the evaluated 12K and 16K settings, DH-BPE improves aggregate compression over Standard BPE, Pruned BPE, and MinGram. The results point to a trade-off between specialized long tokens and reusable components across distributions.

6 Conclusion

  • Across 12K and 16K, DH-BPE improves aggregate compression over Standard BPE, Pruned BPE, and MinGram, while MinGram-PP’s advantage remains domain-dependent.DH-BPE combines minimum-token exposure with the dependency structure of a BPE-derived candidate vocabulary under a fixed model-visible vocabulary budget.Source: §6 · p. 19
  • Effective vocabulary construction balances highly specialized long tokens against reusable components that remain useful across distributions.The qualitative analysis identifies DH-BPE as one practical mechanism for navigating this trade-off.Source: §6 · p. 19
  • DH-BPE uses token exposure under exact minimum-token segmentation together with dependencies among tokens in a BPE-derived candidate vocabulary.Source: §6 · p. 19
Loading 2609.06898v1…