Improved systems, methods and apparatuses are provided for fast beam-search decoding for phrasal statistical machine translation. The provided techniques incorporate a front-loaded distortion penalty estimate for future estimated distortion penalty and/or early pruning to reduce the search space. The improvements result in up to an order of magnitude increase in translation speed for statistical machine translation systems. The disclosed details enable various refinements and modifications according to decoder and system design considerations.