Beam Search Interview Questions: Length Bias, Repeated Tokens, and Search Errors

Beam search interview questions become difficult when the interviewer asks why the decoder returned a worse sentence after you increased the beam width. The answer is not automatically a pruning bug. A wider search can better optimize a probability objective that prefers short, repetitive, or otherwise unhelpful output.

For software and machine-learning candidates, the useful distinction is search error versus objective error. First specify the sequence score, finished-candidate policy, length convention, and stopping rule. Then trace whether a desirable candidate was discarded or merely scored below an undesirable one. These are different problems with different repairs.

The worked examples below are original teaching fixtures, not employer scoring rules or measurements of a deployed language model.

Beam search interview questions: define the contract first

Beam search is a bounded search procedure that retains several promising partial sequences instead of only one. At each step it expands the current frontier, scores the resulting candidates, and keeps a limited number. The beam width bounds that frontier; it does not prove global optimality.

An interview-ready definition also states what “promising” means. In the baseline exercise, the score is the sum of generated-token log probabilities, including the end-of-sequence token, or EOS. Higher is better: minus one outranks minus two. Prompt tokens are not rescored. A generated-length cap excludes the prompt in our discussion unless an exercise explicitly defines total length.

This matters when moving from a toy function to a library. Hugging Face documents separate controls for generated length, beam width, length penalty, and early stopping; these controls are not interchangeable. Check the exact installed version and configuration instead of treating a familiar parameter name as the whole algorithm. Transformers generation reference

Ask whether finished candidates share beam slots with live prefixes or are held separately. Ask how ties are broken and what happens if no valid token remains. Neither choice is universal. A correct implementation must match the specified contract, and a test must state which contract it expects.

Trace global pruning, not per-prefix winners

Consider this original finite probability tree. The start distribution assigns A probability 0.6 and B probability 0.4. After A, x and EOS each have probability 0.5. After B, y has probability 0.99 and EOS has probability 0.01. After x or y, EOS has probability one.

Each distribution sums to one, so the numbers can support probability reasoning rather than being arbitrary unnormalized scores. There are no other outgoing tokens. For this trace, finished sequences remain eligible in the shared frontier, and ties use lexicographic token order with EOS first.

Step	Candidates and decision
First expansion	A: 0.6; B: 0.4. Width one retains A; width two retains both.
Second expansion, width two	A x: 0.30; A EOS: 0.30; B y: 0.396; B EOS: 0.004. Keep B y and A EOS under the tie rule.
Third expansion	B y EOS: 0.396; A EOS remains 0.30. Return B y EOS.

Greedy decoding chooses A, then EOS under the specified tie rule, producing probability 0.30. Width two preserves B long enough to find the better complete sequence, probability 0.396. The log scores are approximately minus 1.204 and minus 0.926 respectively.

The important implementation detail is the single global candidate pool. Keeping two children per parent is not the same as keeping the best two candidates overall. If one parent produces both best continuations, it may legitimately occupy both slots. Conversely, a weak parent should not retain a reserved slot merely because it existed in the previous step.

Explain this trace without saying that beam search “looks ahead at every possibility.” It explores a bounded subset. A pruned prefix cannot reappear unless the algorithm includes some separate recovery mechanism. Keeping a larger beam reduces some pruning risks but does not remove the bound.

Why raw sequence scores favor shorter outputs

Every additional conditional probability is at most one. Multiplying by it cannot increase a path's raw probability; adding its nonpositive logarithm cannot increase the raw log score. This is a property of extending a particular prefix, not proof that every shorter sentence outranks every longer sentence.

For an original score-comparison exercise, suppose a completed one-token sequence, counting EOS, has log score minus 1.2. A completed four-token sequence has log score minus 2.4. The raw objective picks the shorter candidate because minus 1.2 is larger.

Now define a different objective explicitly: score divided by generated length to the power alpha, with alpha equal to one. The short candidate stays at minus 1.2; the longer candidate becomes minus 0.6 and wins. Its raw probability did not improve. We changed how candidates are ranked.

Do not call this a universal correction. Length normalization can prefer overly long continuations, and its effect depends on the model and task. Establish whether length includes EOS, excludes the prompt, or uses some other offset before calculating. Two implementations with identical log scores can disagree because their denominators differ.

Research on neural machine translation makes this distinction concrete: Yang, Huang, and Ma examined rescoring and stopping criteria when wider beams hurt translation quality. That is task-specific evidence for checking the objective, not a universal recommendation for one beam width or penalty setting. Breaking the Beam Search Curse

Separate a search failure from a model failure

A search failure means the decoder missed a better candidate under its declared objective. An objective or model failure means the preferred candidate under that objective is undesirable for the task. “The sentence looks worse” does not establish which failure occurred.

Use a tiny bounded vocabulary and maximum length so you can enumerate every complete sequence. Compare the beam output against exhaustive search using the same EOS, cap, and score rules. If exhaustive search finds a higher-scoring sequence, you have demonstrated a search error. If both select the same poor sequence, search is doing what the objective requests.

Stahlberg and Byrne used exact inference to distinguish search errors from model errors in an NMT setting. Their findings concerned particular models and a particular translation test set; they do not establish how every modern chat model behaves. The interview lesson is the diagnostic separation, not a transferable failure percentage. On NMT Search Errors and Model Errors

