Since the efficiency of the beam search approach is based on restrictions on the allowed coverage vectors C alone, the approach may be used for different types of translation models as well (e.g., for the multiword-based translation model proposed in Och, Tillmann, and Ney [1999]).
since the decoding problem for the IBM-4 translation model is provably NP-complete, as shown in Knight (1999) and Germann et al.