KenLM: Faster and Smaller Language Model Queries

TLDR

The paper introduces KenLM, a library that implements two data structures for efficient language model queries, and benchmarks its performance against alternative implementations. KenLM implements two efficient data structures—Probing, a linear‑probing hash table for speed, and Trie, a bit‑packed trie with interpolation search and optional quantization for low memory—along with open‑source, thread‑safe code integrated into Moses, cdec, and Joshua. Probing is 2.4× faster than SRILM while using 57% of its memory, and Trie consumes less memory than the smallest lossless baseline and less CPU than the fastest baseline.

Abstract

We present KenLM, a library that implements two data structures for efficient language model queries, reducing both time and memory costs. The Probing data structure uses linear probing hash tables and is designed for speed. Compared with the widely-used SRILM, our Probing model is 2.4 times as fast while using 57% of the memory. The Trie data structure is a trie with bit-level packing, sorted records, interpolation search, and optional quantization aimed at lower memory consumption. Trie simultaneously uses less memory than the smallest lossless baseline and less CPU than the fastest baseline. Our code is open-source, thread-safe, and integrated into the Moses, cdec, and Joshua translation systems. This paper describes the several performance techniques used and presents benchmarks against alternative implementations.