Multi-Pass Decoding for Large Vocabulary Sequence Tasks

This direction is split into other directions: n-best list rescoring. Its last version stays readable and citable here.

Version 1 of 197 papers120 conceptsfrozen 2026-10-04

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:

  1. N-best Lists: A ranked list of the top $N$ complete sequences (e.g., the top 100 translations).
  2. 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:

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.

Papers in this version

Showing 60 of 97 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_multi_pass_decoding_for_large_vocabulary_ae257417,
  title = {Multi-Pass Decoding for Large Vocabulary Sequence Tasks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-pass-decoding-for-large-vocabulary-sequence-tasks/rdr_ae257417cdfe417c9debc63feed72cfd},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_multi_pass_decoding_for_large_vocabulary_ae257417_v1,
  title = {Multi-Pass Decoding for Large Vocabulary Sequence Tasks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-pass-decoding-for-large-vocabulary-sequence-tasks/rdr_ae257417cdfe417c9debc63feed72cfd/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}