One Vector Is Not Enough: Where Embedding Search Hits a Wall

The Vector Has a Ceiling. Someone Measured It.

Last time we wrote that a belief is a vector: inside a model, a concept has coordinates you can point at. That is true, and it is powerful. But a vector is also something less flattering: a compression. A single list of numbers standing in for something far richer. And compression has limits.

A team at Google DeepMind and Johns Hopkins just measured one of them, and the result should change how you build retrieval. The paper is On the Theoretical Limitations of Embedding-Based Retrieval (ICLR 2026, arXiv:2508.21038). Its finding is not “embeddings could be better.” It is “embeddings provably cannot do this, and buying a bigger model will not help.”

What They Proved

Almost every RAG system in production works the same way. Turn each document into one vector. Turn the query into one vector. Return the documents whose vectors sit closest. One vector, one dot product, done. It is fast, it generalizes, and it has carried the entire industry.

The paper asks a simple question: can that setup represent every combination of relevance? For a set of documents, can a single-vector model be made to return any group of them as the top matches for some query?

The answer is no, and the ceiling is the embedding dimension. Lay out which documents are relevant to which queries as a giant grid, and the number of distinct “top-k” patterns a set of vectors can reproduce is bounded by how many numbers are in each vector. Past that point, some relevance patterns are not merely unlikely; they are unreachable. No training run, no data, no architecture tweak inside the single-vector paradigm gets you there.

They then put numbers on it. Even in the best possible case (optimizing the vectors directly against the test answers, with none of the constraints of real language), a 512-dimensional embedding runs out at roughly 500,000 documents. A 1024-dimensional one at about 4 million. Even a 4096-dimensional embedding, larger than most production systems run, tops out near 250 million. And that is the generous ceiling. Real models, which also have to model actual language, fall far below it.

Embeddings do not fail here because they were trained badly. They fail because you are asking a fixed number of dimensions to encode more distinctions than it has room for.

The Part That Should Worry You

Theory is easy to wave away. So the authors built LIMIT: a dataset so simple it feels like a joke. Short natural-language facts: “Jon likes quokkas and apples.” A trivial query: “Who likes quokkas?” The only twist is that it systematically covers many combinations of who-likes-what.

State-of-the-art embedding models fail on it. Badly. A task a child solves, and the best dense retrievers in the world cannot.

Meanwhile BM25, the boring keyword algorithm from the 1990s, comes close to perfect. And a multi-vector model beats the single-vector ones by a wide margin. This is not domain shift, and training on more examples does not fix it; the authors checked. The simple task is intrinsically beyond what one vector per document can represent.

Here is why this matters beyond a benchmark. The whole industry is pushing retrieval toward generality: “represent any query, any definition of relevance,” instruction-following search, retrieval that reasons. That is exactly the direction this ceiling lives in. Narrow, natural queries stay fine, which is why your RAG demo worked. Ask the same stack to handle arbitrary logical combinations of relevance, and you walk straight into a wall that scaling does not move.

So What Do You Use Instead

“Vectors are not enough” is only useful if it comes with a next move. There are several, and the honest answer is that none of them is a drop-in replacement: each buys expressiveness at a different cost.

Sparse / lexical search (BM25, SPLADE). The oldest trick beat the newest one on LIMIT. Exact-term matching has no dimension ceiling, and it is cheap. The lesson of the last two years: you threw lexical away too early. It belongs in almost every serious stack.

Multi-vector / late interaction (ColBERT, ColPali). Instead of one vector per document, keep one per token and compare them at query time (MaxSim). Far more expressive than a single vector, and it comes with a bonus: you can see which tokens matched, so retrieval stops being a black box. The cost is storage and compute (thousands of vectors per document), so in practice it reranks a candidate pool rather than scanning everything.

Cross-encoders. The most expressive similarity of all: run query and document through the model together. Also the most expensive: it scores one pair at a time, so it is a final-stage reranker over a short list, never first-stage retrieval.

Where Knowledge Graphs Come In

The alternatives above are all still asking “which text is similar to this query?” A knowledge graph asks a different question entirely: “how are these things connected?”

