[maths] How small can I make my embeddings before retrieval degrades?

[akash-coded]

Casebook thread. A reconstructed conversation, written for teaching. The people in it
are illustrative; every number is real and reproducible from the notebook cited below.
Replies are welcome — if you hit this yourself, add your numbers.

The question in one line

I want to cut 1536-dimensional embeddings to something that fits in memory. Johnson–Lindenstrauss
is supposed to answer this — but when I plug my numbers in, the bound says I need more
dimensions than I started with. What am I doing wrong?

The numbers

corpus            n = 1,200,000 chunks
target distortion ε = 0.1
JL bound          d >= 8 ln(n) / ε^2  ~=  11,200
current dimension d = 1,536

Where

nanorag/embed.py — the dim parameter

[akash-coded]

Marcus · cohort peer

You are not doing anything wrong — I think you have just found that JL is useless in practice.
The bound is famously loose. Everyone ignores it and picks 256 or 768 because those work.

I would just sweep the dimension and stop thinking about the lemma.

[akash-coded]

Dana · reviewer · owns the eval harness

Right conclusion, wrong reason, and the reason matters because it is the interview question.

The bound is not "loose" in the sense of being badly derived. It is a worst-case guarantee over
adversarial point sets — it must hold for any million points, including a configuration
constructed to be maximally hard to project.

Real embeddings are nothing like that. They sit close to a low-dimensional manifold, so their
intrinsic dimension is far below 1,536, and random projection preserves what matters far
better than the bound is allowed to assume.

That difference is worth being able to state, because "the bound is loose" sounds like you do
not know why, and "the bound cannot assume structure my data has" shows you do.

[akash-coded]

Marking Dana's correction, and adding the three things the lemma does not promise — which is
where this question usually goes next in an interview.

1 · It says nothing about your query. JL preserves distances among the projected points.
Retrieval computes a similarity between a query, which was not in the set the projection was
chosen for, and the documents. Related results cover that case; the plain lemma does not.

2 · Preserving distance is weaker than preserving rank. A (1 ± ε) distortion can reorder
two documents whose true distances are within 2ε of each other. Retrieval is a ranking
problem and near-ties are exactly where the interesting decisions live.

3 · Random is not learned. PCA, an autoencoder, or a Matryoshka-trained encoder all beat
random projection at a fixed budget, because they can use the data distribution. JL's advantage
is needing no training and no data.

What to actually do, in order:

1. If your encoder was trained with nested representations, truncate and renormalise. The
   first k dimensions are already a usable embedding — no projection matrix, cheaper and better
   than JL.
2. Otherwise sweep d against evidence recall on your own corpus and find where the curve bends.
3. Expect the shape the lemma predicts — graceful degradation, then a cliff — and use it to know
   roughly where not to bother looking.

Full write-up: Johnson–Lindenstrauss. Worth reading alongside
Eckart–Young, because the two answer the same practical
question — how many dimensions — from completely different directions, and neither optimises for
retrieval.