# Fast, Small and Exact: Infinite-order Language Modelling with Compressed Suffix Trees

arXiv: https://arxiv.org/abs/1608.04465 · HTML: https://mlsanity.com/paper/1608.04465/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Aug 2016.

## Built on by (most cited first, 1 of 1)

- [Koala: An Index for Quantifying Overlaps with Pre-training Corpora](https://mlsanity.com/paper/2303.14770/) (2023)

## Abstract (arXiv)

Efficient methods for storing and querying are critical for scaling high-order n-gram language models to large corpora. We propose a language model based on compressed suffix trees, a representation that is highly compact and can be easily held in memory, while supporting queries needed in computing language model probabilities on-the-fly. We present several optimisations which improve query runtimes up to 2500x, despite only incurring a modest increase in construction time and memory usage. For large corpora and high Markov orders, our method is highly competitive with the state-of-the-art KenLM package. It imposes much lower memory requirements, often by orders of magnitude, and has runtimes that are either similar (for training) or comparable (for querying).