保留正文与补采附件。源页面当前未重新核验；具体限制见交付清单。

Revisit consent button We value your privacy We use cookies to enhance your browsing experience, serve personalised ads or content, and analyse our traffic. By clicking "Accept All", you consent to our use of cookies. Customise Reject All Accept All Customise Consent Preferences We use cookies to help you navigate efficiently and perform certain functions. You will find detailed information about all cookies under each consent category below. The cookies that are categorised as "Necessary" are stored on your browser as they are essential for enabling the basic functionalities of the site. ... Show more NecessaryAlways Active Necessary cookies are required to enable the basic features of this site, such as providing secure log-in or adjusting your consent preferences. These cookies do not store any personally identifiable data.

Functional Functional cookies help perform certain functionalities like sharing the content of the website on social media platforms, collecting feedback, and other third-party features.

Analytics Analytical cookies are used to understand how visitors interact with the website. These cookies help provide information on metrics such as the number of visitors, bounce rate, traffic source, etc.

Performance Performance cookies are used to understand and analyse the key performance indexes of the website which helps in delivering a better user experience for the visitors.

Advertisement Advertisement cookies are used to provide visitors with customised advertisements based on the pages you visited previously and to analyse the effectiveness of the ad campaigns.

Uncategorised Other uncategorised cookies are those that are being analysed and have not been classified into a category as yet. No cookies to display. Reject All Save My Preferences Accept All Toggle SearchToggle Mobile Navigation Publish AI, ML & data-science insights to a global community of data professionals. Sign inSubmit an Article LatestEditor's PicksNewsletterShipAI

Write For TDS LinkedInXToggle Search Artificial Intelligence

Beam Search: the Most Used Algorithm in Sequence Models

Learn the working principles of the most famous algorithm for text translation and speech recognition. Riccardo Andreoni December 13, 20236 min read Beam Search allows to consider multiple streams of candidates. Image source: unsplash.com. Beam Search allows to consider multiple streams of candidates. Image source: unsplash.com. Imagine you're an AI language model, like ChatGPT, completing a sentence. How do you choose the next word to make it not just grammatically correct but also contextually relevant? This is where Beam Search steps in. By efficiently exploring multiple possibilities in parallel and maintaining top candidates at each step, Beam Search plays a crucial role in the task of predicting subsequent elements. Being an effective and powerful algorithm, it ensures output aligns with grammatical constraints and the context. To understand Beam Search's impact, think about all the applications requiring precise sequence generation, like language translation , text completion , and chatbots. In all these applications, Beam Search plays a critical role. In this article, I will introduce the theory and guide you through a practical step-by-step example of the Beam Search algorithm. I will also present several Beam Search variants, and detail all the pros and cons of this fundamental algorithm. Learn this step by step with the interactive AI Engineer, Computer Science and Machine Learning roadmaps.

Understanding Beam Search

Imagine you need to translate the following sentence from Spanish to English:

Pablo estará en Nueva York la próxima semana. We don't only want to obtain a correct translation, we want to obtain the best one. For a language model, the best output coincides with the most probable one. To achieve this task, most sequence-to-sequence models employ Beam Search. It serves as an heuristic algorithm, systematically exploring multiple possibilities in parallel. At each step, a defined "beam width" maintains a fixed number of top candidates. This allows the algorithm to explore several candidates. This approach mimics decision-making processes, with the model evaluating and selecting the most promising options.

Beam Search Step-by-Step

Consider a standard sequence-to-sequence model, represented by the simple network below: Image by the author. Image by the author. At each timestep t , the model outputs a single word, used to compose the final sequence. The final sequence will be nothing other than the provided translated sentence. If you are not familiar with RNNs, I suggest to check the simple introduction I included in this article:

Use Deep Learning to Generate Fantasy Names: Build a Language Model from Scratch For text translation, we commonly use an encoder, which is a portion of the network dedicated to converting the input sequence into a vectorial form. In this case, the input sequence is the Spanish sentence to be translated. The encoder is followed by a decoder which, at each timestep, returns a piece of the output sequence. Image by the author. Image by the author. Let's check the first step out in detail. The encoder (green part) receives the Spanish sentence "Pablo estará en Nueva York la próxima semana. " and provides a vector form of it to the decoder (blue part). Image by the author. Image by the author. At timestep 1, the decoder will output the first word of the translation. The key question is: How does the decoder choose the word? The decoder chooses the most probable word, given the input sequence x. In other words, for each word in the dictionary, the model computes the corresponding probability to be the first word of the output sequence. The one word that maximizes this probability is chosen. Here is where Beam Search enters the game : it introduces a parameter B , called beam width , which represents the number of words chosen by the model at each step. By setting, for instance, B=3 , the model will return not only one but three candidate words. Let's suppose the most probable first words of the translation are "Pablo ", "Next ", and "During ". Image by the author. Image by the author. For each of these 3 candidate words, the model proceeds by guessing the second word y² in the English translation. Image by the author. Image by the author. As always, the model picks the words that maximize a given probability. In this case: You can clearly see the reason for the name Beam Search now. Starting from a narrow set of 3 candidates, the algorithm will enlarge it at each step, considering the probabilities of all these combinations. The output of step 2 consists of 9 candidate sequences: "Pablo will ", "Pablo is ", ..., "During next ", and "During one ". The model associates each one of them with a probability. By setting the parameter B=3 , the model will keep only the three candidate sequences with the higher probability. Suppose that the candidates with higher probabilities are "Pablo will ", "Pablo is ", and "Next week ". During the 3-rd step, the decoder will guess 3 subsequent word for each candidate. Image by the author. Image by the author. The same process is iterated all over again until the model predicts as the most likely word the End of Sentence token. The EOS token states that the sequence reached its end and it is now considered complete.

Beam Search Variants

Beam Search adaptability can be enhanced by several variants of the algorithm. They provide options that may be more or less adequate for diverse sequence generation tasks. The most common variants are:

Image source: unsplash.com. Image source: unsplash.com.

Conclusion

In summary, in this post we understood why Beam Search is the most used algorithm in the field of sequence generation, particularly in the context of language translation models, but also for chatbot responses. Its systematic exploration of multiple possibilities in parallel, guided by a defined beam width, enhances the precision and the contextualize of the generated sequences. I am confident that the step-by-step example I provided will make the abstract concept of Beam Search more concrete. As I always do in my posts, I will now recap some pros and cons of Beam Search. The main advantages of this algorithm are:

However, in Machine Learning there are no free meals. It is then important to clarify the drawbacks of each algorithm. In the case of Beam Search, I identified these possible issues:

Image by the author. Image by the author. Finally, I invite you to explore the provided resources to get a deeper understanding of this algorithm.

If you liked this story, consider following me to be notified of my upcoming projects and articles!

References

Register Now to Continue Reading

Unlock Towards Data Science with a Free Account

All articles on Towards Data Science are available to registered users. Create a free account today to access this article and thousands more. Register for freeSign in to your account

Written By

Riccardo Andreoni

See all from Riccardo Andreoni AlgorithmsArtificial IntelligenceMachine LearningProgrammingSequence Model Share This Article

Towards Data Science is a community publication. Submit your insights to reach our global audience and earn through the TDS Author Payment Program. Write for TDS

Related Articles

Pythonic Tips & Tricks - Working with Lambda

Programming How to apply the Lambda function in Python Tonichi Edeza February 9, 20213 min read

Ultimate Setup for Your Next Python Project

Programming Starting any project from scratch can be daunting task... But not if you have this ultimate Python project blueprint! Martin Heinz January 15, 20208 min read

Web-Based Database-Powered Chatbot Project - Module 1: Approximate String Matching

Artificial Intelligence A project spanning web programming, math, AI, and more. Luciano Abriata May 10, 202213 min read

31 Uniques Python Packages To Improve Your Data Workflow

Artificial Intelligence Various Python packages for data people Cornellius Wijaya July 26, 202217 min read

Kernel Case Study: Flash Attention

Machine Learning Understanding all versions of flash attention through a triton implementation Arunjith A April 3, 202514 min read

Efficient Machine Learning - Why You Should Think About the "Customer" in Your Algorithm

Artificial Intelligence It's easy to get caught up in building a lovely new machine learning algorithm. You see one network design, then another, and you keep... Kabir Nagrecha April 9, 20214 min read

Large Language Models: TinyBERT - Distilling BERT for NLP

Large Language Models Unlocking the power of Transformer distillation in LLMs Slava Efimov October 21, 20238 min read

Learn to use the seven most crucial python libraries for data science

Artificial Intelligence As a data scientist, these libraries will save your life while implementing ML/DL algorithms. Harsh Maheshwari November 25, 20215 min read

Shell Language Processing: Machine Learning for Security Intrusion Detection with Linux auditd

Machine Learning How-to guide with code samples for specialists willing to apply data science techniques for solving cyber-security problems. Dmitrijs Trizna September 22, 202211 min read

Your home for data science and AI. The world's leading publication for data science, data analytics, data engineering, machine learning, and artificial intelligence professionals. Subscribe to Our NewsletterWrite For TDS•About•Advertise•Privacy Policy•Terms of Use © Insight Media Group, LLC 2026•The New Stack•roadmap.sh•Creator Network

Recommended Articles

Close