← All AI/ML open problems

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.

OpenEditorially scopedFramework needs definitionCompiled 2026-11-19

Seed catalog · Showing the bundled record.

Problem statement

Let documents be subsets S⊆[d]S\subseteq[d] of size at most ss and queries be conjunctions Q⊆[d]Q\subseteq[d] of size kk; a document is relevant exactly when Q⊆SQ\subseteq S. Compare single-vector scores ⟨e(Q),v(S)⟩\langle e(Q),v(S)\rangle with multi-vector maximum-inner-product scores, using pp-bit coordinates and margin γ\gamma. Determine dimension, storage, training-label and search costs for recall at least 1−ε1-\varepsilon 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

  1. 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.

  2. 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.