给LLM开挂！SGLang 中结构化输出策略介绍

大模型应用中，结构化输出能让模型的输出更符合特定格式要求，便于后续处理。约束大模型解码，实现结构化输出，主要有三种方式：基于有限状态机（FSM-Based）、交错解码（Interleave-Based）和跳跃（Jump-Forward）解码方式。本文主要围绕大模型结构化输出介绍以下内容：

1）三种结构化解码方式的运行机制和特点 2）通过实际代码，展示从json限制格式到正则表达式，再到FSM的过程。 3）跳跃解码中FSM构建单元和大模型解码token的不匹配问题以及解决方式。

1，FSM-Based Decoding

构建方式：分两步，首先把要输出的限制格式（如json格式）转换为正则表达式。其次，将正则表达式再构建为有限状态机（Finite State Machine FSM）。

• • json格式转换为正则表达式

json 格式具有特定的结构，包含大括号、键值对、引号、逗号等元素。将 json 格式转换为正则表达式，需要针对这些元素制定相应的匹配规则。如以下，使用 Outlines库将特定的json格式转化为正则。

from enum import Enum
from pydantic import BaseModel
class Name(str, Enum):
 john = "John"
 paul = "Paul"
class Age(int, Enum):
 twenty = 20
 thirty = 30
class Character(BaseModel):
 name: Name
 age: Age

以上建立了一个具有两个变量的类，其可以解析为json格式，以pydantic类为载体，将其转换为正则表达式仅需要一个函数：

json_schema = Character.model_json_schema()
json_schema
# 输出结果
"""
{'$defs': {'Age': {'enum': [20, 30], 'title': 'Age', 'type': 'integer'},
 'Name': {'enum': ['John', 'Paul'], 'title': 'Name', 'type': 'string'}},
 'properties': {'name': {'$ref': '#/$defs/Name'},
 'age': {'$ref': '#/$defs/Age'}},
 'required': ['name', 'age'],
 'title': 'Character',
 'type': 'object'}
"""

• • 正则表达式到FSM

有限状态机（FSM）由状态集合、输入符号集合、转移函数、初始状态和接受状态组成。将正则表达式转换为 FSM，需要根据正则表达式的语法规则，构建相应的状态和状态转移。

简单点，以正则表达式 “a|b” 为例，它表示匹配 “a” 或者 “b”。构建 FSM 时，初始状态为 S0，当输入 “a” 时，从 S0 转移到接受状态 S1；当输入 “b” 时，从 S0 转移到接受状态 S2，S1 和 S2 都是接受状态。

使用Outlines库中实现：

