用 Rust 从零实现 HNSW:向量检索为什么能用图来做近似最近邻
100 万条 768 维向量,找出和查询向量最相似的那条——暴力搜索要做 7.68 亿次乘法。
这是个真实的量级。RAG 应用、以图搜图、推荐系统都卡在这个问题上。工业界的答案是近似最近邻(ANN):用一点点准确率换取几十倍的性能。
HNSW(Hierarchical Navigable Small World)是目前最主流的 ANN 算法之一。它的思想其实和前面写过的跳表一脉相承——用多层结构把"长距离跳跃"和"精细搜索"分开。
先定义问题
暴力搜索是这样的:
fn brute_force(query: &[f32], vectors: &[Vec<f32>], k: usize) -> Vec<usize> {
let mut scores: Vec<(usize, f32)> = vectors
.iter()
.enumerate()
.map(|(i, v)| (i, cosine(query, v)))
.collect();
scores.sort_unstable_by(|a, b| b.1.partial_cmp(&a.1).unwrap());
scores.into_iter().take(k).map(|(i, _)| i).collect()
}复杂度 O(n × d)。n 是向量数,d 是维度。
ANN 的目标:不保证找到真正最近的那个,但以很高的概率找到"足够近"的那几个。 典型指标叫 recall@k——比如 recall@10 = 0.95 意思是"真实 Top10 里平均有 9.5 个出现在结果里"。
单调递减的距离度量:内积转余弦
先把距离定义清楚。最常用的是余弦相似度:
/// 余弦相似度,越大越相似
fn cosine(a: &[f32], b: &[f32]) -> f32 {
let mut dot = 0.0f32;
let mut na = 0.0f32;
let mut nb = 0.0f32;
for i in 0..a.len() {
dot += a[i] * b[i];
na += a[i] * a[i];
nb += b[i] * b[i];
}
if na == 0.0 || nb == 0.0 {
return 0.0;
}
dot / (na.sqrt() * nb.sqrt())
}工程实践里会先把所有向量归一化,这样余弦相似度就退化成内积,省掉两次开方:
fn normalize(v: &mut [f32]) {
let norm = v.iter().map(|x| x * x).sum::<f32>().sqrt();
if norm > 0.0 {
for x in v.iter_mut() {
*x /= norm;
}
}
}归一化之后 cosine 就是简单的点积——距离计算是 ANN 里最热的内层循环,这里的每一步优化都会被放大几百万倍。
核心思想:一张"小世界图"
HNSW 的基础结构是一个图:
- 节点:每条向量是一个节点
- 边:两个节点"邻近"就连一条边,每个节点最多 M 条边
查询时的走法叫贪心搜索(greedy search):从某个入口点开始,看它的邻居里有没有比当前点更近的;有就走过去,没有就停。
fn greedy_search(
graph: &Graph,
vectors: &[Vec<f32>],
query: &[f32],
entry: usize,
) -> usize {
let mut current = entry;
let mut current_dist = distance(query, &vectors[current]);
loop {
let mut improved = false;
for &neighbor in graph.neighbors(current) {
let d = distance(query, &vectors[neighbor]);
if d < current_dist {
current_dist = d;
current = neighbor;
improved = true;
}
}
if !improved {
return current; // 局部最优,停
}
}
}这就是小世界网络(small world)的直觉:每个节点都有一些"远距离捷径"和大量"近距离邻居",于是任意两点之间的跳数很短。
但贪心搜索有个致命问题:它会卡在局部最优。 如果入口点附近就没有通往目标区域的边,就永远走不到。
HNSW 的解法是分层。
分层:和跳表一模一样的思想
HNSW 建了多层图:
L2: A ---------------> H (稀疏:只有长边,用于快速接近)
L1: A ---> C ----> F -> H ---> K
L0: A -> B -> C -> D -> E -> F -> G -> H -> I -> J -> K (稠密:全部节点)- L0 包含所有节点,每个节点有最多
2M条边 - 上层是下层的稀疏采样,每个节点最多 M 条边
- 层数按指数衰减——和跳表的抛硬币完全一样
查询流程:
1. 从最高层的入口点开始,贪心搜索,找到该层里离 query 最近的点
2. 用这个点作为下一层的入口,重复
3. 到了 L0,用 ef 个候选做更宽的搜索pub fn search(&self, query: &[f32], k: usize, ef: usize) -> Vec<usize> {
let mut entry = self.entry_point;
let mut entry_dist = self.distance(query, entry);
// 1. 上层:每层只找一个最优点,快速"降落"
for level in (1..=self.max_level).rev() {
let (best, dist) = self.greedy_in_level(query, entry, level);
entry = best;
entry_dist = dist;
}
// 2. L0:用 ef 的宽度做精确一些的搜索
self.search_layer(query, entry, ef, 0).into_iter().take(k).collect()
}上层很稀疏,所以每层只需要很少的跳数就能接近目标;到了 L0 才做细致搜索。 这和跳表"顶层大步跳,底层逐格走"是同一个策略。
HNSW = 跳表的分层思想 + 近邻图的贪心搜索。 理解了这个组合,剩下的都是工程细节。
层的分配:又见抛硬币
const M: usize = 16;
const MAX_LEVEL: usize = 16;
impl Hnsw {
fn random_level(&self) -> usize {
let mut level = 0;
let mut r = self.rand();
// 每升一层概率乘 1/M
while level < MAX_LEVEL && (r % M as u64) == 0 {
level += 1;
r /= M as u64;
}
level
}
}分布大致是:L0 有全部节点,L1 有 1/16,L2 有 1/256……
期望层数是 1/(1 - 1/M),所以即使节点很多,高层也只有寥寥几个节点。空间开销是线性的,查询路径长度是对数的。
建图:插入时找邻居
这是 HNSW 最精妙的部分。插入一个新节点时,要:
- 找到它该连的邻居
- 连上(双向)
- 如果某个邻居的度数超了,裁掉最远的那个
impl Hnsw {
pub fn insert(&mut self, vector: Vec<f32>) -> usize {
let id = self.vectors.len();
self.vectors.push(vector);
let level = self.random_level();
self.node_levels.push(level);
let query = &self.vectors[id];
// 从最高层开始下降,找到每层的入口
let mut entry = self.entry_point;
let mut entry_dist = self.distance(query, entry);
for l in (level + 1..=self.max_level).rev() {
let (best, dist) = self.greedy_in_level(query, entry, l);
entry = best;
entry_dist = dist;
}
// 从上往下逐层建边
for l in (0..=level.min(self.max_level)).rev() {
let candidates = self.search_layer(query, entry, M, l);
let neighbors = self.select_neighbors(query, candidates, M);
// 双向连接
for &n in &neighbors {
self.add_edge(id, n, l);
}
// 邻居可能超度数,裁剪
for &n in &neighbors {
let nbrs = self.neighbors_at(n, l);
if nbrs.len() > self.max_degree(l) {
let trimmed = self.select_neighbors(&self.vectors[n], nbrs, self.max_degree(l));
self.set_neighbors(n, l, trimmed);
}
}
if let Some(&first) = neighbors.first() {
entry = first;
}
}
if level > self.max_level {
self.max_level = level;
self.entry_point = id;
}
id
}
}这几步里藏着 HNSW 最关键的启发式规则。
邻居选择:不只是"最近的 M 个"
朴素的选法是"取最近的 M 个"。但这样会让图变得"局部聚集"——所有邻居都在同一个方向,没有长边,图就退化成一群孤立的小簇,贪心搜索跳不出去。
HNSW 论文提出了一个更聪明的启发式(heuristic neighbor selection):
按距离升序遍历候选,凡是"和已选邻居中任何一个的距离 都小于 到 query 的距离"的候选,就跳过。意思是:如果一个候选能被已选邻居"覆盖",就不选它。
fn select_neighbors(&self, query: &[f32], candidates: Vec<usize>, m: usize) -> Vec<usize> {
let mut sorted = candidates;
sorted.sort_by(|&a, &b| {
self.distance(query, a).partial_cmp(&self.distance(query, b)).unwrap()
});
let mut selected: Vec<usize> = Vec::with_capacity(m);
for &cand in &sorted {
if selected.len() >= m {
break;
}
// 判断这个候选能不能被已选邻居"覆盖"
let cand_dist = self.distance(query, cand);
let covered = selected.iter().any(|&s| {
self.distance(&self.vectors[cand], &self.vectors[s]) < cand_dist
});
if !covered {
selected.push(cand);
}
}
// 如果启发式选不够 m 个,用剩下的补齐(保证连通性)
if selected.len() < m {
for &cand in &sorted {
if selected.len() >= m {
break;
}
if !selected.contains(&cand) {
selected.push(cand);
}
}
}
selected
}这个启发式是 HNSW 性能的核心。 它保证了图里既有"近距离的密集连接",也有"跨越不同簇的长边"。没有它,recall 会明显下降。
在 ANN 图里,边不是越多越好,而是"方向要分散"。 一堆同方向的近邻,不如几个不同方向的远邻有用。
L0 的搜索:用优先队列做更宽的探索
上层用贪心(每次只保留一个最优点),L0 要"宽"一些——同时追踪 ef 个候选。
这是标准的最佳优先搜索(best-first search):
use std::collections::BinaryHeap;
fn search_layer(&self, query: &[f32], entry: usize, ef: usize, level: usize) -> Vec<usize> {
// candidates: 小顶堆(按距离),下一个要展开的
// results: 大顶堆(按距离),当前最好的 ef 个
let mut visited = std::collections::HashSet::from([entry]);
let mut candidates: BinaryHeap<Reverse<Scored>> = BinaryHeap::new();
let mut results: BinaryHeap<Scored> = BinaryHeap::new();
let d = self.distance(query, entry);
candidates.push(Reverse(Scored { dist: d, id: entry }));
results.push(Scored { dist: d, id: entry });
while let Some(Reverse(current)) = candidates.pop() {
// 剪枝:当前点已经比 results 里最差的还远,停止
if let Some(worst) = results.peek() {
if current.dist > worst.dist && results.len() >= ef {
break;
}
}
for &neighbor in self.neighbors_at(current.id, level) {
if !visited.insert(neighbor) {
continue;
}
let d = self.distance(query, neighbor);
if results.len() < ef || d < results.peek().unwrap().dist {
candidates.push(Reverse(Scored { dist: d, id: neighbor }));
results.push(Scored { dist: d, id: neighbor });
if results.len() > ef {
results.pop(); // 丢掉最远的
}
}
}
}
results.into_iter().map(|s| s.id).collect()
}ef 是这个算法里最重要的调参旋钮:
| ef | 效果 |
|---|---|
| ef = k | 最快,recall 最低 |
| ef = 10 × k | 常见默认,recall 0.95+ |
| ef = 100 × k | 很准,但慢 |
注意 ef 是查询参数,不是建图参数。 这意味着同一个索引可以在"低延迟"和"高召回"两种模式之间切换——这是 HNSW 很实用的一个特性。
删除:HNSW 的软肋
HNSW 不支持真正的删除。理由是:删掉一个节点会破坏图的连通性,重新连边代价很高。
工业实现(比如 hnswlib)的做法是标记删除:
pub struct Hnsw {
deleted: std::collections::HashSet<usize>,
}
fn search_with_deletes(&self, query: &[f32], k: usize, ef: usize) -> Vec<usize> {
// 搜索时多取一些,过滤掉被删除的
let mut results = self.search(query, k * 2 + self.deleted.len().min(100), ef);
results.retain(|id| !self.deleted.contains(id));
results.truncate(k);
results
}注意要"多取一些再过滤"——如果直接取 k 个再过滤,删掉几个就凑不齐 k 个了。
空间也不会回收。彻底清理需要重建索引(rebuild)。所以 HNSW 适合"写少读多、更新以插入为主"的场景。
内存上的取舍
HNSW 的内存开销主要来自两部分:
- 原始向量:n × d × 4 字节。这是大头。
- 图结构:每个节点 L0 有 2M 条边,上层有 M 条。用
u32存 id,大约 n × 2M × 4 字节。
向量本身占内存的 90% 以上。 所以生产上会做向量量化(PQ/SQ):把 f32 压成 int8 甚至 4 bit,内存直接降一个数量级,recall 掉几个点。
/// 标量量化:把 f32 线性映射到 u8
fn quantize(v: &[f32]) -> Vec<u8> {
v.iter().map(|&x| ((x.clamp(-1.0, 1.0) + 1.0) * 127.5) as u8).collect()
}用量化后的向量做"粗筛",再用原始向量对候选做"精排"——这是向量检索里经典的"两阶段"结构。
和别的 ANN 算法比
| 算法 | 原理 | 优点 | 缺点 |
|---|---|---|---|
| HNSW | 分层图 + 贪心 | 召回和延迟都好 | 内存大,删除难 |
| IVF | 聚类 + 倒排 | 内存可控 | 召回依赖聚类质量 |
| PQ | 乘积量化 | 内存极小 | 精度损失大 |
| IVF+PQ | 组合 | 大规模首选 | 调参复杂 |
| DiskANN | 图 + SSD | 超大规模 | 延迟高于内存版 |
小规模(< 1000 万)且要低延迟,HNSW 基本是最优选。 上了亿级,内存成本会逼你转向 IVF+PQ 或 DiskANN。
结论
HNSW 把两件事拼在一起,就得到了一个效果惊人的结构:
分层(跳表思想)负责"快速接近目标",近邻图负责"精细定位";建图时的启发式邻居选择保证边方向分散;查询时用 ef 调节召回与延迟;删除只能标记,量化用来压内存。
写一遍之后,再看 hnswlib 的那些参数(M、efConstruction、efSearch),你会清楚每个旋钮在动什么——M 决定图的连通度,efConstruction 决定建图质量,efSearch 决定查询时的探索宽度。