THE BEAM SEARCH TIE
Intermediate
Difficulty: Medium Tags: LLM Decoding, Beam Search, Ranking
Story
A text-generation service keeps the best candidate beams after each decoding step. Equal scores must be resolved by the lower beam ID to make output reproducible across workers.
The Math
Each candidate has a cumulative log score s_i and a unique ID
id_i. Rank by descending score, then ascending ID for ties. Keep the
first k. Scores are already cumulative log probabilities: never
apply softmax or normalize them.
Input Format
candidates (list of (id, score) pairs), k (int).
Output Format
List of the selected IDs in ranking order.
Constraints
1 <= k <= n <= 10^5, scores are finite reals.- Time limit: 1.0 second.
Example
Input
candidates = [(8,-2.3), (3,-1.1), (4,-1.1), (1,-4.0)], k = 2
Output
[3, 4]
Explanation: The highest score is -1.1; IDs 3 and 4 tie, so the
lower ID ranks first.
Keywords
llm-decodingbeam-searchranking
Python
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.