Subscribe
educational
7 min read

What Is an N-gram? The Counting Trick That Ran Language Models for 50 Years

Before transformers, every language model was a table of word counts. What an n-gram is, how fifty years of smoothing research scaled it to trillions of tokens, and why it still filters pre-training data and accelerates inference in 2026.

Olivetti-style illustration of a typewriter feeding a paper tape into a mechanical counting machine under the title What Is an N-gram?
Olivetti-style illustration of a typewriter feeding a paper tape into a mechanical counting machine under the title What Is an N-gram?

Every language model answers the same question: given the text so far, what comes next? For fifty years, before a model could be trained, it had to be counted. The answer was an n-gram table, a lookup structure holding how often each short phrase appeared after each other short phrase. Phone-company dictation systems, Google's translation pipeline and the spellcheckers in your first email client all ran on them. The technique looks quaint from inside the transformer era. It also still holds two jobs in the modern LLM stack, one in data filtering and one in inference.

What an n-gram is

An n-gram is a run of n consecutive items in a text, words or characters, taken by sliding a window across the document. The sentence "the court adjourned without dissent" contains the bigrams "the court", "court adjourned", "adjourned without", "without dissent", and the trigrams "the court adjourned", "court adjourned without", and so on.

An n-gram language model turns those counts into a prediction. The probability that the next word is w after a given context is estimated by a ratio: how often the context-plus-w appeared in the training text, divided by how often the context alone appeared. The model assumes, following Markov, that only the last n-1 words matter. A unigram model uses no context at all, a bigram model uses the previous word, a trigram model the previous two. Brants et al. (2007) state the formalism exactly this way: the probability of a token string is the product of conditional probabilities given the preceding n-1 tokens, with each conditional estimated by relative frequency in the training data.

After "New", "York" should outscore "man". The model does not know that. It has simply counted that "New York" is common and "New man" is not.

A hand-cranked counting machine sliding a three-frame window over blank tiles and stacking tally columns

The sparsity problem

The scheme has an obvious limit. With a vocabulary of V words and order n, there are V to the n possible n-grams. A vocabulary of 100,000 words means more than a quadrillion possible trigrams. No corpus on earth contains them all, and the counts that are missing are not zero by accident, they are zero because language is mostly unseen. Raw maximum-likelihood counting assigns them probability zero, which means one unknown phrase can zero out the score of an entire sentence. The Brants paper puts it directly: increasing n-gram order can improve predictive accuracy in principle, but it makes the sparse-data problem worse.

Sixty years of research went into the fix, which is called smoothing. The core idea is to discount the counts you have observed and hand the freed probability mass to the counts you have not. Katz (1987) introduced backing off to a shorter context when a longer one is unseen. Kneser and Ney (1995) improved it by discounting with continuation counts, how often a word has been seen in new contexts rather than how often it has been seen. Chen and Goodman (1996) benchmarked seven smoothing variants on the Brown corpus and set the comparison table the field used for a decade.

It starts with Shannon

The n-gram approximation of English is Claude Shannon's. In "A Mathematical Theory of Communication" (1948) he modeled text as a Markov source of increasing order and computed how much entropy, the uncertainty per character, fell as context was added. In "Prediction and Entropy of Printed English" (1951) he measured it with people: subjects guessed the next character of a passage given the preceding text, and their success rates let Shannon bound the entropy of printed English near 1 bit per character, against roughly 4.7 bits for random letters drawn from the alphabet. His conclusion, that English is on the order of 75 percent redundant, is the reason statistical language modeling works at all. Text is mostly predictable, and the predictable part lives in short, repeatable contexts.

Peak n-gram: when "large language model" meant a lookup table

By the mid-2000s the counting had gone planetary. Brants and Franz (2006) released Google's web-corpus n-gram counts, trained on one trillion tokens, pruning any n-gram seen fewer than forty times and replacing words seen fewer than 200 times with an unknown token, as documented by Buck et al. (2014), who rebuilt the same machinery on Common Crawl.

