The path calculation for beam search

For normal beam search, a traceback is needed to recover the word string after the Viterbi search. For this reason, the memory must contain information which word was 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. Usually, $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.