LEANN: A Low-Storage Overhead Vector Index

作者/机构: Yichuan Wang† 1, Zhifei Li 1, Shu Liu 1, Yongji Wu† 1, Ziming Mao 1, Yilong Zhao 1, Xiao Yan 2, Zhiying Xu∗ 3, Yang Zhou 1 4, Ion Stoica 1, Sewon Min 1, Matei Zaharia 1, Joseph E. Gonzalez 1

A1 主要贡献

核心问题: 基于嵌入的向量搜索在推荐系统和检索增强生成（RAG）等应用中至关重要，但其依赖的向量索引需要存储高维嵌入和大量的索引元数据，总大小可能是原始数据（如文本块）的数倍。这种高存储开销使得在个人设备或大规模数据集上部署向量搜索变得困难甚至不切实际。

研究目标: 设计一种能够显著减少存储开销，同时保持高搜索准确率和满足合理宽松延迟要求的向量索引。

创新点 (LEANN):
本文提出了LEANN，一种为存储受限环境量身定制的向量索引，通过系统和算法优化，可将索引占用空间减少到原始数据的5%以下，同时保持高准确率和合理的检索延迟。其核心创新点包括：

1. 即时嵌入重计算: LEANN的核心思想之一是，在查询时动态地重新计算嵌入向量，而不是将它们全部存储起来。它观察到，先进的邻近图索引（如HNSW）在每次查询时仅需访问一小部分嵌入。这极大地减少了对嵌入向量本身的存储需求。
2. 两级搜索与动态批处理: 为缓解即时重计算带来的延迟，LEANN引入了两级搜索算法。该算法利用高压缩率下（虽然不精确但计算成本低）的近似距离来剪枝，从而减少需要精确重计算的嵌入数量。此外，LEANN还采用动态批处理机制，将跨图搜索步骤的嵌入计算聚合起来，以提高GPU利用率并降低重计算延迟。
3. 高阶节点保留的图剪枝: 针对索引元数据（邻近图）本身也占用大量空间的问题，LEANN提出了一种高阶节点保留的图剪枝策略。该策略基于一个关键观察：图中少数高阶（连接邻居多）的“枢纽”节点被访问的频率远高于低阶节点，对搜索至关重要。因此，LEANN会保留这些枢纽节点的边，同时移除低阶节点的低效用边，从而在不牺牲搜索准确性和效率的情况下，大幅减小索引大小。
4. 存储高效的索引构建与更新: LEANN设计了一种分片合并的索引构建流水线，确保即使在构建大规模数据集的索引时，峰值存储消耗也不会超过设定的预算。同时，它还支持对压缩索引进行高效更新（如添加新数据），在保持存储效率的同时显著减少更新时间。

如下表1所示，在RAG应用中，与传统的BM25等方法相比，LEANN能在大幅减少存储（从188GB降至4GB）的同时，保持与HNSW相当的下游任务准确率，且端到端延迟仅有少量增加。

A3 背景知识

向量搜索。为了检索非结构化数据（例如文本、图像、视频）中语义相关或相似的对象，向量搜索被广泛使用。具体来说，给定一个向量数据集 $X = \{x_1, x_2, · · · , x_N \} \subset \mathbb{R}^d$ 和一个查询向量 $q \in \mathbb{R}^d$，向量搜索旨在找到 $X$ 中与 $q$ 最相似的top-k个向量，即：

$$|\mathcal{S}_q| = k \text{ with } \|q - x_i\| \le \|q - x_j\| \forall x_i \in \mathcal{S}_q, x_j \in \mathcal{X} \setminus \mathcal{S}_q.$$

相似度函数也可以是内积或余弦相似度，其中值越大表示相似度越高。然而，由于高维空间中的维度灾难，精确的向量搜索需要进行线性扫描【索引49，A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search，2021】，这对于大型数据集来说成本高昂。因此，近似最近邻搜索（ANNS）被普遍采用【索引25，Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs，2018；索引21，The inverted multi-index，2012】，它通过牺牲微小的结果不准确性来换取显著降低的查询延迟。ANNS的结果质量通常通过召回率来衡量，即返回的近似邻居集合 $S'_q$ 中包含的真实top-k邻居的比例，即：

像RAG这样的应用通常需要高召回率（例如，≥ 0.9）才能获得良好性能【索引43，Towards understanding systems trade-offs in retrievalaugmented generation model inference，2024】。

