Beam Search

Implement beam search decoding.

Given a log-probability matrix where log_probs[t][v] is the log-probability of token v at time step t, find the top-k highest-scoring sequences.

At each time step:

1. Expand each beam with all possible next tokens
2. Score each candidate: beam_score + log_probs[t][v]
3. Keep only the top beam_width candidates

Input:

• log_probs: shape (T, V) — log-probabilities at each time step
• beam_width: number of beams to keep (int)

Output: A dict with:

• “sequences”: the best sequence (list of token indices, length T)
• “score”: the log-probability score of the best sequence (scalar)