On the Theoretical Limitations of Embedding-Based Retrieval

Embedding-based retrieval models have advanced from sparse methods to dense neural embeddings, tasked with increasingly complex queries and relevance definitions. However, theoretical limits exist on what combinations of relevant documents these embeddings can represent, constrained by embedding dimension.

The authors connect learning theory and communication complexity to show that the number of top-k document subsets representable by embeddings is limited by vector dimension. Even with k=2, some document combinations cannot be encoded, regardless of training or model size.

To empirically validate this, the authors optimize embeddings directly on test data (free embeddings), revealing a critical point where embedding dimension is too small to represent all top-k combinations. This relationship fits a polynomial curve, highlighting scalability challenges.

The authors introduce LIMIT, a simple yet challenging dataset that instantiates all top-k combinations for a small set of documents and queries. Despite task simplicity, state-of-the-art embedding models perform poorly, confirming theoretical limitations in real-world scenarios.

Embedding dimension strongly affects performance on LIMIT. Larger dimensions improve recall but even the biggest models struggle. Sparse lexical models like BM25 excel due to their high dimensionality, while multi-vector models show promise but are not yet widely applied to reasoning tasks.

Training embedding models on LIMIT's training set yields minimal gains, indicating that poor performance is not due to domain shift but intrinsic model limitations. Overfitting on the test set is possible but unrealistic for generalization, reinforcing fundamental constraints.

Different query relevance patterns affect difficulty. Dense qrel matrices with many document combinations are significantly harder for embedding models than sparser patterns, confirming that complexity of top-k combinations drives retrieval challenges.

The authors discuss alternatives to single-vector embeddings: cross-encoders can perfectly solve LIMIT but are computationally expensive; multi-vector models improve expressiveness; sparse models handle many combinations but struggle with instruction-following tasks.

In conclusion, embedding models face fundamental limits in representing all top-k document combinations due to dimensionality constraints. Future retrieval research should explore architectures beyond single-vector embeddings to handle complex, instruction-based queries effectively.