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

Kenny Shao

cs.CLSep 7, 2026

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

Authors: Kenny Shao

Abstract

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.

Figures & tables

Method	Vocabulary modification	Segmentation / optimization	BPE dependency	Selection or removal signal	Primary objective
PathPiece	Top-down pruning from a large seed	Exact minimum-token DP	No explicit use	Estimated token-count increase after omission	Token-count compression
SaGe	Top-down pruning from an oversized seed	Iterative re-tokenization with contextual scoring	No explicit use	Contextual Skip-Gram ablation loss	Context-aware vocabulary construction
BPE trimming	Post-training vocabulary reduction	BPE encoding with recursive decomposition	Uses BPE decomposition	Final token-frequency threshold	Vocabulary reduction
PickyBPE	During BPE training	Modified BPE training	No explicit merge graph	Intersection-over-Self criterion	Remove redundant intermediate tokens
LiteToken	Post-training residue removal	BPE-based split and re-merge	Yes	Intermediate/final usage and neighbor-diversity signals	Remove underused merge residues
AdaptBPE	Fixed-budget merge replacement	BPE merge adaptation	Yes	Adaptation-corpus frequency and compression	Domain/language adaptation

Table 1: Comparison of DH-BPE with closely related BPE vocabulary-construction and refinement methods

Panel of Figure 1 — Figure 1: Effect of two-space token protection across four DH-BPE configurations

Panel of Figure 2 — Figure 2: Effect of the overshoot factor for DH-BPE trained on Corpus I+II at an 18K target vocabulary size

Panel of Figure 3 — Figure 3: Effect of the overshoot factor for DH-BPE trained on Corpus II at a 12K target vocabulary size

Panel of Figure 4 — Figure 4: Effect of the pruning ratio for DH-BPE trained on Corpus I+II at an 18K target vocabulary size

Method	Configuration	Corpus II	Corpus I	Corpus III	Overall	$\mathbf{G_{M}}$ (%)
Standard BPE	–	307,026,651	190,730,625	276,009,112	773,766,388	0.000
Pruned BPE	$r=0.70$	305,341,252	190,006,412	274,706,279	770,053,943	0.480
MinGram	$f=1.15$	304,671,017	189,891,430	274,850,074	769,412,521	0.563
MinGram-PP	$f=2.0$	302,442,192	188,991,924	275,064,145	766,498,261	0.939
	$f=3.0$	302,224,084	189,055,077	275,376,899	766,656,060	0.919
	$f=4.0$	302,148,125	189,082,771	274,071,348	765,302,244	1.094

Table 2: Comparison of methods trained on Corpus II at a 12K target vocabulary size

Panel of Figure 5 — Figure 5: Encoded-length differences on Corpus III subsets for Corpus II-trained 12K vocabularies

Method	Configuration	Corpus II	Corpus I	Corpus III	Overall	$\mathbf{G_{M}}$ (%)
Standard BPE	–	292,257,884	182,736,861	263,421,152	738,415,897	0.000
Pruned BPE	$r=0.65$	290,775,983	181,962,160	262,531,829	735,269,972	0.426
MinGram	$f=1.15$	290,172,998	181,990,067	263,154,525	735,317,590	0.420
MinGram-PP	$f=2.0$	288,217,401	181,301,272	263,708,429	733,227,102	0.703
MinGram-PP	$f=3.0$	287,975,182	181,301,360	262,688,176	731,964,718	0.874
DH-BPE	$f=1.08,\ r=0.75$	290,193,410	181,843,497	262,355,943	734,392,850	0.545

Table 3: Supporting comparison using Corpus II training at a 16K target vocabulary size

Subword Tokenization

Subword tokenization divides text into reusable units smaller than words to support efficient and flexible language modeling.

See all 83 papers

Pruned BPE: Post-training Visibility Pruning and Token Reallocation for Byte Pair Encoding
Aug 1, 2026Kenny ShaoToken Pruning Subword Tokenization
Department of Computer Science Florida International University
Joint Optimization for Greedy Longest-match Tokenization
Jul 25, 2026Adhiraj Singh, Deepanshu Mody, Ghina Al Shdaifat +4Subword Tokenization
Center for Data Science, New York University New York, NY, USA · Kensho Technologies Cambridge, MA, USA
Rethinking BPE: Merge Selection as Model Selection
Oct 19, 2026Vijini Liyanage, François YvonTokenization in Language Models Tokenization
Sorbonne-Université, CNRS, ISIR, Paris

Aug 1, 2026J/K move · Enter open · S save

Pruned BPE: Post-training Visibility Pruning and Token Reallocation for Byte Pair Encoding

Kenny Shao

Department of Computer Science Florida International University

Token Pruning Subword Tokenization Byte-Pair Encoding

Open paper AskPDF arXiv

Byte Pair Encoding (BPE) is widely used for subword tokenization, but standard BPE exposes every learned merge token to the downstream model, including tokens that mainly serve as intermediate construction units and rarely appear in the final encoded corpus. This paper proposes Pruned BPE, a post-training visibility-pruning and token-reallocation method that separates merge construction from model-visible vocabulary selection. After standard BPE training, tokens are evaluated by final exposure. Low-exposure tokens are retained as internal-only merge nodes, while their visible vocabulary slots are reassigned to better-exposed candidates learned through resumed training. During encoding, internal-only tokens are recursively expanded into visible descendants while the original BPE merge order is preserved. Experiments on two non-overlapping English- and Chinese-dominated corpora and their combination show that Pruned BPE consistently reduces encoded length relative to Standard BPE at the same training corpus, evaluation corpus, and model-visible vocabulary size. At a 40% exposure threshold, the reduction is approximately 0.27%--0.36% on same-corpus evaluations. In a vocabulary-only evaluation using a shared exact minimum-token dynamic-programming encoder, Pruned BPE retains an advantage of approximately 0.23%--0.31%, indicating that the improvement arises from a more efficient visible vocabulary. These gains represent a meaningful fraction of the approximately 1.5%--3.8% marginal reduction that would otherwise require adding another 2K Standard BPE tokens. Qualitative analysis shows that internal-only tokens include reusable English fragments, Chinese components, partial UTF-8 byte sequences, and structured-text fragments. The results indicate that post-training visibility pruning can improve BPE vocabulary efficiency without increasing the vocabulary exposed to the language model.

Abstract

Subword Tokenization

Explore similar work

Pruned BPE: Post-training Visibility Pruning and Token Reallocation for Byte Pair Encoding

Joint Optimization for Greedy Longest-match Tokenization

Rethinking BPE: Merge Selection as Model Selection