# 23 多层分桶的参数选择与优化

整理日期：2026-10-16。  
适用范围：球帽型 BGJ 多层分桶的参数建模、覆盖约束、成本估计与实验选参。  
前置笔记：[21 球面 LSF 与过滤器](/knowledge/spherical-lsf-and-filters/)、[22 BGJ 递归分桶与多层筛选](/knowledge/bgj-recursive-bucketing/)。

第 22 篇说明了多层分桶怎样运行。本篇进一步讨论：怎样选择各层阈值、分支数和处理批量，使搜索在达到所需质量时尽量节省时间与空间。

**符号说明：** 本篇沿用[19 筛法中的近邻搜索与分桶](/knowledge/nearest-neighbor-search-and-bucketing/)第 4 节和[22 BGJ 递归分桶与多层筛选](/knowledge/bgj-recursive-bucketing/)第 4 节的 $C,H,U$：$C$ 统计全部候选对的检查次数，包含重复与无效对；$H$ 统计含重复的有效对命中次数；$U$ 统计至少被检查一次的不同有效源对数量。本篇另外用 $F$ 表示“向量与中心”的过滤测试总次数，无论是否通过都计数。它不同于[21 球面 LSF 与过滤器](/knowledge/spherical-lsf-and-filters/)第 4 节中表示单个方向通过的过滤器数量的 $F(u)$，也不同于第 22 篇第 3 节表示过滤区域的 $F$。

## 1. 先规定优化目标

固定维数 $s$、非零向量池 $D=\{x_1,\ldots,x_N\}$ 和真实约化判据，记 $E$ 为有效源对集合，$U$ 为本轮至少检查过一次的不同有效源对数量。

一种适合分析固定输入池的目标是

$$
\min_{\eta}\ \mathbb E[T(D;\eta)],
\qquad
\text{满足}\quad
\mathbb E[U(D;\eta)]\ge\rho|E|,
\quad
M_{\mathrm{peak}}\le M_{\mathrm{budget}},
$$

其中 $\eta$ 是待选参数，$\rho\in(0,1)$ 是目标覆盖比例。期望针对算法的随机选择；峰值内存还要由实际执行方式与空间限制核验。

这里要求的是期望覆盖，不保证每次运行都达到 $\rho$。实验时需要同时观察覆盖率的波动。

对于完整筛法，也可以把目标改为“达到同一长度质量或饱和标准的总耗时”。它包含多轮搜索与数据库更新，不能仅由固定池上的覆盖率代替。

因此，比较参数前应固定输入状态、接纳规则和停止条件。含重复的有效命中 $H$、不同源对 $U$、不同新向量、实际接纳数量，应分别统计。

## 2. 参数的分工与分析模型

待选参数主要有：

- $k$：过滤层数。
- $\alpha_\ell$：第 $\ell$ 层阈值，控制过滤严格程度。
- $t_\ell$：每个父桶尝试的子桶数，控制搜索分支。
- $b_{\min}$：转为直接枚举的桶大小阈值。
- $g_\ell$：一次同时处理的中心数，满足 $1\le g_\ell\le t_\ell$。

这里 $\ell=0,\ldots,k-1$。**$t_\ell$ 是总共尝试多少个中心，$g_\ell$ 是这些中心怎样分批执行。** 在中心集合固定、全部分支都完成时，改变批量不改变理论覆盖；提前停止或修改过滤规则时，则需重新评估。

下面先使用一个便于计算的模型：

1. 输入池固定，每个节点的中心都在原 $s$ 维单位球面上独立均匀采样。
2. 每层参数固定，完整展开 $k$ 层，不按桶大小提前枚举。
3. 叶子完整检查内部无序对，跨叶子的重复检查保留。

沿用第 21 篇的双侧球帽过滤器，记

$$
p_\ell=2p_s(\alpha_\ell),
\qquad
q_\ell(\theta)
=2q_s(\alpha_\ell,\theta)
+2q_s(\alpha_\ell,\pi-\theta).
$$

