LSH,PQ,IVF-PQ

哈喽大家好！

咱们之前的文章里，聊了 K-Means（聚类）、IVF（倒排） 和 HNSW（图索引）。
大家还记得那个"不可能三角"吗？速度、精度、内存，三者很难兼得。

  • HNSW 速度快、精度高，但是太吃内存了！
  • Flat 精度最高，但是太慢了！

那有没有一种办法，既能省内存，又能算得快呢？
这就是今天要讲的主角：量化压缩（Quantization） 和 哈希（Hashing） 大法！

📌 还是那个专利案例！

继续用我们的老朋友：

场景：1000 万条专利，每条是 768 维向量

查询："一种基于深度学习的图像去噪方法"

内存问题：1000 万 × 768 维 × 4 字节 = 约 29 GB！

这么大的内存，普通服务器根本扛不住啊！今天就来看看怎么"瘦身"。

我们将深入拆解三个核心概念：

  1. LSH (局部敏感哈希)：怎么用哈希撞库来找邻居？
  2. PQ (乘积量化)：怎么把庞大的向量“压缩”成几个字节？
  3. IVF-PQ：工业界最爱用的“黄金搭档”是怎么炼成的？

话不多说，硬核干货走起！🚀

一、 LSH：专门“搞碰撞”的哈希

提到哈希（Hash），稍微懂点计算机的朋友第一反应通常是 MD5 或 SHA-256。
传统的哈希算法，目标是**“避免碰撞”**：只要内容差一点点（比如 abc 和 abd），哈希值必须天差地别。【hash可以理解为一个函数 比如我输入a --> hash(a)—>123（举例的hash值） 相同输入一定会有相同的输出 但是不同的输入不一定有不同的输出因为有时候可能hash处理后结果仍然是一样的 不理解也没有关系啦~现在LSH我都没有见到有人用…】

但是！LSH (Locality Sensitive Hashing，局部敏感哈希) 是个奇葩。
它的目标刚好相反：它希望“制造碰撞”！

1. 核心原理：相似的进同一个桶

LSH 的设计理念是：如果两个向量在原空间里离得很近，那么经过哈希计算后，它们有很大的概率会得到相同的哈希值（也就是掉进同一个桶里）。

2. 怎么实现？（随机投影 Random Projection）

最经典的方法叫“随机投影”。
想象一下，我们在高维空间里随便切几刀（画几个超平面）：

  • 如果在平面的左边，记为 0。
  • 如果在平面的右边，记为 1。

切了 3 刀，每个向量就会得到一个 3 位的二进制码（比如 011）。
离得很近的两个点，大概率会一直站在平面的同一侧，所以它们的二进制码是一样的！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
graph LR
    Input[输入向量 A & B] -->|随机切刀 1| Bit1{在左还是右?}
    Input -->|随机切刀 2| Bit2{在左还是右?}
    Input -->|随机切刀 3| Bit3{在左还是右?}
    
    Bit1 -- A右/B右 --> Code1[1]
    Bit2 -- A左/B左 --> Code2[0]
    Bit3 -- A右/B右 --> Code3[1]
    
    Code1 & Code2 & Code3 --> HashValue[哈希桶: 101]
    
    subgraph 结果
    Bucket[桶 101: 存放向量 A, B, C...]
    end
    
    HashValue --> Bucket
    
    style Bucket fill:#bfb,stroke:#333

3. LSH 的优缺点

  • 优点：极快！ 计算几个哈希值非常简单，适合超大规模数据的初步去重和粗筛。
  • 缺点：精度一般。运气不好的话，本来不相似的两个点可能刚好被切到了一起（误报），或者相似的点刚好被一刀切开了（漏报）。

🔬 专利案例演示：LSH 的"切刀"过程

让我们看看 LSH 是怎么处理我们的专利数据的：

Step 1：随机切 10 刀（10 个超平面）

1
2
3
4
5
6
7
8
🔪 对 768 维空间切 10 刀

