跳到主要内容
Agent Memory ANN 系统

第2章：静态 ANN 技术回顾 —— IVF / HNSW / 量化 / 磁盘图四条主干

把 ANN 索引最经典的四条技术主干讲透：IVF 的粗搜+精搜两阶段、PQ 到 RaBitQ 的量化谱系、HNSW 的分层小世界图、Vamana / DiskANN 的磁盘图扩展。每条主干给出算法直觉、关键参数、Faiss 调用示例，最后用一张矩阵表说清「什么场景选什么」，并把静态 ANN 的四条根本假设拆穿——这是后续动态 ANN / Agent Memory ANN 章节的地基。

ANN IVF HNSW PQ RaBitQ DiskANN Vamana Faiss 向量检索基础

第 1 章把 16 年的演进史拉直了，但有一类读者会卡在更前面的位置：HNSW 到底怎么工作？PQ 是哪种”压缩”？为什么 DiskANN 要重新设计而不是直接把 HNSW 写盘？ 这些问题不搞清楚，后面读 Pancake、d-HNSW、SPFresh 都是悬空的。本章把 Stage 1 这十年沉淀下来的四条主干（IVF、量化、HNSW、磁盘图）按”算法直觉 → 关键参数 → 工程注意点”的格式逐个拆开，每条主干给一段 Faiss 调用代码，让你能立刻跑出来。读完这章你会拿到一份”静态 ANN 工具箱”——并且知道这些工具箱在 agent 时代为什么不够用（这是第 3 章的引子）。

📑 目录

1. 暴力 kNN 为什么必须近似

1.1 一组直接的数字

假设你有 10 亿条 768 维的向量（一个中等规模 RAG 库），用户来一个查询，要找 top-100 最近邻。最朴素的算法（brute force）是：

延迟 = 10^9 × 768 × (一次乘加约 0.5 ns) ≈ 380 秒

而工业界对向量检索的 SLA 是 50 ms 以内——差了七千倍。这就是所有 ANN 算法存在的物理基础。

把这个数字按规模列出来：

库规模 N维度 dbrute force 延迟 (单核)工业要求
10 万1286 ms< 5 ms
100 万12864 ms< 5 ms
1000 万128640 ms< 10 ms
1 亿76838 s< 50 ms
10 亿768380 s< 50 ms

🌟 关键事实：brute force 在百万量级以上就已经撑不住毫秒级 SLA——这不是工程问题，是 O(Nd) 物理墙。

1.2 近似的两个含义

ANN 的 “Approximate” 是两层含义的复合：

  1. 召回率近似：返回的 top-k 里可能有几个不是”真正”的最近邻，但绝大多数是
  2. 距离近似：用量化、降维、或粗排估计距离，不是精确欧氏/内积

工业界的目标是 Recall@10 ≥ 0.95 同时 延迟 < 50 ms。能同时打到这两个数的算法，就是合格的 ANN 索引。

🍎 直觉比喻：暴力 kNN 是用秤称每一颗苹果挑最重的；ANN 是先用眼睛粗看挑出十几颗大的，再用秤精确比一比——绝大多数情况下”最重的那颗”就在这十几颗里。

1.3 衡量 ANN 的四个指标

任何一篇 ANN 论文，benchmark 至少要看这四个数：

指标含义越大越好还是越小越好
Recall@k返回的 top-k 中真正 top-k 的占比越大越好（典型 0.9~0.99）
QPS每秒能处理的查询数越大越好
Latency P9999 分位查询延迟越小越好（典型 < 50 ms）
Index Size索引在内存/磁盘上占多少字节越小越好

⭐ 重要：这四个指标之间是 Pareto 关系——没法同时最优。比如把 ef_search 调大 → recall 升、QPS 降；把 PQ 子向量数 m 调大 → recall 升、index size 升。所有 ANN 论文都在画 Pareto 前沿。

2. ANN 算法分类法

按”用什么数据结构组织数据”分，主流 ANN 索引可以归为五大类，这五类不是互斥的，可以叠加组合（IVF + PQ、IVF + HNSW、HNSW + PQ）：

            ┌──── 树类（Tree-based）：KD-tree、Annoy
            │       └ 优点：构建快；缺点：高维退化
            │
            ├──── 哈希类（Hash-based）：LSH、FALCONN
            │       └ 优点：理论保证；缺点：实际召回不如图
            │