$p_\ell$ 是固定向量通过一层过滤的概率，$q_\ell(\theta)$ 是夹角为 $\theta$ 的固定源对共同通过的概率。

第 3—4 节的公式是上述模型下的直接计数与概率推导。对桶内自选中心、相关中心、提前终止等实现，应回到第 22 篇的实际递归树统计，不能直接套用这些闭式表达。

## 3. 从参数计算过滤工作量与叶子检查

记经过 $\ell$ 层过滤后的桶总数为

$$
B_0=1,
\qquad
B_{\ell+1}=B_\ell t_\ell.
$$

令 $Q_\ell$ 为该层全部桶的成员引用总数。同一向量进入多个桶时分别计数，则

$$
\boxed{
\mathbb E[Q_\ell]
=N B_\ell\prod_{h=0}^{\ell-1}p_h.
}
$$

空乘积取 $1$。指定路径上的单桶期望大小为 $N\prod_{h<\ell}p_h$，但全部桶的引用数还要乘以 $B_\ell$。因此，单桶变小并不代表总成员存储或总处理量减少。

若每个中心都扫描其父桶，令 $F$ 为“向量与中心”的过滤测试总次数，则

$$
\boxed{
\mathbb E[F]
=\sum_{\ell=0}^{k-1}t_\ell\mathbb E[Q_\ell]
=N\sum_{\ell=0}^{k-1}
B_{\ell+1}\prod_{h=0}^{\ell-1}p_h.
}
$$

对固定输入池，令 $\theta_{ij}$ 为 $u_i=x_i/\|x_i\|$ 与 $u_j$ 的夹角。叶子中的无序对检查总次数 $C$ 满足

$$
\boxed{
\mathbb E[C]
=B_k\sum_{i<j}
\prod_{\ell=0}^{k-1}q_\ell(\theta_{ij}).
}
$$

理由是：固定源对沿一条路径进入叶子的概率为各层共同通过率之积，再对全部叶子和源对求和。这里使用期望的线性性，不要求不同叶子的命中事件独立。

这个表达保留了源对的夹角。一般不能用

$$
B_k\binom N2
\left(\prod_{\ell=0}^{k-1}p_\ell\right)^2
$$

替代它；只根据平均桶大小估算两两检查，会遗漏桶大小波动与共同过滤带来的相关性。

$F$ 和 $C$ 是两类操作的计数。直接计算内积时，主要算术量为 $O(sF+sC)$；中心生成、桶管理、去重、更新和数据移动仍需另计。总引用数的期望也不是峰值内存，后者取决于哪些桶同时驻留。

## 4. 用覆盖约束反推分支数

固定一个夹角为 $\theta$ 的源对。令 $R_\ell(\theta)$ 表示：已知它共同进入第 $\ell$ 层父桶，从这里出发，最终至少被一个叶子检查的概率。

到达叶子便会检查，所以

$$
R_k(\theta)=1.
$$

一个子分支成功，需要先共同通过该层过滤，再在其子树中成功。不同子分支使用独立的新中心，因此

$$
\boxed{
R_\ell(\theta)
=1-
\left[1-q_\ell(\theta)R_{\ell+1}(\theta)\right]^{t_\ell}.
}
$$

于是，不同有效源对的期望覆盖数为

$$
\mathbb E[U]
=\sum_{(i,j)\in E}R_0(\theta_{ij}).
$$

这把“至少命中一次”与第 3 节包含重复的检查次数区分开来。优化时同时需要两者。

以两层为例。固定一个目标角度 $\theta_*$，简记 $q_\ell=q_\ell(\theta_*)$。选定阈值和下层分支数 $t_1$ 后，下层覆盖概率为

$$
r_1=1-(1-q_1)^{t_1}.
$$

若要求该目标对的覆盖概率至少为 $\rho$，且 $0<q_0r_1<1$，则顶层最小分支数为

$$
\boxed{
t_0=
\left\lceil
\frac{\ln(1-\rho)}
{\ln(1-q_0r_1)}
\right\rceil.
}
$$

