💬 NLP

Constrained Adaptive Rejection Sampling

本文介绍了约束自适应拒绝采样（Constrained Adaptive Rejection Sampling, CARS），这是一种通过利用前缀树（trie）自适应地剪枝无效延续，从而在严格约束下增强语言模型生成样本效率的方法，该方法在保持原始分布的同时，相比现有的贪婪或标准拒绝采样方法，提升了接受率和多样性。

原作者： Paweł Parys, Sairam Vaidya, Taylor Berg-Kirkpatrick, Loris D'Antoni

发布于 2026-06-04

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Paweł Parys, Sairam Vaidya, Taylor Berg-Kirkpatrick, Loris D'Antoni

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在教一位非常有才华但有点随性的厨师（即语言模型）烹饪一道特定的复杂菜肴（即有效输出），而这道菜必须遵循一本严格的食谱（即约束条件）。这位厨师擅长即兴发挥，但他们经常忽视规则，加入一些会让菜肴变得难以下咽或在结构上无法实现的食材。

这篇论文介绍了一种名为 CARS（约束自适应拒绝采样）的新方法来解决这个问题。为了理解为什么 CARS 特别，让我们来看看两种旧的解决方法，以及为什么它们都失败了。

旧的方法：两种有缺陷的策略

1. “扔掉重做”法（拒绝采样/Rejection Sampling）
想象一下，厨师做了一顿完整的饭菜，你检查了食谱，如果发现不对，你就把整锅菜扔进垃圾桶，并要求他们重新开始。

问题所在： 如果食谱非常严格（比如一种复杂的编程语言），厨师可能要做出 999 顿坏掉的饭菜才能得到一顿正确的。你浪费了大量的精力和时间去扔掉食物。
优点： 最终端上桌的那一顿饭是完美的，完全符合厨师原本的意图。

2. “悬空之手”法（贪婪解码/Greedy Decoding）
想象一下，你站在厨师肩膀后面盯着他。每当他伸手去拿一个违反规则的食材时，你就拍掉他的手，强迫他选择另一个。

问题所在： 厨师停止了自然的烹饪过程。他们变得像机器人一样，只会挑选“安全”的食材。最终做出的饭菜虽然可以食用，但不再具有厨师独特的风格了；它被扭曲了。
优点： 你能非常快速地得到一份有效的饭菜，几乎没有浪费。

新的解决方案：CARS（“聪明的记录员”）

作者提出了 CARS，它结合了两者的优点：既保留了厨师的自然风格（保真度），又避免了在不可能的菜肴上浪费时间（效率）。

以下是 CARS 的工作原理，使用**“禁忌路径库”**这一类比：

开始烹饪： 厨师开始自然地烹饪，就像“扔掉重做”法那样。
犯错： 假设厨师试图做一个以 0++ 开头的句子（这在数学上是无效的）。系统捕捉到了这一点。
聪明的笔记： 系统并没有仅仅扔掉这一个特定的句子，而是打开了一个 Trie（一种特殊的树状结构笔记本）。它写下：“任何以 0++ 开头的菜肴都是不可能实现的。”
连锁反应： 至关重要的是，系统还意识到，任何以 0+ 开头且紧跟另一个 + 的菜肴也是注定失败的。它将这些整个分支都标记为“禁忌”。
未来的烹饪： 下次厨师开始烹饪时，他们会查阅这个笔记本。如果他们试图选择一个会导致“禁忌”分支的食材，系统会在他们浪费时间做完整顿坏饭之前，轻轻地引导他们避开。
结果： 厨师再也不会做出坏掉的饭菜。他们烹饪得更快了，因为他们不再把时间浪费在死胡同里；但当他们烹饪时，依然保持着自己原汁原味的风格，而不是被迫模仿。

为什么这意义重大？

论文在三个需要生成大量不同有效内容的真实场景中测试了 CARS：

程序模糊测试（寻找 Bug）： 想象尝试通过喂给软件程序数百万个不同的输入来破坏它。你需要输入既是有效代码，又足够奇特到能让系统崩溃的内容。CARS 比旧方法找到了更多的 Bug（覆盖了更多的代码行），因为它能更快速地生成有效且多样化的输入，而不会陷入停滞。
分子发现（设计药物）： 化学家需要生成有效的化学结构。CARS 生成有效、多样化分子的速度比以往的方法快得多，节省了大量的计算能力。
Text-to-SQL（将问题转化为数据库查询）： 当向数据库提问时，答案必须是一个完美的 SQL 查询。CARS 用最少的尝试次数产生了最准确的查询。

