---
tags: [AI, retrieval, rerank]
阶段: 06-Prompt与RAG
难度: ★★★
created: 2026-10-18
related: "[[Embedding与向量检索]], [[RAG文档分块策略]], [[RAG评估]]"
---

# 检索优化与重排Rerank

## 定义

**召回**（recall stage）指用低成本打分函数从文档集合中选出固定数量的候选；**重排**（reranking）指用高成本打分函数对候选重新排序。两阶段检索的形式为

$$
C=\operatorname{TopK}_{d\in\mathcal{D}}\,s_{\text{fast}}(q,d),
\qquad
\hat\pi=\operatorname{sort}_{d\in C}\,s_{\text{slow}}(q,d),
$$

其中 $C$ 是候选集，$\hat\pi$ 是最终排序。

符号约定如下。

| 符号 | 含义 |
|---|---|
| $\mathcal{D}$ | 文档或块集合，$N=\lvert\mathcal{D}\rvert$ |
| $q$ | 查询 |
| $d$ | 文档或块 |
| $C$ | 召回候选集，$\lvert C\rvert=k$ |
| $s_{\text{fast}}$ | 召回打分函数，本篇指 BM25 或双塔余弦 |
| $s_{\text{slow}}$ | 重排打分函数，本篇指 cross-encoder |
| $f(t,d)$ | 词项 $t$ 在文档 $d$ 中的频次 |
| $n_t$ | 包含词项 $t$ 的文档数 |
| $\lvert d\rvert$ | 文档 $d$ 的 token 长度 |
| $\mathrm{avgdl}$ | 集合的平均文档长度 |
| $k_1$ | BM25 词频饱和参数 |
| $b$ | BM25 长度归一化参数 |
| $\mathrm{rank}_r(d)$ | 检索器 $r$ 对文档 $d$ 的排名，从 1 开始 |
| $\kappa$ | RRF 平滑常数，区别于候选数 $k$ |
| $r_i$ | 位置 $i$ 的相关性等级 |

其余术语在首次出现处定义。**稀疏检索**（sparse retrieval）指以词表维度的高维稀疏向量表示文档的检索方法，BM25 是其代表；**稠密检索**（dense retrieval）指以低维稠密向量表示查询与文档、用内积或余弦打分的检索方法；**双塔模型**（bi-encoder）指查询与文档分别编码、只在末端做内积的结构；**交叉编码器**（cross-encoder）指把查询与文档拼接后一起送入 Transformer、由输出层给出相关性分数的结构；**混合检索**（hybrid retrieval）指融合稀疏与稠密两路结果的方法；**倒数排名融合**（Reciprocal Rank Fusion，RRF）指只使用排名而非分数的融合方法；**查询改写**（query rewriting）指在检索前改变查询文本的方法；**上下文压缩**（context compression）指在生成前删除检索结果中与查询无关内容的方法；**nDCG**（normalized Discounted Cumulative Gain）是带折扣的排序质量指标。

## 为什么重要

单阶段检索面临成本与质量的直接冲突。BM25 借助倒排索引可以在毫秒级处理百万级文档集合，但它只匹配字面词项，查询与文档使用不同措辞时得分为零；cross-encoder 让查询与文档的每个 token 互相注意，能识别同义改写与否定，但对 $N$ 个文档各做一次前向的成本无法接受。取 $N=10^6$、单对前向 $2\times10^{9}$ 次浮点运算，总运算量为 $2\times10^{15}$，远超单次查询的预算。

两阶段架构把成本分解为 $N c_{\text{fast}}+k c_{\text{slow}}$。当 $k\ll N$ 时，昂贵的模型只作用于少量候选，总成本由召回阶段主导。这一分解成立的前提是召回阶段把相关文档放进了候选集：重排只能在 $C$ 内调整顺序，无法恢复未召回的文档。因此召回率构成最终排序质量的上限，$k$ 的选择同时决定上限与延迟。

检索优化在本库中连接三个环节。[[Embedding与向量检索]] 给出双塔编码与相似度的定义；[[RAG文档分块策略]] 决定候选的粒度与长度；[[向量数据库]] 提供近似最近邻索引，使稠密召回的复杂度从 $O(N)$ 降到亚线性；[[RAG评估]] 定义 recall@k 与 nDCG 的口径。对应学习目标中的"懂原理"与"会评估"：能逐项解释 BM25 的四个组成部分，能用手算例子验证融合是否真的提高 nDCG。

## 原理与推导

### 1 两阶段排序的成本分解

设召回阶段单文档成本为 $c_{\text{fast}}$，重排阶段单候选成本为 $c_{\text{slow}}$，忽略生成阶段，总成本为

$$
T(k)=N\,c_{\text{fast}}+k\,c_{\text{slow}}.
$$

若跳过召回、对全部文档重排，成本为 $N c_{\text{slow}}$。两阶段更便宜的条件是

$$
N c_{\text{fast}}+k c_{\text{slow}}<N c_{\text{slow}}
\iff
k<N\left(1-\frac{c_{\text{fast}}}{c_{\text{slow}}}\right).
$$

当 $c_{\text{slow}}\gg c_{\text{fast}}$ 时，该条件近似为 $k<N$，几乎总成立。更有用的问题是：给定成本比 $c_{\text{slow}}/c_{\text{fast}}=\rho$，候选数 $k$ 最大可取多少而不使重排成本超过召回成本？令 $k c_{\text{slow}}=N c_{\text{fast}}$，得

$$
k=\frac{N}{\rho}.
$$

