Investigating the Effectiveness of BPE: The Power of Shorter Sequences

Matthias GalléEMNLP 2019 · DOI

Abstract

Byte-Pair Encoding (BPE) is the predominant sub-word tokenization method in modern Natural Language Processing (NLP). This study argues that BPE’s success is primarily due to its efficiency as a data compression algorithm rather than linguistic or morphological accuracy. By evaluating various tokenization strategies across multiple language pairs, we demonstrate a strong negative correlation between the number of tokens per sentence and translation quality. Our findings suggest that for a fixed vocabulary budget, minimizing sequence length is a key driver of performance in Neural Machine Translation (NMT).

Introduction

In modern NLP, selecting the optimal "atomic symbols" or tokens is a critical design choice. While word-level tokenization suffers from massive vocabularies and out-of-vocabulary (OOV) errors, character-level models struggle with computational overhead and long-range dependencies. Sub-word tokenization, specifically BPE, has emerged as the industry standard to bridge this gap. Despite being a "greedy" algorithm lacking a linguistic foundation, BPE frequently outperforms more sophisticated morphological tools. This paper seeks to explain this phenomenon by framing tokenization as a data compression problem.

Methodology

The study treats tokenization as a task of finding a fixed-size dictionary ($N$) that represents a dataset using the minimum number of tokens. To isolate the impact of sequence length on translation quality, BPE was compared against several other compression algorithms while maintaining constant vocabulary sizes (16k or 32k tokens):

  • IRRMGP: A high-performance algorithm optimizing for the most "useful" substrings.
  • MAXLEN: A greedy algorithm selecting the longest repeating strings.
  • SEQUITUR: A linear-time algorithm building hierarchical text representations.
  • RANDOM: A baseline selecting random repeating patterns.

Experiments were conducted on two language pairs: the Kyoto Free Translation Task (KFTT) for Japanese $\leftrightarrow$ English and IWSLT’14 for German $\leftrightarrow$ English. Performance was evaluated using ConvS2S and Transformer architectures.

Results and Analysis

The core finding of this research is the "Compression Hypothesis": a significant negative correlation exists between the average number of tokens per sentence and the resulting BLEU score. As shown in the figures below, translation quality consistently drops as the mean tokens per sentence increase across all models and language pairs.

Translation quality (BLEU) vs. sequence length for English-to-German (en->de) translation.

BPE consistently performs near the top-left of these performance curves, achieving high BLEU scores with low token counts. It is often only slightly outperformed by the computationally intensive IRRMGP algorithm. Conversely, the RANDOM baseline, which produces the longest sequences, performed the worst, confirming that the efficiency of the sub-word vocabulary is paramount.

Translation quality (BLEU) vs. sequence length for Japanese-to-English (ja->en) translation.

Discussion

The results suggest that NMT models do not strictly require linguistically correct "morphemes." Instead, they benefit from shorter "paths" of tokens, which likely reduces the information bottleneck and the complexity of tracking dependencies across internal layers.

Interestingly, the study found that "optimal parsing" performed worse than greedy parsing. This indicates that consistency between dictionary construction and inference is more important than mathematical minimality at test time. Furthermore, maintaining word boundaries (preventing tokens from crossing whitespace) was found to be beneficial, suggesting that some linguistic priors remain valuable.

Conclusion

BPE serves as a "good enough" compressor that balances computational efficiency with sequence length reduction. While more optimal compressors like IRRMGP exist, their $O(n^4)$ complexity makes them impractical for large-scale LLM training. Future work should investigate if the "shorter is better" rule extends beyond translation to tasks like text summarization and generative pre-training.

Summary updated

BibTeX
@inproceedings{galle2019investigating,
  author = {Matthias Gallé},
  title = {{Investigating the Effectiveness of BPE: The Power of Shorter Sequences}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2019},
  doi = {10.18653/v1/d19-1141},
}
Figure