Pruning of beam width

There are two methods to prune the beam width.

1. Select the beam width based on some threshold.
2. Select a fixed beam width.

In most case, a method that selects the beam width with some threshold is used. Such a method is computationally cheap. But the threshold must be determined before recognition[1]. Therefore, under some recognition conditions, the output is faulty. A method that selects a fixed beam width, on the other hand, requires $G_t(w_1,w_0,i)$ to be sorted for each frame. This method requires a lot of computation. However, $G_t(w_1,w_0,i)$ need not be fully sorted, if only the values of the best $B$ likelihoods are calculated, and the other likelihood values are subsequently pruned. Concretely, if the maximum beam width is $N$, this calculation is only of order $O( log_2 N )$ , which is not too costly.