From Decoding to Meta-Generation：Inference-time Algorithms for Large Language Models

生成的目标

记某个生成的结果集为 $S$, 用户会对其打分为 $A(S) \in \mathbb{R}$, 将其归一化处理后可以得到一个概率分布, 记作 $q_*$, 显然有 $q_*(S) \propto A(S)$. 设 $\mathrm{d} (p, q) \in \mathbb{R}$ 是某评价两分布接近程度的函数, $g$ 是生成器采样得到结果的分布, 我们不妨假定用户希望最小化 $\mathrm{d} (q_*, g)$. 但往往 $q_*$ 是几乎不可知的, 于是我们接下来考虑如何在不知道 $q_*$ 的情况下最小化 $\mathrm{d} (q_*, g)$.

直觉上, 对于一个训练好的语言模型, 我们认为它只需要针对一个输入, 从模型的输出分布中选择一个即可, 但事实并非如此. 一般生成使用的都是自回归模型, 每次根据上下文生成一个 token, 并将该 token 加入上下文中, 如此反复. 以下是几种生成的方式:

• 最大化: 考虑每次生成一个结果 $S$, 使 $v(S)$ 最大化, 其中 $v$ 是某个近似估计当前输出与 $q_*$ 拟合程度的函数.

• 采样: 每次从一个分布 $p_θ(\cdot | y_{:i−1})$ 中采样, 然后将其附加到上下文中.

• 从指定的目标分布中采样: 采样到某个结果的概率正比于其与分布 $q_*$ 的拟合程度.

Token 级别的生成算法

MAP Decoding Algorithm

最简单的 MAP 解码就是贪心地选择使当前 $p_\theta(y|x)$ 最大的 $y$, 但显然其不一定取到整个序列的最优解.

对 MAP 解码的一个优化是, 考虑保留排名前 $k$ 的结果分别加入上下文中用于下次迭代.

当然, MAP 解码有一些缺陷, 在实践中发现其倾向于产生较短的结果, 对于此, 可以通过将序列的对数概率除以其长度缓解, 但并不足以完全解决. 同时, 由于贪心算法本身的特性, 序列的生成也可能陷入循环. 而在误差方面, 由于最终结果空间中每条路径的概率都非常小, 一些偶然误差就会影响非常大, 结果就容易退化. 在一些情况下, 假设各个 token 的概率相近, 每次取概率最大的 token 可能导致最终结果路径偏离典型集非常远.

尽管 MAP 解码有许多缺点, 其在翻译等输入输出问题上表现得仍然很好, 原因可能是其结构无意中符合了人的思维模式. 另一方面, MAP 解码会极大地限制输出的多样性, 而保留排名前 $k$ 的结果又会导致极大的计算资源开销, 所以我们需要更高效从模型中进行采样的算法.

采样和适配器

MAP 解码的一个替代方法是不进行任何贪心操作, 直接从 $y \sim y_\theta(y|x)$ 中采样, 各项分布正比于对数概率, 这被称为祖先采样.

祖先采样避免了许多 MAP 解码的退化行为, 比如重复陷阱, 并为语言模型的生成引入了更丰富的多样性. 当然, 祖先采样也有一些缺陷, 比如可能会过度采样不太可能的 token. 对于此, 可以通过启发式方法在每个时间步骤选择一个阈值, 仅考虑采样概率高于该阈值的 token. 有些时候我们希望获得比祖先采样更高的多样性, 可以考虑在贪心采样和均匀采样之间进行插值.

考虑用一个式子拟合以上方法

$$q_t(y_t | y_{<t}, x; p_\theta, \tau) \propto \exp(s_\theta(y_{<t}, x) / \tau) $$

将 $\tau$ 设为 $\to 0$ 即为贪心解码, 设 $\tau$ 为 $1$ 即为祖先采样, 设 $\tau > 1$ 即接近于均匀采样.

控制生成

考虑将生成概率复合上一个调节序列 $c(y)$, 即

$$q_* \propto p_\theta(y|x)c(y) $$

以下是基于 $c(y)$ 结构的三个例子.

分类器: 设 $c(y) = p(a|x, y)$, 它预测 $y$ 包含一个属性 $a$ 的概率, 比如某种风格. 目标从以下分布中采样