若 cross-encoder 单候选成本是 BM25 单文档成本的 $10^4$ 倍，则 $k=N/10^4$；$N=10^6$ 时 $k=100$。该式说明候选数应由成本比与语料规模共同决定，而不是取固定值。

召回率上限可以写成显式约束。设相关文档集为 $R$，候选集为 $C$，则最终排序最多只能覆盖 $R\cap C$。若 $\lvert R\cap C\rvert/\lvert R\rvert=0.7$，则无论重排多准，recall@10 不可能超过 0.7。提高 $k$ 会提高 $\lvert R\cap C\rvert$，但重排器在更长的候选列表上可能引入新的排序错误，因此实际 nDCG 随 $k$ 先升后平，不会单调上升。

### 2 BM25 的逐项解释

BM25 的完整形式为

$$
\mathrm{BM25}(q,d)=\sum_{t\in q}\mathrm{IDF}(t)\cdot
\frac{f(t,d)\,(k_1+1)}
{f(t,d)+k_1\left(1-b+b\,\dfrac{\lvert d\rvert}{\mathrm{avgdl}}\right)}.
$$

IDF 采用 Lucene 形式

$$
\mathrm{IDF}(t)=\ln\left(1+\frac{N-n_t+0.5}{n_t+0.5}\right).
$$

该形式来自概率相关框架。设相关文档数为 $N_R$，其中包含 $t$ 的文档数为 $r_t$，则词项权重为相关与不相关的对数几率

$$
w_t=\ln\frac{(r_t+0.5)/(N_R-r_t+0.5)}
{(n_t-r_t+0.5)/(N-n_t-N_R+r_t+0.5)}.
$$

在没有相关标注时取 $N_R=0$、$r_t=0$，分子为 $0.5/0.5=1$，得到

$$
w_t=\ln\frac{N-n_t+0.5}{n_t+0.5}.
$$

稀有词 $n_t$ 小，该值为正且较大；当 $n_t>N/2$ 时该值为负，包含高频词的文档会被惩罚。为避免负权重，Lucene 在 log 内加 1，得到上文形式。加 1 使 IDF 的下界为 0：当 $n_t\to N$ 时 $\frac{N-n_t+0.5}{n_t+0.5}\to0$，$\mathrm{IDF}\to\ln 1=0$，高频词的权重趋近于零而不为负。

词频饱和由分式

$$
g(f)=\frac{f(k_1+1)}{f+K},\qquad
K=k_1\left(1-b+b\frac{\lvert d\rvert}{\mathrm{avgdl}}\right)
$$

控制。性质如下。

第一，$g(0)=0$，$g(f)\to k_1+1$（$f\to\infty$），单个词项的贡献有上界。

第二，导数为

$$
g'(f)=\frac{(k_1+1)K}{(f+K)^2}>0,
$$

且随 $f$ 增大单调递减，边际收益递减。

第三，$f=K$ 时 $g=(k_1+1)/2$，$K$ 是半饱和点。$k_1$ 越小，$K$ 越小，饱和越快；$k_1=0$ 时 $g(f)=1$ 对任意 $f>0$ 成立，退化为二值匹配。

长度归一化由 $b$ 控制。$b=0$ 时 $K=k_1$，长度不进入公式；$b=1$ 时 $K=k_1\lvert d\rvert/\mathrm{avgdl}$，长度按比例完全归一化。取 $b=0.75$ 表示大部分长度差异被归一化，但仍保留部分长文档惩罚。

数值例子。取 $N=1000$、$n_t=10$，则

$$
\mathrm{IDF}=\ln\left(1+\frac{990.5}{10.5}\right)=\ln(95.33)=4.557.
$$

取 $k_1=1.5$、$b=0.75$、$\lvert d\rvert=\mathrm{avgdl}$，则 $K=1.5$。

| 词频 $f$ | $g(f)$ | 词项贡献 $4.557\,g(f)$ | 相对 $f=1$ |
|---|---|---|---|
| 1 | 1.000 | 4.557 | 1.00 |
| 5 | 1.923 | 8.763 | 1.92 |
| 20 | 2.326 | 10.598 | 2.33 |
| 100 | 2.463 | 11.224 | 2.46 |
| $\infty$ | 2.500 | 11.393 | 2.50 |

词频从 1 增到 20，实际频次增加 20 倍，得分只增加 2.33 倍。若没有饱和项而直接使用 $f$，单个高频词会支配整个分数，长文档与关键词堆砌文档会获得不成比例的优势。

长度惩罚同样可以量化。$\lvert d\rvert=2\,\mathrm{avgdl}$ 时 $K=1.5(0.25+1.5)=2.625$，$f=1$ 时 $g=2.5/3.625=0.690$，相对平均长度文档下降 31%。$\lvert d\rvert=0.5\,\mathrm{avgdl}$ 时 $K=1.5(0.25+0.375)=0.9375$，$g=2.5/1.9375=1.290$，上升 29%。

参数选择的一般范围如下。

| 参数 | 作用 | 常用值 | 调大后的效果 |
|---|---|---|---|
| $k_1$ | 控制词频饱和速度 | 1.2–2.0 | 高频词贡献上限提高，饱和变慢 |
| $b$ | 控制长度归一化强度 | 0.75 | 长文档惩罚加重 |

短 passage 检索常用 $k_1=0.9$、$b=0.4$，因为段落长度差异小，过强的长度归一化会引入噪声。

### 3 稠密检索

双塔模型分别编码查询与文档。记归一化后的查询向量为 $\mathbf{q}=E_q(q)$、文档向量为 $\mathbf{d}=E_d(d)$，则

