--- title: "Decoding complexity in word-replacement translation models" description: "Kevin Knight examines how computationally hard decoding is in statistical machine translation built on… 3 references, cited by 81 papers here." authors: ["Kevin Knight"] year: 1999 venue: "Computational Linguistics" source: "https://aclanthology.org/J99-4005/" licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/" summary_licence: "Elamur Cosmic License" canonical: "https://research.elamur.ai/free/en/papers/knight-1999-decoding-complexity-word-replacement-translation/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/knight-1999-decoding-complexity-word-replacement-translation/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1999](https://md.research.elamur.ai/free/en/papers/1999/) / Decoding complexity in word-replacement translation models # Decoding complexity in word-replacement translation models **Authors:** [Kevin Knight](https://md.research.elamur.ai/free/en/authors/kevin-knight/) · **Year:** 1999 · **Venue:** [Computational Linguistics](https://md.research.elamur.ai/free/en/venues/cl/) ([Computational Linguistics 1999](https://md.research.elamur.ai/free/en/venues/cl/1999/)) · **Publisher:** [The MIT Press](https://md.research.elamur.ai/free/en/publishers/the-mit-press/) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/) **Links:** [Publisher's page](https://aclanthology.org/J99-4005/) · [PDF](https://aclanthology.org/J99-4005.pdf) · [OpenAlex](https://openalex.org/W1555286493) **Citations:** 258 citations (OpenAlex, 2026-10-14) · [81](https://md.research.elamur.ai/free/en/papers/knight-1999-decoding-complexity-word-replacement-translation/cited-by/) in our library, of the 141,840 papers whose bibliographies we read ## Summary Kevin Knight examines how computationally hard decoding is in statistical machine translation built on the source-channel framework of Brown et al. (1993). In that setup, a bigram source model generates English, and a channel model turns it into French. Decoding means searching for the most probable English source of a given French sentence. He first contrasts translation with part-of-speech tagging and letter-substitution ciphers, where dynamic programming gives efficient training and decoding. He then turns to IBM Model 1. Its training cost can be made polynomial with an algebraic rearrangement of the sum over alignments. Decoding, however, is a different matter. Knight states a decision version of Model 1 decoding (M1-DECIDE) and proves it NP-complete, using two separate polynomial reductions. One comes from the Hamilton Circuit Problem and captures the difficulty of choosing word order. The other comes from Minimum Set Cover and captures the difficulty of choosing a compact set of source words when dictionary entries overlap. This worst-case result explains why MT systems rely on heuristic search such as beam search, or on restricted channel models. ## Key points - The paper compares several costs: - POS tagging decoding takes O(mv²) with dynamic programming, versus naive enumeration of O(v^m) tag sequences. - Model 1 EM training drops from naive O(ml^m) to O(lm) per sentence pair. - Naive Model 1 decoding, with English length capped at 2m, costs O(m²v^(2m)). - M1-DECIDE asks whether some English string of length at most 2m reaches a score P(e)·P(f|e) above k. It belongs to NP because a guessed candidate can be checked in O(m²) time. - The two proofs isolate distinct sources of hardness: - Word ordering arises from the source model and is related to the Traveling Salesman Problem. - Concise word selection arises from the channel model and is related to Minimum Set Cover. - The intractability result carries over to fertility/distortion models (IBM Models 2–5). This follows by allowing only fertility 1 and making distortion tables uniform. - Knight points to optimism from Traveling Salesman research, where heuristics often come within 2% of the optimal tour and the best possible route through more than 13,000 U.S. cities has been computed. He cautions that those results depend on symmetry and the triangle inequality, which word ordering lacks. He also notes that costly decoding suggests costly training from monolingual text. *Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.* ## Institutions - [University of Southern California](https://md.research.elamur.ai/free/en/universities/university-of-southern-california/) — University, Los Angeles, United States · 104 works · 33,876 citations 📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,086 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,889 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works 🧭 Topics (1): [🔁 Machine translation](https://md.research.elamur.ai/free/en/topics/machine-translation/) · 958 works ## Cite Cite as: Kevin Knight. 1999. Decoding complexity in word-replacement translation models. Computational Linguistics. The paper itself, not this page. BibTeX from the library's record of the work. ```bibtex @article{knight1999decoding, title = {{Decoding complexity in word-replacement translation models}}, author = {Kevin Knight}, journal = {Computational Linguistics}, year = {1999}, url = {https://aclanthology.org/J99-4005/} } ``` - [← previous Automatic construction of a hypernym-labeled noun hierarchy from text](https://md.research.elamur.ai/free/en/papers/caraballo-1999-automatic-construction-hypernym-labeled-noun/) - [next → Mining the Web for Bilingual Text](https://md.research.elamur.ai/free/en/papers/resnik-1999-mining-web-bilingual-text/) - [↑ back to papers of 1999](https://md.research.elamur.ai/free/en/papers/1999/) ## References 3 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet. 1. Brew, Chris. 1992. Letting the cat out of the bag: Generation for shake-and-bake MT. In Proceedings of the 14th International Conference on Computational Linguistics (COLING), pages 610-616, Nantes, France, August. [find](https://scholar.google.com/scholar?q=Brew%2C+Chris%2E+1992%2E+Letting+the+cat+out+of+the+bag%3A+Generation+for+shake%2Dand%2Dbake+MT%2E+In+Proceedings+of+the+14th+International+Conference+on+Computational+Linguistics+%28COLING%29%2C+pages+610%2D616%2C+Nantes%2C+F) 2. Brown, Peter, Stephen Della-Pietra, Vincent Della-Pietra, and Robert Mercer. 1993. The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics, 19(2):263-311. [find](https://scholar.google.com/scholar?q=Brown%2C+Peter%2C+Stephen+Della%2DPietra%2C+Vincent+Della%2DPietra%2C+and+Robert+Mercer%2E+1993%2E+The+mathematics+of+statistical+machine+translation%3A+Parameter+estimation%2E+Computational+Linguistics%2C+19%282%29%3A263%2D311%2E) 3. Church, Kenneth. 1988. A stochastic parts program and noun phrase parser for unrestricted text. In Proceedings of the 2nd Conference on Applied Natural Language Processing, pages 136-143, Austin, TX, June. [our card](https://md.research.elamur.ai/free/en/papers/church-1988-stochastic-parts-program-noun-phrase/) *Updated 24 October 2026*