---
title: "cdec — paper by Dyer et al. (2010)"
description: "The paper presents cdec, an Apache-licensed C++ framework. 31.6 BLEU. 28 references, cited by 150 papers here."
authors: ["Chris Dyer", "Adam Lopez", "Juri Ganitkevitch", "Jonathan Weese", "Ferhan Ture", "Phil Blunsom", "Hendra Setiawan", "Vladimir Eidelman", "Philip Resnik"]
year: 2010
venue: "Proceedings of the ACL 2010 System Demonstrations"
source: "https://aclanthology.org/P10-4002/"
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/dyer-2010-cdec-decoder-alignment-learning-framework/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/dyer-2010-cdec-decoder-alignment-learning-framework/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2010](https://md.research.elamur.ai/free/en/papers/2010/) / cdec: A Decoder, Alignment, and Learning Framework for Finite-State and Context-Free Translation Models

# cdec: A Decoder, Alignment, and Learning Framework for Finite-State and Context-Free Translation Models

**Authors:** [Chris Dyer](https://md.research.elamur.ai/free/en/authors/chris-dyer/), [Adam Lopez](https://md.research.elamur.ai/free/en/authors/adam-lopez/), [Juri Ganitkevitch](https://md.research.elamur.ai/free/en/authors/juri-ganitkevitch/), [Jonathan Weese](https://md.research.elamur.ai/free/en/authors/jonathan-weese/), Ferhan Ture, [Phil Blunsom](https://md.research.elamur.ai/free/en/authors/phil-blunsom/), [Hendra Setiawan](https://md.research.elamur.ai/free/en/authors/hendra-setiawan/), [Vladimir Eidelman](https://md.research.elamur.ai/free/en/authors/vladimir-eidelman/) and [Philip Resnik](https://md.research.elamur.ai/free/en/authors/philip-resnik/) · **Year:** 2010 · **Venue:** [Proceedings of the ACL 2010 System Demonstrations](https://md.research.elamur.ai/free/en/venues/acl/) ([ACL 2010](https://md.research.elamur.ai/free/en/venues/acl/2010/)) · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **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/P10-4002/) · [PDF](https://aclanthology.org/P10-4002.pdf) · [OpenAlex](https://openalex.org/W2155607551)

**Citations:** 224 citations (OpenAlex, 2026-10-14) · [150](https://md.research.elamur.ai/free/en/papers/dyer-2010-cdec-decoder-alignment-learning-framework/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## Summary
The authors address a practical obstacle in statistical machine translation research. Existing open-source decoders such as Moses and Joshua mix translation logic, language-model integration, and pruning in one codebase. They also assume only a handful of dense features. This makes new models hard to prototype and hard to compare fairly. The paper presents cdec, an Apache-licensed C++ framework. In cdec, model-specific code only has to build a translation forest, stored as a hypergraph. Word-based, phrase-based, SCFG, and tagging models all produce this same structure. Generic components then operate on it: rescoring with FST-like models such as n-gram language models, pruning, k-best extraction, alignment against a reference, and training. Training can use MERT (here called VEST) or gradient-based optimization of conditional likelihood, which supports millions of sparse features. On a Chinese-English hierarchical phrase-based task, cdec reaches the same BLEU as Joshua and Hiero. It is faster than single-threaded Joshua and the Python Hiero, and it needs the least memory. The work matters because it provides one reusable infrastructure for decoding, aligning, and learning across model families.

## Key points
- **Two-stage pipeline:**
  - Stage 1 converts the input into a hypergraph and then rescores it. The input can be a sentence, a lattice, or a source-side CFG forest.
  - Rescoring offers three intersection strategies: full intersection, cube pruning, and cube growing.
  - Stage 2 extracts outputs from the rescored forest: 1-best or k-best derivations, feature expectations, or an alignment forest obtained by parsing the target reference.
- **Semiring framework:**
  - Most quantities are computed in time linear in the size of the hypergraph, using a semiring framework.
  - In C++, a semiring is just a type with `+=`, `*=`, a default constructor, and `T(1)`, so built-in types like double, int, and bool qualify.
  - The library adds a log-space `prob_t` type and a first-order expectation semiring.
- **Training:**
  - VEST runs MERT over the full hypergraph rather than over k-best lists.
  - Discriminative training maximizes conditional log likelihood. Both the objective and its gradient are a difference between computations on the alignment hypergraph and on the translation hypergraph.
  - The batch pipeline is split into map and reduce steps. Supported optimizers are LBFGS, RPROP, and SGD.
- **Experimental setup:** NIST MT03 Chinese-English, with a grammar from a suffix-array rule extractor. All decoders used a span limit of 15, cube pruning with 30 candidates per node, and the SRI LM toolkit. Every system scored between 31.4 and 31.6 BLEU.
- **Speed and memory (per sentence):**

  | Decoder | Time | Memory |
  |---|---|---|
  | cdec | 0.37 s | 1.0 GB |
  | Joshua, 1 thread | 0.98 s | 1.5 GB |
  | Joshua, 8 threads | 0.35 s | 2.5 GB |
  | Hiero (Python) | 4.04 s | 1.1 GB |

## Interesting ideas
- **Separate search-space construction from scoring.** Models only emit an unscored forest, and shared code handles language-model integration and pruning. Any new pruning or inference method then benefits every model at once, and comparisons between models become controlled. This design fits any structured-prediction toolkit, for example taggers or parsers for Ukrainian.
- **Treat alignment as parsing the reference with the translation forest.** The decoder's own search space is reused to find how a known output could be derived. This avoids writing a separate aligner and gives a natural sanity check when a model cannot produce a reference.
- **Express training as "clamped minus free".** The likelihood and its gradient come from running the same inside or expectation computation on two hypergraphs: one constrained to the reference and one unconstrained. A single inference routine thus serves both decoding and learning. With sequence models, this reduces exactly to CRF training.
- **Define a semiring as a type with overloaded operators.** One generic algorithm then yields many quantities, such as derivation counts, expectations, entropy, or Viterbi scores, simply by swapping the value type. A log-space type removes underflow problems. The pattern is cheap to adopt in any dynamic-programming code.
- **Make decoding the map step of training.** Running the decoder as the map function and optimization as the reduce step lets expensive gradient-based training scale across a cluster. This suits any objective that decomposes over sentences.

*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 Edinburgh](https://md.research.elamur.ai/free/en/universities/university-of-edinburgh/) — University, Edinburgh, United Kingdom · 255 works · 68,771 citations
- [Johns Hopkins University](https://md.research.elamur.ai/free/en/universities/johns-hopkins-university/) — University, Baltimore, United States · 187 works · 92,194 citations
- [University of Oxford](https://md.research.elamur.ai/free/en/universities/university-of-oxford/) — University, Oxford, United Kingdom · 52 works · 154,829 citations
- [University of Maryland, College Park](https://md.research.elamur.ai/free/en/universities/university-of-maryland-college-park/) — University, College Park, United States · 83 works · 23,784 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: Chris Dyer, Adam Lopez, Juri Ganitkevitch, Jonathan Weese, Ferhan Ture, Phil Blunsom, Hendra Setiawan, Vladimir Eidelman and Philip Resnik. 2010. cdec: A Decoder, Alignment, and Learning Framework for Finite-State and Context-Free Translation Models. Proceedings of the ACL 2010 System Demonstrations.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{dyer2010cdec,
  title = {{cdec: A Decoder, Alignment, and Learning Framework for Finite-State and Context-Free Translation Models}},
  author = {Chris Dyer, Adam Lopez, Juri Ganitkevitch, Jonathan Weese, Ferhan Ture, Phil Blunsom, Hendra Setiawan, Vladimir Eidelman and Philip Resnik},
  booktitle = {Proceedings of the ACL 2010 System Demonstrations},
  year = {2010},
  url = {https://aclanthology.org/P10-4002/}
}
```

- [← previous Entity Disambiguation for Knowledge Base Population](https://md.research.elamur.ai/free/en/papers/dredze-2010-entity-disambiguation-knowledge-base-population/)
- [next → The CoNLL-2010 Shared Task: Learning to Detect Hedges and their Scope in Natural Language Text](https://md.research.elamur.ai/free/en/papers/farkas-2010-conll-2010-shared-task-learning/)
- [↑ back to papers of 2010](https://md.research.elamur.ai/free/en/papers/2010/)

## References

28 references, 8 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. P. Blunsom and M. Osborne. 2008. Probalistic inference for machine translation. In Proc. of EMNLP. [find](https://scholar.google.com/scholar?q=P%2E+Blunsom+and+M%2E+Osborne%2E+2008%2E+Probalistic+inference+for+machine+translation%2E+In+Proc%2E+of+EMNLP%2E)
2. P. Blunsom, T. Cohn, and M. Osborne. 2008. A discriminative latent variable model for statistical machine translation. In Proc. of ACL-HLT. [our card](https://md.research.elamur.ai/free/en/papers/blunsom-2008-discriminative-latent-variable-model-statistical/)
3. P. F. Brown, V. J. Della Pietra, S. A. Della Pietra, and R. L. Mercer. 1993. The mathematics of statistical machine translation: parameter estimation. Computational Linguistics, 19(2):263–311. [find](https://scholar.google.com/scholar?q=P%2E+F%2E+Brown%2C+V%2E+J%2E+Della+Pietra%2C+S%2E+A%2E+Della+Pietra%2C+and+R%2E+L%2E+Mercer%2E+1993%2E+The+mathematics+of+statistical+machine+translation%3A+parameter+estimation%2E+Computational+Linguistics%2C+19%282%29%3A263%E2%80%93311%2E)
4. D. Chiang, K. Knight, and W. Wang. 2009. 11,001 new features for statistical machine translation. In Proc. of NAACL, pages 218–226. [find](https://scholar.google.com/scholar?q=D%2E+Chiang%2C+K%2E+Knight%2C+and+W%2E+Wang%2E+2009%2E+11%2C001+new+features+for+statistical+machine+translation%2E+In+Proc%2E+of+NAACL%2C+pages+218%E2%80%93226%2E)
5. D. Chiang. 2007. Hierarchical phrase-based translation. Comp. Ling., 33(2):201–228. [our card](https://md.research.elamur.ai/free/en/papers/chiang-2007-hierarchical-phrase-based-translation/)
6. J. Dean and S. Ghemawat. 2004. MapReduce: Simplified data processing on large clusters. In Proc. of the 6th Symposium on Operating System Design and Implementation (OSDI 2004), pages 137–150. [find](https://scholar.google.com/scholar?q=J%2E+Dean+and+S%2E+Ghemawat%2E+2004%2E+MapReduce%3A+Simplified+data+processing+on+large+clusters%2E+In+Proc%2E+of+the+6th+Symposium+on+Operating+System+Design+and+Implementation+%28OSDI+2004%29%2C+pages+137%E2%80%93150%2E)
7. C. Dyer and P. Resnik. 2010. Context-free reordering, finite-state translation. In Proc. of HLT-NAACL. [find](https://scholar.google.com/scholar?q=C%2E+Dyer+and+P%2E+Resnik%2E+2010%2E+Context%2Dfree+reordering%2C+finite%2Dstate+translation%2E+In+Proc%2E+of+HLT%2DNAACL%2E)
8. C. Dyer, S. Muresan, and P. Resnik. 2008. Generalizing word lattice translation. In Proc. of HLT-ACL. [our card](https://md.research.elamur.ai/free/en/papers/dyer-2008-generalizing-word-lattice-translation/)
9. C. Dyer. 2010. Two monolingual parses are better than one (synchronous parse). In Proc. of HLT-NAACL. [find](https://scholar.google.com/scholar?q=C%2E+Dyer%2E+2010%2E+Two+monolingual+parses+are+better+than+one+%28synchronous+parse%29%2E+In+Proc%2E+of+HLT%2DNAACL%2E)
10. L. Huang and D. Chiang. 2005. Better k-best parsing. In In Proc. of IWPT, pages 53–64. [find](https://scholar.google.com/scholar?q=L%2E+Huang+and+D%2E+Chiang%2E+2005%2E+Better+k%2Dbest+parsing%2E+In+In+Proc%2E+of+IWPT%2C+pages+53%E2%80%9364%2E)
11. L. Huang and D. Chiang. 2007. Forest rescoring: Faster decoding with integrated language models. In Proc. ACL. [our card](https://md.research.elamur.ai/free/en/papers/huang-2007-forest-rescoring-faster-decoding-integrated/)
12. L. Huang, K. Knight, and A. Joshi. 2006. A syntax-directed translator with extended domain of locality. In Proc. of AMTA. [find](https://scholar.google.com/scholar?q=L%2E+Huang%2C+K%2E+Knight%2C+and+A%2E+Joshi%2E+2006%2E+A+syntax%2Ddirected+translator+with+extended+domain+of+locality%2E+In+Proc%2E+of+AMTA%2E)
13. P. Koehn, F. J. Och, and D. Marcu. 2003. Statistical phrase-based translation. In Proc. of HLT/NAACL, pages 48–54. [find](https://scholar.google.com/scholar?q=P%2E+Koehn%2C+F%2E+J%2E+Och%2C+and+D%2E+Marcu%2E+2003%2E+Statistical+phrase%2Dbased+translation%2E+In+Proc%2E+of+HLT%2FNAACL%2C+pages+48%E2%80%9354%2E)
14. P. Koehn, H. Hoang, A. B. Mayne, C. Callison-Burch, M. Federico, N. Bertoldi, B. Cowan, W. Shen, C. Moran, R. Zens, C. Dyer, O. Bojar, A. Constantin, and E. Herbst. 2007. Moses: Open source toolkit for statistical machine translation. In Proc. of ACL, Demonstration Session, pages 177–180, June. [find](https://scholar.google.com/scholar?q=P%2E+Koehn%2C+H%2E+Hoang%2C+A%2E+B%2E+Mayne%2C+C%2E+Callison%2DBurch%2C+M%2E+Federico%2C+N%2E+Bertoldi%2C+B%2E+Cowan%2C+W%2E+Shen%2C+C%2E+Moran%2C+R%2E+Zens%2C+C%2E+Dyer%2C+O%2E+Bojar%2C+A%2E+Constantin%2C+and+E%2E+Herbst%2E+2007%2E+Moses%3A+Open+source+toolkit+fo)
15. S. Kumar, W. Macherey, C. Dyer, and F. Och. 2009. Efficient minimum error rate training and minimum B ayes-risk decoding for translation hypergraphs and lattices. In Proc. of ACL, pages 163–171. [find](https://scholar.google.com/scholar?q=S%2E+Kumar%2C+W%2E+Macherey%2C+C%2E+Dyer%2C+and+F%2E+Och%2E+2009%2E+Efficient+minimum+error+rate+training+and+minimum+B+ayes%2Drisk+decoding+for+translation+hypergraphs+and+lattices%2E+In+Proc%2E+of+ACL%2C+pages+163%E2%80%93171%2E)
16. Z. Li and J. Eisner. 2009. First- and second-order expectation semirings with applications to minimum-risk training on translation forests. In Proc. of EMNLP, pages 40–51. [our card](https://md.research.elamur.ai/free/en/papers/li-2009-first-second-order-expectation-semirings/)
17. Z. Li, C. Callison-Burch, C. Dyer, J. Ganitkevitch, S. Khudanpur, L. Schwartz, W. N. G. Thornton, J. Weese, and O. F. Zaidan. 2009. Joshua: an open source toolkit for parsing-based machine translation. In Proc. of the Fourth Workshop on Stat. Machine Translation, pages 135–139. [our card](https://md.research.elamur.ai/free/en/papers/li-2009-joshua-open-source-toolkit-parsing/)
18. D. C. Liu, J. Nocedal, D. C. Liu, and J. Nocedal. 1989. On the limited memory BFGS method for large scale optimization. Mathematical Programming B, 45(3):503–528. [find](https://scholar.google.com/scholar?q=D%2E+C%2E+Liu%2C+J%2E+Nocedal%2C+D%2E+C%2E+Liu%2C+and+J%2E+Nocedal%2E+1989%2E+On+the+limited+memory+BFGS+method+for+large+scale+optimization%2E+Mathematical+Programming+B%2C+45%283%29%3A503%E2%80%93528%2E)
19. A. Lopez. 2007. Hierarchical phrase-based translation with suffix arrays. In Proc. of EMNLP, pages 976–985. [find](https://scholar.google.com/scholar?q=A%2E+Lopez%2E+2007%2E+Hierarchical+phrase%2Dbased+translation+with+suffix+arrays%2E+In+Proc%2E+of+EMNLP%2C+pages+976%E2%80%93985%2E)
20. A. Lopez. 2008. Statistical machine translation. ACM Computing Surveys, 40(3), Aug. [find](https://scholar.google.com/scholar?q=A%2E+Lopez%2E+2008%2E+Statistical+machine+translation%2E+ACM+Computing+Surveys%2C+40%283%29%2C+Aug%2E)
21. A. Lopez. 2009. Translation as weighted deduction. In Proc. of EACL, pages 532–540. [find](https://scholar.google.com/scholar?q=A%2E+Lopez%2E+2009%2E+Translation+as+weighted+deduction%2E+In+Proc%2E+of+EACL%2C+pages+532%E2%80%93540%2E)
22. M.-J. Nederhof. 2003. Weighted deductive parsing and Knuth’s algorithm. Comp. Ling., 29(1):135–143, Mar. [find](https://scholar.google.com/scholar?q=M%2E%2DJ%2E+Nederhof%2E+2003%2E+Weighted+deductive+parsing+and+Knuth%E2%80%99s+algorithm%2E+Comp%2E+Ling%2E%2C+29%281%29%3A135%E2%80%93143%2C+Mar%2E)
23. F. Och. 2003. Minimum error rate training in statistical machine translation. In Proc. of ACL, pages 160–167. [find](https://scholar.google.com/scholar?q=F%2E+Och%2E+2003%2E+Minimum+error+rate+training+in+statistical+machine+translation%2E+In+Proc%2E+of+ACL%2C+pages+160%E2%80%93167%2E)
24. K. Papineni, S. Roukos, T. Ward, and W.-J. Zhu. 2002. BLEU: a method for automatic evaluation of machine translation. In Proc. of ACL, pages 311–318. [our card](https://md.research.elamur.ai/free/en/papers/papineni-2002-bleu-method-automatic-evaluation-machine/)
25. M. Riedmiller and H. Braun. 1993. A direct adaptive method for faster backpropagation learning: The RPROP algorithm. In Proc. of the IEEE international conference on neural networks, pages 586–591. [find](https://scholar.google.com/scholar?q=M%2E+Riedmiller+and+H%2E+Braun%2E+1993%2E+A+direct+adaptive+method+for+faster+backpropagation+learning%3A+The+RPROP+algorithm%2E+In+Proc%2E+of+the+IEEE+international+conference+on+neural+networks%2C+pages+586%E2%80%93591%2E)
26. F. Sha and F. Pereira. 2003. Shallow parsing with conditional random fields. In Proc. of NAACL, pages 134–141. [find](https://scholar.google.com/scholar?q=F%2E+Sha+and+F%2E+Pereira%2E+2003%2E+Shallow+parsing+with+conditional+random+fields%2E+In+Proc%2E+of+NAACL%2C+pages+134%E2%80%93141%2E)
27. M. Snover, B. Dorr, R. Schwartz, L. Micciulla, and J. Makhoul. 2006. A study of translation edit rate with targeted human annotation. In Proc. AMTA. [our card](https://md.research.elamur.ai/free/en/papers/snover-2006-study-translation-edit-rate-targeted/)
28. A. Stolcke. 2002. SRILM – an extensible language modeling toolkit. In Intl. Conf. on Spoken Language Processing. [find](https://scholar.google.com/scholar?q=A%2E+Stolcke%2E+2002%2E+SRILM+%E2%80%93+an+extensible+language+modeling+toolkit%2E+In+Intl%2E+Conf%2E+on+Spoken+Language+Processing%2E)

*Updated 24 October 2026*