Grammar backend、状态推进与回滚#

这章解决什么问题#

结构化生成前面的章节已经解释了 schema、regex、tool parser、reasoning roundtrip 和 surface 选择，但还有一层更靠近实现本体的内容没有单独展开：grammar backend 自己是怎样维护状态、接受 token、分配 vocab mask，并在 jump-forward、reasoning 或错误回退时做 rollback。

如果不把这一层讲透，结构化生成章节仍然会停在“约束会进入 generation path”，却说不清约束对象自身是怎样活着、怎样前进、怎样在出错时退回上一个一致状态。

为什么 backend 状态机值得单独讲#

python/sglang/srt/constrained/ 下面并不是只有一个统一后端。当前代码至少涉及：

  • xgrammar_backend.py
  • llguidance_backend.py
  • outlines_backend.py
  • reasoner_grammar_backend.py
  • base_grammar_backend.py
  • grammar_manager.py

这说明“grammar-based generation”并不是单个条件分支，而是一组共享接口下的具体状态机实现。一本想靠近好书标准的技术书，不应该只告诉读者“支持 json_schema / regex / ebnf”，还应该告诉读者这些约束在运行时究竟靠什么对象活着。

一张图：grammar 对象在 generation path 里的位置#

这张图解决的理解障碍是：很多读者知道 grammar 会影响 token 选择，但不清楚 grammar 对象到底是在前向前、采样前还是输出后更新。

flowchart LR
    Build["dispatch_json / dispatch_regex / dispatch_ebnf"] --> G["BaseGrammarObject impl"]
    G --> Mask["allocate / fill vocab mask"]
    Mask --> Sample["sampling under grammar mask"]
    Sample --> Accept["accept_token()"]
    Accept --> State["state advance / finished"]
    State --> Roll["rollback() / jump_and_retokenize() when needed"]

图比纯文字多解释的一点是：grammar backend 不是一次性编译后就躺着不动，而是在 token 生成过程中不断分配 mask、接受 token、推进状态，并在必要时回滚。

BaseGrammarObject 定义了什么最小契约#

base_grammar_backend.py 里的 BaseGrammarObject 把 grammar backend 的最低限度接口定义得很明确：

  • accept_token(token)
  • rollback(k)
  • is_terminated()
  • allocate_vocab_mask(...)
  • fill_vocab_mask(...)
  • move_vocab_mask(...)
  • apply_vocab_mask(...)
  • copy()
  • try_jump_forward(...)
  • jump_forward_str_state(...)
  • jump_and_retokenize(...)

这份接口本身就很有书写价值，因为它告诉你：约束生成不是只靠“判断某个 token 合法不合法”，而是一个包含状态推进、mask 生成、回滚、跳跃式前进的完整状态机协议。

XGrammar：状态推进和回滚最直接的一种实现#

xgrammar_backend.py 里的 XGrammarGrammar 很适合作为阅读入口，因为它把典型 grammar backend 的职责写得非常直接。

accept_token(...)#

它会把 token 交给 matcher.accept_token(token)，如果失败就抛 ValueError，否则把 token 记录进 accepted_tokens。这说明 grammar backend 并不总是温和失败；当 token 和当前 grammar 状态不兼容时，它会显式炸出错误。

rollback(k)#

matcher.rollback(k) 再配合 accepted_tokens = accepted_tokens[:-k]，说明 grammar 回滚不是抽象概念，而是要同时回退 matcher 的内部状态和书面记录的已接受 token。

jump_and_retokenize(...)#

这一段尤其值得技术书展开。实现会先找 old_output_ids 与 new_output_ids 的公共前缀，再回滚旧输出里不再保留的那部分 token，最后按新输出剩余部分重新 accept_token(...)。这说明 jump-forward 不是“状态直接跳到某处”，而是“基于新旧 token 序列差异重新建状态”。

LLGuidance：EOS 与 finished 状态的另一种处理方式#

llguidance_backend.py 的 GuidanceGrammar 提醒读者，不同 backend 的 finished 语义未必完全相同：

  • 如果 ll_matcher.is_stopped() 且 token 是 EOS，就把 finished = True。
  • rollback(num_tokens) 时，如果当前已 finished，要先把 finished 清回 False，并考虑 EOS 没有被 matcher 追踪这一事实。

