Implement Beam Search

Free with account Updated Nov 16, 2026 · 5 min read
On this page

    Problem statement

    Implement beam search decoding. You get a function next_log_probs(seq) that returns a dictionary of possible next tokens and their log probabilities given a sequence. Starting from a start token, return the highest-scoring complete sequence (ending in an end token) found with beam width W, within a maximum length, with optional length normalisation.

    A classic decoding question for ML and inference roles; it checks search, bookkeeping and the classic length-bias trap.

    Example

    Example probabilities. Greedy commits to "the" and ends with 0.20; beam search keeps "a" alive and finds 0.36.
    Example probabilities. Greedy commits to "the" and ends with 0.20; beam search keeps "a" alive and finds 0.36.
    greedy        → <s> the </s>       p = 0.5 × 0.4       = 0.20
    beam (W = 2)  → <s> a cat </s>     p = 0.4 × 0.9 × 1.0 = 0.36

    Constraints (assumed)

    • W from 1 to about 10; vocabulary given as a dictionary per step (in a real model, a vector of size V).
    • Maximum length up to a few hundred tokens.
    • Pure Python for the interview version.

    What this question tests

    • Search bookkeeping: expanding, pruning, finished vs active beams.
    • Log-space arithmetic to avoid underflow.
    • Knowing the length bias and how to normalise.
    • Comparing with greedy and sampling, and knowing when beam search is the wrong tool.

    Questions to ask first

    1. Should finished sequences stay in the beam or move aside? (Move aside.)
    2. Length normalisation: yes, and which formula? (log p / length^α, α configurable.)
    3. What if no beam finishes before max length? (Return the best unfinished one.)
    4. Is the next-token function batched? (No, one sequence per call here.)
    5. Any constraints such as no repeated n-grams? (Not here; a follow-up.)