Fast, Small and Exact: Infinite-order Language Modelling with Compressed Suffix Trees
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).
Code (1)
Tasks
Language ModelingLanguage ModellingSimilar Papers 제목 키워드 기반
On Noisy Negative Curvature Descent: Competing with Gradient Descent for Faster Non-convex Optimization
The Hessian-vector product has been utilized to find a second-order stationary solution with strong complexity guarantee (e.g., almost linear time complexity in the problem's dimensionality). In this paper, we propose to…
The Method of Infinite Descent
Training - the optimisation of complex models - is traditionally performed through small, local, iterative updates [D. E. Rumelhart, G. E. Hinton, R. J. Williams, Nature 323, 533-536 (1986)]. Approximating solutions thro…
Application of MUSIC-type imaging for anomaly detection without background information
It has been demonstrated that the MUltiple SIgnal Classification (MUSIC) algorithm is fast, stable, and effective for localizing small anomalies in microwave imaging. For the successful application of MUSIC, exact values…
Anomaly DetectionSR-TTT: Surprisal-Aware Residual Test-Time Training
Test-Time Training (TTT) language models achieve theoretically infinite context windows with an O(1) memory footprint by replacing the standard exact-attention KV-cache with hidden state ``fast weights'' W_fast updated v…
Self-Supervised LearningProbabilistic Inference with Generating Functions for Poisson Latent Variable Models
Graphical models with latent count variables arise in a number of fields. Standard exact inference techniques such as variable elimination and belief propagation do not apply to these models because the latent variables …