$$
s_{\text{dense}}(q,d)=\langle \mathbf{q},\mathbf{d}\rangle,
$$

其中 $E_q,E_d$ 为两个编码器，输出经 L2 归一化，内积等于余弦。训练常用对比损失

$$
\mathcal{L}=-\log
\frac{\exp\big(s(q,d^{+})/\tau\big)}
{\exp\big(s(q,d^{+})/\tau\big)+\sum_{j=1}^{J}\exp\big(s(q,d_j^{-})/\tau\big)},
$$

其中 $d^{+}$ 为正例，$d_j^{-}$ 为第 $j$ 个负例，共 $J$ 个负例，$\tau$ 为温度。负例来自批内其他样本或 BM25 召回的困难负例。

双塔的关键性质是文档编码可以离线完成，在线只计算查询编码与 $N$ 次内积。内积本身是 $O(Nd)$，在 $N=10^6$、$d=768$ 时为 $7.7\times10^8$ 次乘加，仍高于倒排索引的词项查找；实际系统用 HNSW 或 IVF 把候选搜索降到亚线性，代价是近似误差。索引细节见 [[向量数据库]]。

稠密检索的弱点是精确匹配。产品编号、错误码、人名、数字区间在嵌入空间中不占特殊位置，训练分布之外的稀有 token 容易被平均掉。查询 `EXP-4471` 时，包含该编号的文档与包含其他编号的文档余弦接近，排序由其他语义成分决定。

### 4 混合检索与分数归一化

稀疏分数与稠密分数的量纲不同。BM25 无上界，取值随查询长度与 IDF 变化；余弦在 $[-1,1]$ 内。直接相加会让 BM25 主导排序。常用归一化有两种。

最小最大归一化：

$$
\tilde s(d)=\frac{s(d)-\min_{d'\in C}s(d')}{\max_{d'\in C}s(d')-\min_{d'\in C}s(d')}.
$$

z 分数归一化：

$$
\tilde s(d)=\frac{s(d)-\mu_C}{\sigma_C},
$$

其中 $\mu_C$ 与 $\sigma_C$ 是候选集上的均值与标准差。最小最大归一化对离群值敏感：一个极高分会把其余分数压到接近 0；z 分数假设分布近似单峰，长尾分布下方差被少数极端值抬高。

融合公式为凸组合

$$
s_{\text{hybrid}}(q,d)=\alpha\,\tilde s_{\text{sparse}}(q,d)+(1-\alpha)\,\tilde s_{\text{dense}}(q,d),
\qquad \alpha\in[0,1].
$$

$\alpha$ 必须在验证集上选择，不能在测试集上扫描后报告最优值，否则指标偏高。归一化在单个查询的候选集内进行，因此融合后的分数不能跨查询比较，只用于同一查询内的排序。

### 5 RRF 的公式与性质

RRF 只使用排名：

$$
\mathrm{RRF}(d)=\sum_{r\in\mathcal{R}}\frac{w_r}{\kappa+\mathrm{rank}_r(d)},
$$

其中 $\mathcal{R}$ 是检索器集合，$w_r$ 是权重，$\kappa$ 是平滑常数，文档未出现在某检索器的结果中时该项为 0。经典设置取 $w_r=1$、$\kappa=60$。

$\kappa$ 控制分布的平坦程度。相邻名次的贡献比为

$$
\frac{\kappa+\mathrm{rank}+1}{\kappa+\mathrm{rank}}.
$$

$\kappa=60$ 时第 1 名与第 2 名的比值为 $62/61=1.016$，几乎相等；$\kappa=10$ 时为 $12/11=1.09$；$\kappa=0$ 时为 2。$\kappa$ 大意味着单个检索器的第 1 名只比第 2 名多贡献 1.6%，融合结果由多个检索器的共识决定；$\kappa$ 小意味着头部名次主导。

以两个检索器为例。文档 $A$ 在一个检索器中排第 1、另一个未出现，得分 $1/61=0.0164$；文档 $B$ 在两个检索器中都排第 5，得分 $2/65=0.0308$。$B$ 的得分约为 $A$ 的 1.9 倍，说明 RRF 偏好被两路共同召回的中段文档，而非单路的头部文档。这一性质在候选池较大时能抑制单个检索器的偶然命中，在候选池很小时会抹平真实的质量差异。

RRF 的优点是无需分数归一化，对分数量纲、异常值与查询长度不敏感；缺点是完全丢弃分数幅度。若一个检索器对某个候选给出远高于其余候选的分数，该信息在 RRF 中只剩排名，融合结果可能不如加权分数融合。

### 6 cross-encoder 重排

cross-encoder 把查询与文档拼成一个序列送入 Transformer：

$$
s_{\text{CE}}(q,d)=\mathbf{w}^{\top}
\mathrm{Enc}\big([\mathrm{CLS}]\,q\,[\mathrm{SEP}]\,d\,[\mathrm{SEP}]\big)_{[\mathrm{CLS}]}.
$$

自注意力在每一层同时覆盖查询 token 与文档 token，因此模型可以表示"查询中的否定词作用于文档中的哪个短语"这类交互，而双塔只能在末端做一次内积，无法表示 token 级交互。

输出头有三种常见形式。二分类头对 $[\mathrm{CLS}]$ 向量做线性变换后接 sigmoid，用二元交叉熵训练：

$$
\mathcal{L}_{\text{BCE}}=-\frac{1}{B}\sum_{i=1}^{B}
\Big[y_i\log\sigma(s_i)+(1-y_i)\log\big(1-\sigma(s_i)\big)\Big],
$$

