Faster Phrase-Based Decoding by Refining Feature State

We contribute a faster decoding algo-rithm for phrase-based machine transla-tion. Translation hypotheses keep track of state, such as context for the language model and coverage of words in the source sentence. Most features depend upon only part of the state, but traditional algorithms, including cube pruning, handle state atom-ically. For example, cube pruning will re-peatedly query the language model with hypotheses that differ only in source cov-erage, despite the fact that source cover-age is irrelevant to the language model. Our key contribution avoids this behav-ior by placing hypotheses into equivalence classes, masking the parts of state that matter least to the score. Moreover, we ex-ploit shared words in hypotheses to itera-tively refine language model scores rather than handling language model state atom-ically. Since our algorithm and cube prun-ing are both approximate, improvement can be used to increase speed or accuracy. When tuned to attain the same accuracy, our algorithm is 4.0–7.7 times as fast as the Moses decoder with cube pruning.