MediumNLPnlp-290

Greedy versus Beam Divergence

Problem

Compare context-dependent greedy decoding with beam search. vocab is the token list, model maps a space-joined prefix to the probability row for the next token, steps is the number of tokens to decode, and beam_width controls the search.

Return the first index where the greedy sequence and the best beam sequence differ, the shorter length when one is a prefix of the other, or -1 when they are identical.

Hint

Greedy commits to each prefix argmax, while beam search can abandon it after seeing better continuations.

Test cases

case 1

in: [["a","b"],{"":[0.6,0.4],"a":[0.5,0.5],"b":[0.9,0.1]},2,2]

expected: 0

case 2

in: [["a","b"],{"":[0.6,0.4],"a":[0.5,0.5],"b":[0.9,0.1]},2,1]

expected: -1

case 3

in: [["a","b","c"],{"":[0.2,0.3,0.5],"c":[0.1,0.2,0.7]},2,2]

expected: -1

case 4

in: [["a","b","c"],{"":[0.6,0.3,0.1],"a":[0.4,0.3,0.3],"a a":[0.2,0.4,0.4],"a b":[0.9,0.05,0.05]},3,2]

expected: 1

case 5

in: [["a","b"],{"":[0.5,0.5],"a":[1,0],"b":[0,1]},2,2]

expected: -1

Starter codePython

import math
def greedy_vs_beam_divergence(vocab, model, steps, beam_width):
    # Your code here
    pass

5 test cases · run your code against them in the editor