Information retrieval · Embeddings & representations · Statistical learning theory / Open question
The Geometry of Search
A retriever can fail because its representation cannot express the desired answer set, because training cannot find the right query, or because the index cannot search it efficiently.
Seed catalog · Showing the bundled record.
Problem statement
Let documents be subsets of size at most and queries be conjunctions of size ; a document is relevant exactly when . Compare single-vector scores with multi-vector maximum-inner-product scores, using -bit coordinates and margin . Determine dimension, storage, training-label and search costs for recall at least under uniform queries and documents, including the cost of learning the encoders from relevance labels.
Assumptions and scope
- Fix the relevance family, query distribution and top-k loss, together with document/query encoder classes and the training objective.
- State whether the document index is frozen, a required score margin and finite-precision constraints; dimension-only exact-real constructions can hide fragile encodings.
- Charge index storage, training and query-time scoring separately, including approximate-neighbor search error. Representing a ranking is not the same as efficiently learning or searching it.
What would settle it?
Matching capacity/learnability bounds or a provable multi-vector advantage for a nontrivial relevance family under declared resource constraints, with the three failure sources separated.
Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.
Status and evidence
Embedding-dimension limitations are established, and Wikum et al. give SQ-hard query-learning examples even when a small perfect encoder exists. The target is a positive-and-negative structured resource frontier, not a claim that dense-retrieval limitations are unknown. This is an editorial, source-motivated research target. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.
Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.
Sources and further reading
- Weller et al. — On the Theoretical Limitations of Embedding-Based Retrieval ↗partial theory · source checked 2026-11-19
Primary search abstract checked: dimension limits the realizable top-k set family in single-vector retrieval. Training larger encoders does not remove every geometric limitation; exact real-valued constructions and finite-margin retrieval must be distinguished.
- Wikum et al. — Learning Query Encoders Can Be Hard Even When Vector Retrieval Is Geometrically Easy ↗partial theory · source checked 2026-11-19
Primary search abstract checked: a small representable query encoder with perfect recall can coexist with exponential SQ learnability barriers. Geometric capacity and learning difficulty are separate.