返回资讯中心
外部精选
软件工程
#开发者实时流

Tim Vieira 提出测试随机化算法的新思路

来源标题:Ideas for Testing Randomized Algorithms

Tim Vieira 发文探讨如何测试随机化算法,尤其是概率推断中使用的采样算法。他通过一个具体的采样算法实现案例,展示从弱到强的多种测试策略,每种策略都能捕捉前一种遗漏的缺陷。最后还将该模块接入顺序蒙特卡洛流程,测试整条管线。

Hacker News 最新bacr2026/11/4 · 13 天前30 分钟阅读

以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。

2026年11月1日 作者:Tim Vieira 标签:采样算法测试 蒙特卡洛 程序追踪

随机算法很难测试。它们的输出在设计上就是不可预测的——而这种不可预测性是一种特性,而非缺陷。正是这一点赋予了它们诸如无偏性和计算效率之类的有用保证。但这也让它们难以捉摸:当一个随机程序每次运行时都给出不同的答案,你该如何检验它是正确的?

本文勾勒了一些思路,探讨如何思考随机算法的测试——尤其是我们用于概率推断的那类算法。我会给出一个具体的采样算法,并附上几种看似合理的实现——有些是正确的,有些存在不易察觉的缺陷——然后逐步构建越来越强大的测试策略,以便把它们区分开来。每一种策略都能捕获前一种策略漏掉的缺陷。

这个算法是一个小的构建模块。它的作用是在序列蒙特卡洛(SMC)中,为语言模型的受约束生成提议下一个 token。孤立地测试这个模块只是工作的一半,所以在最后我们会把它接入 SMC,测试整条流水线。

假设我们有一个定义在有限集 $\mathcal{X} = {1, \ldots, N}$ 上的分布 $p$,以及一个条件 $C \subseteq \mathcal{X}$(即“好”元素的集合)。我们想要从条件分布 $p(\cdot \mid C)$ 中采样。但不是返回一个普通样本,我们想要一个正确加权的样本 $(x, w)$——一个可用于无偏估计的样本-权重对。

下面这个算法,我们称之为 AWRS(来自 Lipkin et al., 2025),正是做这件事的。下面是论文中的伪代码:

思路是:运行两次拒绝采样。第一遍找到一个满足条件的样本 $x_c$,同时跟踪被拒绝的总概率质量 $\psi_0$。第二遍生成额外的拒绝以获得计数 $n$。权重 $(1 - \psi_0) / (n + 1)$ 将这两个信号——被拒绝的质量和拒绝计数——组合成对归一化常数 $Z$ 的无偏估计。在找到有效 token 之前的拒绝次数包含了关于 $Z$ 大小的信号,而按实际移除的概率质量(而不仅仅是计数)加权可以降低方差。

我们实现得对吗?这正是我们希望测试来回答的问题。为了让这个练习具体化,这里有四个 Python 实现。它们看起来都合理,但至少有一个存在缺陷。哪些是正确的?

每个变体都接受一个 draw 参数,默认从分类分布中采样。这是一个我们稍后会利用的钩子:在生产环境中它调用 RNG,但在测试中我们会把它替换成能让我们枚举每一种可能执行的东西。

def awrs_a(p, cond, draw=sample_categorical):
    p_cond = p.copy()
    n, psi = 0, 0
    xc0 = None
    for i in range(2):
        while True:
            q = p_cond / p_cond.sum()
            x = draw(q, context=('awrs', i, xc0))
            if cond(x):
                if i == 0:
                    xc0 = x
                break
            else:
                if i == 0:
                    psi += p_cond[x]
                p_cond[x] = 0
                n += 1
    return xc0, (1 - psi) / (n + 1)

变体 B

def awrs_b(p, cond, draw=sample_categorical):
    p_cond = p.copy()
    n, psi = 0, 0
    xc0 = None
    for i in range(2):
        while True:
            q = p_cond / p_cond.sum()
            x = draw(q, context=('awrs', i, xc0))
            if cond(x):
                if i == 0:
                    xc0 = x
                break
            else:
                if i == 0:
                    psi += p_cond[x]
                p_cond[x] = 0
                n += 1
    return xc0, (1 + psi) / (n + 1)

变体 C

def awrs_c(p, cond, draw=sample_categorical):
    p_cond = p.copy()
    n, psi = 0, 0
    xc0 = None
    for i in range(2):
        while True:
            q = p_cond / p_cond.sum()
            x = draw(q, context=('awrs', i, xc0))
            if cond(x):
                if i == 0:
                    xc0 = x
                break
            else:
                psi += p_cond[x]
                p_cond[x] = 0
                n += 1
    return xc0, (1 - psi) / (n + 1)

变体 D

def awrs_d(p, cond, draw=sample_categorical):
    p_cond = p.copy()
    n, psi = 0, 0
    xc0 = None
    for i in range(2):
        while True:
            q = p_cond / p_cond.sum()
            x = draw(q, context=('awrs', i, xc0))
            if cond(x):
                if i == 0:
                    xc0 = x
                break
            else:
                if i == 0:
                    psi += q[x]
                p_cond[x] = 0
                n += 1
    return xc0, (1 - psi) / (n + 1)

这些变体彼此之间只差一两行。我鼓励你在继续往下滚动之前仔细阅读它们,试着找出差异。比较四个变体中的 else 分支和 return 语句。

我们的任务是构建能捕获有缺陷实现的测试策略——理想情况下无需知道哪一行是错的。但在我们能测试任何东西之前,我们需要回答软件测试中最重要的一个问题:

没有规格说明,就无法测试代码。对于随机算法,规格说明来自理论——而把理论转化为可检验的性质是成功的一半。在本文中,我们会为每个算法不断回到这个问题。

对于 AWRS,规格说明是:它应返回一个样本-权重对 $(x, w)$,使得对于每个 $x' \in \mathcal{X}$,$w \cdot \mathbf{1}[x = x']$ 都是未归一化条件分布的无偏估计:

$$ \mathop{\mathbb{E}}_{(x,w) \sim \text{AWRS}} \left[ w \cdot \mathbf{1}[x = x'] \right]

p(x') \cdot \mathbf{1}[x' \in C] $$

右边是未归一化的目标——限制在条件 $C$ 上的 $p$,其归一化常数为 $Z = \sum_{x \in C} p(x)$。AWRS 满足这一点是 Lipkin et al., 2025 中的一个定理,我们将把它视为既定事实。我们的问题是代码是否做到了论文所证明的事情。

请注意,你常常需要调整定义、收窄或拓宽理论的适用范围,以适合你代码的预期用途。这是把理论转化为测试的一项重要技能。

现在我们有了一个可测试的定义,我们需要考虑方程中哪些东西我们可以计算,哪些东西我们需要估计。让我们构造一个具体的测试用例:

p = np.array([0.5, 0.3, 0.15, 0.04, 0.01])  # a distribution with a long tail
cond = np.array([True, False, True, False, False])  # the "good" elements
N = len(p)
Z = p[cond].sum()

(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →