Answers.Body: <p>Here is Guillaume Klein's answer at <a href="https://github.com/guillaumekln/faster-whisper/issues/392#issuecomment-1660568838" rel="nofollow noreferrer">the issue section of the Git repository</a>:</p>
  <p>  <a href="https://en.wikipedia.org/wiki/Beam_search" rel="nofollow noreferrer">&quot;Beam Search&quot; in Wikipedia</a>:<br />
    Additionally, the beam size/beam width is controlling the number of paths that are explored at each step when generating an output.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-08-08T18:12:57.583Z
Answers.LastActivityDate: 2023-08-08T18:12:57.583Z
Answers.UserDisplayName: Cloud Cho
Answers.Body: <h3>Beam search</h3>
  <p>The <strong>beam search</strong> is a algorithm to find probable output sequences for an input sequence, so it has been used for <em>decoding</em> in the context of sequence-to-sequence tasks, like machine translation. It's an alternative to a <strong>greedy search</strong>, which just samples the most likely token at every step (which is not guaranteed to find the most likely sequence, though), that can keep a set of solutions.</p>
  <p>I think I first encountered this algorithm a few years ago while reading <a href="https://arxiv.org/pdf/1409.0473.pdf" rel="nofollow noreferrer">this important paper</a>, which refers to <a href="https://arxiv.org/pdf/1211.3711.pdf" rel="nofollow noreferrer">this Alex Graves' paper</a>, which actually contains a description and the pseudocode of a beam search, but I had forgotten about it, so I decided to review it :)</p>
  <p>A good description can be found <a href="https://arxiv.org/pdf/1703.01619.pdf" rel="nofollow noreferrer">here</a> (section 7.2.3) or <a href="https://d2l.ai/chapter_recurrent-modern/beam-search.html#id1" rel="nofollow noreferrer">here</a>.</p>
  <p>If you're familiar with search algorithms like breadth-first search (BFS), think of beam search as a similar search algorithm, where nodes are the tokens from some vocabulary and the edges are the probabilities of selecting a certain token given the previously selected tokens (important!). In fact, it can be viewed as a generalization of BFS (exhaustive search) - if you set the beam size equal to the vocabulary size, you get BFS.</p>
  <p>The following image (taken from <a href="https://d2l.ai/chapter_recurrent-modern/beam-search.html#id1" rel="nofollow noreferrer">here</a>, which provides a nice explanation) should give you the intuition</p>
  <p><a href="https://d2l.ai/chapter_recurrent-modern/beam-search.html#id1" rel="nofollow noreferrer"><img src="https://i.sstatic.net/9kPSV.png" alt="enter image description here" /></a></p>
  <h3>What is a beam? Just a guess</h3>
  <p>Now, I don't know the origin of the term <strong>beam</strong> in this context or why it's called <em>beam search</em>. In some papers I've come across (<a href="https://www.eecs.qmul.ac.uk/%7Esimond/pub/2015/SigtiaBoulanger-LewandowskiDixon-ISMIR2015-Chord.pdf" rel="nofollow noreferrer">example</a>), the beam acts like an object that has properties like the size (beam size).</p>
  <p>However, it could refer to the paths or the polygon formed by the external nodes at each layer from the first to the last, which is kind of similar to or could remind us of a light beam (image taken from <a href="http://saladgamer.com/vlb-doc/comp-effect-pulse/" rel="nofollow noreferrer">here</a>).</p>
  <p><a href="https://i.sstatic.net/9rJxh.gif" rel="nofollow noreferrer"><img src="https://i.sstatic.net/9rJxh.gif" alt="enter image description here" /></a></p>
  <p>The terminology is not very important, unless you're only interested in the history of the algorithm, which I assume not</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-08-08T03:49:50.040Z
Answers.Text: So the "beam" is the path through this search tree?
Answers.UserDisplayName: Geremia
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-08-08T08:54:03.087Z
Answers.Text: @Geremia That's one possibility, but I am not 100% sure. Like I wrote, I found the term "beam" alone only in a couple of papers and both of them seem to use it as an abstraction that contains the parameters of the beam search. If we consider the meaning of "beam size/width" (which is the number of nodes we consider at each layer), then the "beam" could also refer to _all paths down the search graph/tree_, which, together, form kind of a beam - the term may originate from the term _light beam_. This is just a guess but it kind of makes sense.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-08-08T00:59:24.467Z
Answers.LastActivityDate: 2023-08-08T14:25:24.700Z
Answers.LastEditDate: 2023-08-08T14:25:24.700Z
Answers.UserDisplayName: nbro
Body: <p>For example, <a href="https://github.com/guillaumekln/faster-whisper#usage" rel="nofollow noreferrer">faster-whisper</a>'s <code>transcribe</code> function takes an argument</p>
  <pre><code>beam_size: Beam size to use for decoding.
  </code></pre>
  <p>What does &quot;beam&quot; mean?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-08-05T19:18:57.587Z