索引在向量搜索中的作用。索引对于向量搜索的效率至关重要，它能将距离计算限制在一小部分向量上。向量索引的存储成本包括两个部分：向量本身和索引元数据。最流行的两种向量索引是IVF（Inverted File）【索引21，The inverted multi-index，2012】和邻近图（Proximity Graph）【索引25，Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs，2018；索引10，Fast approximate nearest neighbor search with the navigating spreadingout graph，2019；索引44，DiskANN: fast accurate billionpoint nearest neighbor search on a single node，2019】。IVF将向量分组到簇中，并用一个中心向量表示每个簇，查询时首先扫描这些中心，然后检查少数最相似簇中的向量。邻近图则连接相似的向量形成一个图，并通过在图上进行最佳优先遍历来进行向量搜索。尽管IVF构建成本更低，存储索引结构所需的空间也更小，但邻近图在向量搜索方面达到了SOTA效率，因为它需要的距离计算要少得多【索引44，DiskANN: fast accurate billionpoint nearest neighbor search on a single node，2019】。

邻近图上的最佳优先搜索。邻近图索引的变体（例如，HNSW【索引25，Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs，2018】，NSG【索引10，Fast approximate nearest neighbor search with the navigating spreadingout graph，2019】，Vamana【索引44，DiskANN: fast accurate billionpoint nearest neighbor search on a single node，2019】）在边的连接规则上有所不同，但查询处理算法是相似的。算法1展示了邻近图上的最佳优先搜索。该搜索维护一个有界的优先队列 $C$，其中包含候选节点，按它们到查询 $q$ 的距离排序。在每个探索步骤（第5行），算法读取（但不移除）$C$ 中最近的未访问节点 $u$ 并探索其邻居。对于每个尚未计算距离的邻居，算法提取其嵌入，计算其与 $q$ 的距离，如果队列未满或者该邻居比 $C$ 的末尾条目更近，则将其插入到 $C$ 中。参数 $ef$ 限制了队列的大小，并作为一个质量调节旋钮：更大的 $ef$ 会以更多的距离计算为代价来提高召回率。一旦 $C$ 中的所有节点都被访问过，搜索就终止。根据经验，基于图的索引只需 $O(\log N)$ 次嵌入提取和距离计算就能实现高召回率。这是因为图遍历可以通过每一步移动到更相似的邻居来快速收敛到查询的邻居。

A2 方法细节

3 LEANN 概述

图1展示了LEANN的端到端工作流程，包括离线索引构建和在线查询服务。

离线阶段。给定一个项目数据集，例如分块的非结构化文本，LEANN会计算嵌入并构建一个基于图的向量索引。为了最小化存储，它应用了一种保留高阶节点的图剪枝算法（§5），并丢弃密集的嵌入，只保留剪枝后的图结构。在构建过程中，LEANN还建立了一个轻量级的产品量化（PQ）表，该表存储近似嵌入，用于在查询处理期间进行快速距离估计（§4）。可选地，如果指定了峰值存储预算，LEANN会采用一种基于图分区的构建策略（§6），通过顺序构建和合并分片来将存储占用控制在此限制内。在离线阶段结束时，LEANN会持久化两个紧凑的组件：（i）剪枝后的图邻接表和（ii）PQ压缩的嵌入表。

在线阶段。当查询到达时，LEANN使用算法1在剪枝后的图上进行搜索。为了加速查询处理，LEANN采用了一种两级搜索策略，首先使用PQ嵌入计算轻量级的近似距离，然后通过本地嵌入生成器按需为最有希望的候选者重新计算精确嵌入。在重计算期间，LEANN应用动态批处理来组合跨探索步骤的多个候选节点，从而提高GPU利用率并减少端到端延迟。最后，系统通过与查询的精确距离对所有访问过的节点进行排序，并将排名最高的结果返回给下游任务。LEANN还提供了一个轻量级的更新流水线用于动态索引维护（§6），并且如果磁盘容量允许，还可以选择性地使用嵌入缓存来存储频繁访问的节点，以避免冗余的重计算。

存储组成。在两个阶段中，LEANN都存储紧凑的结构。对于 $N$ 个数据块（节点），剪枝后的图需要 $O(N \bar{D})$ 个整数条目，其中 $\bar{D}$ 表示平均节点度数。PQ表使用的码本比原始的FP32嵌入小100倍，占用 $O(4N \times \text{dim}/100)$ 字节（例如，dim = 768）。这些组件共同作用，与传统的密集索引相比，存储减少高达50倍。

使用场景。LEANN可以在用户设备（例如笔记本电脑和个人服务器）上进行向量搜索，这些设备的存储空间非常有限。我们的实验评估也主要集中在这种使用场景上。LEANN也可能用于数据湖，其中包含许多数据集，而一些冷数据集的查询频率很低【索引24，Cracking vector search indexes，2025】。为这些冷数据集存储索引会产生高昂的空间开销，而由于查询频率低，为它们重新计算嵌入的成本不高。同样，LEANN可以处理嵌入访问模式有偏斜的数据集，例如在推荐和内容搜索中，热门条目更有可能成为向量搜索的结果【索引27，High-throughput vector similarity search in knowledge graphs，2023】。对于这些数据集，LEANN可以为热门条目存储精确向量，并对冷条目使用嵌入重计算来减少存储。