其中 $B$ 为批大小，$y_i\in\{0,1\}$ 为标签，$s_i$ 为模型打分。

回归头直接输出实数，用均方误差拟合分级标签：

$$
\mathcal{L}_{\text{MSE}}=\frac{1}{B}\sum_{i=1}^{B}\big(s_i-y_i\big)^2,
\qquad y_i\in\{0,1,\dots,4\}.
$$

pairwise 排序损失要求正例分数高于负例一个边界：

$$
\mathcal{L}_{\text{pair}}=\frac{1}{B}\sum_{i=1}^{B}
\max\big(0,\ m-s(q,d_i^{+})+s(q,d_i^{-})\big),
$$

其中 $m$ 是边界超参数。

训练数据由 $(q,d^{+},d^{-})$ 三元组构成，负例通常取 BM25 召回中排名较高但不相关的文档，即困难负例。困难负例使重排器学会区分"字面匹配但不相关"与"措辞不同但相关"，若只用随机负例，模型学到的分界线过于粗糙。

复杂度对比如下。

| 维度 | 双塔 bi-encoder | 交叉编码器 cross-encoder |
|---|---|---|
| 文档编码 | 离线一次，可缓存 | 每个查询对每个候选在线编码 |
| 查询文档交互 | 仅末端内积 | 每层全注意力 |
| 在线复杂度 | $O(Nd)$ 或 ANN 亚线性 | $O(kL^{2}d)$，$L$ 为拼接后长度 |
| 新增文档 | 编码后插入索引 | 无需重建，但每次打分仍在线 |
| 分数可比性 | 跨查询大致可比 | 仅在单次查询的候选内可比 |

$O(kL^2d)$ 中的 $k$ 是候选数而非文档总数，这是两阶段架构能够使用 cross-encoder 的原因。若对全部文档打分，复杂度为 $O(NL^2d)$，在 $N=10^6$ 时不可行。

重排的延迟由三部分组成：候选检索、批量前向、结果合并。批量前向的近似模型为

$$
T_{\text{rerank}}\approx \frac{k\,t_{\text{pair}}}{B_{\text{par}}}+T_{\text{overhead}},
$$

其中 $t_{\text{pair}}$ 是单对前向时间，$B_{\text{par}}$ 是并行度。取 $t_{\text{pair}}=2\,\mathrm{ms}$、$k=50$、串行执行，延迟约 100 ms；若 GPU 批处理把 50 对压到一次前向，延迟由单次批处理时间决定，通常显著低于串行总和。工程上应测量目标硬件上的实际吞吐，不能直接用参数量推算。

### 7 查询改写

同义扩展用词典或嵌入近邻为查询补充同义词。设原查询增加 $m$ 个词项 $t_1,\dots,t_m$，BM25 在扩展后的查询上重新打分。风险是扩展词引入歧义：`bank` 扩展出 `river` 与 `finance`，两者只有一个与上下文相符。

HyDE（Hypothetical Document Embeddings）先用模型生成一个假设答案 $\hat a=\mathrm{LLM}(q)$，再用 $\hat a$ 的嵌入检索：

$$
d^{*}=\arg\max_{d}\cos\big(E(\hat a),E(d)\big).
$$

其依据是答案与文档在表述上比问题与文档更接近：问题通常短且含疑问结构，文档是陈述句，假设答案与文档同属陈述语气，词汇分布更接近。代价是一次额外的模型调用，风险是假设答案包含错误事实，检索结果偏离原问题。HyDE 适合开放域事实问答，不适合需要精确匹配编号或日期的查询。

多查询（multi-query）生成 $m$ 个改写版本 $q_1,\dots,q_m$，分别检索后用 RRF 融合：

$$
\mathrm{RRF}(d)=\sum_{j=1}^{m}\frac{1}{\kappa+\mathrm{rank}_{j}(d)}.
$$

召回率随 $m$ 提高，成本随 $m$ 线性增长。$m$ 通常取 3 到 5，继续增加时新查询与已有查询高度重复，边际召回收益下降。

查询分解把多跳问题拆成子问题：`Atlas 项目负责人所在城市` 分解为 `Atlas 项目负责人是谁` 与 `该负责人的办公地点`。分解需要模型判断实体依赖关系，属于 [[进阶RAG-Self-RAG与Agentic-RAG]] 的迭代检索范畴。

### 8 上下文压缩与句子级剪枝

检索返回的块中常有大段与查询无关的内容。上下文压缩在生成前删除这些内容，降低 token 成本并减少干扰。

句子级剪枝把块拆成句子 $s_1,\dots,s_n$，为每个句子打相关性分数，在预算 $B_{\text{ctx}}$ 内选择子集：

$$
\max_{S\subseteq\{1,\dots,n\}}\ \sum_{i\in S}\mathrm{rel}(s_i)
\quad\text{s.t.}\quad \sum_{i\in S}\mathrm{len}(s_i)\le B_{\text{ctx}}.
$$

该问题是 0-1 背包，句子数较少时可用动态规划，工程上常用按 $\mathrm{rel}(s_i)/\mathrm{len}(s_i)$ 排序的贪心近似。相关性分数可由 cross-encoder 给出，也可由查询词覆盖与嵌入相似度的加权和给出。

压缩的风险有三类。删除包含代词指代先行词的句子，剩余句子中的"它"失去指代对象；删除否定句或条件句，答案的适用条件丢失；删除引用所需的最小证据片段，答案无法溯源。压缩率越高，这三类风险越大，因此需要同时评估压缩率与答案忠实度，不能只报告 token 节省比例。

