n-gram

N-gram language models, treated properly: a long-form article, a typed and tested TypeScript implementation, and an interactive explorer that trains a model on text you paste and runs entirely in your browser.

▶ Open the explorer · Read the article · Read the model

The three artifacts are meant to be read together. Every equation in the article that the repository implements is implemented in src/lib/, tested against the property it promises, and reproducible in the explorer in about thirty seconds.

📖 The article	Theory, estimation, sparsity, smoothing (additive → Good–Turing → Jelinek–Mercer → Katz → Kneser–Ney), cross-entropy and perplexity, generation, engineering at web scale, and the lineage to neural LMs. Ten sections, twelve references, real numbers throughout.
🎛️ The explorer	Train on pasted text or your own .txt files, watch $P(w_t \mid w_{t-n+1},\dots,w_{t-1})$ reshape as the context window slides, and act as the sampler yourself. Nothing leaves the page — no fetch, no analytics, no server.
🧮 src/lib/	The model: strict TypeScript, zero runtime dependencies, 50 tests covering the mathematical invariants — above all that every smoothed conditional sums to 1, and that the two engines agree on every count.

Why n-grams, in 2026

An n-gram model is the smallest complete instance of the language-modeling problem. The autoregressive factorization, the cross-entropy objective, perplexity, temperature and top-$k$, and the tension between memorization and generalization all appear here in a form you can compute by hand — and then watch move. What changes on the way to a transformer is one thing: which histories are allowed to share probability mass. An n-gram shares it only between histories that end in the same $n-1$ tokens; a neural model shares it between histories that are close in a learned metric. Smoothing becomes generalization. §9 of the article develops that argument.

Quick start

npm install
npm run dev            # explorer at localhost:5173, hot reload
npm test               # 50 tests: the mathematical invariants
npm run demo           # trains 12 model variants; prints every number quoted in the article

No installation needed to just look: the hosted explorer is the same build. npm run build:single emits one self-contained HTML file you can open from disk, mail to a class, or keep offline — the Web Worker is inlined, so the file has no siblings and makes no network requests.

Using the library directly:

import { NGramModel } from './src/lib/model.js';
import { perplexity } from './src/lib/evaluate.js';
import { toSequences } from './src/lib/tokenize.js';

const seqs  = toSequences(text, 'word');
const model = new NGramModel(3, 'kn', { d: 0.75 }).fit(seqs);

model.prob('lamp', ['the', 'great']);   // P(lamp | the great)
model.dist(['the'], 5);                 // top-5 next-token distribution
model.backoffLadder(['the', 'great']);  // what each order knows about this context
model.generate(30, { temperature: 0.9 });
perplexity(model, seqs);

What the explorer shows

• Walk the chain — the live next-token distribution. Click a bar to emit that token, seed the walk with your own words, watch the context window slide. A backoff evidence ladder shows what each order knows about the current context, and a novelty meter classifies every generated token as a verbatim training continuation or invented by smoothing. Raise $n$ and watch novelty collapse toward zero: generation degenerates into quotation, which is the sparsity argument of §4 made visible.
• The chain as a constellation — the Markov chain as a rotating 3D graph (hand-rolled force layout and perspective projection on a canvas; no 3D library). At orders 3–4 the nodes become multi-token contexts — the de Bruijn view — and the graph visibly shatters.
• The word globe — tokens as cities on a planet. A spherical layout condenses co-occurring words into continents, and every sampled step flies a great-circle route between the cities it touches; routes persist and brighten with traffic.
• Sampling telemetry — distribution entropy and per-choice surprisal, drawn live. The running average of the surprisal trace is the cross-entropy.
• Sparsity · Train-vs-held-out perplexity · Score any sentence — type counts and singleton shares per order, the overfitting picture across $n$, and per-token surprisal shading for any sentence you type.
• Token filters — punctuation, the ⟨/s⟩ sentence marker, and 103 stopwords can each be excluded from the model, with the cost each exclusion imposes on a language model stated in place. The graphs additionally have a display-only "content words" view.

Every control and panel carries an ⓘ explanation. When a quantity is mathematically undefined — perplexity under unnormalized stupid-backoff scores, for instance — the panel explains why instead of printing a number.

