Beam search

As explained in Natural Language Processing in Action, Second Edition

Beam search generates sequences by retaining a limited set of high-scoring partial paths and expanding them over multiple decoding steps.

Beam search improves generative language-model decoding by keeping several promising token paths instead of committing to one choice at every step. It selects the sequence with the highest total probability after exploring the available paths. section 10.2.1

The method controls search in two dimensions:

• Breadth limits how many beams or partial paths remain active. section 10.2.1
• Depth limits how many tokens each path can generate. section 10.2.1
• Recursive expansion after each token creates a receding-horizon process with a predictable time bound, avoiding the exponential growth of unrestricted sequences. section 10.2.1

A road-trip plan

Imagine choosing a road-trip route while keeping several promising routes alive. Slow traffic resembles a low-probability token; beam search delays commitment so the final route can have the best overall score. section 10.2.1

Figure 10.3 A beam search decision tree

A decision-tree figure makes the retained beams and their successive expansions visible. section 10.2.1

How Natural Language Processing in Action, Second Edition covers it

How deep it goes

Explains retained paths, cumulative probability, breadth, depth, and recursive expansion, but does not provide beam-search implementation code.

Examples

Uses a road-trip analogy and a decision-tree figure showing two possible beams.

What you can do after

Apply beam search to bound generative decoding while retaining multiple candidate token sequences.

How it connects

Connects beam search with greedy search, sampling, token decoding, probability, and generative language models.

liveBookmanning.com

Read Natural Language Processing in Action, Second Edition on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Transformers in ActionBeam search is a decoding algorithm that maintains a fixed number of highest-probability partial token sequences and expands each sequence at every step.
• 

  liveBookmanning.com
  Optimization Algorithms: AI techniques for design, planning, and control problemsAn informed search technique that retains only a limited number of the most promising partial solutions at each step.
• 

  liveBookmanning.com
  Deep Learning with Python, Third EditionA decoding method that keeps a fixed number of candidate generation paths and expands them step by step.
• 

  liveBookmanning.com
  Sutskever's ListBeam search is a sequence-decoding algorithm that retains a fixed-size set of high-scoring partial candidates at each expansion step.

Compare how 5 books explain beam search →

Related concepts

• greedy algorithmalternative to · A greedy algorithm builds a solution incrementally by choosing the locally best available option at each step, without generally accounting for all future consequences or revising prior choices.
• informed searchkind of · Informed search is a search strategy that uses problem-specific knowledge or heuristic estimates to prioritize promising states or paths.
• decoding strategykind of · A decoding strategy is a procedure for selecting successive tokens from a model’s output distribution to generate an output sequence.

This explainer was generated by Manning's knowledge graph from the text of Natural Language Processing in Action, Second Edition. The section links point to the parts of the book it draws on.