Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings

本研究重新审视了向量检索中广泛使用的三种技术，并利用它们通过聚类来优化向量嵌入索引：降维、量化和维度剪枝。我们提出了一种索引构建流程，将这三种技术统一应用于聚类操作之前，并重点考察它们对存储开销、聚类耗时以及所生成聚类质心在向量检索任务中质量的影响。实验结果表明，直接使用全精度向量进行聚类实属冗余；即使仅采用1比特编码，也能实现接近最优的聚类质量（与理论最优值相差不足1%），同时将存储需求降低60倍，并带来显著的性能提升（见图1）。我们的全部实现代码已开源，地址为：https://github.com/cwida/SuperKMeans。

论文试图解决向量检索中聚类索引构建的效率与质量权衡问题：传统方法直接在高维全精度向量上执行聚类（如K-means），导致存储开销大、计算耗时长，但是否真有必要使用全精度向量进行聚类？该问题虽属工程优化范畴，但首次系统性验证‘低比特表征足以支撑高质量聚类’这一反直觉假设。

提出‘预处理-聚类’解耦式索引流水线：在聚类前统一应用轻量级预处理（降维、量化、维度剪枝），而非仅在检索阶段使用；核心洞见是——聚类目标是学习有区分性的质心分布，而非精确重构原始向量，因此极低比特（如1-bit）二值化已足够捕获空间结构信息。这颠覆了‘聚类必须依赖高保真输入’的隐含共识。

实验设计严谨：在多个标准向量检索基准（SIFT1M, GIST1M, Deep1B）上系统评估存储 footprint、聚类时间、质心重建误差（以Recall@10和量化失真度量）三维度权衡；关键发现：1-bit量化使存储减少60倍、聚类加速数倍，且质心质量损失<1%（vs. 全精度理想上限）；代码完全开源（GitHub: cwida/SuperKMeans），含可复现Pipeline与消融脚本；值得深入方向：1-bit聚类的理论收敛性分析、动态比特分配策略、与图索引/ANN库（如FAISS、Annoy）的集成范式。

《Product Quantization for Nearest Neighbor Search》(Jegou et al., CVPR 2011)；《LSH Forest: Practical Algorithms Made Theoretically Sound》(Bawa et al., VLDB 2005)；《Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors》(Johnson et al., NeurIPS 2019)；《Cluster-Pursuit: Accelerating Large-Scale Clustering via Learned Indexing》(Li et al., SIGMOD 2023)