PILLAR：面向增强检索的私有倒排索引词法查找

如何在服务器持有公开语料时，让客户端取回与私有查询最相似的 k 篇文档，而服务器既看不到查询词项也看不到访问模式，同时避免纯稠密私有检索的多轮 PIR 与质量损失。

• 场景与风险：作者称 RAG 已是把大语言模型接地到参数外知识的标准做法，也是主要搜索引擎做 AI 摘要的机制。客户端查询被原样交给托管语料的服务器。作者援引搜索日志可识别用户、用户向 LLM 披露敏感细节、以及现有模型能从很少文本推断可识别信息，称暴露查询有实际风险。
• 现有 PPRAG 的两点不足：作者称既有工作分稠密与稀疏两类，多数做稠密。ANN 遍历是自适应的，每跳依赖查询，隐藏访问模式必须用与查询无关的固定日程。作者称在 MS MARCO 上 PACMANN 每查询要 20 次往返，MRR@10 仅 0.266，而同一嵌入上的非私有 ANN 基线约为 0.31。其次，既有协议只支持单一检索架构，而作者称真实 RAG 常用词法评分后再比较嵌入相似度；两类方法失败方式互补，合用才能互相弥补。
• 核心观察：作者指出文献缺口是：没有 PPRAG 同时使用稀疏与稠密架构，而单架构方案在交互次数和答案质量上付出代价。混合协议应同时具备稀疏检索的低且固定轮次、用词法重叠快速排除文档、以及稠密嵌入的语义精度。
• 本文提出什么：作者提出 PILLAR，一种基于 PIR 的隐私混合检索 PPRAG。稀疏段对预计算 BM25 分数索引发少量、次数固定的 PIR，把语料滤到与查询共词的候选；稠密段只取这些候选的文档嵌入并在客户端重排。两个协议：PILLAR-Bin（哈希装箱、单轮、作者称延迟低于 SOTA）与 PILLAR-Tree（把 block-max 剪枝变成不经意树遍历加 cuckoo 哈希表，作者称质量最高且延迟低于 SOTA）。作者称二者在 PIR-hybrid model 下对半诚实服务器隐藏查询，并称这是结合词法与语义打分的 PPRAG。
• 威胁模型：
  • 目标：理想功能 PPRAG(C, Q) = (⊥, Dk)。服务器对公开语料 C 输出空；客户端输入私有查询 Q，输出 k 篇文档 Dk，使 Dk 中每篇相对语料其余文档的 score(Q, ·) 都不更低。
  • 知识与对手：语料公开且服务器已知。采用带预处理的单服务器 PIR。服务器为 semi-honest：遵守协议但试图恢复被请求的索引。作者称在 PIR-hybrid model 下证明两种协议隐藏查询。
  • 能力：客户端不把查询词项交给服务器，而是对索引发 PIR；轮数和每条消息大小只依赖公开参数，不依赖 Q。客户端本地做词法上界求和与余弦重排。
  • 受害系统：托管公开文档语料、向客户端提供检索以增强 LLM 回答的 RAG 服务器。

PIR 与私有检索

• PIR（Chor et al., 1995；Kushilevitz and Ostrovsky, 1997；Beimel et al., 2000）：客户端从不加密数据库取一条记录而不揭示取的是哪一条。本文关注带预处理的单服务器 PIR（Zhou et al., 2024a；Corrigan-Gibbs and Kogan, 2020；Beimel et al., 2000），含预处理与查询两阶段。
• 批处理 PIR：作者沿用 Zhou et al. (2024b)，把多个索引打进一次查询，摊销到每个索引为次线性代价。

稠密 PPRAG

• Tiptoe（Henzinger et al., 2023）：在聚类嵌入上做私有搜索。
• Compass（Zhu et al., 2025）：用 ORAM 遍历 HNSW 图。
• PACMANN（Zhou et al., 2024b）：作者称为当前 SOTA。客户端遍历 ANN 图。作者批评其遍历自适应，在 MS MARCO 上每查询 20 次往返且 MRR@10 为 0.266，低于同一嵌入上非私有 ANN 的约 0.31；且只做检索评测、未评端到端答案。

稀疏检索与混合检索

