NeuralPath // AI & ML Learning Hub

The Core Thesis: Before neural networks and Transformers existed, how did computers predict the next word on your phone keyboard or score whether a sentence sounded like real English? They used N-Gram Language Models—statistical engines that count how often short sequences of $N$ words appear together in a massive text corpus. Understanding N-Grams gives you the exact mathematical foundation of modern Large Language Models, because GPT-4 and Llama-3 solve the exact same next-token probability equation[cite: 10]!

Beginner Foundations: What is a Language Model?

At its core, a Language Model (LM) is any mathematical system that does two equivalent things:

1. Score a Full Sentence

Assigns a probability $P(w_1, w_2, \dots, w_T)$ to an entire sequence of words so a speech recognizer or translator knows that "recognize speech" is much more likely than "wreck a nice beach"!

P("the cat sat") >> P("sat cat the")

2. Predict the Next Word

Given the preceding words, computes the conditional probability of the upcoming word $P(w_t \mid w_1, \dots, w_{t-1})$ [cite: 10]—powering autocomplete and text generation[cite: 10]!

P("mat" | "the cat sat on the")

How are these two tasks connected? Through the Chain Rule of Probability! The probability of any full sentence is simply the product of each word's conditional probability given all the words that came before it:

P(w_1, w_2, \dots, w_T) = P(w_1) \cdot P(w_2 \mid w_1) \cdot P(w_3 \mid w_1, w_2) \cdots = \prod_{t=1}^{T} P(w_t \mid w_1, \dots, w_{t-1})

Why Counting Full Histories Fails Immediately

Suppose we want to compute $P(\text{"mat"} \mid \text{"Yesterday the fluffy ginger cat sat quietly on the"})$ by counting how many times that exact $9$ -word history appeared on the internet. Because language is infinitely creative, almost any long sentence has appeared $0$ times in your dataset! We need a shortcut that looks only at the most recent few words.

Beginner: What is an N-Gram and the Markov Assumption?

An N-Gram is simply a contiguous chunk of $N$ consecutive tokens (words) from a piece of text. Depending on the window size $N$ , we give them specific names:

1. Unigram (

N = 1

)

["the"], ["cat"], ["sat"]

Single isolated words ( $0$ words of context). Assumes every word is chosen independently based purely on how common it is.

2. Bigram (

N = 2

)

["the cat"], ["cat sat"]

2-word pairs. Predicts the next word by looking at only the $1$ immediately preceding word: $P(w_t \mid w_{t-1})$ .

3. Trigram (

N = 3

)

["the cat sat"]

3-word triplets. Predicts the next word by looking at the $2$ preceding words: $P(w_t \mid w_{t-2}, w_{t-1})$ .

To make counting possible, an N-Gram model makes the Markov Assumption: instead of conditioning on the entire paragraph history, we assume the probability of the next word depends only on the last $N - 1$ words:

P(w_t \mid w_1, w_2, \dots, w_{t-1}) \approx P(w_t \mid w_{t-N+1}, \dots, w_{t-1})

⚡ Knowledge Check

In a Trigram ( $N = 3$ ) language model, how many previous words of context does the model look at when predicting the next word $w_t$ ?

A) 2 previous words (because N - 1 = 3 - 1 = 2)▼

✓ Correct!A Trigram consists of

3

words total: the

2

context words

(w_{t-2}, w_{t-1})

plus the

1

target word

w_t

being predicted!

B) 3 previous words▼

✕ Incorrect.Looking at

3

previous words plus the

1

predicted word forms a

4

-word window (a 4-gram). An

N

-gram model always conditions on

N - 1

previous words.

Intermediate: Maximum Likelihood Estimation (Counting & Dividing)

How do we "train" a Bigram ( $N = 2$ ) model on a text dataset? There is no gradient descent required! By Maximum Likelihood Estimation (MLE), the probability $P(w_t \mid w_{t-1})$ is simply the number of times the pair $(w_{t-1}, w_t)$ appeared together, divided by the total number of times $w_{t-1}$ appeared:

P_{\text{MLE}}(w_t \mid w_{t-1}) = \dfrac{\text{Count}(w_{t-1}, w_t)}{\text{Count}(w_{t-1})}

Step-by-Step Worked Example: Calculating Bigram Probabilities by Hand

Suppose our training corpus has $3$ sentences framed with start <s> and end </s> tokens:

<s> I love deep learning </s>
<s> I love machine learning </s>
<s> deep learning is fun </s>

What follows "love"?

\text{Count}(\text{love}) = 2

