实现 HNSW 踩过的六个坑：从 0% Recall 到 98%+ 的 Debug 实录

在我的向量数据库项目 vex 中实现 HNSW 算法（AI 辅助生成初版代码，后续自己做 debug 和优化），第一次跑 Recall 测试——全部 0%。不是 50%、不是 30%，是 0。HNSW 返回的结果和 BruteForce 完全不重叠。本文记录了从 0% recall 一路 debug 到 98%+ 的完整过程，以及对照 HNSW 论文逐一修复六个关键 Bug 的技术细节。

一、HNSW 论文核心思想速览

开始 debug 之前，先把 HNSW 论文（Malkov & Yashunin, 2018）的核心结构搞清楚，后面每个 Bug 都能对应到论文的哪一条。

1.1 分层跳表 + 近邻图

HNSW 的核心是一个多层图。每一层都是一个近邻图，上层稀疏、下层稠密。搜索时从最高层入口点开始贪心下降，每层找到当前最近邻后跳到下一层，直到 Layer 0 精确搜索。

Layer 2:    [A] ──────────────── [B]              (稀疏，跳远步)
             │                    │
Layer 1:    [A] ── [C] ── [D] ── [B] ── [E]      (中等密度)
             │      │      │      │      │
Layer 0:    [A]-[C]-[F]-[D]-[G]-[B]-[E]-[H]-...  (全量节点)

直觉：就像地图导航——先在省级高速跳到目标城市附近，再切到市级公路，最后走街道到达目的地。

1.2 论文中的五个关键参数

1.3 论文中的两个核心堆

论文 Algorithm 2（搜索）明确规定了两个堆的语义：

搜索过程中维护两个集合：
  C = min-heap (candidates)   -> 优先扩展最近的候选
  W = max-heap (working set)  -> 维护当前最好的 ef 个结果，淘汰最差的

循环：
  1. 从 C 弹出最近候选 c（min-heap pop）
  2. 如果 dist(c) > W 中最差的距离 -> 停止
  3. 遍历 c 的所有邻居 e
  4. 如果 dist(e) < W 中最差的距离 -> 加入 C 和 W
  5. 如果 |W| > ef -> 从 W 弹出最差的（max-heap pop）

这一段极其重要，后面会看到，搞反这两个堆的语义就是 0% recall 的直接根因。

1.4 Algorithm 4：SelectNeighbors 的多样性启发式

论文最被忽视的贡献之一。选择邻居时不是简单取最近的 M 个，而是要考虑空间多样性：

Algorithm 4: SELECT-NEIGHBORS-HEURISTIC(q, C, M)
  R ← ∅ (结果集)
  W ← C (工作集，按距离排好序)

  while |W| > 0 AND |R| < M:
    e ← 从 W 中取出最近的
    if dist(q, e) < dist(e, r) for all r ∈ R:  // e 不被任何已选邻居"支配"
      R ← R ∪ {e}
    else:
      discard e  (被已选邻居覆盖了)

  // keepPrunedConnections: 用被丢弃的候选填充剩余名额

直觉：假设你在选择几个通讯基站的位置。最优策略不是全部选在信号最强的市中心，而是要分散到不同方向，保证每个区域都能被覆盖。

二、第一个惊雷：Recall 全线 0%

2.1 测试框架

我先写了一个 Recall@K 测试，思路很简单：同一批向量分别插入 HNSW 和 BruteForce，对相同查询取 top-k，计算两者结果集的重叠率：

$$Recall@k = \frac{|HNSW_{top-k} \cap BruteForce_{top-k}|}{k}$$

func calculateRecallAtK(hnswResults, groundTruth []vector.SearchResult, k int) float64 {
    truthSet := make(map[string]bool, len(groundTruth))
    for _, r := range groundTruth {
        truthSet[r.Key] = true
    }
    matches := 0
    for _, r := range hnswResults {
        if truthSet[r.Key] {
            matches++
        }
    }
    return float64(matches) / float64(k)
}

测试配置覆盖了 6 个组合：

2.2 全军覆没

