HNSW 是怎么做近似最近邻的？相比暴力检索牺牲了什么？
谁在问：有算法背景的面试官、基础架构团队二面；简历写了向量库调优必被追
口语化问法
- 向量检索底层是怎么做到毫秒级的？总不能挨个算距离吧。
- HNSW 讲一下原理。
- 你们索引参数怎么配的？召回率不够的时候调什么？
考察意图
这题筛的是「知道向量库怎么用」和「知道它为什么快」的差别。三个递进的观察点：① 你有没有意识到 Approximate（近似） 这个词本身就是一个权衡声明；② 能不能讲清多层图的机制而不是背名词；③ 知不知道哪个参数是运行时可调的——这个细节骗不了人，只有真调过的人才会脱口而出 ef_search。
参考答案
60 分答案（及格线）
HNSW 全称分层可导航小世界图。核心思路是建一个多层图结构：上层节点稀疏、边跨度大，用来做长距离跳跃；下层节点稠密，用来精细定位。检索时从顶层入口点出发，每层贪心地走向离目标向量更近的邻居，走不动了就下沉一层，直到底层输出 Top-K。复杂度从暴力检索的 O(N) 降到大约 O(log N)。
牺牲的是精确性——它是近似最近邻，不保证 100% 找到真正的最近邻，可能会漏。换来的是几个数量级的速度提升。另外它的图结构常驻内存，内存开销较大。
90 分答案（有生产经验的回答）
在原理之上补三块：
一个好类比：像查地图找店。顶层只有城市（北京→上海一步到位），中层是区（跳到黄浦区），底层是具体街道（小范围精找）。每层内部是「小世界」网络——任意两点跳几步就能到，所以贪心走很快收敛。
三个参数及其可调性：
| 参数 | 作用 | 调大的后果 | 何时可改 |
|---|---|---|---|
M |
每节点邻居数 | 召回↑、内存↑、构建慢 | 建索引时定，改需重建 |
ef_construction |
建索引时候选队列长度 | 索引质量↑、建得更慢 | 建索引时定，改需重建 |
ef_search |
查询时候选队列长度 | 召回↑、查询变慢 | 运行时可调，无需重建 |
所以「召回率不够怎么办」的第一反应应该是 先调 ef_search 看看——零成本、立刻见效。这比重建索引或换模型便宜得多。
三个必须知道的代价：① 内存常驻，千万级向量时内存可能先于 CPU 成为瓶颈；② 召回非 100%，ef_search 太小会漏；③ 删除是软删除（图结构不好真删，一般打标记跳过），删除比例高了会让图劣化、召回下降，需要定期 compact 或重建。
再补一句横向定位：HNSW 不是唯一选择——IVF（先聚类，只搜几个簇，内存友好但召回略低）、DiskANN（索引放 SSD，适合内存装不下的超大规模）、量化（标量/乘积/二值量化，用精度换内存，可压到几分之一）。选型取决于内存预算和规模。
追问链
为什么分层能加速？只用一层稠密图不行吗？
期望单层贪心易陷局部最优，从随机入口走到目标要很多步；分层让上层「粗定位、大跨步」把起点直接送到目标附近，下层只做局部精搜 —— 本质是用层次结构把搜索路径变短信号说得出「避免局部最优 + 缩短路径」→ 真理解；只说「分层就是快」→ 背诵召回率不达标，你会先调哪个参数？为什么？
期望先调ef_search—— 唯一的运行时参数，不用重建索引，代价只是查询变慢；调到延迟预算上限仍不够，才增大M/ef_construction重建索引 → 再回头查是不是 embedding、分块的问题信号本题最强的实操探针：答不出ef_search可在线调 → 基本没调过参HNSW 的内存大概怎么估？100 万条 1536 维向量要多少？
期望1536 × 4 字节 ≈ 6KB/条→ 100 万条约 6GB → 再加图结构开销（与M相关，是向量本身的一个可观比例），所以实际预留要明显高于 6GB。优化手段：降维（见 Q2-06）、量化信号当场能粗算 → 做过容量规划；完全没概念 → 多半没上过规模文档删除了，索引里怎么处理？删多了会怎样？
期望多数实现是软删除（打标记、检索时跳过），空间不立即释放；删除比例高 → 图连通性劣化、召回下降、查询变慢 → 定期compact或重建。工程上用版本号/时间戳元数据过滤旧版本再异步清理，避免更新期出现检索空窗信号以为向量库删除和数据库DELETE一样即时干净 → 没运维过数据从 100 万涨到 1 亿，你这套还能用吗？
期望单机 HNSW 内存先扛不住。按序：① 量化压缩（乘积量化可压到几分之一）→ ② 换 DiskANN 类磁盘索引 → ③ 上 Milvus 这类分布式做分片 → ④ 业务侧按租户/时间分区，缩小单次检索范围。每条都要同时说出代价：量化掉精度、分布式增运维、分区限制跨域检索信号只说「换 Milvus」、不谈量化和分区 → 方案单一
ef_search 可以在线调」就把「读过论文」和「调过库」切开了 —— 第 2 层是这题的闸门；第 3、4 层再验容量规划与软删除运维。评分要点
- 说清多层图结构与「上层跳跃、下层精搜」的机制
- 明确指出「近似」是核心权衡，召回非 100%
- 能给出复杂度量级（O(log N) vs O(N)）
- 说得出三个参数及各自影响
- 知道
ef_search是运行时可调的唯一旋钮 - 知道内存开销大这一代价
- 加分：知道软删除及其对召回的长期影响
- 加分：知道 IVF / DiskANN / 量化等替代方案及适用
常见错误
ef_search 和 ef_construction 搞混。