大型语言模型的高效引导生成：迭代 FSM 处理和索引

链接表

• 摘要和简介
• LLM 抽样和指导生成
• 迭代 FSM 处理和索引
• 迭代解析的扩展
• 讨论、参考文献和致谢

3. 迭代 FSM 处理和索引

准确地说，我们考虑 5 元组有限自动机形式的正则表达式 [Sipser，1996，定义 1.5]：

定义 1 （有限自动机）。有限自动机或有限状态机由 (Q, Σ, δ, q0, F) 给出，其中 Q 是一组有限状态，Σ 是有限字母表，δ : Q × Σ → Q 是转换函数，q0 ∈ Q 是起始状态，F ⊆ Q 是接受状态集。

V 中字符串的组成字符来自 Σ：即 V ⊂ P(Σ)。为简单起见，FSM 状态 Q 将始终用整数值表示。

示例 1。我们在图 1 中说明了正则表达式 ([0-9]*)?\.?[0-9]* 的 FSM 采样过程，该正则表达式可用于生成浮点数。为简单起见，让词汇表 V 仅由以下字符串组成：“A”、“.”、 “42”、“.2”和“1”。

当生成开始时，FSM 处于状态 0，因此我们的算法会屏蔽字符串“A”，因为它不会被 FSM 接受。在这种情况下，我们只能采样“.”、“42”、“.2”和“1”。

如果我们采样“.2”，则将 FSM 推进到状态 3。在这种情况下，只有“42”和“1”是有效完成，因此我们在采样之前屏蔽其他值。如果我们采样“1”，则将 FSM 推进到状态 1，在这种情况下，“。”、”.42”、“.2”和“1”是有效完成，并且屏蔽保持不变。

循环遍历词汇表以确定有效的下一个标记仍然是最大的问题。为此，我们使用正则表达式的 FSM 对词汇表进行预处理并构建索引。重要的是我们考虑从每个可行的 FSM 状态开始，因为词汇表中的字符串可以匹配正则表达式的任意部分，而这些部分隐含地是 FSM 状态。

算法 3 中给出了从 FSM 中的任意点开始生成匹配的过程。结果是子序列列表，详细说明了 FSM 在接受提供的字符串时将遍历的状态。

通过将这些子序列的起始状态与算法 2 中循环一步到达的最后一个 FSM 状态进行匹配，我们可以使用映射 σ : Q → P(V) 有效地对词汇表进行索引，将 FSM 状态与 FSM 在这些状态下将接受的词汇表元素集连接起来。

算法 4 描述了 σ 的构造。

使用哈希映射 σ 可以使算法 2 中的 m 步骤平均仅花费 O(1)。此外，由于 σ 是在标记采样过程之外构建的，因此其运行时成本实际上无关紧要，尽管理论上它需要的内存等于 FSM 中的状态数（即 |Q|）。幸运的是，对于正则表达式和词汇表的非病态组合，词汇表中的并非每个字符串都会被 FSM 接受，并且并非每个 FSM 状态都会由 V 中的字符串表示。

3.1 示例

在本节中，我们使用 GPT2-medium（355M 个参数）来说明正则表达式引导生成在实践中的工作原理。我们使用库 Outlines 来生成它们：

清单 3.1 – 续

清单 3.3 – 续

3.2 与当前方法的比较

为了说明本文所述并在 Outlines 中实现的索引方法的效率，我们与 Guidance 库进行了简单的比较。截至撰写本文时，Guidance 库使用部分正则表达式匹配（每次从采样序列的开头应用），并且必须在每一步迭代 LLM 的词汇表（N = 50, 257）。

本次比较使用的指导代码和提示如下：

清单 3.4 – 续

对应的Outlines代码如下：

清单 3.5 – 续

max_tokens 的值是变化的，并且使用 timeit 记录单个循环和单个重复值的时间（即，对于每个 max_tokens 值只收集一个样本）。结果绘制在第 3.2 节中。

除非存在可能导致较大运行时差异的配置疏忽，否则观察到的最大采样令牌数量的缩放是惊人的，并且表明该方法隐含的计算问题日益严重。