LLM Inference Interview Questions #21 - The Search Error Trap

You’re in a Senior ML Engineer interview at Google DeepMind and the interviewer asks:

“Your colleague says greedy decoding is a fine approximation of the most likely sequence, because we take the max at every step. Where does that argument break, and does beam search actually fix it?”

Don’t say: “Greedy is fine, beam search finds the highest-probability sequence.” Wrong on both halves. That answer tells the interviewer you’ve never debugged a decoder.

Here’s the reality.

Greedy decoding optimizes a local objective. Sequence likelihood is a global one. Those are not the same problem.

Walk the failure mode explicitly:

a) The split point. At step t, two tokens are nearly tied, say eats at 0.5 and sees at 0.4. Greedy commits to eats. Irreversibly.

b) The payoff is one step away. The eats branch has a flat continuation: best next token is 0.1. The sees branch has a peaked one: 0.9.

c) Do the multiplication. Greedy’s path: 0.5 × 0.1 = 0.05. The path it discarded: 0.4 × 0.9 = 0.36.

Greedy just returned a sequence 7x less likely, after two tokens. Stretch that across a 200-token generation and the gap is orders of magnitude. This is search error, not model error. Your model was right. Your decoder threw the answer away.

Now the part that gets you hired:

Beam search doesn’t eliminate this. It postpones it.

Width-K beam search still prunes to K hypotheses at every single step. The pruning is still local. The moment the true global optimum’s prefix ranks K+1 at any timestep, it’s evicted — permanently, with zero chance of recovery. You haven’t removed the greedy trap. You’ve moved it from rank 1 to rank K.

The only way to guarantee the true mode is exhaustive Viterbi-style decoding over |V|^T paths. Computationally absurd. Beam search is an approximation, not a solution.

Reducing search error often makes outputs worse. That’s the curse of beam search, crank the width up and downstream quality degrades, because you start surfacing degenerate modes (empty strings, repetition loops) that the search error was accidentally protecting you from.

The answer that gets you hired: Greedy decoding fails because local argmax ≠ global argmax at every branch point, and beam search only widens the window on that same local pruning, it never removes it.

#MachineLearning #LLM #AIEngineering #NLP #MLOps #DeepLearning #AIInterview