### 9 重排候选数 $k$ 的选择

$k$ 的选择由召回率曲线与延迟预算共同决定。设 $\mathrm{recall@}k$ 为相关文档进入前 $k$ 的比例，最终 nDCG 的上界随 $\mathrm{recall@}k$ 提高。定义净效用

$$
U(k)=\mathbb{E}\big[\mathrm{nDCG@10}\mid k\big]-\lambda\,k\,c_{\text{slow}},
$$

其中 $\lambda$ 把延迟换算为与指标同单位的成本。选择使 $U(k)$ 最大的 $k$，或选择召回率曲线拐点：从 $k$ 到 $k+\Delta$ 的召回增益小于 $\Delta c_{\text{slow}}\lambda$ 时停止增加。

工程经验值：cross-encoder 重排取 $k=50$ 到 $100$；LLM 重排取 $k=20$ 到 $50$，因为单次调用成本更高；多路融合时选取并集，$k$ 按每路计算后去重。若 $\mathrm{recall@10}$ 已经达到 0.95，继续增大 $k$ 只增加延迟。

本篇「例子与代码」一节的实测给出一个具体例子：BM25 的 $\mathrm{recall@10}$ 为 0.75，稠密检索为 0.9167。若只用 BM25 且取 $k=10$，四分之一的相关文档从未进入重排，nDCG 上限被锁定在 0.75 附近；把 $k$ 提高到 20 或改用混合召回，上限才提高。

### 10 nDCG 的定义

nDCG 用分级相关性衡量排序质量：

$$
\mathrm{DCG@}k=\sum_{i=1}^{k}\frac{2^{r_i}-1}{\log_2(i+1)},
\qquad
\mathrm{nDCG@}k=\frac{\mathrm{DCG@}k}{\mathrm{IDCG@}k},
$$

其中 $r_i$ 是位置 $i$ 的相关性等级，$\mathrm{IDCG@}k$ 是把候选按相关性降序排列后的 DCG。增益 $2^{r}-1$ 使高相关性等级的边际价值递增，折扣 $1/\log_2(i+1)$ 使靠前位置权重更高。nDCG 取值在 $[0,1]$，便于跨查询平均。

使用 nDCG 时需固定相关性等级的定义与 $k$。等级从二元改为三级会改变数值，历史结果不可直接比较。

## 关键直觉

> [!tip]
> 两阶段检索把"找得到"与"排得准"分开：召回阶段只需保证相关文档以较高概率进入候选集，重排阶段只需在候选集内恢复正确顺序。BM25 的饱和项使词频的边际收益递减，RRF 用排名替代分数以消除量纲差异，cross-encoder 则把查询与文档的交互放入同一个注意力计算。

该表述与形式定义对应：召回阶段的目标是最大化 $\lvert R\cap C\rvert$，重排阶段的目标是在固定 $C$ 上最大化 nDCG。两个目标可分别优化，但不能互相替代，因为重排无法改变 $C$ 的构成。

## 例子与代码

以下代码在一个 22 篇文档的小语料上实现 BM25、基于嵌入的稠密检索、最小最大归一化加权融合与 RRF，并用 nDCG@10 比较融合前后的排序质量。运行环境为 Python 3.10 及以上、NumPy 1.24 及以上。

语料含 3 个主题，每个主题 6 篇文档，另有 4 篇干扰文档。相关性等级为 0、1、2 三级，由人工按主题与证据强度标注。稠密检索使用可复现的替代嵌入：词项经同义词映射后哈希到 128 维，并叠加主题概念向量。该设计使代码不依赖模型权重，同时保留"语义匹配"与"字面匹配"的差异；真实系统应替换 `embed` 为双塔模型。