ANN 索引 ───┼──── 聚类倒排（IVF）：IVF-Flat、SPANN、SPFresh
            │       └ 优点：磁盘友好、可扩展；缺点：边界数据召回差
            │
            ├──── 图类（Graph-based）：HNSW、NSG、Vamana
            │       └ 优点：召回/QPS 业界最高；缺点：内存重、不易动态化
            │
            └──── 量化类（Quantization）：PQ、OPQ、ScaNN、RaBitQ
                    └ 优点：内存压缩 32-256x；缺点：单用召回低，需配合 IVF/图

🧠 关键洞察：树类和哈希类在 d > 50 的高维向量下都会显著退化（“curse of dimensionality”），所以现代工业系统主要用”图 / IVF / 量化”的组合。Faiss / Milvus / Pinecone 默认都是这种组合。

实际工程组合最常见的几种：

组合含义典型场景
HNSW-FlatHNSW 图 + 原始向量单机百万级，召回优先
IVF-FlatIVF 聚类 + 原始向量单机千万级，可分布式
IVF-PQIVF 聚类 + 簇内 PQ 压缩10 亿级，内存有限
IVF-HNSWIVF 聚类 + 用 HNSW 找最近簇万亿级（很少用，工程复杂）
DiskANN单层图 + 磁盘 + PQ 压缩残差10 亿级，单机磁盘部署

3. IVF：粗搜 + 精搜两阶段范式

3.1 算法直觉

IVF（Inverted File）是 Hervé Jégou 等人 2010 年提出的，它定义了一个延续至今的范式：先用 k-means 把库分成 nlist 个簇，查询时只搜最近的 nprobe 个簇。

┌─────────── 索引构建 ───────────┐
│                                │
│  1. 对全库 N 个向量做 k-means  │
│     得到 nlist 个聚类中心       │
│                                │
│  2. 每个向量分配到最近的中心   │
│     形成 nlist 个倒排列表       │
│                                │
└────────────────────────────────┘

┌─────────── 查询流程 ───────────┐
│                                │
│  1. 查询 q 与 nlist 个中心比距  │  ← 粗搜（coarse）
│     选出最近的 nprobe 个簇      │
│                                │
│  2. 在这 nprobe 个簇的成员中    │  ← 精搜（fine）
│     做精确 kNN                  │
│                                │
└────────────────────────────────┘

🍎 直觉对应：先找你住在哪个区（粗搜），再在区里找最近的便利店（精搜）——不用扫遍全市。

3.2 关键参数

参数含义典型值调参权衡
nlist簇的总数√N 量级太小：簇大、精搜慢；太大：粗搜慢、簇平均小但容易漏
nprobe查询时搜几个最近簇1-128越大召回越高，但延迟线性增
m（用 PQ 时）PQ 子向量数8-64越大召回越高、内存占用越大

3.3 IVF 的失效场景

🧠 致命弱点 1：边界数据召回差

如果查询 q 离两个簇中心的距离差不多，但真正最近邻在第二个簇，nprobe=1 会漏掉。

🧠 致命弱点 2：簇大小不均衡

k-means 收敛后簇大小常常是 10x 量级差异。大簇成为瓶颈——一个查询如果落到大簇上，精搜延迟会被拖慢。这是 SPFresh / Quake 在动态场景重点解决的问题。

3.4 Faiss 调用片段

import faiss
import numpy as np

# 准备数据
d = 128
N = 1_000_000
xb = np.random.random((N, d)).astype('float32')
xq = np.random.random((10000, d)).astype('float32')

# 构建 IVF-Flat 索引
nlist = 1024
quantizer = faiss.IndexFlatL2(d)
index = faiss.IndexIVFFlat(quantizer, d, nlist)

# IVF 必须先 train（学聚类中心）
index.train(xb)
index.add(xb)

# 查询
index.nprobe = 16
D, I = index.search(xq, 10)   # top-10 近邻

🌟 结论：IVF 是”聚类 + 倒排”的范式，几乎所有大规模分布式向量库（Milvus、Vespa、Vald）都用它做数据分片。

