Traditional machine translation systems treat a document as an disconnected sequence of isolated sentences. This "sentence-as-an-island" paradigm relies on incremental decoding algorithms, such as beam search or dynamic programming, which construct translations word-by-word from left to right.
While highly effective for local fluency, incremental decoding struggles with document-wide properties. If a decoder must choose the correct translation for an ambiguous pronoun or a technical term in sentence 5, it cannot easily evaluate how that choice aligns with sentences 1 or 10 because those sentences are processed independently. To resolve cross-sentence dependencies, a translation system needs a global view of the entire text during the decoding process.
As Zhengxian Gong et al. demonstrated in Improve SMT with Source-Side "Topic-Document" Distributions, attempting to enforce document-level constraints post-hoc—such as reranking an $N$-best list of completed translations—is fundamentally limited. By the time an $N$-best list is generated, the sentence-level decoder has already discarded many paths that might have been globally optimal. True document-level translation requires integrating global context directly into the search process itself.
Shifting to Complete-State Space
To evaluate global features during decoding, researchers introduced a paradigm shift: complete-state decoding. Instead of building a translation incrementally, the decoder operates on a fully formed, complete translation hypothesis of the entire text, iteratively modifying it to maximize a global objective function.
The foundational mechanics of this approach were explored at the sentence level by Philippe Langlais et al. In A greedy decoder for phrase-based statistical machine translation and Recherche locale pour la traduction statistique à base de segments, the authors introduced greedy local search decoders (such as feGreedy). Rather than searching for a path through a graph, these decoders take an initial, complete sentence translation (often generated by a fast baseline decoder) and apply local search to refine it, demonstrating that optimizing complete states can match or exceed the performance of traditional beam search at a fraction of the computational cost.
Incremental Decoding (Beam Search):
[Start] -> [Word 1] -> [Word 2] -> [Word 3] -> ... (No global context available yet)
Complete-State Decoding (Local Search):
[Initial Complete Document State]
│
▼ (Iterative Mutations: Swap phrases, change words)
[Optimized Complete Document State] (Evaluates global context at every step)
Christian Hardmeier et al. scaled this concept to encompass entire texts in Document-Wide Decoding for Phrase-Based Statistical Machine Translation. In this framework, the decoder initializes a complete translation for every sentence in a document simultaneously. It then uses stochastic local search—such as hill climbing or simulated annealing—to explore the space of alternative document translations.
Mechanics of Document-Wide Local Search
To navigate the massive search space of an entire document, the decoder applies small, stochastic operations to the current document state. As detailed by Sara Stymne et al. in Tunable Distortion Limits and Corpus Cleaning for SMT, these local modifications typically include:
- Changing a translation: Replacing a target phrase with an alternative from the translation table.
- Swapping phrases: Altering the word order within a sentence to improve reordering.
- Merging or splitting phrases: Re-segmenting the source sentence into different phrase alignments.
This architecture was formalized in an open-source document-level decoder called Docent, developed by Christian Hardmeier et al. and presented in Docent: A Document-Level Decoder for Phrase-Based Statistical Machine Translation. Because Docent maintains the state of the entire document at every step of the search, it can compute non-local scoring functions that are mathematically impossible to integrate into a standard word-by-word decoder. For example, Aaron Smith et al. demonstrated in Climbing Mont BLEU: The Strange World of Reachable High-BLEU Translations that this complete-state approach allows a system to directly optimize for document-wide evaluation metrics like BLEU during the search itself.
Unlocking Global Discourse Features
Operating on a complete document state allows researchers to design features that enforce long-range consistency and discourse structure across sentence boundaries.
Cross-Sentence Anaphora Resolution
In Baseline Models for Pronoun Prediction and Pronoun-Aware Translation, Jörg Tiedemann highlighted how traditional systems fail to translate pronouns accurately when their antecedents reside in previous sentences. By utilizing document-level local search, Christian Hardmeier et al. successfully integrated cross-sentence anaphora models in Anaphora Models and Reordering for Phrase-Based SMT, ensuring that translated pronouns grammatically agree with antecedents across sentence boundaries.
Lexical Consistency and Context
Short, ambiguous texts like tweets heavily rely on surrounding context for accurate translation. Cristina España-Bonet et al. demonstrated in The UPC TweetMT participation: Translating Formal Tweets Using Context Information that treating a stream of related segments as a single document helps resolve local lexical ambiguities. By incorporating distributed representations, such as bilingual word embeddings, into a document-level decoder, the authors further improved semantic accuracy and terminology consistency across sentence boundaries (Document-Level Machine Translation with Word Vector Models).
Document-Wide Constraints
Document-level decoding also allows systems to optimize for global stylistic properties. In Statistical Machine Translation with Readability Constraints, Jörg Tiedemann et al. integrated readability metrics and vocabulary density constraints directly into the objective function. The local search strategy iteratively adjusted phrase choices across the entire text to tailor the translation's complexity for specific target audiences.
Escaping Local Optima with Multi-Occurrence Moves
A significant challenge of applying hill-climbing search to a document is the presence of local optima. If a technical term appears ten times in a text, changing just a single instance to a more consistent translation might temporarily lower that individual sentence's local translation score, causing the decoder to reject the move. Consequently, standard local search becomes trapped.
Local Optima Trap:
[Term translated inconsistently] ──(Change 1 instance)──> [Lower Local Score] ──> REJECTED
Multi-Occurrence Move:
[Term translated inconsistently] ──(Change ALL instances)──> [Higher Global Score] ──> ACCEPTED
To overcome this, Eva Martínez García et al. introduced specialized decoding operations in Using Word Embeddings to Enforce Document-Level Lexical Consistency in Machine Translation. Their approach tracks the repetition of terms throughout a text and introduces a "multi-occurrence" move that changes all instances of a term simultaneously across multiple sentences. This global update allows the search process to bypass local score drops and transition directly to a globally consistent document state that would otherwise be unreachable through incremental changes.
Extension to Neural Architectures
The core intuition of complete-state refinement is not restricted to phrase-based statistical machine translation; it also extends to neural network architectures. For example, in Microsoft Translator at WMT 2019: Towards Large-Scale Document-Level Neural Machine Translation, Marcin Junczys-Dowmunt implemented a two-stage decoding process for neural machine translation (NMT). The system first generates a complete draft at the sentence level using standard methods, and then refines that draft in a second pass using document-level context to maximize overall coherence and consistency.
Key Foundational Work
Recherche locale pour la traduction statistique à base de segments (2008) — contributed 1 concept elements to this direction.
A greedy decoder for phrase-based statistical machine translation (2007) — contributed 1 concept elements to this direction.