Beam Search

Control Beam Search Length Bias with Length Normalization

Beam search is a common way to decode sequence models when choosing the most likely token at every step is too shortsighted. It keeps several partial candidates alive, expands them, and repeatedly retains the strongest alternatives. There is a subtle problem: the score used for a sequence usually accumulates one log-probability per generated token. Because token probabilities are at most 1, their log-probabilities are normally non-positive. Extending a sequence therefore tends to make its raw cumulative score smaller. When finished candidates of different lengths compete directly, this can create a preference for outputs that end too early.