Beam Search Decoding
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), withTdecoding steps and vocabulary sizeV;log_probs[t][v]is the log-probability of tokenvat stept.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_widthsingle tokens by log-probability. - Each later step: extend every current beam with every token, then keep the top
beam_widthcandidates by cumulative score. - With
beam_width = 1this is greedy decoding. - If
top_kexceeds 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
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium