On the Theoretical Limitations of Embedding-Based Retrieval

0:00You ever really stop and think about how much we lean on AI these days? just to find stuff. Oh, constantly. Right. Like from finding a recipe to, you know, asking some AI assistant for really specific nuanced information. These systems are just churning away, digging through tons of data. And we kind of just expect them to pull out the perfect answer every single time. Yeah. We take it for granted, don't we? Totally. But what if there are actual, like, theoretical limits to what these powerful AI models can even understand or retrieve? Limits they just can't get past. Exactly. Limits that even the fanciest daily art systems are hitting and, well, maybe can't overcome, no matter how much data you throw out of them.

0:43That's, yeah, that's a pretty big thought, especially given how much we want AI to do for us. It is. So today we're doing a deep dive into some really fascinating new research. It's from Google DeepMind and Johns Hopkins University. The paper's called On the Theoretical Limitations of Embedding-Based Retrieval, Orion Weller and colleagues. And it's really challenging some basic ideas about AI search. So they're questioning the foundations a bit. Pretty much. Our mission today is to unpack how they're showing these intrinsic limitations of what we call embedding models. And crucially, what does this actually mean for the future of AI search?

1:20Right. The practical implications. Yeah. We'll dig into why these limits exist. And get this, how even queries that seem pretty simple can actually, well, break these cutting edge models. Okay. I'm intrigued. Where do we start? Well, let's set the stage first. Information retrieval, finding stuff online, it's changed massively, hasn't it? Oh, absolutely. Night and day. Remember the old days? Like those sparse techniques. Basically just keyword matching. BM25 and things like that. Yeah. Search cat. You get documents with cat. Simple. Now, though, we have these neural language models using embeddings.

1:55It's a totally different ballgame. It really is. That shift to dense retrieval, it was huge. Instead of just keywords, the entire meaning of your query and every document gets boiled down to a single embedding. Like a numerical fingerprint. Exactly. A point, a vector in this huge multidimensional geometric space. And the magic is it captures meaning, the concept behind the words. That lets it generalize, solve way more complex things than just matching cat to cat. And we've definitely been pushing these models, haven't we? The tests, the benchmarks, they're getting seriously complex. Yeah, we're asking a lot.

2:32We're asking them to handle really subtle queries, complex ideas of what's relevant. I saw some examples in the paper like the Quest dataset, where you're asking for moths or insects or arthropods of Guadalupe using logic. Right, Boolean operators within the query itself. Or Bright, needing actual reasoning, like finding coding problems on LeetCode that share a subtask, like dynamic programming. Yeah, that's way beyond simple keyword spotting. We've certainly come a long way from just finding the word moth. We have, and these benchmarks show how ambitious we've become, you know? expecting these dense retrievers to handle almost anything we throw at them.

3:09But there was always this underlying assumption, right? Well, yeah. People had noticed some limitations before, sure. But the general thinking was, it's probably just, you know, unrealistic queries causing problems. Where we just need better data, bigger models. Exactly. The feeling was we could just engineer our way out of it. But this paper, it really questions that fundamental idea. It suggests some limits aren't just speed bumps. They might be built into the architecture itself. the single vector embedding approach. Okay, so what's the core finding then? What's the theoretical wall? Right, so the main theoretical point they make is this.

3:44The number of unique groups of relevant documents, so they call them top egg subsets, that an embedding model can possibly return for any query. That number is fundamentally limited. Limited how? It's tied directly to the dimension of the embedding, its size, its naive value. Okay, let's unpack that, maybe an analogy. Like, say you have a small drawer. Okay. No matter how clever you are folding your socks, that drawer can only hold so many unique combinations of socks, right? Right. The physical size is a constraint. So the embedding space, this geometric space, is like the drawer. A higher dimension, a bigger D, needs a bigger drawer, maybe holds more combinations.

4:23But the key thing is it still has a hard limit, no matter what. Precisely. That's the core idea. And it's not just something they observed. It's grounded in some pretty deep math. Like what? It connects back to established results in communication complexity theory, specifically something called the sign rank of a matrix. Sign rank. Okay, that sounds technical. It is a bit, but think of it like this. Sign rank measures how complex the relationships are between all possible queries and all possible documents. If you have really intricate patterns of relevance, this query needs these docs. That query needs those docs, but not these ones that complexity needs a high sign rank.

5:03A high sign rank. Demands a high embedding dimension, a big D, just to even have a chance of representing all those complex relationships accurately. It's a mathematical requirement. Wow. Okay. So they're basically saying some combinations of relevant documents just cannot be represented by an embedding model if its dimension isn't big enough. Full stop. That's the takeaway. It's not about better training or more data for those specific cases. It's like trying to fit a square peg in a round hole if the dimension's too small. The architecture itself imposes a ceiling. Exactly. It's an architectural limitation.

