# What changes when you randomly choose BPE merge operations? Not much

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 23 references that are in the map.
- First posted on arXiv 4 May 2023.

## Builds on (most cited first, 13 of 13)

- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing](https://mlsanity.com/paper/1808.06226/) (2018)
- [A Call for Clarity in Reporting BLEU Scores](https://mlsanity.com/paper/1804.08771/) (2018)
- [Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation](https://mlsanity.com/paper/1609.08144/) (2016)
- [Effective Approaches to Attention-based Neural Machine Translation](https://mlsanity.com/paper/1508.04025/) (2015)
- [Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates](https://mlsanity.com/paper/1804.10959/) (2018)
- [Between words and characters: A Brief History of Open-Vocabulary Modeling and Tokenization in NLP](https://mlsanity.com/paper/2112.10508/) (2021)
- [Fast WordPiece Tokenization](https://mlsanity.com/paper/2012.15524/) (2020)
- [Revisiting Low-Resource Neural Machine Translation: A Case Study](https://mlsanity.com/paper/1905.11901/) (2019)
- [Dynamic Programming Encoding for Subword Segmentation in Neural Machine Translation](https://mlsanity.com/paper/2005.06606/) (2020)
- [Evaluating Multiway Multilingual NMT in the Turkic Languages](https://mlsanity.com/paper/2109.06262/) (2021)

## Built on by (most cited first, 10 of 10)

- [Tokenization Is More Than Compression](https://mlsanity.com/paper/2402.18376/) (2024)
- [Unpacking Tokenization: Evaluating Text Compression and its Correlation with Model Performance](https://mlsanity.com/paper/2403.06265/) (2024)
- [Tokenization and the Noiseless Channel](https://mlsanity.com/paper/2306.16842/) (2023)
- [Greed is All You Need: An Evaluation of Tokenizer Inference Methods](https://mlsanity.com/paper/2403.01289/) (2024)
- [Beyond Text Compression: Evaluating Tokenizers Across Scales](https://mlsanity.com/paper/2506.03101/) (2025)
- [When Every Token Counts: Optimal Segmentation for Low-Resource Language Models](https://mlsanity.com/paper/2412.06926/) (2024)
- [LiteToken: Removing Intermediate Merge Residues From BPE Tokenizers](https://mlsanity.com/paper/2602.04706/) (2026)
- [DPAR: Dynamic Patchification for Efficient Autoregressive Visual Generation](https://mlsanity.com/paper/2512.21867/) (2025)
- [Train It and Forget It: Merge Lists are Unnecessary for BPE Inference in Language Models](https://mlsanity.com/paper/2508.06621/) (2025)
- [How Long Is a Piece of String? A Brief Empirical Analysis of Tokenizers](https://mlsanity.com/paper/2601.11518/) (2026)

## Abstract (arXiv)

We introduce three simple randomized variants of byte pair encoding (BPE) and explore whether randomizing the selection of merge operations substantially affects a downstream machine translation task. We focus on translation into morphologically rich languages, hypothesizing that this task may show sensitivity to the method of choosing subwords. Analysis using a Bayesian linear model indicates that two of the variants perform nearly indistinguishably compared to standard BPE while the other degrades performance less than we anticipated. We conclude that although standard BPE is widely used, there exists an interesting universe of potential variations on it worth investigating. Our code is available at: https://github.com/bltlab/random-bpe.