Two engines, one truth

	exact engine	big engine
source	src/lib/model.ts	src/lib/big.ts
used for	corpora ≤ 2M chars	corpora > 2M chars (auto-switch)
structure	hash tables per order	token ids + one sorted position index (LSD counting sort)
memory	~100 bytes per distinct n-gram	~12 bytes per token, however many n-grams exist
estimators	MLE, add-$k$, Jelinek–Mercer, interpolated Kneser–Ney	stupid backoff (Brants et al. 2007); held-out perplexity on demand via Jelinek–Mercer over range counts
training	instant, main thread	Web Worker with progress; ~100M chars in ~4s on one laptop core, exercised to 352M

Agreement between them is tested, not assumed: same corpus, two data structures, identical counts (big.test.ts checks against naive recounts and against model.ts).

There is no GPU and no server anywhere. Training an n-gram model is counting; counting is memory-bound rather than FLOP-bound, so the data structure is the lever, not the processor. §8 of the article makes the argument and big.ts is that section made runnable.

Reproducing the article's numbers

npm run demo prints the perplexity table of §5.5, the training-perplexity sequence of §3, and the generation samples of §7. It is seeded, so its output is deterministic and should match the article exactly. If it ever doesn't, the article is wrong — please open an issue.

model ($n=3$, 499-token corpus, 15% held out)	train PPL	test PPL
MLE	1.64	∞
add-$k$ ($k{=}1$)	61.78	96.73
Jelinek–Mercer ($\lambda{=}0.7$)	1.94	27.41
Kneser–Ney ($d{=}0.75$)	3.19	22.30

These are internally comparable and nothing more. Perplexities are only comparable across models sharing a tokenization and an out-of-vocabulary convention, and a 499-token synthetic corpus is not a benchmark. The point of the table is the shape: MLE memorizes and cannot generalize, additive smoothing generalizes by giving up on the data, and the hierarchical methods actually solve the problem.

Layout

ARTICLE.md              the article
src/lib/                the model — zero runtime dependencies, all tests
  tokenize.ts             sentence splitting, word/char tokens, token filters
  model.ts                exact engine: counting, 4 estimators, sampling
  evaluate.ts             cross-entropy, perplexity, per-token surprisals
  big.ts                  big engine: sorted-index counting, stupid backoff,
                          Jelinek-Mercer over range counts
src/app/                the explorer — Lit web components
  store.ts                application state; owns the active engine
  big-worker.ts           trains the big engine off the main thread
  ngx-walk.ts             walk the chain (strip, seed, ladder, distribution)
  ngx-graph.ts            the constellation (orders 2-4)          [+ graph.ts]
  ngx-globe.ts            the word globe (flights over continents) [+ globe.ts]
  ngx-telemetry.ts        live entropy / surprisal traces
  ngx-controls.ts         corpus, upload, unit, filters, order, smoothing
  ngx-ppl.ts              train vs held-out perplexity (both engines)
  ngx-sparsity.ts         k-gram type counts and singleton share
  ngx-score.ts            per-token surprisal scoring
src/styles/tokens.css   design tokens (light + dark)
examples/demo.ts        reproduces every number quoted in the article
examples/train-big.ts   CLI training for corpora beyond browser memory
data/sample.txt         the demo corpus

Stack: TypeScript (strict), Lit 3, Vite 7, Vitest. Lit is the only runtime dependency; the canvases, the layouts and the charts are hand-rolled, which is what makes the single-file build possible.

Scope, honestly

Good–Turing and Katz backoff are derived in the article but are not selectable estimators here, and modified Kneser–Ney (three discounts) is not implemented. The big engine is the KenLM strategy in miniature, not a competitor to it, and has not been benchmarked against it. The throughput and 352M-character figures are measurements from one machine, not a reproducible benchmark — the corpus is not in the repository.

Contributing

Issues and pull requests are welcome — CONTRIBUTING.md explains the two invariants the tests enforce, the two constraints on the app, and what a change to one of the three artifacts obligates in the others. A wrong number or a wrong claim in the article is the most valuable bug you can report. Security issues go through SECURITY.md, never a public issue. Participation is governed by the Code of Conduct.

License

MIT — see LICENSE.