=== RUN   TestHNSWRecallAccuracy/1K-128D
    recall@1   = 0.0000 (0.00%)
    recall@5   = 0.0000 (0.00%)
    recall@10  = 0.0000 (0.00%)
--- FAIL

=== RUN   TestHNSWRecallAccuracy/10K-256D
    recall@1   = 0.0000 (0.00%)
    recall@5   = 0.0000 (0.00%)
    recall@10  = 0.0000 (0.00%)
--- FAIL

所有 6 个配置、所有 k 值，recall 全部是 0.0000。

插入一个小型 debug 测试来观察两边到底返回了什么：

Query: test-query-0
  HNSW top-5:  [vec-933(-0.22), vec-071(-0.21), vec-445(-0.19), ...]
  BF   top-5:  [vec-236(+0.30), vec-560(+0.29), vec-112(+0.28), ...]
  Overlap: 0/5 (0%)

两个发现：

1. 结果集完全不重叠——不是排序问题，是找到了完全不同的向量
2. HNSW 返回的相似度是负数（-0.22），而 BF 返回的是正数（+0.30）

HNSW 在返回最不相似的向量。

三、Bug #1：距离与相似度的致命混淆

3.1 根因

HNSW 的堆比较逻辑假设 distance 越小越好（像欧氏距离），但实际使用的是 DotProduct 相似度（越大越好）。

// 原始实现——直接返回 DotProduct 相似度
func distanceBetween(vec1, vec2 []float32) (float32, error) {
    return vector.DotProduct(vec1, vec2) // 返回值范围 [-1, 1]，越大越相似
}

// 堆比较逻辑——假设 distance 越小越好
func (h candidateHeap) Less(i, j int) bool {
    return h[i].distance > h[j].distance  // max-heap：大的在根
}

堆说"我要让最大的浮到顶上方便丢掉"，但 distanceBetween 返回的是相似度，最大的恰恰是最好的。结果：每次扩展候选时都从最差的开始，搜索方向完全反了。

3.2 修复

把相似度转为距离——取负：

func distanceBetween(vec1, vec2 []float32) (float32, error) {
    sim, err := vector.DotProduct(vec1, vec2)
    if err != nil {
        return 0, err
    }
    return -sim, nil  // 相似度越高 -> 距离越小（负数越小）
}

// Search 返回时再取反，还原成相似度
results = append(results, vector.SearchResult{
    Key:        node.Key,
    Similarity: -distance,  // 距离 -> 相似度
})

修复效果（recall@1）：

从 0% 到终于有分了——但维度越高、数据越多，recall 越惨。离理想值还差得远。

四、Bug #2：searchLayerWithEf 候选选择条件反转

4.1 根因

修复距离方向后，搜索函数里还有一个条件写反了：

// 错误：选择距离更大（更差）的候选
if distance > w[0].distance || len(w) < ef {
    // 加入候选集
}

// 正确：选择距离更小（更好）的候选  
if distance < w[0].distance || len(w) < ef {
    // 加入候选集
}

w[0] 是 max-heap 的堆顶（当前结果集中最差的）。新候选的距离应该比最差的更小（更好）才值得加入。写成 > 等于在说"只要比最差的还差就加进来"——完全反了。

4.2 修复效果

1K 数据有改善，10K 仍然惨不忍睹。说明还有更深层的问题。

五、Bug #3-#6：对照论文的系统性审查

到这一步，我停下来做了一次完整的代码审查，对照论文逐条比对。一次性发现了剩下四个问题。

5.1 Bug #3：candidates 堆语义错误（最致命）

论文要求：candidates 是 min-heap（优先扩展最近候选），W 是 max-heap（维护结果集，淘汰最差的）。

实际实现：两个都是 max-heap。这意味着搜索时每次从 candidates 弹出的是最远的候选去扩展邻居——搜索方向完全错误。

// 论文要求                              
// candidates: min-heap -> pop 最近的    
// W:          max-heap -> pop 最远的    
                                        
// 我的实现（错误）                       
// candidates: max-heap -> pop 最远的  (错)
// W:          max-heap -> pop 最远的  (对)

