Methods and systems for beam search decoding. One of the methods includes initializing beam data specifying a set of k candidate output sequences and a respective total score for each of the candidate output sequences; updating the beam data at each of a plurality of decoding steps, comprising, at each decoding step: generating a score distribution that comprises a respective score for each token in the vocabulary; identifying a plurality of expanded sequences; generating, for each expanded sequence, a respective backwards-looking score; generating, for each expanded sequence, a respective forward-looking score; computing, for each expanded sequence, a respective total score from the respective forward-looking score for the expanded sequence and the respective backwards-looking score for the expanded sequence; and updating the set of k candidate output sequences using the respective total scores for the expanded sequences.