Algorithm · Microsoft · Medium
You are given the transition structure of an autoregressive decoder, organized as a graph split into layers. Your job is to decode a sentence from it in two ways: with greedy decoding and with beam search. Decoding always begins in state 0, and from there exactly D tokens must be produced, one per layer. Every edge in layer i is written as parent_state token child_state probability. Such an edge says that while the sequence sits in parent_state, the decoder is allowed to…