核心结论

可以将 CARS 看作是一个学习过滤器。

旧方法要么通过扔掉错误的尝试来浪费时间（拒绝采样），要么通过强迫 AI 过于僵化来破坏质量（贪婪解码）。
CARS 从每一次错误中学习。它构建了一张“死胡同”地图，这样 AI 就永远不会再走错路。这意味着你既能得到完美有效的结果，同时保留 AI 自然的声音，而且由于不再把能量浪费在不可能的路径上，你获得它们的速度也更快了。

该论文声称，这是第一个对于这类严格任务既能做到精确（完美准确）又能做到高效（快速）的方法。

技术摘要：约束自适应拒绝采样 (CARS)

1. 问题陈述

语言模型（LM）正越来越多地应用于需要满足严格语义或语法约束的应用场景，例如生成符合语法规则的代码、遵循数据模式（Schema）或生成化学结构。约束生成的核心挑战在于平衡两个相互竞争的需求：

保真度（Fidelity）： 样本必须严格遵循语言模型在给定约束下的条件分布（ $P_L$ ），而非其近似分布。
效率（Efficiency）： 该方法必须最小化生成有效样本所需的语言模型前向传播次数。

现有方法可分为三类，每种方法都无法同时满足上述两个标准：

精确但低效： 标准拒绝采样（Rejection Sampling, RS）能产生来自真实约束分布的无偏样本，但在结构化领域（如接受率 <1%）会丢弃绝大多数候选样本，导致计算成本极高。
高效但有偏： 贪婪约束解码（Greedy Constrained Decoding, GCD）通过在生成过程中对无效 Token 进行掩码处理来强制执行有效性。虽然高效，但它会证明性地扭曲语言模型的条件分布，从而通常会导致下游性能下降，并可能出现无法终止的情况。
渐近精确但不稳定： MCMC 或序列蒙特卡洛（Sequential Monte Carlo, SMC）等方法在极限情况下收敛到正确的分布，但没有原则性的停止规则。早期样本可能存在任意偏差，且效率高度依赖于超参数调优和达到稳定所需的迭代次数。

本文认为，目前缺乏一种既能实现精确性（保留真实分布）又具备摊销效率（在不牺牲保真度的前提下随时间提高效率）的算法，特别是在需要多样化有效样本集的领域，如程序模糊测试（Fuzzing）和分子发现。

2. 方法论：约束自适应拒绝采样 (CARS)

CARS 是一种精确采样算法，它结合了拒绝采样的保真度与自适应剪枝的效率。它基于自适应拒绝采样（Adaptive Rejection Sampling, ARS）构建，并通过利用约束的结构特性，不仅剪枝被拒绝的样本，还剪枝整个无效延续的族群，从而对 ARS 进行了扩展。

核心机制

该算法维护一个在采样过程中发现的无效前缀（ $W$ ）集合。它使用 Trie（前缀树） 数据结构来存储这些前缀，并动态重塑采样分布（ $R_W$ ）以避开这些前缀。

初始化： 算法从空的前缀集合开始（ $W = \emptyset$ ）。
采样： 在每次迭代中，算法从重加权分布 $R_W$ $R_{W}$ 中采样一个序列。该分布是通过对原始语言模型分布 $P$ $P$ 进行归一化得到的，其中仅考虑不属于 $W$ $W$ 中任何前缀的序列。
- 形式上，对于前缀 $u$ ，其扩展为有效序列的概率被追踪为 $p_u$ 。如果 $u$ 延伸出了已知的无效前缀，则 $p_u = 0$ 。
- 给定前缀 $u$ 时，Token $a$ 的采样概率进行调整： $R_W(ua | u) = P(ua | u) \cdot \frac{p_{ua}}{p_u}$ 。
自适应剪枝（关键创新）： 当生成一个样本时，CARS 不仅仅记录被拒绝的字符串（如标准 ARS 那样）。相反，它会识别出生成的序列中所有违反约束的前缀及其所有的无效延续。
- 具体而言，如果生成了序列 $w$ ，CARS 会将 $w$ 的最短前缀 $u$ （若 $u$ 不在合法语言 $L$ 中）添加到 $W$ 中。
- 至关重要的是，它还会添加所有扩展项 $ua $（其中$ a$ 是一个 Token），使得 $ua \notin prefix(L)$ 。
- 这一过程有效地从未来的抽取中“减去”了整个无效子树的概率质量。
更新： 更新 Trie 树以反映新的无效前缀，并将概率值（ $p_u$ ）向上游传播。这确保了未来的样本永远不会再次访问这些无效路径，从而单调地提高接受率。

