Beam Search Decoding
Text Generation & NLP Evaluation DS practice problem on Onlearn.
Difficulty: medium.
Topics: Understanding Beam Search for Sequence Generation, Beam Width, Cumulative Log-Likelihood, Pruning, Softmax Normalization, Token Indexing, Natural Language Processing, Probability Theory, Dynamic Programming, Search Algorithms, Information Theory, Autoregressive Modeling, Sequence Decoding, Log-Probability Summation, Heuristic Search, Greedy vs Exhaustive Search.
Implement a beam search decoder that takes a function (representing a language model's next token probability distribution), a start token, a vocabulary size, and a beam width 'k'. The function should generate a sequence of length 'max len' by keeping track of the top k most probable paths at each step.