On the Theoretical Limitations of Embedding-Based Retrieval

Introduction: The Evolution of Information Retrieval and Current Challenges

Over the past 20 years, Information Retrieval technology has undergone significant transformations. Initially, sparse, keyword-matching techniques, such as the well-known BM25, were dominant. However, with the advancements in AI and NLP, there has been a shift towards methods centered around LM. These neural models typically transform both queries and documents into a single numerical vector (i.e., an "embedding"), and then assess the relevance between queries and documents by calculating the similarity of these vectors. This approach is known as "dense retrieval."

In recent years, as user demands on retrieval systems have increased—for instance, the desire for models to understand more complex instructions and logical combinations (e.g., in the QUEST dataset, "find documents that contain both Moths and Insects")—single-vector embedding models face new challenges. Researchers at Google DeepMind have discovered that such single-vector embedding models may have fundamental theoretical limitations when processing certain complex information retrieval tasks.

The core objective of this research is to uncover these limitations at a deeper level, rather than merely proposing new evaluation metrics. Their main contributions are in three areas:

1. Theoretical Foundation: They provide the first theoretical proof for this fundamental limitation of embedding models.
2. Best-Case Empirical Analysis: Through an ideal experiment called "free embeddings," they verify that these theoretical limitations persist even under optimal conditions.
3. Real-World Dataset: They constructed a new dataset named LIMIT, specifically designed to simulate real-world complex query scenarios that pose severe challenges to single-vector embedding models.

This research holds significant importance for the entire AI community. It reminds us that as information retrieval tasks become increasingly complex, especially when models are required to return arbitrary combinations of "top-k" relevant documents, single-vector embedding models may reach the limits of their representational capacity. Therefore, we need to consider new evaluation methods and explore alternative retrieval architectures, such as Cross-Encoders or Multi-vector models.

Representational Capacity of Vector Embeddings: The Root of Theoretical Limitations

To understand the limitations of single-vector embedding models, we need to introduce a core theoretical concept: sign_rank.

Analogy Explained with High School Knowledge Background: Imagine we have a set of building blocks (documents) and some construction blueprints (queries). Each blueprint specifies which particular combinations of blocks are needed to complete a structure (relevance).

• Documents: Can be seen as blocks of different shapes, colors, and sizes.
• Queries: Can be seen as blueprints for building a specific structure (e.g., "a red car" or "a flying box").
• Relevance: If a combination of blocks can build the structure according to the blueprint, then they are relevant.
• Vector Embeddings: Like attaching a "label" to each block and each blueprint. This label is a sequence of numbers (a vector), and by comparing the similarity of these labels, we determine if the blocks and blueprints match.
• Embedding Dimension: Can be understood as the length of this "label," or the richness of information that can be recorded on the label. The longer the label, the more features it can record, and theoretically, the more types of block and blueprint combinations it can distinguish.

Now, the core question arises: If we want to use these "labels" to accurately identify all possible matching relationships between block combinations and blueprints, how long do these labels need to be?

sign_rank is an indicator that measures the intrinsic complexity of such a "matching relationship matrix" (i.e., the relevance matrix between queries and documents).

• If a relevance matrix has a high sign rank, it means it contains very complex and diverse matching patterns, like having countless ways to combine blocks and blueprints that need to be identified.
• Research shows that the complexity of query-document relevance patterns that a single-vector embedding model can accurately represent is limited by its embedding dimension. Simply put, if the sign rank (complexity) of the relevance matrix exceeds the upper limit representable by the embedding dimension (label length), then even the most advanced embedding models cannot accurately identify all correct matching relationships.

This is like having an alphabet with only 26 letters; you cannot use it to write a dictionary containing all Chinese characters. The amount of information you can represent is limited. For any fixed embedding dimension d, there will always be some complex relevance patterns that it cannot represent.

Empirical Connection: Validation Under Ideal Conditions

