Research map / Learning theory and algorithms / Sample complexity
$\mathbb{R}^{2k}$ is Theoretically Large Enough for Embedding-based Top-$k$ Retrieval
Zihao Wang, Hang Yin, Lihui Liu, Hanghang Tong, Yangqiu Song, Ginny Wong, Simon See
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace learned single-vector embedder with random token-sum (vanilla tokenizer) | random Gaussian token vectors · LIMIT (d=4096) | Recall@2: 0.030 -> 0.7060 | Improved |
| replace learned single-vector embedder with random token-sum (vanilla tokenizer) | random Gaussian token vectors · LIMIT-small (d=4096) | Recall@2: 0.543 -> 0.9545 | Improved |
| use handmade phrase tokenizer instead of Qwen tokenizer (ablation) | random token-sum · LIMIT (d=4096) | Recall@2: 0.2675 -> 0.9980 | Improved |
| use Qwen3-0.6B tokenizer instead of vanilla word tokenizer (ablation) | random token-sum · LIMIT (d=4096) | Recall@2: 0.7060 -> 0.2675 | Hurt |
| increase embedding dimension from 32 to 4096 (ablation) | random token-sum, handmade tokenizer · LIMIT | Recall@2: 0.0020 -> 0.9980 | Improved |
| use cyclic polytope construction for top-2 retrieval | cyclic-polytope witness · synthetic top-2 retrieval | witness dimension: dimension 4 for every tested m | Improved |
| use centroid-query gradient descent instead of fitted free-embedding curve | centroid GD witness · synthetic top-2 retrieval | witness dimension | Improved |
| use cyclic polytope to overfit LIMIT in R4 | cyclic polytope · LIMIT and LIMIT-small | exact top-2 retrieval | Improved |
Closest papers by meaning
- On the Theoretical Limitations of Embedding-Based Retrieval (ICLR 2026 · similarity 0.86)
- Embedding Dimension of Contrastive Learning and $k$-Nearest Neighbors (NeurIPS 2024 · similarity 0.85)
- Sparse Dimensionality Reduction Revisited (ICML 2024 · similarity 0.85)
- Beyond Worst-Case Dimensionality Reduction for Sparse Vectors (ICLR 2025 · similarity 0.84)
- NUDGE: Lightweight Non-Parametric Fine-Tuning of Embeddings for Retrieval (ICLR 2025 · similarity 0.84)
- Exploiting Distribution Constraints for Scalable and Efficient Image Retrieval (ICLR 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
