Johnson–Lindenstrauss Lemma

Summary: A result in high-dimensional geometry that says you can project a set of points from very high dimensions down to surprisingly few dimensions while approximately preserving all pairwise distances — and equivalently, that the number of vectors you can fit in ${\mathbb{R}}^d$ that are nearly orthogonal to one another grows exponentially in $d$. This second framing is the one that matters for superposition in neural networks.

The classic statement

Given $n$ points in ${\mathbb{R}}^D$ (think: high-dimensional feature vectors) and an error tolerance $\epsilon \in (0,1)$, there exists a linear map $f:{\mathbb{R}}^D\to {\mathbb{R}}^d$ with

$d=O\left(\frac{\log n}{{\epsilon }^2}\right)$

such that for every pair of input points,

$(1-\epsilon )\Vert \vec{u}-\vec{v}{\Vert }^2\le \Vert f(\vec{u})-f(\vec{v}){\Vert }^2\le (1+\epsilon )\Vert \vec{u}-\vec{v}{\Vert }^2.$

In words: you can project $n$ points down to about $\log n$ dimensions and still have every pairwise distance preserved up to a multiplicative $\epsilon$ error. Remarkably, the needed dimension $d$ depends only on $n$ and $\epsilon$ — not on the original dimension $D$.

A standard proof uses a random Gaussian projection: pick $f$ at random, and with high probability it preserves distances for your fixed point set.

The “near-orthogonal vectors” framing

The version that shows up in superposition discussions is a dual consequence:

In ${\mathbb{R}}^d$, the maximum number of unit vectors you can fit so that every pair has dot product $\le \epsilon$ in absolute value (i.e. all pairs within some angle of perpendicular) grows exponentially in $d$.

Intuitively: as $d$ grows, high-dimensional space is so “spacious” that random unit vectors are already close to perpendicular to each other, and you don’t need many extra dimensions to fit a lot of such vectors.

Scaling intuition

The scaling is sharply nonlinear in the tolerance:

• Tight tolerance $(89°,91°)$ → the exponential regime doesn’t really kick in until $d$ is in the hundreds of thousands.
• Looser tolerance ($85°$, dot product $\lesssim 0.087$) → headroom explodes much earlier.
• At $85°$ and $d=12,288$ (GPT-3’s embedding width), well over $10^{10}$ near-orthogonal unit vectors fit.
• At $85°$ and $d\sim 116,000$ (frontier model scale), the count is somewhere past $10^{100}$ — a googol of room.

This tolerance sensitivity matters: the “superposition gives exponential capacity” story needs a reasonably loose angular budget to be load-bearing.

Why it matters for LLMs

The embedding/residual-stream vectors of a transformer live in a space with $d\sim 10^4$ dimensions. Because JL lets the model pack exponentially many near-orthogonal feature directions into that space, it can represent vastly more distinct concepts than it has dimensions (or neurons). See superposition for the interpretability consequences.

See also

• superposition — the main application here
• word-embedding — the space these vectors live in
• transformer-architecture — where high-dimensional embedding spaces come from

Sources

• src-3b1b-llms-ch4-mlps-store-facts