Query encoders often underperform despite easy document retrieval geometry
Learning Query Encoders Can Be Hard Even When Vector Retrieval Is Geometrically Easy
Information RetrievalMachine Learning
Summary
Finding the right documents through vector similarity is easier than training the query encoders that match queries to those documents. The authors find that on several standard tests, the query encoders often fail to reach the best possible retrieval quality that the document vectors could support. They also show, through theory, that training these query encoders can be really hard even in simple cases. This means that the main challenge may not be with the document representations but with making good query encoders.
What this means in practice
- •For information retrieval engineers: Recognize the limits of current query encoders for improving search recall when document embeddings are already well-structured.
- •For machine learning system designers: Account for potential computational hardness in training query encoders to avoid wasted effort on difficult-to-learn tasks for embedding-based retrieval.
Tested on several real-world retrieval benchmarks.
Authors
Anders Wikum, Nina Mishra, Amin Saberi, Tal Wagner
Abstract
Efficient vector retrieval requires both a corpus geometry that supports retrieving the right documents through vector similarity, and a query encoder that can embed queries near their desired documents in the embedding space. Recent work has studied geometric capacity through the lens of the minimum embedding dimension needed to realize all top-$k$ answer sets of $n$ documents. We study a different notion of geometric capacity--the maximum recall achievable for a frozen document index--and explore whether learned query encoders can reach this ceiling. On several real-world retrieval benchmarks, we show that retrieval quality of single-vector query encoders often lies far below what the document indices can support. Motivated by this observation, we give theoretical evidence that learning query encoders can be computationally hard. In particular, we construct a retrieval task that (1) admits a query encoder with perfect recall which is representable by a small one-hidden-layer ReLU network, but (2) any statistical-query learner (a class capturing learners that access training data through aggregate statistics) provably requires exponentially many statistical queries to achieve non-trivial recall advantage over the random baseline $k/n$. Taken together, our results suggest substantial unrealized geometric capacity in retrieval benchmarks and establish query encoder learnability as a possible barrier in embedding-based retrieval.