An n-gram language model is a statistical language model that assigns probabilities to sequences of tokens by predicting each token from at most the preceding tokens. Tokens may be words, characters, or smaller-than-word units. In its conventional form, the model learns conditional probabilities from counts in a text corpus, with adjustments for rare or unseen sequences. N-gram models were central to statistical speech recognition and machine translation and remain useful as efficient baselines, compact predictive models, and components of larger systems.
Definition and mathematical basis
An n-gram is a contiguous sequence of tokens. For the word sequence “the cat sat down,” the word bigrams are “the cat,” “cat sat,” and “sat down”; the trigrams are “the cat sat” and “cat sat down.”
An n-gram language model uses such sequences to estimate a probability distribution over the next token. For a sequence , the chain rule of probability theory gives
Conditioning on every preceding token requires estimating distributions for an enormous number of possible histories. The n-gram approximation replaces the full history with a fixed-length suffix:
At the beginning of a sequence, the context is shorter or is padded with special beginning-of-sequence symbols. This is a finite-order Markov assumption: once the retained context is known, earlier tokens do not directly affect the next-token probability.
The principal orders are:
| Model | Context used to predict the next token |
|---|---|
| Unigram, | No preceding tokens |
| Bigram, | One preceding token |
| Trigram, | Two preceding tokens |
| Four-gram, | Three preceding tokens |
An n-gram language model therefore has a context length of , not . An n-gram language model and an order- Markov model can consequently use different numbering conventions: in the latter, the order commonly denotes the number of preceding states retained.
Sentence models normally include an end-of-sentence token. Its probability represents the decision to stop rather than generate another ordinary token. Without an explicit stopping mechanism or a separate model of length, a product of next-token probabilities scores a sequence of a specified length but does not by itself define a normalized distribution over complete sentences of arbitrary length.
Estimation from counts
The simplest estimator is maximum likelihood estimation. Let be a context of length , and let count how often token follows in the training data. Then
where is the prediction vocabulary, including any predicted boundary or unknown-token symbols.
For example, suppose “the cat” is followed by a predicted token 20 times, with “sat” occurring on 12 of those occasions. A trigram maximum-likelihood estimate gives
In the familiar count-ratio notation, this is often written as . The denominator must count occurrences of the history that have a corresponding predicted continuation under the model’s boundary conventions.
Raw counting alone has two important weaknesses:
- A continuation absent from the training data receives probability zero.
- For a completely unseen history, the conditional distribution is undefined.
A single zero-probability event makes the probability of the entire containing sequence zero. Because plausible language regularly contains previously unseen combinations, practical count-based models generally require smoothing.
Smoothing and combining context lengths
Smoothing reallocates probability mass to improve estimates from finite data, especially for rare and unseen events. It is not merely a numerical safeguard: it expresses the expectation that an observed corpus does not exhaust the possibilities of the language.
Additive smoothing
Additive smoothing adds a positive pseudocount to every possible continuation:
Setting gives add-one, or Laplace, smoothing. Although simple, it often allocates too much probability to unseen events in large-vocabulary word models and substantially distorts estimates for observed events.
Interpolation and backoff
Interpolation combines distributions based on different context lengths. A trigram model might use
with nonnegative weights satisfying . The weights may be global or depend on the available evidence for the context. Shorter-context components must themselves be defined where higher-order contexts are missing.
Backoff instead uses a higher-order estimate when the relevant n-gram is available and otherwise falls back to a shorter context. Discounting and normalization ensure that the resulting conditional probabilities sum to one. Katz backoff is a widely used historical example, commonly associated with Good–Turing discounting.
Interpolation and backoff are related but distinct: interpolation can incorporate lower-order evidence even for observed higher-order n-grams.
Kneser–Ney smoothing
Kneser–Ney smoothing combines discounting with a special treatment of lower-order probabilities. Its central insight is that a useful lower-order estimate should reflect the diversity of contexts in which a token appears, rather than only its overall frequency.
A word occurring frequently almost exclusively after one particular predecessor need not be a good prediction after an unfamiliar predecessor. Kneser–Ney’s continuation probabilities account for this distinction by counting distinct preceding contexts. Modified Kneser–Ney smoothing uses multiple discount values and is a strong, widely used method for conventional word n-gram models.
Tokenization, vocabulary, and boundaries
Model behavior depends heavily on how text is divided into tokens.
- Word models capture lexical combinations and collocations directly but can require large vocabularies.
- Character models use small vocabularies and can assign probabilities to novel word spellings, but a short character context covers less linguistic material than an equally sized word context.
- Subword models operate on units smaller than words, potentially using a segmentation method such as WordPiece.
Languages without consistent spaces between written words require particular care when constructing word-based models. For example, different Chinese word segmentation conventions produce different token inventories and n-gram counts.
A fixed-vocabulary word model commonly replaces rare training words with an unknown-word token and maps unseen test words to that token. This addresses out-of-vocabulary words operationally, but it does not distinguish their identities or assign separate probabilities to their spellings.
An n-gram model over subword tokens is not the same as a unigram subword model. The latter usually refers to a model used to learn or select segmentations; it is not simply an ordinary word unigram predictor.
Sentence-boundary rules, case normalization, punctuation, and number handling also affect the learned distribution. Models normally avoid counting n-grams across sentence boundaries unless cross-sentence context is intentionally part of the design.
Evaluation
N-gram models are commonly evaluated on held-out text not used to estimate their parameters. A validation set can be used to select smoothing parameters, interpolation weights, vocabulary thresholds, and model order.
A standard measure is perplexity. For a test sequence of predicted tokens,
Perplexity is the exponential of the average negative log probability, closely related to cross-entropy. Lower values indicate that a model assigns higher average probability to the observed test tokens.
Comparisons require compatible evaluation conditions. Vocabulary, tokenization, unknown-word mapping, and treatment of end-of-sentence tokens can substantially change the result. A word-level perplexity and a character-level perplexity are not directly comparable. Lower perplexity also does not guarantee better performance in every downstream application.
Historical development and applications
Finite-context probabilistic models of symbol sequences have roots in Markov’s work on dependent sequences. Claude Shannon’s 1948 work on information theory examined successive statistical approximations to English, including approximations that preserve progressively more local context. These helped establish the connection between language predictability, probability, and information.
Word n-gram models became major components of statistical speech recognition and later statistical machine translation. In speech recognition, they help distinguish candidate transcriptions that are acoustically similar. In machine translation, they traditionally provide a target-language fluency score alongside translation-model scores. Their ability to assign probabilities to arbitrary candidate sequences made them useful in search and ranking systems.
Other applications include:
- Predictive typing and word completion.
- Ranking spelling-correction candidates.
- Scoring alternatives in optical character recognition.
- Character-based language identification.
- Domain-specific text scoring and probabilistic text generation.
An n-gram language model should be distinguished from a system that merely uses n-gram features. For example, BLEU measures overlap between candidate and reference translations using modified n-gram precision; it does not thereby constitute a next-token probability model.
Computational properties
For a vocabulary of size , there are up to possible n-grams of length . Most are never observed, so practical implementations store a sparse collection of observed entries rather than a complete table.
Counts and probabilities can be stored using tries, hash-based structures, or compressed representations. Pruning removes entries judged to contribute little to predictive performance, reducing memory and lookup costs. Large models can also quantize stored probabilities and backoff weights.
For fixed , scoring a sequence requires a number of next-token evaluations proportional to its length. Lookup costs depend on the representation and any backoff steps. This predictable computation, together with straightforward count collection, is an important practical advantage.
Limitations and relationship to neural models
The main statistical limitation is data sparsity. Increasing provides more context but sharply reduces the evidence available for individual contexts. Smoothing mitigates this problem without eliminating it.
Other limitations include:
- Restricted context: dependencies outside the retained window cannot directly affect a prediction.
- Limited generalization across related expressions: conventional count tables do not automatically share evidence between semantically or morphologically related tokens.
- Domain sensitivity: probabilities learned from one register or subject area may fit another poorly.
- Memory growth: retaining many higher-order n-grams can require substantial storage.
These constraints make long-distance syntactic dependencies, discourse structure, and many aspects of meaning difficult to capture. They do not imply that n-gram statistics contain no grammatical information: many local grammatical patterns are strongly reflected in token frequencies.
Neural language models use neural networks and learned representations to share statistical information across contexts. Modern large language models can condition on much longer contexts and represent dependencies that short fixed-order count models cannot express directly. N-gram models nevertheless remain useful where low latency, transparent local estimates, limited computational resources, or a reproducible statistical baseline are important.