4. 向量量化谱系：PQ → OPQ → ScaNN → RaBitQ

量化（Quantization）的核心目标是 把每个向量从 d × 4 字节（float32）压到 m 字节（典型压缩 32-128 倍）。压缩后内存够小，可以全部放进 DRAM 甚至 L3 cache。

4.1 PQ（Product Quantization, 2010）

核心思路：把 d 维向量切成 m 段子向量，每段独立用 k-means 量化（典型 k=256，每段 1 字节编码）。

原始向量 [128 维 float32]   = 512 字节
  ↓ 切成 8 段，每段 16 维
[16d]·[16d]·[16d]·[16d]·[16d]·[16d]·[16d]·[16d]
  ↓ 每段独立做 k=256 的 k-means
[ 8bit ]·[ 8bit ]·[ 8bit ]·[ 8bit ]·[ 8bit ]·[ 8bit ]·[ 8bit ]·[ 8bit ]
  ↓ 拼起来
压缩后 [8 字节]    ← 64x 压缩

距离估计：查询时把 q 也切 m 段，预计算每段对 256 个码字的距离 → 查表累加。一次距离估计只需 m 次查表 + m 次加法。

🍎 直觉比喻：PQ 像把一篇文章拆成 8 个段落，每段做”段落摘要”（从 256 个候选摘要里选最像的一个）。查询时不读原文，读摘要拼出来。

4.2 OPQ（Optimized PQ, 2013）

核心改进：PQ 默认按维度顺序切子向量，但自然向量空间常常是各向异性的——某些维度方差大、某些小。OPQ 先做一个旋转矩阵 R，让各维度方差均衡，再切 m 段做 PQ。

收益：同样压缩率下 recall 提升 2-5%。代价：训练慢、查询时多一个矩阵乘。

4.3 ScaNN（Score-Aware Quantization, ICML 2020）

核心改进：PQ 优化的是”重建误差”（量化向量和原始向量的 L2 距离），但 ANN 真正在意的是”对最相似的那些向量，距离估计要准”。ScaNN 引入各向异性损失：对接近的向量赋予更高权重训练量化器。

收益：在 GloVe 等数据集上 Recall@10 提升 10%+。

4.4 RaBitQ（SIGMOD 2024）⭐

核心改进：前面的 PQ 系列都没有理论误差界——你不知道用 PQ 估算出的距离误差到底有多大。RaBitQ 给出了：

对任意 d 维单位向量 v，用 D-bit 随机化二值化编码，距离估计的均方误差有显式上界 O(1/D)。

RaBitQ 的工程意义：

  • 首次让”压缩多少 bit 就够用”有了数学答案
  • D-bit 编码可以在不同数据集上无脑迁移（不像 PQ 需要重训码本）
  • GPU 友好：bit-packed 向量 SIMD 加速极强

🌟 结论：RaBitQ 是 2024-2026 年最重要的量化突破。Pancake、d-HNSW、IVF-RaBitQ (GPU) 都在用它。Extended-RaBitQ（SIGMOD 2025）把它推广到任意压缩率。

4.5 量化方法对比表

方法压缩率Recall (vs Flat)训练时间理论误差界代表工作
PQ32-64x-5 ~ -15%中❌Faiss-IVFPQ
OPQ32-64x-3 ~ -10%中❌Faiss-IVFOPQ
ScaNN32-64x-1 ~ -5%中❌Google ScaNN
RaBitQ16-256x-1 ~ -3%极快（无需训练）✅RaBitQ (SIGMOD’24)
Extended-RaBitQ任意-0.5 ~ -2%极快✅SIGMOD’25

⭐ 2026 年选型建议：新项目首选 RaBitQ / Extended-RaBitQ。除非要严格兼容 Faiss-IVFPQ 老索引，否则没有用 PQ 的理由。

5. HNSW：分层小世界图

5.1 算法直觉（看懂这一节，就懂 HNSW 八成）

HNSW（Hierarchical Navigable Small World，Malkov & Yashunin, TPAMI 2018）是 目前工业界最常用的 ANN 算法。Faiss、Milvus、Pinecone、Qdrant、Weaviate 默认都是它。