理论特性

精确性： CARS 精确地从目标约束分布 $P_L$ 中进行采样。重加权机制确保了概率质量在有效序列之间得到正确的重新分配。
单调性： 随着 $W$ 集合的增长，接受率呈单调提升。
收益递减： 每个样本移除的预期概率质量是非增的。这提供了一个实用的启发式策略：一旦 Trie 树停止移除显著的概率质量，即可将分布“冻结”，以便进行后续采样而不产生明显的效率损失。

3. 主要贡献

算法设计： 引入了 CARS，这是一种新的约束语言模型生成算法，通过利用约束结构来剪枝无效前前缀的延续，实现了精确性与实际效率的结合。
理论保证： 证明了 CARS 从真实的约束分布中采样，并且其自适应更新会单调增加产生有效样本的概率。
实证验证： 在多个领域中证明了 CARS 在采样效率（每个有效样本所需的语言模型前向传播次数更少）和样本多样性方面优于现有方法。

4. 实验结果

作者在四个模型（Llama-3.1-8B/70B, Qwen2.5-7B/14B）以及三个不同领域上对 CARS 进行了评估：

A. 基于语法的模糊测试 (Grammar-Based Fuzzing)

任务： 生成多样化、有效的程序种子（JSON, SQL, XML），以最大化模糊测试器的代码覆盖率。
结果： CARS 实现 100 个有效样本的目标时，所需的生成次数显著低于 RS、ARS 和 RSFT。例如，在没有语法提示的 XML 生成任务中，CARS 仅需约 440 次生成，而 RS/ARS（未能达到目标）则需要超过 2,000 次。
影响： 与 GCD（7,115 行）和 MCMC（7,965 行）相比，CARS 生成的种子带来了更高的行覆盖率（~7,985 行），这表明分布保真度可以转化为更好的下游性能。

B. 分子合成 (Molecular Synthesis)

任务： 为特定化学类别（丙烯酸酯、链增长剂、异氰酸酯）生成有效的 SMILES 字符串。
结果： 为了生成 100 个有效分子，CARS 比 RS 少了 4.3 倍的样本，比 ARS 少了 1.3 倍。它在精确方法中实现了最高的有效性和多样性得分。
保真度： CARS 的 KL 散度比 MCMC 低 1.5 倍，比 AWRS 低 1.8 倍，表明其对真实分布的遵循程度更高。

C. Text-to-SQL 生成

任务： 从自然语言问题生成 SQL 查询（Spider 数据集）。
结果： CARS 在所有方法中实现了最高的执行准确率（0.578）。它比 RS 少了 1.85 倍的样本，比 ARS 少了 1.28 倍。
对比： 虽然像 GCD 这样的近似方法更快（1.00 样本/查询），但其准确率较低（0.525）。CARS 提供了最佳的权衡，在准确率上超越了 GCD，同时仅需 1.1 倍的样本量。

5. 意义与主张

论文声称 CARS 为从语言模型的精确约束分布中进行采样设定了新的基准（SOTA）。其重要性在于解决了精确性与效率之间的根本权衡：

不同于 RS，CARS 在实践中具有摊销效率，使其适用于需要大量多样化样本的任务。
不同于 GCD 及其他近似方法，CARS 保留了真实的语言模型分布，确保下游性能（如模糊测试覆盖率、化学多样性、SQL 执行准确率）不会因分布扭曲而受损。

作者指出，当约束是可前缀检查（prefix-checkable）且对剪枝具有高度信息量（例如上下文无关文法）时，CARS 的效果最为显著。在无效输入空间由许多独立的低概率子空间组成且缺乏共享前缀的情况下，CARS 相对于 ARS 的增益可能较为有限，此时近似方法可能仍是实际的选择。然而，对于大多数结构化生成任务，CARS 提供了一个原则性的、精确且高效的解决方案。