mlsanityData to 7 Oct 2026

Dynamic Programming Encoding for Subword Segmentation in Neural Machine Translation

arXiv 2005.06606 ↗First posted 3 May 2020cs.CL cs.LGcited by 38

Not on the map. Why?

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).

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 8; 2023: 9; 2024: 7; 2025: 3; 2026: 3.

38 papers.

Sort:

  1. 2021Charformer: Fast Character Transformers via Gradient-based Subword Tokenizationcited by 158
  2. 2021Between words and characters: A Brief History of Open-Vocabulary Modeling and Tokenization in NLPcited by 130
  3. 2021Survey of Low-Resource Machine Translationcited by 92
  4. 2024Tokenization Is More Than Compressioncited by 87
  5. 2021Multi-view Subword Regularizationcited by 40
  6. 2024Greed is All You Need: An Evaluation of Tokenizer Inference Methodscited by 34
  7. 2021You should evaluate your language model on marginal likelihood over tokenisationscited by 29
  8. 2022The SIGMORPHON 2022 Shared Task on Morpheme Segmentationcited by 25
  9. 2022Improving Tokenisation by Alternative Treatment of Spacescited by 19
  10. 2025ActionPiece: Contextually Tokenizing Action Sequences for Generative Recommendationcited by 18
  11. 2023Should you marginalize over possible tokenizations?cited by 17
  12. 2024Scaffold-BPE: Enhancing Byte Pair Encoding for Large Language Models with Simple and Effective Scaffold Token Removalcited by 16
26 more
  1. 2021Joint Optimization of Tokenization and Downstream Modelcited by 15
  2. 2024Two Counterexamples to Tokenization and the Noiseless Channelcited by 13
  3. 2024Lexically Grounded Subword Segmentationcited by 13
  4. 2021How to Split: the Effect of Word Segmentation on Gender Bias in Speech Translationcited by 11
  5. 2022Incorporating Context into Subword Vocabulariescited by 11
  6. 2023What changes when you randomly choose BPE merge operations? Not muchcited by 10
  7. 2024Evaluating Subword Tokenization: Alien Subword Composition and OOV Generalization Challengecited by 8
  8. 2022Tokenization Consistency Matters for Generative Models on Extractive NLP Taskscited by 7
  9. 2023Subword Segmental Machine Translation: Unifying Segmentation and Target Sentence Generationcited by 7
  10. 2022Local Byte Fusion for Neural Machine Translationcited by 5
  11. 2022How Effective is Byte Pair Encoding for Out-Of-Vocabulary Words in Neural Machine Translation?cited by 3
  12. 2022Extending the Subwording Model of Multilingual Pretrained Models for New Languagescited by 3
  13. 2023Subwords as Skills: Tokenization for Sparse-Reward Reinforcement Learningcited by 3
  14. 2024Triples-to-isiXhosa (T2X): Addressing the Challenges of Low-Resource Agglutinative Data-to-Text Generationcited by 3
  15. 2021Dynamic Acoustic Unit Augmentation With BPE-Dropout for Low-Resource End-to-End Speech Recognitioncited by 2
  16. 2025The Learning Dynamics of Subword Segmentation for Morphologically Diverse Languagescited by 2
  17. 2023Evolution of Efficient Symbolic Communication Codescited by 1
  18. 2023SelfSeg: A Self-supervised Sub-word Segmentation Method for Neural Machine Translationcited by 1
  19. 2025PrahokBART: A Pre-trained Sequence-to-Sequence Model for Khmer Natural Language Generationcited by 1
  20. 2022LCP-dropout: Compression-based Multiple Subword Segmentation for Neural Machine Translationcited by 0
  21. 2023Elementwise Language Representationcited by 0
  22. 2023Downstream Task-Oriented Neural Tokenizer Optimization with Vocabulary Restriction as Post Processingcited by 0
  23. 2023Tokenization Preference for Human and Machine Learning Model: An Annotation Studycited by 0
  24. 2026Pretraining Language Models with Subword Regularization: An Empirical Study of BPE Dropout in Low-Resource NLPcited by 0
  25. 2026When Tokenization is Secretly Output Supervisioncited by 0
  26. 2026Dynamic-Programming-Guided Hierarchical BPE and Empirical Analysis of Vocabulary Pruningcited by 0