引言
Structured generation是使用LLM的新姿势。
输出结构的稳定性，尤其便于应用复杂的prompt技巧和搭建workflow。在扣子中，大模型的默认输出格式便是json；openai也开始支持structured output[1]。
笔者已经写了两篇有关structured generation的文章，第一篇使用Kor，其本质仍是基于Prompt，依赖模型的通用instruction following能力，第二篇使用LLM厂商提供的function calling，用一种“曲线救国”的方式，间接实现structured generation。但这两种方法本质上都 不是100%鲁棒 的，模型仍有一定概率失败（即输出不符合schema的内容；结构越复杂则失败概率越大）。
可以预想，各大厂会快速跟进openai的更新，加入structured output能力；而实际上，早有许多开源项目（例如outlines[2], guidance[3], sglang[4], llama.cpp[5], LMQL[6], jsonformer[7]），能基于本地模型实现类似效果，其背后的核心技术是constrained decoding。
本文介绍constrained decoding的基本思想和常见的实现思路。
constrained decoding的基本思想
如何实现constrained decoding？
一个直觉是：定义好schema之后，我们就知道了各个字段的 输出范围 。
例如，有个字段是int类型，那么模型在生成该字段的内容时， 只应该输出0-9的数字，其他的token不能被输出 。
因此，只要先提前做些处理：计算并存储模型在每一步时 可以输出的tokens ；然后在每次生成时，mask掉不该输出的tokens（将其生成概率赋为0），那么最终结果一定符合预先定义的schema。
这是constrained decoding的第一个基本思想。
第二个基本思想： schema中有些部分不需模型生成，因为已经提前定义好了 。
例如，我们想要输出如下json类型的内容（一个典型的Chain Of Thought）：
{
"reasoning_step": "模型的推理过程",
"result": "最终结果"
}
很明显， 括号、双引号、字段名称，都是无需生成的 ，直接“放”在模型的输出中即可，模型只需关注字段内容的生成。
从这2个基本思想，可以得到constrained decoding的基本特性：
- 对于新的schema，有初始的时间和空间花销 。因为需提前把各步的输出token范围计算出来、存储下来，所以有一定的时间花销和空间花销；但对于同一个schema，理论上只需计算一次即可，以后再生成的话，速度几乎没有影响；
- 可能比unconstrained decoding更快 。因为可以跳过一些固定内容的生成；
- 模型效果可能有提升 。模型只需关注每个字段内容的生成，而不用管结构的事，因为生成难度降低了，所以效果可能有提升，例如outlines团队的这篇博客[8]中，在
Berkeley Function Calling Leaderboard的简单任务上，Phi-3-medium-4k-instruct+ structured generation 可以超越GPT-4； - 更好的微调模型仍然是必要的 。structured generation只管结构的事，生成效果的好坏，还得看模型能否理解各种类型、各种难度的schema，因此仍需要针对性的微调模型（例如有Function/Tool Calling能力的模型）。
常见的实现思路
outlines：基于FSM的方法
对于json schema，outlines首先将其转为正则表达式，然后再转为token-level的Finite State Machine（FSM）。
随后，模型的生成过程就变成在state之间的跳转：首先从初始state出发，随后在有限的输出路径中选一条，到达下一个state，直到到达最后一个state，完成生成。
其中”有限的输出路径“就是前文所提到的tokens输出范围。
对技术细节感兴趣的读者，可以参阅outlines的论文[9]；FSM的缺点是无法准确表示复杂的schema，细节请看下文。
SGLang的优化
outlines充分利用了原理1，但没有利用原理2，即没有避免生成不必要的token，所以还不够快。
SGLang对其进行了优化。核心思路如下图所示。
上图便是SGLang提出的Compressed FSM方法，与原始的FSM相比，该方法压缩了state，合并了一些无需生成的state。
因此，SGLang能有更快的生成速度。与guidance + llama.cpp、outlines + vLLM相比，SGLang可以降低2倍的latency，并提高2.5倍的吞吐量，具体可参见他们的blog[10]。
这里有个细节，同一段文字在token-level也可能有多种组合方式，如果按规则选择其中一种，那么有可能影响后续的生成效果；SGLang用2个方法缓解了这个问题，具体可参见blog。
OpenAI的方案
对outlines和SGLang来说，其思路仍是围绕FSM。但FSM，或者说正则表达式，在表达能力上是有缺陷的，它们无法准确处理复杂的schema，例如嵌套型和递归型的数据结构。
下面是openai给出的一个无法用FSM来表示的schema。
{
"name": "ui",
"description": "Dynamically generated UI",
"strict": true,
"schema": {
"type": "object",
"properties": {
"type": {
"type": "string",
"description": "The type of the UI component",
"enum": ["div", "button", "header", "section", "field", "form"]
},
"label": {
"type": "string",
"description": "The label of the UI component, used for buttons or form fields"
},
"children": {
"type": "array",
"description": "Nested UI components",
"items": {
"$ref": "#"
}
},
"attributes": {
"type": "array",
"description": "Arbitrary attributes for the UI component, suitable for any element",
"items": {
"type": "object",
"properties": {
"name": {
"type": "string",
"description": "The name of the attribute, for example onClick or className"
},
"value": {
"type": "string",
"description": "The value of the attribute"
}
}
}
}
},
"required": ["type", "label", "children", "attributes"],
"additionalProperties": false
}
}
这个例子中，children下面可以嵌套相同的schema，并且可以有任意个；这种情况确实难以用正则来准确表示。
因此，openai不使用FSM，而是使用表达能力更强的Context-Free Grammars（CFGs）。至于什么是CFGs，这里有一个简短的介绍[11]。
openai并未提供具体的技术细节，但提到其生成过程与FSM比较相似，都是限定了模型在每步生成时的范围。
outlines和guidance都支持基于CFGs的
structured generation；对细节感兴趣的朋友可以看它们的github。
Json Mode的实现
Json Mode是structured generation的小弟，它只限定模型输出json，而不限定具体的schema。
它的实现方式也是基于CFGs的。
具体而言，可以预先定义Json的CFGs，然后在生成时限制模型在CFGs内生成。
下图是llama-cpp-python所使用的Json CFGs。
同理，特定的编程语言（SQL、C语言等）也可以预先构建CFGs，以限定模型只能生成符合规范的结果。
总结
本文介绍了constrained decoding技术的基本原理和常见的实现思路，对于复杂的prompt技术和workflow而言，structured generation 会成为开发者的标配，Agent的开发也因此变得更加工程化。
欢迎关注
如果本文对您有帮助，欢迎 点赞、收藏、转发 ！
也欢迎关注公众号（漫谈NLP），笔者将持续分享有趣/有用的AI知识。
参考资料
[1] introducing-structured-outputs-in-the-api: https://openai.com/index/introducing-structured-outputs-in-the-api/
[2] outlines: https://github.com/outlines-dev/outlines
[3] guidance: https://github.com/guidance-ai/guidance
[4] SGLang: https://github.com/sgl-project/sglang
[5] llama-cpp-python: https://github.com/abetlen/llama-cpp-python
[6] LMQL: https://github.com/eth-sri/lmql
[7] jsonformer: https://github.com/1rgs/jsonformer
[8] Beating GPT-4 with Open Source: https://blog.dottxt.co/oss-v-gpt4.html
[9] Efficient Guided Generation for Large Language Models: https://arxiv.org/pdf/2307.09702
[10] Fast JSON Decoding for Local LLMs with Compressed Finite State Machine: https://lmsys.org/blog/2024-02-05-compressed-fsm/
[11] 5分钟理解CFG上下文无关文法: https://blog.csdn.net/u013853733/article/details/113687298