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

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

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

1. 先规定优化目标

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

对固定输入池，可以在期望覆盖与峰值内存约束下，最小化耗时的期望：

\min_{\eta}\ \mathbb E[T(D;\eta)], \qquad \text{s.t.}\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$ 是这些中心怎样分批执行。 在中心集合固定、全部分支都完成时，改变批量不改变理论覆盖；提前停止或修改过滤规则时，则需重新评估。

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

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

沿用球面 LSF的双侧球帽过滤器，记

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 节的公式是上述模型下的直接计数与概率推导。对桶内自选中心、相关中心、提前终止等实现，应回到BGJ 递归分桶的实际递归树统计，不能直接套用这些闭式表达。

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)},

暂用单侧球帽记号，只比较维数的指数主项。双侧过滤的常数因子不改变本节结论。由球面 LSF，对固定阈值 $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$ [1, pp. 73–74]。

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

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

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

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

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

例如，Zhao–Ding–Yang 的实现为 bgj1 选取 $\alpha_0=0.325$ ，为 bgj3 选取 $(0.200,0.210,0.280)$ ；作者通过粗网格搜索与局部搜索获得这些配置 [2, pp. 6–7]。它们是所测试实现中的选参结果，不能直接作为其他平台的最优值。

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

$b_{\min}$ 应对应实际实现中“继续过滤”和“直接枚举”的成本交叉区域。桶太小可能使向量化、GPU 并行或数据搬运难以摊薄，因此减少配对次数不一定减少运行时间 [1, pp. 102–105]。

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

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

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

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

流式实现中，各层桶大小与存储层级共同影响吞吐 [2, pp. 9–11]。因此，理论操作数相近的配置，仍可能有不同的实际时间。估算时可按各层实测吞吐，将过滤与配对计数分别换算为时间，再加入尚未计入的去重、更新等开销。

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

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

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

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

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

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

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

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

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

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

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

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

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

参考文献

1. Wessel P. J. van Woerden. Lattice cryptography, from cryptanalysis to new foundations. 2023. 原文.

2. Ziyu Zhao, Jintai Ding, and Bo-Yin Yang. Sieving with streaming memory access. IACR Transactions on Cryptographic Hardware and Embedded Systems. 2025. DOI.

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

#1. 先规定优化目标

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

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

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

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

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

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

#参考文献