算法2 两级搜索

1: 输入：查询q，入口点p，重排序比例α，结果大小k，搜索队列长度ef
2: 输出：q的k个最近邻
3: 初始化大小为ef的优先队列EQ，包含(p, Dist(q, xp))
4: 初始化空的近似优先队列AQ
5: while EQ中有未访问的节点 do
6:   从EQ中读取最近的未访问节点u
7:   标记u为已访问
8:   for u的每个邻居v do
9:     if 未计算与q的近似距离 then
10:      提取v的近似嵌入x˜v
11:      将(v, Dist(q, x˜v))插入AQ
12:  C ← AQ中排名前α%的候选者，不包括EQ中的节点
13:  for 每个c ∈ C do
14:    重计算嵌入xc
15:    尝试将(c, Dist(q, xc))插入EQ
16: return EQ中距离最小的k个节点

4 基于图的重计算

在本节中，我们介绍我们高效的重计算流水线，它减少了参与重计算的节点数量（§4.1），并在该过程中充分利用GPU资源（§4.2）。

4.1 带有混合距离的两级搜索

动机。LEANN为所有向量存储PQ码以实现近似距离计算。像DiskANN这样的现有系统使用这些近似距离在邻近图上搜索，然后用精确距离对排名靠前的候选者进行重排序，例如，为得到top-10结果而重排top-100的近似邻居。然而，这种方法对LEANN来说是有问题的，因为我们的PQ码为了实现紧凑存储而使用了高压缩比，这导致了较大的量化误差。具体来说，近似距离可能通过访问次优候选者而导致图遍历走弯路，从而延长了搜索时间。此外，由于次优候选者的存在，一些真实的邻居可能会被错过，此时即使重排序更多的近似邻居也无法提高召回率（见图4）。为了解决这个问题，我们将近似和精确距离计算交织进行，而不是像现有系统那样将它们隔离开。具体来说，我们使用精确距离来选择要访问的候选者，以保证图遍历的高质量，同时使用近似距离来剪除不必要的精确计算，从而同时实现准确性和效率。

解决方案。算法2概述了完整的流程。在每个探索步骤中，LEANN首先使用PQ为所有邻居计算近似距离（第11行），并维护一个近似队列（AQ）来存储所有已探索节点的这些值。我们不为每个邻居都重新计算嵌入，而是定义一个重排序比率 $\alpha$，并从AQ中提取排名前 $\alpha\%$ 的节点，同时排除那些已经在精确队列（EQ）中的节点。选定的子集 $C$（第12行）随后会被精确地重新计算，并且每个节点都会被插入到EQ中以供进一步探索。这种混合策略在不牺牲准确性的前提下，显著减少了重计算的次数。

讨论。在实践中，LEANN使用一个码本小100倍的PQ表，用 $O(4N \times \text{dim}/100)$ 字节表示嵌入（在我们的设置中dim = 768）。这些近似距离为早期过滤提供了一种廉价而有效的信号，而重计算仅保留给一小部分排名靠前的候选者。尽管PQ引入了量化误差，但选择性的精确重计算恢复了排名的保真度并确保了检索质量。该方法很容易推广到其他形式的近似，例如使用蒸馏的嵌入模型或链接与编码表示（link-and-code representations）【索引8，Link and code: Fast indexing with graphs and compact regression codes，2018】。

4.2 用于重计算的动态批处理

动机。在朴素方法中，嵌入是为每个邻居节点逐一重新计算的，如算法2的第14行所示。为了更好地利用GPU，LEANN将在一个探索步骤中对所有邻居节点进行批处理，以便它们的嵌入可以一起重新计算。然而，即使进行了这种优化，每个批次仍然很小——受限于当前节点 $u$ 的度数。在两级搜索算法中（第12行），问题变得更加突出，因为每一步的候选集更小。

解决方案。为了进一步提高GPU利用率，LEANN引入了一种动态批处理策略，该策略放宽了最佳优先搜索（算法1）中严格的数据依赖关系。虽然这会在探索顺序中引入轻微的陈旧性，但它使得可以跨多个探索步骤进行批处理，从而增加了有效批次大小并提高了吞吐量。

具体实现。LEANN动态地从优先队列中收集一组最近的候选者。算法会累积需要重计算的节点，直到达到目标批次大小（例如64），这个大小可以通过轻量级的离线分析高效地确定。这种动态批处理机制自然地与§4.1中描述的两级搜索策略相结合：在实践中，LEANN在多次迭代中累积集合 $C$ 中的节点，直到达到预定义的批处理阈值，然后一起为 $C$ 中的所有节点重新计算嵌入。

