On the Theoretical Limitations of Embedding-based Retrieval

Theory. The authors formalize retrieval as preserving row-wise order or thresholds in a binary qrel matrix and show these capacities are sandwiched by the matrix’s sign-rank. For fixed dimension ddd, some top-k sets are unrepresentable, so certain retrieval tasks are impossible for any single-vector embedder at that ddd.

Best-case optimization. With “free embeddings” directly optimized on the test qrels, the maximum solvable corpus size for k=2k=2k=2 scales roughly as a cubic in ddd. Extrapolated critical sizes remain far below web scale even for 4096-dim embeddings, indicating a fundamental ceiling not attributable to training data or losses.

LIMIT dataset results. LIMIT maps all 2-document combinations to natural-language queries like “Who likes X?” Despite the simplicity, SOTA single-vector models often score below 20% Recall@100 on the full task, and they still cannot solve a 46-document version at Recall@20. Performance improves with larger ddd but remains poor.

Combinatorial density matters. When the qrel graph is made dense to maximize distinct top-k combinations, scores collapse across models. Sparser patterns (random, cycle, disjoint) are markedly easier, highlighting that the number of realizable top-k sets is the bottleneck.

Alternatives and implications. Cross-encoders can solve the small LIMIT variant perfectly, multi-vector late-interaction models fare better than single-vector, and high-dimensional sparse baselines like BM25 perform strongly. For instruction-following retrieval that composes many concepts, systems should pair or replace dense first-stage retrieval with rerankers, multi-vector, or sparse methods.