Instead of dissolving a document into a vector, you extract its entities and the relationships between them, and store those as explicit nodes and edges. Jon likes quokkas. Quokkas live in Australia. Australia is a country. Now a query can traverse: follow the edges, hop from fact to fact and answer questions that no similarity score can, because the answer lives in the structure a single vector throws away. This is what GraphRAG and its lighter cousins (LightRAG, LazyGraphRAG) are built on.

Where graphs genuinely win: multi-hop questions (“which of our suppliers depend on a vendor in a sanctioned region?”), synthesis across many interlinked documents, and disambiguation: a node carries its relationships, so “Jaguar the animal” and “Jaguar the car” are simply different nodes, not two collisions in the same embedding.

Now the honest part, because knowledge graphs get oversold too. Building the graph is real work: you are extracting entities with an LLM, and that step hallucinates and needs correction. Historically the reported gains were inflated: one 2026 bias-corrected analysis found naive RAG slightly beating a popular GraphRAG variant once evaluation leakage was controlled. And the industry’s dirty number is that most enterprise RAG projects never reach production at all, with graph-construction overhead a repeat offender. The 2026 development is that indexing cost has largely collapsed; LightRAG and LazyGraphRAG now index at roughly the price of plain vector RAG. The remaining question is fit, not budget.

Added September 2026. That question of fit now has numbers attached to it. A group at Toronto Metropolitan University (arXiv:2608.28978) built a graph-based memory for long-running agents and measured it against a flat vector baseline at a matched retrieval budget: 0.417 against 0.468 token F1, with the graph behind. Almost the whole gap comes from one kind of question. Where a prior answer has to be recalled word for word, judged correctness drops from 0.911 to 0.607. The cause is structural, since decomposing a turn into entities and relations discards the surface form those questions depend on. The authors note themselves that this tests one small extractor on one benchmark. For the rule of thumb below it adds a third case: alongside exact and combinatorial relevance, a graph also costs you wherever the wording itself matters.

The pragmatic consensus is unglamorous and correct: exhaust hybrid search first. BM25 plus dense vectors, fused, with a reranker on top, beats either alone by 15-30% on recall in practitioner benchmarks. Reach for a knowledge graph when your questions genuinely require synthesis across connected facts, and not before.

When One Vector Is Exactly Right

None of this means embeddings were a mistake. For a large class of problems they are the correct tool, and knowing which class is the entire skill.

A single vector shines when relevance means “semantically similar to this one query,” judged one document at a time. That covers a great deal of real, shipping work:

• Fuzzy search that bridges vocabulary. “How do I cancel my plan?” finding a page titled “Ending your subscription”: no shared keyword, same meaning. This is exactly what BM25 misses and embeddings nail. Dropbox cut empty-result searches by around 17% on this move; support tools like Zendesk shifted real metrics with it.
• Recommendations and “more like this.” Similar products, related articles, matching a résumé to job posts, near-duplicate detection. Here relevance genuinely is similarity, so a similarity score is the right primitive.
• Broad first-stage recall. Pulling a few hundred plausible candidates out of millions, cheaply, before a slower and sharper stage does the precise work.

The discriminator is simple. Vector search wins when relevance is semantic, single-notion and per-item: each result earns its place on its own, by meaning. It breaks when relevance is exact (a part number, an error code, a name; semantic drift turns “Python 3.11 performance” into generic Python tips), combinatorial (you need a specific set, the LIMIT failure), or relational (the answer is defined by connections: the knowledge-graph case).

The working question is “what does relevance mean for this query?” Match the tool to the answer, and one vector is often all you need.

The Real Shift

The “embed everything into a vector database and ship it” era is ending for serious retrieval. Vectors remain a brilliant first-stage recall tool; the problem is that one representation was never going to carry every kind of question. This paper is the proof that the ceiling is real, has coordinates, and does not care how much you spend on a bigger embedding model.

Retrieval is becoming an architecture decision again. Sparse for exact terms. Dense vectors for broad recall. Late interaction for precision. A graph for structure. Composed on purpose, matched to the relevance your product actually needs, not defaulted to whatever the vector-database quickstart showed you.

Why We Track This

When we build retrieval for a client, we do not open with a vector database and hope. We look at the questions the system actually has to answer, measure where the single-vector ceiling would bite, and compose the stack that fits: lexical, dense, late-interaction, graph, in whatever combination the problem earns.

That is the difference between following the quickstart and engineering the system. A vector is a powerful thing. Knowing exactly where it stops being enough is the job.