Implement one decoding step of beam search for autoregressive language models. Given the cumulative log-probabilities of K active beams in each of B independent sequences and the next-token log-probabilities for every token in the vocabulary from each beam, expand all K × V candidate continuations and select the top K candidates per sequence to form the next set of beams.
For each batch b and candidate (k, v), the score is
\[
\text{cand}[b, k, v] = \text{beam\_scores}[b, k] + \text{token\_logprobs}[b, k, v]
\]
Per batch, the top K candidates by score are selected and written, sorted in descending order by score, into new_beam_scores. For each selected candidate, the originating beam index k is written to parent_beam_indices and the chosen vocabulary token v to next_tokens.
solve function signature must remain unchangednew_beam_scores, parent_beam_indices, and next_tokensK outputs must be sorted in descending order by score; parent_beam_indices and next_tokens must correspond positionally to new_beam_scoresK × V candidate scores within a batch are distinct in the test data, so no tie-breaking is required; the behavior on exact ties is unspecified
Input:
beam_scores = [[-0.5, -1.0]]
token_logprobs = [[[-0.3, -1.2, -2.0, -2.5],
[-0.4, -0.1, -1.6, -3.2]]]
B = 1, K = 2, V = 4
Output:
new_beam_scores = [[-0.8, -1.1]]
parent_beam_indices = [[0, 1]]
next_tokens = [[0, 1]]
Explanation:
Candidate scores (cand[k, v] = beam_scores[k] + token_logprobs[k, v]):
from beam 0: [-0.8, -1.7, -2.5, -3.0]
from beam 1: [-1.4, -1.1, -2.6, -4.2]
The two highest scores are -0.8 (beam 0, token 0) and -1.1 (beam 1, token 1).
B ≤ 64 (batch size)K ≤ 32 (beam width)V ≤ 100,000 (vocabulary size)beam_scores, token_logprobs, and new_beam_scores are 32-bit floatsparent_beam_indices and next_tokens are 32-bit integersB = 16, K = 8, V = 50,000