$mathbbR^2k$ is Theoretically Large Enough for Embedding-based Top-$k$ Retrieval

arXiv:2601.20844v2 Announce Type: replace-cross
Abstract: This paper studies the minimal dimension required to embed subset memberships ($m$ elements and $mchoose k$ subsets of at most $k$ elements) into vector spaces, denoted as Minimal Embeddable Dimension (MED). The tight bounds of MED are derived theoretically and supported empirically for various notions of “distances” or “similarities,” including the $ell_2$ metric, inner product, and cosine similarity. In addition, we conduct numerical simulation in a more achievable setting, where the $mchoose k$ subset embeddings are chosen as the centroid of the embeddings of the contained elements. Our simulation easily realizes a logarithmic dependency between the MED and the number of elements to embed. These findings imply that embedding-based retrieval limitations stem primarily from learnability challenges, not geometric constraints, guiding future algorithm design.