In fields like Automatic Speech Recognition (ASR) and Statistical Machine Translation (SMT), we face a fundamental tension between search and scoring.
To find the best output, a model must navigate an astronomical number of possible word sequences. A high-capacity model—like a deep Transformer or a massive neural language model—is excellent at scoring a single sequence accurately. However, running that expensive model on every possible path in a massive search tree is computationally impossible.
The solution used across decades of research is multi-pass decoding. Instead of finding the needle in the haystack in one go, we use a fast, "cheap" model to throw away the obvious hay, leaving a small pile of high-quality candidates for a "smart" model to inspect.
The Search Space Bottleneck
The core problem is that the search space for a sentence grows exponentially with its length. In early speech systems like SPHINX-II, Xuedong Huang and colleagues noted that applying complex linguistic constraints early in the process makes large-vocabulary tasks unfeasible.
If you have a vocabulary of 100,000 words, a simple trigram model already has $10^{15}$ possible states. A neural network, which requires a heavy forward pass for every state transition, simply cannot be used to explore this entire space in real-time. As Holger Schwenk pointed out in Building a Statistical Machine Translation System for French, the computational cost of neural models prevents their direct use during the initial decoding phase.
Pass 1: Pruning the Haystack
The first pass uses a simplified model—often a pruned n-gram model or a lightweight HMM—to generate a restricted set of hypotheses. This stage doesn't need to be perfect; it just needs to be inclusive. It must ensure that the "correct" answer is somewhere in its output.
This output typically takes two forms:
- N-best Lists: A ranked list of the top $N$ complete sequences (e.g., the top 100 translations).
- Word Lattices (Graphs): A directed acyclic graph representing many possible paths. Nicola Ueffing, Franz Josef Och, and Hermann Ney demonstrated in Generation of Word Graphs in Statistical Machine Translation that these graphs are much more efficient than N-best lists because they capture a dense set of alternatives in a compact structure.
By using a "fast" pass to generate these structures, researchers like Ciprian Chelba at Google showed that systems can leverage massive language models trained on billions of words without the prohibitive cost of searching the full state space.
Pass 2: Rescoring and Reranking
Once the search space is narrowed to a lattice or an N-best list, the "expensive" model takes over. This is called rescoring or reranking.
Because the second pass only looks at a few hundred or thousand candidates, it can afford to use features that are "non-local" or computationally intensive:
- Continuous Space Language Models (CSLM): Early neural networks that represent words as vectors to solve data sparseness, as explored by Holger Schwenk in Continuous-Space Language Models for Statistical Machine Translation.
- Segmental Neural Nets (SNN): Models that look at entire phonetic segments rather than isolated frames, which George Zavaliagkos and John Makhoul used to reduce error rates by 25% in 1992.
- Modern Transformers: Even in the era of deep learning, Christoph Lüscher and colleagues found that using a high-capacity Transformer to rescore lattices from a faster hybrid model remains a state-of-the-art strategy.
Why It Works: The Oracle Intuition
The reason this two-stage approach is so effective is that the "Oracle" accuracy of the first pass—the accuracy you would get if you perfectly picked the best candidate from the N-best list—is usually much higher than the accuracy of the first-pass's top choice.
As Eun-Ah Cho and Jan Niehues argued in Analyzing Neural MT Search and Model Performance, the initial search space almost always contains high-quality options. The failure of single-pass systems isn't usually that they can't generate the right answer, but that they lack the discriminative power to recognize it during the heat of the search.
By decoupling candidate generation from candidate evaluation, multi-pass decoding allows each part of the system to do what it does best: the first pass handles the breadth of the language, while the second pass handles its depth. This paradigm has shifted from simple n-gram rescoring to sophisticated "quality-aware" decoding, where Patrick Fernandes and Graham Neubig use heavy metrics like COMET and BLEURT to rerank translations, proving that the two-pass architecture remains the standard for pushing the boundaries of sequence modeling.