On the Theoretical Limitations of Embedding-Based Retrieval

2025/08/28 by Orion Weller, Weller, Orion, Michael Boratko +5 · 22 voices · 40 citations
#cs.IR #cs.CL #cs.LG

paper · pdf · doi:10.48550/arxiv.2508.21038

Abstract

Vector embeddings have been tasked with an ever-increasing set of retrieval tasks over the years, with a nascent rise in using them for reasoning, instruction-following, coding, and more. These new benchmarks push embeddings to work for any query and any notion of relevance that could be given. While prior works have pointed out theoretical limitations of vector embeddings, there is a common assumption that these difficulties are exclusively due to unrealistic queries, and those that are not can be overcome with better training data and larger models. In this work, we demonstrate that we may encounter these theoretical limitations in realistic settings with extremely simple queries. We connect known results in learning theory, showing that the number of top-k subsets of documents capable of being returned as the result of some query is limited by the dimension of the embedding. We empirically show that this holds true even if we directly optimize on the test set with free parameterized embeddings. Using free embeddings, we then demonstrate that returning all pairs of documents requires a relatively high dimension. We then create a realistic dataset called LIMIT that stress tests embedding models based on these theoretical results, and observe that even state-of-the-art models fail on this dataset despite the simple nature of the task. Our work shows the limits of embedding models under the existing single vector paradigm and calls for future research to develop new techniques that can resolve this fundamental limitation.

Citations

• Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilities
• A Comparative Study of Clinical ModernBERT and BioMedical ModernBERT on the DDXPlus Dataset
• Chameleon: Mixed-Modal Early-Fusion Foundation Models
• Improving Text Embeddings with Large Language Models
• Matryoshka Representation Learning
• Training Compute-Optimal Large Language Models
• Training language models to follow instructions with human feedback

Cited by

• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity
• Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach
• Semantically Similar, Logically Distinct: Diagnosing the Semantic-Answerability Gap in Table RAG
• Vectorizing the Trie: Efficient Constrained Decoding for LLM-based Generative Retrieval on Accelerators
• Superintelligent Retrieval Agent: The Next Frontier of Agentic Retrieval
• From Topology to Retrieval: Decoding Embedding Spaces with Unified Signatures
• Generative Query Expansion with Multilingual LLMs for Cross-Lingual Information Retrieval
• Research and Prototyping Study of an LLM-Based Chatbot for Electromagnetic Simulations
• Structured RAG for Answering Aggregative Questions
• Beyond Single Embeddings: Capturing Diverse Targets with Multi-Query Retrieval
• All-in-one Graph-based Indexing for Hybrid Search on GPUs
• LIR: The First Workshop on Late Interaction and Multi Vector Retrieval @ ECIR 2026
• AutoSurvey2: Empowering Researchers with Next Level Automated Literature Surveys
• Is Dimensionality a Barrier for Retrieval Models?
• Understanding LoRA as Knowledge Memory: An Empirical Analysis
• Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods
• Optimizing Retrieval for RAG via Reinforced Contrastive Learning
• Toward Clinically Grounded Foundation Models in Pathology
• GRATING: Low-Latency and Memory-Efficient Semantic Selection on Device
• Investigating LLM Capabilities on Long Context Comprehension for Medical Question Answering
• Fantastic (small) Retrievers and How to Train Them: mxbai-edge-colbert-v0 Tech Report
• GemiRec: Interest Quantization and Generation for Multi-Interest Recommendation
• PRISM: Agentic Retrieval with LLMs for Multi-Hop Question Answering
• LLM-guided Hierarchical Search for End-to-end Reasoning Intensive Retrieval
• Automatic Music Sample Identification with Multi-Track Contrastive Learning
• The Hybrid Multimodal Graph Index (HMGI): A Comprehensive Framework for Integrated Relational and Vector Search
• Beyond the limitation of a single query: Train your LLM for query expansion with Reinforcement Learning
• The Geometry of Reasoning: Flowing Logics in Representation Space
• PairSem: LLM-Guided Pairwise Semantic Matching for Scientific Document Retrieval
• Diffusion-Inspired Masked Fine-Tuning for Knowledge Injection in Autoregressive LLMs
• PLUM: Adapting Pre-trained Language Models for Industrial-scale Generative Recommendations
• TalkPlay-Tools: Conversational Music Recommendation with LLM Tool Calling
• Improving Consistency in Retrieval-Augmented Systems with Group Similarity Rewards
• A-VERT: Agnostic Verification with Embedding Ranking Targets
• Milco: Learned Sparse Retrieval Across Languages via a Multilingual Connector
• CustomIR: Unsupervised Fine-Tuning of Dense Embeddings for Known Document Corpora
• Understanding Generative Recommendation with Semantic IDs from a Model-scaling View
• Does Generative Retrieval Overcome the Limitations of Dense Retrieval?
• Global Minimizers of Sigmoid Contrastive Loss
• MetaEmbed: Scaling Multimodal Retrieval at Test-Time with Flexible Late Interaction