To exclude the influence of language complexity on experimental results, researchers conducted a "free embedding" optimization experiment. This can be seen as an ideal scenario:

• They did not use real language text but directly represented each query and document as a vector that could be freely adjusted (like we can arbitrarily assign any numerical labels to blocks and blueprints).
• Then, they attempted to adjust these vectors through an optimization algorithm (Adam optimizer, a commonly used machine learning optimization tool) so that relevant documents scored higher than irrelevant documents (the objective function was InfoNCE, which can be understood as a "reward good, punish bad" mechanism).

Experiment Purpose: If even under these ideal conditions "free embeddings" cannot solve the problem, then real embedding models, constrained by language, are even less likely to.

Experiment Setup:

• They created random document and query sets and defined the "relevance" between queries and documents.
• Then, they gradually increased the number of documents (n) until the model could no longer solve the problem with 100% accuracy. This point is called the "critical n point."

Experimental Results:

• The results show a clear mathematical relationship between the critical n value (i.e., the maximum number of documents the model can accurately process) and the embedding dimension d, presenting a cubic polynomial curve.
• Key Finding: Even under ideal conditions, the embedding dimension limits the number of documents the model can handle. For example, when the embedding dimension is 512, the model can process a maximum of about 500k document combinations; and even when the dimension is as high as 4096, it can only handle about 250m document combinations. This indicates that for scenarios like internet search, which involve vast numbers of documents, single-vector embedding models still face a theoretical bottleneck in representing all possible complex combinations.

Relationship between critical n value and embedding dimension d

Empirical Connection: Construction and Challenges of the Real-World Dataset LIMIT

Although theoretical analysis and ideal experiments reveal the limitations of single-vector embedding models, how do these limitations manifest in real-world natural language tasks? To answer this question, researchers constructed a dataset called LIMIT (Limitations of Information Retrieval Models on Interconnected Tasks).

Design Philosophy of the LIMIT Dataset:

• Existing retrieval datasets (e.g., QUEST) typically contain only a limited number of query and document combinations because manual relevance annotation is very expensive. However, the actual query space can contain an astronomical number of combinations (e.g., the QUEST corpus might return up to 7.1 x 10^91 unique top-20 document set combinations).
• The design idea behind LIMIT is to artificially create high "sign rank" query-document relevance patterns, thereby maximizing the interconnectedness between documents and queries, specifically to "challenge" single-vector embedding models.
• They achieved this by mapping document combinations to content retrievable by queries, such as "Who likes Apples?", and using synthetic user attributes (e.g., "Jon likes Hawaiian pizza, sports cars, etc.") to generate natural language queries and documents.
• To ensure high interconnectedness, they specifically chose a combination of 46 documents and 1000 queries, such that each query was relevant to 2 documents (i.e., k=2), and there was significant sharing and cross-referencing among these documents.

LIMIT Dataset Creation Process Diagram

Diagram Interpretation: The left side shows an abstract matrix of query-document relevance, where blue squares represent relevance, and dashed squares represent all possible combinations that the embedding model needs to represent. The right side is a real-world instantiation of the LIMIT dataset. For example, the query "Who likes Quokkas?" needs to retrieve both documents: "Jon Durben likes Quokkas and Apples" and "Ovid Rahm likes Quokkas and Rabbits".

Model Evaluation and Results:

• Researchers tested various state-of-the-art single-vector embedding models, including GritLM, Qwen 3 Embeddings, and Gemini Embeddings, with embedding dimensions ranging from 1024 to 4096.
• They also tested non-single-vector models, such as BM25 (a sparse model) and gte-ModernColBERT (a multi-vector model).
• Core Finding: On the full LIMIT dataset, the performance of all single-vector embedding models was very poor, with recall@100 (the proportion of relevant documents found within the first 100 retrieved results) barely reaching 20%. Even on a smaller version of the LIMIT dataset with fewer documents, these models could not effectively solve the task.
• Dimension and Performance: Model performance was closely related to the embedding dimension; larger dimensions led to better performance, consistent with theoretical analysis and free embedding experiments.
• Advantages of Alternative Architectures: In contrast, gte-ModernColBERT (a multi-vector model) significantly outperformed single-vector models, and traditional BM25 (a sparse model) even achieved near-perfect scores. This strongly suggests the potential of non-single-vector architectures in handling such complex relevance tasks.

