可验证语义搜索能否扩展到HNSW图？Atlas与零知识证明挑战

可验证语义搜索必须弥合的信任鸿沟

语义搜索已成为推荐系统、网络搜索和检索增强生成的默认检索机制，但服务提供商同时控制着索引和计算过程，而客户端只能看到返回的结果[1]。服务提供商可能返回过时结果、为削减成本而截断搜索、使排序偏向于自身倾向的结果，或悄然偏离既定算法，而且随着检索结果被下游服务直接消费而无需人工监督，这些风险会进一步叠加[1]。零知识证明原则上可以通过证明结果是在已承诺的索引上按照约定算法得出的，来消除这种信任假设，但高效实现这一点十分困难，因为HNSW——大规模近似最近邻搜索事实上的标准——在构造上就是控制流密集型的[1]。

HNSW 使用优先队列、数据依赖分支和提前退出来导航分层邻近图，这种计算难以映射到现代 ZKP 所依赖的算术约束系统上，因为后者要求电路预先固定，并在每一步都为最坏情况行为做好准备 [1]。因此，此前的可验证搜索系统避开 HNSW，转而构建在基于聚类的索引之上，这类索引离线划分数据集，并通过搜索离查询最近的聚类来回答查询 [1]。这种数据无关的搜索模式可以紧凑地编码为多项式约束，但它牺牲了召回率，因为聚类只选择一次，而聚类之外更近的邻居在搜索的剩余过程中无法被访问到 [1]。

Atlas如何在不放弃图结构的前提下使HNSW可证明

Atlas通过三项技术解决了编码问题。第一，预处理通过cq查找论证将所有依赖数据库的开销转移到离线阶段，因此每次查询的证明开销随遍历长度而非数据库规模扩展，从而保持了HNSW每次查询的亚线性开销[1]。第二，Atlas通过将多层下降折叠为单次图游走，并将两个相互依赖的优先队列替换为一个有界候选集，将HNSW重构为固定大小状态的过程，且作者证明了重构后的输出与HNSW等价[1]。第三，时间步标记批处理为每个元组打上步骤标识符，并将整个遍历的逐步置换和查找论证合并为单次调用，从而防止证明开销随步骤预算增长[1]。

步数上限是重构后的搜索与HNSW唯一的差异所在：预算足够大时，可以精确复现HNSW的结果；预算较小时，则以召回率为代价降低证明成本[1]。正是这一设计选择使系统具备可调性：运营者可以用少量召回率换取更短的证明轨迹，而评估则精确量化了在不同预算分位数下究竟损失了多少召回率[1]。

不同数据集规模下的召回率保持与证明成本

在SIFT1M上，Atlas在0.80秒内完成查询证明，证明大小为16.5 kB，客户端在40毫秒内完成验证；在召回率@1超过0.9的最小配置下，步数预算为Tg=6和Tb=26 [1]。证明成本随达到召回目标所需的束宽和步数预算而扩展，而非随数据库规模扩展：BIGANN-100M仅将证明时间提升至1.98秒，语料库规模仅通过搜索配置影响证明成本，因为更大的语料库需要更大的ef来达到召回目标，ef从26升至48，而M=16保持不变 [1]。截断至固定步数预算对召回率的牺牲很小，因为在第95百分位预算下，经过证明的搜索在整数数据集上与明文HNSW的召回率@1差距保持在0.8个百分点以内，且每个数据集在可部署配置下均超过0.9召回率@1 [1]。

随着嵌入维度的变化，情况也有所不同。在GIST1M（d=960）上，Atlas证明一次查询需要36.66秒，证明大小为75.5 kB，验证时间达到1.94秒，这一开销综合了高维度以及达到召回目标所需的最大配置[1]。在浮点数据集Deep10M和GIST1M上，量化引入了额外的召回损失，在GIST1M上(M,ef)=(32,64)时达到5.2个recall@1点，该测量在固定步长搜索等价于无界HNSW的最大预算下进行，从而将量化效应与截断效应隔离开来[1]。

