It is also noteworthy that the decoder only needs to perform / 2 X expansions as after / 2 X expansions, all combinations of / 2 X phrases would have been explored already.
after / 2 X expansions, we only need to combine the corresponding two partial paths to make up the entire input phrases, then select the path with highest n-gram score as the best translation output.