通过量化与重排序优化HNSW，显著提升向量搜索速度与内存效率。
AQR-HNSW: Accelerating Approximate Nearest Neighbor Search via Density-aware Quantization and Multi-stage Re-ranking
- 按数据密度自适应量化，压缩4倍且保持距离关系
- 多阶段重排序减少35%无效计算，查询速度提升2.5-3.3倍
- 适合大规模向量数据库，尤其适用于推荐与检索系统
近似最近邻（ANN）搜索已成为现代AI基础设施的核心，广泛应用于从Google到OpenAI等企业的推荐系统、搜索引擎和大语言模型中。层次可导航小世界（HNSW）图作为主流的ANN算法，因其召回率与延迟之间的优异平衡而被广泛部署于生产环境。然而，随着向量数据库规模扩展至数十亿嵌入向量，HNSW面临严峻挑战：内存消耗剧增，距离计算开销主导查询延迟，且在异构数据分布下表现不佳。本文提出自适应量化与重排序HNSW（AQR-HNSW），融合三种策略以提升HNSW可扩展性。AQR-HNSW引入（1）密度感知的自适应量化，实现4倍压缩并保留距离关系；（2）多阶段重排序，减少35%的无效计算；（3）针对量化优化的SIMD实现，在不同架构上达到每周期16-64次操作。在标准基准测试中，AQR-HNSW相比现有最优HNSW实现，查询吞吐量提升2.5-3.3倍，召回率超过98%，索引图内存减少75%，索引构建速度提升5倍。
原文摘要 · Abstract (English)
Approximate Nearest Neighbor (ANN) search has become fundamental to modern AI infrastructure, powering recommendation systems, search engines, and large language models across industry leaders from Google to OpenAI. Hierarchical Navigable Small World (HNSW) graphs have emerged as the dominant ANN algorithm, widely adopted in production systems due to their superior recall versus latency balance. However, as vector databases scale to billions of embeddings, HNSW faces critical bottlenecks: memory consumption expands, distance computation overhead dominates query latency, and it suffers suboptimal performance on heterogeneous data distributions. This paper presents Adaptive Quantization and Rerank HNSW (AQR-HNSW), a novel framework that synergistically integrates three strategies to enhance HNSW scalability. AQR-HNSW introduces (1) density-aware adaptive quantization, achieving 4x compression while preserving distance relationships; (2) multi-state re-ranking that reduces unnecessary computations by 35%; and (3) quantization-optimized SIMD implementations delivering 16-64 operations per cycle across architectures. Evaluation on standard benchmarks demonstrates 2.5-3.3x higher queries per second (QPS) than state-of-the-art HNSW implementations while maintaining over 98% recall, with 75% memory reduction for the index graph and 5x faster index construction.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。