Implementationmedium~30 min
Objective
Complete the beam_search_decode function so it explores multiple hypotheses in parallel and returns the highest-scoring complete sequence.
Background
Greedy decoding always picks the single most likely next token, which can miss globally better sequences. Beam search keeps the top beam_width candidates at each step, exploring a wider search space. It's the standard decoding strategy for machine translation, summarization, and speech recognition. You'll implement beam search from scratch using a mock bigram language model, with proper end-token handling and candidate pruning.
Requirements
- 1.Initialize beams with the start token and log-probability 0.0
- 2.Expand each beam with all possible next tokens using mock_next_token_probs
- 3.Keep only the top beam_width candidates sorted by cumulative score
- 4.Handle end-of-sequence tokens by moving completed beams to a finished list
- 5.Return the best completed sequence (or best active beam if none finished)
Evaluation (100 points)
Beam initialization
Initialize with start token and log-prob 0.0
Beam expansion with next-token probs
Expand beams by computing next token probabilities
Top-k selection
Sort candidates by score and keep only beam_width best
End token handling
Detect <end> token and move finished beams to completed list
Returns valid sequence
Function returns a list of token IDs, not NotImplementedError