Number Class
← Back to Explore
Computer Science Artificial Intelligence & Data Vector Embedding Design

The Ruler That Measures Nothing Fixed

A 2024 Netflix/Cornell paper shows cosine similarity scores can shift arbitrarily between equally valid training runs of the same model.

S.J. Nam 7 min read
The Ruler That Measures Nothing Fixed

The One Billion Vector Bluff

In 2017, engineers at Facebook announced they'd hit a milestone that sounds almost boring until you sit with the number:
the first k-nearest-neighbor graph constructed on 1 billion high-dimensional vectors
. The library that did it, FAISS, would go on to become
a tool that can handle billions of vectors and leverage GPUs for search, allowing for fast query speeds, widely used in academia and industry for embedding indexing and nearest-neighbor search at scale
. Today it sits, mostly invisible, underneath chatbots, recommendation engines, and the "similar documents" panel of every serious search product. Ask people what these systems do and they'll say something like: it finds the text most similar to yours. That sentence is true in the way "the weather forecast says it will rain" is true — a confident-sounding output built on a stack of approximations nobody mentions in the demo.

Here is the thesis worth defending: the "nearest neighbor" that AI hands you is neither reliably nearest nor, in high dimensions, a coherent notion of neighbor at all. It is a negotiated compromise — negotiated between speed and accuracy at the algorithmic level, and between mathematical convenience and actual meaning at the conceptual level. Treat that compromise as ground truth, and you get systems that sound authoritative precisely where they're guessing.

Cover and Hart's Clean Idea, and Why It Broke

The idea starts simply enough. In 1967, Thomas Cover and Peter Hart gave the field its founding theorem:
Thomas Cover and Peter Hart proved an upper bound error rate with multiclass kNN classifications
, a result showing that the dumbest possible classifier — just go with whatever label your closest training example has — performs surprisingly well, bounded at roughly twice the error of the theoretically optimal classifier. Their paper,
"Nearest Neighbor Pattern Classification," which proved mathematical bounds on error rates for multiclass KNN classification
, is one of those rare pieces of math that's both elegant and load-bearing; half a century later it's still the conceptual skeleton of every embedding search.

But Cover and Hart were working in low dimensions, with a handful of measured features. Text embeddings live in spaces of 768, 1536, 3072 dimensions or more. And something strange happens to the concept of "distance" as dimensionality climbs: it stops discriminating. Researchers studying what's now called distance concentration have shown that
one aspect of the dimensionality curse is distance concentration, which denotes the tendency of distances between all pairs of points in high-dimensional data to become almost equal
. Push that far enough and the gap between your "nearest" neighbor and your "farthest" neighbor shrinks toward nothing — the entire premise of ranking by closeness starts to wobble. This is the genuinely counterintuitive part most explainers skip: adding more dimensions to an embedding, which sounds like it should capture more nuance and thus better similarity, can instead make similarity rankings less meaningful, not more.

The Cosine Similarity Con

If distance itself gets shaky in high dimensions, the metric everyone actually uses to sidestep the problem has its own quiet scandal. Nearly every text-embedding system — search, recommendation, retrieval-augmented generation — measures "similarity" not by raw distance but by cosine similarity: the angle between two vectors, ignoring their length. It's treated as a neutral, almost physical fact about the text. A 2024 paper out of Netflix and Cornell, led by Harald Steck, Chaitanya Ekanadham, and Nathan Kallus and
published at WWW '24
, found otherwise. The authors concluded that
cosine similarity of the learned embeddings can in fact yield arbitrary results
, and traced the cause not to some implementation bug but to something structural:
the underlying reason is not cosine similarity itself, but the fact that the learned embeddings have a degree of freedom
introduced by how the model was regularized during training. In plain terms: two different — but equally valid — training runs of the same embedding model can produce cosine-similarity rankings that disagree with each other, not because either is "wrong," but because the geometry each model happens to settle into during optimization is itself somewhat arbitrary. That's the detail most coverage of AI similarity search leaves out entirely: the yardstick isn't fixed. It's an artifact of an optimizer's private decisions, dressed up as a universal measure of meaning.

Fast, Approximate, and Confident Anyway

Layer the algorithmic problem on top of the conceptual one. Even if you trusted cosine similarity completely, computing exact nearest neighbors against a billion vectors, one query at a time, is far too slow for anything resembling a product. So the field made peace with approximation. The dominant method now, Hierarchical Navigable Small World graphs, was introduced by Yu Malkov and Dmitry Yashunin, whose paper describes
a new approach for the approximate K-nearest neighbor search based on navigable small world graphs with controllable hierarchy
. Reviewers of the method note that HNSW
is a powerful tool for approximate nearest neighbor search
precisely because its layered graph structure lets it
achieve logarithmic search complexity
instead of scanning every vector. That trade is the whole point: you give up the guarantee of finding the true nearest neighbor in exchange for finding a very-probably-close one, thousands of times faster.

Every production vector database — the infrastructure behind FAISS deployments, Pinecone, Weaviate, Milvus — runs on some version of this bargain, tunable by a recall parameter most users never touch. Push the parameter toward speed and the system will occasionally hand you the fourteenth-nearest neighbor while calling it the first. Nobody displays a confidence interval on that. The chatbot doesn't say "here's a passage that's probably, but not certainly, the most relevant one I could find, using a similarity metric that might rank differently if the underlying model had been trained with slightly different regularization." It just states the retrieved text as if closeness were settled fact.

What the Approximation Costs

None of this means nearest-neighbor search is a scam — FAISS's billion-vector graph and HNSW's logarithmic search are real engineering triumphs that make modern retrieval possible at all, and Cover and Hart's sixty-year-old bound still holds up remarkably well as a description of why the simple idea works so often. The case here isn't that similarity search is broken; it's that it's being sold, implicitly, as more objective than it is. When a retrieval-augmented generation system pulls the "most similar" passage into a legal brief, a medical query, or a research summary, the confidence of that retrieval is doing rhetorical work the underlying math can't fully back up — a stacked approximation (concentrated distances, an arbitrary cosine geometry, an ANN graph tuned for speed) standing in for certainty.

The fix isn't to abandon embeddings; it's to stop talking about them as if they locate a fact in space. They locate a compromise. The next time a system tells you it found your nearest neighbor in text, the more honest translation is: it found something close enough, by a ruler it built for itself, as fast as it could manage without checking too carefully. Whether that's good enough depends entirely on what you're about to do with the answer — and that's a judgment no similarity score will make for you.

References