$$q_* \propto p_\theta(y|x)p(a|x, y)^\beta $$

其中 $\beta$ 是一个超参数, 越大则给分类器分配更高的权重.

提示器: 设 $c(y) = [y \in Y_x^*]$, 它确保生成的结果包含 $Y_x^*$ 中的某个期望关键字, 例如 $Y_x^*$ 是推理问题中的正确解决方案集合. 目标从以下分布中采样

$$q_∗ \propto p_θ(y|x)[y \in Y_x^*] $$

奖励: 一个重要的情况是, 当 $c(y)$ 被奖励函数 $r(x, y) \to \mathbb{R}$ 控制时, 目标从以下分布中采样

$$q_∗ \propto p_θ(y|x) \exp\left(\frac{1}{\beta} r(x, y)\right) $$

其中 $\beta \in \mathbb{R}$ 在从 $p_\theta$ 取样 $(\beta \to \infty)$ 和最大化奖励 $(\beta \to 0)$ 之间进行插值.

约束解码

通常我们希望生成满足某些约束的结果, 这些标记可能是结构性的, 比如, 满足 .json 格式; 或者包含特定的词, 比如, 必须包含「请」. 与控制生成相比, 该约束是强制性的. 显然我们可以通过拒绝采样严格地执行约束, 但这种方法可能导致采样不终止.

基于解析器的结构约束解码: 该方法通过将语言模型与解析器配对来执行此类约束. 解析器只允许有效的拓展成为下一个 token 的候选项. 编写该解析器的难点在于, 如何识别有效的下一 token, 并将解析器与子词分词器连接. 解析器的效率取决于指定的输出集合形式的复杂性, 有些简单的要求可以使用有限状态自动机来实现; 而更复杂的约束需要使用更复杂, 计算开销更大的解析器.

基于解析器的约束解码方法可以加速解码, 简单来说, 候选集只有一个元素的时候就不需要使用大模型向前传递了, 直接接受该 token 即可. 这启发我们约束性解码的一个缺点, 如果候选集为空怎么办呢? 几种解码方法通过一种名为 token healing 的方法处理这个问题, 将生成器回滚至倒数第二个 token, 然后再接着生成下一个 token.

词汇约束解码: 通常, 希望输出中不要包含某些词汇是简单的, 但想要输出特定词汇就比较困难了, 一般采用一些启发式搜索算法解决, 例如利用梯度指导搜索方向.

元生成算法

考虑将前文「token 级别的生成器」作为一个黑盒, 讨论调用子生成器的算法, 也即

$$y \sim g(\cdot | x, \{g_1, g_2, \cdots, g_G\}, \phi) $$

其中 $g$ 定义了元生成器的使用策略, $\{g_1, g_2, \cdots, g_G\}$ 为子生成器, $\phi$​ 是其它任何输出和超参数.

「元生成」作为一种对底层生成器模型实现无关的抽象, 需要澄清其与其它生成算法的关联.

链式元生成器

将生成器直接相接是很自然的, 例如通过以下方法生成一个故事

$$y = f_1 \circ f_2 \circ f_3\left(f:=(x; p_\theta, \phi) \to y\right) $$

其中 $f_1$ 生成故事大纲, $f_2$ 填充各部分, $f_3$ 修改故事以润色和满足长度限制.

问题分解: 很多算法采用链模式, 以将输入–输出问题分解为多个步骤, 每个步骤由语言模型或外部函数实现. 例如: 首先调用生成器将问题分解为子问题, 然后连读调用生成器回复每个子问题; 注意力系统在生成之前重写输入以帮助模型避免关注不相关的信息.

并行元生成器

「并行元生成器」是并行生成多个轨迹, 然后合并生成的终止状态以获得最终生成的序列.

重排序算法: 其用于在 $n$ 个候选列表中排序, 选择排名前 $k$ 的序列. 其只会使得计算复杂度线性增长, 与贪心解码相比, 它更适合于黑箱生成器, 因为它不需要了解用于填充候选列表的生成器.

噪声通道重排序: 将输出的结果经过一些未知噪声模式的扭曲.