核心思路用三句话讲清：

  1. 每个数据点是图上的一个节点
  2. 节点之间有边连接（最多 M 条），边表达”它们互为近邻”
  3. 图分层：上层稀疏（少数枢纽节点）、下层密集（全部节点）
Layer 2  ─── A ─── B ─── C ───        ← 稀疏：3 个节点，全国级"省会"
              │     │     │
Layer 1  ─── A-D   B-E   C-F ─── G ───  ← 中等：10 个节点，"市级"
              │ │   │ │   │ │     │
Layer 0  ── 全部 1,000,000 个节点 ──    ← 密集：底层 + 全连接邻居

🍎 直觉对应：找北京某条胡同的便利店，先看全国地图飞到北京（Layer 2），再看市图飞到东城区（Layer 1），最后看街道图找到便利店（Layer 0）。每层都贪心地往离目标最近的邻居走。

def hnsw_search(graph, query, k, ef_search):
    # 1. 从最高层入口节点开始
    current = graph.entry_point
    for layer in range(graph.max_layer, 0, -1):
        # 在这一层贪心游走到局部最优
        while True:
            best_neighbor = min(current.neighbors[layer],
                                key=lambda n: dist(n, query))
            if dist(best_neighbor, query) < dist(current, query):
                current = best_neighbor
            else:
                break  # 局部最优，下降一层

    # 2. 到 Layer 0 后做 beam search（保留 ef 个候选）
    candidates = MinHeap([current])    # 探索队列
    results = MaxHeap([current])       # top-k 结果
    visited = {current}

    while candidates:
        cur = candidates.pop()
        if dist(cur, query) > results.top():
            break    # 候选都比已有结果远，提前终止

        for n in cur.neighbors[0]:
            if n in visited: continue
            visited.add(n)
            if dist(n, query) < results.top() or len(results) < ef_search:
                candidates.push(n)
                results.push(n)
                if len(results) > ef_search:
                    results.pop()

    return results.top_k(k)

🧠 关键洞察：HNSW 的搜索复杂度大约是 O(log N) ——这是它打败 IVF 的根本原因（IVF 是 O(√N) 量级）。

5.3 关键参数

参数含义典型值调参权衡
M每个节点最多多少邻居（Layer 0）16-64越大召回越高、内存越大
ef_construction建图时的 beam 宽度200-400越大图越好、构建越慢
ef_search查询时的 beam 宽度50-500越大召回越高、延迟越高
max_layer最多多少层log_M(N) 量级自动决定，无需手调

⭐ 重要 trick：HNSW 的层级是几何分布随机决定的——每个新插入节点以概率 p^l 出现在第 l 层（p 典型 1/M）。这保证了上层稀疏、下层密集的”小世界”结构。

5.4 HNSW 的工程问题

🧠 致命弱点 1：内存重

每个节点要存 M 条邻居（每条 4 字节 ID）。对 1 亿向量 + M=32：

邻居开销 = 10^8 × 32 × 4 = 12.8 GB
向量本身 = 10^8 × 128 × 4 = 48 GB
总计 = 60 GB

🧠 致命弱点 2：动态插入会让图退化

新插入节点只能局部搜索找邻居，找到的邻居可能不是真正的 top-M。多次插入后边的质量下降——这是后面所有动态 ANN 工作（SPFresh / Quake / Pancake）要解决的核心问题。

🧠 致命弱点 3：删除不友好

删除一个节点会”扯断”它周围的图——它的邻居们的搜索路径都得改。工程上常用标记删除（tombstone）+ 周期性 compaction 应对，但标记删除会带来”剪枝悖论”：表面 recall 上升、底层图结构持续退化（参见后续动态 ANN 章节）。

5.5 Faiss 调用片段

import faiss

d = 128
N = 1_000_000
xb = np.random.random((N, d)).astype('float32')
xq = np.random.random((10000, d)).astype('float32')

# 构建 HNSW
M = 16
index = faiss.IndexHNSWFlat(d, M)
index.hnsw.efConstruction = 200
index.add(xb)

# 查询
index.hnsw.efSearch = 100
D, I = index.search(xq, 10)

