Implement Beam Search Decoding
Problem statement
Implement beam search over token sequences.
For this exercise, assume a fixed-length decoder with token IDs from 0 through V - 1. startScores[t] is the score for choosing token t first. nextScores[a][b] is the added score for choosing b after a. Scores are added; larger totals rank first.
- Begin with one empty sequence of score zero.
- At each step, extend every retained sequence with every token.
- Rank extensions by descending total score, breaking ties lexicographically by token IDs.
- Keep at most beamWidth extensions before the next step.
Return the retained sequences after exactly steps steps, in rank order. No end token or length normalization is used. Do not replace per-step pruning with a global search over all complete sequences.
Function
beamSearch(startScores: int[], nextScores: int[][], steps: int, beamWidth: int) → int[][]Examples
Example 1
startScores = [0,-1]nextScores = [[-4,0],[0,-4]]steps = 3beamWidth = 2return = [[0,1,0],[1,0,1]]After one step the beam is [[0],[1]]. After two steps it is [[0,1],[1,0]], with scores 0 and -1. After three steps it is [[0,1,0],[1,0,1]], again with scores 0 and -1.
Example 2
startScores = [0,-1]nextScores = [[-10,-10],[0,0]]steps = 2beamWidth = 1return = [[0,0]]Width 1 keeps only [0] after the first step. Its two extensions tie at score -10, so [0,0] survives. The better-scoring [1,0] path cannot be recovered after [1] was pruned.
Example 3
startScores = [0,0]nextScores = [[0,0],[0,0]]steps = 2beamWidth = 3return = [[0,0],[0,1],[1,0]]All scores tie. Lexicographic ordering keeps [0,0], [0,1], and [1,0] in that order.
Constraints
- 1 <= startScores.length <= 12.
- nextScores has startScores.length rows.
- Every nextScores row has startScores.length values.
- Every score is an integer from -1000 through 0.
- 1 <= steps <= 8.
- 1 <= beamWidth <= 20.