An Asynchronous WFST-Based Decoder for Automatic Speech Recognition

Hang Lv, Zhehuai Chen, Hainan Xu, Daniel Povey, Lei Xie, Sanjeev Khudanpur

TL;DR

This paper introduces an "asynchronous dynamic decoder" that significantly speeds up one-pass automatic speech recognition (ASR) by efficiently incorporating large language models. It achieves this by splitting the decoding process into two alternating "fronts" – exploration and backfill – guided by an A* search algorithm, leading to more effective pruning and up to 20.17% speedup.

What Problem Does This Paper Address?

Automatic Speech Recognition (ASR) systems, especially those handling large vocabularies and complex language models (LMs), face a significant computational bottleneck during the decoding phase. While using larger LMs generally improves accuracy, it drastically increases the search space and computational cost. Traditional two-pass decoding (first with a small LM, then rescoring with a large LM) introduces latency. One-pass "on-the-fly" composition decoding aims to solve this by dynamically composing a decoding graph with a large LM as needed. However, this approach can still be slow due to the vast search space. The paper addresses the challenge of achieving accurate, one-pass ASR with large LMs without sacrificing speed, by proposing a more efficient decoding strategy.

Methods

The core innovation is the Asynchronous Dynamic Decoder (AsyncBigLM decoder). It builds upon the "BigLM decoder" concept, which uses on-the-fly composition with a large LM. The key novelty lies in its two-front approach:

  • Exploration Front: This front processes tokens similar to a standard decoder. However, for a given HCLG-state (a state in the combined acoustic and language model graph), it only expands the "best-in-class" token (the one with the lowest cost). Other tokens with the same HCLG-state but higher costs are marked as "un-expanded" and linked implicitly to the best token.
  • Backfill Front: This front processes the "un-expanded" tokens. It uses an A* search algorithm to estimate the potential of these tokens. By leveraging the cost information from the "best-in-class" tokens on the exploration front, it can more intelligently decide which un-expanded tokens are worth pursuing, effectively pruning less promising paths.

The computation alternates between these two fronts, allowing for more aggressive pruning and reduced computational overhead compared to standard one-pass decoders. The A* algorithm's heuristic function is crucial for estimating the cost-to-go for un-expanded tokens.

Datasets

The experiments were conducted using the LibriSpeech corpus, which includes approximately 960 hours of training data and four test sets (dev-clean, dev-other, test-clean, test-other).

Key Insights and Ideas

  • Splitting the Search: The most significant insight is that not all tokens need to be fully explored at every step. By identifying "best-in-class" tokens and deferring the processing of others to a "backfill" phase, the decoder can prune the search space much more effectively.
  • A* for Intelligent Pruning: The application of the A* search algorithm to guide the backfill process is key. It allows the decoder to make informed decisions about which paths to pursue, preventing the exponential growth of the search space that plagues traditional methods.
  • Exploration-Backfill Synergy: The alternating nature of the two fronts creates a powerful synergy. Exploration identifies promising candidates, while backfill efficiently explores the remaining possibilities based on the information gathered during exploration. This leads to a more balanced and efficient decoding process.
  • Speedup with Complexity: The paper highlights that the speedup gained by the asynchronous decoder becomes more pronounced as data complexity increases (e.g., noisier data or larger LMs). This suggests its robustness and scalability.

Key Results

  • Speedup: The proposed AsyncBigLM decoder achieved up to 20.17% relative speedup compared to the standard one-pass BigLM decoder.
  • Accuracy: The accuracy, measured by Word Error Rate (WER), was found to be comparable to the BigLM decoder and lattice-rescoring methods. Table 1 shows very close WER values across different LM sizes and test sets. Table 2 further confirms this by showing negligible differences in average log-likelihoods between BigLM and AsyncBigLM.
  • Efficiency: Table 4 shows a significant reduction in effective propagation times, with the asynchronous decoder having zero backfill propagation times in the tested scenario, demonstrating its efficiency.

Limitations and Future Work

  • Offset Parameter: The "offset" parameter, which determines the gap between the exploration and backfill fronts, is set empirically. The paper notes that the process on each front can be executed for a few frames to balance accuracy and speed, suggesting that further optimization of this parameter could be beneficial.
  • General Applicability: The paper states that the decoder is general-purpose and does not have special requirements for acoustic models (AMs) or language models (LMs), implying broad applicability. However, the specific performance gains might vary depending on the AM and LM architectures used.
  • Future Work: The paper implicitly suggests that further tuning of the exploration and backfill strategies, as well as the A* heuristic, could lead to even greater speedups and potentially improved accuracy. The open-sourcing of the code under Kaldi also facilitates future research and development in this area.

Summary updated

Abstract

We introduce asynchronous dynamic decoder, which adopts an efficient A* algorithm to incorporate big language models in the one-pass decoding for large vocabulary continuous speech recognition. Unlike standard one-pass decoding with on-the-fly composition decoder which might induce a significant computation overhead, the asynchronous dynamic decoder has a novel design where it has two fronts, with one performing "exploration" and the other "backfill". The computation of the two fronts alternates in the decoding process, resulting in more effective pruning than the standard one-pass decoding with an on-the-fly composition decoder. Experiments show that the proposed decoder works notably faster than the standard one-pass decoding with on-the-fly composition decoder, while the acceleration will be more obvious with the increment of data complexity.
BibTeX
@inproceedings{lv2021asynchronous,
  author = {Hang Lv and Zhehuai Chen and Hainan Xu and Daniel Povey and Lei Xie and Sanjeev Khudanpur},
  title = {{An Asynchronous WFST-Based Decoder for Automatic Speech Recognition}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2021},
  url = {https://openreview.net/forum?id=U5UdYFFChW9},
}

Loading related content...

Figure