🌟 结论：HNSW 是单机毫秒级 ANN 的事实标准。百万级以下基本就用它——除非内存吃紧（用 IVF-PQ）或库太大上磁盘（用 DiskANN）。

6. NSG / Vamana / DiskANN：图索引演进

HNSW 之后，图索引继续演进。两个最重要的后继者是 NSG（2019）和 Vamana/DiskANN（2019）。

6.1 NSG（Navigating Spreading-out Graph, Fu et al. VLDB 2019）

核心改进：HNSW 的分层是随机的，层与层之间没有”导航保证”——理论上可能从 Layer 2 找不到最优 Layer 0 节点。NSG 用一个叫 MRNG (Monotonic Relative Neighborhood Graph) 的图，保证从任意起点出发都能贪心走到最优。

收益：召回相同的情况下，搜索更短路径（约 1.5x 加速）。

代价：构建复杂度比 HNSW 高，工业实现少（nmslib、faiss 没默认集成）。

6.2 Vamana（NeurIPS 2019）

核心改进：Vamana 是 Microsoft DiskANN 论文里提出的图算法。它把 HNSW 的”分层”和 NSG 的”单调”思想合并，但只用单层图。每个节点有 M 条 long-range 边和近邻边，通过 alpha 参数控制长短边的比例（alpha=1.2 是经典值）。

为什么用单层图？为了能写到磁盘上——分层图在磁盘上的随机访问极其不友好。

6.3 DiskANN（NeurIPS 2019）

核心创新：把 Vamana 图写到 SSD 上，只在内存里保留压缩向量（PQ）。搜索流程：

1. 用 PQ 估算的距离做粗排（内存里完成，毫秒级）
2. 对粗排前 L 个候选，从 SSD 拉取它们的精确向量 + 邻居列表
3. 用精确向量重排，得到 top-k

SSD 随机 IOPS 现代盘有 10万+，每次查询 4KB × ~50 次 IO，单查询 5-10 ms。这就是用 SSD 撑 10 亿级 ANN 的秘诀。

🍎 直觉对应：DiskANN 像图书馆——内存里只放”书的标签和索引卡”（PQ），真要看书才去书架取（SSD）。

6.4 DiskANN 演进谱系

系统年份改进
DiskANN / VamanaNeurIPS 2019起源，单层 alpha 图 + PQ 残差
FreshDiskANNNeurIPS 2021加流式插入支持（out-of-place + buffer）
Filtered-DiskANNNeurIPS 2023加属性过滤支持
StarlingSIGMOD 2024块洗牌优化 SSD 局部性，43.9x 吞吐提升
PipeANNOSDI 2025BFS 与 SSD 对齐，1ms 十亿级
LSM-VECarXiv 2025LSM-tree 式磁盘 ANN，内存减 66%
OdinANNFAST 2026Direct insert，billion-scale 稳定流式

6.5 Faiss + DiskANN 调用对比

# DiskANN（用 microsoft/DiskANN 而非 Faiss）
from diskannpy import build_disk_index, StaticDiskIndex

build_disk_index(
    data_path="data.fbin",
    distance_metric="l2",
    index_directory="index/",
    complexity=64,           # 类似 ef_construction
    graph_degree=64,         # 类似 M
    search_memory_maximum=8, # 内存上限 (GB)
    build_memory_maximum=32, # 构建内存 (GB)
    num_threads=16,
    pq_disk_bytes=32         # 每向量 PQ 大小
)

index = StaticDiskIndex(
    index_directory="index/",
    num_threads=16,
    num_nodes_to_cache=10000  # 缓存的热点节点数
)

I, D = index.search(query, k=10, complexity=100, beam_width=2)

🌟 结论：DiskANN 系是 10 亿级以上单机 ANN 的标准路线。但它的工程门槛远高于 HNSW——参数多、需要 SSD、依赖 PQ。

7. 静态 ANN 综合对比矩阵

把上面 4 条主干总结到一张表，按”什么场景该选什么”列出来：

