# 22 BGJ 递归分桶与多层筛选

整理日期：2026-10-16。  
适用范围：BGJ 的递归近邻搜索框架、球帽版本的多层分桶，以及条件分布、配对覆盖和时间空间成本。  
前置笔记：[19 筛法中的近邻搜索与分桶](/knowledge/nearest-neighbor-search-and-bucketing/)、[20 角度 LSH 与多表搜索](/knowledge/angular-lsh-and-multiple-tables/)、[21 球面 LSF 与过滤器](/knowledge/spherical-lsf-and-filters/)。

设当前筛法维数为 $s$，固定一轮输入池 $D=\{x_1,\ldots,x_N\}$，所有向量非零，记 $u_i=x_i/\|x_i\|$。本篇继续研究两向量约化中的批量伙伴搜索。

## 1. BGJ 递归地缩小搜索列表

单层分桶把整个池分成若干重叠的小桶，再枚举桶内向量对。BGJ 继续对桶进行过滤，直到列表足够小，再做两两检查。

递归过程中改变的是搜索列表；原格向量及其所在的 $s$ 维空间保持不变。一个向量可以进入多个子桶，同一源向量对也可能沿不同路径到达多个叶子。

需要区分原始过滤器与后续球帽版本：

**BGJ15 原始构造**使用多个随机超平面的符号计数。取独立随机方向 $a_1,\ldots,a_r$，参数 $\delta\in(0,1)$，过滤条件为

$$
f(u)=
\mathbf 1\!\left\{
\sum_{j=1}^{r}\mathbf 1\{\langle u,a_j\rangle\ge0\}
\le
\left\lfloor\frac{1-\delta}{2}r\right\rfloor
\right\}.
$$

