一次典型的 BM25 文档检索：从倒排索引到 FPGA 流水线

BM25 是一种基于关键词匹配的文档排序方法。本文沿着“读取倒排索引、计算 BM25 分数、维护 top-k、返回文档编号”这条路径，解释一次检索如何完成，再结合 HeteroLLM 讨论 FPGA 加速的边界。先看一个整体例子：

用户提问：

为什么 FPGA 适合加速 LLM 的记忆检索？

文档库里可能有 2000 万篇文档。系统不会逐篇阅读，而是通过倒排索引快速定位包含 FPGA、LLM、记忆、检索 等词的文档，再计算分数并选出最相关的若干篇。

这里假设查询与文档采用一致的分词和规范化规则。中文分词不会自动生成英文同义词；跨语言匹配还需要查询翻译或扩展。本文按命中任意查询词的 OR 检索解释候选集合。

完整流程是：

用户问题
   ↓ 分词、统计词频
查询词集合
   ↓
读取这些词的倒排索引
   ↓
找到可能相关的候选文档
   ↓
计算候选文档的 BM25 分数
   ↓
边计算边维护分数最高的 k 篇
   ↓
返回文档 ID
   ↓
根据 ID 读取文档正文，拼进 LLM prompt

一、读取倒排索引

1. 什么是正向索引

假设有三篇文档：

文档 0：FPGA 适合不规则访存
文档 1：GPU 适合矩阵乘法
文档 2：FPGA 可以加速 BM25 检索

最直观的存储方式是：

文档 0 → FPGA、适合、不规则、访存
文档 1 → GPU、适合、矩阵、乘法
文档 2 → FPGA、可以、加速、BM25、检索

这是从“文档”查“文档包含哪些词”，可以叫正向组织。

但如果用户查询 FPGA，系统必须检查每篇文档：

文档 0 有没有 FPGA？
文档 1 有没有 FPGA？
文档 2 有没有 FPGA？

当文档数量达到 2000 万时，这样非常慢。

2. 倒排索引

倒排索引把关系反过来：

FPGA  → 文档 0、文档 2
GPU   → 文档 1
BM25  → 文档 2
检索  → 文档 2
适合  → 文档 0、文档 1

如果进一步保存词频，可以写成：

FPGA →
    (文档 0，出现 1 次)
    (文档 2，出现 1 次)

检索 →
    (文档 2，出现 1 次)

每个词后面的列表叫 Posting List，即倒排列表。

倒排列表通常存储文档 ID、词频，有时还包含位置。下面这些辅助信息也可能保存在索引的其他结构中，文档长度不一定与每条 posting 放在一起：

文档 ID；
这个词在文档中出现的次数；
词出现的位置；
文档长度；
字段信息，例如标题或正文；
压缩后的索引偏移。

3. 查询时怎么读取

假设查询经过分词后是：

FPGA BM25 检索

系统只需要读取：

倒排索引["FPGA"]
倒排索引["BM25"]
倒排索引["检索"]

得到：

FPGA → 文档 0、文档 2
BM25 → 文档 2
检索 → 文档 2

候选集合是：

文档 0、文档 2

所以“计算每篇文档的 BM25 分数”是一种简化说法。更准确地说：

通常只需要计算至少命中一个查询词的候选文档，而不是无条件扫描文档库里的所有正文。

不过当查询词很常见、文档库很大时，候选文档仍然可能非常多。

二、计算 BM25 分数

BM25 用来回答：

某个查询词出现在这篇文档里，这件事有多重要？

它主要考虑三个因素。

1. 查询词是否稀有

假设文档库里：

the 出现在 1900 万篇文档中；
FPGA 只出现在 1 万篇文档中。

一篇文档包含 FPGA，通常比包含 the 更能说明它与查询相关。

这个因素由 IDF 表示：

\operatorname{IDF}(q)=\log\left(\frac{N-n_q+0.5}{n_q+0.5}+1\right)

其中：

$N$ ：文档总数；
$n_q$ ：包含查询词 $q$ 的文档数量。

词越稀有， $n_q$ 越小，IDF 越大。

2. 查询词在文档中出现多少次

如果用户查询 FPGA：

文档 A：FPGA 出现 1 次
文档 B：FPGA 出现 10 次

一般来说，文档 B 可能与 FPGA 更相关。

这个值叫 Term Frequency，即词频：

f(q,D)

不过 BM25 不认为“出现 10 次就一定比出现 1 次重要 10 倍”。

随着出现次数增加，收益会逐渐饱和：

出现 0 次：该查询词在此公式中的贡献为 0
出现 1 次：相关性明显增加
出现 2 次：继续增加
出现 20 次：不会无限增加

否则一篇不断重复 FPGA FPGA FPGA 的垃圾文档会获得极高分数。

3. 文档长度归一化

长文档天然更容易包含查询词。

例如：

文档 A：100 个词，其中 FPGA 出现 3 次
文档 B：10000 个词，其中 FPGA 出现 3 次

文档 A 显然更集中地讨论 FPGA。

因此 BM25 会根据文档长度进行惩罚。