import outlines.fsm as fsm
import json
regex_str = fsm.json_schema.build_regex_from_object(json.dumps(json_schema)
regex_str
#输出结果
"""
'\\\\{"name":("John"|"Paul"),"age":(20|30)\\\\}'
"""

最终转为FSM的图如下：

假如使用Mistral模型，从输入prompt到输出期望的json格式，整体流程的实现代码为：

from outlines import models, generate
model = models.transformers("mistralai/Mistral-7B-v0.1")
generator = generate.json(model, Character)
char = generator("Generate a young character named Paul.")
print(char)
# 输出结果
# Character(name:"Paul", age:20) 

优势和局限：

适用于更广的语法，比如 json、yaml、IP 地址和邮件等。因为这些语法都可以通过构建相应的正则表达式，进而转换为有限状态机来进行约束。FSM 的运行机制本质是通过 “状态锁死” 实现结构化约束。每一步输出的 token 必须能使 FSM 从当前状态合法跳转至下一个状态，否则该 token 会被丢弃，模型需重新生成。这种逐 token 的校验确保了输出不会出现格式错误（如缺少引号、括号不匹配等）。

又因为FSM是在token级构建，所以需要逐token解码，解码效率偏低。为了进一步提高解码效率，发展出了交错解码。

2，Interleaved-Base Decoding

构建方式：将一个json的语法结构拆分成不同的部分，根据不同部分的语法特点，构建限制性解码规则进行解码。

json结构可以拆分为块填充部分和限制解码部分。块填充部分单次的前向过程可以输出多个token，限制解码部分需要特定规则的转化，并逐token解码，这样提升了整体的解码效率。

例如，json中的键名 “name”，“age”，“house”可以直接进行填充，而不用拆解为单个字母的token逐个解码，进而减少了前向计算的次数。图中代码通过Guidance库实现 。

优势和局限：

块填充的部分可以实现多token的解码，进而加快解码速度。

但交错解码需要定制化的语法构造，使其适用范围降低。即不同的 json 结构可能需要构建不同的解码规则，难以通用。

其次频繁的通信导致额外的计算负担。在拆分部分进行解码时，需要不断地与模型进行通信，传递规则和接收结果，增加了计算资源的消耗。

3，Jump-Forward Decoding

结合基于FSM解码和插值解码的优势，SGLang提出了跳跃解码。其核心是以压缩的有限状态机为基础，遇到特定连接符号时，进行预测输出，以实现“跳跃”的效果。

3.1，如何压缩FSM节点

在 SGLang 中，压缩有限状态机（Compressed Finite State Machine）实现核心是通过合并连续的单一转换边来简化状态机结构，从而提升解码效率。

首先基于字符或字符串构建原始的有限状态机，而非基于令牌（tokens）。这为后续的压缩操作奠定基础，核心概念定义：

• • 单一转换边（singular transition edge）：满足两个条件的边称为单一转换边其源节点只有一个后继节点。且边上只有一个可接受的字符或字符串
• • 压缩边（compressed edge）：由若干连续相邻的边压缩而成的边，且 到 都必须是单一转换边。压缩边的文本是 到 所有边的文本的拼接。

压缩过程： 从基于字符的 FSM 开始，递归地将单一转换边合并到其前导边中，直到无法进一步压缩为止。原本需要多个步骤的转换，被合并为一个压缩边，减少了状态转换的次数，从而加快了解码过程。

3.2，词边界问题-重新分词

问题：

压缩有限状态机的构建基础是基于字符或是字符串（characters/strings），而大模型训练和解码是以token为基础的，两者之间存在差异。而且，当有限状态机中存在经过压缩的转换边（包含较长字符串）时，直接对压缩字符串进行随机分割可能破坏 LLM 预训练时的分词规则，导致语义偏差或格式错误。例如，压缩文本{"summary":若被随意分割为{", summa, ry, ":_"会偏离正确分词方式（应保持{"summary":的整体分词逻辑），影响后续解码的准确性。

主要有两个问题，

• • 问题1：压缩后的字符不在解码字典中出现OOV问题。
• • 问题2：随意的拆分长字符偏离正确的分词方式。

解决方式：

通过原始分词器重新分词，对压缩边中的文本，包括可能不在 token 字典中的字符/字符串，结合历史生成的文本，使用大模型原生的分词器进行整体重新分词。这一过程会将字符/字符串映射为模型可识别的 token 序列，即使原始字符/字符串不在字典中，分词器也会按照预训练时的逻辑（如子词切分、字节级编码等）将其拆分为合法 token，确保符合模型的输入格式。

举例：

以常见的 LLM 分词器为例，结合 SGLang 中压缩有限状态机的场景，说明如何通过原始分词器进行重新分词：

假设压缩有限状态机中有一条压缩边包含的文本为{"summary": "AI is，这条文本需要被转换为模型可识别的 token 序列，但直接分割可能不符合分词规则（例如错误拆分为{, ", sum, mary, ": 等）。

使用原始分词器重新分词的过程如下：

1. 输入整合：将历史生成的文本，假设为{"title": "SGLang"}与当前压缩边文本{"summary": "AI is整合，得到完整上下文字符串：{"title": "SGLang"}{"summary": "AI is。
2. 调用分词器：调用原始分词器使用模型原生分词器对整合后的字符串进行分词，得到如下 token 序列：{"、title、": "、SGLang、"}、{"、summary、": "、AI、 is
3. 映射与对齐：将分词结果与压缩边文本对应，提取出压缩边文本对应的 token 序列（{"、summary、": "、AI、 is），结合FSM可以一次性的将5个token输入大模型，进行后续解码。

对跳转机制的解释：输入边上的长字符被重新拆分为多个token，在解码时候遇到特定的字符（长字符的部分子串），可以一次性的将长字符的所有token组成输入到大模型，进行下一次的预测，进而达到 “跳跃” 的效果。

4，总结

基于 FSM 解码通过状态的精确流转，像 “交通信号灯” 一样严格管控每一步输出，是结构化输出中最基础且可靠的约束方式。在三种结构化解码算法中，FSM-Based Decoding 适用于多种语法，但解码效率较低；Interleaved-Base Decoding 通过块填充提高了速度，但适用范围较窄且存在一些额外通信计算问题；Jump-Forward Decoding 在效率上有优势，但对特定字符依赖强且处理复杂结构能力有待提升。

具体场景和需求选择合适的解码方式。

• • 需要处理多种复杂语法且对效率要求不高，可选择基于有限状态机的解码 FSM-Based Decoding；
• • 如果处理的是特定结构且追求速度，交错解码 Interleaved-Base Decoding 可能更合适；
• • 希望在保证一定效率的同时处理结构化输出，跳跃解码 Jump-Forward Decoding 是一个选项，但需注意其局限并采取相应解决措施。