Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensions
高维网格近似最近邻搜索的缩放定律
🧭 高维ANN缩放定律与网格算法
University of California, Berkeley · University of Toronto, St. George · Independent Researcher · University of Waterloo
多探针网格在高维下展现维度不变吞吐，索引成本低，冲击图/树方法的主导地位
📌 工作参考价值（4 点）
- 当推荐系统使用高维嵌入（d≥300）且索引频繁重建（如分钟级更新），可试用多探针网格替代HNSW，利用其近常数维度吞吐和极低索引延迟，避免图索引重建瓶颈。
- 查询时间随N近线性增长，但在千万级数据集上仍可能满足延迟要求；通过调节probe数量可灵活控制精度/速度折中，适合召回延迟不极端的业务。
- 若采用ANN近似自注意力优化大模型推理，网格法的维度不变性可提供更平稳的扩展，值得在推理引擎中作为备选ANN后端。
- 在离线全量索引构建场景（如每日亿级向量重建），网格法的快速索引特性可大幅缩短总耗时，可作为评估向量检索库时的 baseline 方案。