--- title: "KenLM: Faster and Smaller Language Model — Heafield 2011" description: "Decoders for statistical machine translation look up N-gram language model scores extremely often, so how a backoff-smoothed model is stored largely…" authors: ["Kenneth Heafield"] year: 2011 venue: "Proceedings of the Sixth Workshop on Statistical Machine Translation" source: "https://aclanthology.org/W11-2123/" 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/heafield-2011-kenlm-faster-smaller-language-model/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/heafield-2011-kenlm-faster-smaller-language-model/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2011](https://md.research.elamur.ai/free/en/papers/2011/) / KenLM: Faster and Smaller Language Model Queries # KenLM: Faster and Smaller Language Model Queries **Authors:** [Kenneth Heafield](https://md.research.elamur.ai/free/en/authors/kenneth-heafield/) · **Year:** 2011 · **Venue:** Proceedings of the Sixth Workshop on Statistical Machine Translation · **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/W11-2123/) · [PDF](https://aclanthology.org/W11-2123.pdf) · [OpenAlex](https://openalex.org/W2134800885) **Citations:** 1089 citations (openalex-snapshot · 2026-10-14) · [670](#cited-by) in our library, of the 140673 papers whose bibliographies we read ## 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: http://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](https://md.research.elamur.ai/free/en/shelves/machine-translation/) · [Natural language processing](https://md.research.elamur.ai/free/en/shelves/nlp/) Topics: [Machine translation](https://md.research.elamur.ai/free/en/topics/machine-translation/) ## Cited by Cited by 670 papers of our library cite it (of the 140673 whose bibliographies we read); 53 of them have a page here, 617 not yet. - [Towards a Cleaner Document-Oriented Multilingual Crawled Corpus](https://md.research.elamur.ai/free/en/papers/abadji-2022-towards-cleaner-document-oriented-multilingual/) - [Fanar: An Arabic-Centric Multimodal Generative AI Platform](https://md.research.elamur.ai/free/en/papers/abbas-2025-fanar-arabic-centric-multimodal-generative/) - [Leveraging Data Collection and Unsupervised Learning for Code-switched Tunisian Arabic Automatic Speech Recognition](https://md.research.elamur.ai/free/en/papers/abdallah-2023-leveraging-data-collection-unsupervised-learning/) - [The AMARA Corpus: Building Parallel Language Resources for the Educational Domain](https://md.research.elamur.ai/free/en/papers/abdelali-2014-amara-corpus-building-parallel-language/) - [Farasa: A Fast and Furious Segmenter for Arabic](https://md.research.elamur.ai/free/en/papers/aclbulk-2016-abdelali-farasa-fast-furious-segmenter-arabic/) - [Unsupervised Domain Clusters in Pretrained Language Models](https://md.research.elamur.ai/free/en/papers/aharoni-2020-unsupervised-domain-clusters-pretrained-language/) - [Dotless Representation of Arabic Text: Analysis and Modeling](https://md.research.elamur.ai/free/en/papers/al-2023-shaibani-dotless-representation-arabic-text-analysis/) - [Poem Meter Classification of Recited Arabic Poetry: Integrating High-Resource Systems for a Low-Resource Task](https://md.research.elamur.ai/free/en/papers/al-2025-shaibani-poem-meter-classification-recited-arabic/) - [Tower: An Open Multilingual Large Language Model for Translation-Related Tasks](https://md.research.elamur.ai/free/en/papers/alves-2024-tower-open-multilingual-large-language/) - [Good-Enough Compositional Data Augmentation](https://md.research.elamur.ai/free/en/papers/andreas-2020-good-enough-compositional-data-augmentation/) - [Hierarchical Aggregation of Dialectal Data for Arabic Dialect Identification](https://md.research.elamur.ai/free/en/papers/baimukan-2022-hierarchical-aggregation-dialectal-data-arabic/) - [Findings of the 2015 Workshop on Statistical Machine Translation](https://md.research.elamur.ai/free/en/papers/bojar-2015-findings-2015-workshop-statistical-machine/) - [Findings of the 2016 Conference on Machine Translation](https://md.research.elamur.ai/free/en/papers/bojar-2016-findings-2016-conference-machine-translation/) - [Findings of the 2017 Conference on Machine Translation (WMT17)](https://md.research.elamur.ai/free/en/papers/bojar-2017-findings-2017-conference-machine-translation/) - [Findings of the 2018 Conference on Machine Translation (WMT18)](https://md.research.elamur.ai/free/en/papers/bojar-2018-findings-2018-conference-machine-translation/) - [Evaluating the Evaluation Metrics for Style Transfer: A Case Study in Multilingual Formality Transfer](https://md.research.elamur.ai/free/en/papers/briakou-2021-evaluating-evaluation-metrics-style-transfer/) - [Evaluating prose style transfer with the Bible](https://md.research.elamur.ai/free/en/papers/carlson-2017-evaluating-prose-style-transfer-bible/) - [Prompsit's submission to WMT 2018 Parallel Corpus Filtering shared task](https://md.research.elamur.ai/free/en/papers/cartagena-2018-prompsit-s-submission-wmt-2018/) - [Style Transformer: Unpaired Text Style Transfer without Disentangled Latent Representation](https://md.research.elamur.ai/free/en/papers/dai-2019-style-transformer-unpaired-text-style/) - [Colorless Green Recurrent Networks Dream Hierarchically](https://md.research.elamur.ai/free/en/papers/gulordava-2018-colorless-green-recurrent-networks-dream/) - [Anaphora Models and Reordering for Phrase-Based SMT](https://md.research.elamur.ai/free/en/papers/hardmeier-2014-anaphora-models-reordering-phrase-based/) - [Scalable Modified Kneser-Ney Language Model Estimation](https://md.research.elamur.ai/free/en/papers/heafield-2013-scalable-modified-kneser-ney-language/) - [Baseer: A Vision-Language Model for Arabic Document-to-Markdown OCR](https://md.research.elamur.ai/free/en/papers/hennara-2025-baseer-vision-language-model-arabic/) - [Wasm: A Pipeline for Constructing Structured Arabic Interleaved Multimodal Corpora](https://md.research.elamur.ai/free/en/papers/hennara-2025-wasm-pipeline-constructing-structured-arabic/) - [Semantics-Based Machine Translation with Hyperedge Replacement Grammars](https://md.research.elamur.ai/free/en/papers/jones-2012-semantics-based-machine-translation-hyperedge/) - [On the Impact of Various Types of Noise on Neural Machine Translation](https://md.research.elamur.ai/free/en/papers/khayrallah-2018-impact-various-types-noise-neural/) - [The IIT Bombay English-Hindi Parallel Corpus](https://md.research.elamur.ai/free/en/papers/kunchukuttan-2018-iit-bombay-english-hindi-parallel/) - [A Continuously Growing Dataset of Sentential Paraphrases](https://md.research.elamur.ai/free/en/papers/lan-2017-continuously-growing-dataset-sentential-paraphrases/) - [Probabilistic Modelling of Morphologically Rich Languages](https://md.research.elamur.ai/free/en/papers/langstream-2015-botha-probabilistic-modelling-morphologically-rich-languages/) - [The BigScience ROOTS Corpus: A 1.6TB Composite Multilingual Dataset](https://md.research.elamur.ai/free/en/papers/lauren-2023-ccon-bigscience-roots-corpus-1-6tb/) - [OBELICS: An Open Web-Scale Filtered Dataset of Interleaved Image-Text Documents](https://md.research.elamur.ai/free/en/papers/lauren-2023-ccon-obelics-open-web-scale-filtered/) - [Few-shot Learning with Multilingual Language Models](https://md.research.elamur.ai/free/en/papers/lin-2021-few-shot-learning-multilingual-language/) - [Predicting and Using a Pragmatic Component of Lexical Aspect of Simple Past Verbal Tenses for Improving English-to-French Machine Translation](https://md.research.elamur.ai/free/en/papers/loaiciga-2016-predicting-pragmatic-component-lexical-aspect/) - [What is it? Disambiguating the different readings of the pronoun 'it'](https://md.research.elamur.ai/free/en/papers/loaiciga-2017-what-is-it-disambiguating-different/) - [Paraphrasing Revisited with Neural Machine Translation](https://md.research.elamur.ai/free/en/papers/mallinson-2017-paraphrasing-revisited-neural-machine-translation/) - [MUSS: Multilingual Unsupervised Sentence Simplification by Mining Paraphrases](https://md.research.elamur.ai/free/en/papers/martin-2022-muss-multilingual-unsupervised-sentence-simplification/) - [Facebook FAIR's WMT19 News Translation Task Submission](https://md.research.elamur.ai/free/en/papers/ng-2019-facebook-fair-s-wmt19-news/) - [CulturaX: A Cleaned, Enormous, and Multilingual Dataset for Large Language Models in 167 Languages](https://md.research.elamur.ai/free/en/papers/nguyen-2023-culturax-cleaned-enormous-multilingual-dataset/) - [Word predictability estimates from language models are not robust to tokenizer vocabulary](https://md.research.elamur.ai/free/en/papers/nguyen-2026-word-predictability-estimates-language-models/) - [OpenWebMath: An Open Dataset of High-Quality Mathematical Web Text](https://md.research.elamur.ai/free/en/papers/paster-2023-openwebmath-open-dataset-high-quality/) - [Sarcasm SIGN: Interpreting Sarcasm with Sentiment Based Monolingual Machine Translation](https://md.research.elamur.ai/free/en/papers/peled-2017-sarcasm-sign-interpreting-sarcasm-sentiment/) - [MLS: A Large-Scale Multilingual Dataset for Speech Research](https://md.research.elamur.ai/free/en/papers/pratap-2020-mls-large-scale-multilingual-dataset/) - [Scaling Speech Technology to 1,000+ Languages](https://md.research.elamur.ai/free/en/papers/pratap-2023-scaling-speech-technology-1-000/) - [Enhancing function word translation with syntax-based statistical post-editing](https://md.research.elamur.ai/free/en/papers/richardson-2015-enhancing-function-word-translation-syntax/) - [Supplementary Resources and Analysis for Automatic Speech Recognition Systems Trained on the Loquacious Dataset](https://md.research.elamur.ai/free/en/papers/rossenbach-2026-supplementary-resources-analysis-automatic-speech/) - [Fine-Grained Arabic Dialect Identification](https://md.research.elamur.ai/free/en/papers/salameh-2018-fine-grained-arabic-dialect-identification/) - [Diacritic Restoration for Low-Resource Indigenous Languages: Case Study with Bribri and Cook Islands Māori](https://md.research.elamur.ai/free/en/papers/solano-2026-diacritic-restoration-low-resource-indigenous/) - [Facebook AI's WMT21 News Translation Task Submission](https://md.research.elamur.ai/free/en/papers/tran-2021-facebook-ai-s-wmt21-news/) - [VoxPopuli: A Large-Scale Multilingual Speech Corpus for Representation Learning, Semi-Supervised Learning and Interpretation](https://md.research.elamur.ai/free/en/papers/wang-2021-voxpopuli-large-scale-multilingual-speech/) - [CCNet: Extracting High Quality Monolingual Datasets from Web Crawl Data](https://md.research.elamur.ai/free/en/papers/wenzek-2020-ccnet-extracting-high-quality-monolingual/) - [Creating a Translation Matrix of the Bible's Names Across 591 Languages](https://md.research.elamur.ai/free/en/papers/wu-2018-creating-translation-matrix-bible-s/) - [Chinese Poetry Generation with Recurrent Neural Networks](https://md.research.elamur.ai/free/en/papers/zhang-2014-chinese-poetry-generation-recurrent-neural/) - [Beyond Random Sampling: Efficient Language Model Pretraining via Curriculum Learning](https://md.research.elamur.ai/free/en/papers/zhang-2026-beyond-random-sampling-efficient-language/) ## Cite The paper itself, not this page. BibTeX from the library's record of the work. ```bibtex @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/} } ``` - [← previous Joint Hebrew Segmentation and Parsing using a PCFGLA Lattice Parser](https://md.research.elamur.ai/free/en/papers/aclbulk-2011-goldberg-joint-hebrew-segmentation-parsing-pcfgla/) - [next → Large-Scale Cross-Document Coreference Using Distributed Inference and Hierarchical Models](https://md.research.elamur.ai/free/en/papers/singh-2011-large-scale-cross-document-coreference/) - [↑ back to papers of 2011](https://md.research.elamur.ai/free/en/papers/2011/) ## References 17 references, 2 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](https://scholar.google.com/scholar?q=Philip+Clarkson+and+Ronald+Rosenfeld%2E+1997%2E+Statistical+language+modeling+using+the+CMU%2DCambridge+toolkit%2E+In+Proceedings+of+Eurospeech%2E) 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](https://scholar.google.com/scholar?q=Chris+Dyer%2C+Adam+Lopez%2C+Juri+Ganitkevitch%2C+Johnathan+Weese%2C+Ferhan+Ture%2C+Phil+Blunsom%2C+Hendra+Setiawan%2C+Vladimir+Eidelman%2C+and+Philip+Resnik%2E+2010%2E+cdec%3A+A+decoder%2C+alignment%2C+and+learning+framework+f) [our card](https://md.research.elamur.ai/free/en/papers/dyer-2010-cdec-decoder-alignment-learning-framework/) 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](https://scholar.google.com/scholar?q=Marcello+Federico+and+Nicola+Bertoldi%2E+2006%2E+How+many+bits+are+needed+to+store+probabilities+for+phrase%2Dbased+translation%3F+In+Proceedings+of+the+Workshop+on+Statistical+Machine+Translation%2C+pages+94%E2%80%931) 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](https://scholar.google.com/scholar?q=Marcello+Federico%2C+Nicola+Bertoldi%2C+and+Mauro+Cettolo%2E+2008%2E+IRSTLM%3A+an+open+source+toolkit+for+handling+large+scale+language+models%2E+In+Proceedings+of+Interspeech%2C+Brisbane%2C+Australia%2E) 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](https://scholar.google.com/scholar?q=Ulrich+Germann%2C+Eric+Joanis%2C+and+Samuel+Larkin%2E+2009%2E+Tightly+packed+tries%3A+How+to+fit+large+models+into+memory%2C+and+make+them+load+fast%2C+too%2E+In+Proceedings+of+the+NAACL+HLT+Workshop+on+Software+Engi) 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](https://scholar.google.com/scholar?q=David+Guthrie+and+Mark+Hepple%2E+2010%2E+Storing+the+web+in+memory%3A+Space+efficient+language+models+with+constant+time+retrieval%2E+In+Proceedings+of+EMNLP+2010%2C+Los+Angeles%2C+CA%2E) 7. Bo-June Hsu and James Glass. 2008. Iterative language model estimation: Efficient data structure & algorithms. In Proceedings of Interspeech, Brisbane, Australia. [find](https://scholar.google.com/scholar?q=Bo%2DJune+Hsu+and+James+Glass%2E+2008%2E+Iterative+language+model+estimation%3A+Efficient+data+structure+%26+algorithms%2E+In+Proceedings+of+Interspeech%2C+Brisbane%2C+Australia%2E) 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](https://scholar.google.com/scholar?q=Philipp+Koehn%2C+Hieu+Hoang%2C+Alexandra+Birch%2C+Chris+Callison%2DBurch%2C+Marcello+Federico%2C+Nicola+Bertoldi%2C+Brooke+Cowan%2C+Wade+Shen%2C+Christine+Moran%2C+Richard+Zens%2C+Chris+Dyer%2C+Ondrej+Bojar%2C+Alexandra+Consta) 9. Philipp Koehn. 2005. Europarl: A parallel corpus for statistical machine translation. In Proceedings of MT Summit. [find](https://scholar.google.com/scholar?q=Philipp+Koehn%2E+2005%2E+Europarl%3A+A+parallel+corpus+for+statistical+machine+translation%2E+In+Proceedings+of+MT+Summit%2E) 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](https://scholar.google.com/scholar?q=Zhifei+Li%2C+Chris+Callison%2DBurch%2C+Chris+Dyer%2C+Sanjeev+Khudanpur%2C+Lane+Schwartz%2C+Wren+Thornton%2C+Jonathan+Weese%2C+and+Omar+Zaidan%2E+2009%2E+Joshua%3A+An+open+source+toolkit+for+parsing%2Dbased+machine+translatio) [our card](https://md.research.elamur.ai/free/en/papers/li-2009-joshua-open-source-toolkit-parsing/) 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](https://scholar.google.com/scholar?q=Kishore+Papineni%2C+Salim+Roukos%2C+Todd+Ward%2C+and+Wei%2DJing+Zhu%2E+2002%2E+BLEU%3A+A+method+for+automatic+evalution+of+machine+translation%2E+In+Proceedings+40th+Annual+Meeting+of+the+Association+for+Computationa) 12. Robert Parker, David Graff, Junbo Kong, Ke Chen, and Kazuaki Maeda. 2009. English gigaword fourth edition. LDC2009T13. [find](https://scholar.google.com/scholar?q=Robert+Parker%2C+David+Graff%2C+Junbo+Kong%2C+Ke+Chen%2C+and+Kazuaki+Maeda%2E+2009%2E+English+gigaword+fourth+edition%2E+LDC2009T13%2E) 13. Adam Pauls and Dan Klein. 2011. Faster and smaller ngram language models. In Proceedings of ACL, Portland, Oregon. [find](https://scholar.google.com/scholar?q=Adam+Pauls+and+Dan+Klein%2E+2011%2E+Faster+and+smaller+ngram+language+models%2E+In+Proceedings+of+ACL%2C+Portland%2C+Oregon%2E) 14. Yehoshua Perl, Alon Itai, and Haim Avni. 1978. Interpolation search—a log log N search. Commun. ACM, 21:550–553, July. [find](https://scholar.google.com/scholar?q=Yehoshua+Perl%2C+Alon+Itai%2C+and+Haim+Avni%2E+1978%2E+Interpolation+search%E2%80%94a+log+log+N+search%2E+Commun%2E+ACM%2C+21%3A550%E2%80%93553%2C+July%2E) 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](https://scholar.google.com/scholar?q=Bhiksha+Raj+and+Ed+Whittaker%2E+2003%2E+Lossless+compression+of+language+model+structure+and+word+identifiers%2E+In+Proceedings+of+IEEE+International+Conference+on+Acoustics%2C+Speech+and+Signal+Processing%2C+p) 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](https://scholar.google.com/scholar?q=Andreas+Stolcke%2E+2002%2E+SRILM+%2D+an+extensible+language+modeling+toolkit%2E+In+Proceedings+of+the+Seventh+International+Conference+on+Spoken+Language+Processing%2C+pages+901%E2%80%93904%2E) 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](https://scholar.google.com/scholar?q=David+Talbot+and+Miles+Osborne%2E+2007%2E+Randomised+language+modelling+for+statistical+machine+translation%2E+In+Proceedings+of+ACL%2C+pages+512%E2%80%93519%2C+Prague%2C+Czech+Republic%2E)