At subsequent steps, each of the k best hypotheses is extended incrementally by being passed to distinct decoders, which each generate a softmax over the entire vocabulary to extend the hypothesis to every possible next token. Each of these k * V hypotheses is scored by P(y i |x, y <i ): the product of the probability of current word choice multiplied by the probability of the path that led to it. We then prune the k * V hypotheses down to the k best hypotheses, so there are never more than k hypotheses 10.5 • BEAM SEARCH 221 at the frontier of the search, and never more than k decoders. Fig. 10 .12 illustrates this process with a beam width of 2. This process continues until a </s> is generated indicating that a complete candidate output has been found. At this point, the completed hypothesis is removed from the frontier and the size of the beam is reduced by one. The search continues until the beam has been reduced to 0. The result will be k hypotheses.