Beam Search Decoding

MediumML Coding

Problem statement

Implement beam_search_decode(log_probs, beam_width, top_k), beam search over a sequence of per-step log-probability distributions.

In sequence generation (machine translation, text generation) we want high-scoring output sequences. Greedy decoding takes the best token at each step; beam search keeps several candidate sequences ("beams") at each step to search more widely.

Inputs

  • log_probs: numpy array of shape (T, V), with T decoding steps and vocabulary size V; log_probs[t][v] is the log-probability of token v at step t.
  • beam_width: how many candidate sequences to keep after each step.
  • top_k: how many final sequences to return (default 1).

Output

A list of (sequence, score) tuples sorted by score, highest first, where sequence is a list of token indices (one per step) and score is the cumulative log-probability rounded to 4 decimals.

Rules

  • Step 0: the initial beams are the top beam_width single tokens by log-probability.
  • Each later step: extend every current beam with every token, then keep the top beam_width candidates by cumulative score.
  • With beam_width = 1 this is greedy decoding.
  • If top_k exceeds the number of beams left at the end, return all of them.
  • Tests avoid ties in scores.

Example

Input:

log_probs = np.array([[-0.5, -1.0, -2.0], [-0.8, -0.3, -1.5]])
beam_width = 2, top_k = 1

Output:

[([0, 1], -0.8)]

Reasoning: step 0 keeps token 0 ($-0.5$) and token 1 ($-1.0$). Extending gives $[0,0] = -1.3$, $[0,1] = -0.8$, $[0,2] = -2.0$, $[1,0] = -1.8$, $[1,1] = -1.3$, $[1,2] = -2.5$. The top 2 are $[0,1]$ and one of the $-1.3$ candidates; the best is $[0, 1]$ with score $-0.8$.

Show hint

Instead of committing to one token per step, how many partial sequences could you keep alive, and how would you score them?

Relevant roles: LLM Engineer, ML Engineer, AI Engineer and Gen AI Engineer.

Related free problems