Implement a function beam_search_decode that performs beam search decoding over a sequence of log-probability distributions.
In many sequence generation tasks (e.g., machine translation, text generation), we want to find high-scoring output sequences. Greedy decoding picks the best token at each step, but this can miss globally optimal sequences. Beam search maintains multiple candidate sequences ("beams") at each step to explore a wider search space.
Your Task:
Write a function beam_search_decode(log_probs, beam_width, top_k) that takes:
log_probs: A 2D numpy array of shape (T, V) where T is the number of decoding time steps and V is the vocabulary size. Each entry log_probs[t][v] is the log-probability of choosing token v at time step t.beam_width: An integer specifying how many candidate sequences to keep at each step.top_k: An integer specifying how many of the final sequences to return (default 1).The function should return a list of tuples (sequence, score), sorted by score in descending order (highest score first), where:
sequence is a list of integer token indices (one per time step)score is the cumulative log-probability of the sequence, rounded to 4 decimal placesNotes:
beam_width candidates by cumulative score.beam_width=1, beam search reduces to greedy decoding.top_k exceeds the number of available beams, return all available beams.