这里保留符号计数偏向一侧的向量。原论文在过滤后的子列表上递归，列表足够小时转为直接枚举。参见 [Becker–Gama–Joux，ePrint 2015/522，§3，过滤器定义与 Algorithm 3](https://eprint.iacr.org/2015/522.pdf)。

**球帽版本**沿用递归框架，将每层过滤条件换为

$$
f^\pm_{c,\alpha}(u)
=
\mathbf 1\{|\langle u,c\rangle|\ge\alpha\}.
$$

Zhao–Ding–Yang 将使用一、二、三层过滤的版本分别称为 bgj1、bgj2、bgj3。这里的数字表示过滤层数，最终仍检查两条向量的和或差。参见 [《Sieving with Streaming Memory Access》，§3.2，Algorithms 2–3，所链接 PDF 第 6–7 页](https://csrc.nist.gov/csrc/media/events/2025/sixth-pqc-standardization-conference/sieving%20with%20streaming%20memory%20access.pdf)。

下文主要用球帽版本说明多层分桶，最后再回到 BGJ15 的经典复杂度。

## 2. 一个固定输入池的递归流程

设最多使用 $k$ 层过滤。第 $\ell$ 层的阈值为 $\alpha_\ell$，每个父桶尝试 $t_\ell$ 个子桶，$\ell=0,\ldots,k-1$；$b_{\min}$ 是转为直接枚举的大小阈值。

本篇的 $t_\ell$ 均指**每个父桶的分支数**。若完整展开且不提前结束，第 $\ell$ 次过滤后生成的桶总数为 $\prod_{h=0}^{\ell}t_h$。

下面的流程逐个生成、处理并释放子桶。桶内只保存原向量编号，输入池在本轮搜索中保持不变：

~~~text
Search(I, ℓ):                       # 初始调用 Search({1,...,N}, 0)
    如果 |I| < 2：
        返回

    如果 ℓ = k 或 |I| ≤ b_min：
        对 I 中每个无序对 i < j：
            σ ← 1（若 〈x_i,x_j〉 ≥ 0），否则 −1
            w ← x_i − σ·x_j

            如果 0 < ||w|| < max(||x_i||, ||x_j||)：
                输出 (i, j, w)
        返回

    重复 t_ℓ 次：
        c ← 在原 s 维单位球面上独立均匀采样
        J ← {i ∈ I : |〈u_i,c〉| ≥ α_ℓ}
        Search(J, ℓ + 1)
        释放 J
~~~

此处沿用第 19 篇“缩短两者中较长者”的判据。接入具体筛法时，可以换成外层规定的目标长度和接纳规则。

这个固定输入版本允许跨桶重复检查和输出，便于分析。实际实现可能在收集一批候选后更新数据库；更新后的搜索应视为新状态，不能继续套用旧池中的固定源对统计。

## 3. 桶内的条件分布

沿一条路径经历若干过滤后，桶对应的方向区域为

$$
A_\ell
=
\bigcap_{h=0}^{\ell-1}
\{u\in S^{s-1}:|\langle u,c_h\rangle|\ge\alpha_h\}.
$$

它是多个双侧球帽的交集。不同路径的中心不同，对应的区域也不同。

在球面均匀输入模型下，固定这些过滤器后，保留下来的方向服从限制在 $A_\ell$ 内的分布。若下一过滤区域为 $F$，且 $\mu(A_\ell)>0$，则

$$
\Pr[U\in F\mid U\in A_\ell]
=
\frac{\mu(A_\ell\cap F)}{\mu(A_\ell)},
$$

其中 $\mu$ 是球面面积测度。这个条件比例通常不能用 $\mu(F)/\mu(S^{s-1})$ 替代。

**筛选没有改变一对给定向量的夹角，改变的是“从桶内抽取一对向量”时的夹角分布。**

例如，仅看一个单侧球帽，将两条单位向量写成

$$
u=ac+\sqrt{1-a^2}\,\xi,\qquad
v=bc+\sqrt{1-b^2}\,\eta,
$$

其中 $a,b\in[\alpha,1)$，$\xi,\eta$ 是 $c^\perp$ 中的单位向量。由内积展开，

$$
\langle u,v\rangle
=
ab+\sqrt{(1-a^2)(1-b^2)}\,\langle\xi,\eta\rangle.
$$

等长向量的减法约化条件 $\langle u,v\rangle>1/2$ 因而等价于

$$
\langle\xi,\eta\rangle
>
\frac{1/2-ab}{\sqrt{(1-a^2)(1-b^2)}}.
$$

共同的中心分量影响了剩余方向需要满足的条件。只知道桶大小，无法完整描述桶内的配对几何；多层后还需要考虑多个约束的共同作用。这些等式是直接的几何分解，不要求采用某个启发式分布。

同时，要分清随机性来自哪里：若固定当前向量，再独立均匀抽取一个全空间中心，则无论它此前怎样入桶，单点通过率仍为 $2p_s(\alpha)$；固定向量对的共同通过率也仍由其原夹角决定。

因此，“桶内分布改变”不意味着所有单次过滤公式都失效。需要重新分析的是桶内随机向量对的平均行为，以及依赖父桶选择中心、限制中心方向等具体方案。

## 4. 重复命中与整棵树的覆盖

设实际形成的叶子集合为 $\mathcal L$，叶子 $\lambda$ 中的编号集合为 $I_\lambda$。完整枚举叶子内部无序对时，

$$
C
=
\sum_{\lambda\in\mathcal L}\binom{|I_\lambda|}{2}
=
\sum_{i<j}m_{ij},
\qquad
m_{ij}
=
\sum_{\lambda\in\mathcal L}
\mathbf 1\{i,j\in I_\lambda\}.
$$

沿用第 19 篇，记 $E$ 为固定输入池中的有效源对集合，则

$$
H=\sum_{(i,j)\in E}m_{ij},
\qquad
U=\sum_{(i,j)\in E}\mathbf 1\{m_{ij}>0\}.
$$

$H$ 统计包含重复的有效命中，$U$ 统计不同有效源对。增加叶子数量可能同时增加覆盖与重复；不同源对仍可能产生相同的新向量。

尤其需要注意：**共享父桶的叶子，其命中事件通常不独立。**

考虑一个恰好两层、没有提前终止的模型。每个节点都使用新的独立均匀中心，固定一对夹角为 $\theta$ 的向量，令 $q_0,q_1$ 分别为两层的共同通过率。根节点尝试 $t_0$ 个父桶，每个父桶尝试 $t_1$ 个子桶。

该源对在叶子中的期望出现次数为

$$
\mathbb E[m_{ij}]
=
t_0t_1q_0q_1.
$$

但至少命中一个叶子的概率是

$$
\boxed{
P_{\mathrm{cov}}
=
1-
\left(
1-q_0\left[1-(1-q_1)^{t_1}\right]
\right)^{t_0}.
}
$$

推导只需两步：先通过一个父桶，概率为 $q_0$；在此前提下，至少通过它的一个子桶，概率为 $1-(1-q_1)^{t_1}$。最后对独立的顶层分支计算至少一次成功。

不能把它一般地写成 $1-(1-q_0q_1)^{t_0t_1}$，因为同一父桶下的 $t_1$ 条路径共享第一次过滤。增加这些子桶，无法补回在该父桶入口已经丢失的源对。

这个公式由上述两层模型直接推得。若子层中心依赖父桶内容，或采用结构化、相关的中心，需要使用相应的条件概率重新计算。

## 5. 建桶、叶子检查与驻留空间

记实际递归树的内部节点集合为 $\mathcal V$。对节点 $v$，父桶大小为 $b_v$，尝试的子桶数为 $t_v$。

若每个子桶都直接扫描父桶，并用 $s$ 维内积检查成员，主要算术成本为

$$
T_{\mathrm{filter}}
=
O\!\left(s\sum_{v\in\mathcal V}t_vb_v\right),
\qquad
T_{\mathrm{pair}}
=
O\!\left(s\sum_{\lambda\in\mathcal L}
\binom{|I_\lambda|}{2}\right).
$$

前式统计每层建桶，后式统计叶子检查。候选去重、数据库更新与数据移动还需另计。

增加一层是否有利，取决于：**新增的过滤成本，能否由减少的两两检查成本补偿，并维持所需覆盖。** 桶变小本身不足以判断总时间是否下降。

桶大小的波动也会影响成本。对随机桶大小 $B$，

$$
\mathbb E\!\left[\binom B2\right]
=
\frac{(\mathbb E B)^2-\mathbb E B+\operatorname{Var}(B)}{2}.
$$

只用平均桶大小代入平方，会漏掉方差贡献。

空间成本取决于处理顺序。对第 2 节的深度优先流程，临时成员引用主要来自当前递归路径上的桶：

$$
M_{\mathrm{idx}}
=
O\!\left(
\max_{\text{执行时刻}}
\sum_{I\in\text{当前路径}}|I|
\right).
$$

若桶沿路径按固定比例收缩，这部分为 $O(N)$；原始向量坐标另需 $O(sN)$ 空间，中心、递归状态和候选缓冲也应计入。一次保存全部兄弟桶，或保存全局已检查源对集合，会改变这个空间模型。

实际实现还可以把若干中心组成一批：顺序读取父桶中的向量，一次完成多个过滤测试。内积测试数量没有因此消失，但读取的数据可以被复用，小桶也更容易放入较快的存储层。流式访存与分层桶大小的关系可参见 [Zhao–Ding–Yang，§4.2，所链接 PDF 第 9–10 页](https://csrc.nist.gov/csrc/media/events/2025/sixth-pqc-standardization-conference/sieving%20with%20streaming%20memory%20access.pdf)。

## 6. 原始 BGJ 的复杂度从何而来

先抽象出两个概率：

- $p$：固定向量通过一个随机过滤器的概率。
- $q$：处于目标夹角的固定向量对共同通过该过滤器的概率。

用典型子桶大小 $pb$ 代替实际大小，忽略成功率放大因子，并取约 $1/q$ 个子桶，可以写出示意递推

$$
T(b)
\approx
\frac1q\bigl(T(pb)+a_fb\bigr),
$$

其中 $a_f$ 是一次单向量过滤的成本，包含其内积计算。

若递归项表现为 $b^d$，代入得到

$$
\frac1q(pb)^d=b^d,
\qquad
\boxed{
d=\frac{\ln(1/q)}{\ln(1/p)}.
}
$$

当 $q>p^2$ 时，$d<2$：有效对共同通过的概率，高于两个独立通过率的乘积，因而有机会获得次二次搜索。

这个推导解释了概率比如何进入复杂度。它还依赖典型桶大小、递归深度与成功率控制，不能单凭 $p,q$ 就断言任意多层实现的运行时间。

BGJ15 在其列表大小启发式与渐近参数选择下，将 $60^\circ$ 目标角对应的列表规模指数推向 $d=3/2$。配合经典两向量筛法的列表尺度，

$$
N=(4/3)^{s/2+o(s)},
$$

相应时间、空间尺度为

$$
T=(4/3)^{3s/4+o(s)},
\qquad
S=(4/3)^{s/2+o(s)}.
$$

它们的二进制指数系数分别为 $0.311278\ldots$ 和 $0.207518\ldots$。参见 [BGJ15，§3 的 Heuristic 1、§3.1 的递推式与 Theorem 1、§3.2 的 Theorem 2](https://eprint.iacr.org/2015/522.pdf)。

这些是原论文模型中的启发式渐近尺度。具体的 bgj1、bgj2、bgj3 需要根据过滤器、层数、参数与实际桶分布单独分析；也不能把第 21 篇 BDGL 的时间指数直接移植到任意球帽递归实现。

## 7. 多层参数怎样比较

需要联合选择的参数包括：层数 $k$、各层阈值 $\alpha_\ell$、每个父桶的分支数 $t_\ell$、直接枚举阈值 $b_{\min}$，以及同时处理的桶批量。

提高阈值通常减少成员，却也降低目标对的共同通过率；增加分支提高覆盖，同时增加建桶与重复检查。增加层数还会改变条件几何和数据访问方式，因此适合在相同搜索质量下比较完整成本。

对固定输入池，可以先按三个方面记录：

- **桶的规模：** 各层桶大小分布、成员引用总数，以及叶子内部的检查次数。
- **搜索的效果：** 含重复的有效命中 $H$、不同有效源对 $U$，再单独记录不同候选向量与实际接纳数量。
- **实际的成本：** 过滤、配对检查、去重与更新的时间，以及峰值内存和主要数据移动量。

若无法得到全部有效对作为覆盖率分母，可以使用可完整枚举的小规模实例，或明确标注抽样估计；不能把“命中次数更多”直接解释为“覆盖更好”。

从概率模型进入实现时，还要核对中心的来源。例如，G6K 的 bgj1 从当前数据库中选择中心，并利用中心与桶成员之间的约化机会；这与本篇独立球面中心的固定输入模型有所区别。参见 [G6K，kernel/bgj1_sieve.cpp 的算法说明，检索于 2026-10-16](https://github.com/fplll/g6k/blob/master/kernel/bgj1_sieve.cpp)。

本篇建立的基线是：递归分桶流程、条件概率、源对覆盖，以及完整成本计数。后续阅读论文时，可以据此分别整理多层参数优化、重复源对处理和平台实现带来的增量。

## 引用此笔记

- [00 概览与阅读路线](/knowledge/lattices-overview/)
- [23 多层分桶的参数选择与优化](/knowledge/multilevel-bucketing-optimization/)
- [24 重复配对、去重与有效覆盖](/knowledge/duplicate-pairs-and-effective-coverage/)
- [28 BGJ 筛法的流式访存组织](/knowledge/bgj-streaming-memory-organization/)