VineGraph · Graph-based Vector Search on Hybrid Memory

01 · Why

Why we built this为什么做这件事

Retrieval = nearest neighbors检索 = 找最近邻

Similar vectors sit close together. A proximity graph + greedy hops reaches the target in dozens of steps^[1][3].相似向量彼此靠近。近邻图 + 贪心跳转，几十步就能到达目标^[1][3]。

The graph outgrows DRAM图装不进内存

At 100M vectors the graph alone exceeds 50 GB^[2][4] — it has to move to disk.1 亿向量的图光结构就超过 50 GB^[2][4]——只能搬到磁盘上。

Disk systems truncate the graph现有方案削足适履

To fit 4 KB pages, DiskANN-style systems cap every node at a fixed degree^[2][5] — accuracy is lost at build time.为塞进 4 KB 页，DiskANN 一类系统把每个节点的度数一刀切^[2][5]——精度在建图时就丢了。

Our position: the graph should adapt to the memory hierarchy — not be dictated by the storage format.我们的主张：让图去适配存储层级，而不是被存储格式支配。

02 · Prior Systems

How the incumbents search现有系统怎么搜

Same task in both panels: greedily reach the point nearest ★. Watch what each hop costs. 两个面板做同一件事：贪心走到离 ★ 最近的点。看每一跳的代价。

HNSW

^[1]in-memory · multi-layer纯内存 · 多层

Search descends a hierarchy of sparser layers. Fast — but the whole hierarchy lives in memory.搜索沿逐层稀疏的层级下潜。快，但整个层级都得常驻内存。

Memory footprint balloons; billion-scale doesn't fit内存占用大，十亿级装不下
More layers, longer paths; exact answers still hit the base layer层数越多路径越长，精确结果仍要回底层

DiskANN

^[2]DRAM + SSD内存 + SSD

A flat graph on SSD, one node per 4 KB page — every hop is one random read (the flashes on the right).单层图放 SSD，每节点一个 4 KB 页——每跳一步就随机读一次（右侧闪烁）。

Fixed degree drops ~75% of hub edges固定度数丢掉枢纽节点约 75% 的边
Build re-prunes each node ~4.7×, under locks建图每节点反复剪枝约 4.7 次，还要加锁
Long paths × random I/O = high latency路径长 × 随机 I/O = 高延迟

03 · Our Approach

Grow the index from a sparse skeleton从稀疏骨架长出完整索引

We build a deliberately sparse pre-navigation graph (PNG) first, then expand it into the full index — theory guarantees no neighbors are lost^[10]. Press play ▶ 先建一张刻意稀疏的预导航图 PNG，再把它迭代扩展成完整索引——理论保证近邻不丢^[10]。按 ▶ 播放。

One build, four graphs — sparse ones in DRAM, dense ones on SSD一次构建、四张图——稀疏的进内存，稠密的上 SSD

Average degree on SIFT1M. The whole build is lock-free with zero pruning, and shards cleanly across machines. SIFT1M 上的平均度数。整个构建过程无锁、零剪枝，且可直接按节点分片跑分布式。

04 · Two-layer Search

Cheap hops in DRAM, few reads on SSDDRAM 里多跳，SSD 上少读

A query traverses the in-memory PNG first, then enters the on-disk FCG with high-quality entry points. 查询先在内存的 PNG 上逼近目标，再带着高质量入口点进入盘上的 FCG。

phase阶段 – memory hops内存跳数 0 SSD I/O 0 candidates候选列表 –

A DRAM hop costs nanoseconds; an SSD random read costs ~100 µs. Good entry points let the disk stage run a ~60% shorter candidate list — 1.77× faster at equal recall (SIFT1M). DRAM 一跳纳秒级，SSD 随机读约 100 µs。好的入口点让磁盘阶段的候选列表缩短约 60%——同召回率下整体快 1.77 倍（SIFT1M）。

05 · Results

The results结果

All comparisons against DiskANN on the same machine, both in strict disk mode. 全部对比与 DiskANN 同机进行，双方均为严格磁盘模式。

4.78×

speedup @99% recall · 100M vectors99% recall 提速 · 1 亿向量

3 ms

per query @99% recall · SIFT1M单查询 @99% recall · SIFT1M

8.07×

throughput · 22,779 vs 2,822 QPS吞吐 · 22,779 vs 2,822 QPS

9.1×

faster build · GIST1M建图提速 · GIST1M

Recall vs. latency — lower-left is better召回率 × 延迟——越靠左下越好

VineGraph · PNG+FCG VineGraph · NG+FG DiskANN

Throughput @99% recall@100吞吐 @99% recall@100

Random entry points; recall still holds above 99%.随机入口点下，召回率仍保持 99% 以上。

Build time (log scale)建图时间（对数刻度）

Bars show pipeline stages. The slower 100M build is a one-off cost that buys a 4× query speedup.条带为各阶段耗时。亿级构建更慢，是一次性成本，换每条查询 4× 提速。

Accuracy-first精度优先

PNG + FCG

Reaches 99.9% recall — the highest of any configuration.召回率可达 99.9%，所有组合中最高。

Throughput-first吞吐优先

NG + FG

Pruned graphs, lowest latency at equal recall — for high-QPS serving.剪枝后的组合，同召回率延迟最低，适合高 QPS 服务。

Memory-constrained内存受限

PNG / NG

The navigation graph alone: 0.65 ms entries, up to 90% recall@100.仅用导航图：0.65 ms 出入口点，recall@100 可到 90%。

06 · References

References参考文献

Malkov, Y. & Yashunin, D. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (HNSW). IEEE TPAMI, 2018.
Subramanya, S. J. et al. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. NeurIPS, 2019.
Fu, C. et al. Fast Approximate Nearest Neighbor Search with the Navigating Spreading-out Graph (NSG). VLDB, 2019.
Chen, Q. et al. SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search. NeurIPS, 2021.
Wang, M. et al. Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search. SIGMOD, 2024.
Jégou, H. et al. Product Quantization for Nearest Neighbor Search (IVFPQ). IEEE TPAMI, 2011.
Johnson, J. et al. Billion-scale Similarity Search with GPUs (Faiss). IEEE Trans. on Big Data, 2021.
Ren, J. et al. HM-ANN: Efficient Billion-Point Nearest Neighbor Search on Heterogeneous Memory. NeurIPS, 2020.
Lewis, P. et al. Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks. NeurIPS, 2020.
Aurenhammer, F. Voronoi Diagrams — A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys, 1991.
Edge, D. et al. From Local to Global: A GraphRAG Approach to Query-Focused Summarization. arXiv, 2024.