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.
arXiv preprint arXiv:2601.20844 , year =
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
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.
years
2026 5verdicts
UNVERDICTED 5representative citing papers
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.
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 query matrices.
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 inner-product baselines.
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 datasets while releasing a k=3 joint-ranking benchmark.
citing papers explorer
-
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 query matrices.
-
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 inner-product baselines.
-
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 datasets while releasing a k=3 joint-ranking benchmark.