这给出一种直接的选参方式：枚举少量 $t_1$，由覆盖要求计算 $t_0$，再比较总过滤量、叶子检查和内存需求。

增加 $t_1$ 会使 $r_1$ 逐渐接近 $1$，收益递减；一个顶层分支的成功概率仍不超过 $q_0$。因此，各层分别取“约 $1/q_\ell$ 个桶”并不自动给出整棵树的最优配置。

上述反推只针对选定的 $\theta_*$。等长模型常以 $60^\circ$ 作为临界角度估计，边界本身不产生严格缩短；不等长输入与不同接纳规则，应按实际有效对分布检查总体覆盖。

## 5. 单层参照：阈值约 0.366 怎样得到

先看单层、直接扫描全部中心的情形，作为多层选参的参照。

采用随机球面输入与经典池规模

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

暂用单侧球帽记号，只比较维数的指数主项。双侧过滤的常数因子不改变本节结论。由第 21 篇，对固定阈值 $0<\alpha<\sqrt3/2$，

$$
p=(1-\alpha^2)^{s/2+o(s)},
\qquad
q=(1-\tfrac43\alpha^2)^{s/2+o(s)}.
$$

这里 $q$ 使用 $60^\circ$ 临界目标角。要以固定常数概率覆盖该目标对，需要 $t=\Theta(1/q)$ 个独立过滤器。

扫描中心的成本约为 $sNt$。对独立均匀的随机输入与一个固定球帽，两个输入同时进入的概率为 $p^2$，故全部桶的期望配对成本约为 $sN^2tp^2$。保留指数后，

$$
T_{\mathrm{model}}
=2^{o(s)}
\frac{N+N^2p^2}{q}.
$$

低阈值时，桶大，配对检查占主导；阈值过高时，为补偿覆盖损失而增加的过滤器使建桶成本上升。在这个模型中，两项指数的平衡点给出最优指数：

$$
Np^2=2^{o(s)}
\quad\Longrightarrow\quad
\sqrt{\frac43}(1-\alpha^2)=1.
$$

因此，

$$
\boxed{
\alpha
=\sqrt{1-\frac{\sqrt3}{2}}
=\frac{\sqrt3-1}{2}
\approx0.3660.
}
$$

