In traditional statistical machine translation, the search for the best translation is often a process of aggressive elimination. A decoder explores a massive space of possibilities and eventually spits out a single "best" sentence or a short "n-best list" of top candidates.
The problem with this approach is that n-best lists are incredibly redundant. If a system generates 100 variations of a sentence, 90 of them might differ by only a single word or a comma. This redundancy means that high-quality candidates—those that might have scored better if a more complex model had looked at them—are often pruned away far too early.
To solve this, researchers moved toward packed representations: lattices and hypergraphs. Instead of a list of strings, these structures represent the search space as a dense web of possibilities where common sub-sequences are shared.
From Lists to Lattices
The simplest version of a packed representation is the word graph or lattice. As Nicola Ueffing, Franz Josef Och, and Hermann Ney demonstrated in Generation of Word Graphs in Statistical Machine Translation, a lattice is a directed acyclic graph where nodes represent states and edges represent word transitions.
The intuition is simple: if ten different translation hypotheses all start with "The cat sat on," the lattice stores that prefix once. The paths only diverge when the translations differ. This "path sharing" allows a lattice to store an exponential number of potential translations in a linear amount of space. Wenbin Jiang and Qun Liu showed that this compactness is not just for translation; it also allows rerankers for tasks like Chinese word segmentation to evaluate far more candidates than a flat list ever could Word Lattice Reranking for Chinese Word Segmentation and Part-of-Speech Tagging.
Scaling to Hierarchy with Hypergraphs
While lattices work for linear sequences, modern translation often involves nested, hierarchical structures—like syntax trees. To represent these, the field adopted the hypergraph (or packed forest).
In a standard graph, an edge connects two nodes. In a hypergraph, a "hyperedge" can connect a set of antecedent nodes to a single parent node, perfectly mirroring how a grammar rule combines multiple sub-phrases into a larger constituent. Philip Williams and Rico Sennrich describe this in Syntax-Based Statistical Machine Translation as a mathematical framework for managing the "exponential number of possible structural mappings" between languages.
By using hypergraphs, researchers like Yang Liu could perform joint decoding, where different types of models (e.g., phrase-based and syntax-based) "talk" to each other during the search process by mapping their rules to a shared hypergraph structure Joint Decoding with Multiple Translation Models.
Efficient Search via Cube Pruning
The challenge with a packed forest is that it is too dense. You cannot simply calculate the full score for every path because integrating a language model (LM) breaks the independence of the edges. The score of a word depends on the words that came before it, which means the "state" of the search explodes.
To handle this, Liang Huang and David Chiang introduced forest rescoring using an algorithm called cube pruning Forest Rescoring: Faster Decoding with Integrated Language Models. Instead of expanding every possible combination of words at a hypernode, cube pruning only explores the most promising "top-k" combinations in a multi-dimensional grid (a cube).
This approach was further refined by Kenneth Heafield and colleagues, who realized that many states in the hypergraph are redundant because they share the same "boundary words" that the language model cares about Grouping Language Model Boundary Words to Speed K-Best Extraction from Hypergraphs. By grouping these similar states, they achieved significant speedups without losing accuracy.
Applications Beyond Pure Translation
The power of the hypergraph/lattice framework lies in its flexibility. It acts as a "universal interface" for various translation tasks:
- System Combination: Tiejun Zhao and Yupeng Liu used hypergraphs to merge outputs from entirely different translation engines, preserving high-quality candidates that would have been lost in n-best lists Hypergraph Training and Decoding of System Combination in SMT.
- Translation Memory: Liangyou Li and Andy Way treated retrieved human translations as "constraints" within a word lattice, allowing the decoder to choose between statistical probability and exact matches from a database Phrase-Level Combination of SMT and TM Using Constrained Word Lattice.
- Interactive Translation: Jesús González-Rubio showed that hypergraphs allow for real-time human-machine collaboration, as the system can quickly find optimal "suffix completions" within the packed search space as a user types Interactive Machine Translation using Hierarchical Translation Models.
By shifting from linear lists to these graph-based abstractions, the field moved from a "generate and prune" mindset to one of "pack and optimize," enabling more complex models to operate on a vastly larger set of possibilities.