Beam search
AlgoLab runs no language model. Every probability here was written by hand into a twelve-token toy table, which you can read in full in the Data tab.
Beam search picks a sequence one token at a time, but instead of committing to the single most likely token at each step it keeps the k best partial sequences — the beam — and extends all of them. Every extension is scored by adding the log-probability of the new token to the score of the sequence it extends, the candidates are ranked, and only the best k survive to the next step. After the last step the highest-scoring sequence in the beam is the answer.
When it is the right choice
It is the standard decoding strategy wherever a model produces a sequence and the whole sequence is what matters: machine translation, summarisation, speech recognition. It is worth the extra work exactly when a locally poor token opens onto a strong continuation, which greedy decoding can never reach because it has already thrown that branch away. It is the wrong choice when you want varied or surprising output — beam search is a search for the highest-probability sequence, and high-probability text is bland, repetitive text. Sampling methods exist for that reason, not as an inferior alternative.
How it works
- Start with one empty sequence, scoring zero.
- At each step, extend every sequence in the beam by every token that can follow it, taking each token's probability from the authored table.
- Score each extension by adding the natural logarithm of that probability to the score of the sequence it extends. Logarithms rather than a running product: a real decoder runs hundreds of steps, and a product of hundreds of probabilities underflows to zero long before it finishes. Ranking is unchanged either way, because the logarithm is monotonic.
- Rank the candidates by score, best first, breaking ties by the order they were created so a shared link reproduces the same run exactly.
- Keep the best k, discard the rest, and repeat. After the last step, the best sequence in the beam is the answer.
Worth noticing
- Beam search is not exhaustive and does not guarantee the best sequence. A prefix that scores badly early is pruned even if it leads somewhere excellent; widening the beam makes that less likely, never impossible. On this data a beam of two misses the best sequence and a beam of three finds it.
- Set the beam to one and it is greedy decoding, exactly — one sequence in, one candidate kept, no branch ever compared against another. That is not an analogy: it is the same procedure with k = 1, and a test in this repository asserts the two produce identical output.
- Widening the beam has sharply diminishing returns. Going from three to four changes nothing at all here, and a beam wider than the number of tokens that can follow any one context cannot prune anything at the first step.
- Scores get more negative with every step, because every log-probability is negative. Comparing sequences of different lengths therefore needs length normalisation — which does not arise here, since every sequence is exactly five tokens.
Where the numbers come from
The tool decodes over a table of next-token probabilities that a person typed in, held attools/beam-search/src/data/probability-tree.v1.json and shown in full in the tool’s Data tab. It has twelve nonsense tokens and thirteen rows — one for the start of a sequence and one for each token — with four possible successors each, every row summing to 1. Those thirteen rows describe a depth-five branching tree of 1,024 possible sequences, of which beam search ever builds at most sixty-nine.
Nothing about that is a limitation being hidden. Four probabilities can be read and checked; fifty thousand cannot. The reason this page can promise that its arithmetic is verifiable is the same reason it cannot promise to show you a real model.
Cost
- Time
- O(k · B · D)
- Extra space
- O(k · D)
- Widest beam
- 4
k is the beam width, B the number of tokens that can follow any one context — four here — and D the number of decoding steps, five. The widest beam is four because a beam wider than B cannot prune anything at the first step: there are only four candidates to choose from, so every setting past four would differ in nothing you could see.