对应的典型桶大小在指数尺度上约为 $\sqrt N$。这一单层基准可对照 [Wessel van Woerden 博士论文《Lattice Cryptography, from Cryptanalysis to New Foundations》，§3.3 的 BGJ1 讨论，正文第 73–74 页](https://ir.cwi.nl/pub/32912/32912E.pdf)。

第 21 篇中 $\alpha=1/2$ 的分析依赖高效定位过滤器，其建桶项近似 $Ntp$；本节逐个测试中心，建桶项为 $Nt$。成本模型不同，得到的阈值也不同。

$\alpha\approx0.3660$ 只是这里的单层渐近基准，不能据此要求多层的每个阈值都取同一个值。

## 6. 有限维数、层数与批量执行

实际选参还需要补上三类成本。

**有限维数与真实输入。** 指数主项省略了概率的多项式因子，也没有描述实际池的长度和角度分布。确定具体参数时，应使用有限维概率计算或与实现相符的测量，再核对真实覆盖。

例如，Zhao–Ding–Yang 的实现为 bgj1 选取 $\alpha_0=0.325$，为 bgj3 选取 $(0.200,0.210,0.280)$；作者通过粗网格搜索与局部搜索获得这些配置。它们是所测试实现中的选参结果，不能直接作为其他平台的最优值。参见 [《Sieving with Streaming Memory Access》，§3.2、Table 1 与脚注 11，所链接 PDF 第 6–7 页](https://csrc.nist.gov/csrc/media/events/2025/sixth-pqc-standardization-conference/sieving%20with%20streaming%20memory%20access.pdf)。

**层数与直接枚举阈值。** 新增一层会减少单个叶子的大小，也会增加过滤、建桶和管理工作。只有在维持所需覆盖时，总成本下降，新增层才有价值。

$b_{\min}$ 应对应实际实现中“继续过滤”和“直接枚举”的成本交叉区域。桶太小可能使向量化、GPU 并行或数据搬运难以摊薄，因此减少配对次数不一定减少运行时间。GPU 实现中的这一现象可参见 [van Woerden 博士论文，§4.3.3，正文第 102–105 页](https://ir.cwi.nl/pub/32912/32912E.pdf)。

**批量与驻留空间。** 同时处理 $g_\ell$ 个中心，可以让读入的父桶数据服务于多次过滤，提高数据复用；但需要容纳更多子桶与工作缓冲。

若每条桶成员记录占 $w$ 字节、典型子桶大小为 $b_{\ell+1}$，则一批子桶的成员空间可粗估为

$$
w\,g_\ell b_{\ell+1}.
$$

这只是容量规划的起点。实际峰值还要计入桶大小波动、同时运行的任务、祖先桶、向量坐标和候选缓冲，不能把平均值当作空间保证。

流式实现中，各层桶大小与存储层级共同影响吞吐，可参见 [Zhao–Ding–Yang，§4.2 与 Table 2，所链接 PDF 第 9–11 页](https://csrc.nist.gov/csrc/media/events/2025/sixth-pqc-standardization-conference/sieving%20with%20streaming%20memory%20access.pdf)。因此，理论操作数相近的配置，仍可能有不同的实际时间。估算时可按各层实测吞吐，将过滤与配对计数分别换算为时间，再加入尚未计入的去重、更新等开销。

## 7. 一个由粗到细的选参流程

理论模型适合缩小搜索范围，实际测量决定当前实现中的参数。可以按下面的流程组织：

~~~text
输入：代表性输入池、目标搜索质量、硬件与内存预算

对少量候选层数 k：
    粗搜索各层阈值 α_0, ..., α_{k-1}

    对每组阈值：
        计算或估计有限维的 p_ℓ、q_ℓ
        用覆盖递推筛选分支数组合 t_0, ..., t_{k-1}
        估计过滤工作量、叶子检查与驻留空间
        保留成本较低的候选配置

对保留的配置：
    测量不同批量 g_ℓ 与枚举阈值 b_min
    在邻近的阈值和分支数上继续搜索
    按真实执行流程重新检查覆盖与峰值内存

用多个随机种子重复实验：
    比较同一质量目标下的总时间及波动
    用其他代表性输入池核验效果
    接入完整筛法，比较到达同一停止条件的总耗时

输出：当前测试范围内的最佳配置、适用条件与测量记录
~~~

启用提前枚举、早停或数据库更新后，要重新测量实际流程，不能继续把完整树公式当作精确预测。

若无法枚举大池中的全部有效源对，可用小规模真实输入完整核验，或采用注明权重与误差的抽样估计。高维有效对可能很稀少，普通随机抽样没有命中，不能据此认为不存在有效对。

保存一次选参结果时，至少记录：

- 维数、池规模、输入状态、真实接纳规则与停止条件。
- 层数、各层阈值和分支数、处理批量、直接枚举阈值。
- 各层桶大小分布、$F$、$C$、$H$、$U$，以及实际接纳数量；估计值应注明方法。
- 分阶段时间、峰值内存、随机种子、硬件和代码版本。

本篇建立的选参顺序是：**固定质量目标，用覆盖约束选择分支，联合比较全部成本，再由实测修正参数。** 后续论文中的新参数、调度或硬件优化，可以围绕这套基线记录其新增收益与适用条件。

## 引用此笔记

- [00 概览与阅读路线](/knowledge/lattices-overview/)
- [24 重复配对、去重与有效覆盖](/knowledge/duplicate-pairs-and-effective-coverage/)
- [27 筛法的并行化与平台成本模型](/knowledge/parallel-lattice-sieving-and-platform-costs/)
- [28 BGJ 筛法的流式访存组织](/knowledge/bgj-streaming-memory-organization/)