For a production answer, name the evaluation criterion too. Probability, factual correctness, translation adequacy, and latency are different measurements. A decoder can improve the first while worsening another. Keep the model, prompt, processor settings, and length budget fixed while examining the change; otherwise you cannot attribute the difference to beam width alone.

Repeated tokens are not a missing-beams problem

Suppose the model gives a repeated continuation a high conditional probability each time. Retaining several prefixes does not forbid that continuation. Multiple beams may contain different prefixes that converge toward similarly repetitive output.

Consider the generated tokens red blue red blue. With a no-repeat bigram constraint, appending red would create the already-seen bigram blue red, so that extension is blocked. Appending a different token may remain legal. This is a sequence-history constraint, not a second search frontier.

Such constraints can also block legitimate repeated names, quotations, or structured output. Test a repeated phrase that should be prevented and a repeated phrase the task requires. “Less repetition” is not sufficient evidence if the decoder now corrupts valid output.

Distinguish masking, penalties, and sampling. Masking removes a token from eligibility. A penalty adjusts preference. Sampling chooses probabilistically from a distribution. Top-k sampling truncates next-token choices; beam width limits retained sequence hypotheses. Neither parameter can be substituted for the other simply because both use the letter k. Transformers generation strategies

If all extensions are blocked, the algorithm needs a declared outcome: stop with a constraint failure, return a partial result, or apply an explicitly allowed fallback. Silently removing constraints changes the contract. Keep both raw model score and processed search score when debugging, so the effect of a processor is observable.

EOS and early stopping need a proof boundary

EOS ends a particular hypothesis, not necessarily the entire search. A completed candidate should not continue generating ordinary tokens. Its score must not accumulate an EOS transition repeatedly on later iterations.

For raw nonpositive log probabilities, a live prefix's current score is an upper bound on all its continuations. If the best finished score is minus 1.1 and every retained live prefix scores at most minus 1.2, none of those prefixes can beat the finished candidate. That supports stopping relative to the retained search frontier, not recovering candidates already pruned.

Length-normalized scores break that simple argument. A live prefix at score minus 1.2 and length one could finish at length four without further score loss in a synthetic deterministic continuation. Its normalized score would be minus 0.3, better than a one-token finished score of minus 1.1. A bound must incorporate the length cap and exact normalization rule.

Likewise, a positive token reward changes the bound. You cannot keep the old stopping proof after changing the objective. Tell the interviewer which assumptions make the proof valid, then identify the modification that invalidates them.

Keep completion reason in the result. EOS completion, maximum-length truncation, and a dead end are not equivalent. A partial string at the length cap may be acceptable in a teaching exercise, but a caller generating a structured document needs to know it was truncated.

Tests that expose implementation errors

A practical test suite starts with the normalized tree above, then changes one rule at a time. Test width one against greedy under identical policies, a tie across different parents, and a finished candidate that survives another step. Include an empty initial prefix and a nonempty prompt that is not included in the generated score.

Test the cap at zero generated tokens and at exactly the EOS boundary. Test a vocabulary in which all ordinary tokens are disallowed, and reject NaN scores rather than allowing an unstable sort to select arbitrary candidates. Negative infinity may represent an impossible token; it should not accidentally become a valid fallback.

For a model with cached decoding, preserve the parent-to-child relationship when reordering beams. Reusing a cache from the wrong parent makes the subsequent probabilities belong to a different prefix. The resulting output may look like a scoring bug even though the actual defect is state association.

Discuss costs in terms of beam width B, vocabulary size V, and generated steps T. There can be roughly B times V candidate extensions per step, but neural-model inference, selection, sequence copying, and cache storage have separate costs. Do not present that candidate count as an end-to-end latency benchmark.

Practice the mechanics and the follow-ups

Some records may require Premium for full explanations; the original examples in this article remain usable independently.

Question	What to defend after solving
Implement greedy decoding and beam search	Global top-k selection and finished-beam handling.
Greedy and Top-k Beam Search Decoding That Returns the Sentence Probability	Log-space accumulation and the probability returned to the caller.
Implement Beam Search With Length Normalization	A precisely defined length denominator and changed stopping bound.
Design sequence decoding with greedy and beam search	Quality versus cost without claiming universal optimality.
Implement greedy and beam decoding	Deterministic traces before applying repetition controls.

The answer to carry into the interview

For beam search interview questions, explain what is retained, how complete sequences are ranked, and when unfinished work can safely stop. Then classify a poor answer before proposing a repair: recover a discarded path for search error, or reconsider the objective for an undesirable high-scoring result.

Start with the length-normalization exercise, write down two candidates whose ranking changes, and derive the new stopping condition. That follow-up demonstrates more judgment than increasing the beam width until the example passes.

Sources and Further Reading

• Hugging Face Transformers 5.17.0 generation configuration
• Hugging Face Transformers generation strategies
• Yang, Huang, and Ma: Breaking the Beam Search Curse
• Stahlberg and Byrne: On NMT Search Errors and Model Errors

Research checked October 3, 2026. Probability trees, score comparisons, and constraint examples are original fixtures; no production-model quality or latency benchmark is claimed.