这是 0% recall 到 5% 的根本原因。即使修复了距离方向，堆的语义仍然在把搜索引向错误的方向。

修复：candidates 改用 min-heap，Less 函数取反：

// min-heap for candidates
func (h candidateHeap) Less(i, j int) bool {
    return h[i].distance < h[j].distance  // 最小的在根 -> 优先扩展
}

5.2 Bug #4：SelectNeighbors 缺乏多样性启发式

原始实现：

func (h *HNSWIndex) getNeighbors(candidates []*HNSWNode, m int) []*HNSWNode {
    if len(candidates) <= m {
        return candidates
    }
    return candidates[:m]  // 简单截断 — 致命错误
}

这是论文 Algorithm 4 明确反对的做法。只取最近的 M 个，导致所有邻居聚集在同一个方向，图的连通性极差。

对照论文实现 Algorithm 4：

func (h *HNSWIndex) selectNeighborsHeuristic(
    query []float32, candidates []*HNSWNode, m int,
) []*HNSWNode {
    // 限制工作集大小 -> O(3M × M × dim)
    workSet := candidates
    if len(workSet) > m*3 {
        workSet = workSet[:m*3]
    }

    selected := make([]*HNSWNode, 0, m)
    discarded := make([]*HNSWNode, 0, len(workSet))

    for _, e := range workSet {
        if len(selected) >= m {
            break
        }
        distQE, _ := distanceBetween(query, e.Vector)

        // 检查是否被已选邻居"支配"
        dominated := false
        for _, r := range selected {
            distER, _ := distanceBetween(e.Vector, r.Vector)
            if distER < distQE {
                dominated = true  // r 比 q 更接近 e，e 被 r 覆盖了
                break
            }
        }

        if !dominated {
            selected = append(selected, e)
        } else {
            discarded = append(discarded, e)
        }
    }

    // keepPrunedConnections：用被丢弃的候选填充空位
    for _, e := range discarded {
        if len(selected) >= m {
            break
        }
        selected = append(selected, e)
    }
    return selected
}

关键判断：distER < distQE 意味着对于候选 e，已选邻居 r 比查询点 q 更近。此时 e 被 r “覆盖"了——从 e 出发不如从 r 出发，没有额外的导航价值。

5.3 Bug #5：Layer 0 未使用 M₀ = 2M

论文 §4 明确指出 Layer 0 的连接数应该是其他层的两倍，因为 Layer 0 包含所有节点，需要更高的连通度来保证搜索质量。

// 修复前
neighbors := h.selectNeighborsHeuristic(vec, candidates, h.M)

// 修复后
mEffective := h.M
if layer == 0 {
    mEffective = h.M * 2  // M₀ = 2M，论文 §4
}
neighbors := h.selectNeighborsHeuristic(vec, candidates, mEffective)

5.4 Bug #6：pruneNeighbors 使用 O(M²) 冒泡排序

// 修复前：冒泡排序
for i := 0; i < len(neighbors); i++ {
    for j := i + 1; j < len(neighbors); j++ {
        // swap...
    }
}

// 修复后：O(M log M) 标准排序
sort.Slice(neighbors, func(i, j int) bool {
    return neighbors[i].Distance < neighbors[j].Distance
})

单看一次 pruneNeighbors 差别不大，但它在每次 Insert 时都会对每个邻居的邻居列表调用。10K 个节点 × 每个节点 M=32 个邻居 × 每个 O(M²)，积累起来就是显著的性能差距。

5.5 其他修复

全局 RNG 竞态：assignLevel() 使用 rand.Float64()，在并发插入时有竞态条件。改为每个索引实例持有独立的 rand.Rand。

Delete 悬垂指针：删除节点时只从 nodes map 中移除，没有清理其他节点邻居列表中的引用。搜索时可能遍历到已删除节点。修复：删除时遍历该节点所有层的邻居，移除反向引用，并加上 deleted 标记做搜索过滤。

六、六个 Bug 修复后的效果

=== HNSW Recall@K After All Fixes ===

