返回文章列表

用 Rust 从零实现 HNSW:向量检索为什么能用图来做近似最近邻

590 字·5 分钟阅读
Rust从零造轮子向量检索

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 最精妙的部分。插入一个新节点时,要:

  1. 找到它该连的邻居
  2. 连上(双向)
  3. 如果某个邻居的度数超了,裁掉最远的那个
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 的内存开销主要来自两部分:

  1. 原始向量:n × d × 4 字节。这是大头。
  2. 图结构:每个节点 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 决定查询时的探索宽度。