Model Scores on the LIMIT Task

Diagram Interpretation: This chart displays the recall@2, recall@10, and recall@100 scores of different embedding models on the LIMIT dataset. It can be seen that all single-vector models (solid lines) have very low scores, while BM25 and gte-ModernColBERT (dashed lines) perform much better.

Model Scores with Different Embedding Dimensions on the Small Version of LIMIT Task (N=46)

Diagram Interpretation: On the smaller version of LIMIT with fewer documents (N=46), the performance of single-vector models (solid lines) improved somewhat but still failed to achieve high scores, further confirming the limitation of embedding dimensions on performance.

In-depth Analysis: Reasons for Poor Performance

• Is it Domain Transfer? Researchers ruled out "domain transfer" (i.e., the models being unfamiliar with the language patterns in the LIMIT dataset) as the cause of low performance. They found that even with fine-tuning on the LIMIT training set, model performance barely improved. This indicates that the issue lies in the intrinsic difficulty of the task itself, rather than the model's inability to adapt to the data.

Training on the LIMIT Training Set Does Not Significantly Improve Performance

Diagram Interpretation: The green line represents the performance of models trained on the training set, with recall@2 being almost 0, while the blue line represents models trained (overfitted) on the test set, showing significant improvement. This indicates that low performance is not caused by domain transfer.

• Impact of Query Relevance Patterns: The study found that when the qrel matrix (query-document relevance matrix) had higher interconnectedness (i.e., "dense patterns"), single-vector models performed worse. This further confirms that tasks with higher sign rank (higher complexity) are more difficult for single-vector models.

Model Results for LIMIT Dataset Under Different Query Relevance Patterns

Diagram Interpretation: This chart shows model performance under different relevance patterns (random, cyclic, disjoint, dense). In the "dense" pattern, the scores of all single-vector models significantly decreased, reconfirming the difficulty of highly interconnected tasks.

• Correlation with MTEB: The study also compared model performance on LIMIT with performance on BEIR (a benchmark used in MTEB v1). The results showed no significant correlation between the two. This suggests that the LIMIT dataset indeed captures unique problems that challenge single-vector embedding models, which were not previously addressed by existing benchmarks.

No Significant Correlation Between BEIR and LIMIT Performance

Diagram Interpretation: This scatter plot shows no clear linear relationship between model scores on the BEIR and LIMIT datasets, indicating that LIMIT evaluates capabilities different from traditional benchmarks.

Alternative Approaches to Embedding Models

Given the limitations of single-vector embedding models, what alternative approaches can better handle these complex information retrieval tasks?

1. Cross-Encoders:
   • How they work: Unlike single-vector models, cross-encoders do not generate separate vectors for queries and documents. Instead, they take both the query and document together as input, allowing the model to perform joint encoding and directly output a relevance score. This is like having an experienced expert simultaneously read the blueprint and all the blocks, and then directly judge if they match, rather than just looking at their "labels."
   • Advantages: Because they are not limited by a single embedding dimension, cross-encoders like Gemini-2.5-Pro can achieve 100% accuracy on the small version of the LIMIT dataset.
   • Limitations: Computationally very expensive. Since joint encoding is required every time, they are not suitable for the first stage of rapid retrieval in large-scale document collections.
