Exploring Recombination for Efficient Decoding of Neural Machine Translation

Zhisong Zhang, Rui Wang, Masao Utiyama, Eiichiro Sumita, Hai Zhao

TL;DR

This paper introduces a novel "recombination" technique for Neural Machine Translation (NMT) decoding. By identifying and merging similar partial translation hypotheses, the method achieves comparable translation quality with significantly smaller beam sizes, leading to more efficient decoding without sacrificing accuracy.

What Problem Does This Paper Address?

Neural Machine Translation (NMT) models, particularly those using Recurrent Neural Networks (RNNs), excel at capturing the entire decoding history. However, this strength can lead to inefficiency: even minor differences in partial translation hypotheses (prefixes) are treated as entirely distinct. This means that many hypotheses that are locally similar and likely to lead to the same future translations are explored independently. This redundancy in the search space can slow down the decoding process, especially when using large beam sizes to ensure high-quality translations. The paper aims to address this inefficiency by intelligently merging these similar hypotheses.

Methods

The core of the proposed method is recombination, inspired by state merging in traditional Phrase-Based Statistical Machine Translation (PBSMT). The key idea is to define an equivalence function that determines when two partial hypotheses can be considered similar enough to be merged.

The authors propose a heuristic equivalence function based on an n-gram suffix and a length difference threshold. Specifically, two hypotheses are considered equivalent if their last n words (suffix) are identical and their lengths differ by no more than r. This function is applied during the beam search decoding process.

The Algorithm 1: Merging for Beam Search outlines the process:

  1. Candidates are sorted by their model scores.
  2. For each candidate, the algorithm checks if it can be merged with any existing surviving states in the beam.
  3. Merging occurs if the equivalence function is met and the candidate has a lower score than the state it would merge with (preventing merging a better hypothesis with a worse one).
  4. If a candidate is not merged, it's added to the surviving list.
  5. The beam size is then pruned as usual.

This approach adds minimal computational overhead, as the n-gram suffix matching is efficient, and it doesn't require additional neural computations.

Datasets

The proposed method was evaluated on two large-scale translation tasks:

  • Chinese-to-English (Zh-En): Using LDC corpora (1.4M sentence pairs) for training, NIST 02 for development, and NIST 03-06 for testing.
  • English-to-German (En-De): Using 4.5M WMT training data, with newstest 2012/2013 for development and newstest 2014-2016 for testing.

Key Insights and Ideas

  • Equivalence is Key: The paper highlights that the inefficiency in NMT decoding stems from treating locally similar hypotheses as fundamentally different. Defining a practical "equivalence" is crucial for recombination.
  • N-gram Suffix as a Heuristic: Using a simple n-gram suffix for equivalence is surprisingly effective. It captures local linguistic patterns that often indicate similar future translation paths, without the complexity of full neural feature comparison.
  • Efficiency Gains: The primary insight is that by merging, you can achieve the same or better translation quality with a smaller beam size, leading to a significant speedup. This is because the search space is pruned more intelligently.
  • Translation Graph: The recombination process naturally leads to the construction of a translation graph rather than just a k-best list. This graph can represent a much richer set of potential translations, potentially uncovering better hypotheses.
  • Model-Agnostic: The recombination mechanism is designed to be independent of the specific NMT model architecture, making it a general-purpose optimization for decoding.

Key Results

  • Comparable Quality, Faster Speed: The merge-enhanced searchers achieved similar translation quality (BLEU scores) with smaller beam sizes compared to ordinary searchers. For example, a beam size of 6 with merging achieved comparable or better results than a beam size of 12 without merging.
  • Significant Speedup: The speedup was substantial. A beam size of 6 with merging could be more than twice as fast as a beam size of 12 without merging (over 200 tokens/second vs. around 100 tokens/second).
  • Reduced Redundancy: The analysis showed that partial hypotheses were recombined approximately every two steps, and the resulting translation graph was, on average, 200 times larger than the original k-best list.
  • Improved Oracle Scores: The merge-based searcher achieved a higher oracle BLEU score (47.83) within its reached search space compared to ordinary beam search (42.57), indicating it explores a more diverse and potentially better set of hypotheses.
  • High Cosine Similarity: The hidden layer representations of merged partial hypotheses showed a very high average cosine similarity (0.986), validating the reasonableness of the merging criterion.

Limitations and Future Work

  • Heuristic Equivalence: The paper acknowledges that the n-gram suffix based equivalence function is a heuristic approximation. While efficient, it might not capture all nuances of hypothesis equivalence.
  • Model-Based Equivalence: The authors suggest that a more sophisticated, model-based equivalence function (e.g., trained using neural features) could be explored, though this might introduce extra computational cost and complexity.
  • Improved NMT Models: The potential of recombination might be further realized with improved NMT models, suggesting that the decoding optimization can complement advancements in model architecture.
  • Combination with SMT/LLMs: Exploring the combination of this recombination technique with traditional SMT or larger language models is suggested as an interesting future direction.
  • Hyperparameter Sensitivity: While preliminary experiments found good hyperparameter settings (n=4 for n-gram suffix, r=2 for length difference), further tuning might be beneficial.

Summary updated

Abstract

In Neural Machine Translation (NMT), the decoder can capture the features of the entire prediction history with neural connections and representations. This means that partial hypotheses with different prefixes will be regarded differently no matter how similar they are. However, this might be inefficient since some partial hypotheses can contain only local differences that will not influence future predictions. In this work, we introduce recombination in NMT decoding based on the concept of the "equivalence" of partial hypotheses. Heuristically, we use a simple $n$-gram suffix based equivalence function and adapt it into beam search decoding. Through experiments on large-scale Chinese-to-English and English-to-Germen translation tasks, we show that the proposed method can obtain similar translation quality with a smaller beam size, making NMT decoding more efficient.
BibTeX
@inproceedings{zhang2018exploring,
  author = {Zhisong Zhang and Rui Wang and Masao Utiyama and Eiichiro Sumita and Hai Zhao},
  title = {{Exploring Recombination for Efficient Decoding of Neural Machine Translation}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2018},
  url = {https://openreview.net/forum?id=8lvRh-H3RIM},
}

Loading related content...

Figure