5:38That feels significant. Like, it puts a real constraint on where this tech can go. It does. And they didn't just leave it at theory. They tested it empirically. Oh. They set up this best-case scenario. They basically took the test data and directly optimized the embedding vectors themselves. No natural language involved, just pure optimization on the vectors to see what the absolute best performance could be. So like giving the model the answers ahead of time almost, letting it cheat to see the absolute maximum potential. Kind of, yeah. The goal was to find what they called the critical endpoint.

6:12That's the maximum number of documents in for which an embedding of a certain dimension could successfully represent all the possible top cat combinations, even under these ideal optimized conditions. And what did they find? Well, even with small numbers of documents and dimensions, their empirical data showed a very clear pattern. They derived a polynomial function that describes this limit. A formula. Yeah. Y equals 10.5322 plus 4.0309D plus 0.0520D2 plus 0.00037D3. And the really telling part, the R-squared value was 0.999. Okay. R-squared 0.999. For listeners, that basically means the formula is an extremely good fit for the data they observed, right?

6:56Almost perfect prediction. Exactly. It's not just a rough guess. It's a very predictable, quantifiable ceiling based on their observations. So what does it mean in practice when you scale it up? Well, that's where it gets kind of sobering. If you extrapolate that curve out, even a pretty large embedding dimension, say 30070, which is used in some pig models, the theory suggests it might only be able to represent all possible top cat combinations for maybe around 107 million documents. 107 million. Okay. Sounds like a lot, but... Think about the whole web. Or even just a huge company's internal documents.

7:28It's potentially not enough. And even if you go up to 4096 dimensions, it's still only around 250 million documents. Wow. So even in this perfect optimized world, the ceiling hits much sooner than you might think. That's the implication, which led them to think, okay, maybe our current tests aren't actually showing us this problem. Because they don't push these combinations hard enough. Exactly. This led them to create the limit dataset, specifically designed to stress these limitations. Right. You mentioned existing benchmarks might hide this. Why is that? Well, think about how benchmarks are made.

8:02Annotating relevance, saying this document is relevant to this query, is super expensive and time-consuming. Yeah, requires humans usually. Right. So take Quest again. 325 ,000 documents asking for the top 20 relevant ones. The number of potential unique top 20 sets you could possibly make from that many documents is astronomical, like 7.1 times 10 to the power of 91. That's a number I can't even really picture. More than atoms in the universe type number. Pretty much, but Quest only actually has about 3 ,300 queries with relevance judgments. So it's sampling a tiny, tiny fraction of the possible hard combinations.

8:38Exactly. It means these benchmarks barely scratch the surface of the combinatorial complexity, so they don't effectively reveal these fundamental limits. Okay, so existing tests weren't going to cut it. They needed something new. Enter the limit dataset. Yep. They engineered this challenge specifically to expose these weaknesses. What makes it different? How did they build it? It's quite clever. They mapped combinations of documents to simple natural language attributes, like a query could be who likes apples, and the documents are just profiles of people with different likes. Okay, so a simplified but controlled setup.

9:12Right. It uses 50 ,000 documents, 1 ,000 queries, and asks for K2 relevant documents each time. But the key is how they built the relevance relationship, the Quill matrix. They made it dense. Dense meaning? Meaning it was specifically designed to maximize the interconnectedness. Lots of overlap, lots of tricky combinations where documents are relevant to multiple queries in complex ways. This creates many unique and challenging top two combinations. They found a sweet spot with just 46 documents that could generate over a thousand unique top two pairs perfect for testing. And the results. How did the big models do?

9:50Not well. Not well at all. They tested cutting-edge models, you know, GridLM, Quen3 Embeddings, PromptTreever, Gemini Embeddings, Snowflake, Arctic Embed Large, E5 Mistral Instruct. Big dames. Yeah. And they severely struggle, like struggling to even get 20 % recall at 100 on the full limit dataset. 20 % recall at 100. So out of 100 guesses, only 20 were right. That's pretty bad for these systems. It's really poor. And what's more, they couldn't even solve the small version of limit, the one with only 46 documents, even if you looked at the top 20 results. Recall at 20. Wow. Wow. On a 46-item task.

10:24That seems like something they should ace. You'd think so. It's a pretty devastating result for what looks like a simple setup. And did the dimension size matter here, like the theory predicted? Absolutely. Performance was clearly linked to embedding dimensionality. Bigger dimensions generally did better, but still poorly overall. It strongly reinforces that theoretical link. Any other interesting patterns? Well, yeah. Models trained with more diverse instructions, like PompTriever, did comparatively better than others. Still not great, but better. What does that suggest? It might mean that diverse instruction tuning helps models use their limited embedding space more efficiently, perhaps, even if the fundamental capacity limit is still there.

11:05Okay, but could this just be domain shift? You know, the limit data set is artificial. Maybe it's just too weird, too different from what these models usually see. That's a very fair question. And they tested it. How? They took an off-the-shelf model, lighten a modern BERT, embed large, and fine-tuned it specifically on a limit training set, separate from the test set. Okay. So if it was just unfamiliarity, it should learn the domain and improve significantly. You'd expect a big jump. But they only saw minor improvement, like from basically zero to about 2.8 % recall at 10. Tiny. Wow. Oh. But, and this is crucial, when they then trained it directly on the test set, essentially letting it memorize the answers.

