整理日期：2026-10-16。
适用范围：球帽型 BGJ 多层分桶的参数建模、覆盖约束、成本估计与实验选参。
前置笔记：21 球面 LSF 与过滤器、22 BGJ 递归分桶与多层筛选。
第 22 篇说明了多层分桶怎样运行。本篇进一步讨论：怎样选择各层阈值、分支数和处理批量，使搜索在达到所需质量时尽量节省时间与空间。
符号说明： 本篇沿用19 筛法中的近邻搜索与分桶第 4 节和22 BGJ 递归分桶与多层筛选第 4 节的 \(C,H,U\)：\(C\) 统计全部候选对的检查次数，包含重复与无效对；\(H\) 统计含重复的有效对命中次数；\(U\) 统计至少被检查一次的不同有效源对数量。本篇另外用 \(F\) 表示“向量与中心”的过滤测试总次数，无论是否通过都计数。它不同于21 球面 LSF 与过滤器第 4 节中表示单个方向通过的过滤器数量的 \(F(u)\)，也不同于第 22 篇第 3 节表示过滤区域的 \(F\)。
1. 先规定优化目标#
固定维数 \(s\)、非零向量池 \(D=\{x_1,\ldots,x_N\}\) 和真实约化判据，记 \(E\) 为有效源对集合，\(U\) 为本轮至少检查过一次的不同有效源对数量。
一种适合分析固定输入池的目标是
其中 \(\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\) 层，不按桶大小提前枚举。
- 叶子完整检查内部无序对，跨叶子的重复检查保留。
沿用第 21 篇的双侧球帽过滤器，记
\(p_\ell\) 是固定向量通过一层过滤的概率，\(q_\ell(\theta)\) 是夹角为 \(\theta\) 的固定源对共同通过的概率。
第 3—4 节的公式是上述模型下的直接计数与概率推导。对桶内自选中心、相关中心、提前终止等实现，应回到第 22 篇的实际递归树统计，不能直接套用这些闭式表达。
3. 从参数计算过滤工作量与叶子检查#
记经过 \(\ell\) 层过滤后的桶总数为
令 \(Q_\ell\) 为该层全部桶的成员引用总数。同一向量进入多个桶时分别计数，则
空乘积取 \(1\)。指定路径上的单桶期望大小为 \(N\prod_{h<\ell}p_h\)，但全部桶的引用数还要乘以 \(B_\ell\)。因此，单桶变小并不代表总成员存储或总处理量减少。
若每个中心都扫描其父桶，令 \(F\) 为“向量与中心”的过滤测试总次数，则
对固定输入池，令 \(\theta_{ij}\) 为 \(u_i=x_i/\|x_i\|\) 与 \(u_j\) 的夹角。叶子中的无序对检查总次数 \(C\) 满足
理由是：固定源对沿一条路径进入叶子的概率为各层共同通过率之积，再对全部叶子和源对求和。这里使用期望的线性性，不要求不同叶子的命中事件独立。
这个表达保留了源对的夹角。一般不能用
替代它；只根据平均桶大小估算两两检查，会遗漏桶大小波动与共同过滤带来的相关性。
\(F\) 和 \(C\) 是两类操作的计数。直接计算内积时，主要算术量为 \(O(sF+sC)\)；中心生成、桶管理、去重、更新和数据移动仍需另计。总引用数的期望也不是峰值内存，后者取决于哪些桶同时驻留。
4. 用覆盖约束反推分支数#
固定一个夹角为 \(\theta\) 的源对。令 \(R_\ell(\theta)\) 表示：已知它共同进入第 \(\ell\) 层父桶，从这里出发，最终至少被一个叶子检查的概率。
到达叶子便会检查，所以
一个子分支成功，需要先共同通过该层过滤，再在其子树中成功。不同子分支使用独立的新中心，因此
于是，不同有效源对的期望覆盖数为
这把“至少命中一次”与第 3 节包含重复的检查次数区分开来。优化时同时需要两者。
以两层为例。固定一个目标角度 \(\theta_*\)，简记 \(q_\ell=q_\ell(\theta_*)\)。选定阈值和下层分支数 \(t_1\) 后，下层覆盖概率为
若要求该目标对的覆盖概率至少为 \(\rho\)，且 \(0<q_0r_1<1\)，则顶层最小分支数为
这给出一种直接的选参方式：枚举少量 \(t_1\)，由覆盖要求计算 \(t_0\)，再比较总过滤量、叶子检查和内存需求。
增加 \(t_1\) 会使 \(r_1\) 逐渐接近 \(1\)，收益递减；一个顶层分支的成功概率仍不超过 \(q_0\)。因此，各层分别取“约 \(1/q_\ell\) 个桶”并不自动给出整棵树的最优配置。
上述反推只针对选定的 \(\theta_*\)。等长模型常以 \(60^\circ\) 作为临界角度估计，边界本身不产生严格缩短；不等长输入与不同接纳规则，应按实际有效对分布检查总体覆盖。
5. 单层参照：阈值约 0.366 怎样得到#
先看单层、直接扫描全部中心的情形，作为多层选参的参照。
采用随机球面输入与经典池规模
暂用单侧球帽记号，只比较维数的指数主项。双侧过滤的常数因子不改变本节结论。由第 21 篇，对固定阈值 \(0<\alpha<\sqrt3/2\)，
这里 \(q\) 使用 \(60^\circ\) 临界目标角。要以固定常数概率覆盖该目标对，需要 \(t=\Theta(1/q)\) 个独立过滤器。
扫描中心的成本约为 \(sNt\)。对独立均匀的随机输入与一个固定球帽，两个输入同时进入的概率为 \(p^2\)，故全部桶的期望配对成本约为 \(sN^2tp^2\)。保留指数后，
低阈值时，桶大，配对检查占主导；阈值过高时，为补偿覆盖损失而增加的过滤器使建桶成本上升。在这个模型中，两项指数的平衡点给出最优指数：
因此，
对应的典型桶大小在指数尺度上约为 \(\sqrt N\)。这一单层基准可对照 Wessel van Woerden 博士论文《Lattice Cryptography, from Cryptanalysis to New Foundations》，§3.3 的 BGJ1 讨论，正文第 73–74 页。
第 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 页。
层数与直接枚举阈值。 新增一层会减少单个叶子的大小，也会增加过滤、建桶和管理工作。只有在维持所需覆盖时，总成本下降，新增层才有价值。
\(b_{\min}\) 应对应实际实现中“继续过滤”和“直接枚举”的成本交叉区域。桶太小可能使向量化、GPU 并行或数据搬运难以摊薄，因此减少配对次数不一定减少运行时间。GPU 实现中的这一现象可参见 van Woerden 博士论文，§4.3.3，正文第 102–105 页。
批量与驻留空间。 同时处理 \(g_\ell\) 个中心，可以让读入的父桶数据服务于多次过滤，提高数据复用；但需要容纳更多子桶与工作缓冲。
若每条桶成员记录占 \(w\) 字节、典型子桶大小为 \(b_{\ell+1}\)，则一批子桶的成员空间可粗估为
这只是容量规划的起点。实际峰值还要计入桶大小波动、同时运行的任务、祖先桶、向量坐标和候选缓冲，不能把平均值当作空间保证。
流式实现中，各层桶大小与存储层级共同影响吞吐，可参见 Zhao–Ding–Yang，§4.2 与 Table 2，所链接 PDF 第 9–11 页。因此，理论操作数相近的配置，仍可能有不同的实际时间。估算时可按各层实测吞吐，将过滤与配对计数分别换算为时间，再加入尚未计入的去重、更新等开销。
7. 一个由粗到细的选参流程#
理论模型适合缩小搜索范围，实际测量决定当前实现中的参数。可以按下面的流程组织：
输入：代表性输入池、目标搜索质量、硬件与内存预算
对少量候选层数 k：
粗搜索各层阈值 α_0, ..., α_{k-1}
对每组阈值：
计算或估计有限维的 p_ℓ、q_ℓ
用覆盖递推筛选分支数组合 t_0, ..., t_{k-1}
估计过滤工作量、叶子检查与驻留空间
保留成本较低的候选配置
对保留的配置：
测量不同批量 g_ℓ 与枚举阈值 b_min
在邻近的阈值和分支数上继续搜索
按真实执行流程重新检查覆盖与峰值内存
用多个随机种子重复实验：
比较同一质量目标下的总时间及波动
用其他代表性输入池核验效果
接入完整筛法，比较到达同一停止条件的总耗时
输出：当前测试范围内的最佳配置、适用条件与测量记录启用提前枚举、早停或数据库更新后，要重新测量实际流程，不能继续把完整树公式当作精确预测。
若无法枚举大池中的全部有效源对，可用小规模真实输入完整核验，或采用注明权重与误差的抽样估计。高维有效对可能很稀少，普通随机抽样没有命中，不能据此认为不存在有效对。
保存一次选参结果时，至少记录：
- 维数、池规模、输入状态、真实接纳规则与停止条件。
- 层数、各层阈值和分支数、处理批量、直接枚举阈值。
- 各层桶大小分布、\(F\)、\(C\)、\(H\)、\(U\)，以及实际接纳数量；估计值应注明方法。
- 分阶段时间、峰值内存、随机种子、硬件和代码版本。
本篇建立的选参顺序是：固定质量目标，用覆盖约束选择分支，联合比较全部成本，再由实测修正参数。 后续论文中的新参数、调度或硬件优化，可以围绕这套基线记录其新增收益与适用条件。