Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for generating a target sequence from an input sequence. In one aspect, a method comprises maintaining a set of current hypotheses, wherein each current hypothesis comprises an input prefix and an output prefix. For each possible combination of input and output prefix length, the method extends any current hypothesis that could reach the possible combination to generate respective extended hypotheses for each such current hypothesis; determines a respective direct score for each extended hypothesis using a direct model; determines a first number of highest-scoring hypotheses according to the direct scores; rescores the first number of highest-scoring hypotheses using a noisy channel model to generate a reduced number of hypotheses; and adds the reduced number of hypotheses to the set of current hypotheses.