优势。这种动态批处理方法允许LEANN跨多个图探索步骤对节点进行批处理，而不管单个节点的度数如何，通过牺牲轻微的陈旧性来换取相比单步处理显著提高的GPU利用率。

5 紧凑的图结构

通过两级搜索和动态批处理机制优化了重计算延迟后，我们现在研究LEANN如何通过一种保留高阶节点的图剪枝算法进一步减少图索引元数据的存储开销。如§3所述，尽管LEANN通过在查询时重新计算嵌入而无需存储精确嵌入，但引导搜索的图元数据仍然会产生显著的存储成本（见表1）。实际上，即使有嵌入，仅索引元数据一项就可能超过30%。

问题形式化。给定磁盘使用约束 $B$，LEANN旨在对图索引进行剪枝，使其元数据存储保持在预算内，同时维持检索准确性。形式上，优化问题如下：

这里，$G_1$ 是剪枝后的图，而 $|V_i|$ 是在使用 $G_1$ 进行搜索时，在每个探索步骤中重新计算的节点数。一个较小的 $T(G_1)$ 表示重计算次数较少，因此查询延迟较低。$Space(G_1)$ 表示图的元数据大小，以压缩稀疏行（CSR）格式存储，该格式记录了每个节点的出度邻居ID。$deg(v)$ 是节点 $v$ 的出度，每个存储的邻居ID占用4个字节。目标是在将图保持在存储预算 $B$ 内且准确率（召回率）高于阈值 $\tau$ 的同时，最小化重计算成本。

动机。有两种简单的方法可以缩小邻近图索引：（1）随机删除边，以及（2）降低每个节点的度数限制。如图6所示，这两种方法即使在轻微的尺寸缩减下也会显著降低搜索准确性，因为它们损害了图的连通性，而这对于有效的遍历至关重要。从图2中我们观察到，边的重要性并非均等：一小部分节点具有高度数（即接近或达到度数限制），并且这些节点的访问频率远高于低度数节点。这些高度数节点实质上充当了图遍历的“导航枢纽”，类似的现象也在【索引28，Down with the hierarchy: The’h’in hnsw stands for” hubs”，2024】中被观察到。因此，我们保留高度数节点的边以确保邻近图的良好导航性，并对低度数节点进行边剪枝。

解决方案：保留“枢纽”节点。我们的关键洞见是，保留一小部分枢纽节点足以维持搜索性能。借鉴先前的工作【索引34，Hm-ann: efficient billionpoint nearest neighbor search on heterogeneous memory，2020；索引28，Down with the hierarchy: The’h’in hnsw stands for” hubs”，2024】，高度数节点是图连通性的骨干；因此，LEANN专注于保留这些枢纽，同时减少边的总数。算法3概述了这种保留高阶节点的图剪枝策略。

具体策略。我们根据节点的重要性分配度数阈值：大多数节点的度数被限制在一个较低的值 $m$，而一小部分节点（$\beta\%$）可以保留多达 $M$ 个连接（第7行）。根据经验，我们设置 $m = M/5$，并通过离线分析为给定的存储预算 $B$ 确定 $M$。我们使用节点度数作为节点重要性的代理，并按度数选择前 $\beta\%$ 的节点（第4行）。仅保留前2%的高度数节点就能显著减少边的数量，同时保持高检索准确性。

保证图的可导航性。此外，虽然我们在节点首次插入图时限制了其出向连接的数量（第8行），但我们允许所有节点与新插入的节点形成双向链接，上限为较高的阈值 $M$（第11行），而不是较低的限制 $m$。这种设计确保了每个节点都保留了与高度数枢纽节点连接的机会，从而以最小的搜索质量影响保持了图的可导航性。

6 索引构建与更新

存储高效的索引构建。LEANN中朴素的索引构建方法需要预先计算所有对象的嵌入以构建图结构。尽管这些嵌入之后会被丢弃以在查询时减少存储，但构建过程中的峰值存储使用量仍然可能相当可观。为了解决这个问题，LEANN引入了一种简单而有效的分片合并流水线策略，该策略能在用户指定的存储约束下高效地构建索引，同时保持图的质量。分片合并流水线过程包括三个阶段：1）使用k-means进行软分配。我们首先在语料库的一小部分子集上运行k-means以获得k个质心。然后，每个对象被嵌入并分配给其最近的两个质心。这是顺序执行的；分配后，嵌入会立即被丢弃，只保留每个段落的两个质心映射。2）分片式图构建。分配后，我们为k个分片中的每一个分别构建图索引。对于每个分片，重新计算嵌入，构建图，然后丢弃嵌入。由于每个段落都属于两个分片，合并后的图能实现良好的全局连通性。3）图合并。然后我们将k个分片图合并成一个单一的结构。对于出现在两个分片中的节点，我们将其两个HNSW层级中较高的一个作为最终层级。对于较低的层级，我们合并它们的边列表，并在节点度数超过M时随机丢弃边。这种启发式方法产生了一个连接良好、高质量的图（参见附录D中的图10）；更高级的合并策略，如基于RNG的剪枝【索引16，Relative neighborhood graphs and their relatives，1992】，留待未来工作。

