score(y) = log P(y|x) = log (P(y 1 |x)P(y 2 |y 1 , x)P(y 3 |y 1 , y 2 , x)...P(y t |y 1 , ..., y t−1 , x)) = t i=1 log P(y i |y 1 , ..., y i−1 , x) (10.19) Thus at each step, to compute the probability of a partial translation, we simply add the log probability of the prefix translation so far to the log probability of generating the next token. Fig. 10 .13 shows the scoring for the example sentence shown in Fig. 10 .12, using some simple made-up probabilities. Log probabilities are negative or 0, and the max of two log probabilities is the one that is greater (closer to 0). Figure 10 .13 Scoring for beam search decoding with a beam width of k = 2. We maintain the log probability of each hypothesis in the beam by incrementally adding the logprob of generating each next token. Only the top k paths are extended to the next step. Fig. 10 .14 gives the algorithm. One problem arises from the fact that the completed hypotheses may have different lengths. Because models generally assign lower probabilities to longer strings, a naive algorithm would also choose shorter strings for y. This was not an issue during the earlier steps of decoding; due to the breadth-first nature of beam search all the hypotheses being compared had the same length. The usual solution to this is function BEAMDECODE(c, beam width) returns best paths y 0 , h 0 ← 0 path ← () complete paths ← () state ← (c, y 0 , h 0 , path)