P(\text{deep} \mid \text{love}) = \dfrac{1}{2} = 0.50, \quad P(\text{machine} \mid \text{love}) = \dfrac{1}{2} = 0.50

What follows "deep"?

\text{Count}(\text{deep}) = 2

P(\text{learning} \mid \text{deep}) = \dfrac{\text{Count}(\text{deep, learning})}{\text{Count}(\text{deep})} = \dfrac{2}{2} = 1.00

Intermediate: The Zero-Probability Trap, Smoothing & Perplexity

What happens at test time if a user types a completely valid phrase like "I love Python", where the bigram ("love", "Python") never appeared in our small training set?

Because $\text{Count}(\text{love, Python}) = 0$ , our MLE formula gives $P(\text{Python} \mid \text{love}) = 0.0$ . Worse yet, because sentence probability multiplies all word probabilities together ( $P_1 \times P_2 \times 0 \times P_4 = 0$ ), a single unseen N-gram makes the probability of the entire document collapse to ZERO (and $\ln(0) = -\infty$ )!

1. Add-

k

/ Laplace Smoothing (

k = 1

)

The simplest fix: add a small count $k$ (e.g., $k=1$ for Laplace smoothing, or $k=0.1$ ) to every possible bigram in the vocabulary of size $|\mathcal{V}|$ , and add $k|\mathcal{V}|$ to the denominator so probabilities still sum to $1.0$ :

P_{\text{Add-}k}(w_t \mid w_{t-1}) = \dfrac{\text{Count}(w_{t-1}, w_t) + k}{\text{Count}(w_{t-1}) + k|\mathcal{V}|}

2. Interpolation & Kneser-Ney Backoff

For large vocabularies, Linear Interpolation blends Trigram, Bigram, and Unigram probabilities together ( $\lambda_3 P_3 + \lambda_2 P_2 + \lambda_1 P_1$ where $\sum \lambda_i = 1$ ) so the model falls back to shorter contexts when a 3-gram is unseen!

\hat{P}(w_t \mid w_{t-2}, w_{t-1}) = \lambda_3 P_3 + \lambda_2 P_2 + \lambda_1 P_1

How We Evaluate ANY Language Model: Perplexity ( $\text{PPL}$ )

How do researchers compare an N-Gram model, Llama-3, and GPT-4 on a test dataset? We use Perplexity ( $\text{PPL}$ ), which is simply the exponential of the average Cross-Entropy (Negative Log-Likelihood) Loss over $T$ test tokens:

\text{Perplexity (PPL)} = \exp\left( -\dfrac{1}{T} \sum_{t=1}^{T} \ln P(w_t \mid w_{\lt t}) \right) = \exp(\mathcal{L}_{\text{Cross-Entropy}})

Intuitive Meaning of Perplexity (Lower is Better!)

Perplexity measures the effective branching factor—how "surprised" or confused the model is by the test text. If a language model has a Perplexity of $10$ , it means that on average, at each step, the model is as uncertain as if it had to choose uniformly among $10$ equally likely words. A perfect model that predicts every word with $100\%$ certainty ( $P = 1.0$ ) has the lowest possible Perplexity of $e^0 = 1.0$ !

⚡ Knowledge Check

You evaluate two language models on a validation dataset. Model A achieves an average Cross-Entropy Loss of $2.0$ ( $\text{PPL} = e^{2.0} \approx 7.39$ ), while Model B achieves a Cross-Entropy Loss of $4.0$ ( $\text{PPL} = e^{4.0} \approx 54.60$ ). Which model is better?

A) Model A (Lower Perplexity 7.39 means higher probability assigned to the true test words!)▼

✓ Correct!Lower Perplexity is always better: Model A narrows the next token down to

\approx 7.4

plausible choices on average, whereas Model B is confused among

\approx 54.6

choices.

B) Model B (because 54.60 is a larger number)▼

✕ Incorrect.Perplexity is

\exp(\text{Loss})

—so a higher Perplexity means higher error and lower confidence on the ground-truth tokens.

Advanced: Why N-Grams Hit a Wall & How Neural LLMs Replaced Them

Why can't we just build a $50$ -gram count model to rival ChatGPT? Because classical N-Gram models suffer from three fatal scaling bottlenecks that only Neural Language Models (Embeddings + Transformers) could solve:

Bottleneck	Classical N-Gram Count Model	Modern Neural LLM (Transformer)
1. Curse of Dimensionality	Table size explodes as $\|\mathcal{V}\|^N$ . For $\|\mathcal{V}\|=50\text{k}$ , a 4-gram table has $6.25 \times 10^{18}$ cells!	Uses fixed-size weight matrices $\mathbf{W}$ that scale linearly/quadratically with dimension $d$ , not $\|\mathcal{V}\|^N$ .
2. Zero Semantic Sharing	Seeing "the cat chased the mouse" teaches the model zero about "the dog pursued the rodent"!	Vector Embeddings place "cat" and "dog" nearby in $\mathbb{R}^d$ , generalizing across synonyms automatically!
3. Myopic Context Window	Blind to anything beyond $3\text{--}5$ words ago; forgets a character's name from the previous sentence.	Self-Attention attends directly across $32\text{k}\text{--}1\text{M}+$ tokens of context!

Where N-Grams Are Still Used in Modern AI Today!

Even in the age of GPT-4, N-Grams are used every day for: (1) Evaluation Metrics like BLEU (precision of $1\text{--}4$ grams in machine translation) and ROUGE-N (summarization overlap), (2) BM25 / TF-IDF Keyword Retrieval inside Hybrid RAG systems, and (3) N-Gram Speculative Decoding, where a fast N-gram lookup drafts candidate tokens from the prompt and the LLM verifies them in parallel!

⚡ Knowledge Check

A Trigram model is trained on a corpus containing "The surgeon walked into the operating room" $500$ times, but the phrase "The physician walked into the operating room" never appeared once. Why does a Neural Language Model assign a high probability to the second sentence while the unsmoothed Trigram model assigns $0$ ?

A) Neural models represent "surgeon" and "physician" as similar dense vectors; N-grams treat words as unrelated discrete symbols▼

✓ Correct!Because N-gram tables index by exact string IDs, zero information transfers between synonyms. Neural LMs map both words to nearly identical vectors in embedding space, so anything learned about "surgeon" generalizes to "physician"!

B) Because Neural Language Models do not predict conditional probabilities▼

✕ Incorrect.Both N-gram models and Neural LLMs predict the exact same conditional distribution

P(w_t \mid \text{context})

[cite: 10]; they differ in how they parameterize that function (count tables vs. continuous embeddings + neural weights).

Visual Explanation: From N-Gram Counts to Perplexity & Generation

Look at how a statistical N-Gram Language Model extracts sliding windows of $N$ tokens, builds a smoothed conditional probability table, evaluates test sentences via Perplexity, and generates new text autoregressively:

Python Implementation: Smoothed Bigram Language Model & Perplexity Calculator

Here is a complete, runnable Python implementation of a Laplace-Smoothed Bigram Language Model that trains on a text corpus, computes exact Perplexity on an unseen test sentence, and generates text autoregressively:

ngram_language_model.pyPython 3.11+ · Math & Collections

import mathfrom collections import Counter # 1. Training Corpus Framed with <s> (BOS) and </s> (EOS)corpus = [    "<s> neural networks learn representations </s>",    "<s> neural networks predict tokens </s>",    "<s> language models predict tokens </s>"] unigramCounts = Counter()bigramCounts = Counter()vocab = set() for sentence in corpus:    tokens = sentence.split()    vocab.update(tokens)    for i in range(len(tokens)):        unigramCounts[tokens[i]] += 1        if i > 0:            bigramCounts[(tokens[i - 1], tokens[i])] += 1 vocabSize = len(vocab) # 2. Add-k (Laplace) Smoothed Bigram Probability P(w_t | w_)def bigramProb(prevWord: str, targetWord: str, k: float = 0.1) -> float:    num = bigramCounts[(prevWord, targetWord)] + k    den = unigramCounts[prevWord] + (k * vocabSize)    return num / den # 3. Compute Sentence Perplexity: exp( -1/T * sum(ln P(w_t | w_)) )def computePerplexity(sentence: str, k: float = 0.1) -> float:    tokens = sentence.split()    logProbSum = 0.0    numPredictions = len(tokens) - 1    for i in range(1, len(tokens)):        prob = bigramProb(tokens[i - 1], tokens[i], k=k)        logProbSum += math.log(prob)    avgNegLogLikelihood = -logProbSum / numPredictions    return math.exp(avgNegLogLikelihood) seenSentence = "<s> neural networks predict tokens </s>"unseenMix    = "<s> language models learn representations </s>"print("P(networks | neural):", round(bigramProb("neural", "networks"), 4))print("Perplexity on Seen Sentence:", round(computePerplexity(seenSentence), 3))print("Perplexity on Unseen Mix:", round(computePerplexity(unseenMix), 3))

Pro Tip (Why We Sum Log-Probabilities Instead of Multiplying Raw Probabilities):

Look at logProbSum += math.log(prob) inside computePerplexity()! If a test book has $10{,}000$ words and each word has probability $0.1$ , multiplying $0.1^{10000}$ immediately underflows to 0.0 in 64-bit floating-point arithmetic. Summing $\ln P$ in log-space and taking $\exp()$ at the very end completely prevents numerical underflow!

Key Points

✓A Language Model assigns probabilities to sequences of tokens via the Chain Rule of Probability:

P(w_1, \dots, w_T) = \prod_{t=1}^{T} P(w_t \mid w_1, \dots, w_{t-1})

✓An N-Gram model applies the Markov Assumption to approximate the full history using only the preceding

N - 1

tokens (Unigram

N=1

, Bigram

N=2

, Trigram

N=3

✓Maximum Likelihood Estimation (MLE) computes N-gram probabilities by simple frequency ratios:

P(w_t \mid w_{t-1}) = \dfrac{\text{Count}(w_{t-1}, w_t)}{\text{Count}(w_{t-1})}

✓Smoothing techniques (Laplace Add-

k

Smoothing, Linear Interpolation, and Kneser-Ney Backoff) prevent unseen N-grams from assigning zero probability to valid test sentences.

✓Perplexity (

\text{PPL} = \exp(\text{Cross-Entropy Loss})

) is the universal intrinsic evaluation metric for both N-gram models and modern LLMs; lower Perplexity means a better, more confident model.

✓Classical N-grams suffer from exponential memory growth (

|\mathcal{V}|^N

) and zero semantic generalization across synonyms—limitations solved by Word Embeddings and Transformers.

Common Mistakes

✕ Evaluating an unsmoothed N-gram model on unseen test data.

Without smoothing or backoff, a single unseen word pair yields $P = 0$ , causing $\ln(0) = -\infty$ and an infinite Perplexity score! Always apply smoothing or interpolation.

✕ Multiplying raw probabilities P_1 * P_2 * ... * P_T instead of adding log-probabilities.

Multiplying more than a few dozen probabilities smaller than $1.0$ causes floating-point underflow to zero. Always compute $\sum \ln P(w_t \mid \text{context})$ in log space.

✕ Comparing Perplexity scores between two models that use different tokenizers/vocabularies.

Perplexity is a branching factor over a specific vocabulary $|\mathcal{V}|$ . A model with a $32\text{k}$ vocabulary will naturally have a lower per-token Perplexity than a model with a $128\text{k}$ vocabulary! Only compare Perplexity directly when models share the same tokenizer (or normalize by character/byte count).

✕ Forgetting to add start <s> and end </s> boundary tokens before counting N-grams.

Without <s>, the model does not know which words are likely to start a sentence; without </s>, generated sequences have no way to know when a sentence is complete and probabilities over all finite-length strings do not sum to $1.0$ .

The Big Picture

Classical N-Gram Language Models (Count Tables)

Look Back Only 2–4 Words → Exact String Matching → Zero Synonym Sharing → Explodes at Large N

Neural Language Models / LLMs (Embeddings + Self-Attention)

Same Next-Token Equation P(w_t | context) → Continuous Vector Space → 100k+ Context Window!

The important conceptual shift is realizing that the goal of language modeling has never changed: both a 1990s Trigram model and GPT-4 are autoregressive engines trying to minimize Perplexity by predicting $P(w_t \mid \text{context})$ [cite: 10]. What changed is how we compute that probability—moving from brittle, discrete count tables to continuous Word Embeddings and Transformer Self-Attention.

Remember: N-Grams proved that simple next-word prediction could capture grammar and local fluency, and their core failure—treating words as isolated symbols with zero shared meaning—directly motivated the invention of Word Embeddings!

N-Grams and Language Models

Beginner Foundations: What is a Language Model?

Beginner: What is an N-Gram and the Markov Assumption?

Intermediate: Maximum Likelihood Estimation (Counting & Dividing)

Step-by-Step Worked Example: Calculating Bigram Probabilities by Hand

Intermediate: The Zero-Probability Trap, Smoothing & Perplexity

How We Evaluate ANY Language Model: Perplexity (PPL\text{PPL}PPL)

Advanced: Why N-Grams Hit a Wall & How Neural LLMs Replaced Them

Visual Explanation: From N-Gram Counts to Perplexity & Generation

Python Implementation: Smoothed Bigram Language Model & Perplexity Calculator

Key Points

Common Mistakes

The Big Picture

How We Evaluate ANY Language Model: Perplexity ( $\text{PPL}$ )