高效的索引更新。我们通过一系列优化在LEANN中实现了高效更新，这些优化大幅减少了计算和存储开销。对于单个更新请求，朴素的重计算过程的复杂度为 $O(M \cdot efC + efC^2 + M^3)$，这源于重复的嵌入计算和邻居维护。这三项分别对应于邻居搜索、邻居选择以及反向边的选择和更新。LEANN通过轻量级嵌入、缓存和简化的选择策略来提高效率，消除了冗余计算，并将总成本降低到 $O(M \cdot efC)$，同时保持了图的连通性和质量。对于删除操作，LEANN采用软删除，通过将节点标记为非活动状态而不是从图结构中移除它们，从而在避免代价高昂的图重组的同时保持了连通性。详细信息在附录B中提供。

批量添加操作。除了单节点插入，LEANN还通过系统级优化支持批量添加操作。传入的嵌入被临时缓冲，在收到查询时，LEANN会扫描缓冲区并将其结果与现有图的结果合并。缓冲的条目随后被异步插入，从而分摊了更新成本。这种设计在保持低搜索延迟的同时，最小化了计算和峰值存储使用。

A4 实验环境

• 数据集:

  • 数据存储 (Datastore): 使用 RPJ-Wiki 数据集【索引6，RedPajama: An open source recipe to reproduce LLaMA training dataset，2023】，包含约 76 GB 的原始维基百科文本。文本被分割成 256 个 token 的块，共计 6000 万 (N=60M) 个段落。
  • 嵌入模型: 使用 CONTRIEVER 模型【索引15，Unsupervised dense information retrieval with contrastive learning，2021】为每个块生成 768 维的向量，总嵌入大小约为 173 GB。
  • 问答 (QA) 数据集: 采用四个 RAG 和开放域检索的标准基准：NQ【索引19，Natural questions: A benchmark for question answering research，2019】，TriviaQA【索引17，Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension，2017】，GPQA【索引32，Gpqa: A graduate-level google-proof q&a benchmark，2024】和 HotpotQA【索引53，Hotpotqa: A dataset for diverse, explainable multi-hop question answering，2018】。
  • 其他任务: FinanceBench【索引14，Financebench: A new benchmark for financial question answering，2023】（金融文档检索）、Enron Email Corpus【索引38，EnronQA: Towards personalized RAG over private documents，2024】（邮件检索）和 LAION【索引39，Laion-400m: Open dataset of clipfiltered 400 million image-text pairs，2021】（图像数据检索）。

• 硬件配置:

  • 工作站: NVIDIA RTX 4090 GPU【索引29，Nvidia geforce rtx 4090 graphics card，2022】，32GB RAM，1 TB 磁盘，运行 WSL2。
  • Mac: AWS EC2 M1 Mac 实例【索引3，Amazon EC2 G5 instance，2023】，配备 Apple M1 Ultra (Arm64) 处理器，macOS，128GB RAM 和 512 GB EBS 卷。

• 软件配置与基线:

  • 基线方法: HNSW【索引25，Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs，2018】、IVF、DiskANN【索引44，DiskANN: fast accurate billionpoint nearest neighbor search on a single node，2019】、IVF-Disk、IVF-Recompute【索引40，Edgerag: Online-indexed rag for edge devices，2024】、PQ 压缩【索引18，Product quantization for nearest neighbor search，2011】和 BM25【索引7，Ms marco: Benchmarking ranking models in the largedata regime，2021】。
  • 实现细节: 详细配置见附录 C.1。

A4 实验结果

存储消耗 (图3): 在所有方法中，只有LEANN和IVF-Recompute的总存储开销低于原始数据集大小（76 GB）的5%。大多数现有系统，如HNSW（188GB）和DiskANN（270GB），产生高达原始数据大小2.5倍的巨大开销，不适用于个人设备。PQ压缩虽然将向量压缩到5GB，但仍需15GB的图元数据。相比之下，LEANN仅存储一个紧凑的图（2GB）和高度压缩的PQ嵌入（2GB），总共4GB，开销极低。在各类个人数据集上，LEANN相比最常用的HNSW索引实现了超过97%的存储节省（表3）。

