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

• URL: http://arxiv.org/abs/2609.06898v1
• Date: Mon, 07 Sep 2026 00:50:08 GMT
• Title: Dynamic-Programming-Guided Hierarchical BPE and Empirical Analysis of Vocabulary Pruning
• Abstract summary: We propose a vocabulary-construction method that combines token exposure under exact minimum-token segmentation with the hierarchical dependencies induced by BPE training.<n>We show DH-BPE consistently improves aggregate compression over Standard BPE, Pruned BPE, and MinGram under a shared exact minimum-token DP encoder.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Pruned BPE: Post-training Visibility Pruning and Token Reallocation for Byte Pair Encoding [0.0]
  Pruned BPE is a post-training visibility-pruning and token-reallocation method.<n>It separates merge construction from model-visible vocabulary selection.<n>Experiments show that Pruned BPE consistently reduces encoded length relative to Standard BPE.
  arXiv  Detail & Related papers  (2026-08-01T19:34:44Z)
• Significance-Gain Pair Encoding for LLMs: A Statistical Alternative to Frequency-Based Subword Merging [0.0]
  Significance-Gain BPE is a drop-in alternative merge criterion that measures cohesion via a z-statistic under an independence null model.<n>It reduces validation and test perplexity by 13% and 12%, respectively, and improves validation and test BPC by about 0.9 to 1.0%.
  arXiv  Detail & Related papers  (2026-02-26T20:29:18Z)
• Parity-Aware Byte-Pair Encoding: Improving Cross-lingual Fairness in Tokenization [53.22544362024936]
  Tokenization is the first -- and often least scrutinized -- step of most NLP pipelines.<n>Standard algorithms for learning tokenizers rely on frequency-based objectives.<n>We introduce Parity-aware Byte Pair.<n>We find empirically that Parity-aware BPE leads to more equitable token counts across languages.
  arXiv  Detail & Related papers  (2025-08-06T18:14:43Z)
• Effective Length Extrapolation via Dimension-Wise Positional Embeddings Manipulation [60.22622442950905]
  Large Language Models (LLMs) often struggle to process and generate coherent context when the number of input tokens exceeds the pre-trained length.<n>Recent advancements in long-context extension have significantly expanded the context window of LLMs.<n>We propose Dimension-Wise Positional Embeddings Manipulation (DPE) to extrapolate the context window of LLMs.
  arXiv  Detail & Related papers  (2025-04-26T08:46:10Z)
• MorphTok: Morphologically Grounded Tokenization for Indian Languages [18.594241501479747]
  Tokenization is a crucial step in NLP, especially with the rise of large language models (LLMs)<n>We propose morphology-aware segmentation as a pre-tokenization step before applying the classical Byte-pair.<n>To handle the dependent vowels common in syllable-based writing systems, we propose Constrained BPE (CBPE)<n>CBPE handles dependent vowels to form a cohesive unit with other characters instead of occurring as a single unit.
  arXiv  Detail & Related papers  (2025-04-14T15:44:45Z)
• SuperBPE: Space Travel for Language Models [103.09169510391972]
  We introduce a "superword" tokenizer, SuperBPE, which incorporates a simple pretokenization curriculum into the byte-pair encoding (BPE) algorithm.<n>SuperBPE encodes a fixed piece of text with up to 33% fewer tokens than BPE on average.<n>Our model trained with SuperBPE achieves an average +4.0% absolute improvement over the BPE baseline across 30 downstream tasks.
  arXiv  Detail & Related papers  (2025-03-17T17:53:23Z)
• Adaptive BPE Tokenization for Enhanced Vocabulary Adaptation in Finetuning Pretrained Language Models [26.442558912559658]
  We show a fundamental limitation in vocabulary adaptation approaches that use Byte-Pair. (BPE) tokenization scheme for fine-tuning pretrained language models (PLMs) to expert domains. We propose AdaptBPE where the BPE tokenization phase is modified to first perform the longest string matching on the added (target) vocabulary before tokenizing at the character level.
  arXiv  Detail & Related papers  (2024-10-04T09:24:55Z)
• SelfSeg: A Self-supervised Sub-word Segmentation Method for Neural Machine Translation [51.881877192924414]
  Sub-word segmentation is an essential pre-processing step for Neural Machine Translation (NMT) This paper introduces SelfSeg, a self-supervised neural sub-word segmentation method. SelfSeg is much faster to train/decode and requires only monolingual dictionaries instead of parallel corpora.
  arXiv  Detail & Related papers  (2023-07-31T04:38:47Z)
• Efficient CNN with uncorrelated Bag of Features pooling [98.78384185493624]
  Bag of Features (BoF) has been recently proposed to reduce the complexity of convolution layers. We propose an approach that builds on top of BoF pooling to boost its efficiency by ensuring that the items of the learned dictionary are non-redundant. The proposed strategy yields an efficient variant of BoF and further boosts its performance, without any additional parameters.
  arXiv  Detail & Related papers  (2022-09-22T09:00:30Z)
• Dynamic Programming Encoding for Subword Segmentation in Neural Machine Translation [80.38621085548013]
  This paper introduces Dynamic Programming (DPE) a new segmentation algorithm for tokenizing sentences into subword units. A mixed character-subword transformer is proposed, which enables exact log marginal likelihood estimation and exact MAP inference to find target segmentations.
  arXiv  Detail & Related papers  (2020-05-03T05:00:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.