Decoding Algorithms Comparison

Once an advanced acoustic model like CTC, an attention-based encoder-decoder, or an RNN Transducer has been trained, it produces outputs representing the likelihood of different linguistic units (like characters or phonemes) given the input audio features. However, these raw outputs, often probability distributions over time or sequences, are not the final transcription. The important next step is decoding: the process of searching for the most probable sequence of words that corresponds to the model's output. This search process is non-trivial because the number of possible sequences can be enormous. Different acoustic model architectures necessitate distinct decoding strategies, each with its own characteristics and trade-offs regarding accuracy, computational cost, and suitability for applications like real-time transcription.

The Search Problem in ASR Decoding

At its heart, decoding aims to find the output sequence $Y$ (e.g., characters or words) that maximizes the probability given the input acoustic features $X$. For end-to-end models, this is often represented as finding $\hat{Y} = \arg\max_Y P(Y|X)$. For hybrid systems, this involves combining probabilities from the acoustic model (AM), pronunciation lexicon (L), and language model (LM): $\hat{Y} = \arg\max_Y P(X|Y) P(Y)$.

Finding the globally optimal sequence is often computationally intractable due to the vast search space. Therefore, practical decoders rely on heuristic search algorithms, primarily variations of beam search, to find a high-probability sequence efficiently. The choice and configuration of the decoding algorithm significantly impact the final ASR performance.

Decoding with Hybrid HMM-DNN Systems: WFSTs

Traditional hybrid systems, which combine DNNs with Hidden Markov Models (HMMs), typically rely on Weighted Finite State Transducers (WFSTs) for decoding. This approach elegantly combines different knowledge sources into a single search graph.

1. Components: The process involves composing several WFSTs:
   • H (HMM): Represents the acoustic context-dependent HMM state transitions. The DNN provides the emission probabilities (likelihoods of acoustic features given HMM states).
   • C (Context-dependency): Maps context-dependent units (e.g., triphones) to context-independent ones (e.g., monophones).
   • L (Lexicon): Maps sequences of phonemes to words.
   • G (Grammar/Language Model): Represents the probability of word sequences, typically an n-gram LM converted into WFST form.
2. Composition: These WFSTs are composed into a single large search graph: $S = H \circ C \circ L \circ G$. This graph encodes all valid paths from acoustic states to word sequences, weighted by the combined probabilities.
3. Search: Decoding involves finding the best path through the composed graph $S$ given the sequence of acoustic feature vectors $X$. This is typically done using token-passing algorithms, which are essentially optimized forms of Viterbi search or beam search operating directly on the WFST.

WFST-based decoding is powerful and allows seamless integration of complex lexicons and large n-gram language models. However, constructing and optimizing these WFSTs can be complex, and the approach tightly couples the acoustic model to predefined HMM states and pronunciation dictionaries.

Decoding with Connectionist Temporal Classification (CTC)

CTC models simplify the process by learning alignments implicitly. They output probability distributions $P(k|t, X)$ for each token $k$ (including a special blank symbol, $\epsilon$) at each time frame $t$. Decoding involves finding the most likely output sequence $Y$ by considering all possible alignments $\pi$ that map to $Y$ after removing repeated non-blank symbols and then removing blanks.

1. Greedy (Best Path) Decoding: The simplest approach. At each time step $t$, select the token $k$ with the highest probability $P(k|t, X)$. Concatenate these tokens and then apply the CTC collapsing rules (remove repeats, remove blanks). This is very fast but often suboptimal as it makes local decisions without considering the full sequence probability.
2. Beam Search Decoding: A more effective approach that maintains a set (the "beam") of the $B$ most probable candidate prefix sequences at each time step.
   • Initialization: Start with an empty prefix with probability 1.0.
   • Expansion: At each time step $t$, expand each prefix in the beam by considering appending the next possible output token (including blank). Calculate the probability of the extended prefixes using the CTC output probabilities $P(k|t, X)$ and the probabilities of the prefixes from the previous step. Handle the merging of paths that result in the same output sequence after collapsing (e.g., A -> AA and A -> A$\epsilon$ both result in A).
   • Pruning: Keep only the top $B$ most probable prefixes in the beam for the next time step.
   • Termination: Continue until the end of the input sequence. The highest probability sequence in the final beam is the result.
3. LM Integration: A standard n-gram or neural language model can be incorporated during CTC beam search. When expanding a prefix, the probability can be adjusted by adding the log-probability of the proposed next word (or character) from the LM, often weighted by a hyperparameter $\lambda$. This is sometimes called prefix beam search or shallow fusion.

A view of CTC beam search expansion over time steps, maintaining candidate prefixes and their probabilities. Actual implementations handle merging paths based on CTC collapsing rules.

CTC decoding is simpler than WFST decoding as it avoids explicit HMM states and lexicon composition, but effective LM integration during the beam search is important for high accuracy.

Decoding with Attention-Based Encoder-Decoders (AED)

AED models, such as Listen, Attend, and Spell (LAS) or Transformer-based ASR models, generate the output sequence $Y = (y_1, y_2, ..., y_L)$ autoregressively. That is, the probability of the next token $y_i$ depends on the encoded acoustic features $H_{enc}$ and the previously generated tokens $y_{<i}$: $P(y_i | H_{enc}, y_{<i})$.

