HNSW、IVF 与 PQ:定位搜索和压缩各自损失了什么
沿图搜索、聚类分桶和乘积量化的计算路径理解参数,使用受控算例拆分候选损失与距离失真。
“换ANN索引后更快但Recall下降”还不足以确定怎么修。候选没被搜索到,与候选被搜索到但压缩距离算错,是两种不同问题。HNSW、IVF和PQ可以组合,却分别改变访问路径、候选区域和向量存储,应该按这三个维度分析。
HNSW:从稀疏高层导航到底层细搜
HNSW构造分层近邻图,上层节点较少,帮助快速接近查询所在区域;下降到底层后在邻居连接中扩大搜索。它不是每次遍历全图,也不是只走一条永不回头的路径。查询维护候选与已访问集合,探索宽度影响能否绕过局部不佳节点。
M限制连接数量的相关规模,影响图内存、连通性和构建成本;efConstruction影响构建时寻找邻居的探索范围;efSearch影响查询探索宽度。提高查询宽度通常增加工作量,有机会改善Recall,但不能补救所有糟糕图结构。改变建图参数通常需要重建,查询参数则可按请求调整。插入顺序、随机层分配和实现也会影响结果,评测要固定或记录。
IVF:先选桶,再查桶里的向量
IVF先用训练样本学习粗聚类中心,把向量分配到相应倒排桶。查询先找最接近的若干中心,再搜索这些桶里的向量。nlist是桶数,nprobe是查询探查桶数。桶多会让单桶更小,但中心训练、路由与不均衡问题也更明显;只探查一个桶时,边界附近的真正近邻可能在旁边桶里。
训练集需要代表实际分布。新业务数据集中落到少数桶,会产生长尾和Recall退化;不是简单提高nlist就能自动修复。增加nprobe是在查询时扩大候选,重新训练中心则改变分桶结构,两者成本和作用不同。
PQ:把向量拆成子空间并保存码字
乘积量化把D维向量拆成m个子向量,为每个子空间训练独立码本,每个子向量保存最近码字的编号。若每段用b位,主体编码大小为 m×b/8 字节。查询时可以预计算查询子向量到各码字的距离表,对候选的码字查表求和;不一定需要完整解压每个向量。IVFPQ常量化相对粗中心的残差,具体训练和距离公式要看实现。
768维FP32原向量占3072字节,m=96、每段8位时主体编码96字节,比例32倍。这不包括码本、向量ID、粗中心、倒排/图结构、对齐和可选原始向量,不能把主体压缩比当整个数据库的显存下降比。子空间的量化误差可能改变近邻排序;保留原向量精排可修正候选内的错误,但找不回未召回的向量。
用两个对照实验隔离损失
保存为 index_errors.py,运行 python -X utf8 index_errors.py。程序用一维点、手工候选和取整量化展示因果关系,不是HNSW/IVF/PQ实现或性能基准。
"""手工桶与标量量化,用来隔离候选损失和距离失真;非完整IVF/PQ。"""
def search(query,points,ids=None,quantize=False):
ids=list(points) if ids is None else ids
return sorted(ids,key=lambda key:((query-(round(points[key]) if quantize else points[key]))**2,key))
if __name__=='__main__':
points={'a':.44,'b':.49,'c':1.8};query=.52
print('全量原值',search(query,points))
print('受限候选原值',search(query,points,['a','c']))
print('全量量化值',search(query,points,quantize=True))
candidates=search(query,points,quantize=True)[:2]
print('量化前2再精排',search(query,points,candidates))
d,m,bits=768,96,8
print('FP32向量字节',d*4,'PQ编码字节',m*bits//8)
print('不含码本/ID/图边/原始向量的压缩比',d*4/(m*bits//8))全量原值 ['b', 'a', 'c']
受限候选原值 ['a', 'c']
全量量化值 ['a', 'b', 'c']
量化前2再精排 ['b', 'a']
FP32向量字节 3072 PQ编码字节 96
不含码本/ID/图边/原始向量的压缩比 32.0查询0.52最接近b=0.49。限制候选为a/c后,无论距离多精确都找不到b。保留全量候选却把a=0.44与b=0.49都量化为0,两者近似距离相同,固定ID规则让a排前;取量化前2后用原值重排,恢复b第一。这两个错误应分别调搜索范围与压缩/精排配置。
更新和内存也属于选型
精确Flat适合作质量基线;HNSW需要图边内存,删除和重建能力依实现;IVF需要代表性训练集,PQ增加码本与量化训练。向量更新可能等价于删旧再插新,不应默认数据库在同一时刻提供原子替换。高更新率要测写入、索引维护、查询延迟和可见性,而不仅测静态大库QPS。
建立四组对照:精确原值、ANN原值、压缩全候选、ANN压缩并可选精排。固定embedding、过滤条件和查询集,比较业务Recall、ANN Recall、尾延迟、内存、构建时间、更新吞吐。真正选择的是满足质量和延迟约束的工作点,而不是某个索引名称。
运行真实Faiss索引:把搜索范围和量化误差分开
前面的手算只是因果示意。下面实际训练并查询Faiss的IndexHNSWFlat、IndexIVFFlat和IndexIVFPQ,使用4096条16维标准正态合成向量与32个独立查询。它验证真实索引API和该数据上的Recall,不是语义检索效果,也不是吞吐/延迟基准。单线程与固定随机种子有助复现,但不同平台、库版本和图构建实现仍可能改变近邻结果。
本次环境为Python 3.13、NumPy 2.1.3、faiss-cpu 1.15.1。依赖安装在项目F盘的独立目录,没有修改网站依赖。自行复现可以在自己的虚拟环境安装 numpy==2.1.3 faiss-cpu==1.15.1,然后执行 python faiss_indexes.py;特定平台若无该版本wheel,应先确认官方支持,不能把安装失败记成实验通过。
"""真实Faiss索引合成数据实验;Recall是该固定样本的数值,不是生产性能基准。"""
import numpy as np
import faiss
def recall(actual,gold):
return sum(len(set(a)&set(g)) for a,g in zip(actual,gold))/(gold.shape[0]*gold.shape[1])
def main():
faiss.omp_set_num_threads(1)
rng=np.random.default_rng(42)
data=rng.normal(size=(4096,16)).astype('float32')
query=rng.normal(size=(32,16)).astype('float32');k=10
exact=faiss.IndexFlatL2(16);exact.add(data);_,gold=exact.search(query,k)
print('faiss',faiss.__version__,'numpy',np.__version__,'data',data.shape,'queries',query.shape)
graph=faiss.IndexHNSWFlat(16,16);graph.hnsw.efConstruction=80;graph.add(data)
for ef in (16,64):
graph.hnsw.efSearch=ef;_,ids=graph.search(query,k)
print('HNSW efSearch',ef,'Recall@10',round(recall(ids,gold),4))
ivf=faiss.IndexIVFFlat(faiss.IndexFlatL2(16),16,16)
ivf.train(data);ivf.add(data)
for nprobe in (1,4,16):
ivf.nprobe=nprobe;_,ids=ivf.search(query,k)
print('IVFFlat nprobe',nprobe,'Recall@10',round(recall(ids,gold),4))
pq=faiss.IndexIVFPQ(faiss.IndexFlatL2(16),16,16,4,4)
pq.train(data);pq.add(data);pq.nprobe=16
_,ids=pq.search(query,100)
reranked=[]
for q,candidates in zip(query,ids):
candidates=candidates[candidates>=0]
distances=((data[candidates]-q)**2).sum(axis=1)
reranked.append(candidates[np.argsort(distances)[:k]])
print('IVFPQ nprobe16 Recall@10',round(recall(ids[:,:k],gold),4))
print('IVFPQ候选100原值精排 Recall@10',round(recall(np.array(reranked),gold),4))
print('PQ主体每向量字节',pq.code_size,'FP32主体字节',16*4)
assert recall(ivf.search(query,k)[1],gold)==1.0
assert recall(np.array(reranked),gold)>=recall(ids[:,:k],gold)
print('全桶IVFFlat精确召回与候选精排非退化断言通过')
if __name__=='__main__':main()本机实际输出:
faiss 1.15.1 numpy 2.1.3 data (4096, 16) queries (32, 16)
HNSW efSearch 16 Recall@10 0.9
HNSW efSearch 64 Recall@10 1.0
IVFFlat nprobe 1 Recall@10 0.325
IVFFlat nprobe 4 Recall@10 0.7688
IVFFlat nprobe 16 Recall@10 1.0
IVFPQ nprobe16 Recall@10 0.3031
IVFPQ候选100原值精排 Recall@10 0.8531
PQ主体每向量字节 2 FP32主体字节 64
全桶IVFFlat精确召回与候选精排非退化断言通过IndexFlatL2提供相同向量、相同L2度量的精确top10。HNSW由efSearch16到64,这次Recall从0.9到1;不能据此承诺所有数据单调提高或达到满召回。IVFFlat在nprobe=16访问所有16个桶后恢复精确结果,nprobe=1只得到0.325,体现候选范围损失。
IVFPQ也访问全部桶,却只有0.3031,说明此时主要损失来自压缩距离而不是未探查桶。取100个近似候选后使用保存的原值计算L2精排,提高到0.8531,但仍不是1,因为真正近邻可能不在这100个候选内。代码保留原数据用于精排,所以2字节PQ主体不等于整个系统每条只占2字节;原向量、码本、ID与索引结构都额外占空间。
该实验确实构建了HNSW/IVF/PQ,但没有测真实embedding、元数据过滤、多租户、增量删除、服务并发或磁盘持久化。用业务数据选型时要扩大样本并同时记录Recall、构建成本、p95/p99、内存和更新行为。
删除与漂移更新:索引算法名不等于更新契约
HNSW上的删除要分清三件事:业务不可见、搜索结果不再返回、物理节点/边和向量空间被回收。应用tombstone可以立即阻断结果,却不表示索引已经释放内存。某些实现保留被标记节点供遍历或复用槽位;另一些不支持该删除接口,因此不能写一段“所有HNSW都调用remove_ids”的通用操作。2026-10-31在本页同一个本地 Faiss 1.15.1 环境对两条二维向量的 IndexHNSWFlat 调用 remove_ids,实际得到 remove_ids not implemented for this type of index。这个结果限于该版本/索引类型,不推断未来版本;而 hnswlib官方接口 明确区分 mark_deleted 与允许复用删除槽位的配置。hnswlib这里只核对当日默认分支README,未安装运行;选型时应固定其release/commit并重新验证。
用抽象链路a—b—c理解风险:若b是桥,直接删除b及其边而不修补会使a到c的可达性改变;只标记“不返回b”则未必断开遍历,但仍可能消耗访问预算。这是图结构推演,不声称实际HNSW只有一条链。可选策略是应用立即过滤已删除ID,再按实现支持处理标记/替换,累积删除或召回退化达到门槛时用仍有效原向量重建。重建多占一份索引和计算资源,但能清理历史负担;小批删除不应无条件每条全量重建。记录逻辑删除数量、有效返回率、访问工作量、Recall与内存,区分安全生效时间与物理回收时间。
IVF/PQ则有训练分布问题。假设旧数据在0和10附近,粗中心也是0/10;新数据大量集中到100,可能全部塞进旧中心10的桶,形成负载偏斜;若残差PQ码本只见过很小残差,也会出现更大的重建误差。先固定原始向量比较Flat、IVFFlat和IVFPQ:Flat正常、IVFFlat在小nprobe漏而全桶恢复,优先查分桶/搜索范围;全桶IVFPQ仍差,查量化误差与训练样本。提高nprobe不改变PQ码本,不能替代重训。修改中心后旧向量必须重新分配倒排桶;修改码本后旧字节码也不能按新码本解释,因此应构建新的索引实例并重加/重编码,而非对已承载请求的旧实例原地改几组参数。
安全切换顺序是:冻结源快照水位w0,训练并构建v2,重放w0之后的增删改到w1,验证条数、有效ID、删除水位、过滤和固定gold,再发布包含编码器/度量/中心/PQ/数据水位的完整清单。查询一次只绑定一个清单版本;活动指针用存储的原子比较交换,不能逐字段更新造成新编码器配旧索引。多副本还要确认v2已就绪及路由版本传播,保留旧版本直到在途读取结束。回滚也必须持续应用删除和权限撤销,不能复活旧数据。这里是状态迁移设计,没有执行分布式切换。Faiss具体删除/ID语义见 官方特殊索引操作;新增训练集应同时覆盖旧/新业务分布,防止只适配最新批而损伤旧问题。
综合边界推演与面试追问
真实Faiss实验保持同一4096×16向量:IVFFlat的nprobe从1到16,Recall由0.325到1;全桶IVFPQ仍只有0.3031,候选100原值精排为0.8531。HNSW efSearch16与64分别得到0.9与1。这些数值只对应固定合成数据。
图连接M与建图探索影响内存和质量,查询efSearch改变在线探索;IVF nlist改变分桶,nprobe改变访问;PQ减少主体编码但引入距离失真。增加搜索无法完全修复量化排序,保留原值精排也增加内存且受候选上限限制。
新数据集中落少数桶时检查桶负载与训练分布;图更新/删除看具体实现是否支持及其维护代价。分开记录建图时间、码本/ID/图边/原值内存,不能用2字节编码声称整个系统每向量仅2字节;索引参数必须与版本一同留档。
课后练习展开习题收起习题
先独立作答,再展开参考思路。检查自己的解释是否包含机制、条件和反例。
HNSW的M、efConstruction、efSearch分别控制什么?
参考思路与常见误区
M关联每节点连接规模与图内存;efConstruction影响建图寻找邻居的探索;efSearch控制查询探索宽度。建图参数改变通常要重建,查询宽度可查询时调整,具体约束依实现。
常见误区:把所有参数都当成返回top-k条数。
IVF中nlist和nprobe为什么不能混为一谈?
参考思路与常见误区
nlist是训练得到的粗桶数量,影响分桶结构;nprobe是一次查询检查多少桶,影响候选范围。边界近邻在未探查桶中时,提高nprobe可能恢复,但分布失衡还可能需要重训中心。
常见误区:认为增加桶数必然提高召回且不改变构建成本。
768维FP32转96段8位PQ,主体编码多大?
参考思路与常见误区
原向量768乘4为3072字节;编码96乘8除8为96字节,主体比例32倍。码本、ID、图边、中心与可选原向量不在这个比例里。
常见误区:宣称整个数据库总内存一定下降32倍。
如何拆分ANN候选损失与量化损失?
参考思路与常见误区
先比较全量原值和ANN原值,隔离搜索范围;再固定全量或相同候选比较原值与量化距离,隔离表示失真;最后测试量化候选的原值精排。保持模型、度量和过滤相同。
常见误区:一次同时改图参数、量化精度与embedding模型后归因给某一项。
原向量精排能修复所有量化和ANN错误吗?
参考思路与常见误区
只能重新排序已经进入精排候选的向量,未召回的近邻无法恢复。应扩大或改善候选,再在质量、内存和延迟约束下选择精排窗口。
常见误区:只要最后有精排就认为前面的召回无关紧要。