11:47Letting it cheat. Right. Then it could overfit and perform well. So that really nails it down, doesn't it? It's not that the model can't learn the patterns if it sees them directly. It's that the underlying task, representing those complex combinations with a single vector, is inherently difficult unless you overfit. Exactly. It confirms the difficulty is intrinsic to the combinatorial representation task for these single vector models. Did they look at how the relevance patterns were structured? Did that matter? Hugely. They did an ablation study looking at different querel patterns, how the query relevance matrix is built.

12:21The dense pattern, the one designed to maximize tricky combinations and used in the main limit data set, was significantly harder than other patterns like random connections or simple cycles or having disjoint sets of documents. How much harder? The impact was massive. GRIT LM's recall at 100 dropped by 50 absolute percentage points on the dense pattern compared to simpler ones. E5 Mistral saw almost a 10x reduction. Whoa. Yeah. They also introduced some metrics like graph density and average query strength to quantify this complexity. And limit has much higher values for these than standard benchmarks like natural questions, hotpot QA, sci-fact.

12:59So limit is just way more combinatorially complex by design. Precisely. And that complexity is what really exposes these theoretical limits. It suggests that as real-world tasks demand more of this kind of nuanced combinatorial retrieval, our current single-vector models are likely to hit this wall more often. Okay, so if single-vector embeddings have these fundamental limits, what are the alternatives? We can't just give up on complex search. No, definitely not. And the research points towards other approaches. It acknowledges that while single vectors are efficient, the community really needs to consider that they will encounter combinations of documents they simply cannot represent, especially with complex instructions.

13:37So what else is there? What about cross encoders or re-rankers, those models that look at the query and document together? Good question. They tested that too using Gemini 2.5 Pro, which is a powerful model often used for re-ranking. The result was pretty striking. On the limit small dataset, the 46 document one, Gemini 2.5 Pro solved all 1 ,000 queries. 100 % accuracy in one go. Wow. So it doesn't have the same limitation. It seems not. Because it processes the query and document pair interactively, it's not forced to compress everything into a single fixed-size vector beforehand. It has more flexibility.

14:16But the downside is compute costs, right? They're slower. Exactly. They're computationally expensive, especially for first-pass retrieval over millions or billions of documents. You can't realistically run a cross encoder over everything. Okay, so cross encoders work, but are slow for the initial search. What else? Multi-vector models show promise. Things like GTE Modern Colbert. How do they work? Instead of one vector per document, they use multiple vectors, often representing different parts or aspects, and then combine them using techniques like MaxSim. More vectors means more capacity to represent complexity.

14:47And how do they do on limit? Greatly above the single vector models. Better, definitely, though still not perfect, like the Reranker. It shows that adding representational capacity helps. Interesting. Anything else? Well, perhaps surprisingly, traditional sparse models, like BM25, the keyword-based one we talked about earlier. How'd it do? Very well. Close to perfect scores on limit. Seriously? The old keyword method? Why? Because its implicit dimensionality is much, much higher. By focusing on individual words and phrases, it has many more dimensions or features to work with. It has more slots to represent those specific combinations, so it doesn't hit that low-dimensional bottleneck in the same way.

15:28Huh. So it's less about being intelligent in the AI sense and more about just having more space, more dimensions to store the specific connections needed for these tricky combat tutorial tasks? In a way, yes. It's like comparing, I don't know, a massive library with a detailed card catalog versus a single, very dense, very sophisticated summary of all the books. The summary is smart. It understands concepts. Right. But it just can't hold every specific detail and cross-reference the way the full catalog and the giant library can. That's a pretty good analogy, actually. Okay. This has been a really fascinating deep dive.

16:04So let's try and wrap up the main takeaway. I think the core message is pretty clear. These modern single-vector embedding models, as powerful as they are, they have real fundamental limits. Tied directly to their embedding dimension. Exactly. And as we push AI to do more complex, nuanced retrieval, especially following intricate constructions, these limits are going to become more obvious. We might be hitting a wall for certain tasks. Which means we probably need to think beyond just making existing models bigger. I think so. This research really pushes us to consider more diverse approaches, maybe hybrid systems, combining sparse and dense or using multivector models more or finding entirely new ways around this dimensional constraint.

16:48Just scaling up might not cut it for everything. So maybe the provocative thought for listeners is this. Next time you type a really complex query or ask an AI to find something very specific that involves combining lots of ideas, pause for a second. Are you asking that model to do something its very design might fundamentally prevent it from ever doing perfectly? It's definitely something to ponder as we design the next generation of AI systems. Well, thank you for joining us for another deep dive into the weeds of AI research. We hope this gave you plenty to think about. Thanks for having me.

17:21We encourage you to keep exploring these fascinating topics. Until next time.