怎么考「HNSW 是怎么做近似最近邻的？相比暴力检索牺牲了什么？」
谁在问：有算法背景的面试官、基础架构团队二面；简历写了向量库调优必被追
开场怎么问
向量检索底层是怎么做到毫秒级的？总不能挨个算距离吧。
换个问法
- HNSW 讲一下原理。
- 你们索引参数怎么配的？召回率不够的时候调什么？
五层追问链
左边照着问，右边对着听。最后一层是压力面，不必每个候选人都问到。
为什么分层能加速？只用一层稠密图不行吗？
- 期望
- 单层图上贪心搜索容易陷入局部最优、且从随机入口走到目标要很多步；分层让上层做「粗定位、大跨步」，把搜索起点直接送到目标附近，下层只需局部精搜。本质是用层次结构把搜索路径变短。
- 信号
- 能说出「避免局部最优 + 缩短路径」的，是真理解；只说「分层就是快」的是背诵。
召回率不达标，你会先调哪个参数？为什么？
- 期望
- 先调
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 和 ef_construction 搞混。评分卡
- 说清多层图结构与「上层跳跃、下层精搜」的机制
- 明确指出「近似」是核心权衡，召回非 100%
- 能给出复杂度量级（O(log N) vs O(N)）
- 说得出三个参数及各自影响
- 知道
ef_search是运行时可调的唯一旋钮 - 知道内存开销大这一代价
- 加分：知道软删除及其对召回的长期影响
- 加分：知道 IVF / DiskANN / 量化等替代方案及适用
参考答案与考察意图面试中途别看这一段
考察意图
这题筛的是「知道向量库怎么用」和「知道它为什么快」的差别。三个递进的观察点：① 你有没有意识到 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，适合内存装不下的超大规模）、量化（标量/乘积/二值量化，用精度换内存，可压到几分之一）。选型取决于内存预算和规模。