向量搜索与RAG延迟 (表2和表3): 实验表明，在RAG流程中，生成阶段的耗时（通常超过10秒）远超检索阶段，这证明了LEANN用少量检索延迟换取巨大存储节省的设计是合理的。在存储高效的方法中，只有LEANN兼具高速和高准确率。BM25和PQ无法达到90%的召回率，而IVF-Recompute虽然召回率高，但检索速度比LEANN慢两个数量级（最高慢200倍）。尽管LEANN的独立向量搜索延迟高于HNSW和DiskANN，但在完整的RAG流程中，它引入的端到端延迟开销通常低于20%，在推理密集的GPQA等任务上甚至低于3%。在Mac平台上的实验也得出了相同的结论，证明了LEANN的普适性（附录表4）。

下游RAG应用准确率 (图4): 在四个QA数据集上，LEANN在下游任务的准确率（Exact Match和F1分数）上达到了最高水平，与HNSW相当，并显著优于BM25和PQ。与BM25相比，EM分数最高提升11.8%，F1分数最高提升12.0%。这证实了LEANN在大幅节省存储的同时，成功地保持了SOTA的检索质量。

消融研究与微基准测试 (§7.3):

• 延迟优化技术 (图5): 与基线相比，两级搜索机制带来了平均1.4倍的加速，再结合动态批处理后，平均加速比达到1.8倍，峰值可达2.0倍。
• 图剪枝方法 (图6和图7): LEANN的高阶保留剪枝方法性能与原始HNSW图相当，但仅使用了一半的边（存储）。相比之下，随机剪枝和简单限制最大度数（Small M）的方法性能大幅下降，分别需要多达1.8倍和5.8倍的节点重计算才能达到相同的召回率。图7的度分布分析表明，只有LEANN的方法成功保留了高阶“枢纽”节点。
• 索引更新 (图8): 经过优化的LEANN添加操作比朴素方法快63.3倍。对于批量添加，使用缓冲区和延迟插入策略可以进一步提高搜索速度。

A5 结论

针对高维嵌入的相似性搜索是许多生成式AI应用（如RAG）的基础。然而，由于嵌入和索引元数据需要大量存储，实现这些功能仍然具有挑战性。我们提出了LEANN，一种基于图重计算的存储高效向量索引。通过将两级搜索与动态批处理相结合，LEANN支持高效的查询处理，而无需存储完整的嵌入集。一种保留高阶节点的剪枝策略进一步减少了图存储，同时保持了准确性。LEANN还提供了快速、存储高效的索引构建和更新流水线。综合这些技术，LEANN能够以小于原始数据大小5%的索引运行，与现有方法相比，存储减少高达50倍，同时保持高召回率和低延迟。

A6 附录

A RNG 剪枝

RNG剪枝规则。对于插入任何邻近图索引（包括HNSW）的节点v，算法首先搜索一个候选邻居列表a, b, c, d（见算法1），并按与v的距离排序。然后，在第6行实现的基于RNG的剪枝规则【索引16，Relative neighborhood graphs and their relatives，1992；索引48，The relative neighbourhood graph of a finite planar set，1980】会按距离递增的顺序遍历此列表。如果存在一个更近的邻居a，使得Dist(a, x) < Dist(v, x)，则候选节点x被剪枝。这实际上移除了由(v, a, x)形成的三角形中最长的边。如图9所示，边v-b和v-c被剪枝，因此从v到b或c的搜索会间接地通过a进行。这种剪枝策略在现代基于图的ANN索引中被广泛使用，并使得最终的图极其稀疏【索引28，Down with the hierarchy: The’h’in hnsw stands for” hubs”，2024；索引25，Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs，2018】。

B LEANN 更新策略

ADD算法在算法4中呈现。

B.1 添加操作：方法与时间复杂度

朴素实现。在LEANN中，ADD操作的朴素实现会从头重新计算所有距离，因为只存储了图结构。其总时间复杂度可以表示为：

$$O(M \cdot efC + efC^{2} + M^{3}),$$

其中$efC$是构建队列长度，$M$是最大节点度数。

复杂度分析。我们首先分析SHRINKNEIGHBORLIST的复杂度。每个被放入保留集 $R$ 的节点可能会被重新检查多达 $|W|$ 次，因此单次调用的成本为 $O(|W|^2)$。具体来说：
* SEARCHNEIGHBORSTOADD 执行一次性的邻居搜索，不重复访问节点，复杂度为 $O(M \cdot efC)$。缓存没有好处，因为节点不会被重访。
* SHRINKNEIGHBORLIST（第12行）的运行时间为 $O(efC^2)$，因为它在多达 $efC$ 个候选者之间计算成对距离。
* 添加前向边不需要重计算，因为每个节点最多维护 $M$ 个链接。
* 添加反向边的成本为 $O(M^3)$，因为最多有 $M$ 个邻居被更新，每次更新都会触发一个 $O(M^2)$ 的基于RNG的收缩操作。

