If Beam Search Is the Answer, What Was the Question?
By Clara Meister, Tim Vieira, Ryan Cotterell. 2020
176 citations recorded by the source corpus.
Quite surprisingly, exact maximum a posteriori (MAP) decoding of neural language generators frequently leads to low-quality results. Rather, most state-of-the-art results on language generation tasks are attained using beam search despite its overwhelmingly high search error rate. This implies that the MAP objective alone does not express the properties we desire in text, which merits the question: if beam search is the answer, what was the question? We frame beam search as the exact solution to a different decoding objective in order to gain insights into why high probability under a model alone may not indicate adequacy. We find that beam search enforces uniform information density in text, a property motivated by cognitive science. We suggest a set of decoding objectives that explicitly enforce this property and find that exact decoding with these objectives alleviates the problems encountered when decoding poorly calibrated language generation models. Additionally, we analyze the text produced using various decoding strategies and see that, in our neural machine translation experiments, the extent to which this property is adhered to strongly correlates with BLEU.
Subfields: Artificial Intelligence, Natural Language Processing, Machine Translation
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Sergey Levine
- Michael Janner
- Qiyang Li
- Ilya Kostrikov
- Mengjiao Yang
- Ryan Cotterell
- Pieter Abbeel
- Chelsea Finn
In Natural Language Processing
- Sergey Levine
- Michael Janner
- Qiyang Li
- Tiago Pimentel
- Charles Burton Snell
- Clara Meister
- Ryan Cotterell
- Ilya Kostrikov
In Machine Translation
Citations in the corpus
- Offline Reinforcement Learning as One Big Sequence Modeling Problem (2021, methodology): “Following the presentation in Meister et al. (2020), we have overloaded log P θ ( · | x ) to define the likelihood of a set of sequences in addition to that of a single sequence: log P θ ( Y | x ) = y ∈ Y log P θ ( y | x ) .”
- Typical Decoding for Natural Language Generation (2022, methodology): “Further, the UID hypothesis has been used as rationale for the effectiveness of beam search in the context of machine translation (Meister et al., 2020b).”
- A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions (2023, unknown): “The rationale for incorporating randomness into decoding strategies stems from the realization that high likelihood sequences often result in surprisingly low-quality text, which is called likelihood trap (Stahlberg and Byrne, 2019; Holtzman et al., 2020; Meister et al., 2020; Zhang et al., 2021).”
- Offline RL for Natural Language Generation with Implicit Language Q Learning (2022, background): “Much prior work on steering language models towards desired behavior has done so without an explicit utility function, instead either carefully curating finetuning datasets [32, 33, 34], or designing subtle decoding heuristics [35, 36, 37, 38, 39, 40, 41, 42].”