维度IVF-FlatIVF-PQHNSW-FlatHNSW-PQDiskANN
典型规模1M-100M100M-10B1K-10M1M-100M100M-10B
存储位置内存内存内存内存SSD+少量内存
召回 (Recall@10)0.990.85-0.950.990.92-0.970.92-0.97
QPS (单机)千万万万千
内存 / 1M 128d512 MB8-32 MB580 MB40-60 MB5 MB (内存) + 600 MB (SSD)
构建时间 / 1M30 s1 min3 min4 min10 min
支持动态插入部分部分✅✅部分 (FreshDiskANN)
支持高效删除❌❌⚠️（标记）⚠️❌
代表实现Faiss / MilvusFaiss / VespaFaiss / hnswlibFaissMicrosoft DiskANN

选型决策树

你的库规模？
├── < 100 万 ──────────→ HNSW-Flat（首选，召回高、配置简单）
│
├── 100 万 ~ 1 亿 ─────→ 内存够吗？
│                          ├── 够 ─→ HNSW-Flat 或 IVF-Flat
│                          └── 不够 → HNSW-PQ 或 IVF-PQ
│
├── 1 亿 ~ 10 亿 ──────→ 单机吗？
│                          ├── 单机 → DiskANN（SSD） 或 IVF-PQ（DRAM）
│                          └── 分布式 → IVF-PQ 分片 (Milvus)
│
└── > 10 亿 ──────────→ 分布式 IVF-PQ 或 DiskANN 分片
                            （进入 Stage 5 的腹地，参见第 3 章）

⭐ 2026 年趋势：用 RaBitQ 替换 PQ 几乎在所有场景下都是无脑升级。IVF-RaBitQ (GPU) 在召回 0.95 时比 CPU IVF-PQ 快 12.5x。

8. 静态 ANN 的四条根本假设

这一节是本章最重要的部分——所有静态 ANN 工作都建立在四条隐藏假设上，而这四条假设在 Agent 时代全部失效。这是后续动态 ANN / Agent Memory ANN 章节的引子。

假设 1：read-mostly（读远多于写）

静态 ANN 的世界观：库一次性建好，之后绝大多数操作是查询。即使要更新，也是 每天/每周 批量重建。

Agent 时代的反例：

  • Agent 每步对话产生新记忆，需要立刻可检索（毫秒级延迟，不能等批量）
  • 推荐系统每秒数千次 embedding 更新
  • 长上下文 LLM 把对话历史存进向量库做”工作记忆”

🔥 失效后果：HNSW 的”局部搜索找邻居”在动态场景下让图持续退化（剪枝悖论——参见第 3 章和第 5 章）。

假设 2：批量更新（amortized 假设）

静态 ANN 的世界观：插入/删除可以攒一批再做，更新代价摊到一批上是 O(log N)。

Agent 时代的反例：

  • 每条对话都是”一个事件 + 一次插入”，无法批量
  • 删除需要”立即生效”（隐私合规、过期记忆清理）

🔥 失效后果：FreshDiskANN 用 buffer 攒一批的策略在 agent 场景下要么 buffer 太小不省事、要么太大延迟变高。这是 SPFresh / Quake / Pancake 都在攻克的问题。

假设 3：单租户（single workload）

静态 ANN 的世界观：整个索引服务一种工作负载，所有数据点访问频率分布相似。

Agent 时代的反例：

  • 多 Agent 共享一个记忆库，每个 Agent 关心的子集完全不同
  • 用户的”最近对话”和”一年前的对话”访问频率差 1000 倍

🔥 失效后果：HNSW 的层级结构对所有节点”一视同仁”，热点节点和冷节点放一起，远程内存场景下 cache miss 率惊人（参见第 8 章 d-HNSW 实测）。

假设 4：内存可控（datasize ≤ memory）

静态 ANN 的世界观：索引能装进内存，最多用 PQ 压缩一下；上磁盘就用 DiskANN 但仍假设是”少量随机 IO”。

Agent 时代的反例：

  • 终身 agent 的记忆库可能达到千亿向量（数百 TB）
  • 不同 agent 的记忆有不同的 hot/cold 模式，单一缓存策略失效

🔥 失效后果：单机内存装不下 → 必须走分离式内存（CXL / RDMA / 鲲鹏 UB）。这是 d-HNSW / SHINE / CoTra 的研究背景，第 8 章详细展开。