4. 完整公式

单个查询词 $q$ 对文档 $D$ 的贡献通常写成：

\operatorname{score}(q,D)=\operatorname{IDF}(q)\cdot\frac{f(q,D)(k_1+1)}{f(q,D)+k_1\left(1-b+b\frac{|D|}{\operatorname{avgdl}}\right)}

其中：

$f(q,D)$ ：查询词在文档中的出现次数；
$|D|$ ：当前文档长度；
$\operatorname{avgdl}$ ：整个文档库的平均文档长度；
$k_1$ ：控制词频增长多快饱和；
$b$ ：控制文档长度惩罚强度；
$\operatorname{IDF}(q)$ ：这个词的稀有程度。

这里采用带 +1 的非负 IDF 形式。不同 BM25 实现的 IDF 和词频归一化约定可能不同，比较绝对分数时需要确认具体公式。本文把 Q 看作去重后的查询词集合，每个词权重为 1；若要计入查询词重复次数，应额外定义查询权重。

多个查询词的分数相加：

\operatorname{BM25}(Q,D)=\sum_{q\in Q}\operatorname{score}(q,D)

三、具体算一个简化例子

查询：

FPGA 检索

假设有三篇候选文档：

文档	长度	FPGA 次数	检索次数
文档 0	100	3	2
文档 1	1000	3	1
文档 2	120	0	5

为便于复算，设 k₁ = 1.2、b = 0.75、avgdl = 400；FPGA 的 IDF 为 3.0，检索的 IDF 为 1.5。这些是教学用假设统计量：三篇候选来自一个更大的文档库，avgdl 不是这三篇长度的平均值，IDF 也不是由这三篇反推的。

记长度归一化项 K(D) = k₁ × (1 − b + b × |D| / avgdl)。

文档 0 的 K(D) = 1.2 × (0.25 + 0.75 × 100 / 400) = 0.525。

因此它的两项贡献为：

FPGA：3 × (3 × 2.2) / (3 + 0.525) ≈ 5.617；
检索：1.5 × (2 × 2.2) / (2 + 0.525) ≈ 2.614；
总分：约 8.231。

另外两篇按同一公式计算：

文档       K(D)     FPGA贡献    检索贡献     总分
文档 0     0.525     5.617       2.614       8.231
文档 1     2.550     3.568       0.930       4.497
文档 2     0.570     0.000       2.962       2.962

最终排序为：文档 0 > 文档 1 > 文档 2。表中各项独立四舍五入，总分按未舍入值计算。

文档 0 同时命中两个词，且篇幅较短，因此得分最高；文档 1 虽被长度归一化削弱，但仍获得稀有词 FPGA 的贡献，超过只命中“检索”的文档 2。

这里展示的是当前参数下的结果，不能脱离词频、IDF 和归一化参数，预先保证任意两篇文档的顺序。

这不是余弦相似度，也不需要运行神经网络。BM25 主要是查表、加法、乘除法和文档统计信息读取。

四、为什么 BM25 访问很不规则

假设查询词是：

FPGA、LLM、memory

它们的倒排列表可能完全不同：

FPGA   → [17, 83, 902, 50001, ...]
LLM    → [2, 17, 39, 21000, ...]
memory → [7, 17, 2048, 50001, ...]

系统需要：

读取三个不同位置的倒排列表；
根据文档 ID 更新不同文档的累计分数；
查询文档长度；
读取每个词的词频；
合并重复出现的文档；
动态维护 top-k。

访问地址取决于用户输入了什么词，所以无法事先固定。

这会出现大量类似操作：

score[17] += ...
score[50001] += ...
score[83] += ...
score[2] += ...

这些地址不连续，属于不规则访存。

这是按词遍历、散点累加的一种执行方式，并不代表所有实现。倒排列表内部通常按文档 ID 有序且可压缩，读取本身可以较连续；按文档合并、分块和剪枝也会改变访问模式。因此，不能仅凭“不规则访存”断言 FPGA 必然快于 GPU，还需要结合数据布局、流水线和实测结果。

五、在线维护 top-k

假设候选文档有 100 万篇，但最后只需要返回 64 篇。

一种笨办法是：

计算全部 100 万个分数
   ↓
把全部分数保存到内存
   ↓
对 100 万个分数排序
   ↓
取前 64 个

问题是：

要存储大量中间分数；
完整排序成本高；
分数需要写入内存后再读出；
实际只关心前 64 名。

在线 top-k 的含义

“在线”不是指互联网，而是指：

每产生一个文档的最终分数，就更新当前 top-k，不等待所有候选文档全部完成打分。

假设 $k=3$ 。

依次到达的结果是：

文档 0：2.1
文档 1：7.4
文档 2：3.8
文档 3：9.0
文档 4：1.2
文档 5：6.5

维护过程：

收到文档 0：[(0, 2.1)]

收到文档 1：[(1, 7.4), (0, 2.1)]

收到文档 2：[(1, 7.4), (2, 3.8), (0, 2.1)]

