In this work we present two extensions to the well-known dynamic programming beam
search in phrase-based statistical machine translation (SMT), aiming at increased
efﬁ- ciency of decoding by minimizing the number of language model computations and
hypothesis expansions. Our results show that language model based pre-sorting
yields a small improvement in translation quality and a speedup by a factor of 2.
Two look-ahead methods are shown to further increase translation speed by a factor
of 2 without changing the search space and a factor of 4 with the side-effect of
some additional search errors. We compare our approach with Moses and observe the
same performance, but a substantially better trade-off between translation quality
and speed. At a speed of roughly 70 words per second, Moses reaches 17.2% BLEU,
whereas our approach yields 20.0% with identical models.