Elamur Research
☰
home / papers / 2011 / KenLM: Faster and Smaller Language Model Queries

KenLM: Faster and Smaller Language Model Queries

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/W11-2123.pdf

Summary

Decoders for statistical machine translation look up N-gram language model scores extremely often, so how a backoff-smoothed model is stored largely determines both runtime and RAM usage. Heafield presents KenLM, an open-source (LGPL) C++ library with two query structures for ARPA models built by other toolkits. PROBING places all n-grams of one order into a single linear-probing hash table keyed by 64-bit hashes, so any n-gram can be reached in one lookup. TRIE is a reverse trie built on sorted arrays. It packs fields at the bit level, uses interpolation search in place of binary search, and can optionally quantize values. The author benchmarks both against SRILM, IRSTLM, MITLM, RandLM and BerkeleyLM in perplexity runs and inside the Moses decoder. PROBING was the fastest option tested. TRIE needed less memory than any other lossless package and still ran faster than SRILM. KenLM is thread-safe and already integrated into Moses, cdec and Joshua, so these savings carry over to practical translation systems.

Key points

  • Compared with SRILM, PROBING answers queries about 2.4× faster while needing roughly 57% of its memory.
  • TRIE lowers search cost from O(log |A|) to O(log log |A|) through interpolation search. Using the known range of vocabulary IDs alone gave a 24% speedup. Quantization can use any width from 2 to 25 bits, compared with fixed widths in IRSTLM (8 bits) and BerkeleyLM (17–20 bits).
  • About 1.2% of higher-order n-grams in SRILM-pruned models lacked their suffix. KenLM fills these gaps with placeholder entries so it still returns correct results, which BerkeleyLM's hash and compressed variants do not.
  • In single-threaded Moses, unquantized TRIE took 82.9 min, used 12.16 GB resident memory and scored 27.24 BLEU. The 4-bit TRIE used 7.74 GB and scored 27.09 BLEU. RandLM stupid backoff used only 5.07 GB but took 218.7 min and scored 25.54 BLEU.
  • Code: kheafield.com/code/kenlm. It has minimal dependencies (POSIX, g++) and offers C++ and Java interfaces.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Machine translation · Natural language processing

Topics: Machine translation

Cited by

670 papers of our library cite it (of the 140673 whose bibliographies we read); 31 of them have a page here, 639 not yet.

Cite

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

@inproceedings{heafield2011kenlm,
  title = {{KenLM: Faster and Smaller Language Model Queries}},
  author = {Heafield, Kenneth},
  booktitle = {Proceedings of the Sixth Workshop on Statistical Machine Translation},
  year = {2011},
  url = {https://aclanthology.org/W11-2123/}
}

References

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

  1. Philip Clarkson and Ronald Rosenfeld. 1997. Statistical language modeling using the CMU-Cambridge toolkit. In Proceedings of Eurospeech. find
  2. Chris Dyer, Adam Lopez, Juri Ganitkevitch, Johnathan 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. In Proceedings of the ACL 2010 System Demonstra… find
  3. Marcello Federico and Nicola Bertoldi. 2006. How many bits are needed to store probabilities for phrase-based translation? In Proceedings of the Workshop on Statistical Machine Translation, pages 94–101, New York City, June. find
  4. Marcello Federico, Nicola Bertoldi, and Mauro Cettolo. 2008. IRSTLM: an open source toolkit for handling large scale language models. In Proceedings of Interspeech, Brisbane, Australia. find
  5. Ulrich Germann, Eric Joanis, and Samuel Larkin. 2009. Tightly packed tries: How to fit large models into memory, and make them load fast, too. In Proceedings of the NAACL HLT Workshop on Software Engineering, Testing, and Quality Assurance for Natural Language Processing, pages 31–39, Boulder, Color… find
  6. David Guthrie and Mark Hepple. 2010. Storing the web in memory: Space efficient language models with constant time retrieval. In Proceedings of EMNLP 2010, Los Angeles, CA. find
  7. Bo-June Hsu and James Glass. 2008. Iterative language model estimation: Efficient data structure & algorithms. In Proceedings of Interspeech, Brisbane, Australia. find
  8. Philipp Koehn, Hieu Hoang, Alexandra Birch, Chris Callison-Burch, Marcello Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, Chris Dyer, Ondrej Bojar, Alexandra Constantin, and Evan Herbst. 2007. Moses: Open source toolkit for statistical machine translation. In Annu… find
  9. Philipp Koehn. 2005. Europarl: A parallel corpus for statistical machine translation. In Proceedings of MT Summit. find
  10. Zhifei Li, Chris Callison-Burch, Chris Dyer, Sanjeev Khudanpur, Lane Schwartz, Wren Thornton, Jonathan Weese, and Omar Zaidan. 2009. Joshua: An open source toolkit for parsing-based machine translation. In Proceedings of the Fourth Workshop on Statistical Machine Translation, pages 135–139, Athens,… find
  11. Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. BLEU: A method for automatic evalution of machine translation. In Proceedings 40th Annual Meeting of the Association for Computational Linguistics, pages 311–318, Philadelphia, PA, July. find
  12. Robert Parker, David Graff, Junbo Kong, Ke Chen, and Kazuaki Maeda. 2009. English gigaword fourth edition. LDC2009T13. find
  13. Adam Pauls and Dan Klein. 2011. Faster and smaller ngram language models. In Proceedings of ACL, Portland, Oregon. find
  14. Yehoshua Perl, Alon Itai, and Haim Avni. 1978. Interpolation search—a log log N search. Commun. ACM, 21:550–553, July. find
  15. Bhiksha Raj and Ed Whittaker. 2003. Lossless compression of language model structure and word identifiers. In Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing, pages 388– 391. find
  16. Andreas Stolcke. 2002. SRILM - an extensible language modeling toolkit. In Proceedings of the Seventh International Conference on Spoken Language Processing, pages 901–904. find
  17. David Talbot and Miles Osborne. 2007. Randomised language modelling for statistical machine translation. In Proceedings of ACL, pages 512–519, Prague, Czech Republic. find