📄 Forest Rescoring: Faster Decoding with Integrated Language Models

Summary

Decoding in statistical machine translation is costly when an n-gram language model is built directly into the search, because every partial hypothesis must track target-side boundary words. Plain k-best rescoring is cheap but misses many good translations. Huang and Chiang place both phrase-based and SCFG/tree-to-string decoding in a single hypergraph (forest) framework. Within it, they generalize cube pruning, which keeps only the top k +LM items at each forest node and enumerates them roughly best-first. They also introduce cube growing, a lazy variant that computes only as many items per node as the root actually needs. Together these are called forest rescoring. On large English-to-Chinese tasks, they compare against beam-search full integration at matched search error and BLEU:

• In their phrase-based decoder (Cubit), cube pruning is more than ten times faster.
• In their tree-to-string system, cube growing gives a speed-up of up to 9.8×.

The work matters because it makes LM-integrated decoding much faster across very different translation models. It also suggests a general strategy for combining expensive models during search.

Key points

• Unified view: phrase-based and syntax-based decoding are both framed as deduction over a −LM forest (graph or hypergraph). +LM items add boundary words: the last word for phrase-based, the left and right words (a⋆b) for SCFG. Experiments use trigram LMs.
• Phrase-based setup:
  • Decoder: Cubit, which reproduces Pharaoh (BLEU always within 0.004).
  • Test data: 140 sentences drawn from the NIST 2003 test set.
  • Limits: phrase-table limit 100 and distortion limit 4.
  • Result: cube pruning is over 10× faster at every search-quality level and 32× faster at the lowest search-error level.
• Tree-to-string setup:
  • Source side parsed with a Collins (1997)-style parser.
  • 24.7M rules extracted using the Galley et al. (2006) method.
  • Forest hyperedges binarized on the target side before decoding.
• Tree-to-string speed-ups: at the lowest search-error level, cube growing is 9.8× and cube pruning 4.1× faster than full integration. Measured in BLEU, the gains look even larger.
• Cube growing heuristic: it relies on lower-bound heuristics taken from the 100 best unique −LM translations. Computing these costs about 0.12 seconds per sentence, which is negligible.

Interesting ideas

• I1. Cheap model first, costly model on top: first build a compact forest using only the cheap model, then apply the expensive model inside the forest rather than only on a final k-best list. This middle ground suits any pipeline that joins a fast structural model with a slow scoring model, such as parsing with non-local features or joint tagging and parsing.
• I2. Best-first grid exploration: combine sorted lists from child nodes by expanding a grid best-first from its top-left corner. This finds near-top combinations without scoring all pairs, which helps wherever top-k results must be built from several ranked sub-results.
• I3. Buffer and re-sort: an interaction cost (here the LM) can make the grid non-monotonic, so items may come out in the wrong order. Collecting k items in a buffer and sorting them afterwards is a cheap repair worth reusing in approximate k-best merges.
• I4. Lazy, demand-driven computation: cube growing computes only as many items at each node as the final output requires, guided by estimates from the cheap model. Laziness of this kind generalizes to any hierarchical search where most intermediate candidates are never used.
• I5. Fair efficiency comparison: methods are compared on curves of search quality (model cost or BLEU) against work done (hypotheses or items explored), not at a single setting. This gives a fair basis for judging approximate search methods.