Reading

Structured Generation

Aug 15, 2025
5368 views
Large Model
#Acceleration #LLM #Large Model

引言

Structured Generation with LLM，是指让LLM按照预先定义的schema，输出符合schema的结构化结果。

常见的应用场景有：

  1. 数据处理。主要功能为a -> b，即从源文本中抽取/生成符合schema的结果，例如给定新闻，进行分类、抽取关键词、生成总结等；
  2. Agent。主要功能是Tool Calling，即根据用户query，选择适当的tool和入参。

将 LLM 限制为始终生成符合特定模式的、有效的 JSON 或 YAML，是许多应用的关键功能。

Kor

Kor，一个基于prompt的技术方案；Kor比较适合数据处理场景，且原理简单、易于理解，适合作为入门, 并且Kor适用于那些不支持function calling的比较旧的模型。

image
image

使用Kor进行structured generation的流程如下：

  1. 定义schema，包括结构、注释还有例子；
  2. Kor用特定的prompt template，将用户提供的schema和待处理的raw text，组装成prompt；
  3. 将prompt发送给LLM，借助其通用的In Context Learning能力，尽量生成符合schema的内容；
  4. Kor对LLM的输出进行parse，返回符合schema的结构化结果，但也有概率没有返回（当LLM的输出不符合schema时）。

Kor的工作是其中的第2步、第4步。由此可见，Kor是对LLM的一层包装。

Kor的优点是：使用方便。Kor无需介入decode过程，只要有一个text to text的LLM API即可使用，既可以用闭源模型，也可以用开源模型。

但Kor的缺点也很明显：无法保证抽取结果一定满足schema，这是因为：

  • 本质上Kor只是帮你“组装”了一下prompt而已，输出是否符合schema还取决于模型自身的instruction-following能力。

Example

介绍了Kor的原理之后，可以通过两个实例来查看Kor的具体过程

Example 1

  • 中文翻译器效果：输入任意文本，返回{"translate_result": {"chinese": 翻译结果}}
  • 在结构化输出中，一般只需两步即可：
    • 设置schema（即想要llm输出的结构，同时包含注释、例子）；
    • 用结构化输出工具（例如本文提到的Kor）得到schema结果。

Kor支持两种设置schema的模式，Kor schema和Pydantic Model，在这个例子中，我们使用Kor schema。

# kor schema，我们想要的输出格式
schema = Object(
    id="translate_result",
    description=(
        "任意文本的翻译结果。"
    ),
    attributes=[
        Text(
            id="chinese",
            description="中文翻译结果",
            examples=[], # Kor支持few-shot examples，但本例子比较简单，故不需要
            many=False,
        ),
    ],
    many=False,
)
# 运行结果*chain = create_extraction_chain(llm, schema, encoder_or_encoder_class='json')
text="We've trained a model, based on GPT-4, called CriticGPT to catch errors in ChatGPT's code output. We found that when people get help from CriticGPT to review ChatGPT code they outperform those without help 60% of the time. We are beginning the work to integrate CriticGPT-like models into our RLHF labeling pipeline, providing our trainers with explicit AI assistance. This is a step towards being able to evaluate outputs from advanced AI systems that can be difficult for people to rate without better tools."
print(chain.run(text)['data'])
{'translate_result': {'chinese': '我们训练了一个基于GPT-4的模型，称为CriticGPT，用于捕捉ChatGPT代码输出的错误。我们发现，当人们从CriticGPT那里获得帮助来审查ChatGPT代码时，他们比没有帮助的人高出60%的效率。我们正在开始将类似CriticGPT的模型集成到我们的RLHF标记流程中，为我们的训练师提供明确的AI辅助。这是朝着能够评估来自高级AI系统的输出迈出的一步，这些输出在没有更好的工具的情况下很难被人类评估。'}}

示例1成功运行：
我们打印kor的prompt来看看。

print(chain.prompt.format_prompt(text="[user input]").to_string())
Your goal is to extract structured information from the user's input that matches the form described below. When extracting information please make sure it matches the type information exactly. Do not add any attributes that do not appear in the schema shown below.

```TypeScript

translate_result: { // 任意文本的翻译结果。
 chinese: string // 中文翻译结果
}
```

Please output the extracted information in JSON format. Do not output anything except for the extracted information. Do not add any clarifying information. Do not add any fields that are not in the schema. If the text contains attributes that do not appear in the schema, please ignore them. All output must be in JSON format and follow the schema specified above. Wrap the JSON in <json> tags.




Input: [user input]

Output:

Example2

  • 评价解析预期效果：输入一段用户评价，得到评价属性（口味、价格等）、评价极性（正向、负向、中立）、评价词（好吃、贵等）、参考片段。
  • 结构化输出，第一步是定义schema，我们可以设置成这样的schema
[
    {
        'aspect': 评价属性,
        'sentiment': 评价极性,
        'sentiment_word': 评价词,
        'reference': 参考片段,
    }
]

