Beam search

Beam search is employed to decrease the computational cost[5]. In Viterbi search, at each time $t$, we compute the probability of all possible combinations. In comparison, with the beam search algorithm, we only compute the probability of the most likely word combinations within a beam width $B$. Assuming a large enough beam width, the globally optimal Viterbi path will exist within that beam width. The complexity of the beam search algorithm is $O( B \cdot T )$. So the memory requirement and the calculation cost are reduced by $O { B / (Q^2 \cdot l_w )}$.