The path calculation for beam search

For normal Viterbi search, a traceback is needed to recover the word string after a likelihood calculation. For this reason, the memory must contain information as to which word is selected for each frame. This requires $B \times T$ memory cells. A capacity of $B \times H$ is however sufficient, if we store likelihoods and word strings as $G_t(w_1,w_0,i)$ together, where $H$ is the number of words in a sentence. In this case, no traceback is needed. In most cases, $H$, the number of words in a sentence, is smaller than $T$, the number of input frames, so the memory is reduced but the calculation cost is slightly increased.