缓存优化。为了提高效率，LEANN引入了一个距离缓存来消除SHRINK步骤中的冗余计算，将总体复杂度降低到：

$$O(M \cdot efC + efC + M^2),$$

因为收缩操作现在只需要 $O(|W|)$ 的成本。

简化的RNG剪枝。通过进一步简化SHRINKNEIGHBORLIST，改为随机选择邻居而不是执行完整的RNG检查，复杂度变为：

$O(M \cdot efC + M^{2})$.

最终优化。最后，将相同的简化应用于反向边更新步骤，得到了优化后的复杂度：

$$O(M \cdot efC)$$

这将成本从关于 $M$ 的三次方降低到线性，同时保持了相当的图连通性。

B.2 批量添加操作：优化

延迟插入。当一批添加操作之后紧跟着一个搜索请求时，LEANN不会立即插入所有新段落。相反，它会临时缓冲它们的嵌入，并将来自现有图和缓冲嵌入的搜索结果合并。搜索完成后，缓冲的段落会异步插入，我们称这个过程为延迟插入。

系统优化复用。之前描述的相同系统优化可以在这里重用，并增加一个全局缓存以避免跨多个添加请求的冗余计算。为了保持存储效率，LEANN会监控缓存大小，一旦达到预定义的预算就清除它，开始新一轮的批量插入。

B.3 软删除策略

实现方式。LEANN对图节点采用简单的软删除。每个节点保留一个二进制删除标志，因此移除是一个 $O(1)$ 的更新，不会触动邻接表。在查询处理期间，我们仍然会遍历被删除的节点以到达它们的邻居，但在产生结果之前，我们会根据此标志过滤候选队列（算法2中的EQ），然后取前k个活动条目以保证正确性。

后台重建。如果被删除节点的比例超过一个阈值（例如5%），我们可以触发后台重建。探索这类策略留待未来工作。

1: 输入：现有图G；构建队列长度efC；最大度数M；要插入的节点v
2: 输出：包含节点v的更新后的图G
3: function SHRINK(W, M)
4:   初始化R
5:   for x in W (按与查询q的距离升序) do
6:     if 不存在y ∈ R 使得 Dist(x, y) < Dist(x, q) then
7:       将x添加到R
8:       if |R| = M then
9:         break
10:  return R
11: W ← SEARCH(v, efC) ▷ 见算法1
12: W ← SHRINK(W, M) ▷ ShrinkNeighborList
13: 添加从v到W中所有节点的有向边
14: for 每个w ∈ W do
15:   添加从w到v的有向边
16:   if deg(w) > M then
17:     SHRINK(w的邻居列表, M)

C 评估细节

C.1 基线配置

• HNSW (Malkov & Yashunin, 2018): 我们使用 faiss.IndexHNSWFlat 实现，构建参数遵循FAISS的建议：M=30，efConstruction=128，这与搜索时参数 ef 不同。
• IVF (Lempitsky, 2012): 我们采用 faiss.IndexIVFFlat 实现。根据FAISS的最佳实践【索引37，Guidelines to choose an index，2025】和先前的工作【索引13，Private web search with tiptoe，2023】，我们将质心数量设置为 $\sqrt{N}$，其中 N 是数据存储的大小。对于我们的 N=60M 设置，这对应于 nlist=8192。
• DiskANN (Subramanya et al., 2019): 我们使用 DiskANN，参数为 M=60 和 efConstruction=128，遵循推荐设置【索引44，DiskANN: fast accurate billionpoint nearest neighbor search on a single node，2019】。它只在内存中存储一个 PQ 表，并按需从磁盘加载完整的嵌入。
• IVF-Disk: 通过使用内存映射文件（mmap）而不是将整个索引加载到内存中来减少内存使用。使用FAISS的 faiss.contrib.ondisk 模块实现，参数与IVF相同。
• IVF-Recompute (Seemakhupt et al., 2024): 受Edge-RAG启发，这个变体在查询时重新计算嵌入而不是存储它们，使用与IVF相同的构建参数。
• PQ Compression (Jegou et al., 2011): 应用乘积量化来压缩存储的嵌入，同时保留图结构。为公平比较，我们将向量压缩到5 GB——略大于我们系统的4 GB占用空间。我们使用来自【索引44，DiskANN: fast accurate billionpoint nearest neighbor search on a single node，2019】的PQ实现。
• BM25 (Craswell et al., 2021; Rekabsaz et al., 2021): 一种经典的词汇排名方法，广泛用于基于关键字的检索系统。我们采用Pyserini【索引23，Pyserini: A Python toolkit for reproducible information retrieval research with sparse and dense representations，2021】的标准实现。

C.2 延迟测量和评估协议

