REVIEW 5 cited by
mathbb{R}^(2k) is Theoretically Large Enough for Embedding-based Top-k Retrieval
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
mathbb{R}^(2k) is Theoretically Large Enough for Embedding-based Top-k Retrieval
read the original abstract
This paper studies the Minimal Embeddable Dimension (MED): the least dimension in which there exists a configuration of $m$ object vectors so that every subset of size at most $k$ is exactly retrieved by score comparison. Our result shows MED is $\Theta(k)$, independent of $m$, for inner product, Euclidean distance, and cosine similarity. We then consider Robust MED (RMED), where all vectors are unit normed and an $\epsilon$ gap of scores is required. We derive the $m$-dependent feasibility ceiling $\epsilon_\star(m,k)=m/\sqrt{k(m-1)(m-k)}$, which approaches $1/\sqrt{k}$ when $m\gg k$, and a Gaussian centroid construction gives a robust witness upper bound in the feasible margin regime. Numerical simulation on synthetic top-$2$ retrieval with cyclic polytope and centroid query optimization confirmed our theoretical claims. Experiments on LIMIT and LIMIT-small datasets also show that simple embedding-based retrieval baselines can overfit and outperform the reported single-vector LLM embedding baseline. Both theoretical and empirical findings rule out the lack of exact geometric capacity as the obstruction.
Forward citations
Cited by 5 Pith papers
-
Compact Geometric Representations of Hierarchies
Proves constant-dimension 3 reachability embeddings for directed trees, O(t log n) for treewidth-t graphs, with lower bounds of Omega(n) for general DAGs and Omega(t/log(n/t)) for treewidth t, plus real-dataset results.
-
What Limits Does Quantization Place on Dense Top-$k$ Retrieval? A Theoretical Study
Quantization forces Bd = Ω(k ln N) for perfect top-k retrieval realizability, plus a B* = O(ln ln N) threshold below which no d works under uniform scalar quantization.
-
Is Dimensionality a Barrier for Retrieval Models?
Dimension d = O(m^{-2} log n) nearly achieves the optimal margin m^rd(+∞, A) for retrieval embeddings, with matching lower bounds showing d = O(k log(n/k)) suffices and is necessary for m = Θ(k^{-1/2}) on k-sparse que...
-
Non-negative Elastic Net Decoding for Information Retrieval
NNN decoding selects documents via non-negative elastic net reconstruction of the query embedding, with a theorem showing it strictly dominates dense retrieval on correlated corpora and experiments showing gains over ...
-
Neural Scalable Symbolic Search Framework for Complex Logical Queries with Multiple Free Variables
NS3 approximates joint ranking for EFO_k queries on KGs by merging free variables into hypernodes, pruning domains with dynamic budget B, and reducing to EFO_{k-1} queries, improving joint performance on three dataset...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.