Discussions

• The Theoretical Limitations of Embedding-Based Retrieval [hn, 151 points, 38 comments]
• [arXiv] On the Theoretical Limitations of Embedding-Based Retrieval arxiv.org/abs/2508.2... It's impossible to retrieve all combinations of pairs of documents post-embedding. Thus, there's usecases th [bsky, 11 points, 0 comments]
• [3/3] "Semantic search" has mathematical blind spots. If you abandon exact keywords for pure vector search, you lose visibility on logic-based queries. arxiv.org/pdf/2508.21038 [bsky, 2 points, 0 comments]
• On the Theoretical Limitations of Embedding-Based Retrieval #embeddings #rag #limits [bsky, 1 points, 0 comments]
• ⭐️🔗 arxiv.org/abs/2508.210... 👉 Discuss with me in Discord: linktr.ee/qdrddr [bsky, 1 points, 0 comments]
• クエリ・文書間のrelevanceをベクトルの内積で表現する、という問題設定にしたとき、埋め込み次元を固定する限りdocumentが増えるとrelevance=1 の文書をすべて漏れなく上位に置くことができなくなるということを示しているらしい。単一ベクトルretrievalの限界 www.arxiv.org/abs/2508.21038 [bsky, 1 points, 0 comments]
• Embeddings are an essential component in AI systems, and understanding their scaling limitations is critical; Google has published an interesting paper that dives into just that: Paper: www.arxiv.org/ [bsky, 1 points, 0 comments]
• The Theoretical Limitations of Embedding-Based Retrieval #HackerNews https://arxiv.org/abs/2508.21038 [bsky, 0 points, 0 comments]
• The Theoretical Limitations of Embedding-Based Retrieval https://arxiv.org/abs/2508.21038 https://news.ycombinator.com/item?id=45068986 [bsky, 0 points, 0 comments]
• The Theoretical Limitations of Embedding-Based Retrieval https://arxiv.org/abs/2508.21038 [bsky, 0 points, 0 comments]
• On the Theoretical Limitations of Embedding-Based Retrieval [bsky, 0 points, 0 comments]
• The Theoretical Limitations of Embedding-Based Retrieval https://arxiv.org/abs/2508.21038 (https://news.ycombinator.com/item?id=45068986) [bsky, 0 points, 0 comments]
• ⚡ Hackernews Top story: The Theoretical Limitations of Embedding-Based Retrieval [bsky, 0 points, 0 comments]
• On the Theoretical Limitations of Embedding-Based Retrieval www.arxiv.org/abs/2508.21038 [bsky, 0 points, 0 comments]
• 👇 Verriss des Papers "On the Theoretical Limitations of Embedding-Based Retrieval" (arxiv.org/abs/2508.21038) ist schon deshalb interessant, weil es ganz nebenbei Embedding-Based Retrieval anschaulic [bsky, 0 points, 1 comments]
• https://arxiv.org/abs/2508.21038 この論文は、埋め込みベース検索の理論的限界に関するものです。 埋め込みを用いた検索手法の性能限界について考察しています。 詳細な内容はリンク先をご参照ください。 [bsky, 0 points, 0 comments]
• arxiv.org/abs/2508.21038 [bsky, 0 points, 0 comments]
• The Theoretical Limitations of Embedding-Based Retrieval https://arxiv.org/abs/2508.21038 [bsky, 0 points, 0 comments]
• The Theoretical Limitations of Embedding-Based Retrieval https://arxiv.org/abs/2508.21038 (https://news.ycombinator.com/item?id=45068986) [bsky, 0 points, 0 comments]
• ベクトルへの埋め込みを使った検索システムの理論的な限界と、実験と、現実的な例についての論文(DeepMindのインターンシップの成果らしい)。 arxiv.org/abs/2508.21038 [bsky, 0 points, 1 comments]
• https://bsky.app/profile/hackernews.com.web.brid.gy/post/3lxmfpepeplw2 [bsky, 0 points, 0 comments]
• The Theoretical Limitations of Embedding-Based Retrieval [bsky, 0 points, 0 comments]

Related

• NV-Embed: Improved Techniques for Training LLMs as Generalist Embedding Models
• Text Embeddings for Retrieval From a Large Knowledge Base
• Beyond Single Embeddings: Capturing Diverse Targets with Multi-Query Retrieval
• Dense Retrievers Can Fail on Simple Queries: Revealing The Granularity Dilemma of Embeddings
• Experimental Analysis of Large-scale Learnable Vector Storage Compression