liveBook · Manning

Greedy algorithm

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

Greedy decoding is an autoregressive text-generation method that selects the highest-probability next token at each step without considering alternative continuations.

Greedy decoding generates autoregressive text by selecting the highest-probability next token for the current context, then repeating that choice until reaching a length limit or termination token. section 5.2.1 section 5.7

w_t = argmax_w P(w | w_1, w_2, ..., w_{t-1})

The selection rule chooses the token w with maximum conditional probability given all preceding tokens. section 5.2.1

Apply the procedure one token at a time:

  • Initialize the sequence with a prompt or first token. section 5.2.1
  • Predict the probability distribution for the next token from the current context. section 5.2.1
  • Select the highest-probability token and append it to the sequence. section 5.2.1
  • Repeat prediction and selection until the desired length or an end-of-sequence token is reached. section 5.2.1

Choosing the next word

Given “The cat sat on the...” and candidate probabilities for “jumps,” “runs,” and “walks,” greedy decoding appends whichever candidate has the highest probability, then predicts again from the expanded sentence. section 5.2.1

The method is computationally efficient and simple to implement because it follows only one path. That determinism can produce repetitive, monotonous text and prevents exploration of alternative continuations. section 5.2.1

Use greedy decoding when efficient, deterministic generation matters; compare it with beam search, top-k sampling, nucleus sampling, and temperature scaling when diversity or creativity matters. section 5.2 section 5.5

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

How deep it goes
Explains the selection loop, advantages, and limitations, but stops short of implementation code or model internals.
Examples
Demonstrates next-token selection with the fragment “The cat sat on the...” and candidate words such as “jumps,” “runs,” and “walks.”
What it assumes
Assumes familiarity with prompts, tokens, conditional probabilities, and autoregressive decoder models.
What you can do after
Apply greedy decoding to generate text one token at a time using maximum-probability selection and explicit stopping conditions.
How it connects
Contrasts with beam search, top-k sampling, nucleus sampling, and temperature scaling within decoder-model generation.

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 Build an Advanced RAG Application (From Scratch). The section links point to the parts of the book it draws on.