每条专利根据在每刀的哪一侧，得到一个 10 位二进制码：

"卷积神经网络降噪"  → 在切刀 1 的右边、切刀 2 的左边... → 哈希码：1011010110
"深度学习图像增强"  → 哈希码：1011010110  ← 和上面一样！进同一个桶！
"自编码器去噪"      → 哈希码：1011010111  ← 最后一位不同，去了隔壁桶！
"机械臂控制系统"    → 哈希码：0100101001  ← 完全不同，去了很远的桶

Step 2：查询来了

1
2
3
4
5
查询："一种基于深度学习的图像去噪方法"
      ↓
计算哈希码：1011010110
      ↓
去桶 1011010110 里找

Step 3：搜索结果

1
2
3
4
5
6
7
8
9
10
11
📊 LSH 搜索结果

桶 1011010110 里有 3200 条专利
在这 3200 条里找最近的...

✅ 第 1 名：基于卷积神经网络的图像降噪系统（距离 0.12）
✅ 第 2 名：深度学习图像增强方法（距离 0.15）
❌ 第 3 名：某个图像滤波专利（距离 0.38）

召回率：67%
漏掉了："自编码器去噪"（它的哈希码最后一位不同，被切到隔壁桶了）

为什么会漏？
“自编码器去噪"刚好在第 10 刀的边界上，被切到了另一边。这就是 LSH 的"边界问题”。

怎么补救？
可以多建几组哈希表（Multi-probe LSH），但这样内存又上去了……所以现在高精度场景更多用 PQ。

所以，现在在大模型 RAG 这种对精度要求高的场景下，单纯用 LSH 的比较少了，更多的是用下面的 PQ。

二、 PQ (Product Quantization)：向量界的“压缩神器”

现在的 Embedding 向量动不动就是 1024 维、float32 类型。
算一笔账：1 亿条数据 = 1 亿 * 1024 * 4 字节 ≈ 400 GB！
这光存都要存死人，更别说放进内存里算了。

PQ (乘积量化) 就是为了解决这个问题。它的目标是：把向量从“庞然大物”压缩成“迷你代码”。

1. 分身术：切分向量

假设我们有一个 128 维的向量。
PQ 的第一步，是把它切断。比如切成 8 段，每段就是 16 维。我们把这些小段叫做子向量 (Sub-vectors)。

2. 聚类：制作密码本 (Codebook)

对于每一段（比如第 1 段），我们把所有数据的第 1 段拿出来，做一个 K-Means 聚类。
假设聚成 256 类。那么，每一个聚类中心（Centroid）就有一个 ID（0 到 255）。
这个 ID，只占 1 个字节 (8 bit)！

3. 替换：压缩存储

现在，神奇的事情发生了：
原始向量的那 16 个浮点数（占 64 字节），现在只需要存储它最近的聚类中心的 ID（占 1 字节）。

  • 压缩前：128 维 * 4 字节 = 512 字节。
  • 压缩后：8 段 * 1 字节 (ID) = 8 字节。
  • 效果：内存直接缩小了 64 倍！

🔬 专利案例演示：PQ 压缩过程

让我们看看一条专利向量是怎么被"压缩"的：

原始数据：768 维向量（占 3072 字节）

1
2
"卷积神经网络降噪" 的原始向量：
[0.234, -0.567, 0.891, 0.123, -0.456, 0.789, ... 共 768 个数字]

Step 1：切成 8 段

1
2
3
4
5
6
📦 把 768 维切成 8 段，每段 96 维

段 1：[0.234, -0.567, 0.891, ... 共 96 个数]
段 2：[0.123, -0.456, 0.789, ... 共 96 个数]
...
段 8：[0.345, 0.678, -0.901, ... 共 96 个数]

Step 2：每段查密码本

1
2
3
4
5
6
7
📖 每段都有一个预先训练好的密码本（256 个聚类中心）

