Research Blog: 10 years of Byte-Pair Encoding Tokenization

Rico Sennrich, Associate Professor in Computational Linguistics at the University of Zurich

Neural machine translation of rare words with subword units was published 10 years ago at ACL. In a field that has changed so much in the last 10 years, it is somewhat surprising that byte-pair encoding (BPE) tokenization had such an enduring impact on the field, and is still used in the vast majority of Large Language Models (LLMs) today. I take this opportunity to reflect about some of the keys to success, and lessons learned, during the project.

To summarize why the paper is worth a reflection post: the limitation of neural translation and language models to a fixed vocabulary was a major limitation at the time, and existing solutions were unsatisfactory. The paper was the first to show that a data-driven subword segmentation is a simple and effective compromise between (small-vocabulary) word-level models and (inefficient) character-level models for text generation with neural models. In particular, BPE, originally a compression algorithm, was first adapted to the task of subword segmentation in this paper, and BPE still enjoys wide popularity as a tokenization algorithm in NLP and beyond. Lastly, learning a shared subword segmentation across languages has gained wide popularity because it enables massively multilingual models with modest vocabulary sizes, and has been named as one factor in the effectiveness of cross-lingual transfer.

Visualisation of how a paper abstract is tokenized byGPT-5 using BPE.

I will not claim that the lessons we learned are universally applicable, but maybe some insights from the project can help students shape their own research.

In spring 2015, neural machine translation (NMT) was making some waves, but still met with skepticism. Montreal had just submitted their NMT system output to the WMT 2015 shared task,  and while human evaluation results were still months away, the translation output was immediately public.

I was at the time concerned with two problems in machine translation: translation outputs with phrase-based systems were often ungrammatical because long-distance interactions weren't modelled, and word-based systems didn't handle compounds and inflectional morphology well. While I was investigating solutions in syntax-based machine translation, looking at NMT outputs allowed me to recalibrate research priorities. 

Indeed, grammaticality was already much better with NMT than with phrase-based systems, and even on par or better than the syntax-based system I was working on at the time:

The key challenge here is that the German subordinate clause has the verb at the end. The phrase-based output lacks a verb, the syntax-based only has an auxiliary without the necessary main verb, and only the Montreal system gets it right.

However, the NMT system was a clear step back when it came to translating compounds, often deleting parts of it as in ''reception centre'' below:

Looking at the data helped me decide that:

1. the limited vocabulary in NMT is not just a theoretical problem, but the impact on translation quality can be spotted within minutes.
2. the fact that NMT was competitive with other approaches despite this glaring problem meant that NMT had the potential to become the leading method for machine translation.

I regularly encourage my students to look at the data they're working with, and not just at metrics, but raw inputs and outputs. Sometimes, this reveals that the problem they want to address is dwarfed by other, bigger ones.

2a. Get out of your comfort zone

An important factor in the paper's success was timing. In early 2015, only few teams were actively working on NMT, and there was still a lot of untapped potential in the technology. At the same time, NMT had not yet demonstrated state-of-the-art results, and it lacked an ecosystem of tutorials, code documentation, and the like. Abandoning (at least temporarily) toolkits and methods in which I had become an expert to dive into something so unexplored did feel bad on some level, but I try to counter-steer this sunk-cost fallacy both in my own decisions and advice to students. Researchers should strive towards the unexplored, because that is where one can generate the most knowledge.

2b. Play to your strengths

Despite the previous recommendation, one of course still has to consider one's own strengths and resources. ''Why am I the right person to tackle this research project? Can I complete it before others do the same, or do it better?''

At the University of Edinburgh, we were in a good position to execute this project quickly and well because:

1. we could benefit from our expertise in machine translation, and re-use prepared data, baselines, and evaluation pipelines from previous work. We also made novel choices, for example being an early adopter of chrF for evaluation, but this was also helped by our knowledge of the research area.
2. we already worked on neural language modelling (for syntax-based machine translation), and thus were ahead of most research groups in that we already had some expertise, and almost more crucially, 4 NVIDIA GPUs, to train up neural systems.
3. we were able to work with an existing code base rather than having to re-implement NMT from scratch. Open-sourcing of research code was still less common than nowadays, and an important consideration when judging the feasibility of a research project.

Of course, with the growing size of the field and dominance of large language models, this question has become all the more pressing, even though the details have shifted. Access to code is rarely the main obstacle (although code rot and compatibility issues may lead to nasty surprises), but every academic has learned to steer their students away from large-scale pre-training research for which they don't have the resources. This can be anxiety-inducing, but I'm generally optimistic about students' ability to find a suitable project and make genuine research contributions:

1. It is ok to start with smaller/easier projects, as long as you challenge yourself enough for personal growth. Not every project needs to be field-changing, or published, but be ready to move on from it after a few months. The best projects for growth are those where even if they fail, you will have learned something that will help your next project, be it skills you can re-use or results that let you formulate a better research hypothesis.
2. If you follow the mainstream, it can indeed be harder to make a research contribution that won't be scooped or made obsolete quickly. But playing to your strengths can be as simple as working on a question or problem that has been underexplored, and where your interest and curiosity about the question sets you apart from others.

It may be debatable whether 1994 counts as old, but it is certainly much older than typical citations in NLP. We didn't start the project with a plan to use byte-pair encoding, but we started with the less elegant way of splitting rare words into character n-grams. I call this in-elegant because:

1. it introduced a sudden switch between frequent words (encoded as one token) and rare words (encoded as a potentially very long sequence of character n-grams).
2. character n-grams may also be unseen at training time.
3. the method didn't make use of the fact that rare words may be composed of multiple subwords that are themselves frequent.