在这个例子中，我们使用Pydantic Model来定义schema，Pydantic Model也能够支持few-shot examples，其额外好处是可以Validate

# 评价解析的pydantic model
class Sentiment(enum.Enum):
    positive = "positive"
    negative = "negative"
    neural = "neural"

class Dianpin(BaseModel):
    aspect: str = Field(
        description="评价属性"
    )
    sentiment_word: str = Field(
        description='对评价属性的评价词，从原文中抽取',
    )
    sentiment: Optional[Sentiment] = Field(
        description='对评价属性的情感，positive\negative\neural中的一个',
    )
    reference: str = Field(
        description='评价的原文'
    )
# 运行kor
schema, validator = from_pydantic(
    Dianpin,
    description='对评价的解析结果',
    examples=[],
    many=True #支持list of aspect
)
chain = create_extraction_chain(
    llm, schema, encoder_or_encoder_class="json", validator=validator
)

pprint(chain.run("整体来说，环境可以，味道的话也还不错，但价格有一点小贵。"))
{'data': {},
 'errors': [ParseError('The LLM has returned structured data which does not match the expected schema. Providing additional examples may help improve the parse.')],
 'raw': '\n'
        '<json>\n'
        '[\n'
        '  {\n'
        '    "aspect": "环境",\n'
        '    "sentiment_word": "可以",\n'
        '    "sentiment": "positive"\n'
        '  },\n'
        '  {\n'
        '    "aspect": "味道",\n'
        '    "sentiment_word": "还不错",\n'
        '    "sentiment": "positive"\n'
        '  },\n'
        '  {\n'
        '    "aspect": "价格",\n'
        '    "sentiment_word": "小贵",\n'
        '    "sentiment": "negative"\n'
        '  }\n'
        ']\n'
        '</json>',
 'validated_data': {}}

注意，此时data字段数据为空，因为LLM的返回不符合预期的schema，kor建议加入examples
于是我们加入一个简单的example

# 运行kor
schema, validator = from_pydantic(
    Dianpin,
    description='对评价的解析结果',
    examples=[
        ('味道真不错，下次还来！', [{"aspect":"味道", "sentiment_word": "真不错", "sentiment": "positive", "reference": "味道真不错"}])
    ],
    many=True #支持list of aspect
)
chain = create_extraction_chain(
    llm, schema, encoder_or_encoder_class="json", validator=validator
)

pprint(chain.run("整体来说，环境可以，味道的话也还不错，但价格有一点小贵。"))
{'data': {'dianpin': [{'aspect': '环境',
                       'reference': '整体来说，环境可以',
                       'sentiment': 'positive',
                       'sentiment_word': '可以'},
                      {'aspect': '味道',
                       'reference': '味道的话也还不错',
                       'sentiment': 'positive',
                       'sentiment_word': '还不错'},
                      {'aspect': '价格',
                       'reference': '但价格有一点小贵',
                       'sentiment': 'negative',
                       'sentiment_word': '小贵'}]},
 'errors': [],
 'raw': '\n'
        '<json>\n'
        '{\n'
        '  "dianpin": [\n'
        '    {\n'
        '      "aspect": "环境",\n'
        '      "sentiment_word": "可以",\n'
        '      "sentiment": "positive",\n'
        '      "reference": "整体来说，环境可以"\n'
        '    },\n'
        '    {\n'
        '      "aspect": "味道",\n'
        '      "sentiment_word": "还不错",\n'
        '      "sentiment": "positive",\n'
        '      "reference": "味道的话也还不错"\n'
        '    },\n'
        '    {\n'
        '      "aspect": "价格",\n'
        '      "sentiment_word": "小贵",\n'
        '      "sentiment": "negative",\n'
        '      "reference": "但价格有一点小贵"\n'
        '    }\n'
        '  ]\n'
        '}\n'
        '</json>',
 'validated_data': [Dianpin(aspect='环境', sentiment_word='可以', sentiment=<Sentiment.positive: 'positive'>, reference='整体来说，环境可以'),
                    Dianpin(aspect='味道', sentiment_word='还不错', sentiment=<Sentiment.positive: 'positive'>, reference='味道的话也还不错'),
                    Dianpin(aspect='价格', sentiment_word='小贵', sentiment=<Sentiment.negative: 'negative'>, reference='但价格有一点小贵')]}

加入example之后，示例2成功运行。

我们也打印kor的prompt，看看长什么样，以及few-shot examples是如何使用的。

print(chain.prompt.format_prompt(text="[user input]").to_string())

Your goal is to extract structured information from the user's input that matches the form described below. When extracting information please make sure it matches the type information exactly. Do not add any attributes that do not appear in the schema shown below.

