Abstract
In automatic speech recognition (ASR), algorithmic efficiency does not always translate to hardware performance. This study investigates the trade-off between the mathematically optimized Weighted Finite State Transducer (WFST) and the structurally regular Linear Lexical Model (LLM). While WFSTs minimize total operations, their irregular memory patterns hinder GPU performance. Conversely, the LLM's redundancy allows for superior parallelization, often outperforming WFSTs on manycore architectures by better utilizing hardware throughput.
Introduction: The Parallelization Challenge
For decades, ASR algorithm design focused on sequential efficiency—minimizing total operations to conserve CPU cycles. This led to the dominance of the Weighted Finite State Transducer (WFST), a highly compressed representation that eliminates redundancy. However, the emergence of GPUs has shifted the bottleneck from raw operation count to memory access patterns and data parallelism. GPUs thrive on regularity but struggle with the fine-grained synchronization and irregular memory access inherent in complex WFST graphs. This paper explores whether "redundant" models like the Linear Lexical Model (LLM) might be more suitable for modern parallel hardware.
Methodology and System Architecture
The researchers evaluated two distinct recognition network representations within a GPU-based inference engine.
- Linear Lexical Model (LLM): An older approach representing each word's pronunciation as an independent chain of states. While highly redundant, its structure is predictable and matrix-like.
- Weighted Finite State Transducer (WFST): The modern standard that merges redundant paths into a concise but irregular graph.
The inference engine was implemented using the Viterbi search algorithm, with specific optimizations for "Phase 2" (graph traversal). Testing was conducted on NVIDIA GTX285 and GTX480 (Fermi) architectures using the 5k Wall Street Journal (WSJ1) corpus.
Key Insights: Regularity vs. Algorithmic Elegance
The core finding of this research is the "Work vs. Speed" paradox. To achieve a Word Error Rate (WER) of 8.9%, the LLM must evaluate 22 times more transitions than the WFST. In a traditional sequential execution environment, the LLM would be significantly slower.
However, the GPU's architecture favors the LLM's regularity. The system can gather data for the LLM 53–65x faster than for the WFST. Furthermore, the actual evaluation of these transitions is 4.7–6.4x faster per transition. The WFST’s irregular graph forces the GPU into inefficient "Data Gathering" patterns, whereas the LLM allows for the dense, high-throughput operations that GPUs are designed to accelerate.
Results and Performance Analysis
On the GTX480 architecture, the WFST reached a performance of 13.7x faster than real-time, while the LLM reached 10.9x. Interestingly, on the older GTX285 hardware, the LLM actually outperformed the WFST at certain accuracy thresholds (WER > 8.8%).
The introduction of hardware caches in the Fermi (GTX480) architecture provided a 79% speedup for the WFST by mitigating some irregular memory access penalties. Nevertheless, the LLM remained competitive due to its massive throughput, capable of evaluating over 20 million transitions per second.
Conclusion and Future Directions
The study demonstrates that hardware-aware algorithm design is crucial for manycore platforms. While the LLM is effective for a 5k-word vocabulary, its primary limitation is scalability; larger vocabularies (50k+) may lead to a state explosion exceeding GPU memory. Future research should focus on hybrid approaches that combine WFST conciseness with LLM-like data locality through static or dynamic network partitioning.
Summary updated