As explained in [@nolleDeepAlignAlignmentbasedProcess2020], Beam search is a greedy algorithm that finds a trade-off between traversing all possible combinations and only the most probable next word. For every prediction, the BS algorithm expands only the K most probable sentence continuations (beams). In the next step, the best K probable continuations over all K beams from the previous step are chosen, and so on. For K = 1, BS is equivalent to the greedy 1-best approach explained above. BS has the advantage of pruning the search space to feasible sizes, while still traversing a sufficient part of the search space to produce a good approximation of the most likely sentence continuation.
tags: computation-theory related: Bidirectional Beam Search