```TypeScript

dianpin: Array<{ // 对评价的解析结果
 aspect: string // 评价属性
 sentiment_word: string // 对评价属性的评价词，从原文中抽取
 sentiment: "positive" | "negative" | "neural" // 对评价属性的情感，positive
egative
eural中的一个
 reference: string // 评价的原文
}>
```

Please output the extracted information in JSON format. Do not output anything except for the extracted information. Do not add any clarifying information. Do not add any fields that are not in the schema. If the text contains attributes that do not appear in the schema, please ignore them. All output must be in JSON format and follow the schema specified above. Wrap the JSON in <json> tags.

Input: 味道真不错，下次还来！
Output: <json>{"dianpin": [{"aspect": "味道", "sentiment_word": "真不错", "sentiment": "positive", "reference": "味道真不错"}]}</json>
Input: [user input]
Output:

小结

Kor主要基于prompt，是对LLM的一层封装；Kor的设计理念使其便于进行数据处理（raw data -> schema），但Kor的最大限制是，并不能保证所抽取内容的结构稳定性，而这点将会被guided decoding类技术解决。

Function Calling

这里以mistral发布的12B模型 -- Mistral-Nemo-Instruct-2407为例，初步研究其实现方式。

从一个简单的FC例子入手：

  • tool是经典的get_current_weather，schema如下
Function(
  name="get_current_weather",
  description="Get the current weather",
  parameters={
    "type": "object",
    "properties": {
      "location": {
          "type": "string",
          "description": "The city and state, e.g. San Francisco, CA"},
        "format": {
           "type": "string",
           "enum": ["celsius", "fahrenheit"],
           "description": "The temperature unit to use. Infer this from the users location."},
      },
     "required": ["location", "format"],
})
  • 用户query：What's the weather like today in Paris and Beijing? I prefer Celsius format.

打印出来prompt如下：

image

在input侧，mistral-nemo的做法是直接将用户提供的tool schema转为string，并包裹在特殊的tag（AVAILABLE_TOOLS）之中，然后插入到user query之前。

既然都是组装Prompt，我们拿它和Kor的Prompt做个对比：

image

可以发现，mistral-nemo的prompt更精简（不包含Your goal is .... 、All output must be in JSON format.... 等内容）。

这就是微调模型与通用模型的用法差异：

  • mistral-nemo在fine-tuning时，按照这样的格式进行训练，FC的“要求”已经被encode到模型的参数中去了；
  • Kor是第三方实现，无从得知模型的训练细节，只能依靠模型的通用In Context Learning能力，因此需要把“要求”写清楚，于是prompt细节较多。
    接着，我们来看output侧。

mistral-nemo的输出结果如下：

image

看起来，这是一个普通的text generation过程，通过特殊标记（TOOL_CALLS）来表明，这是一个tool_call message，而非常见的text message；同时nemo支持同时call多个tools，每个call为一个字典，其中包含function name和arguments参数（json格式）。

小结

总结一下，mistral-nemo这样实现FC：

  1. 将tools按照特定的template，组装到prompt中去；
  2. LLM输出时，也遵循特定的template，call tool时加入特殊标记（TOOL_CALLS），并返回name和arguments。

需要提到的是，FC虽然经过了fine-tuning，输出结构的稳定性有一定保证，但若未使用constrain decoding技术，那么仍然不是100%鲁棒的

Constrained Decoding

Structured generation 使得输出结构的稳定性，尤其便于应用复杂的prompt技巧和搭建workflow。在扣子中，大模型的默认输出格式便是json；openai也开始支持structured output。

之前介绍的Kor，其本质仍是基于Prompt，依赖模型的通用instruction following能力，而使用LLM厂商提供的function calling，用一种“曲线救国”的方式，间接实现structured generation。但这两种方法本质上都不是100%鲁棒的，模型仍有一定概率失败（即输出不符合schema的内容；结构越复杂则失败概率越大）。

可以预想，各大厂会快速跟进openai的更新，加入structured output能力；而实际上，早有许多开源项目（例如outlines, guidance, sglang, llama.cpp, LMQL, jsonformer），能基于本地模型实现类似效果，其背后的核心技术是constrained decoding。

constrained decoding的基本思想

image

如何实现constrained decoding？这里有两个基本的思想：

  1. 一个直觉是：定义好schema之后，我们就知道了各个字段的输出范围。
    例如，有个字段是int类型，那么模型在生成该字段的内容时，只应该输出0-9的数字，其他的token不能被输出。
    因此只要先提前做些处理：计算并存储模型在每一步时可以输出的tokens；然后在每次生成时，mask掉不该输出的tokens（将其生成概率赋为0），那么最终结果一定符合预先定义的schema。
  2. schema中有些部分不需模型生成，因为已经提前定义好了。
    例如，我们想要输出如下json类型的内容（一个典型的Chain Of Thought）

{
  "reasoning_step": "模型的推理过程", 
  "result": "最终结果"
}