与现有可验证检索系统的比较

与同样证明HNSW搜索的同期工作zkRAG相比，Atlas在相同参数(M,ef)=(32,64)和相同数量的已处理第0层节点(Nexp=2^12)下，证明查询速度快2.8倍，在Xeon 8151的单线程上耗时18.6秒，而zkRAG在Xeon 6126的单线程上耗时51.5秒，两款处理器单核性能差距在10%以内[1]。速度提升的同时还伴随着更强的保证，因为zkRAG的证明会泄露每一层所采取的步数，而Atlas除结果外不泄露任何信息[1]。在多线程设置下，Atlas也优于IVF-PQ系统V3DB，达到V3DB所能达到的每一个召回水平都快10倍到45倍，因为乘积量化将V3DB的recall@1上限限制在0.50，而Atlas在0.64秒内就超过了这一上限，V3DB则需要29.2秒[1]。

在完整的RAG流水线中，使用BGE-M3进行嵌入、Qwen2-7B进行生成，Atlas以远低于VeriRAG的证明时间超越了其F1，在SQuAD上以2.5秒达到60.3 F1，而VeriRAG为6.6秒达到46.9；在TriviaQA-Val上以3.2秒达到51.3，而VeriRAG为38.7秒达到41.1 [1]。这一差距源于IVF-PQ的检索质量瓶颈，因为基于聚类的索引恢复的相关段落较少，并降低了生成器所接收上下文的质量 [1]。Atlas的证明成本取决于搜索配置而非语料库规模，而VeriRAG的证明成本则随语料库直接增长，从SQuAD上的6.6秒增至TriviaQA-Train上的56.0秒以及KILT上的96.2秒 [1]。

可验证性保证的边界

该证明仅限于 HNSW 搜索和特定基准，评估覆盖了六个标准 ANN 基准，跨度从一百万到一亿个向量、嵌入维度从 96 到 960，但未扩展到其他索引结构或查询类型 [1]。所报告的召回率反映了量化和截断两者的损失，而在浮点数据集上，仅量化损失在 GIST1M 上就达到 5.2 个 recall@1 点，这意味着即使在最大预算下，可验证系统的召回率也不等同于未量化的 float32 基线 [1]。降维技术使投影维度成为另一个可调参数，以答案质量换取证明成本，其中 PCA 降至 d=128 可将证明时间缩短 3 倍，代价是在各数据集上损失 3.5 至 6.1 个 F1 点 [1]。

可验证计算的更广泛背景既揭示了这一研究方向的潜力，也揭示了其局限。RaG-Tree表明，HNSW图可以与R树耦合用于多属性范围过滤搜索，在DBLP、MSMarco和LAION上，当召回率约为0.95时，其QPS分别比最强的竞争方法高出2.8倍、2.4倍和1.9倍，但其关注点在于过滤条件下的查询效率，而非密码学可验证性[2]。零知识验证已被探索用于基于协作无人机蜂群和信任感知多智能体学习的边缘生成式AI推理，其中验证时效性、恶意服务器检测延迟和能效是所测量的结果，这表明可验证性正在AI技术栈的多个层面以不同的约束和威胁模型被追求[4]。早期关于近似最近邻搜索的工作确立了压缩和量化技术——如结合自适应乘积量化的结构敏感哈希和集合压缩树——可以在SIFT1M和GIST1M上实现低内存占用和精确近似，为可验证系统提供了必须对照衡量的检索质量基线[3][5]。仍不确定的是，Atlas方法是否能以非 prohibitive 的证明成本推广到其他基于图的索引、过滤搜索以及超出已测试范围的嵌入维度。

关于这些来源

本研究页面基于5项研究（4篇同行评审、1篇预印本）——发表于2015年至2026年间，其中3项来自2024年或之后——这些研究是从通过质量筛选的6项研究中选出的最相关研究，而这些研究又是从超过5亿篇文献的数据库中检索到的50篇论文中筛选而来。

本文引用的文献