在个人设备上部署检索增强生成（RAG）系统面临一个根本性挑战：向量索引的存储开销。传统向量数据库如 FAISS 需要存储所有高维嵌入向量，导致索引大小通常是原始数据的 1.5 到 7 倍。这意味着索引 100GB 原始数据需要 150-700GB 存储空间，这在存储受限的个人设备上完全不切实际。
LEANN（Low-Storage Vector Index）通过革命性的存储压缩技术解决了这一难题，实现了97% 的存储节省，将索引大小压缩到原始数据的5% 以下。本文将深入解析 LEANN 实现这一惊人压缩比的核心技术，包括基于图的选择性重计算、高阶保持图剪枝、两级搜索算法等关键工程实现。
存储压缩的核心挑战与 LEANN 的解决方案
传统向量索引的存储开销主要来自两个方面：嵌入向量本身和索引元数据。以 HNSW（Hierarchical Navigable Small World）为例，每个节点需要存储 768 维的嵌入向量（约 3KB）和 64 个邻居链接（256 字节）。对于 6000 万文档的数据集，仅嵌入向量就需要约 201GB 存储空间。
LEANN 的核心洞察是：在基于图的近似最近邻搜索中，单个查询通常只探索图中一小部分节点。因此，与其存储所有嵌入向量，不如在搜索时按需重新计算。这一看似简单的想法面临两个关键挑战：
- 重计算延迟：按需计算嵌入向量会显著增加搜索延迟
- 图元数据存储：即使不存储嵌入向量，图结构本身仍有可观的存储开销
LEANN 通过三个核心技术解决了这些挑战：
- 基于图的选择性重计算：只在搜索路径上重新计算嵌入向量
- 高阶保持图剪枝：压缩图结构同时保留关键连接性
- 两级搜索与动态批处理：优化重计算效率
基于图的选择性重计算机制
重计算的基本原理
LEANN 建立在 HNSW 图结构之上，但有一个根本区别：构建索引后丢弃所有嵌入向量，只保留图结构和原始文本数据。在搜索时，系统沿着图遍历，当需要评估某个节点的相似度时，才重新计算其嵌入向量。
这一机制的关键在于理解图搜索的局部性。在最佳优先搜索（BFS）算法中，查询从入口节点开始，逐步探索最有可能的邻居。研究表明，单个查询通常只访问图中 **0.1%-1%** 的节点。这意味着 97%-99% 的嵌入向量在单次查询中根本不需要。
重计算延迟的数学建模
重计算延迟可以形式化为以下优化问题：
最小化 T = Σ_{i=1}^{ef} |D_i| / Throughput
约束条件：存储空间 = Σ_{i=1}^{n} |D_i| × Dtype < C
其中：
T是搜索延迟ef是搜索队列长度D_i是节点 i 的度数Throughput是嵌入服务器的处理吞吐量C是存储预算Dtype是连接数据类型大小（通常为 4 字节）
这个公式揭示了 LEANN 的设计哲学：在给定存储预算下，最小化需要重计算的节点数量。
高阶保持图剪枝：压缩图元数据
图存储开销分析
即使不存储嵌入向量，图元数据本身也有显著存储开销。在典型的 HNSW 配置中，每个节点有 64 个邻居链接，每个链接 4 字节，每个节点需要 256 字节元数据。对于 256 个 token 的文档块，这相当于25% 的存储开销。
LEANN 观察到图连接性存在高度冗余：并非所有节点和边对搜索质量都有同等贡献。特别是，高度数节点（"枢纽" 节点）在维持图可导航性方面起着关键作用。
高阶保持剪枝算法
LEANN 的高阶保持剪枝算法（Algorithm 3）采用差异化度阈值策略：
def high_degree_preserving_pruning(G, ef, M, m, a):
# G: 原始图，ef: 候选列表大小
# M: 高阶节点的最大连接数，m: 普通节点的最大连接数
# a: 高阶节点百分比
# 计算所有节点的出度
degrees = {v: out_degree(v) for v in G.nodes()}
# 选择前a%的高阶节点
high_degree_nodes = sorted(degrees.items(),
key=lambda x: x[1],
reverse=True)[:int(len(G)*a/100)]
pruned_graph = empty_graph()
for v in G.nodes():
# 搜索v的ef个最近邻居
candidates = search(v, ef)
if v in high_degree_nodes:
max_connections = M
else:
max_connections = m
# 选择最多max_connections个邻居
selected_neighbors = select_neighbors(candidates, max_connections)
# 添加双向边
for neighbor in selected_neighbors:
add_bidirectional_edge(pruned_graph, v, neighbor)
# 如果邻居出度超过M，收缩边
if out_degree(neighbor) > M:
shrink_edges(neighbor, M)
return pruned_graph
该算法的关键创新点：
- 差异化度阈值：普通节点最多连接
m个邻居，高阶节点最多连接M个邻居（m < M） - 双向边建立：所有节点都可以与高阶节点建立连接，不受
m限制 - 边收缩机制：防止高阶节点过度连接
实验表明，仅保留前 2% 的高阶节点，同时将总边数减少 50%，就能维持接近原始图的搜索质量。
节点访问模式分析
LEANN 的剪枝策略基于对节点访问模式的深入分析。研究发现，在基于图的搜索中，节点访问概率呈现高度偏斜分布：
- 高阶节点：访问频率高，是图导航的关键枢纽
- 普通节点：访问频率低，主要作为搜索结果返回
这种偏斜分布使得选择性保留高阶节点成为可能，同时大幅减少普通节点的连接数。
两级搜索算法：减少重计算节点
算法设计原理
即使采用图剪枝，重计算仍然是主要延迟来源（占 76%）。为了进一步减少重计算节点数量，LEANN 引入了两级搜索算法（Algorithm 2）。
传统的最佳优先搜索在探索每个节点的邻居时，需要计算所有邻居的精确距离。两级搜索的核心思想是：使用近似距离进行初步筛选，只对最有希望的候选者计算精确距离。
两级搜索实现细节
def two_level_search(q, p, a, k, ef):
# q: 查询向量，p: 入口点
# a: 重排序比例，k: 返回结果数，ef: 搜索队列长度
visited = {p}
AQ = MinPriorityQueue() # 近似队列，存储近似距离
EQ = MinPriorityQueue() # 精确队列，存储精确距离
R = MinPriorityQueue() # 结果队列
EQ.push(p, exact_distance(p, q))
R.push(p, exact_distance(p, q))
while not EQ.empty():
v = EQ.pop_min() # 当前扩展节点
# 终止条件检查
if distance(v, q) > max_distance_in_R(R, q):
break
# 探索邻居
for neighbor in neighbors(v):
if neighbor not in visited:
visited.add(neighbor)
# 计算近似距离（使用PQ压缩）
approx_dist = approximate_distance(neighbor, q)
AQ.push(neighbor, approx_dist)
# 选择前a%的候选者进行精确计算
M = select_top_percentage(AQ, a, exclude=EQ)
for m in M:
# 精确重计算
exact_dist = recompute_embedding_and_distance(m, q)
EQ.push(m, exact_dist)
R.push(m, exact_dist)
# 保持结果队列大小
if len(R) > ef:
R.pop_max()
return top_k(R, k)
近似距离计算优化
两级搜索中的近似距离计算使用产品量化（Product Quantization, PQ）技术：
- PQ 压缩：将 768 维嵌入向量压缩到 2GB 空间（相比原始 200GB）
- 快速距离估计：使用 PQ 码本进行近似距离计算，避免完整重计算
- 重排序比例：参数
a控制精确计算的比例，典型值为 10%-20%
这种混合距离计算策略实现了1.40 倍的平均加速，最高达到 1.64 倍。
动态批处理：最大化 GPU 利用率
GPU 利用率挑战
即使采用两级搜索，重计算仍然是瓶颈。问题在于：每个扩展步骤只触发少量节点的重计算（通常等于当前节点的度数），这无法充分利用 GPU 的并行计算能力。
动态批处理机制
LEANN 通过动态批处理策略解决了这一问题：
def dynamic_batching_search(q, p, batch_size=64):
visited = {p}
EQ = MinPriorityQueue()
R = MinPriorityQueue()
batch_candidates = []
EQ.push(p, exact_distance(p, q))
R.push(p, exact_distance(p, q))
while not EQ.empty():
v = EQ.pop_min()
# 收集批处理候选者
for neighbor in neighbors(v):
if neighbor not in visited:
visited.add(neighbor)
batch_candidates.append(neighbor)
# 当达到批处理大小时执行重计算
if len(batch_candidates) >= batch_size or EQ.empty():
# 批量重计算
batch_results = batch_recompute(batch_candidates, q)
for node, dist in batch_results:
EQ.push(node, dist)
R.push(node, dist)
batch_candidates = []
return top_k(R, k)
批处理大小优化
批处理大小的选择至关重要：
- 太小：GPU 利用率不足
- 太大：引入搜索顺序的 "陈旧性"，可能影响搜索质量
LEANN 通过轻量级离线分析确定最优批处理大小：
- A10 GPU：64-128 个节点
- M1 Mac：32-64 个节点
动态批处理将整体加速提升到1.76 倍，最高达到 2.02 倍。
工程实现参数与监控要点
关键配置参数
在实际部署 LEANN 时，需要优化以下参数：
-
图构建参数：
M：高阶节点最大连接数（默认：32-64）m：普通节点最大连接数（默认：16-32）a：高阶节点百分比（默认：2%）efConstruction：构建时的搜索复杂度（默认：128）
-
搜索参数：
ef：搜索队列长度（默认：32-64）re_ranking_ratio：重排序比例（默认：10%-20%）batch_size：动态批处理大小（GPU 相关）
-
存储参数：
storage_budget：存储预算（相对于原始数据大小）cache_size：嵌入缓存大小（如果磁盘空间允许）
性能监控指标
部署 LEANN 系统时，应监控以下关键指标：
-
存储效率：
存储节省率 = 1 - (索引大小 / 原始数据大小) 目标：> 95% -
搜索性能：
重计算比例 = 重计算节点数 / 总访问节点数 目标：< 30% GPU利用率 = GPU活跃时间 / 总搜索时间 目标：> 70% -
质量指标：
Recall@k：前k个结果的召回率 目标：> 90% (k=3) 下游任务准确率：RAG应用的最终输出质量
缓存策略优化
当磁盘空间允许时，LEANN 可以缓存高阶节点的嵌入向量：
- 选择性缓存：仅缓存前 10% 的高阶节点嵌入
- 缓存命中率：实验显示可达 41.9%
- 性能提升：缓存 10% 嵌入带来 1.47 倍加速
缓存策略需要在存储开销和性能提升之间权衡：
- 10% 缓存：1.47 倍加速，额外 10% 存储
- 20% 缓存：1.68 倍加速，额外 20% 存储
实际应用场景与性能数据
存储节省对比
LEANN 在不同应用场景下的存储节省效果：
| 系统 | DPR (2.1M) | Wiki (60M) | 聊天记录 (400K) | 邮件 (780K) | 浏览器历史 (38K) |
|---|---|---|---|---|---|
| 传统向量数据库 | 3.8 GB | 201 GB | 1.8 GB | 2.4 GB | 130 MB |
| LEANN | 324 MB | 6 GB | 64 MB | 79 MB | 6.4 MB |
| 节省率 | 91% | 97% | 97% | 97% | 95% |
搜索延迟性能
在四个标准基准测试（NQ、HotpotQA、TriviaQA、GPQA）上的性能：
-
A10 GPU 工作站：
- 90% Recall@3：< 2 秒
- 相比 Edge-RAG：21.17× 到 200.60× 加速
-
M1 Mac：
- 90% Recall@3：< 4 秒
- 相比 A10：2.28× 到 3.01× 延迟增加
下游任务准确率
使用 Llama-3.2-1B 作为生成模型的 RAG 任务准确率：
| 数据集 | LEANN (90% 召回) | BM25 | PQ 压缩 |
|---|---|---|---|
| NQ | 45.2% EM | 28.7% EM | 22.1% EM |
| TriviaQA | 68.3% EM | 52.4% EM | 46.7% EM |
| HotpotQA | 32.1% EM | 25.8% EM | 21.3% EM |
| GPQA | 18.7% EM | 16.2% EM | 14.9% EM |
技术局限性与未来方向
当前局限性
- 索引构建峰值存储：构建时需要一次性计算所有嵌入向量，峰值存储使用较高
- 重计算瓶颈：重计算占搜索延迟的 76%，是主要性能瓶颈
- GPU 依赖：需要 GPU 支持以获得最佳性能
优化方向
- 增量索引构建：分块构建索引，减少峰值内存使用
- 更轻量嵌入模型：使用 GTE-small（34M 参数）替代 Contriever（110M 参数），实现 2.3× 加速
- 硬件特定优化：针对不同 GPU 架构优化批处理策略
扩展应用
LEANN 的技术原理可扩展到其他场景：
- 多模态检索：图像、视频的压缩向量索引
- 联邦学习：隐私保护的分布式向量搜索
- 边缘计算：资源受限设备的智能检索
总结
LEANN 通过基于图的选择性重计算、高阶保持图剪枝、两级搜索和动态批处理等创新技术，实现了 97% 的存储节省，将向量索引大小压缩到原始数据的 5% 以下。这一突破使得在个人设备上部署大规模 RAG 系统成为可能，为隐私保护、低延迟的个性化 AI 应用开辟了新道路。
关键技术要点总结：
- 选择性重计算：只在搜索路径上重新计算嵌入向量，利用搜索局部性
- 高阶节点保留：差异化剪枝策略，保留关键的图导航枢纽
- 混合距离计算：PQ 近似距离筛选 + 精确距离重排序，减少重计算量
- 动态 GPU 批处理：最大化硬件利用率，降低重计算延迟
随着消费级 GPU 性能的持续提升和轻量级嵌入模型的发展，LEANN 的延迟将进一步降低，使其在更广泛的边缘计算场景中发挥重要作用。
资料来源：
- LEANN 论文：https://arxiv.org/abs/2506.08276
- GitHub 仓库：https://github.com/yichuan-w/LEANN