Language model rest costs and space-efficient storage

Approximate search algorithms, such as cube pruning in syntactic machine translation, rely on the language model to estimate probabili-ties of sentence fragments. We contribute two changes that trade between accuracy of these estimates and memory, holding sentence-level scores constant. Common practice uses lower-order entries in an N-gram model to score the first few words of a fragment; this vio-lates assumptions made by common smooth-ing strategies, including Kneser-Ney. Instead, we use a unigram model to score the first word, a bigram for the second, etc. This im-proves search at the expense of memory. Con-versely, we show how to save memory by col-lapsing probability and backoff into a single value without changing sentence-level scores, at the expense of less accurate estimates for sentence fragments. These changes can be stacked, achieving better estimates with un-changed memory usage. In order to interpret changes in search accuracy, we adjust the pop limit so that accuracy is unchanged and re-port the change in CPU time. In a German-English Moses system with target-side syntax, improved estimates yielded a 63 % reduction in CPU time; for a Hiero-style version, the reduction is 21%. The compressed language model uses 26 % less RAM while equivalent search quality takes 27 % more CPU. Source code is released as part of KenLM.