1. Greedy Decoding: At each output step $i$, simply choose the token $y_i$ with the highest probability $P(y_i | H_{enc}, y_{<i})$. This is fast but prone to errors early in the sequence that cannot be corrected later.
2. Beam Search Decoding: The standard approach for sequence generation models.
   • Initialization: Start with a begin-of-sequence token (<sos>) as the initial hypothesis.
   • Expansion: At each step $i$, take the current set of $B$ hypotheses (partial sequences) in the beam. For each hypothesis, calculate the probability distribution over the next possible token $y_i$ using the model. Expand each hypothesis by appending the top $k$ most likely next tokens (where $k$ might be equal to the beam width $B$ or smaller).
   • Scoring: The score (typically log probability) of an expanded hypothesis is the sum of the log probabilities of its constituent tokens. $Score(y_1...y_i) = \sum_{j=1}^{i} \log P(y_j | H_{enc}, y_{<j})$.
   • Pruning: Collect all expanded hypotheses and keep only the top $B$ overall highest-scoring ones.
   • Termination: Stop when hypotheses reach an end-of-sequence token (<eos>) or a maximum length. The completed hypothesis with the highest score (possibly adjusted for length) is selected.
3. LM Integration: Language models are commonly integrated to improve fluency and recognize rare words.
   • Shallow Fusion: During beam search, the score of a hypothesis is modified by adding a weighted LM log probability: $Score_{fused} = Score_{AM} + \lambda \cdot Score_{LM}$. The LM scores $P_{LM}(y_i | y_{<i})$ independently.
   • Deep Fusion: The internal state of the LM is combined with the decoder state of the ASR model before predicting the next token probability. This allows for tighter integration but increases model complexity.

Beam search significantly improves AED performance over greedy decoding but introduces latency as it checks multiple paths.

Decoding with RNN Transducers (RNN-T)

RNN-T models predict outputs token-by-token while simultaneously deciding whether to advance in the input audio time steps, naturally supporting streaming inference. The model outputs a joint distribution over the next output token $y_i$ and emitting a blank symbol $\epsilon$: $P(k | t, u)$, where $t$ is the current audio frame index and $u$ is the index of the previously predicted non-blank token.

1. Greedy Decoding: At each step in the implicit alignment grid, choose the highest probability action: either emit a specific token $k \neq \epsilon$ (advancing $u$) or emit $\epsilon$ (advancing $t$).
2. Beam Search Decoding: Standard beam search needs adaptation for RNN-T's structure.
   • Hypothesis State: Each hypothesis in the beam must track not only the generated token sequence $y$ but also the current audio frame index $t$ and the index/state related to the last predicted non-blank token $u$.
   • Expansion: For each hypothesis $(y, t, u)$ in the beam, calculate probabilities for all possible next tokens $k$ (including $\epsilon$) using $P(k | t, u)$. If $k = \epsilon$, the new state is $(y, t+1, u)$. If $k \neq \epsilon$, the new state is $(y \cdot k, t, u+1)$, where $y \cdot k$ denotes appending $k$ to $y$.
   • Pruning: Keep the top $B$ hypotheses based on their accumulated probabilities. Specialized algorithms like alignment-length synchronous decoding are often used for efficiency.
3. LM Integration: Similar to CTC, LMs can be integrated during beam search, typically via shallow fusion, adjusting scores when a non-blank token is proposed.

RNN-T decoding is well-suited for low-latency streaming ASR, as predictions can be made as audio arrives. The beam search algorithm is more complex than standard AED beam search due to the need to manage both time and output sequence progression.

Comparison and Trade-offs

Feature	WFST (Hybrid)	CTC	AED (Attention/Transformer)	RNN-T
Architecture	DNN + HMM/GMM	End-to-End (w/ blank)	End-to-End (Seq2Seq)	End-to-End (Streaming)
Alignment	Explicit (HMM states)	Implicit (via blank)	Implicit (Attention)	Implicit (Alignment Grid)
Primary Decoder	WFST Search	Beam Search	Beam Search	Specialized Beam Search
Streaming	Difficult / Requires hacks	Possible (w/ latency)	Difficult (Autoregressive)	Natural
LM Integration	WFST Composition	Shallow Fusion / Prefix BS	Shallow / Deep Fusion	Shallow Fusion / Prefix BS
Complexity	High (WFST composition)	Medium	Medium	High (Beam Search State)
Dependencies	Lexicon, HMM topology	Minimal	Minimal	Minimal

Comparison of decoding approaches for different ASR architectures.

Considerations:

• Latency vs. Accuracy: Greedy decoding is fastest but least accurate. Beam search increases accuracy at the cost of computation and latency. Larger beam widths ($B$) generally improve accuracy but increase cost. RNN-T offers the best native support for low-latency streaming.
• Language Model Integration: Integrating an external LM is almost always beneficial for accuracy. Shallow fusion is easier to implement across different architectures, while deep fusion (primarily for AEDs) offers potentially tighter integration.
• Computational Resources: WFST decoding can require significant memory for the composed graph. Beam search complexity scales with beam width and sequence length. RNN-T beam search requires careful state management.
• Implementation: Libraries like Kaldi provide tools. Toolkits like ESPnet, NeMo, and SpeechBrain offer implementations for CTC, AED, and RNN-T decoding.

Ultimately, the choice of decoding algorithm is intertwined with the acoustic model architecture. Understanding the principles behind WFSTs, CTC beam search, sequence-to-sequence beam search, and RNN-T decoding allows you to select and configure the appropriate search strategy for your specific ASR system and application requirements. Efficient and accurate decoding is just as important as a well-trained acoustic model for achieving state-of-the-art speech recognition performance.