很明显，括号、双引号、字段名称，都是无需生成的，直接“放”在模型的输出中即可，模型只需关注字段内容的生成。

从这2个基本思想，可以得到constrained decoding的基本特性：

  1. 对于新的schema，有初始的时间和空间花销。因为需提前把各步的输出token范围计算出来、存储下来，所以有一定的时间花销和空间花销；但对于同一个schema，理论上只需计算一次即可，以后再生成的话，速度几乎没有影响；
  2. 可能比unconstrained decoding更快。因为可以跳过一些固定内容的生成；
  3. 模型效果可能有提升。模型只需关注每个字段内容的生成，而不用管结构的事，因为生成难度降低了，所以效果可能有提升，例如outlines团队的这篇博客

Beating GPT-4 with Open Source

在Berkeley Function Calling Leaderboard的简单任务上，Phi-3-medium-4k-instruct+ structured generation 可以超越GPT-4；

  1. 更好的微调模型仍然是必要的。structured generation只管结构的事，生成效果的好坏，还得看模型能否理解各种类型、各种难度的schema，因此仍需要针对性的微调模型（例如有Function/Tool Calling能力的模型）。

下面介绍一些常见的实现思路

outlines：基于FSM的方法

http://github.com/dottxt-ai/outlines

基本使用

假设我们希望语言模型生成一个代表故事中角色的 JSON 对象。我们的角色需要有一个名字和一个年龄，分别包含在 JSON 的“name”和“age”字段中。为了简化本文中的问题，我们将限制可能的名字和年龄的数量。以下是使用 Pydantic 定义此角色的方法：

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

可以使用 Outlines 来使用任何开源语言模型生成故事角色，这里是一个使用 Mistral-7B-v0.1 的示例：

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)

使用 generate.json 与让模型和自由生成文本一样快，只是输出结构得到了保证。为了理解其如何使这种生成显著更快，我们需要深入了解 Outlines 的内部机制。

具体原理

对于一个json schema，outlines首先将其转为正则表达式，然后再转为token-level的Finite State Machine（FSM）。

随后，模型的生成过程就变成在state之间的跳转：首先从初始state出发，随后在有限的输出路径中选一条，到达下一个state，直到到达最后一个state，完成生成。

image

将 JSON 转换为正则表达式

Outlines的第一步是将我们的 JSON 模式转换为正则表达式。正如稍后将看到的，正则表达式是使结构化生成快速的关键部分。当你将一个 Pydantic 对象传递给 Outlines 时，它首先将其转换为 JSON 模式规范：

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'}

这个 JSON 模式规范进一步转换为正则表达式。如果模型生成的字符串与这个正则表达式匹配，那么我们就知道它是符合 JSON 模式规范的，因此可以被 Pydantic 解析。

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)\\\\}'

接下来我们将使用这个正则表达式来帮助我们控制结构化生成。

注意：从技术上讲，所有可能的合法 JSON 模式都不能用正则表达式表示，但在大多数情况下，用正则表达式近似就足够了。

将 JSON 正则表达式转换为有限状态机FSM

Outlines 中结构化生成速度的秘密在于正则表达式和有限状态机（FSM）之间众所周知的等价性。为了理解这是如何工作的，我们需要将我们的 JSON 正则表达式转换为 FSM。

我们使用 interegular 库将表示 JSON Schema 的正则表达式翻译成有限状态机。这是该过程输出的有限状态机的可视化：

image.png

我们可以使用以下步骤从这个有限状态机生成有效的 JSON

  1. 从state 0 开始
  2. 随机生成一个允许的转换字符
  3. 跟随相应的转换到新状态
  4. 重复直到达到 FSM 的一个最终状态（在本例中，只有状态 27）。

按照这个步骤，无论我们在 FSM 中遵循什么路径，刚刚生成的字符串都是有效的！

此时，我们已经将 JSON 表示为 FSM，我们只需要跟踪当前状态，就可以几乎不增加额外成本来控制采样。

融合：朴素字符合并

现在我们可以探索使用一种初步迈向融合的技术来改进结构化生成。如果我们看看上面 FSM 的一部分，某些东西应该会立刻变得明显：

image.png

看看那些状态中只有一种可能转换的情况有多少！回想一下，我们使用 FSM 来限制从模型中进行采样的选择，一个状态外的转移数量代表了我们可以采样的可能值。如果只有一个值，那么就没有必要采样！这就产生了一个明显的优化：如果我们压缩具有单个转换的节点，我们可以跳过那个采样步骤。这将导致一个新的有限状态机，看起来像这样：

image.png

看起来我们极大地简化了模型，并发现了一种加速生成的好方法！不幸的是，我们在使用 LLMs 时遗漏了一个重要部分：LLMs 不使用单个字符，而是使用 token。事实证明，这引入了更多细微差别，这些细微差别对生成质量可能产生重大影响。以字符为单位思考可能会让我们误入歧途。

