On the Theoretical Limitations of Embedding-Based Retrieval
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 restrict to k=2, and directly optimize on the
test set with free parameterized embeddings. We then create a realistic dataset
called LIMIT that stress tests 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
methods that can resolve this fundamental limitation.
68b111a5b19c540001484933
Orion Weller
claimed_verified
2025-09-03T19:26:03.223Z
6362d9712691058b19de1ba4
https://cdn-avatars.huggingface.co/v1/production/uploads/6362d9712691058b19de1ba4/c9QrA2oE6lcs_46ShaTY1.jpeg
Orion Weller
user
orionweller
68b111a5b19c540001484934
Michael Boratko
68b111a5b19c540001484935
Iftekhar Naim
68b111a5b19c540001484936
Jinhyuk Lee
On the Theoretical Limitations of Embedding-Based Retrieval
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 restrict to k=2, and directly optimize on the
test set with free parameterized embeddings. We then create a realistic dataset
called LIMIT that stress tests 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
methods that can resolve this fundamental limitation.
Vector embeddings face theoretical limitations in handling even simple queries, as demonstrated by a new dataset that shows state-of-the-art models fail due to the single vector paradigm.
vector embeddings retrieval tasks reasoning instruction-following coding learning theory top-k subsets document retrieval LIMIT dataset embedding models