检索准确率。为了评估检索准确性，我们报告了§2中定义的Recall@k。在开放领域设置中，检索到的段落的真实标签通常是不可用的。遵循标准实践【索引18，Product quantization for nearest neighbor search，2011；索引39，Laion-400m: Open dataset of clipfiltered 400 million image-text pairs，2021；索引59，Compass: Encrypted semantic search with high accuracy，2024】，我们将精确搜索的结果作为真实值的代理。在所有实验中，我们设置k=3，与先前的工作【索引42，Scaling retrievalbased language models with a trillion-token datastore，2024；索引1，Selfrag: Learning to retrieve, generate, and critique through self-reflection，2023】一致，并报告Recall@3作为我们的检索准确性指标。

延迟评估。对于延迟评估，我们测量达到不同目标召回率水平所需的时间。具体来说，我们执行二分搜索来找到达到所需召回率的最小搜索队列长度 ef（如算法1中定义）。使用得到的 ef，我们记录20个随机查询的平均检索延迟。

C.3 RAG流水线中的延迟测量

评估设置。我们在所有数据集上评估LEANN在90%召回率水平下的延迟。对于文本生成，我们使用Qwen3-4B【索引52，Qwen3 technical report，2025】，对于多模态工作负载，我们使用Qwen2.5-VL-7B-Instruct【索引4，Qwen2. 5-vl technical report，2025】。嵌入和生成模型都使用Hugging Face框架实现。

C.4 Mac平台上的RAG延迟

跨平台验证。为了验证我们结果在不同硬件平台上的普适性，我们在Mac硬件上进行了额外的实验。表4展示了在Mac上的向量搜索和端到端RAG延迟测量，遵循与主论文中RTX 4090结果相同的实验协议。结果表明，尽管底层架构和计算特性不同，LEANN在Mac硬件上仍保持其效率优势，与其他方法相比，检索开销仍然很低。

D 更多消融研究

D.1 索引构建的比较

评估方法。我们评估了在§6中介绍的存储高效索引构建技术，并将其与标准的HNSW构建方法进行比较。具体来说，我们实现了所提出的分片合并流水线方法的两个变体：（1）一种基于k-means的方法（见§6），在分片前将相似的段落分组，以及（2）一种省略聚类的随机分配基线。我们使用与之前相同的方法评估图的质量，结果如图10所示。在此设置中，数据集被划分为15个分片，在索引构建期间实现了约5倍的峰值存储使用减少。

结果分析。基于k-means分片的图实现了与原始HNSW几乎相同的召回率，而重计算成本仅有少量增加，这表明它在分片和合并后保持了强大的连通性。相比之下，随机分片的图需要更多的重计算才能达到相同的召回率。这些结果突显了在分片前聚类相似段落的好处，验证了我们分片合并流水线方法的设计。

D.2 使用不同大小的嵌入模型

动机与设置。由于我们系统的主要瓶颈在于重计算过程，我们通过采用一个更小的嵌入模型来进一步探索延迟降低的潜力。具体来说，我们将§7.1中使用的原始Contriever模型（1.1亿参数）替换为轻量级的GTE-small模型【索引22，Towards general text embeddings with multi-stage contrastive learning，2023】（仅3400万参数）。我们在一个包含200万文档的数据存储上，使用固定的搜索队列长度ef=50来评估性能。

结果。如图11所示，GTE-small实现了2.3倍的加速，同时下游任务准确率与Contriever基线相比保持在2%以内，这表明LEANN可以通过利用更轻量的编码器来进一步降低延迟，而不会牺牲答案质量。

D.3 放宽磁盘约束

缓存高阶节点。当磁盘存储约束放宽时，LEANN可以物化高阶节点的嵌入以减少重计算开销。图12量化了在改变缓存嵌入比例时，四个数据集上由此带来的延迟改进和缓存命中率。

性能提升。仅存储10%的原始嵌入就带来了1.5倍的加速，缓存命中率高达41.9%。这种高缓存命中率源于基于图的遍历所特有的偏斜访问模式，尽管SSD加载开销使得延迟增益无法与命中率完全匹配。

D.4 基于图的重计算分解

延迟分析。图13将一批查询的延迟分解为三个阶段：PQ查找、文本处理和嵌入重计算。每个批次聚合了多次重计算的跳数，如§4.2所述。首先，LEANN执行PQ查找以选择有希望的节点，然后检索并对相应的原始文本进行分词。分词后的输入被发送到本地嵌入生成器。最后，LEANN执行嵌入重计算和距离计算。

瓶颈与优化机会。尽管嵌入重计算是LEANN的主要瓶颈，约占总延迟的76%，但这三个阶段跨越了I/O、CPU和GPU资源，表明存在重叠工作并进一步提高效率的机会。