← All problems
#98 Beam Search Step Medium

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.

Implementation Requirements

Example 1:

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).

Constraints

Guided walkthrough coming soon. Below is the official starter signature in each language; the clickable line-by-line explanation hasn't been authored yet.
Problem text & starters from the official AlphaGPU/leetgpu-challenges. Solve it on leetgpu.com.