Approximate Nearest Neighbors (HNSW / IVF): 解释 IVF 与 PQ 的原理。

Core Concept: IVF 先聚类缩小搜索范围（nprobe 控制）；PQ 把向量切段量化省内存；IVF-PQ 组合最省内存。

数学机理：<strong>(1) IVF（Inverted File）</strong>——(a) <strong>构建</strong>——用 <strong>k-means</strong> 把所有向量聚成 <strong>n_list</strong> 个簇（每个簇有一个质心）；每个向量归到最近的簇；<strong>倒排列表</strong>记录每个簇包含的向量 id。(b) <strong>查询</strong>——计算查询向量与所有<strong>质心</strong>的距离，选出最近的 <strong>n_probe</strong> 个簇；只在这些簇内<strong>精确计算</strong>距离（或进一步用 PQ 近似）。(c) <strong>n_probe 的作用</strong>——控制'搜索范围'：n_probe 大 → 召回高但慢；小 → 快但漏。<strong>典型 n_probe=1~64</strong>（n_list 常取 √N）。(d) <strong>优点</strong>——省内存（只需存向量 + 倒排列表）、可扩展；<strong>缺点</strong>——边界效应（真实最近邻可能落在'非最近的簇'中 → 漏召回）。(2) <strong>PQ（Product Quantization）</strong>——(a) <strong>原理</strong>——把 d 维向量<strong>切成 m 段</strong>（每段 d/m 维）；对每段用 <strong>k-means 聚成 k 个质心</strong>（码本，常 k=256 即 8 bit）；每个向量表示为'<strong>m 个码字 id</strong>'（共 m 字节）。(b) <strong>压缩比</strong>——原始 d×4 字节（FP32）→ m 字节；如 d=768、m=96 → 从 3072 字节压到 96 字节（<strong>32 倍</strong>）。(c) <strong>查询</strong>——预计算'查询向量各段与各质心的距离表'（m×k 表）；然后用<strong>查表求和</strong>估算距离（快）。(d) <strong>优点</strong>——<strong>内存极省</strong>（10~100 倍）；<strong>缺点</strong>——<strong>量化误差</strong>（精度损失）。(3) <strong>IVF-PQ（组合）</strong>——先用 IVF 缩小范围（n_probe 个簇），再用 PQ 的距离表快速估算；<strong>优点</strong>——<strong>最省内存</strong>（适合十亿级）；<strong>缺点</strong>——召回损失较大（IVF 的边界效应 + PQ 的量化误差）。<strong>精度补偿</strong>——(a) <strong>重排（rerank）</strong>——用 PQ 粗筛出候选（如 top-1000），再用<strong>完整向量</strong>精确重排（取 top-10）；<strong>效果</strong>——PQ 的量化误差只影响候选集大小（不影响最终精度）；这是<strong>标准做法</strong>。(b) <strong>残差量化（RQ）</strong>——用多级码本逐步逼近（更精确）；(c) <strong>OPQ（优化 PQ）</strong>——先做旋转使各段独立（降低量化误差）；(d) <strong>更大码本/更多段</strong>（m 大则误差小但存储多）。<strong>其他量化</strong>——(a) <strong>标量量化</strong>（FP32→INT8，简单省 4 倍）；(b) <strong>二值量化</strong>（省 32 倍，用汉明距离）；(c) <strong>ScaNN / 各向异性量化</strong>（Google，对'内积'优化）。<strong>实践</strong>——(a) <strong>内存充足</strong> → HNSW（召回高）；(b) <strong>内存受限/超大规模</strong> → IVF-PQ + 重排；(c) <strong>极致省内存</strong> → 二值 + 重排；(d) <strong>调参</strong>：n_list（常 √N）、n_probe（召回-延迟旋钮）、m（压缩比-精度旋钮）。<strong>度量</strong>——(a) 召回率；(b) 内存占用；(c) QPS/延迟；(d) 重排后的最终精度。

深度剖析与工程权衡：① <strong>'IVF 缩小范围、PQ 压缩向量'是两者的分工</strong>——前者省'搜索范围'、后者省'存储'；面试中能清晰区分是深度理解的标志。② <strong>'PQ 的量化误差用重排补偿'是标准技巧</strong>——它使'省内存'与'高精度'可兼得（代价是候选集要大些）。③ <strong>'n_probe 是召回-延迟旋钮'</strong>——与 HNSW 的 efSearch 对应。④ <strong>'IVF 的边界效应'</strong>——真实最近邻可能落在非最近的簇；故 n_probe 不能太小。⑤ <strong>'OPQ/RQ 的改进'</strong>——它们降低量化误差（提升精度）；故生产系统常组合使用。⑥ <strong>面试要点</strong>——被问'IVF 与 PQ'，应给出'<strong>IVF（聚类 + n_probe 控制范围）+ PQ（切段量化 + 查表算距离）+ 组合省内存 + 重排补偿精度</strong>'；能给出'768 维压到 96 字节（32 倍）'的量化直觉是深度理解的标志。