Abstract
Syntactic machine translation models often suffer from extreme computational complexity when integrated with n-gram language models (LMs). This paper presents a multipass, coarse-to-fine decoding approach that incrementally introduces language model complexity. By utilizing hierarchical word clusters—termed "language projections"—the decoder can efficiently prune the search space in early, abstract passes. Experimental results across multiple language pairs demonstrate speed-ups of up to 50 times over single-pass decoding while simultaneously improving BLEU scores.
Introduction: The Lexical Explosion Problem
In syntactic machine translation, translation is modeled as a parsing problem where a tree of the target language is constructed to correspond to the source language. While efficient on its own, producing natural-sounding output requires integration with an n-gram language model. This integration creates a massive computational bottleneck known as "lexical explosion."
To calculate phrase probabilities, the decoder must track boundary words for every hypothesis to ensure grammatical connectivity. This turns a manageable search space into a gargantuan one. Traditional solutions, such as bigram-to-trigram decoding, often fail to provide sufficient speed because even a bigram model with a full vocabulary remains too large for rapid processing.
Methodology: Language Projections
The core innovation of this work is a coarse-to-fine decoding strategy that operates along two orthogonal axes of abstraction: language model order and word bit-depth.
Hierarchical Clustering
Instead of decoding with the full vocabulary immediately, the authors map words into hierarchical clusters represented as a binary tree. A "1-bit" encoding might split the entire language into just two broad categories (e.g., function words vs. content words), while a "10-bit" encoding provides 1,024 distinct clusters. This allows the decoder to work with a drastically reduced set of "words" in early passes.
Multi-pass Decoding and Posterior Pruning
The system performs a sequence of decoding passes. The initial pass uses a very coarse model (e.g., a 2-cluster bigram model), which is computationally inexpensive. Following each coarse pass, the algorithm calculates the posterior probability of each state. States that are highly unlikely in the coarse representation are pruned, ensuring they are never considered in the subsequent, more expensive fine-grained passes.
Key Results
The researchers evaluated the approach using the Europarl corpus for Spanish-to-English, French-to-English, and German-to-English translation.
Performance and Efficiency
The coarse-to-fine approach achieved speedups of up to 50x compared to standard single-pass decoders. Remarkably, the entire multi-pass cascade was often faster than just the initial bigram pass of traditional two-pass decoders.
Beyond speed, the approach also yielded a surprising improvement in translation quality, with BLEU scores increasing by approximately 0.4 points. This suggests that by pruning the search space intelligently, the decoder can afford to maintain a wider "beam" of possibilities in the final pass than a single-pass decoder could manage within the same time constraints.
Conclusion
By focusing on vocabulary size as the primary driver of complexity, language projections provide a powerful mechanism for accelerating syntactic machine translation. The ability to prune the search space using abstract language representations allows for high-quality translation at a fraction of the traditional computational cost. Future work may explore the theoretical risks of pruning and the potential for these coarse models to act as beneficial secondary signals for translation quality.
Summary updated