| 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. |
Similar Papers
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. |
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. |
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. |
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. |
Determinantal Beam Search (2021.acl-long)
Copied to clipboard
| Challenge: | a new beam search approach allows for a diverse subset selection process . standard beam search does not encode interactions between candidates . |
| Approach: | They propose a beam search reformulation that casts subset selection as the subdeterminant optimization problem. |
| Outcome: | The proposed method offers competitive performance against other diverse set generation strategies while providing a more general approach to optimizing for diversity. |
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. |
Incremental Beam Manipulation for Natural Language Generation (2021.eacl-main)
Copied to clipboard
| Challenge: | a larger beam size can lead to deteriorating performance of natural language generation systems due to model errors . performance of NLG systems can plateau or even decrease when beam sizes larger than 10 are used . |
| Approach: | They propose to rerank the output of beam search to produce a good set of hypotheses . they propose incremental beam manipulation to discarded hypothese . |
| Outcome: | The proposed method outperforms a strong reranker on the E2E and WebNLG datasets while being on par with the existing method. |
Best-k Search Algorithm for Neural Text Generation (2023.acl-long)
Copied to clipboard
| Challenge: | Modern natural language generation paradigms require a decoding strategy to obtain quality sequences out of the model. |
| Approach: | They propose a deterministic search algorithm balancing quality and diversity . they investigate the vanilla best-first search algorithm and propose k-k search algorithm. |
| Outcome: | The proposed algorithm is parameter-free, lightweight, efficient, and easy-to-use. |
A Stable and Effective Learning Strategy for Trainable Greedy Decoding (D18-1)
Copied to clipboard
| Challenge: | Existing methods for decoding text using beam search are expensive and require reinforcement learning. |
| Approach: | They propose a method that allows us to reap the full benefits of beam search with no additional computational cost. |
| Outcome: | The proposed method outperforms greedy decoding and beam search on machine translation tasks with minimal computational cost. |
A Streaming Approach For Efficient Batched Beam Search (2020.emnlp-main)
Copied to clipboard
| Challenge: | During decoding, candidates terminate or are pruned according to heuristics, a streaming method is used to "refill" the batch after it finishes translating some fraction of the current batch. |
| Approach: | They propose an efficient batching strategy for variable-length decoding on GPU architectures by streamlining the batching process. |
| Outcome: | The proposed method reduces runtime by 71% compared to a fixed-width beam search baseline and 17% compared with a variable-widness baseline while matching baselines’ BLEU. |