将字符正则表达式适配为与 token 工作

幸运的是，事实证明你可以将这个基于字符的有限状态机确定性地转换为另一个与 token 工作的有限状态机。以下代码展示了如何在 Outlines 中实现这一点：

from outlines.fsm.regex import make_deterministic_fsm, create_fsm_index_tokenizer

new_fsm, _ = make_deterministic_fsm(fsm)
index, _ = create_fsm_index_tokenizer(new_fsm, tokenizer)

其中，index 对象是一个字典，它将有限状态机的状态映射到可能的转换；转换表示为一个字典，它将允许的 token 映射到如果我们采样这个 token，我们需要进入的有限状态机的下一个状态。

生成第一个 token 的步骤是：

  1. 将提示词传递给模型，获取下一个 token 的概率分布。
  2. 从状态 0 启动 FSM。列出所有与 index[0].keys() 对应的有效转换的标记。
  3. 使用概率分布来采样其中一个 token，比如 X 。
  4. 跟随与此标记对应的转换，并使用 new_state = index[0]["X"] 移动到相应状态

让我们看看这个索引，并将标记 ID 转换为标记以了解发生了什么：

index_with_tokens = {}
for state, transitions in index.items():
    transitions = {
        tokenizer.tokenizer.decode([key]): value for key, value in transitions.items()
    }
    index_with_tokens[state] = transitions

for state, transitions in index_with_tokens.items():
    print(f"{state}: {transitions}")
0: {'{': 1, '{"': 2}
1: {'"': 2}
2: {'na': 4, 'nam': 5, 'name': 6, 'n': 3}
3: {'a': 4, 'ame': 6, 'am': 5}
4: {'me': 6, 'm': 5}
5: {'e': 6}
6: {'"': 7, '":': 8, '":"': 9}
7: {':': 8, ':"': 9}
8: {'"': 9}
9: {'P': 11, 'Paul': 14, 'Pa': 12, 'J': 10, 'Jo': 26, 'John': 14}
10: {'o': 26, 'oh': 27, 'ohn': 14}
11: {'au': 13, 'a': 12, 'aul': 14}
12: {'ul': 14, 'u': 13}
13: {'l': 14}
14: {'","': 17, '",': 16, '"': 15}
15: {',"': 17, ',': 16}
16: {'"': 17}
17: {'age': 20, 'a': 18, 'ag': 19}
18: {'g': 19, 'ge': 20}
19: {'e': 20}
20: {'"': 21, '":': 22}
21: {':': 22}
22: {'20': 24, '2': 23, '3': 23, '30': 24}
23: {'0': 24}
24: {'}': 25}
26: {'hn': 14, 'h': 27}
27: {'n': 14}

数字代表有限状态机的状态，字符串代表模型词汇表中的符号。我们还可以可视化整个有限状态机，它比我们最初的那个复杂得多。

image.png

尽管增加了这种复杂性，但理解这一点与我们在原始生成示例中的理解一样简单。

需要注意的是，我们状态机中的每个转换都代表对 LLM 的一次昂贵调用。在普通的生成中，所有这些调用也是必要的。我们使用状态机来表示正则表达式，这意味着控制输出几乎不需要比普通生成更多的成本。然而，我们不必满足于仅仅没有增加成本：如果我们可以找到一种方法来跳过对 LLM 的调用，结构化生成就有可能实现更快的生成。

Coaescence

让我们聚焦于前一幅图中从 2→6 的路径。每条这些转换都代表从阶段 2 到阶段 6 可能的有效转换序列。总共有 8 条路径，但它们都生成相同的字符串：“name”。

image.png

