A.13 有限状态机与文法:约束解码的数学底座

本页范围:附录 A 第 13 节 | 整理时间:2026-10-09

快速浏览

核心问题12.4 节说「把格式编译成状态机,解码每步查表,非法 token 置 −∞」。状态机到底是什么?它凭什么能逐步回答「下一个 token 合不合法」,什么时候又不够用?
本节主张有限状态机只有三样东西:有限个状态、一张转移表、几个接受态。它把「整段文本合不合法」拆成「每步有没有路可走」的局部查询,与逐 token 生成天然咬合。正则表达式总能编译成状态机;任意深的嵌套它数不了,加一条栈就是上下文无关文法。
一句话结论看懂状态机,就看懂了 12.4 节约束解码那台「判卷机」是怎么干活的。
关键词
有限状态机转移表接受态正则表达式上下文无关文法约束解码

  12.4 节讲约束解码时反复使用一句话:把目标格式编译成状态机,解码每一步向它查询合法 token,其余置 −∞。这句话里被当作黑盒的正是状态机本身。它是什么、为什么能逐步判定合法性、能力边界画在哪里,就是本附录要补齐的背景。

  本节按「机器本身 → 描述格式的语言 → 接回解码」的顺序展开,路线图如下:

  1. 状态机:只有三样东西的小机器(A.13.1):状态、转移、接受态,用一台识别 JSON 字符串的最小机器走一遍完整判定;
  2. 正则与文法:多一条栈的差别(A.13.2):正则表达式为什么总能编译成状态机,括号嵌套为什么编译不了;
  3. 接回解码:每步查表,非法置 −∞(A.13.3):无记忆、只查表的性质为什么恰好咬合逐 token 生成。

  读完全节,应能手画一台识别简单格式的状态机,也能讲清 12.4 节那台「判卷机」凭什么每步都答得上话。

