# Dynamic Programming Encoding for Subword Segmentation in Neural Machine Translation

arXiv: https://arxiv.org/abs/2005.06606 · HTML: https://mlsanity.com/paper/2005.06606/

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 May 2020.

## Built on by (most cited first, 30 of 38)

- [Charformer: Fast Character Transformers via Gradient-based Subword Tokenization](https://mlsanity.com/paper/2106.12672/) (2021)
- [Between words and characters: A Brief History of Open-Vocabulary Modeling and Tokenization in NLP](https://mlsanity.com/paper/2112.10508/) (2021)
- [Survey of Low-Resource Machine Translation](https://mlsanity.com/paper/2109.00486/) (2021)
- [Tokenization Is More Than Compression](https://mlsanity.com/paper/2402.18376/) (2024)
- [Multi-view Subword Regularization](https://mlsanity.com/paper/2103.08490/) (2021)
- [Greed is All You Need: An Evaluation of Tokenizer Inference Methods](https://mlsanity.com/paper/2403.01289/) (2024)
- [You should evaluate your language model on marginal likelihood over tokenisations](https://mlsanity.com/paper/2109.02550/) (2021)
- [The SIGMORPHON 2022 Shared Task on Morpheme Segmentation](https://mlsanity.com/paper/2206.07615/) (2022)
- [Improving Tokenisation by Alternative Treatment of Spaces](https://mlsanity.com/paper/2204.04058/) (2022)
- [Should you marginalize over possible tokenizations?](https://mlsanity.com/paper/2306.17757/) (2023)
- [ActionPiece: Contextually Tokenizing Action Sequences for Generative Recommendation](https://mlsanity.com/paper/2502.13581/) (2025)
- [Scaffold-BPE: Enhancing Byte Pair Encoding for Large Language Models with Simple and Effective Scaffold Token Removal](https://mlsanity.com/paper/2404.17808/) (2024)
- [Joint Optimization of Tokenization and Downstream Model](https://mlsanity.com/paper/2105.12410/) (2021)
- [Two Counterexamples to Tokenization and the Noiseless Channel](https://mlsanity.com/paper/2402.14614/) (2024)
- [Lexically Grounded Subword Segmentation](https://mlsanity.com/paper/2406.13560/) (2024)
- [How to Split: the Effect of Word Segmentation on Gender Bias in Speech Translation](https://mlsanity.com/paper/2105.13782/) (2021)
- [Incorporating Context into Subword Vocabularies](https://mlsanity.com/paper/2210.07095/) (2022)
- [What changes when you randomly choose BPE merge operations? Not much](https://mlsanity.com/paper/2305.03029/) (2023)
- [Evaluating Subword Tokenization: Alien Subword Composition and OOV Generalization Challenge](https://mlsanity.com/paper/2404.13292/) (2024)
- [Tokenization Consistency Matters for Generative Models on Extractive NLP Tasks](https://mlsanity.com/paper/2212.09912/) (2022)
- [Subword Segmental Machine Translation: Unifying Segmentation and Target Sentence Generation](https://mlsanity.com/paper/2305.07005/) (2023)
- [Local Byte Fusion for Neural Machine Translation](https://mlsanity.com/paper/2205.11490/) (2022)
- [How Effective is Byte Pair Encoding for Out-Of-Vocabulary Words in Neural Machine Translation?](https://mlsanity.com/paper/2208.05225/) (2022)
- [Extending the Subwording Model of Multilingual Pretrained Models for New Languages](https://mlsanity.com/paper/2211.15965/) (2022)
- [Subwords as Skills: Tokenization for Sparse-Reward Reinforcement Learning](https://mlsanity.com/paper/2309.04459/) (2023)
- [Triples-to-isiXhosa (T2X): Addressing the Challenges of Low-Resource Agglutinative Data-to-Text Generation](https://mlsanity.com/paper/2403.07567/) (2024)
- [Dynamic Acoustic Unit Augmentation With BPE-Dropout for Low-Resource End-to-End Speech Recognition](https://mlsanity.com/paper/2103.07186/) (2021)
- [The Learning Dynamics of Subword Segmentation for Morphologically Diverse Languages](https://mlsanity.com/paper/2511.09197/) (2025)
- [Evolution of Efficient Symbolic Communication Codes](https://mlsanity.com/paper/2306.02383/) (2023)
- [SelfSeg: A Self-supervised Sub-word Segmentation Method for Neural Machine Translation](https://mlsanity.com/paper/2307.16400/) (2023)

## Abstract (arXiv)

This paper introduces Dynamic Programming Encoding (DPE), a new segmentation algorithm for tokenizing sentences into subword units. We view the subword segmentation of output sentences as a latent variable that should be marginalized out for learning and inference. A mixed character-subword transformer is proposed, which enables exact log marginal likelihood estimation and exact MAP inference to find target segmentations with maximum posterior probability. DPE uses a lightweight mixed character-subword transformer as a means of pre-processing parallel data to segment output sentences using dynamic programming. Empirical results on machine translation suggest that DPE is effective for segmenting output sentences and can be combined with BPE dropout for stochastic segmentation of source sentences. DPE achieves an average improvement of 0.9 BLEU over BPE (Sennrich et al., 2016) and an average improvement of 0.55 BLEU over BPE dropout (Provilkov et al., 2019) on several WMT datasets including English <=> (German, Romanian, Estonian, Finnish, Hungarian).