2. Multi-vector models:
   • How they work: These models generate multiple vectors to represent a query or document, rather than just a single one. For example, a document might be broken down into multiple passages, each with its own vector. During retrieval, relevance is determined by comparing these multiple vectors (e.g., using the MaxSim operator, which takes the maximum similarity). This is like attaching multiple labels to different parts of a building block, or multiple labels to different steps of a blueprint.
   • Advantages: On the LIMIT dataset, multi-vector models (such as gte-ModernColBERT) significantly outperform single-vector models, demonstrating stronger expressive power.
   • Open Questions: The performance of these techniques in more complex instruction following or reasoning tasks requires further research.
3. Sparse models:
   • How they work: For example, traditional BM25 models do not rely on dense vector embeddings but instead use statistical information like term frequency and inverse document frequency to determine relevance. They can be understood as a single-vector model with "very high dimensions," but most elements in their vectors are zero (i.e., "sparse").
   • Advantages: BM25 performed well on the LIMIT dataset because it avoids the dimension limitation issue of neural embedding models.
   • Limitations: Sparse models may struggle with complex instruction following and reasoning tasks that lack lexical or paraphrastic overlap.

Conclusion and Limitations

Core Conclusion: This research by Google DeepMind, through theoretical proof, ideal experiments, and the real-world dataset LIMIT, reveals that current mainstream single-vector embedding models have fundamental theoretical limitations in information retrieval. These models cannot effectively represent all possible "top-k" document combinations, especially when facing highly complex, highly interconnected query-document relevance patterns, where their representational capacity is strictly constrained by the embedding dimension.

This study reminds us that as information retrieval tasks become increasingly complex, such as requiring models to understand and retrieve documents containing arbitrary logical combinations, we will encounter a "combinatorial limit" that single-vector models cannot overcome.

Limitations of the Study:

• The findings of this study primarily target the most common single-vector embedding models and may not fully apply to all other types of models (e.g., multi-vector models).
• The study did not delve into the theoretical performance when allowing for certain errors (e.g., capturing most combinations rather than all).
• While it proved that there are tasks that single-vector models can never solve, it did not explicitly pinpoint which specific types of combinations these models will fail on.

Appendix: Brief Explanations of Other Related Concepts

• Triangle Inequality: This is a mathematical concept stating that in a metric space, the distance between any two points is not greater than the sum of their distances to a third point. While useful in geometry, it cannot be used to prove the theoretical limitations of embedding models because cosine similarity, commonly used in vector search, does not satisfy the properties of a metric space.
• Order-K Voronoi Regions: This is a concept from computational geometry describing regions in space closest to a specific k number of points. Although it shares similarities with retrieving top-k result sets in information retrieval, this study chose to analyze the limitations of embedding models through sign rank due to computational complexity.
• Metrics for Measuring Query Relevance Graph Density:
  • Graph Density: Measures how tightly connected a graph is. In a query-document relevance graph, it represents the proportion of edges between document nodes. Higher density indicates more complex and interconnected relevance among documents.
  • Average Query Strength: Measures the average strength of connections between queries in a dataset. Higher strength indicates more complex relevance among queries.
  • Comparison of LIMIT with other datasets: The LIMIT dataset scores significantly higher on both these metrics than other standard information retrieval datasets (e.g., NQ, HotpotQA, SciFact) and instruction-following datasets (e.g., FollowIR Core17). For example, LIMIT's average query strength is as high as 28, while other datasets typically have 0.6 or lower. This further emphasizes the unique challenge of the LIMIT dataset, as it simulates highly interconnected and complex retrieval scenarios.

Comparison of Query Relevance Matrix Density Metrics

• The LIMIT dataset scores significantly higher on both Graph Density and Average Query Strength metrics compared to other standard information retrieval datasets (e.g., NQ, HotpotQA, SciFact) and instruction-following datasets (e.g., FollowIR Core17).
• For example, the Query Similarity (Average Query Strength) of LIMIT is as high as 28, while other datasets are only 0.6 or lower.
• Empirical ablation experiments suggest that datasets with higher values for these metrics are harder for retrieval models to represent, although this cannot be definitively proven.