• Coeus（Ahmad et al., 2021）：作者称为稀疏私有检索的代表，把查询对词频矩阵打分。词法打分函数还包括 TF-IDF、Okapi BM25（Robertson and Zaragoza, 2009）和 SPLADE（Formal et al., 2021）。Block-max / 动态剪枝来自 Turtle and Flood (1995)、Broder et al. (2003)、Ding and Suel (2011)。
• 稠密检索基础：DPR（Karpukhin et al., 2020）把文档和查询映到向量空间，常用余弦相似度；ANN 把语料建成高相似度图再遍历（亦见 Malkov and Yashunin, 2018）。作者引 Ma et al. (2021)、Thakur et al. (2021b)、Bruch et al. (2023) 说明嵌入与词法失败方式互补。
• 工程中的混合检索（附录 I.2）：Elasticsearch、OpenSearch、Weaviate、Azure AI Search 把 BM25 与向量检索融合（含 RRF，Cormack et al., 2009）。作者引 Microsoft 白皮书称混合检索加重排在其生产 RAG 中是基本配置；Anthropic 的 Contextual Retrieval 把嵌入与 BM25 合用，top-20 检索失败率从 3.7% 降到 2.9%。作者写明这些来源说明混合检索被广泛支持和推荐，并不是已部署系统的普查。

基线方法与基准

• 基线：PACMANN，多轮私有 ANN 遍历。非私有对照仅在引言中以同一嵌入上的 ANN 基线（MRR@10 约 0.31）出现。
• 基准：MS MARCO（Bajaj et al., 2018）与 SciFact（Wadden et al., 2020）。检索质量用 BEIR 常用的 MRR@10、Recall@10（Thakur et al., 2021a）；端到端用 RAGAS 的 Faithfulness 与 Answer Relevancy（Es et al., 2025）。配置筛选用 Kneedle（Satopaa et al., 2011）。

作者把本文定位为同时使用词法与语义打分的 PPRAG：稀疏段固定轮次筛候选，稠密重排完全在客户端，从而同时压低交互次数并提高相对单架构私有检索的质量。

PILLAR 去掉一切自适应成分：轮数和消息大小只取决于公开参数。服务器侧先做粗糙的词法筛选，客户端再取候选嵌入，用余弦相似度本地重排。两个实例化对应两种私有词法检索。

问题设定

• 对象：语料 C = {D1, …, Dn}。Analyze 把原文变成词项，词表 V 为语料中全部唯一词项。Emb 把原文映到 d 维向量；文档嵌入 eD、查询嵌入 eQ。相似度由 score(·, ·) 给出。
• 理想功能：PPRAG(C, Q) = (⊥, Dk)，仅客户端得到 k 篇最高分文档。标准 PIR 只按索引取单篇，不能直接当 PPRAG，因为客户端输入是查询词项而非索引。
• 安全：PIR 安全指服务器发现不了被请求索引 i。作者称完整协议在附录 E，安全性分析在附录 G，并称在 PIR-hybrid model 下两种协议都隐藏查询。

PILLAR-Bin：单轮哈希装箱

• 要解决的两点：非私有 bin-based BM25 由服务器按查询取 posting list 并返回 top-k，但 PPRAG 中服务器看不到 Q；哈希表越大碰撞越少，但 PIR 计算复杂度随表规模超线性增长。
• 设计：服务器对每个词只返回固定 t 篇，由客户端本地重排。posting list 按该哈希词的词频排序，返回频率最高的 t 篇。表只有 R ≪ |C| 行，词 w 映到行 H(w) (mod R)，H 公开，PIR 隐藏行号。碰撞词的 posting list 用 round-robin 交错，第 i 条表的第 j 篇放在位置 (j−1)m + i（m 为碰撞词数），读前 t·m 个位置即各表的前 t 篇；跨表重复文档由服务器去掉。
• 记录内容与批处理：建表前服务器算好每篇文档的嵌入并直接存嵌入。PIR 库有 R 行，每行恰好 t 个嵌入、即 t·d 个域元素，行长与碰撞数无关。多次独立 PIR 会暴露 |Q|，因此用 batched PIR，批大小固定为填充上界 3，而不是 |Q|。客户端一次批查询，解码每行 t 个嵌入，候选池 Dcand 至多 t 乘批大小，去掉重复。协议一轮，消息大小依赖 R、t、d 和批上界。Table 1 中另有参数 emb：直接取嵌入，或用两轮 PIR。