```python
# Python 3.10+, numpy>=1.24
import hashlib
import math
import re
from collections import Counter

import numpy as np

DOCS = {
    "d01": "Travel expense reimbursement policy: submit original receipts within 30 days of the trip. Claims above 5000 require manager approval. Use form EXP-4471.",
    "d02": "Staff may recover out-of-pocket costs incurred on business trips; attach original invoices. Finance settles the amount within ten working days.",
    "d03": "Refund of unused travel advances is handled by the finance desk.",
    "d04": "The travel desk books flights and hotels for visiting customers.",
    "d05": "Expense reports are archived for seven years by the finance team.",
    "d06": "Managers approve claims above 5000; the approval is recorded in the expense system.",
    "d07": "Serving a 70B parameter model requires about 140 GB of GPU memory in FP16; INT8 quantization halves the requirement.",
    "d08": "VRAM use during inference is dominated by model weights and the KV cache; batch size scales the cache linearly.",
    "d09": "GPU selection should compare memory bandwidth, not only FLOPs, for token generation throughput.",
    "d10": "Training a 70B model requires data parallelism and tensor parallelism across many accelerators.",
    "d11": "Quantization to four bits reduces weight memory but may lower accuracy on long prompts.",
    "d12": "Throughput per GPU depends on batch size and sequence length.",
    "d13": "Split a document into chunks of 200 to 500 tokens; overlap of 10 to 20 percent reduces boundary loss.",
    "d14": "A splitter should respect paragraph and sentence boundaries before falling back to fixed windows.",
    "d15": "Small chunks improve matching precision but may cut the evidence needed for generation.",
    "d16": "Parent-child indexing retrieves small children and passes large parents to the generator.",
    "d17": "Tables and code blocks must be kept intact; splitting them breaks syntax.",
    "d18": "Metadata such as source and page number supports citation and filtering.",
    "d19": "The finance desk processes purchase orders every Tuesday.",
    "d20": "Office printers are maintained by the IT service desk.",
    "d21": "The company cafeteria opens at eight in the morning.",
    "d22": "Customer support tickets are triaged by severity.",
}

QUERIES = {
    "q1": ("travel expense reimbursement procedure form EXP-4471",
           {"d01": 2, "d02": 1, "d03": 1, "d06": 1}),
    "q2": ("GPU memory required for 70B model inference",
           {"d07": 2, "d08": 1, "d09": 1, "d11": 1}),
    "q3": ("document chunk overlap splitter boundary",
           {"d13": 2, "d14": 1, "d15": 1, "d16": 1}),
}

STOP = set("a an the of to for in on at and or is are was were be by with from as it its this that".split())


def tok(text):
    return [w for w in re.findall(r"[a-z0-9\-]+", text.lower()) if w not in STOP]


class BM25:
    def __init__(self, docs, k1=1.5, b=0.75):
        self.ids = list(docs)
        self.k1, self.b = k1, b
        self.tfs = [Counter(tok(docs[i])) for i in self.ids]
        self.lens = [sum(tf.values()) for tf in self.tfs]
        self.avgdl = sum(self.lens) / len(self.lens)
        self.df = Counter()
        for tf in self.tfs:
            self.df.update(tf.keys())

    def idf(self, term):
        n = self.df.get(term, 0)
        return math.log(1 + (len(self.ids) - n + 0.5) / (n + 0.5))

    def scores(self, query):
        q = tok(query)
        out = {}
        for i, doc_id in enumerate(self.ids):
            s = 0.0
            for term in q:
                f = self.tfs[i].get(term, 0)
                if f == 0:
                    continue
                denom = f + self.k1 * (1 - self.b + self.b * self.lens[i] / self.avgdl)
                s += self.idf(term) * f * (self.k1 + 1) / denom
            out[doc_id] = s
        return out


DIM = 128
SYN = {"trips": "trip", "costs": "cost", "receipts": "receipt", "claims": "claim",
       "settles": "settle", "invoices": "invoice", "chunks": "chunk", "reimbursement": "settle",
       "refund": "settle", "travel": "trip", "expense": "cost", "reimburse": "settle"}
LEXICON = {
    "expense": {"cost", "trip", "settle", "invoice", "claim", "receipt", "advance"},
    "gpu": {"gpu", "vram", "memory", "quantization", "batch", "tokens", "latency", "inference", "70b"},
    "chunk": {"chunk", "split", "splitter", "overlap", "token", "boundary", "document", "sentence"},
}
_CACHE = {}


def concept_vec(name):
    if name not in _CACHE:
        seed = int(hashlib.md5(name.encode()).hexdigest()[:8], 16)
        v = np.random.default_rng(seed).standard_normal(DIM)
        _CACHE[name] = v / np.linalg.norm(v)
    return _CACHE[name]


def embed(text):
    """同义词归一后的哈希词袋加主题概念向量，替代真实双塔模型。"""
    words = [SYN.get(w, w) for w in tok(text)]
    lex = np.zeros(DIM)
    for w in words:
        h = int(hashlib.md5(w.encode()).hexdigest()[:8], 16)
        lex[h % DIM] += 1.0
    if np.linalg.norm(lex) > 0:
        lex = lex / np.linalg.norm(lex)
    con = np.zeros(DIM)
    for name, lexicon in LEXICON.items():
        if any(w in lexicon for w in words):
            con = con + concept_vec(name)
    if np.linalg.norm(con) > 0:
        con = con / np.linalg.norm(con)
    v = 0.5 * lex + con
    sigma = np.linalg.norm(v)
    return v / sigma if sigma > 0 else v


DOC_VECS = {doc_id: embed(text) for doc_id, text in DOCS.items()}
BM = BM25(DOCS)


def dense_scores(query):
    qv = embed(query)
    return {doc_id: float(qv @ dv) for doc_id, dv in DOC_VECS.items()}


def minmax(scores):
    vals = np.array(list(scores.values()))
    lo, hi = float(vals.min()), float(vals.max())
    if hi - lo < 1e-12:
        return {k: 0.0 for k in scores}
    return {k: (v - lo) / (hi - lo) for k, v in scores.items()}


def rank_by(scores, positive_only=True):
    items = [(d, s) for d, s in scores.items() if (s > 1e-12 or not positive_only)]
    return [d for d, _ in sorted(items, key=lambda kv: (-kv[1], kv[0]))]


def rrf(rank_lists, k=60):
    acc = Counter()
    for ranking in rank_lists:
        for r, doc_id in enumerate(ranking, start=1):
            acc[doc_id] += 1.0 / (k + r)
    return dict(acc)


def ndcg_at_10(ranking, rel, k=10):
    dcg = sum((2 ** rel.get(d, 0) - 1) / math.log2(i + 2) for i, d in enumerate(ranking[:k]))
    ideal = sorted(rel.values(), reverse=True)[:k]
    idcg = sum((2 ** r - 1) / math.log2(i + 2) for i, r in enumerate(ideal))
    return dcg / idcg if idcg else 0.0


def recall_at_k(ranking, rel, k):
    relevant = {d for d, r in rel.items() if r > 0}
    return len(set(ranking[:k]) & relevant) / len(relevant)


def run():
    rows = []
    for qid, (query, rel) in QUERIES.items():
        bm = BM.scores(query)
        dn = dense_scores(query)
        rb, rd = rank_by(bm), rank_by(dn)

        nb, nd = minmax(bm), minmax(dn)
        fused = {d: 0.5 * nb[d] + 0.5 * nd[d] for d in DOCS}
        rf60 = rrf([rb, rd], k=60)
        rf10 = rrf([rb, rd], k=10)

        methods = {
            "BM25": rb,
            "Dense": rd,
            "Linear 0.5": rank_by(fused),
            "RRF k=60": rank_by(rf60),
            "RRF k=10": rank_by(rf10),
        }
        row = {"query": qid, "rel": rel}
        for name, ranking in methods.items():
            row[name] = ndcg_at_10(ranking, rel)
        rows.append(row)

        if qid == "q1":
            print("q1 BM25 top5:", rb[:5])
            print("q1 Dense top5:", rd[:5])
            print("q1 RRF k=10 top5:", rank_by(rf10)[:5])
            print()

    names = ["BM25", "Dense", "Linear 0.5", "RRF k=60", "RRF k=10"]
    print(f"{'查询':<6}" + "".join(f"{n:>12}" for n in names))
    for row in rows:
        print(f"{row['query']:<6}" + "".join(f"{row[n]:12.4f}" for n in names))
    print(f"{'平均':<6}" + "".join(f"{np.mean([r[n] for r in rows]):12.4f}" for n in names))

    print("\nalpha 敏感性（线性融合，nDCG@10 均值）")
    for alpha in [0.2, 0.4, 0.5, 0.6, 0.8]:
        vals = []
        for qid, (query, rel) in QUERIES.items():
            bm, dn = minmax(BM.scores(query)), minmax(dense_scores(query))
            fused = {d: alpha * bm[d] + (1 - alpha) * dn[d] for d in DOCS}
            vals.append(ndcg_at_10(rank_by(fused), rel))
        print(f"alpha={alpha:.1f}  nDCG@10={np.mean(vals):.4f}")

    print("\n候选数 k 与召回率（相关文档指 rel>=1）")
    print(f"{'k':<4}{'BM25':>8}{'Dense':>8}")
    for k in [1, 3, 5, 10]:
        rb = np.mean([recall_at_k(rank_by(BM.scores(q)), rel, k) for q, rel in QUERIES.values()])
        rd = np.mean([recall_at_k(rank_by(dense_scores(q)), rel, k) for q, rel in QUERIES.values()])
        print(f"{k:<4}{rb:8.4f}{rd:8.4f}")


if __name__ == "__main__":
    run()
```

