Beam Search

For an introduction, see Wikipedia - Beam Search.

• Beam search for RNNs: Rush et al 2015 - A Neural Attention Model for Abstractive Sentence Summarization This may be the first paper to use beam search in seq2seq models (as far as Jeff knows)
• Goyal et al 2017 - A Continuous Relaxation of Beam Search for End-to-end Training of Neural Sequence Models

Invented for decoding in speech recognition, beam search was the de-facto decoding algorithm for statistical machine translation and was also used for statistical parsing. Historical references are here:

• Speech Recognition
  • Jelinek 1969 - Fast Sequential Decoding Algorithm Using a Stack This is the standard stack-based beam search decoder, used extensively in statistical MT. Cited and used by Brown et al 1988 for MT. Didn't use the term beam search however.
• Machine translation, see Statistical Machine Translation
  • Och et al 2003 - Statistical Phrase-Based Translation
  • Khoen 2004 - Pharaoh: a beam search decoder for phrase-based statistical machine translation models

• Decoding
• Seq2seq