A.13 有限状态机与文法:约束解码的数学底座
本页范围:附录 A 第 13 节 | 整理时间:2026-10-09
12.4 节讲约束解码时反复使用一句话:把目标格式编译成状态机,解码每一步向它查询合法 token,其余置 −∞。这句话里被当作黑盒的正是状态机本身。它是什么、为什么能逐步判定合法性、能力边界画在哪里,就是本附录要补齐的背景。
本节按「机器本身 → 描述格式的语言 → 接回解码」的顺序展开,路线图如下:
- 状态机:只有三样东西的小机器(A.13.1):状态、转移、接受态,用一台识别 JSON 字符串的最小机器走一遍完整判定;
- 正则与文法:多一条栈的差别(A.13.2):正则表达式为什么总能编译成状态机,括号嵌套为什么编译不了;
- 接回解码:每步查表,非法置 −∞(A.13.3):无记忆、只查表的性质为什么恰好咬合逐 token 生成。
读完全节,应能手画一台识别简单格式的状态机,也能讲清 12.4 节那台「判卷机」凭什么每步都答得上话。
A.13.1 状态机:只有三样东西的小机器
这台机器的全名是有限状态机(finite-state machine,FSM):「有限」说的是状态总数有限,「状态机」说的是它任何时刻只停在一个状态上,靠读入符号在状态之间跳转。拆开看,整台机器只有三样东西:
- 状态(state):机器内部的有限几种处境,任何时刻只处于其中一个;
- 转移(transition):一张查算表,每行的形状是「当前状态 + 读入的符号 → 下一个状态」,查不到的组合一律不允许;
- 接受态(accepting state):事先指定的若干状态,输入全部读完时机器停在其中,这段输入才算合法。
用一个最小例子把三要素看全。要识别的目标是 JSON 字符串(JSON 是程序之间交换数据的文本格式,12.4 节介绍过)。规则取简化版:以英文双引号开头,中间是任意多个非引号字符,以双引号收尾(真实规则还允许 \" 转义,此处略去,不影响要领)。按这三条造机器,只需三个状态:
- 开始:等待开引号,只认
"; - 串内:读到普通字符原地不动,读到
"跳出; - 结束:唯一的接受态,停在这里意味着字符串合法。
拿 "小明" 走一遍,引号本身也是输入字符。第一步机器在「开始」,读到 ",查表「开始 + " → 串内」,跳过去;第二步读「小」,查表「串内 + 普通字符 → 串内」,原地不动,「明」同理;第四步读收尾的 ",进入「结束」。输入读完,机器停在双圈上,判定合法。两个反例对照着看更清楚:"小明 缺收尾引号,读完停在「串内」,不是接受态,不合法;小明 压根没有引号,第一步「开始 + 小」在表里查无此行,直接卡死,同样不合法。整台机器与这次走查画在图 1 里。
这台小机器有一个看似短板、实则关键的性质:它没有记忆。它不记得读过哪几个字符,只记得现在停在哪个状态。「整段文本合不合法」这个全局问题,被拆成「当前状态下,这个符号有没有路可走」的一连串局部查询,每次判定只查一行表。正是这个性质让它在解码环节派上用场,A.13.3 会接回这一点。
A.13.2 正则与文法:多一条栈的差别
工程里描述格式,很少直接画状态机,更常用的是正则表达式(regular expression):一种用字符加少量运算符描述文本模式的记法。比如 "[^"]*" 读作「一个引号、任意多个非引号字符、再一个引号」,正好是 A.13.1 那台机器识别的语言。这不是巧合。形式语言理论的一个经典结论是:每个正则表达式都能编译成一台等价的有限状态机。对应关系在直觉层面很直接:
| 正则写法 | 含义 | 对应的状态机元件 |
|---|---|---|
a | 一个字符 a | 一条标着 a 的转移 |
ab | 先 a 后 b | 两个状态前后相接 |
a* | a 重复任意次(含零次) | 一个自环 |
a|b | a 或 b 任选其一 | 同一状态出发的两条平行转移 |
于是「正则 → 状态机」是一条双向通道:写格式用正则,对人友好;跑判定用状态机,对机器友好;中间由编译器翻译。12.4 节的 Outlines 走的正是这条路:开发者交出 JSON Schema 或正则,库负责把它编译成状态机。
但有一类格式,状态机在原理上就做不了:任意深的嵌套。括号配对是代表:() 合法、(()) 合法、((())) 也合法,规律是「每开一个就必须关一个」。状态机数不了这笔账:开着的个数可以是任意大的整数,而状态总数有限,没法用「停在第几号状态」记住「已经开了几层」。要处理嵌套,得给机器添一条记忆。
比状态机多一条栈(stack,后进先出的一摞格子)的文法体系。识别它的机器叫下推自动机(pushdown automaton),可以理解成「FSM + 一条栈」:每遇开括号压入一格,每遇闭括号弹出一格,输入读完时栈恰好为空才算配对成功。栈提供了无界的记忆,嵌套多深都应付得来。JSON 的完整语法(对象套数组、数组再套对象)就落在这一层,12.4 节的 GBNF 方案做的正是 CFG 级约束。
| 有限状态机 FSM | CFG + 下推自动机 | |
|---|---|---|
| 记忆 | 只有当前状态,总数有限 | 当前状态加一条无界的栈 |
| 搞得定的格式 | 正则级:固定字段、枚举值、字符串模式 | 嵌套级:括号配对、对象套数组 |
| 在 12.4 节的代表 | Outlines | llama.cpp GBNF |
A.13.3 接回解码:每步查表,非法置 −∞
把这台机器接回解码。12.4.2 节里约束解码的一步,用本节语言写出来是三句查询:
- 状态机吃掉已生成的前缀,停在某个状态上,比如「等待键名字符串」;
- 查这个状态的转移表:词表 6400 个 token(minimind 配置)里,哪些能被状态机吸收且不走进死路,构成合法集合;
- 合法集合之外的 token,logit(模型对每个候选 token 的打分,A.3 节)一律置 \(-\infty\),softmax 之后概率归零,合法集合内部重新归一化,温度与采样照常叠加。
第 3 步的「置 \(-\infty\)」就是 A.11 节讲的 softmax 掩码,那里讲透了 \(-\infty\) 怎么让概率精确归零;本节回答的是另一半问题:\(-\infty\) 的名单从哪来。答案就是第 2 步的那张转移表。
回看 A.13.1 的「无记忆」性质,它在解码环节恰好是优点:状态机不需要预见未来,只按当前状态回答下一步的合法集合,这与逐 token 生成的节奏天然咬合——每生成一个 token,状态机推进一步,新的合法集合立等可取。Outlines 干脆把「状态 × 词表」的合法集合离线全部算好,运行时每步只查一次表,额外开销很小。
难点只剩一个:token 对齐。语法按字符书写,模型按 token 生成,两者粒度错位——一个 token 可能横跨多个语法符号("age": 恰好切成一个 token 时,一口气穿过「串内、收尾、冒号之后」三个状态),一个语法符号也可能要几个 token 才拼得出来。判定「这个 token 合法吗」,必须模拟它整段喂进状态机后停在哪里、会不会走进死路,这是各家约束解码实现的主要复杂度(12.4.3 节有展开)。
三节串成一句话:格式先编译成状态机(或带栈的文法),解码每步由它划出合法集合,集合外置 −∞。模型决定「合法者之中谁更受青睐」,状态机决定「谁能出场」,两者各管一段,互不越界。
本书用在哪
| 出现在哪 | 用它做什么 |
|---|---|
| 12.4.2 约束解码原理 | 每步的合法 token 集合由状态机(或文法)按当前状态查出,集合外置 −∞;那台「判卷机」就是本节的机器 |
| 12.4.3 Outlines / GBNF / Structured Outputs | 三套工程方案的底座分别是 FSM 与 CFG,差别只在格式怎么写、在哪一侧编译,逐步判定的逻辑都是本节这套 |