代码分五部分。`BM25` 类按第 2 节的公式实现，`idf` 使用 Lucene 形式以保证非负；`embed` 与 `dense_scores` 实现稠密一路，`concept_vec` 用固定种子生成主题向量，保证跨进程可复现；`minmax` 与 `rank_by` 实现归一化与排序，`rank_by` 过滤零分文档，模拟倒排索引只返回命中项的行为，若保留零分文档，不相关文档会占据名次并虚高 recall；`rrf` 与 `ndcg_at_10` 实现融合与评估；`run` 逐查询比较五种排序。去掉 `rank_by` 的过滤后，BM25 的 recall@10 会从 0.75 升到 0.83 左右，这是实现细节改变评估口径的例子。

运行输出如下。

```text
q1 BM25 top5: ['d01', 'd03', 'd04', 'd05', 'd06']
q1 Dense top5: ['d01', 'd02', 'd03', 'd04', 'd05']
q1 RRF k=10 top5: ['d01', 'd03', 'd04', 'd05', 'd06']

查询            BM25       Dense  Linear 0.5    RRF k=60    RRF k=10
q1          0.8808      0.9837      0.9589      0.9589      0.9589
q2          0.9398      0.9302      0.9398      0.9302      0.9302
q3          0.7960      0.6864      0.9056      0.7438      0.7438
平均          0.8722      0.8667      0.9347      0.8776      0.8776

alpha 敏感性（线性融合，nDCG@10 均值）
alpha=0.2  nDCG@10=0.9315
alpha=0.4  nDCG@10=0.9347
alpha=0.5  nDCG@10=0.9347
alpha=0.6  nDCG@10=0.9347
alpha=0.8  nDCG@10=0.9347

候选数 k 与召回率（相关文档指 rel>=1）
k       BM25   Dense
1     0.2500  0.2500
3     0.5000  0.6667
5     0.6667  0.7500
10    0.7500  0.9167
```

结果可以逐项读出。

q1 中 BM25 的前五名是 d01、d03、d04、d05、d06，d02 完全缺席。d02 是政策正文的改写版本，使用 `recover out-of-pocket costs`、`business trips`、`invoices`、`settles` 等词，与查询 `travel expense reimbursement` 没有共同词项，BM25 得分为 0。稠密检索把 d02 排在第 2，因为同义词映射与概念向量把它放在费用主题上。这一差异是混合检索的主要收益来源。

q3 中 BM25 只返回 d13 与 d14 两篇非零分文档，d15 与 d16 得分为 0；稠密检索返回 d14、d15、d13。线性融合把 d13 排在第一：BM25 对 d13 的分数为 7.024，远高于 d14 的 2.640，归一化后 d13 接近 1，而稠密分数中 d14 与 d13 只差 0.105，融合结果保留了 BM25 的置信度。RRF 把 d14 排在第一，因为 d14 在 BM25 中第 2、在稠密中第 1，得分为 $1/12+1/11=0.1742$；d13 在两个列表中分别为第 1 与第 3，得分为 $1/11+1/13=0.1678$。d14 是 1 级相关，d13 是 2 级相关，把 d14 排在前面损失了 nDCG。这个例子说明 RRF 丢弃分数幅度后，可能把"两路都较好"的文档排在"一路极强、一路较好"的文档之前。