段 1 最接近密码本里的第 42 号中心 → 记录 ID: 42
段 2 最接近密码本里的第 156 号中心 → 记录 ID: 156
段 3 最接近密码本里的第 7 号中心 → 记录 ID: 7
...
段 8 最接近密码本里的第 233 号中心 → 记录 ID: 233

Step 3：压缩完成！

1
2
3
4
5
6
✨ 压缩结果

原始：768 个 float32 数字 = 3072 字节
压缩后：[42, 156, 7, 89, 201, 34, 178, 233] = 8 字节

压缩比：3072 / 8 = 384 倍！！

内存对比：

存储方式 1000 万条专利占用内存
原始向量 29 GB
PQ 压缩后 76 MB

从 29 GB 压到 76 MB，这就是 PQ 的威力！

img

4. 怎么算距离？（非对称距离计算 ADC）

压缩是爽了，搜索时候怎么算距离？
我们不需要把压缩的向量还原回去（那样太慢）。
我们可以预先算出查询向量 Query 和 密码本里所有中心点 的距离表。查表相加即可！这速度比直接算浮点数乘法快多了。

🔬 专利案例演示：PQ 搜索过程

Step 1：查询来了，先建距离表

1
2
3
4
5
6
7
8
9
10
查询："一种基于深度学习的图像去噪方法" → 768 维向量

把查询向量也切成 8 段，每段和密码本的 256 个中心算距离：

段 1 的距离表：[到中心0的距离, 到中心1的距离, ..., 到中心255的距离]
段 2 的距离表：[到中心0的距离, 到中心1的距离, ..., 到中心255的距离]
...
段 8 的距离表：[到中心0的距离, 到中心1的距离, ..., 到中心255的距离]

共计算：8 段 × 256 个中心 = 2048 次距离计算

Step 2：查表算距离

1
2
3
4
5
6
7
8
9
10
11
📊 计算查询和"卷积神经网络降噪"的距离

"卷积神经网络降噪"的 PQ 码：[42, 156, 7, 89, 201, 34, 178, 233]

查表：
段 1 距离 = 距离表1[42] = 0.015
段 2 距离 = 距离表2[156] = 0.018
...
段 8 距离 = 距离表8[233] = 0.012

总距离 ≈ 0.015 + 0.018 + ... + 0.012 = 0.13（估算值）

对比计算量：

  • 原始方式：768 次浮点乘法
  • PQ 查表：8 次查表 + 8 次加法

快了将近 100 倍！

三、 IVF-PQ：工业界的黄金搭档

现在我们手里有两张王牌：

  1. IVF (倒排索引)：能快速缩小搜索范围（找班长）。
  2. PQ (乘积量化)：能极度压缩内存，加速距离计算。

把它俩合体，就是工业界最经典的 IVF-PQ 算法！

1. 结构设计

  • 外层 (Coarse Quantizer)：用 IVF。把所有向量聚类成 1000 个桶（Voronoi 单元）。
  • 内层 (Fine Quantizer)：在每个桶内部，向量不是存原始数据，而是存 PQ 压缩后的代码。

2. 检索流程

当用户发来一个 Query：

  1. 第一步 (IVF)：先算 Query 离哪几个桶最近（比如最近的 3 个桶）。
  2. 第二步 (Lookup)：拿到这 3 个桶里所有数据的 PQ 代码。
  3. 第三步 (PQ Distance)：利用查表法，快速算出 Query 和这些 PQ 代码的近似距离。
  4. 第四步 (Re-rank)：(可选) 如果想要精度更高，可以把这步选出来的 Top-N 个结果，回库捞出原始向量，做一次精确排序。

🔬 专利案例演示：IVF-PQ 完整流程

这是工业界最常用的组合，让我们完整走一遍！

Step 1：IVF 粗筛（找班长）

1
2
3
4
5
6
7
8
查询："一种基于深度学习的图像去噪方法"

