Source-linked AI summary
Beam Search Strategies for Neural Machine Translation
Markus Freitag, Yaser Al-Onaizan
TL;DR
NMT beam search can waste computation on poor candidates while excluding near-best hypotheses, and larger beams slow decoding. The paper introduces score- and history-based pruning that makes candidate counts flexible. Across German-English and Chinese-English experiments, decoding became up to 43% faster without losing translation quality.
Problem
Fixed-size beam search explores candidates far worse than the best while potentially excluding near-best hypotheses, whereas larger beams reduce decoding speed.
Method
The paper applies relative, absolute, local-score, and shared-history pruning schemes after reducing candidates to the current beam size.
Results
Up to 43% faster decoding was achieved without losing translation quality across the German-English and Chinese-English experiments.
Takeaways & Limitations
Pruning can make NMT beam search faster without sacrificing translation quality in the reported experiments.
Abstract
from arXiv · showhide
The basic concept in Neural Machine Translation (NMT) is to train a large Neural Network that maximizes the translation performance on a given parallel corpus. NMT is then using a simple left-to-right beam-search decoder to generate new translations that approximately maximize the trained conditional probability. The current beam search strategy generates the target sentence word by word from left-to- right while keeping a fixed amount of active candidates at each time step. First, this simple search is less adaptive as it also expands candidates whose scores are much worse than the current best. Secondly, it does not expand hypotheses if they are not within the best scoring candidates, even if their scores are close to the best one. The latter one can be avoided by increasing the beam size until no performance improvement can be observed. While you can reach better performance, this has the draw- back of a slower decoding speed. In this paper, we concentrate on speeding up the decoder by applying a more flexible beam search strategy whose candidate size may vary at each time step depending on the candidate scores. We speed up the original decoder by up to 43% for the two language pairs German-English and Chinese-English without losing any translation quality.
1 Introduction
NMT has reached performance comparable to or better than SMT, shifting attention toward practical decoding. This work targets faster beam search by pruning candidates without losing translation quality.
- NMT has achieved performance comparable to or better than traditional statistical machine translation.
- NMT decoding uses left-to-right beam search to approximately maximize a trained model’s conditional probability.
- Fixed-size beam search can explore poor-scoring candidates and miss near-best hypotheses outside the beam.
- Increasing beam size can improve translation performance but significantly reduces decoder speed after quality reaches a saturation point.
- The proposed work prunes the search graph to speed decoding without losing translation quality.
2 Related Work
Prior work improves NMT search efficiency by restricting candidate vocabularies or pruning candidates using score-based thresholds. This paper extends that line by investigating absolute and relative pruning schemes from statistical machine translation.
- Earlier work introduced the original beam-search strategy for sequence-to-sequence models and NMT.
- Constraint softmax methods reduce computation by normalizing only a limited set of translation candidates.
- Other work retains tokens whose local scores remain within a beam-size threshold of the best token and prunes weak partial hypotheses.
- This paper investigates absolute and relative pruning schemes previously applied successfully in statistical machine translation.
3 Original Beam Search
Original beam search builds translations left to right while retaining a fixed number of highest-scoring candidates at each step. Completed hypotheses leave the active beam, and decoding ends when no active candidates remain.
- The decoder approximately maximizes a model’s conditional probability while constructing translations left to right.
- At each time step, it keeps a fixed beam of translation candidates with the highest log-probability.
- Selecting an end-of-sequence symbol reduces the beam by one and stores that translation in the final candidate list.
- When the beam reaches zero, the decoder selects the highest-log-probability translation after length normalization.
4 Search Strategies
The proposed search strategies first limit candidates to the current beam, then prune according to score differences, local scores, or shared histories. These mechanisms allow the active candidate count to vary with search conditions.
- All extensions first reduce the candidate list to the current beam size before applying one or more pruning schemes.
- Relative Threshold Pruning: Relative threshold pruning discards candidates whose scores are far worse than the best active candidate.
- Absolute Threshold Pruning: Absolute threshold pruning discards candidates that are worse than the best active candidate by a specified threshold.
- Relative Local Threshold Pruning: Relative local threshold pruning compares only the score of the last generated word rather than the total hypothesis score.
- Maximum Candidates per Node: Maximum candidates per node limits how many better-scoring partial hypotheses can share the same history at each time step.
5 Experiments
Experiments evaluate pruning-based beam search for German→English and Chinese→English NMT, measuring decoding speed, fan out, translation quality, and search errors. Combined pruning preserves translation performance while substantially reducing decoding time.
- German→English pruning experiments use WMT 2016 data with 3.9M parallel sentences, while Chinese→English uses 11M BOLT sentences.
- The experiments use an in-house attention-based NMT implementation, with German→English subword vocabularies and Chinese→English frequency-limited word vocabularies.German→English uses 40k subword symbols for both languages; Chinese→English uses the top 300K words.
- Decoding speed is evaluated relative to an unpruned setup and by average fan out, the number of candidates expanded per time step.Fan out can decrease through early stopping or the proposed pruning schemes.
- 13% faster decoding for German→English at beam size 5 and 43% faster at beam size 14 without performance loss.The relative pruning technique worked best at beam size 5, while absolute pruning worked best at beam size 14.
- 10% faster decoding for Chinese→English at beam size 5 and 24% faster at beam size 14 without loss in translation quality.Search errors changed 4% of sentences at beam size 5 and 22% at beam size 14.
6 Conclusion
The conclusion presents pruning as a way to make NMT beam search more efficient without sacrificing translation quality. It reports speedups of up to 43%, while added decoder diversity did not improve translation quality.
- Combining absolute and relative pruning schemes speeds up the NMT decoder by up to 43% without losing translation quality.
- The original decoder explores a fixed number of left-to-right translation candidates, including candidates far below the best score.
- Adding more diversity to the decoder did not improve translation quality.
- Table 1 reports German→English results for relative pruning, absolute pruning, relative local pruning, and maximum candidates per node.Average fan out denotes the average number of candidates kept at each decoding time step.
- Table 2 reports Chinese→English results for relative pruning, absolute pruning, relative local pruning, and maximum candidates per node.