A Call for Clarity in Beam Search: How It Works and When It Stops (2024.lrec-main)
Copied to clipboard
| Challenge: | Empirical results show that a modified beam decoding implementation improves decoding performance of strong, neural language generation models. |
| Approach: | They propose a modification to a beam decoding implementation that generalizes the stopping criterion and provides flexibility to the depth of search. |
| Outcome: | The proposed method improves decoding performance of strong models on news text summarization and machine translation over diverse language pairs with negligible inference slowdown. |
Similar Papers
If beam search is the answer, what was the question? (2020.emnlp-main)
Copied to clipboard
| Challenge: | surprisingly, beam search results on language generation tasks are low-quality . despite its high error rate, beam searches can be used to decode models with high probability . |
| Approach: | They frame beam search as the exact solution to a different decoding objective . they propose a set of decoding objectives that explicitly enforce this property . |
| Outcome: | The proposed method enforces uniform information density in text, a property motivated by cognitive science. |
Speculative Beam Search for Simultaneous Translation (D19-1)
Copied to clipboard
| Challenge: | Beam search is widely used in (full-sentence) machine translation but its application to simultaneous translation remains highly non-trivial. |
| Approach: | They propose a beam search algorithm that hallucinates several steps into the future to reach a more accurate decision by implicitly benefiting from a target language model. |
| Outcome: | The proposed method improves on language models over diverse language pairs and shows significant improvements over greedy search. |
Machine Translation Decoding beyond Beam Search (2021.emnlp-main)
Copied to clipboard
Rémi Leblond, Jean-Baptiste Alayrac, Laurent Sifre, Miruna Pislar, Lespiau Jean-Baptiste, Ioannis Antonoglou, Karen Simonyan, Oriol Vinyals
| Challenge: | a new study examines whether beam search can be replaced by a more powerful metric-driven search technique. |
| Approach: | They propose a beam search method which is agnostic to the end metric and report results on a variety of metrics. |
| Outcome: | The proposed method is based on a Monte-Carlo Tree Search (MCTS) based method and shows it can be used in language applications. |
Best-First Beam Search (2020.tacl-1)
Copied to clipboard
| Challenge: | Currently, beam search is the default for decoding structured predictors . however, little work has been done to speed up beam search itself . |
| Approach: | They propose a beam search algorithm that prunes the scoring function to a monotonic sequence length, which allows for safe pruning of hypotheses that cannot be in the final set of hypothecies. |
| Outcome: | The proposed method can be implemented up to 10x faster in practice. |
Breaking the Beam Search Curse: A Study of (Re-)Scoring Methods and Stopping Criteria for Neural Machine Translation (D18-1)
Copied to clipboard
| Challenge: | Beam search is widely used in neural machine translation, but beam sizes larger than 5 hurt translation quality. |
| Approach: | They propose to use beam search to improve translation quality by using hyperparameter-free methods that outperform the widely-used heuristic of length normalization by +2.0 BLEU. |
| Outcome: | The proposed methods outperform the widely-used heuristic on Chinese-to-English translation and achieve the best results among all methods. |
Improving Beam Search by Removing Monotonic Constraint for Neural Machine Translation (P18-2)
Copied to clipboard
| Challenge: | a beam search algorithm produces monotonic left-to-right order, meaning a hypothesis cannot be revisited . a proposed algorithm allows discarded hypotheses to be recovered in a later step. |
| Approach: | They propose to decode a beam search algorithm that considers multiple hypotheses simultaneously . they propose to maintain all found hypothese a single priority queue and a universal score function . |
| Outcome: | The proposed algorithm improves translations even for high-performance models in English-Japanese translation task. |
On Decoding Strategies for Neural Text Generators (2022.tacl-1)
Copied to clipboard
| Challenge: | a recent study suggests that decoding strategies may be more important than the model architecture itself when generating text from probabilistic models. |
| Approach: | They propose to measure changes in attributes of generated text as a function of decoding strategy and task using human and automatic evaluation. |
| Outcome: | The proposed study shows that decoding strategies do not always transfer across tasks . authors show that the differences in attributes are not always consistent across tasks, they say . |
Learning to Stop in Structured Prediction for Neural Machine Translation (N19-1)
Copied to clipboard
| Challenge: | Beam search optimization solves many problems in neural machine translation, but lacks principled stopping criteria and does not learn how to stop during training. |
| Approach: | They propose a ranking method which enables an optimal beam search stop-ping criteria and a structured prediction loss function which penalizes suboptimal finished candidates produced by beam search during training. |
| Outcome: | Experiments on synthetic and real languages show that the proposed methods improve translation quality and length. |
Local Temperature Beam Search: Avoid Neural Text DeGeneration via Enhanced Calibration (2023.findings-acl)
Copied to clipboard
Dongkyu Lee, Gyeonghun Kim, Janghoon Han, Taesuk Hong, Yi-Reun Kim, Stanley Jungkyu Choi, Nevin L. Zhang
| Challenge: | Existing approaches to inference have been based on stochastic decoding but they sacrifice output quality due to randomness. |
| Approach: | They propose a deterministic decoding scheme, local temperature beam search, which reduces repetition while maintaining the level of coherence as in beam search. |
| Outcome: | The proposed inference scheme reduces repetition while maintaining coherence as in beam search. |
Efficient Beam Search for Large Language Models Using Trie-Based Decoding (2025.emnlp-main)
Copied to clipboard
| Challenge: | Large language models (LLMs) face memorybound performance bottlenecks due to their high memory requirements. |
| Approach: | They propose a trie-based parallel decoding method that shares a single KV cache across beams with common prefixes to dramatically reduce memory usage and enables efficient decoding. |
| Outcome: | The proposed method significantly reduces memory usage and enables efficient decoding without compromising generation quality. |