liveBook · Manning

Greedy algorithm

As explained in Retrieval Augmented Generation, The Foundational Ideas

Greedy decoding generates a sequence by selecting the single most probable next token at each step.

Greedy decoding selects the single most probable next token at each step and commits to it. A locally probable choice can lead to a worse complete sequence. section 9.3.2

Beam search keeps several candidate continuations alive and chooses the highest-scoring sequence at the end. In Self-RAG, token-guided scoring further rewards continuations judged relevant, supported, and useful. section 9.3.2

How Retrieval Augmented Generation, The Foundational Ideas covers it

How deep it goes
Defines next-token selection and commitment, then contrasts this local choice with beam search's multi-candidate search.
Examples
Illustrates commitment through choosing the most probable next word and contrasts it with keeping the top-k continuations.
What you can do after
Evaluate/understand how greedy decoding commits to locally probable tokens, unlike beam search's retained alternatives.
How it connects
Contrasts with beam search and appears alongside Self-RAG's token-guided decoding.

Also explained in

Compare how 16 books explain greedy algorithm →

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.