Comments.Text: https://en.wikipedia.org/wiki/Beam_search
Comments.UserDisplayName: David Hoelzer
Tags: <terminology><speech-recognition><inference>
Title: What is a beam?
UserDisplayName: Geremia
ThreadText: # What is a beam?
  
  (Asked by: username_0 on 2023-08-05)
  
  For example, [faster-whisper](https://github.com/guillaumekln/faster-whisper#usage)'s `transcribe` function takes an argument
  
  ```
  beam_size: Beam size to use for decoding.
  
  ```
  
  What does "beam" mean?
  
  **Tags:** terminology, speech-recognition, inference
  
  > **Comments:**
  > **username_1**: https://en.wikipedia.org/wiki/Beam_search  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2023-08-08. Score: 4 | Accepted answer
  
  ### Beam search
  
  The **beam search** is a algorithm to find probable output sequences for an input sequence, so it has been used for *decoding* in the context of sequence-to-sequence tasks, like machine translation. It's an alternative to a **greedy search**, which just samples the most likely token at every step (which is not guaranteed to find the most likely sequence, though), that can keep a set of solutions.
  
  I think I first encountered this algorithm a few years ago while reading [this important paper](https://arxiv.org/pdf/1409.0473.pdf), which refers to [this Alex Graves' paper](https://arxiv.org/pdf/1211.3711.pdf), which actually contains a description and the pseudocode of a beam search, but I had forgotten about it, so I decided to review it :)
  
  A good description can be found [here](https://arxiv.org/pdf/1703.01619.pdf) (section 7.2.3) or [here](https://d2l.ai/chapter_recurrent-modern/beam-search.html#id1).
  
  If you're familiar with search algorithms like breadth-first search (BFS), think of beam search as a similar search algorithm, where nodes are the tokens from some vocabulary and the edges are the probabilities of selecting a certain token given the previously selected tokens (important!). In fact, it can be viewed as a generalization of BFS (exhaustive search) - if you set the beam size equal to the vocabulary size, you get BFS.
  
  The following image (taken from [here](https://d2l.ai/chapter_recurrent-modern/beam-search.html#id1), which provides a nice explanation) should give you the intuition
  
  [![enter image description here](https://i.sstatic.net/9kPSV.png)](https://d2l.ai/chapter_recurrent-modern/beam-search.html#id1)
  
  ### What is a beam? Just a guess
  
  Now, I don't know the origin of the term **beam** in this context or why it's called *beam search*. In some papers I've come across ([example](https://www.eecs.qmul.ac.uk/%7Esimond/pub/2015/SigtiaBoulanger-LewandowskiDixon-ISMIR2015-Chord.pdf)), the beam acts like an object that has properties like the size (beam size).
  
  However, it could refer to the paths or the polygon formed by the external nodes at each layer from the first to the last, which is kind of similar to or could remind us of a light beam (image taken from [here](http://saladgamer.com/vlb-doc/comp-effect-pulse/)).
  
  [![enter image description here](https://i.sstatic.net/9rJxh.gif)](https://i.sstatic.net/9rJxh.gif)
  
  The terminology is not very important, unless you're only interested in the history of the algorithm, which I assume not
  
  > **Comments:**
  > **username_0**: So the "beam" is the path through this search tree?  
  > **username_3**: @username_0 That's one possibility, but I am not 100% sure. Like I wrote, I found the term "beam" alone only in a couple of papers and both of them seem to use it as an abstraction that contains the parameters of the beam search. If we consider the meaning of "beam size/width" (which is the number of nodes we consider at each layer), then the "beam" could also refer to _all paths down the search graph/tree_, which, together, form kind of a beam - the term may originate from the term _light beam_. This is just a guess but it kind of makes sense.  
  
  ---
  
  ### Answer by username_2 on 2023-08-08. Score: 1
  
  Here is Guillaume Klein's answer at [the issue section of the Git repository](https://github.com/guillaumekln/faster-whisper/issues/392#issuecomment-1660568838):
  
  ["Beam Search" in Wikipedia](https://en.wikipedia.org/wiki/Beam_search):  
    Additionally, the beam size/beam width is controlling the number of paths that are explored at each step when generating an output.
  
  
  ---
  
  