和 1000 个簇中心比距离：
簇 #789（图像处理类）：距离 0.08 ← 最近
簇 #791（计算机视觉类）：距离 0.11
簇 #456（化学类）：距离 0.89

选择 nprobe=3，进入 #789、#791、#788 三个簇

Step 2：PQ 快速计算（查表）

1
2
3
4
5
6
7
8
9
10
11
12
13
三个簇里共有 25000 条专利的 PQ 码

建立距离表（2048 次计算）
然后对 25000 条 PQ 码查表：

#789 簇内：
  "卷积神经网络降噪" PQ码[42,156,7...] → 估算距离 0.13
  "深度学习图像增强" PQ码[41,158,9...] → 估算距离 0.16
  ...

#791 簇内：
  "自编码器去噪" PQ码[45,152,8...] → 估算距离 0.19
  ...

Step 3：返回结果

1
2
3
4
5
6
7
8
📊 IVF-PQ 搜索结果（耗时：0.015 秒）

✅ 第 1 名：基于卷积神经网络的图像降噪系统（估算距离 0.13）
✅ 第 2 名：深度学习图像增强方法（估算距离 0.16）
✅ 第 3 名：图像去噪的自编码器实现（估算距离 0.19）

召回率：100%
内存占用：约 150 MB（IVF 中心点 + PQ 码）

对比总结：

方案 耗时 内存 召回率
暴力搜索 47 秒 29 GB 100%
纯 HNSW 0.003 秒 35 GB 100%
IVF-PQ 0.015 秒 150 MB 100%

结论：IVF-PQ 用 5 倍的时间（仍然很快），换来了 200 倍的内存节省！这就是为什么它是"穷人的最佳选择"。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
graph TD
    Query[用户查询 Query] -->|Step 1: IVF 粗筛| Clusters{找最近的桶}
    Clusters --> BucketA[桶 A]
    Clusters --> BucketB[桶 B]
    
    %% 修改点：标题文本必须加双引号 "..."
    subgraph Inner ["桶内计算 (PQ加速)"]
        BucketA -->|拿出PQ码| CodeA["PQ Codes: 5, 12, 9..."]
        BucketB -->|拿出PQ码| CodeB["PQ Codes: 3, 22, 1..."]
        
        CodeA & CodeB -->|Step 2: 查表算距离| Calc[快速距离估算]
    end
    
    Calc -->|Step 3: 排序| Result[返回近似 Top K]
    
    style Query fill:#f9f,stroke:#333
    style Result fill:#bfb,stroke:#333

四、 总结与避坑指南

讲完了 LSH、PQ 和 IVF-PQ，最后给大家整理一份避坑指南，帮你在这堆算法里找到方向。

1. 什么时候用谁？

算法组合 内存占用 检索速度 精度 (Recall) 适用场景
FLAT 极大 极慢 100% 数据极少，做验证
IVF-FLAT 大 快 高 数据量适中，内存够用
HNSW 很大 极快 极高 目前首选，内存不差钱
IVF-PQ 极小 很快 中等 海量数据 (亿级)，为了省钱
LSH 小 快 低 只需要大概去重，不追求高精度

2. 核心权衡 (Trade-off)

做向量搜索，永远是在做取舍。

  • PQ 是一种有损压缩。压缩率越高（分的段越少），内存越省，但精度损失越大。
  • IVF 是一种剪枝策略。nprobe（搜索的桶数）越小，速度越快，但越容易漏掉正确答案。

建议：
如果你刚开始做 RAG 或者大模型应用，先无脑上 HNSW。等你的数据量真的撑爆了内存（比如到了几千万、上亿级别），或者老板开始心疼服务器成本了，再去研究 IVF-PQ 这种省钱的方案。

好啦，关于向量数据库最硬核的算法原理，咱们这几篇基本上全拆完了！希望大家以后再面对 Vector DB 的时候，不光会调 API，还能明白底层这些巧妙的设计智慧。