A.13.1 状态机:只有三样东西的小机器

  这台机器的全名是有限状态机(finite-state machine,FSM):「有限」说的是状态总数有限,「状态机」说的是它任何时刻只停在一个状态上,靠读入符号在状态之间跳转。拆开看,整台机器只有三样东西:

  1. 状态(state):机器内部的有限几种处境,任何时刻只处于其中一个;
  2. 转移(transition):一张查算表,每行的形状是「当前状态 + 读入的符号 → 下一个状态」,查不到的组合一律不允许;
  3. 接受态(accepting state):事先指定的若干状态,输入全部读完时机器停在其中,这段输入才算合法。

  用一个最小例子把三要素看全。要识别的目标是 JSON 字符串(JSON 是程序之间交换数据的文本格式,12.4 节介绍过)。规则取简化版:以英文双引号开头,中间是任意多个非引号字符,以双引号收尾(真实规则还允许 \" 转义,此处略去,不影响要领)。按这三条造机器,只需三个状态:

  • 开始:等待开引号,只认 ";
  • 串内:读到普通字符原地不动,读到 " 跳出;
  • 结束:唯一的接受态,停在这里意味着字符串合法。

  拿 "小明" 走一遍,引号本身也是输入字符。第一步机器在「开始」,读到 ",查表「开始 + " → 串内」,跳过去;第二步读「小」,查表「串内 + 普通字符 → 串内」,原地不动,「明」同理;第四步读收尾的 ",进入「结束」。输入读完,机器停在双圈上,判定合法。两个反例对照着看更清楚:"小明 缺收尾引号,读完停在「串内」,不是接受态,不合法;小明 压根没有引号,第一步「开始 + 小」在表里查无此行,直接卡死,同样不合法。整台机器与这次走查画在图 1 里。

原创示意图 · 非论文原图 识别合法 JSON 字符串的最小状态机(三要素:状态、转移、接受态;规则已简化) 起点 开始 只认开引号 "(开引号) 串内 普通字符原地消化 普通字符(除引号外) "(收尾引号) 结束 双圈 = 接受态 走一遍 "小明"(引号也是输入字符),每读一个字符查一行转移表: 开始 " 串内 小 串内 明 串内 " 结束 ✓ 读完停在双圈:合法 ✗ 反例一:"小明(缺收尾引号)读完停在「串内」,不是接受态 → 不合法 ✗ 反例二:小明(没有引号)第一步在「开始」查不到转移,直接卡死 → 不合法
图 1:识别合法 JSON 字符串的最小状态机(原创示意,未考虑 \" 转义)。上方是机器本身:从「开始」读入开引号进「串内」,普通字符靠自环原地消化,收尾引号把它送进双圈接受态。下方走一遍 "小明":四步各查一行转移表,停在双圈,合法;两个反例分别演示「停错状态」与「查无此路」两种失败。12.4 节图 3 那台完整 JSON 对象状态机,就是同一思路放大到更多状态。

  这台小机器有一个看似短板、实则关键的性质:它没有记忆。它不记得读过哪几个字符,只记得现在停在哪个状态。「整段文本合不合法」这个全局问题,被拆成「当前状态下,这个符号有没有路可走」的一连串局部查询,每次判定只查一行表。正是这个性质让它在解码环节派上用场,A.13.3 会接回这一点。

A.13.2 正则与文法:多一条栈的差别

  工程里描述格式,很少直接画状态机,更常用的是正则表达式(regular expression):一种用字符加少量运算符描述文本模式的记法。比如 "[^"]*" 读作「一个引号、任意多个非引号字符、再一个引号」,正好是 A.13.1 那台机器识别的语言。这不是巧合。形式语言理论的一个经典结论是:每个正则表达式都能编译成一台等价的有限状态机。对应关系在直觉层面很直接:

正则写法含义对应的状态机元件
a一个字符 a一条标着 a 的转移
ab先 a 后 b两个状态前后相接
a*a 重复任意次(含零次)一个自环
a|ba 或 b 任选其一同一状态出发的两条平行转移

  于是「正则 → 状态机」是一条双向通道:写格式用正则,对人友好;跑判定用状态机,对机器友好;中间由编译器翻译。12.4 节的 Outlines 走的正是这条路:开发者交出 JSON Schema 或正则,库负责把它编译成状态机。

  但有一类格式,状态机在原理上就做不了:任意深的嵌套。括号配对是代表:() 合法、(()) 合法、((())) 也合法,规律是「每开一个就必须关一个」。状态机数不了这笔账:开着的个数可以是任意大的整数,而状态总数有限,没法用「停在第几号状态」记住「已经开了几层」。要处理嵌套,得给机器添一条记忆。

上下文无关文法 CFG context-free grammar;规则允许「自己套自己」,如 A → ( A )

比状态机多一条栈(stack,后进先出的一摞格子)的文法体系。识别它的机器叫下推自动机(pushdown automaton),可以理解成「FSM + 一条栈」:每遇开括号压入一格,每遇闭括号弹出一格,输入读完时栈恰好为空才算配对成功。栈提供了无界的记忆,嵌套多深都应付得来。JSON 的完整语法(对象套数组、数组再套对象)就落在这一层,12.4 节的 GBNF 方案做的正是 CFG 级约束。

像收银台摞盘子:每开一个括号放一只盘子,每关一个取走一只,账算完时台面也该空了。状态机没有这摞盘子,三层之后就数不清。
有限状态机 FSMCFG + 下推自动机
记忆只有当前状态,总数有限当前状态加一条无界的栈
搞得定的格式正则级:固定字段、枚举值、字符串模式嵌套级:括号配对、对象套数组
在 12.4 节的代表Outlinesllama.cpp GBNF

A.13.3 接回解码:每步查表,非法置 −∞

  把这台机器接回解码。12.4.2 节里约束解码的一步,用本节语言写出来是三句查询:

  1. 状态机吃掉已生成的前缀,停在某个状态上,比如「等待键名字符串」;
  2. 查这个状态的转移表:词表 6400 个 token(minimind 配置)里,哪些能被状态机吸收且不走进死路,构成合法集合;
  3. 合法集合之外的 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,差别只在格式怎么写、在哪一侧编译,逐步判定的逻辑都是本节这套