In sequence prediction tasks like Automatic Speech Recognition (ASR) and Statistical Machine Translation (SMT), researchers face a fundamental trade-off between search breadth and scoring depth. A model that considers every possible grammatical nuance or long-range acoustic dependency is often too computationally expensive to search through the astronomical number of possible sentences.
To solve this, the field converged on a multi-pass architecture. Instead of finding the perfect answer in one go, these systems use a "filter-then-rank" strategy: a fast, simple model prunes the search space to a handful of candidates, which a sophisticated, "heavy" model then re-evaluates.
The Computational Bottleneck
The primary challenge in decoding is that the search space grows exponentially with the length of the output. Traditional decoders, such as those described by Huang et al. in An Overview of the SPHINX-II Speech Recognition System, rely on the Viterbi algorithm or beam search. These methods require "local" scoring—deciding the next word based only on the immediate past (e.g., bigrams).
However, the most accurate features are often "global." For instance, checking if a translated sentence is syntactically sound or if a spoken word matches the context of a conversation from five minutes ago requires looking at the entire sequence at once. As Zavaliagkos et al. argued in A Hybrid Neural Net System for State-of-the-Art Continuous Speech Recognition, applying these complex scores during the initial search is mathematically intractable. Two-pass rescoring decouples the generation of possibilities from the evaluation of their quality.
Pass 1: Generating the N-Best List
The first pass uses a computationally efficient model—like a Hidden Markov Model (HMM) or a phrase-based translation engine—to generate a set of high-probability candidates. This output typically takes two forms:
- N-Best Lists: A simple ranked list of the top $N$ hypotheses (e.g., the top 100 most likely sentences).
- Word Graphs (Lattices): A directed acyclic graph representing a dense set of possible paths. Ueffing et al. showed in Generation of Word Graphs in Statistical Machine Translation that lattices allow for a much larger search space to be passed to the second stage than a flat list.
By restricting the second pass to this pre-filtered set, researchers can use models that would otherwise be far too slow for real-time use.
Pass 2: The Power of Global Context
Once the search space is reduced to a few hundred candidates, the system can afford to be "expensive." This second pass, or rescoring stage, integrates high-level linguistic and acoustic information that the first pass ignored.
- Neural Language Models: Early neural approaches, such as the Continuous Space Language Model (CSLM) described by Holger Schwenk in Building a Statistical Machine Translation System for French Using the Europarl Corpus, used neural networks to overcome the data sparsity of traditional n-grams. Because these models are slow to compute, they were initially applied only to rescore n-best lists.
- Syntactic and Semantic Constraints: The authors of Experiments in Discriminating Phrase-Based Translations on the Basis of Syntactic Coupling Features demonstrated how a second pass can re-evaluate translations based on their grammatical structure relative to the source text. Similarly, Nadejde et al. used a neural verb lexicon to fix specific translation errors that a general-purpose decoder missed.
- Long-Range Context: In conversational speech, Xiong et al. showed in Session-level Language Modeling for Conversational Speech that rescoring allows a model to look at the entire history of a conversation, significantly improving accuracy by tracking the topic over time.
The Oracle Bottleneck
While powerful, two-pass systems are limited by the quality of the first pass. This is known as the "oracle" problem: if the correct transcription or translation is not present in the initial N-best list or lattice, the second-pass model—no matter how sophisticated—can never select it.
Schwenk et al. noted in Large and Diverse Language Models for Statistical Machine Translation that the diversity of the initial candidate set is a hard ceiling on performance. Similarly, Allauzen et al. pointed out in LIMSI @ WMT12 that the computational cost of neural models often forces a two-pass approach, creating a bottleneck where the final output is strictly limited by the less accurate initial search.
Despite this limitation, rescoring remains a standard technique for integrating state-of-the-art models—from early Segmental Neural Nets (Zavaliagkos et al.) to modern self-supervised models like wav2vec 2.0 (Hu et al.)—into practical, high-performance systems.
Key Foundational Work
A Hybrid Neural Net System for State-of-the-Art Continuous Speech Recognition (1992) — contributed 1 concept elements to this direction.
BBN BYBLOS and HARC February 1992 ATIS Benchmark Results (1992) — contributed 1 concept elements to this direction.
Integration of Diverse Recognition Methodologies Through Reevaluation of N-Best Sentence Hypotheses (1991) — contributed 1 concept elements to this direction.