1K-128D:   recall@1  = 100.00%   recall@10 = 100.00%   recall@100 = 100.00%
1K-256D:   recall@1  = 100.00%   recall@10 = 100.00%   recall@100 = 100.00%
1K-512D:   recall@1  = 100.00%   recall@10 = 100.00%   recall@100 = 100.00%
10K-128D:  recall@1  = 100.00%   recall@10 = 100.00%   recall@100 = 100.00%
10K-256D:  recall@1  = 99.99%    recall@10 = 99.98%    recall@100 = 99.96% 
10K-512D:  recall@1  = 98.39%    recall@10 = 98.80%    recall@100 = 98.21% 

从 全线 0% 到 1K-10K 128D/256D 接近 100%，10K-512D 约 98%。高维大规模数据的最后 2% 受限于维度诅咒和 ef 参数权衡，属于正常范围。

六个 Bug 的修复效果叠加一览（以 1K-128D recall@1 为观测指标）：

七、高维性能问题：自适应 ef

修完所有 Bug 后，1K-10K 的 128D/256D 都能在合理时间内完成。但 10K-512D 跑了 512 秒还没完。

7.1 问题分析

ef=600 在 512 维下的构建成本：

每次 Insert:
  searchLayerWithEf: 600 个候选 × 512 维距离计算
  selectNeighborsHeuristic: 3M × M × 512 维
  
10K 次 Insert:
  10,000 × (600 + 96) × 512 = ~35 亿次浮点运算

7.2 解法：自适应 ef

高维空间中向量分布更均匀，较小的 ef 已足够覆盖最近邻区域。受此启发，让 ef 按维度自适应缩放：

$$ef_{adaptive} = \frac{ef_{base}}{\sqrt{dim / dim_{ref}}}$$

func (h *HNSWIndex) adaptiveEf(baseEf, dim int) int {
    const refDim = 128
    if dim <= refDim {
        return baseEf
    }
    ef := int(float64(baseEf) / math.Sqrt(float64(dim)/refDim))
    if ef < h.M*2 {
        ef = h.M * 2  // 下限保护
    }
    return ef
}

效果：

构建时间减半，Recall 仅微降，在高维场景下是合理的精度-性能权衡。

八、与工业实现的差距

修完这些之后，从原理上已经对齐了论文。但和 Faiss、hnswlib 这些工业级实现相比，仍然有差距。下表列出当前状态（含本次修复后已实现的部分）：

当前最大的瓶颈在内存布局和量化——Go 的 map + 指针结构对 CPU cache 不友好，高维向量没有压缩导致内存占用大。这两个是后续优化的重点方向。

九、Debug 方法论总结

回顾这次 debug 过程，有几个方法论值得记录：

1. 先写测试框架再写算法

如果不是一开始就有 Recall@K 测试，可能永远不知道搜索结果是错的。HNSW 的 Search 函数不会报错——它总是"成功"返回结果，只是返回的是错误的向量。

2. 纯 0% 比 50% 更容易 debug

0% recall 意味着有方向性的系统错误，而不是随机的精度损失。这让排查更有针对性——一定是某个基本假设搞反了。

3. 对照论文逐条比对

每篇算法论文的伪代码都有严格的语义约定（min-heap vs max-heap、距离 vs 相似度）。实现时差一个符号就是天壤之别。

4. 不要用降低阈值来"通过"测试

我犯过一个错误：当 recall 仅有 15% 时，试图把阈值从 85% 降到 1% 来让测试通过。这是在掩盖问题而不是解决问题。正确的做法是保持理想阈值不变，把实际值作为 Bug 的量化指标。

5. 一次修一个变量

六个 Bug 不是一次性发现的。每修一个，跑一次测试，观察 recall 的变化趋势。这样才能评估每个修复的实际贡献。

项目地址：github.com/uzqw/vex — 一个用 Go 实现的向量数据库，支持 HNSW 索引、BruteForce 索引、持久化快照。

参考论文：Malkov, Y.A. & Yashunin, D.A. (2018). “Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs.” IEEE TPAMI.