The same Google group's 2007 paper is titled "Large Language Models in Machine Translation". It described a distributed training infrastructure that built 5-gram models of up to 300 billion n-grams from up to 2 trillion tokens of news, served with single-pass decoding. Its smoothing method was deliberately crude at that scale: "Stupid Backoff", no discounting, raw relative frequencies, skipping n-grams never seen together. It approached the quality of Kneser-Ney as data grew. Note the title. The phrase large language model meant a big n-gram table about fifteen years before it meant what it means now, and the paper's own lesson, that data beats cleverness, is the argument the scaling era would run with.

N-gram counts also produced the era's most famous public dataset. Google's Books Ngram Viewer shipped in December 2010 and powered the Science paper behind "culturomics" (Michel et al., 2011): 5,195,769 digitized books, about 4 percent of all books ever published, over 500 billion word tokens, 361 billion of them in English. It did not predict text; it counted n-gram frequencies by publication year. Researchers have spent fifteen years arguing about what those counts mean, which is more than most statistical products achieve.

The evaluation metric of the field was n-grams too. BLEU, introduced by Papineni et al. (2002), scores a machine translation by counting what fraction of its n-grams appear in reference translations. It outlived the systems it was built for by two decades and still sits on machine-translation dashboards.

The neural handover, and the hybrid decade after

Bengio et al. (2003), "A Neural Probabilistic Language Model", is the standard before-and-after marker. A feed-forward network learned a continuous embedding for each word and scored contexts by generalization instead of memorization: unseen n-grams got sensible probabilities because similar contexts sit near each other in the learned space. The lineage runs through the recurrent and then transformer models that replaced n-grams as predictors.

The replacement was slow, because n-grams were load-bearing infrastructure. Microsoft's 2017 conversational speech recognition system, which hit then-record word error rates, still decoded with a 4-gram language model and used LSTM language models to rescore hypotheses; the neural rescorers bought a 22 to 25 percent relative error reduction over the n-gram baseline. The counting table was the spine of the system as late as that.

A vintage typewriter feeding blank tiles along a conveyor belt into a modern server rack

What n-grams still do in 2026

Filter your training data. Meta's CCNet pipeline (Wenzek et al., 2019) trains a 5-gram Kneser-Ney model with the KenLM estimator (Heafield, 2011) on Wikipedia, then scores every Common Crawl document by perplexity under that model and keeps the head of the distribution. KenLM runs on CPUs and chews through a crawl snapshot in hours on a few thousand cores, which is why it became the default quality filter in open pre-training corpora. A 2024 study that set out to improve it ("Rethinking KenLM", arXiv:2409.09613) describes it as the most widely used method for the job, trained on Wikipedia across a long list of downstream corpora. Some fraction of the text your favorite model read during pre-training was admitted by a smoothing scheme from 1995.

Draft your speculative decoding. vLLM and SGLang ship an n-gram method, also called prompt-lookup decoding, for speculative inference. The drafter proposes the next few tokens by finding where the recent output matches earlier text and copying what followed there; the large model verifies the proposals in parallel, and accepted tokens are exactly what the large model would have produced alone. For retrieval-augmented generation, summarization and code editing, where output quotes its input, the n-gram lookup is close to free acceleration. LinkedIn's Hiring Assistant runs n-gram speculation in its vLLM serving stack and reported roughly 4x higher throughput and a 66 percent reduction in P90 latency. A string table from the KenLM era is accelerating production inference for a frontier-deployed agent.

Why it still matters

The n-gram is the minimal version of the bet every language model still makes: that the immediate past constrains the next word, and that statistics over enough text capture the constraint. What the neural generation added was learned generalization, and scale did the rest. The object being estimated never changed. It is still the conditional distribution of the next token, exactly where Shannon put it in 1948.

Sources

educational