WFST Decoding in Speech Recognition

A weighted finite-state transducer, or WFST, is a directed graph whose arcs carry input symbols, output symbols, and weights. A path represents a sequence of symbol mappings with an accumulated cost or score. Composition connects compatible transducers so a pipeline of mappings can be represented as one search graph. Speech recognition has long used WFSTs to combine different knowledge sources while searching for a likely word sequence. In the conventional hybrid HMM recipe described in Kaldi, H represents the HMM transition structure, C represents context dependency that maps context-dependent phones, L represents the pronunciation lexicon mapping phones to words, and G represents a grammar or language model over words. Their composition is commonly written HCLG. The acoustic model supplies scores associated with acoustic states or transitions; decoding searches graph paths for a low-cost explanation of the observed speech. HCLG describes a graph construction recipe, not an end-to-end neural architecture. The graph encodes alternatives and constraints before or during decoding. A pronunciation lexicon can include multiple pronunciations. The language-model component favors some word sequences over others. Weights from acoustic and language sources must be scaled appropriately because they may be on different effective scales. A narrow grammar can speed search but exclude valid expressions; a broad vocabulary can increase ambiguity and graph size. Building a decoding graph requires careful symbol tables, disambiguation symbols, and composition details. Context expansion can increase state counts. Determinization, minimization, and weight pushing can reduce graph size or improve efficiency when conditions permit, but are specialized operations with correctness assumptions. A graph that builds successfully still requires recognition evaluation and vocabulary coverage checks. WFSTs are not limited to older recognizers, but the HCLG decomposition is specifically associated with hybrid systems using HMM state structures and pronunciation lexicons. End-to-end systems may decode with other search methods and token structures. Understanding the WFST graph remains useful for maintaining hybrid pipelines and for recognizing how weighted constraints are composed.