PILLAR-Tree：束搜索与子块精炼

• 树：叶子是文档块，内部节点是子树对应的 super-block。每节点存 |V| 项，第 i 项是词 i 在该 super-block 上的最大词法分。树为 r 叉，以降低高度。束宽 W 的 beam search（Bisiani, 1987）：下一层只看当前最高分 W 个节点的孩子，每层至多考察 W×r 个候选，对每个候选把查询词的上界相加，保留该层最高的 W 个。作者注明束搜索是启发式，不保证找到真正的 top-k 块。下降 ⌈log_r(|C|/|B|)⌉ 层，上界数组读取量为 O(W · r · |Q| · log_r(|C|/|B|))，相对线性扫描块的 |Q|·|C|/|B|。
• 阈值放在客户端：每一层客户端用 PIR 取已确定候选的数组项，本地求和得到上界，再决定下一层候选。底层存的是块内嵌入的标识而非嵌入本身，再多一轮 PIR 取嵌入，然后客户端做稠密检索。Figure 2 分三阶段：Stage 1 每层一轮 PIR 直到 W 个叶块；Stage 2 取这些叶块的子块上界，选出 top ks 个子块并得到嵌入标识；Stage 3 PIR 取嵌入，客户端按 cos(eQ, eD) 排，输出 top-k 文档标识。
• 四项优化：预处理时把语料聚类，使每块内文档彼此相似。每个 PIR 项存的是词 w 相对节点 B 的 r 个孩子的分数，而不是相对 B 本身，从而把 |Q|Wr 次、库大小为 |V|×r^{ℓ+1} 的查询，降成 |Q|W 次、库大小为 |V|×r^ℓ。叶块再分成每块 s 篇的子块，分支因子 r⋆ = ⌈|B|/s⌉；树遍历滤到 W×|B| 篇后，精炼层只留 top ks 个子块，嵌入获取从 |B|×W 降到 ks×s。每层 PIR 库用 cuckoo 哈希表只存非零上界，用 m 次 PIR 换存储和 PIR 代价下降（附录 H）。参数 r、|B|、s、W 的作用在附录 D.1 讨论。

成功判定与端到端

• 检索：理想功能要求返回的 k 篇在 score 下不低于语料中其余文档。实验里稀疏段用预计算 BM25，稠密段用余弦。作者在脚注中区分：通常 hybrid-retrieval 指把稠密分与稀疏分合成最终分数；本文的 hybrid 只指检索方法，不指最终分数合成。
• 答案：检索出的文档交给 LLM 生成回答，再用 RAGAS 的 Faithfulness（回答中的断言是否被检索文档支持）和 Answer Relevancy（LLM 是否回答了问题，不论正确文档是否在内）打分。
• 安全声称：作者称两种协议在 PIR-hybrid model 下对半诚实服务器隐藏查询的词项与访问模式；通信模式固定，不随 Q 变化。

实验设置

