Exploring Recombination for Efficient Decoding of Neural Machine Translation

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

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.

Introduction

In Neural Machine Translation (NMT), the decoder (typically an RNN) generates a translation word-by-word. Because these models use continuous hidden states that capture the entire preceding history, the search process treats every unique prefix as a completely different state. For example, "the workers in these two cities" and "workers of these two cities" lead to different hidden states, even though their future predictions (the words following "cities") are likely to be identical.

Standard beam search is forced to keep both in its limited "k-best" list, wasting slots on redundant paths. This inefficiency means we often need large beam sizes to find high-quality translations, which slows down inference. This paper introduces Recombination—a classic trick from statistical machine translation—into the NMT decoding process to address this redundancy.

Methods

The core idea is to identify "equivalent" partial hypotheses and keep only the one with the highest score, effectively merging redundant paths into a translation lattice.

The Equivalence Function

Since NMT states are continuous and technically never identical, the authors use a heuristic $n$-gram suffix match to define equivalence. Two states $s_1$ and $s_2$ are considered equivalent if they share the same $n$-gram suffix (e.g., the last 4 words are the same) and the difference in their sequence lengths is below a small threshold $r$ (e.g., 2 words).

Search with Merging

The authors modify the standard beam search algorithm. At each time step, before pruning the beam to size $k$, the algorithm checks if a new candidate can be merged into an existing surviving state. If a match is found, and the new candidate has a lower score, it is "merged" (discarded as a redundant path). By merging paths, the decoder creates a "translation graph" or lattice that can represent roughly 200 times more possible sequences than a standard k-best list of the same size.

Figure 5: A visualization of the translation lattice where equivalent partial hypotheses are merged based on their suffixes.

To keep this efficient, they use hashing for the $n$-gram suffixes, ensuring that the merging check adds less than 10% overhead to the total decoding time.

Experimental Results

The method was evaluated on two large-scale translation tasks: NIST Chinese-to-English (Zh-En) and WMT English-to-German (En-De).

Efficiency Gains

On the Zh-En task, a searcher with beam size 6 plus merging achieved a BLEU score of 37.17, slightly outperforming a standard searcher with beam size 12 (37.11 BLEU). Because the beam size was effectively halved for the same quality, the merging-enhanced decoder was more than twice as fast (over 200 tokens/sec vs. ~100 tokens/sec).

Figure 3: BLEU scores and decoding speeds for Zh-En and En-De tasks, comparing standard beam search (w/o merge) against the proposed method (w merge).

Hidden State Validation

To see if their $n$-gram heuristic actually made sense for neural networks, the authors calculated the cosine similarity between the hidden layers of merged states. The average similarity was 0.986, confirming that states with the same suffix are indeed "nearly equivalent" in the eyes of the model. In a beam size of 10, the authors found an average of 22.5 merges per sentence, indicating that a partial hypothesis is recombined roughly every two steps.

Conclusion

Recombination provides a robust way to improve NMT decoding efficiency without retraining models. While the current approach relies on a simple $n$-gram suffix heuristic, it successfully captures the redundancy inherent in neural hidden states. Future work may involve training neural models to predict state equivalence or adapting the technique for Transformer architectures, which utilize self-attention over the entire history.

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},
}
Figure