beam-search-step — Zoom case

Zoom-inspired speech/transcription prototype keeps several candidate sequences instead of committing to a single next token. You need to perform one beam-search expansion and retain the highest-scoring candidates deterministically.

Perform one beam-search expansion step. beams is a list of (tokens, score) pairs (tokens is a list), next_logp holds the log-probability of every vocabulary token for the next position (the same for every beam) and width is the number of beams to keep. Extend every beam with every token, add the log-probability to the score, and keep the width best candidates; ties are broken in favour of the lexicographically smaller token list.

Implement solve(beams,next_logp,width).

Returns. Return a list of at most width (tokens, score) pairs sorted from best to worst.

Examples

Example 1

Input:

solve([([], 0.0)], [-0.1, -2.0, -1.0], 2)

Output:

[([0], -0.1), ([2], -1.0)]

Example 2

Input:

solve([([1], -0.5), ([2], -0.7)], [-0.2, -0.9], 3)

Output:

[([1, 0], -0.7), ([2, 0], -0.9), ([1, 1], -1.4)]