• 协议与实现：Go 实现 PILLAR-Bin 与 PILLAR-Tree，对照 PACMANN（多轮私有 ANN）。三者都做超参网格（Table 1）。Bin：R（哈希表行数）、t（每 bin 文档数）、emb（直接取嵌入或两轮 PIR）。Tree：r、|B|、s、W。PACMANN：p（ANN 步数）、n（每步邻居数）。每种协议用 Kneedle 从 Pareto 前沿选五个代表配置：最低代价 C1、归一化收益相对归一化代价最大的 C2、最高 MRR@10 的 C3、最高 Recall@10 的 C4、最高代价 C5。收益是先做 min-max 归一化的 MRR@10 与 Recall@10 的均值。代价代理为每查询 WAN 延迟。附录 D 含全部配置，以及 LAN 延迟、计算时间和总发送数据等其他代价。
• 数据：MS MARCO passage retrieval，880 万段落、6980 条查询，开放域、精确词重叠对相似度较弱。SciFact，5183 篇文档、300 条查询，科学主张、稀有术语，词法打分更强。嵌入均为 192 维：SciFact 用 e5-base-v2；MS MARCO 用 msmarco-MiniLM-L-6-v3（Sentence-BERT bi-encoder，基于 MiniLM，在 MS MARCO 上微调），作者称与 PACMANN 相同以便公平比较。
• 机器与网络：检索在 Debian 12 容器、64 核 128 线程 AMD EPYC Zen 2 上跑，每进程限 15 线程。每配置 120 GB 内存；Bin 中把嵌入库放内存且每行超过 1.5K 篇的配置用 1 TB 内存机器。WAN：RTT 50 ms、带宽 400 Mbps。LAN（附录 D）：1000 Mbps、RTT 5 ms。
• 端到端：选出的配置所检索文档交给 Qwen2.5-7B-Instruct。RAGAS 评审模型为 Llama-3-70B。LLM 实验在单张 NVIDIA A100（80GB）上，RAGAS 阶段每数据集固定 100 条查询。
• 指标：Recall@10（正确文档是否在 top 10）、MRR@10（正确文档是否靠前）。Faithfulness、Answer Relevancy 定义见设置。作者称 PACMANN 原文只报 MRR 与 Recall，本文额外报 RAGAS，因为 MRR/Recall 看不出检索上下文对 LLM 是否有用。正文未写 MRR/Recall 的查询级样本量是否用完全部 6980/300 条，只写明 RAGAS 为每数据集 100 条。论文未报告重复次数。
• Figure 1 / Figure 3：Figure 1 是 MS MARCO 上各方法 Top-5 配置的 Pareto，横轴 Latency (s)，纵轴 Relevancy，标注约 0.54–0.78。Figure 3 对两数据集各画 MRR@10、Recall@10、Relevancy、Faithfulness 对 WAN 延迟；黑线为 Pareto 前沿，不在前沿上的点略透明。正文给出的可读数字如下，图中未逐点标出的配置不填。

主结果

Swipe horizontally to read the table

协议	数据集	延迟	质量	出处
PILLAR-Bin 最快	MS MARCO	0.098 s（top-10）	作者称与 PACMANN 质量相当，未给该配置的 MRR	§5.2、引言
PILLAR-Bin 最快	SciFact	0.065 s（top-10）	未报告该点的具体 MRR/Recall	§5.2
PACMANN 最快	MS MARCO	0.293 s	未报告该配置的 MRR；引言另称 PACMANN 为 0.266 MRR@10、20 次往返	§5.2、§1
PACMANN 最快	SciFact	0.270 s	未报告	§5.2
PILLAR-Tree 最高质量配置	作者称“最佳配置中最高质量文档”	作者称对应 PACMANN 延迟超过其 2 倍	answer Relevancy 0.75；该 PACMANN 配置为 0.72	引言
PILLAR-Tree C5 / 最低延迟配置	MS MARCO	C5 为最高延迟	MRR 0.318 对 0.248（作者称 +28%）	§5.2、Figure 4b

• 前沿归属：作者称 Figure 1 的 Top-5 前沿上只有 PILLAR-Bin 或 PILLAR-Tree，PACMANN 在延迟或 Relevancy 上都不更好。对 Figure 3 的全部实验，作者称 Pareto 前沿上 93% 的点来自 PILLAR，7% 来自 PACMANN；用来画 Figure 3 的配置中 54% 是 PILLAR-Tree。
• 速度：作者称没有落在前沿上、且在任一数据集上低于 0.1 s 的 PACMANN 配置，而 PILLAR-Bin 有多个；最快 PACMANN 相对上述 Bin 延迟为 3× 到 4×。结论中作者称 Bin 总有更快的配置，回答查询比 PACMANN 所允许的任一配置快三倍。Tree 很少达到 Bin 的延迟，因为遍历需要 ⌈log_r(|C|/|B|)⌉ 轮。
• 质量：作者称 Figure 3 前沿上、运行时间低于 1.0 s 的全部配置中，PILLAR-Tree 在两个数据集、全部指标上质量最高。引言中最高 answer Relevancy 为 PILLAR-Tree 的 0.75，找到最好文档的 PACMANN 配置为 0.72，但延迟超过 2×。Figure 3 纵轴刻度包括 MS MARCO 上 MRR@10 约 0.12–0.36、Recall@10 约 0.2–0.6、Relevancy 约 0.54–0.78、Faithfulness 约 0.80–0.96，以及 SciFact 上 MRR@10 约 0.52–0.68、Recall@10 约 0.65–0.85、Relevancy 约 0.55–0.70、Faithfulness 约 0.60–0.72；除正文点名的数字外，各配置的精确点值论文在正文中未逐一列出。

