Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

N-gram Language Models › Higher-Order N-gram Tradeoffs

Michael BrenndoerferMarch 23, 20256 min read

Language AI HandbookAll chapters

Part 2 of 67Classical Text Representations

Chapter 8N-gram Language Models › Higher-Order N-gram Tradeoffs

Reading section 8 of 15 · Higher-Order N-gram Tradeoffs · 6 minSection 8 of 15 · 6 min

Section 8 of 15 · 6 min read

N-gram Language Models › Higher-Order N-gram TradeoffsOne section · Sections in this chapter8 / 15 ↓

Sections in this chapter15

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

Choosing the right n-gram order involves a fundamental tradeoff: more context yields better predictions, but more context also means sparser counts and more zero probabilities.

A unigram model treats every word independently and assigns the same probability to "the cat" and "the mat." A bigram model knows that "cat" frequently follows "the" but "xkcd" rarely does. A trigram model additionally knows that "sat on the" is a common pattern while "flew under the" is unusual in most corpora. A 4-gram model can capture even longer dependencies, like the fact that "I would like to" commonly continues with a verb.

As n-gram order increases, the number of possible n-grams grows exponentially:

\text{Possible n-grams} = V^n

where:

$V$ : the vocabulary size (number of unique word types)
$n$ : the n-gram order
$V^n$ : exponential growth, so each additional word of context multiplies the parameter count by $V$

For English with $V = 100{,}000$ words and $n = 3$ (trigrams), we have $100{,}000^3 = 10^{15}$ potential trigrams. Even storing just one byte per trigram would require a petabyte of memory. Fortunately, the vast majority of combinations never occur in real text, so sparse storage structures (dictionaries or tries) are practical.

The deeper problem is not storage but coverage. Even with enormous corpora, higher-order n-grams remain sparse:

N-gram order vs. approximate test coverage on a typical large corpus. Higher-order n-grams capture more context but suffer from exponentially increasing data sparsity. By order 4, fewer than half of test n-grams appear in training.
N-gram Order	Model Type	Approx. Test Coverage	Notes
1	Unigram	~98%	Almost all words seen in training
2	Bigram	~85%	Most word pairs covered
3	Trigram	~62%	Significant gaps emerge
4	4-gram	~35%	Majority unseen
5	5-gram	~15%	Severe sparsity

The coverage statistics explain why simply using more context is not an obvious win. Yes, a 5-gram model can condition on four words of context, but 85% of the time it will encounter a 5-gram it has never seen and must fall back to some default. In practice, trigram models ( $n = 3$ ) were the standard choice for production NLP systems before neural language models, balancing context length against manageable sparsity.

Out[25]:

Visualization

Bar chart showing the number of observed unique n-gram types for orders one through five. — Observed n-gram types by model order on the training corpus. The number of distinct observed sequences grows with order, but remains far below the exponentially expanding theoretical space.

Bar chart showing context coverage fraction falling sharply from order one through five. — Context coverage relative to the theoretical maximum by n-gram order. Coverage collapses as order increases because the possible context space grows much faster than the available training data.

The plots use our small training corpus but illustrate the key pattern: as order increases, both the count of observed n-grams grows (because there are more distinct longer sequences) and coverage of the theoretical maximum collapses (because the space grows much faster than the data).

Model Storage and EfficiencyLink Copied

In[26]:

Code

def estimate_model_size(model):
    """Estimate memory usage of an n-gram model."""
    num_ngrams = len(model.ngram_counts)
    num_contexts = len(model.context_counts)
    vocab_size = len(model.vocab)

    # Each n-gram tuple holds string references (~50 bytes each) plus count
    ngram_memory = num_ngrams * (model.n * 50 + 28)
    context_memory = num_contexts * ((model.n - 1) * 50 + 28)
    vocab_memory = vocab_size * 50

    total_bytes = ngram_memory + context_memory + vocab_memory

    return {
        "num_ngrams": num_ngrams,
        "num_contexts": num_contexts,
        "vocab_size": vocab_size,
        "estimated_mb": total_bytes / (1024 * 1024),
    }


sizes = {
    "Unigram": estimate_model_size(unigram_model),
    "Bigram": estimate_model_size(bigram_model),
    "Trigram": estimate_model_size(trigram_model),
}

Out[27]:

Console

Model Storage Statistics:
------------------------------------------------------------
Model         N-grams   Contexts    Vocab    Est. MB
------------------------------------------------------------
Unigram            19          1       19     0.0023
Bigram             36         19       20     0.0068
Trigram            44         29       20     0.0120

Our toy corpus produces tiny models measured in kilobytes. Real-world models trained on billions of words require a completely different approach to storage. Production systems typically use trie-based storage, where each path from the root to a node represents an n-gram prefix and nodes store counts and probabilities. Tries share prefixes between n-grams, reducing memory and enabling efficient prefix queries. The ARPA language model format, used by tools like KenLM and SRILM, stores n-gram counts and back-off weights in a text format that most speech recognition and MT systems can read. KenLM further compresses this using sorted arrays, reducing a multi-gigabyte text file to a few hundred megabytes in binary format.