平均 nDCG 从 BM25 的 0.8722 与稠密的 0.8667 提高到线性融合的 0.9347，提升约 0.06。RRF 的平均值为 0.8776，只略高于 BM25。在本实验的小候选集上，RRF 不占优的原因是 $\kappa=60$ 使相邻名次几乎等权，而候选集只有 22 篇文档，名次差异本身携带的信息量小；同时两路检索的排序高度相关，RRF 无法利用 BM25 的大分数间隔。若候选池扩大到数百篇、两路分数量纲差异更大或融合三路以上，RRF 的相对表现会改善。这一比较也说明融合方法需要与候选规模、检索器相关性一起评估，不能默认 RRF 优于加权融合。

alpha 从 0.2 到 0.8 时均值在 0.9315 到 0.9347 之间，说明在该语料上两路质量接近，融合权重不敏感。若一路明显更强，曲线会出现峰值，此时 alpha 必须在验证集上选择。

召回率表给出 $k$ 的依据。$k=1$ 时两路召回都只有 0.25；$k=10$ 时 BM25 为 0.75、稠密为 0.9167。若重排候选数取 10 而只用 BM25，四分之一的相关文档不会进入重排，nDCG 上限被锁定。把 $k$ 提高到 20 以上或改用混合召回，上限才提高。真实系统应在自己的验证集上画出同样的曲线，再按第 9 节的净效用选择 $k$。

## 易错点

> [!warning]
> - 直接把 BM25 分数与余弦相似度相加：两者量纲不同，BM25 的数值范围随查询长度与 IDF 变化，未归一化时融合结果几乎完全由 BM25 决定。
> - 在测试集上扫描 $\alpha$ 与 $k$ 后报告最优值：这是用测试集调参，指标偏乐观；应在验证集选择，测试集只评估一次。
> - 认为 RRF 必然优于加权融合：RRF 丢弃分数幅度，当一路检索器明显更强或候选集很小时会损失信息，本篇 q3 的结果即为反例。
> - 重排候选数取得过小：召回率上限被锁定，重排器再强也无法恢复未召回的文档；取得过大则延迟线性增长，且可能引入更多排序错误。
> - 用 cross-encoder 的原始分数做跨查询阈值判断：分数未校准，不同查询的分布不同，同一阈值在不同查询上的精确率差异很大；需要 Platt 缩放或按查询内分位数判定。
> - IDF 未加 1 平滑：当 $n_t>N/2$ 时 IDF 为负，包含高频词的文档被惩罚，排序出现与直觉相反的结果。

## 关联笔记

- [[Embedding与向量检索]]（前置）：给出双塔编码、余弦相似度与对比学习损失的定义，是稠密召回的基础。
- [[向量数据库]]（前置）：提供 HNSW 与 IVF 等近似最近邻索引，决定稠密召回的召回率与延迟。
- [[RAG文档分块策略]]（前置）：块的长度与边界决定 BM25 的长度归一化项与稠密向量的主题纯度。
- [[RAG评估]]（后续）：定义 recall@k、nDCG 与答案忠实度的计算口径，本篇的实验设计依赖这些指标。
- [[进阶RAG-Self-RAG与Agentic-RAG]]（后续）：在重排之后加入迭代检索与自我验证，处理单轮检索无法覆盖的多跳问题。

## 达标检测

- [ ] 能写出 BM25 的完整公式，并逐项说明 TF 饱和、IDF、长度归一化与 $k_1$、$b$ 的作用。
- [ ] 能手算 $N=1000$、$n_t=10$、$f=5$、$\lvert d\rvert=\mathrm{avgdl}$、$k_1=1.5$、$b=0.75$ 时的 BM25 词项贡献。
- [ ] 能推导两阶段检索的成本平衡点 $k=N/\rho$，并说明 $\rho=10^4$、$N=10^6$ 时 $k$ 的取值。
- [ ] 能对两个排名列表手算 RRF 分数，并说明 $\kappa$ 从 60 降到 10 时排序可能发生的变化。
- [ ] 能运行本篇代码，把 $\kappa$ 改为 5 并解释 nDCG 的变化方向与原因。
- [ ] 能说明 cross-encoder 的在线复杂度为什么是 $O(kL^2d)$ 而不是 $O(NL^2d)$。
- [ ] 能根据一条 recall@k 曲线与单候选延迟，选择一个满足延迟预算的 $k$ 并给出计算过程。
- [ ] 能指出"在测试集上扫描 $\alpha$ 与 $k$ 后报告最优值"这一做法的偏差来源，并给出正确的调参流程。

## 参考来源

- Robertson & Zaragoza, *The Probabilistic Relevance Framework: BM25 and Beyond*, 2009 —— 对应本篇 BM25 的概率相关推导、饱和项与参数含义。
- Cormack, Clarke & Buettcher, *Reciprocal Rank Fusion Outperforms Condorcet and Individual Rank Learning Methods*, SIGIR 2009 —— 对应 RRF 公式、$\kappa=60$ 的取值与融合实验。
- Nogueira & Cho, *Passage Re-ranking with BERT*, arXiv:1901.04085, 2019 —— 对应 cross-encoder 的结构、训练方式与重排效果。
- Gao et al., *Retrieval-Augmented Generation for Large Language Models: A Survey*, arXiv:2312.10997 —— 对应检索优化在 RAG 流程中的位置与查询改写的分类。