PILLAR-Tree 分阶段延迟

• 测了什么：Figure 4b 把五个代表配置（C1–C5，具体参数在 Table 3，正文未列出表内数值）的每查询延迟拆成 Section 4.2 的三阶段。
• 结果：作者称在 MS MARCO 上 Stage 1（遍历）和 Stage 3（取嵌入）大致持平，延迟变化几乎全来自 Stage 2（子块检索）。C5 的 MRR 为 0.318，最低延迟配置为 0.248。SciFact 上五个配置相差不到 20 ms。Figure 4b 纵轴刻度：MS MARCO 约 0–0.95 s，SciFact 约 0–0.3 s；各阶段柱高正文未给逐柱数字。
• 作者解读：Stage 2 的延迟带动检索质量。W 决定 Stage 2 精炼多少候选文档，作者称它是换新数据集时首先要调的参数。SciFact 差异小是因为小数据集上树更小。

PILLAR-Bin 消融

• 哈希表规模与通信量：Figure 4a 左图把每 bin 文档数固定为 10，横轴哈希表规模（对数，从 100 到 1M，六个数量级），纵轴每查询 Comm (KB)，刻度约 70–130。MS MARCO 与 SciFact 两条曲线。作者称通信量随表变大而上升，但最大表的通信还不到最小表的 2×，因此表规模对总通信影响小，可按检索质量选表规模（详见附录 D）。
• 每 bin 文档数与质量：右图把哈希表固定为 MS MARCO 100 万行、SciFact 5 千行，横轴每 bin 文档数（对数，刻度含 10、50、200、700、2.5K），纵轴 Quality（MRR@10/Recall@10），刻度 0–0.8。作者称文档数增加时质量上升。SciFact 在每 bin 700 篇之后收益变少；MS MARCO 在测到的最高档 1.0K–2.5K 仍继续上升。

其他消融与分析

• 附录 D 对每种协议的全部配置重画 Figure 3 类图，并换用 LAN 延迟、计算时间、总发送数据作为代价；正文未给出这些图的逐点数字。
• 附录 D.1 讨论 Tree 的 r、W、|B| 等参数及交互；正文只给出上述 C5 与最低延迟配置的 MRR，以及 SciFact 上配置间延迟差小于 20 ms。
• 引言中的非私有 ANN 对照：同一嵌入上 MRR@10 约 0.31，对比 PACMANN 的 0.266 MRR@10 与 20 次往返；该数字不是 Figure 3 的五个代表配置之一。
• 负面/例外：Tree 的束搜索不保证真正 top-k 块。Bin 在 SciFact 上每 bin 超过 700 篇后质量少有再增加。Tree 的延迟很少低到 Bin 的水平。SciFact 上五个 Tree 配置的延迟几乎拉不开（差 < 20 ms），作者归因于树更小。前沿上仍有 7% 的点来自 PACMANN。
• 附录 I.2 的外部数字：Anthropic 把 BM25 加进 Contextual Retrieval 后，top-20 检索失败率从 3.7% 降到 2.9%；这不是本文系统的测量。

作者指出的局限与后续方向

• 论文没有 Limitations、Discussion 或 Future Work 专节。结论只重述两种协议相对 PACMANN 的速度与质量，没有写成后续工作。
• 附录 I.2：作者写明 Elasticsearch、OpenSearch、Weaviate、Azure、Microsoft 白皮书和 Anthropic 这些来源说明混合检索被广泛支持与推荐，它们并不构成已部署系统的普查，而且许多简单 RAG 流水线仍然只用稠密检索。
• 方法正文中的范围说明（作者明确写出、但不是“未来工作”清单）：束搜索是启发式，不保证找到真正的 top-k 块（Section 4.2）。脚注说明本文 hybrid 只指检索方法，不是把稠密分与稀疏分合成最终分数。这两条是设计边界，论文没有把它们写成待解决问题。
• 代码：作者称 PILLAR-Bin 的代码可获得；正文没有把开源写成尚未完成的计划，也没有对 PILLAR-Tree 的代码作出同样陈述。

实验覆盖范围

