liveBook · Manning

Beam search

As explained in Build an Advanced RAG Application (From Scratch)

Beam search is a sequence-decoding method that maintains multiple high-scoring partial hypotheses and expands them to find a strong overall sequence.

Beam search is a sequence-decoding method that explores several partial token sequences, expands them, and retains only the highest-scoring candidates. section 5.2.2

A beam-search loop follows four practical steps:

  • Initialize the beam with the k most likely starting tokens. section 5.2.2
  • Expand every candidate by appending its k most probable next tokens. section 5.2.2
  • Score each expanded sequence using its cumulative probability and keep the top k. section 5.2.2
  • Stop when the maximum length is reached or every candidate emits an end-of-sequence token. section 5.2.2

Beam width two

To generate “the quick brown fox,” begin with “the” and “a.” Expand them to “the quick,” “the cat,” “a dog,” and “a cat,” then retain the two highest-scoring sequences. Expand those again, for example producing “the quick brown” and “the cat sat,” and continue until termination. section 5.2.2

Figure 5.4 Beam search starting with two candidates, “the” and “a.” Two candidate sequences are highlighted, each with a calculated cumulative probability based on the probabilities of the individual words within the sequence.

Use the candidate-sequence figure to inspect how two starting hypotheses receive cumulative-probability scores during search. section 5.2.2

How Build an Advanced RAG Application (From Scratch) covers it

How deep it goes
Explains initialization, expansion, cumulative scoring, selection, and termination, but does not descend into model implementation internals.
Examples
Demonstrates two-token beam width through the expanding candidates “the quick brown” and “the cat sat.”
What it assumes
Assumes familiarity with decoder models producing next-token probabilities and introduces the search procedure from candidate initialization onward.
What you can do after
Apply beam search to generate sequences by expanding, scoring, pruning, and terminating candidate hypotheses.
How it connects
Connects autoregressive language models with greedy decoding, sampling methods, and decoder-model text generation.

Also explained in

Compare how 7 books explain beam search →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Build an Advanced RAG Application (From Scratch). The section links point to the parts of the book it draws on.