一句话定义
近似最近邻（ANN，Approximate Nearest Neighbor）问题：不保证返回真正最近的 k 个点，而是以可控的召回损失，换取比精确检索低几个数量级的延迟与内存——一切向量索引的立身之本。
为什么重要
维度灾难决定了精确 kNN 在高维没有次线性算法（通用情况下必须挨个算距离），而亿级数据的暴力检索在业务上不可接受。接受"近似"，才打开了 IVF、HNSW、PQ 这些算法的设计空间。不理解 ANN 的权衡本质，就无法读懂任何索引参数——每个参数都在调"牺牲多少召回，换多少速度和内存"。
前置知识
kp-003（距离度量）；了解 top-k 的含义。
核心概念
- 精确 kNN：全库计算距离取最小 k 个，复杂度 O(N·d) 每查询。
- 召回率 recall@k：ANN 返回的 k 个中，有多少落在真正 top-k 里。
- 三元权衡：召回率 — 延迟 — 内存，索引与参数只能三者取二地倾斜。
- (1+ε) 近似与概率保证：理论 ANN 的两种严格化定义；工程实现多用经验召回率而非理论界。
- ground truth：由暴力检索算出的标准答案集，评估一切 ANN 的前提。
原理与机制
为什么必须近似：kd-tree 等空间划分结构在低维有效，但维度升高后"最近的点"与"任意点"的距离差急剧缩小（距离集中效应），剪枝失效退化为全扫。工程出路是放弃最优性保证，换取结构可剪枝：或先聚类再局部扫描（IVF），或按图导航只走有希望的路径（HNSW），或把向量压缩后用近似距离筛选（PQ）。
近似不是无底洞：主流索引可在 1 毫秒内对百万向量做到 95%+ recall@10；把召回拉到 99.9% 的代价通常是非线性暴涨的延迟或内存。因此正确姿势是按业务容忍度选工作点，而非追求 100%。
公式或模型
recall@k = |ANN 返回的 top-k ∩ 真实 top-k| / k示例：真实 top-10 中 ANN 命中 9 个 → recall@10 = 0.9。
图示
召回率
1.0 ┤ ······ HNSW ef↑
0.95┤ ·····
0.9 ┤ ··· ← 常用工作点区间
0.8 ┤ ···
└────┬────┬────┬────┬────→ 查询延迟(越左越好)
0.5ms 1ms 2ms 4ms
曲线形态由索引结构与参数决定; "曲线"而非"点"才是索引的真实画像实例或案例
100 万条 768 维向量、单次查询：精确暴力约需 7.7 亿次浮点乘加，实测数百毫秒；HNSW（M=16, efSearch=64）约 0.5 毫秒、recall@10 ≈ 0.97。把 efSearch 提到 256，召回升到 0.995，延迟约 1.2 毫秒——这就是三元权衡的具象化。
直观类比
图书馆找"最像的 10 本书"：精确检索 = 翻遍每个书架；ANN = 先按分区索引直奔几个相关书架（IVF），再让熟悉馆内小路的馆员带路（HNSW）。可能漏一两本，但快了百倍，且"漏"的比例可测量、可控制。
常见误区
- "近似 = 不可靠"——召回率是可量化指标，生产级 ANN 在目标召回上往往比"伪精确"（如被截断的模糊查询）更稳定。
- "应该追求 100% 召回"——边际成本指数上升；除小数据集（直接用 Flat）外，100% 召回通常意味着放弃索引。
- "召回率只看平均值"——过滤条件叠加后（kp-014、kp-017）局部召回可能骤降，平均值掩盖局部塌陷。
自测题
- recall@10 = 0.9 是什么意思？
- 为什么高维空间精确 kNN 没有实用的次线性算法？
- 三元权衡中，"内存"一端通常牺牲什么换来？
答：对某查询，ANN 返回的 10 个结果中有 9 个属于暴力检索算出的真实 top-10。
答：距离集中效应使剪枝失效，任何空间划分树都要访问几乎所有点；因此只能放松最优性要求换取可剪枝的结构。
答：压缩向量（SQ/PQ，见 kp-011/012）或缩小图/候选结构（降低 M、ef），代价是召回下降或需要精排补偿。
与其他知识点的关系
kp-006 是精确基线与 ground truth 的来源；kp-007/008 是两大主流"近似方案"；kp-024 把本篇的召回率纳入完整指标体系。
延伸阅读
Aumüller, Bernhardsson, Faithfull, "ANN-Benchmarks"（SISAP 2017）——确立"以召回-延迟曲线而非单点数字评价 ANN 索引"的标准评测框架。