Combining forward and backward search in decoding

We introduce a speed-up for weighted finite state transducer (WFST) based decoders, which is based on the idea that one decoding pass using a wider beam can be replaced by two decoding passes with smaller beams, decoding forward and backward in time. We apply this in a decoder that works with a variable beam width, which is widened in areas where the two decoding passes disagree. Experimental results are shown on the Wall Street Journal corpus (WSJ) using the Kaldi toolkit, and show a substantial speedup (a factor or 2 or 3) at the “more accurate” operating points. As part of this work we also introduce a new fast algorithm for weight pushing in WFSTs, and summarize an algorithm for the time reversal of backoff language models.