到达同一生成结果有八种路径，这听起来不重复吗？确实如此，这些重复必然是由于分词器训练方式造成的。这篇博客文章（+视频）对于那些感兴趣的人是一个很好的介绍。但足以说，如果 {" 在词汇表中，那么 { 和 " 也必然存在。

五倍速度提升

然而，我们可以利用 FSM 的结构来显著加速生成：我们不必为每个转换对 LLM 进行昂贵的调用，而是可以选择将以下任一token词附加到当前生成的序列中：

  • [”name”]
  • [”n”, “a”, “m”, “e”]
  • [”na”, “m”, “e”]
  • [”nam”, “e”]
  • [”n”, “am”, “e”]
  • [”n”, “ame”]
  • [”na”, “me”]
  • [”n”, “a”, “me”]

为了简化，让我们展示如果始终追加最长的标记（或等价地最短的词）会发生什么。在我们的示例（且仅此示例！）中，这对应以下规则：

在给定的转换中，如果多个token共享相同的前缀，仅保留对应最长token的转换

让我们手动应用这个规则并查看结果：

simplified_index = {
    0: {'{"': 2},
    2: {"name": 6},
    6: {'":"': 9},
    9: {'Paul': 14, 'John': 14},
    14: {'","': 17},
    17: {'age': 20},
    20: {'":': 22},
    22: {'20': 24, '30': 24},
    24: {'}': 25},
}

在答案中的 9 个token中，除了两个状态外，其余都是单状态转换。因此，我们只需要调用模型两次，并直接追加其他token。

这至少比 Outlines 中的结构化生成快 5 倍，在结构化生成中，模型需要考虑所有可能的转换。由于 Outlines 中的结构化生成不会比普通生成产生额外成本，这意味着我们最终从模型的角度来看比普通生成快 5 倍。

“name”中有什么意义？

所有这些路径最终都会指向同一个字符串和相同的速度提升，然而它们在 LLM 达到状态 6 时可能会引导至非常不同的状态。也就是说，字符串是相同的，但每条路径在阶段 6 会引导至不同的条件概率分布。

假设我们不仅对生成一个随机的角色感兴趣，而且需要正确识别命名实体提取任务中的“Paul”或“John”。根据你选择附加的词元，选择“John”或“Paul”的后续概率可能会有完全不同的结果：

image.png

当我们使用大型语言模型生成文本时，我们是从可能序列的分布中进行采样。所有可能的序列（非常非常大）的集合称为该分布的支持集。当我们进行结构化生成时，我们限制了该分布的支持集，因为我们禁止生成不尊重结构的序列。当我们选择要追加的token词时，我们进一步限制了可能的序列数量。

当我们优化生成过程时，我们应该始终问自己：我们是否阻止了更可能的序列被生成？

更快的结构化生成

结构化生成关键在于我们只从允许的下一个token集合中进行采样。我们使用开源库 outlines 基于正则表达式的有限状态机公式构建一个高效的"索引"查找结构。这种结构几乎不会给非结构化生成增加额外开销，并且可以方便地与 Huggingface transformers 及其他库一起用于推理。

使我们能够优化的关键观察是，大多数情况下，可接受的下一个token集合将只占整个词汇表的一小部分。计算它们的分数完全没有意义，因为它们会被掩盖掉。回想一下，在前向传播的最后一步，嵌入向量表示需要转换成词汇表上的分布。这涉及昂贵的矩阵乘法。用正式术语来说，分数/逻辑分布的计算涉及"unembedding matrix” \(\mathbf{W_u} \in \mathbb{R}^{N_V \times d_e}\)，其中 \(N_V\) 是词汇表大小，\(d_e\) 是embedding维度，可以表示为 \(\mathbf{W_u}\mathbf{X}[:, \ell]\)，其中 \(\mathbf{X}\) 是长度为 \(\ell\) 的编码标记序列；因此 \(\mathbf{X}[:, \ell] \in \mathbb{R}^{d_e}\) 是经过所有 Transformer 层的前向传播后最后一个输入token的embedding。这可以如下所示进行可视化表达：

\[\left[\begin{array}{c}\mathbf{W_u}[1, :] \\\mathbf{W_u}[2, :] \\\mathbf{W_u}[3, :] \\\mathbf{W_u}[4, :] \\\vdots \\\mathbf{W_u}[N_V, :] \\\end{array}\right] \mathbf{X}[:, \ell] =\left[\begin{array}{rcl}\mathbf{W_u}[1, :] & \cdot & \mathbf{X}[:, \ell] \\\mathbf{W_u}[2, :] & \cdot & \mathbf{X}[:, \ell] \\\mathbf{W_u}[3, :] & \cdot & \mathbf{X}[:, \ell] \\\mathbf{W_u}[4, :] & \cdot & \mathbf{X}[:, \ell] \\& \vdots & \\\mathbf{W_u}[N_V, :] & \cdot & \mathbf{X}[:, \ell] \\\end{array}\right]\tag{1}\]

输出向量的每个元素（对应词汇表中的一个词元）都是 \(\mathbf{X}[:, \ell]\) 与unembedding matrix 中的一行进行点积的结果。通过仅对允许的下一个词元执行必要的点积运算，我们可以实现运行时的小幅减少，我们称之为选择性乘法(selective multiplication)。

假设仅允许 1 和 3 作为延续词元。那么计算可以简化如下：

\[\left[\begin{array}{c}\color{green}{\mathbf{W_u}[1, :]} \\\color{lightgrey}{\mathbf{W_u}[2, :]} \\\color{green}{\mathbf{W_u}[3, :]} \\\color{lightgrey}{\mathbf{W_u}[4, :]} \\\vdots \\\color{lightgrey}{\mathbf{W_u}[N_V, :]} \\\end{array}\right] \mathbf{X}[:, \ell] =\left[\begin{array}{rcl}\color{green}{\mathbf{W_u}[1, :]} & \color{green}{\cdot} & \color{green}{\mathbf{X}[:, \ell]} \\& \color{lightgrey}{-\infty} & \\\color{green}{\mathbf{W_u}[3, :]} & \color{green}{\cdot} & \color{green}{\mathbf{X}[:, \ell]} \\& \color{lightgrey}{-\infty} & \\& \vdots & \\& \color{lightgrey}{-\infty} & \\\end{array}\right]\tag{2}\]

显然，当允许的词元数量远小于 \(N_V\) 时，(2)是一种有益的方法。我们使用经验启发式方法来确定这种优化是有益还是有害——由于选择行和收集结果的额外开销。如果允许的下一个词元集合太大，我们默认采用原始计算，并对整个词汇表应用掩码以过滤掉不允许的词元。在实践中，我们看到要么允许的词元非常少（例如，当预期出现关键词或特定字段名时），要么太多（例如，当生成自由格式字符串时）。

让我们看看结构化生成的效果。我们使用了一个于 PhiForCausalLM 和 CustomPhiForCausalLM 的 Python/PyTorch 子类，该子类实现了带有我们选择性乘法优化的结构化生成：

model = CustomPhiForCausalLM.from_pretrained(
    checkpoint,
    tokenizer=tokenizer,
    index=simple_schema_index,
    device=device,
).to(device)

inputs_structured = tokenizer.encode("character1 = ", return_tensors="pt").to(device)

set_seed(random_seed)
outputs = model.generate(
    inputs_structured,
    eos_token_id=tokenizer.eos_token_id,
    pad_token_id=tokenizer.eos_token_id,
    max_length=100,
    temperature=0.1,
    renormalize_logits=True,
    do_sample=True,
)

print(tokenizer.decode(outputs[0]))
character1 = {"name": "John", "age": 30, "armor": "chainmail", "strength": 20}<|endoftext|>

注意到我们完全不需要详细的提示，但结果却符合模式！结构化生成不需要在提示中包含示例，就能每次都生成有效的结构。我们发现，在 GSM8K 基准测试中，1-shot 结构化生成的表现与 8-shot 非结构化生成相当。

试验

Outlines作者们后续又进行了一系列实验，发现大型语言模型（LLMs）中的结构化生成能够持续且显著提升模型在 GSM8K 评估集上的性能。

主要发现包括：

  • 在 8 种不同模型中，使用结构化生成可带来超过 70%的性能提升，并且在所有情况下都优于非结构化生成。
  • 此外，我们发现结构化生成具有先前未探索的益处："提示一致性"和"思维控制"。
image.png

另外作者还发现一个现象，称之为“Prompt Efficiency”：对于few-shot任务，使用大纲的结构化生成能够在仅有一个示例的情况下，比非结构化生成在最多 8 个示例的情况下实现更优越的性能。此外，我们观察到 1 次示例的结构化性能与更高次数的结构化生成相似，这意味着在许多情况下，仅 1 次示例就足以获得高质量的性能。这对于各种实际应用场景都非常有用：

  • 便利性：对于few-shot问题，获取示例可能很困难，而标注包含“思维链”推理步骤的示例可能非常耗时且具有挑战性。
  • 速度：更长的提示意味着更多的计算，因此保持提示大小较小意味着更快的推理。
  • 上下文保留：示例很容易消耗掉具有有限上下文长度的模型的上下文。
image.png

具体实现

可参考官方文档：https://dottxt-ai.github.io/outlines/latest/

这里以Qwen2.5VL-3B-Instruct为例

def outlines_inference():
    # Inference: Generation of the output
   

    # To use Qwen-2-VL:
    from transformers import Qwen2_5_VLForConditionalGeneration, AutoProcessor

    tf_model = Qwen2_5_VLForConditionalGeneration.from_pretrained(
        pretrained_model_name_or_path,
        torch_dtype=torch.bfloat16,
        attn_implementation="flash_attention_2",
        device_map="auto",
    )
    
    min_pixels = 256*28*28
    max_pixels = 1280*28*28
    tf_processor = AutoProcessor.from_pretrained(pretrained_model_name_or_path, min_pixels=min_pixels, max_pixels=max_pixels)

    model = outlines.from_transformers(tf_model, tf_processor)

    image = Image.open(image_path)

    # Set up the content you want to send to the model
    messages = [
        {
            "role": "user",
            "content": [
                {
                    # The image is provided as a PIL Image object
                    "type": "image",
                    "image": image,
                },
                {
                    "type": "text",
                    "text": f"""请用中文详细描述一下这张图像.用下面的JSON形式输出:
                    {Caption.model_json_schema()}
                """},
            ],
        }
    ]

    # Convert the messages to the final prompt
    text = tf_processor.apply_chat_template(
        messages, tokenize=False, add_generation_prompt=True
    )

    image_inputs, video_inputs = process_vision_info(messages)
    _generator = outlines.Generator(model, Caption)

    # Generate the receipt summary
    result = _generator(
        {"text": text, "images": image_inputs},
        max_new_tokens=1024
    )
    print(f'Outlines格式化输出:{result}')

模型输出：

正常输出:['```json\\n{\\n    "properties": {\\n        "overall": "汽车内部，前排和后排座椅。",\\n        "persons": [\\n            {\\n                "items": "坐在驾驶座上的男子",\\n                "title": "Person in the driver\\'s seat",\\n                "type": "string"\\n            }\\n        ],\\n        "objects": [\\n            {\\n                "items": "黑色皮革座椅",\\n                "title": "Car seats",\\n                "type": "string"\\n            },\\n            {\\n                "items": "车内物品",\\n                "title": "Items inside the car",\\n                "type": "string"\\n            },\\n            {\\n']
Loading checkpoint shards: 100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 2/2 [00:01<00:00,  1.40it/s]
Outlines格式化输出:{"overall": "汽车内部，前排和后排座椅均为黑色皮革材质。车窗外可以看到城市街道和建筑物。车内有一个人坐在驾驶座上，另一个人站在副驾驶座旁边。车内有一些物品，如水瓶、文件等。", "persons": ["坐在驾驶座上的男子", "站在副驾驶座旁的男子"], "objects": ["黑色皮革座椅", "水瓶", "文件", "车辆内饰"]}

SGLang—基于Compressed Finite State Machine的向前跳跃解码

SGLang对有限状态机的方案其进行了优化。核心思路如下图所示。

image.jpeg

上图便是SGLang提出的Compressed FSM方法，与原始的FSM相比，该方法压缩了state，合并了一些无需生成的state。

具体来说，我们可以通过引入一种基于压缩有限状态机的新的解码算法——向前跳跃解码，来结合基于有限状态机和交错方法的优点。

在由 JSON 模式转换的正则表达式指导下进行解码的过程中，当达到特定节点时，我们可以预测接下来的字符串：

  • 在上图中，解码开始时，根据正则表达式，我们可以预期即将到来的字符串为：
{
	"name":

接下来是实际的解码部分。

  • 类似地，当 LLM 在填充角色属性时输出 G ，我们可以有信心预测下一个字符串将是 ryffindor ，从而完成整个字符串为 Gryffindor 。

这正是跳跃式解码算法使解码速度更快的原因。在跳跃式算法中，我们检查给定正则表达式的有限状态机，识别所有单一转换边，并将连续的边压缩成单一路径。我们不必逐个标记解码这些单一路径，可以直接预填充（扩展）它们，跳跃到下一个分支点。

SGLang 的 RadixAttention 机制极大地简化了跳跃式解码算法的实现。在执行跳跃式解码时，我们只需终止当前请求并排入一个新的请求。SGLang 运行时的 RadixAttention 和高效扩展原语将自动重用前一个 token 的 KV 缓存，从而避免冗余计算。

分词边界处理

在实现约束解码时，处理分词边界总是很棘手，因为字符和 token 之间的可能映射非常复杂。

在 LLM 解码过程中，它可能会倾向于（以更高的概率）将多个字符组合成一个单独的 token。例如，在 JSON 解码的上下文中解码 "Hello" 时，LLMs 可能会输出如下这样的 tokens：

" He llo ",

它不会去解码最后一个 " ，而是总是倾向于将其与后面的 , 组合成更频繁的 token ", 。这种效应可能会导致一些奇怪的行为。例如，在上面的情况下，如果正则表达式设置为 "[\\w\\d\\s]*" （不包括最后一个 , ），它会导致无限解码，因为 LLM 想要在 ", 处停止，但这个 token 是不允许的。此外，在跳转解码过程中，我们发现对于跳转部分采用不同的分词策略可能会导致后续 token 的 logit 分布不同。简单地将分词后的跳转部分追加到当前 token 序列中可能会产生意想不到的结果。

为了解决这些问题，我们提出了以下解决方案：

  • 我们在跳跃阶段实现了一个re-tokenization 机制。这涉及追加字符串而不是token，然后对整个文本进行re-tokenization。这种方法有效地解决了大多数标记化问题，并导致计算开销仅略有增加，约为 4%。
  • 建议使用一个全面的正则表达式来指导整个解码过程，而不是使用多个连接的正则表达式。这种方法确保 FSM 和 LLM 都能了解整个解码过程，从而尽可能减少边界相关的问题。

OpenAI的方案—Context-Free Grammars

对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）。

openai并未提供具体的技术细节，但提到其生成过程与FSM比较相似，都是限定了模型在每步生成时的范围。

outlines和guidance都支持基于CFGs的structured generation；对细节感兴趣的朋友可以看它们的github。

Inference

Structured Generation with LLM（1）：介绍Kor，并用免费的LLM API做点练习

Structured Generation with LLMs(2)：Function Calling，不止于agent

Structured Generation（3）：如何让大模型100%输出符合json schema的结果

https://blog.dottxt.ai/

Fast JSON Decoding for Local LLMs with Compressed Finite State Machine