GINGER: Spicing Up Graph-Based Vector Search
Daniel Salwasser, Lars Gottesbüren, Laxman Dhulipala, Jakub Łącki, Guy Blelloch, Rajesh Jayaram, Tobias Rubel, Kshiteej Sheth, Amir Zandieh, Vahab Mirrokni
cs.IR, cs.DC
2026-11-06
谷歌开源 Ginger,一套十二比特嵌套码同时导航和重排,向量内存少 2.6 倍并接近浮点;95% 召回下平均比各集最快对手快 1.8 倍。
高维 embedding 要做高召回的最近邻,系统大多用邻近图。查询沿着边做 beam search,每次扩展离自己最近、还没访问过的点。HNSW、Vamana、NSG 都是如此。它比 IVF 倒排少算很多距离,瓶颈变成查询带宽、索引体积和建图时间。PiPNN 用递归划分换掉建图时的全局搜索,十亿级能从几小时降到几十分钟。吞吐和内存还没一起解决。
一次查询要给几千个散落的点打分,导航码必须短。收束后的重排又要接近 32 比特浮点。两套表示各存一份,内存付两次。低维上图同样贵:96 维、每坐标 12 比特的向量是 144 字节,64 个邻居的扁平邻接表要 260 字节。
Ginger 是 Google 开源的内存 C++ 库,也是 PiPNN 的正式实现。建图可选 PiPNN 或 Vamana。
NTQ 在 TurboQuant 上做嵌套。向量归一化后做随机正交旋转,坐标接近高斯,所有维度共用一个标量码本。旋转不乘稠密矩阵。维度拆成 r 段长度为 2 的幂的块,块内做 Walsh-Hadamard,块间用小正交矩阵混合。768、1536、3072 维的块数 r=3。若把维度补零到下一个 2 的幂,码和打分量大约多 33%。
前 4 比特单独构成 TurboQuant 导航码,质心是高斯的 Lloyd-Max 点,放在寄存器里做整数点积。其余比特只把这些区间切细后再量化,供重排使用,主实验取 10 或 12 比特。高斯可以逐级细化,嵌套几乎不掉精度。共享残差码本召回更差。两级分开存储,每个向量另附一个缩放,用来抵消范数和量化收缩。
重排码本有 512 或 2048 个正质心时,内存查表在 4096 维约占重排时间的 80%。分段三次多项式改在寄存器里算质心,这两档延迟大约减半,召回不变。
高维用 PCA 把导航降到更低维,投影矩阵同样量化到 4 比特。TurboSlice 只读旋转坐标的前 128 或 256 维,被挡下的邻居不再加载,也不额外占内存。草图不当导航距离,否则贪心会走偏。PCA 一般更有效,而且和预过滤叠不上去。
图侧先做递归划分,把连得紧的点编成连续编号,边表改存编号间隙。AdaptiveGap 沿用 StreamVByte 的控制字节和一次 shuffle 解码,位宽可以小于一字节,小间隙不必补齐到 8 比特。
对照七个库、十四个数据集,机器是双路 72 核 Xeon 6985P-C、2.3 TB 内存。低维六集里五个是十亿级,高维八集从 768 到 4096,最大是约 1.01 亿条的 MS-MARCO。召回看 10@10。Ginger 用 4+8 比特 NTQ,并压缩邻接表。SymphonyQG 和 ScaNN 有集合因内存不足缺席,前者在 Wiki-Cohere 上召回最高约 0.5%。
| 比较 | 基线 | 结果 |
| 95% 召回吞吐 | 各集最快对手 | 平均 1.8 倍;高维 2.0 倍,最高 2.7 倍;低维 1.45 倍 |
| 对单一库横比 | 任意一个库 | 至少 2.3 倍;高维上对更紧凑的库到 2.9 倍 |
| 高维索引体积 | 原始 32 比特向量 | 12 比特 NTQ 平均为 43% |
| 低维索引体积 | 最省的图库 SVS | 四个低维集上平均小 1.54 倍 |
| 十亿级建库 | Faiss 平均 69 分钟 | Ginger 平均 35 分钟 |
十三集在 90% 和 95% 召回都是 Ginger 吞吐最高。例外是 BigANN:坐标已是 8 比特整数,各库不做 TurboQuant,SVS 快 4%。QPS-召回曲线下面积相对 ParlayANN、SVS、SymphonyQG、DiskANN 为 2.35 到 2.79 倍,相对 ScaNN 和 Faiss 为 10.3 与 11.7 倍。
仍保存浮点的 ParlayANN、DiskANN、Hnswlib,高维索引大约大 2.7 倍。SymphonyQG 按边存码,大约大 7.4 倍。SVS 在八个高维集上几何平均少 19.8% 内存,95% 召回却慢 2.9 倍,峰值召回全部更低。在这八个集上,8 比特 NTQ 的 Ginger 比 SVS 更小,吞吐仍高 2.6 倍,其中七个峰值召回更高。十亿点 Deep 的 12 比特索引约 288 GB。图 5 的低维集上,Ginger 的图平均 111 字节/点,扁平邻接表是 260 字节。
500 万子集上的暴力打分里,12 比特接近浮点,残差量化、均匀标量量和 bf16 不够。4 比特时 NTQ 在论文点名的三个高维集上好于复现的 LVQ。消融中,4 比特导航相对浮点快 5.7 倍,PCA 再快 1.8 倍,TurboSlice 为 1.26 倍。同一顶点序下 AdaptiveGap 比 StreamVByte 再省 5.4% 图内存,加上划分后图相对未压缩 CSR 平均小 2.1 倍,吞吐相差不超过 1.4%。PiPNN 构建在十一集上最快,平均领先当时最快对手 1.4 倍。很小的高维集上 PCA 耗时,ParlayANN 最多快 5.7 倍。
库已经开源。高维文本和 LLM 向量上收益最大:95% 召回的吞吐大约是该集最快对手的 2 倍,完整索引平均落到原始浮点的 43%,重排不用再留一份浮点。低维、特别是坐标本来就是 8 比特的数据,优势主要是图压缩,BigANN 上还略慢于 SVS。十亿级构建大约半小时,一些对照库要数小时,或者放不进 2.3 TB。这是单机内存索引。用磁盘换容量的 DiskANN 是另一条产品线。
实验只覆盖单向量稠密检索。文末说相似度可以换成 Chamfer 或多向量,甚至黑盒打分器,没有数据。插入和删除也没测。
摘要里的 2.6 倍是 12 比特码相对 32 比特浮点。高维上完整索引平均是原始向量的 43%,低维还要加上压缩后的图。汇总速度时,部分库在若干集合上内存不足或召回失败,这些集合不进它们的几何平均。SVS 与 ScaNN 的构建时间含作者打的补丁:消除反向边的锁竞争,以及在 8 比特向量上做 k-means。查询数字应不受影响。构建名次要连着这些补丁、以及 Ginger 多出来的重排序时间一起看。
维度不超过 200 就关掉 PCA,因为会伤精度。4096 维上投影能占到查询时间的大约一半,和 TurboSlice 也不能叠加。TurboSlice 引用的是同期仍在投稿的论文。吞吐数字来自 AVX-512 的 Granite Rapids,没有 ARM 或桌面 CPU,查询也不组 batch,磁盘索引没有放进同一内存预算。