liveBook · Manning

Beam search

As explained in Retrieval Augmented Generation, The Foundational Ideas

Beam search is a heuristic decoding algorithm that retains a fixed number of highest-scoring partial sequences at each step.

Beam search is a heuristic decoder that avoids greedy decoding's single-path commitment. At each step, it keeps the top k partial sequences, extends each by one token, prunes back to k candidates, and returns the highest-scoring completed sequence. section 9.3.2

In Self-RAG, beam search scores candidates by combining ordinary text probability with weighted probabilities for positive reflection tokens. Relevance, support, and usefulness can boost a continuation; self-identified lack of support can penalize and remove it. Runtime weights trade fluency against factual grounding without retraining. section 9.3.2

Beam width and retrieval design create practical trade-offs:

  • RAG-token uses one standard beam search while allowing different generated tokens to rely on different retrieved documents. section 4.3.3
  • RAG-sequence requires separate beam searches for documents and additional forward passes for hypotheses missing from a beam. section 4.3.3

When evidence is split across documents

For a response naming a city and a state, token-level decoding can use one passage for the city and another for the state. Sequence-level decoding commits to one passage for the complete answer, so token-level scoring can be substantially higher when evidence is distributed. section 4.3.3

Score(y)=log P(text) + T ∈IsRel, Is

Use the scoring equation to inspect how ordinary text likelihood and reflection-token likelihood combine into a beam-ranking score. section 9.3.2

How Retrieval Augmented Generation, The Foundational Ideas covers it

How deep it goes
Explains candidate expansion, pruning, scoring, and runtime weighting, but does not develop beam-search implementation code.
Examples
Uses a city-and-state evidence-splitting example and compares document-level and token-level beam-search workloads.
What it assumes
Assumes familiarity with greedy decoding, token probabilities, retrieved passages, and generated sequences.
What you can do after
Operate/configure decoding by selecting beam candidates and tuning reflection weights for fluency or factual grounding.
How it connects
Connects beam search to greedy decoding, Self-RAG, retrieval-augmented generation, RAG-token, and RAG-sequence.

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 Retrieval Augmented Generation, The Foundational Ideas. The section links point to the parts of the book it draws on.