两层级softmax采样被证明系统性偏置，S-2LS与SD-2LS修正后KL散度最多降低四个数量级
核心概要
该工作证明两层级softmax（2LS）采样因忽略簇规模不均衡与簇内相似度离散度而系统性错配簇权重，破坏softmax对等相似度项的等概率不变性；作者提出S-2LS（按簇规模加权）与SD-2LS（再按簇内协方差做二阶矩修正），在五个大规模数据集上以与2LS相当或略高的开销获得更接近精确softmax的采样分布。
Figure 1 : Sampling ratio on VK-LSVD ( τ = 0.1 \tau=0.1 ) as a function of cluster size, averaged over queries. Standard 2LS undersamples large clusters and oversamples small ones relative to exact softmax ( R i ( N ) ( q ) ≠ 1 R_{i}^{(N)}(q)\neq 1 , p-value p < 0.01 p<0.01 ), while S-2LS and SD-2LS correct these biases.
arXiv深度剖析
论文首次形式化刻画了2LS采样的系统性偏置：采样比只依赖项目所属簇而与相似度无关，因此同一簇内所有项目被同一因子过采样或欠采样，等相似度项目在不同簇中会得到不同概率。 此前2LS被广泛采用但偏置未被正式刻画，最接近的只是Tranheden等人在簇规模不均衡下经验性观察到的效率损失。 以Proposition 1的解析推导给出，并在VK-LSVD等五个数据集上以采样比随簇规模和簇内方差的变化图经验验证。
偏置沿两条互补轴产生：2LS忽略簇规模不均衡，相对真实softmax质量过采样小簇、欠采样大簇；同时忽略簇内相似度离散度，欠采样项目-查询相似度方差大的簇。 把偏置分解为规模与离散度两个可分别修正的来源，并给出高斯近似下简化的比值形式。 Proposition 2与Proposition 3在i.i.d.混合分布假设下用大数定律给出渐近结果；实验中S-2LS修正规模偏置后，残余的离散度偏置被单独隔离出来观察。
S-2LS在簇级得分中引入簇规模，采样复杂度与2LS相同；SD-2LS进一步用簇内协方差矩阵的二阶矩近似矩生成函数，额外引入O(Kd²)开销，在高斯假设下可渐近恢复精确softmax。 两种修正均为即插即用替换，S-2LS不增加成本，SD-2LS以适度开销换取更强保证。 Proposition 4、5、6给出渐近分析；实验显示S-2LS延迟与2LS在测量噪声内一致，SD-2LS在高维数据集上仅慢约1–2倍、低维上最多约3倍。
在五个大规模数据集上，SD-2LS在所有自然语料上取得最低KL，相对2LS的增益从低温下的1–2个数量级到高温下的1–4个数量级；S-2LS稳定次优，在推荐最相关的低温区间已把KL降低1–2个数量级。 top-k截断即使在低温下误差也很大，层级softmax在YAMBDA上明显更差，而修正方法在保真度-延迟权衡上严格更优。 Table 1跨五个数据集与三个温度报告KL；Table 2报告单线程CPU逐查询延迟；合成数据Synth-balanced与Synth-unbalanced用于隔离簇规模不均衡的作用。
启示与展望
该结果面向以固定离线划分、在线重复采样的推理场景，例如推荐系统中对百万级候选项目的采样与语言模型的大词表生成；此时主导成本是固定划分下的推理复杂度，子线性优势成立。S-2LS适用于簇高度不均衡且延迟敏感的场景；SD-2LS适用于簇内离散度不可忽略且资源允许的场景，论文指出在K远小于N时额外开销可被摊销。作者建议S-2LS无条件替代标准2LS，SD-2LS在簇内方差非平凡时优先使用。
SD-2LS依赖对相似度矩生成函数的截断展开，论文指出在高偏度或高峰度的嵌入分布下二阶近似可能不够准确，更高阶修正留作未来工作。偏置分析针对2LS，作者指出该错配在树状层级softmax的每一层会重复并沿路径乘性累积，逐节点修正尚未展开。实验在单线程CPU、顺序查询下测量延迟，其他硬件与并发设置下的开销表现仍需读者自行评估。此外，正文图表受篇幅限制以VK-LSVD为主，其余四个数据集的完整分析放在附录C。