收到文档 3：9.0 > 当前最小值 2.1
淘汰文档 0
得到：[(3, 9.0), (1, 7.4), (2, 3.8)]

收到文档 4：1.2 < 当前最小值 3.8
直接丢弃

收到文档 5：6.5 > 当前最小值 3.8
淘汰文档 2
得到：[(3, 9.0), (1, 7.4), (5, 6.5)]

此处 top-k 选择器只需保存三个候选；前提是输入已经是每篇文档的最终分数。前面按词执行 score[id] += ... 时，尚未完成的文档仍需要累计状态，不能据此说整个检索器只用 O(k) 内存。按文档合并倒排列表可以在完成当前文档后提交分数；采用其他遍历方式时，需要对应的累计或分块机制。

常见实现

软件中可以使用大小为 $k$ 的最小堆：

堆顶是当前 top-k 中分数最低的文档；
新分数不超过堆顶，直接丢弃；
新分数超过堆顶，替换堆顶；
单次更新时间约为 $O(\log k)$ 。

FPGA 中则可以构造：

比较器；
归约树；
固定大小的候选缓冲区；
流水化更新逻辑。

BM25 模块完成一个文档所有查询词贡献的累加后，可以直接把最终分数送入 top-k 模块：

倒排列表读取
    ↓
BM25 分数计算
    ↓ 不写回外部内存
比较网络
    ↓
更新 top-64

这就是计算与选择的流水融合：减少最终分数在两个模块之间写回、再读出的开销，并不表示倒排索引或所有累计状态都无需访问外部内存。实际实现还可以使用部分选择或有正确上界的剪枝；全量排序只是对照方案，不是唯一的软件实现。

六、返回文档编号

最终 FPGA 返回的不是完整文档，而是类似：

[17, 50001, 83, 902, ...]

这些是文档 ID。

为什么只返回编号？

假设每篇文档平均 4 KB，返回 64 篇正文大约需要：

64\times 4\ \text{KB}=256\ \text{KB}

实际文档可能更大。

但如果每个文档 ID 使用 4 字节，64 个 ID 只有：

64\times 4=256\ \text{bytes}

因此先返回 ID 可以降低检索器输出阶段的通信量。若同时返回分数，还要计入分数字节数；正文仍需由下游读取，这个例子并不代表整个 RAG 只传输了 256 字节。

收到 ID 后，系统再从文档存储中读取正文：

document_store[17]
document_store[50001]
document_store[83]
...

然后构造 prompt：

用户问题

参考文档 1：……
参考文档 2：……
参考文档 3：……

请根据参考文档回答。

最后才交给 LLM 做 Prefill 和 Decode。

七、对应到 HeteroLLM 中各设备的工作

根据论文附录 B.2（第 17 页），单阶段 RAG 将查询预处理为词频字典并传入 FPGA，检索到的文档索引返回 GPU。下面是逻辑分工图；论文该段没有逐项指定分词、正文读取等步骤到底由 CPU 还是 GPU 执行：

CPU/GPU：
对查询分词
统计查询词次数
生成查询字典
        │
        │ PCIe
        ▼
FPGA：
读取查询词对应的倒排索引
计算候选文档 BM25 分数
在线维护 top-64
        │
        │ 只返回文档 ID
        ▼
CPU/GPU：
根据 ID 读取文档正文
把文档拼接到 prompt
执行 LLM 推理

论文实验中：

检索方法是 BM25；
每次检索 64 篇文档；
基线系统的检索后端由 Elasticsearch 替换为 BM25S；论文称其为更快的 BM25 专用后端，这不是对所有配置的普遍性能保证；
FPGA 把 BM25 计算和 top-k 选择融合；
最终只返回文档索引。

因此，它不是用 FPGA 跑整个 RAG，更不是用 FPGA 跑完整 LLM，而是专门加速：

倒排索引访问
+
BM25 打分
+
top-k 筛选

这一段检索路径。需要注意，基线系统包含 GPU，不等于 BM25S 检索算子本身在 GPU 上运行；BM25S 官方实现主要使用 NumPy/SciPy 稀疏计算，其官方性能表采用 CPU 测试。BM25S 还可在索引阶段预计算词项贡献，在线主要完成查表、聚合和选择，因此本文的逐项公式用于解释打分语义，不是所有后端都会在线重算每个乘除法。

最简总结

这四步可以用“图书馆”类比：

读取倒排索引
= 根据关键词查目录，找到可能相关的书

计算 BM25 分数
= 判断每本候选书与问题有多相关

在线维护 top-k
= 每看到一本高分书，就更新当前最佳书单

返回文档编号
= 先返回书架编号，不搬运整本书

真正的文档正文会在得到编号以后才读取，并交给 LLM 使用。

参考资料

HeteroLLM：Understand and Accelerate Memory Processing Pipeline for Large Language Model Inference，附录 B.2，第 17 页（RAG 实验配置）；作者项目仓库。
BM25S 官方实现与基准说明。
BM25S 技术报告：Orders of magnitude faster lexical search via eager sparse scoring。

本文算例用于解释算法，没有进行新的 CPU、GPU 或 FPGA 性能测试。