{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T07:19:43Z","timestamp":1780730383365,"version":"3.54.1"},"reference-count":44,"publisher":"MIT Press","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Transactions of the Association for Computational Linguistics"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:p>Decoding for many NLP tasks requires an effective heuristic algorithm for approximating exact search because the problem of searching the full output space is often intractable, or impractical in many settings. The default algorithm for this job is beam search\u2014a pruned version of breadth-first search. Quite surprisingly, beam search often returns better results than exact inference due to beneficial search bias for NLP tasks. In this work, we show that the standard implementation of beam search can be made up to 10x faster in practice. Our method assumes that the scoring function is monotonic in the sequence length, which allows us to safely prune hypotheses that cannot be in the final set of hypotheses early on. We devise effective monotonic approximations to popular nonmonontic scoring functions, including length normalization and mutual information decoding. Lastly, we propose a memory-reduced variant of best-first beam search, which has a similar beneficial search bias in terms of downstream performance, but runs in a fraction of the time.<\/jats:p>","DOI":"10.1162\/tacl_a_00346","type":"journal-article","created":{"date-parts":[[2020,12,22]],"date-time":"2020-12-22T19:56:37Z","timestamp":1608666997000},"page":"795-809","source":"Crossref","is-referenced-by-count":44,"title":["Best-First Beam Search"],"prefix":"10.1162","volume":"8","author":[{"given":"Clara","family":"Meister","sequence":"first","affiliation":[{"name":"ETH Z\u00fcrich."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tim","family":"Vieira","sequence":"additional","affiliation":[{"name":"Johns Hopkins University."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ryan","family":"Cotterell","sequence":"additional","affiliation":[{"name":"University of Cambridge"},{"name":"ETH Z\u00fcrich."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"281","reference":[{"issue":"10","key":"bib1","doi-asserted-by":"crossref","DOI":"10.1145\/6617.6621","volume":"29","author":"Atkinson M. D.","year":"1986","journal-title":"Communications of ACM"},{"key":"bib2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Bahdanau Dzmitry","year":"2015"},{"key":"bib3","volume-title":"Proceedings of the Conference on Machine Translation, Volume 2: Shared Task Papers","author":"Bojar Ond\u0159ej","year":"2017"},{"key":"bib4","volume-title":"Proceedings of the Conference of the European Association for Machine Translation","author":"Cettolo Mauro","year":"2012"},{"issue":"1","key":"bib5","volume":"1","author":"Dijkstra Edsger W.","year":"1959","journal-title":"Numerische Mathematik"},{"key":"bib6","unstructured":"Kevin Duh. 2018. The multitarget TED talks task.http:\/\/www.cs.jhu.edu\/tildekevinduh\/a\/multitarget-tedtalks\/"},{"key":"bib7","volume-title":"Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing","author":"Edunov Sergey","year":"2018"},{"key":"bib8","volume-title":"Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)","author":"Gehring Jonas","year":"2017"},{"issue":"2","key":"bib9","volume":"4","author":"Hart Peter E.","year":"1968","journal-title":"IEEE Transactions on Systems Science and Cybernetics"},{"key":"bib10","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","author":"He Wei","year":"2016"},{"key":"bib11","volume-title":"Advances in Neural Information Processing Systems","author":"Hermann Karl Moritz","year":"2015"},{"key":"bib12","volume-title":"Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing","author":"Huang Liang","year":"2017"},{"key":"bib13","volume-title":"Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)","author":"Huang Zhiheng","year":"2012"},{"key":"bib14","volume-title":"Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics","author":"Klein Dan","year":"2003"},{"key":"bib15","volume-title":"Proceedings of ACL 2017, System Demonstrations","author":"Klein Guillaume","year":"2017"},{"key":"bib16","volume-title":"Proceedings of the First Workshop on Neural Machine Translation","author":"Koehn Philipp","year":"2017"},{"issue":"01","key":"bib17","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Lafferty John D.","year":"2001"},{"key":"bib18","volume-title":"arXiv:1910. 13461","author":"Lewis Mike","year":"2019"},{"key":"bib19","volume-title":"Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies","author":"Li Jiwei","year":"2016"},{"key":"bib20","volume-title":"Text Summarization Branches Out","author":"Lin Chin-Yew","year":"2004"},{"key":"bib21","volume-title":"Proceedings of the International Conference on Machine Learning","author":"McCallum Andrew","year":"2000"},{"key":"bib22","volume-title":"Proceedings of the Third Conference on Machine Translation: Research Papers","author":"Murray Kenton","year":"2018"},{"key":"bib23","volume-title":"Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008)","author":"Nivre Joakim","year":"2008"},{"key":"bib24","volume-title":"Proceedings of NAACL-HLT: Demonstrations","author":"Ott Myle","year":"2019"},{"key":"bib25","volume-title":"Proceedings of the Annual Meeting on Association for Computational Linguistics","author":"Papineni Kishore","year":"2002"},{"key":"bib26","volume-title":"Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics","author":"Pauls Adam","year":"2009"},{"key":"bib27","volume-title":"Proceedings of the Conference on Machine Translation: Research Papers","author":"Post Matt","year":"2018"},{"key":"bib28","volume-title":"Proceedings of the Annual Meeting of the Association for Computational Linguistics","author":"Sennrich Rico","year":"2016"},{"key":"bib29","doi-asserted-by":"crossref","unstructured":"Iulian Serban, Tim Klinger, Gerald Tesauro, Kartik Talamadupula, Bowen Zhou, Yoshua Bengio, and Aaron Courville. 2017. Multiresolution recurrent neural networks: An application to dialogue response generation.","DOI":"10.1609\/aaai.v31i1.10984"},{"key":"bib30","volume-title":"Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)","author":"Shen Shiqi","year":"2016"},{"key":"bib31","volume-title":"Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)","author":"Shu Raphael","year":"2018"},{"key":"bib32","volume-title":"Proceedings of the Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)","author":"Stahlberg Felix","year":"2019"},{"key":"bib33","volume-title":"Advances in Neural Information Processing Systems","author":"Sutskever Ilya","year":"2014"},{"key":"bib34","volume-title":"Advances in Neural Information Processing Systems","author":"Taskar Ben","year":"2004"},{"key":"bib35","author":"Vaswani Ashish","year":"2018","journal-title":"CoRR"},{"key":"bib36","volume-title":"Advances in Neural Information Processing Systems","author":"Vaswani Ashish","year":"2017"},{"key":"bib37","volume-title":"Proceedings of the Conference on Empirical Methods in Natural Language Processing","author":"Vieira Tim","year":"2016"},{"key":"bib38","volume":"1610","author":"Vijayakumar Ashwin K.","year":"2016","journal-title":"CoRR"},{"key":"bib39","doi-asserted-by":"crossref","unstructured":"Oriol Vinyals and Quoc V. Le. 2015. A neural conversational model.DOI:\u00a0https:\/\/doi.org\/10.1109\/TIT.1967.1054010","DOI":"10.1109\/TIT.1967.1054010"},{"issue":"2","key":"bib40","volume":"13","author":"Viterbi Andrew","year":"1967","journal-title":"IEEE Transactions on Information Theory"},{"key":"bib41","unstructured":"Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V. Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin Johnson, Xiaobing Liu, Lukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, Nishant Patil, Wei Wang, Cliff Young, Jason Smith, Jason Riesa, Alex Rudnick, Oriol Vinyals, Gregory S. Corrado, Macduff Hughes, and Jeffrey Dean. 2016. Google\u2019s neural machine translation system: Bridging the gap between human and machine translation."},{"key":"bib42","volume-title":"Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing","author":"Yang Yilin","year":"2018"},{"key":"bib43","volume-title":"Advances in Neural Information Processing Systems","author":"Yang Zhilin","year":"2019"},{"key":"bib44","volume-title":"Proceedings of the International Conference on International Conference on Automated Planning and Scheduling","author":"Zhou Rong","year":"2005"}],"container-title":["Transactions of the Association for Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/tacl_a_00346","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,8]],"date-time":"2022-12-08T19:56:55Z","timestamp":1670529415000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/tacl\/article\/96473"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12]]},"references-count":44,"alternative-id":["10.1162\/tacl_a_00346"],"URL":"https:\/\/doi.org\/10.1162\/tacl_a_00346","relation":{},"ISSN":["2307-387X"],"issn-type":[{"value":"2307-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12]]}}}