• 数据与模型：检索评测为 MS MARCO（880 万段落、6980 条查询）和 SciFact（5183 篇、300 条查询）。文档/查询嵌入 192 维，分别为 msmarco-MiniLM-L-6-v3 与 e5-base-v2。生成模型为 Qwen2.5-7B-Instruct，RAGAS 评审为 Llama-3-70B，每数据集 100 条查询（附录 I.1）。
• 对照与指标：对照协议为 PACMANN，参数为 ANN 步数 p 与每步邻居数 n。指标为 MRR@10、Recall@10、Faithfulness、Answer Relevancy、每查询 WAN 延迟；附录 D 另报 LAN（5 ms RTT、1000 Mbps）、计算时间和总发送数据。主 WAN 为 50 ms RTT、400 Mbps。代表配置由 Kneedle 每协议选 C1–C5。
• PILLAR 自身测量：Bin 的消融含哈希表规模（六个数量级，每 bin 固定 10 篇）和每 bin 文档数（表规模固定为 MS MARCO 100 万、SciFact 5 千）。Tree 的延迟按 Stage 1–3 拆开，MS MARCO 上 C5 与最低延迟配置的 MRR 为 0.318 与 0.248。
• 论文未报告的设置：论文未报告 MRR/Recall 是否在全部查询上计算、未报告重复次数、未报告各代表配置的完整参数（称列在 Table 3）、未报告 Figure 3 上除点名数字外每个点的精确坐标。安全性分析放在附录 G，正文只给出半诚实、PIR-hybrid model 下隐藏查询的结论，未在实验节测量泄漏。
• 作者讨论过、并说明不适用或未计入的做法：附录 I.2 说明所引生产系统的混合检索推荐不是部署普查。引言用同一嵌入上非私有 ANN 的约 0.31 MRR@10 对照 PACMANN 的 0.266，该非私有数字不是 Section 5 的网格配置。

PILLAR 是面向公开语料的隐私 RAG：半诚实服务器学不到查询词项和访问模式，客户端仍拿到用于增强生成的 k 篇文档。

• 问题：把查询原样交给语料主机会泄露敏感检索意图。已有 PPRAG 以稠密 ANN 为主，遍历随查询变化，隐藏访问模式就要固定日程，交互轮次和检索质量一起变差；作者举 PACMANN 在 MS MARCO 上 20 次往返、MRR@10 0.266，对照同一嵌入非私有 ANN 约 0.31。同时真实系统常用词法加向量，而既有 PPRAG 只做一种架构。
• 方法：稀疏段先对预计算 BM25 索引做次数固定的 PIR，筛掉无词重叠的文档；客户端再 PIR 取候选嵌入，按余弦本地重排。PILLAR-Bin 把倒排表哈希到 R 行、每行截断为 t 个嵌入，碰撞表 round-robin 交错，批大小填充到 3，单轮。PILLAR-Tree 把块组织成 r 叉上界树，客户端用束宽 W 逐层 PIR，叶下再按子块大小 s 精炼，cuckoo 表只存非零上界，最后一轮取嵌入。作者称二者在 PIR-hybrid model 下隐藏查询。
• 结果：MS MARCO（880 万段落、6980 查询）与 SciFact（5183 篇、300 查询）上，用 Kneedle 为每协议选五个配置，WAN 为 50 ms / 400 Mbps。PILLAR-Bin 检索 top-10 最快 0.098 s（MS MARCO）和 0.065 s（SciFact）；最快 PACMANN 为 0.293 s 与 0.270 s。作者称前沿上 1 秒以内的配置里，Tree 在两数据集的 MRR@10、Recall@10、Relevancy、Faithfulness 上都最高；最佳配置中 Tree 的 answer Relevancy 为 0.75，对应 PACMANN 为 0.72 且延迟超过 2 倍。作者称全部实验的 Pareto 前沿点有 93% 来自 PILLAR。MS MARCO 上 Tree 的延迟差主要在子块阶段，MRR 从 0.248 到 0.318。
• 作者的结论：词法预筛与客户端语义重排可以拆开。Bin 提供始终更快的配置，作者称比 PACMANN 任一配置快约三倍；Tree 经常在相同速度下给出更高的文档质量。端到端答案用 Qwen2.5-7B-Instruct 生成、Llama-3-70B 按 RAGAS 评分，每数据集 100 条查询。