一张图总结

                  静态 ANN（Stage 1）        Agent Memory ANN（Stage 5）
                  ────────────────────────  ─────────────────────────────
读写比             读远多于写                每步交替读写
更新粒度           批量（小时/天）            单条（毫秒）
工作负载           单租户                    多 Agent
索引位置           DRAM 或 SSD                DRAM + CXL + RDMA 内存池
评价指标           Recall + QPS               + 更新吞吐 + 一致性 + 多租户公平
                                              + 内存效率 + 健康监控

🌟 关键判断：静态 ANN 不是”被淘汰”，而是”被退化为子模块”。Pancake 内部仍然有 HNSW 子图；SPFresh 仍然用 IVF。它们的价值在于”快”——但完整的 Agent Memory ANN 系统必须在这些子模块之上加一层动态管理。这就是第 3 章要讲的内容。

✅ 自我检验清单

  • brute force 物理墙：能说出 1 亿条 768 维向量暴力 kNN 大约多久（答案约 38 秒），并解释为什么必须近似
  • ANN 分类：能区分 IVF / HNSW / PQ 三者的”工作原理”差异，能解释为什么 IVF-PQ 是常见组合
  • IVF 关键参数：能说出 nlist 和 nprobe 各自的作用，并解释 IVF 失效的两个典型场景
  • 量化谱系：能按时间序列写出 PQ → OPQ → ScaNN → RaBitQ，并说出每一步的关键改进
  • HNSW 搜索过程：能口述 HNSW 的搜索流程（从入口层开始贪心 → 下降 → Layer 0 做 beam search）
  • HNSW 参数：能说出 M / ef_construction / ef_search 各自的作用和典型取值
  • DiskANN 直觉：能解释为什么 DiskANN 用单层 Vamana 图而不是分层 HNSW，能说出 PQ 在 DiskANN 里扮演什么角色
  • 选型决策：给定一个具体的库规模（100M, 128d, 内存 64GB），能给出合理的索引选型
  • 静态 ANN 四条假设：能复述这四条假设，并各举一个 Agent 时代它失效的具体例子

📚 参考资料

概念入门

  • Faiss 官方 wiki “Guidelines to choose an index” —— Faiss 团队：github wiki（中文社区也有翻译版，但 wiki 最新）
  • Pinecone 学习中心 “What is HNSW?”：pinecone.io/learn/series/faiss/hnsw —— 图文并茂讲 HNSW，入门首选
  • ann-benchmarks.com —— 各算法在标准数据集上的 Recall-QPS Pareto 曲线，做选型必查

关键论文

IVF / PQ 谱系：

  • Product Quantization for Nearest Neighbor Search（Jégou, Douze, Schmid, TPAMI 2011）：INRIA PDF —— IVF + PQ 起源
  • Optimized Product Quantization（Ge, He, Ke, Sun, CVPR 2013）：MSR —— OPQ 旋转矩阵改进
  • Accelerating Large-Scale Inference with Anisotropic Vector Quantization (ScaNN)（Guo et al., ICML 2020）：arXiv 1908.10396
  • RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound（Gao & Long, SIGMOD 2024）：ACM DL —— 首次给出量化的理论误差界
  • Extended-RaBitQ: Practical and Asymptotically Optimal Quantization（SIGMOD 2025）：GitHub

HNSW / 图索引：

  • Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (HNSW)（Malkov & Yashunin, TPAMI 2018）：arXiv 1603.09320 —— 必读经典
  • Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph (NSG)（Fu, Xiang, Wang, Cai, VLDB 2019）：arXiv 1707.00143
  • DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node (Vamana)（Subramanya et al., NeurIPS 2019）：NeurIPS PDF
  • Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment（SIGMOD 2024）：ACM DL

Surveys（必读）：

  • A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search（Wang, Xu, Wang, Cai, VLDB 2021）：arXiv 2101.12631 —— 图索引最全 survey
  • A Survey on Vector Database Management Systems（Pan, Wang, Li, 2024）：arXiv 2310.14021
  • Storage-Based Approximate Nearest Neighbor Search Survey（IISWC 2025）：atlarge-research.com PDF —— 磁盘级 ANN 系统视角

行业讨论

框架文档

本系列其它章节