这说明 grammar backend 的 rollback 不只是普通栈回退，还可能要修补“结束态是不是由额外 EOS 驱动”的语义差异。

ReasonerGrammar：为什么 reasoning 模式会让 grammar 状态机变复杂#

reasoner_grammar_backend.py 的 ReasonerGrammarObject 非常值得成书，因为它展示了“同一个 grammar backend 被另一层 reasoning 状态包起来”时会发生什么。

它额外引入了 tokens_after_think_end：

  • -1 表示 thinking 还没结束。
  • 0 表示刚结束 thinking。
  • 正数表示结束后已经走了多少 token。

然后：

  • accept_token(...) 只有在 tokens_after_think_end >= 0 时才真正把 token 交给底层 grammar。
  • rollback(k) 既要回滚底层 grammar，也要回滚 reasoning 层自己的状态。

这说明 reasoning 模式不是一个附加标签，而是会真正改变“哪些 token 应该进入 grammar 状态机”的逻辑边界。

grammar_manager.py 怎样把 backend 编译与请求生命周期接起来#

GrammarManager 的价值，在于它把 compile-time 与 run-time 接上了：

  • 根据 json_schema / regex / ebnf / structural_tag 选择 key。
  • 处理 backend 关闭、编译失败、预处理超时等情况。
  • 把 InvalidGrammarObject 当成显式状态，而不是模糊的异常。

这意味着 grammar 失败并不一定发生在 token 生成阶段，很多问题在“约束对象还没成功编译出来”时就已经决定了。

scheduler 输出处理为什么还要再次碰 grammar#

scheduler_output_processor_mixin.py 里在更新完 next_token_id 之后，会调用 req.grammar.accept_token(...)。如果失败，会记录错误并触发 abort。这说明 grammar 不只是采样前生成 mask；采样后还要用实际接受的 token 去推进 grammar 状态。

这非常重要，因为它回答了一个常见误解：grammar 不是只在 logits 上做筛选，之后就可以不管了。真实系统里，grammar 状态要和最终被接受的 token 序列保持同步，否则下一轮 mask 就会错。

这一层最容易混淆的三件事#

1. 把 backend 编译和 token 接受看成同一个阶段#

编译发生在 dispatch_* 或 manager 预处理阶段；token 接受发生在 decode 后处理阶段。两者的失败现象和排障入口不同。

2. 以为 rollback 只发生在 speculative decoding#

实际上 jump-forward、reasoner 模式和某些 output retokenization 路径都可能触发 rollback 或状态重建。

3. 以为所有 backend 的 finished 语义完全一致#

LLGuidance 对 EOS 的处理、ReasonerGrammar 对 think-end 之前 token 的忽略，都说明 backend 只是共享接口，不共享全部内部语义。

如果 grammar 相关输出出问题，先怎么查#

建议按这个顺序：

  1. 看 GrammarManager 是否成功编译出了 backend 对象，还是已经变成 InvalidGrammarObject。
  2. 看当前用的是 xgrammar、llguidance、outlines 还是 reasoner wrapper。
  3. 看 accept_token(...) 是在什么 token 上失败的。
  4. 看是否经历了 rollback() 或 jump_and_retokenize()。
  5. 再回头看 schema / regex / structural tag 本身是不是设计得太脆。

这套设计的收益与代价#

收益：

  • 多 backend 共用统一接口，结构化生成可以插进同一 generation path。
  • rollback、jump-forward、reasoning 包装都能在统一协议下表达。
  • 失败可以显式落成 InvalidGrammarObject 或 accept_token error，而不是静默漂移。

代价：

  • backend 之间的 finished/rollback 语义并不完全一致，阅读成本高。
  • 结构化生成问题容易同时跨 compile-time 和 decode-time 两个阶段。
  • 一旦 grammar 状态和真实输出 token 序列不同步，后续每一轮 mask 都可能错。

小结#

这一章真正想补齐的，是结构化生成里最“状态机本体”的那层：

  • grammar backend 不是一段静态配置，而是一个会推进、会回滚、会终止的对象。
  • accept_token、rollback、jump_and_retokenize 构成了它最核心的运行时语义。
  • 结构化生成真正难的地方，往往不是 schema 写法，而是这些状态机语义怎样和实际输出 token 序列保持一致。

到这里，结构化生成章节才真正从“约束进入 generation path”扩成“约束对象自己怎样在 generation path 里活着”。