The Viterbi score, can be computed for all the
states in the language model at *t*=*t* and then can
advance to the time instant *t*=*t*+1, in an inductive manner, as
formulated in 1.8 [, ]. This procedure is known as
*time synchronous Viterbi search* because it completely
processes at time *t* before going into the time *t*+1. Finally a
backtracking pass gives the required state sequences. However even
Viterbi search can be very expensive if the number of states is
large. In such cases instead of keeping all candidates at every time
frame *t*, only the first *T* candidates with the highest scores are
allowed to retain. Others are discarded from further considerations.
This procedure is known as *beam search.*

Fri May 10 20:35:10 MET DST 1996