Machine Learning System Design Interview #25 - The Greedy Search Trap

The hidden failure mode behind greedy decoding and why minimal beam search fixes hallucinated factual answers.

You’re in a Senior ML Interview at OpenAI. The interviewer sets a trap:

“We need a low-latency geography trivia bot. Since the questions are factual, should we just use Greedy Search to save compute?”

90% of candidates walk right into the “Yes” trap.

They say “Yes. Greedy Search is O(N), extremely fast, and if the model is well-trained, taking the highest probability token at each step (argmax) should logically yield the most probable correct answer.”

This fails because they are confusing Local Optima with Global Optima.

Greedy decoding cannot backtrack. Once it commits to a token, it is locked in forever, even if that token leads to a dead end.

Consider the probabilities for the next token in the answer to: “Where is The Liberty Bell located?”

- P(”Pennsylvania”) = 0.4 (The correct answer)

- P(”New”) = 0.55 (The start of “New York” or “New Jersey”)