Still, it was a valuable first experiment to validate our hypothesis that neural models could improve with these (primitive) subwords.
What we then wanted was a dynamic algorithm that learned a short code length for frequent words or subwords, and a longer code length for rare ones. After thinking about designing such an algorithm ourselves, the crucial insight was that this sounds very much like a compression algorithm, and that we should be able to identify one that fulfills all our requirements:

1. code length is dynamically assigned based on frequency statistics.
2. the encoding is lossless and revertible.
3. codes are "meaningful". Rare words are not assigned a random code, but a code that is similar to the code of similar words (similar here meaning that they share substrings).
4. the code book can be applied to encode new texts with the code book's vocabulary (importantly, including words not seen during tokenizer learning).

Coincidentally, work parallel to ours also proposed using a compression algorithm as a tokenizer for NMT, but chose Huffman codes, which fulfilled criteria 1-2, but not 3-4. Finding BPE as a fitting solution not only saved us time, but also means that we didn't clutter the field by re-inventing a compression algorithm.

That being said, BPE tokenization is conceptually different from just applying BPE compression to every text:

1. we disallow some merges to achieve more meaningful/efficient units - this is now known as pre-tokenization. 
2. most importantly, we distinguish between a learning and an inference phase. One cannot simply re-compress every text with BPE, which would lead to different code books every time, and only this distinction unlocks requirement 4.

Comparing to earlier or parallel work that paired word-level vocabularies with some backoff mechanisms for rare words, one property that made BPE tokenization attractive is its simplicity. It doesn't require architectural changes to the neural model, only has one hyper-parameter (the size of the merge list), and requires no linguistic resources beyond raw text.

If your goal is not just to publish, but to have other people use or even re-implement your work, it is worth putting a high weight on simplicity and ease of use. With ease of use, I don't mean releasing an implementation that is well-documented and convenient, although this is also important. Even on the algorithmic level, keeping the number of hyperparameters small, or favouring algorithms that are less sensitive to hyperparameter choice, will affect how easy it is to apply the algorithm to new settings. I think it's no coincidence that another widely adopted paper with my involvement, RMS Layer Normalisation, had simplicity (and thus efficiency) as its main selling point.

The significance of our paper was not immediately obvious to all readers, leading to a rejection at TACL and then NAACL 2016 before its acceptance at ACL 2016.

It is easy to be snarky in hindsight about some reviewer comments, but on a more constructive note, it raised my awareness of how important it can be to have a good model of the reader during the writing process. To give a bit of context, I suspect reviewers were experts in the then-dominant phrase-based machine translation, but didn't yet have much experience with neural machine translation. It is through this lens I see the following reviewer comments:

• authors should compare to the following [many] works on morphological segmentation [...].
  I believe our main problem was that we didn't sufficiently explain that we operated under different constraints than prior work on morphological segmentation, and that this made empirical comparison relatively uninteresting. Morphological segmenters whose main success criterion is agreement with human annotations operated with an open morpheme vocabulary, and thus did not solve the problem we were tackling. Going through the various paper versions (still visible in arXiv), we put an increasing emphasis on the fact that neural models operate with a fixed symbol vocabulary, and our goal to do open-vocabulary translation under this constraint. 
• results are not state-of-the art.
  This problem was two-fold. Our initial baseline was about 1 BLEU worse than previous work on NMT because one hyperparameter (gradient clipping) wasn't optimally set (see #4!). This was a lesson about putting sufficient energy into optimizing baselines to increase reader trust. Unfortunately, there was also a comparison that was (still) out of reach, namely that NMT was not yet SOTA compared to phrase-based and syntax-based systems on the English-German WMT task - we only achieved that in follow-up work where we made use of monolingual data for training via back-translation. The community should reward exploration of different approaches, rather than just building on the current SOTA, and I'm happy that there is awareness of this issue in reviewer guidelines. 
• I still don't get why you can call it an open-vocabulary system. If the system is entirely based on characters, then I understand that it can be open-vocabulary because all combinations of characters are possible. But my understanding is that the system is based on subwords defined by some automatic process, so there is no guarantee that all possible words can be generated.
  Perhaps the most frustrating rejection was because a reviewer misunderstood the paper, even after our rebuttal where we emphasized that characters remain part of the subword vocabulary. Maybe the reviewer overlooked this part of the response among other, less important comments in our rebuttal, and one lesson I took away is to keep author responses short and focused on critical points.

I focused on lessons learned from bringing the project towards publication, but of course, publication is not the end of a research journey. We further validated our strategy by participating in the WMT 2016 shared translation task, where our strong results helped to move the field towards neural methods, and disseminated BPE tokenization in various academic and industrial talks. 

 

It's also in the nature of research that we don't sit still, but try to challenge and improve upon earlier work. So my final recommendation to students is to embrace this process and the criticism that is natural part of it, and keep a healthy detachment from your work:
 

"[BPE] tokenization is the real root of suffering" according to Andrej Karpathy.

In 2015, I didn't predict that massively multilingual models with a shared vocabulary would become so effective so soon, but in this scenario it makes perfect sense to use bytes as the starting point instead of characters to control the vocabulary size. Nor did I predict the popularity of Large Language Models and pay-per-token pricing models, which means that tokenization disparities across languages cause economic unfairness. Efforts to improve aspects of BPE, or replace it with completely different strategies, are ongoing, and I'm looking forward to seeing and contributing to the future progress in the area.

Acknowledgments

I want to thank Barry Haddow, Alexandra Birch, Sina Ahmadi, Michelle Wastl, Hanxu Hu, and Jannis Vamvas for discussion and feedback on this blog post.