Interview: 结构化输出(JSON Mode)的实现原理是什么？Constrained Decoding的计算开销多大？
题目解析
结构化输出要求LLM生成严格符合给定schema的JSON或其他格式。核心技术是Constrained Decoding：在每一步解码时，根据当前状态和语法规则，将不合法的token的logit设为负无穷，只从合法token中采样。这保证了输出100%符合格式要求。
解答思路
实现原理：1）将JSON Schema编译为上下文无关文法(CFG)或正则表达式；2）构建有限状态自动机(FSA)或下推自动机(PDA)；3）每一步解码时根据当前自动机状态计算合法的token集合，生成一个token mask；4）将mask应用到logits上（非法token设为-inf）。Outlines库和guidance库是典型实现。计算开销主要来自：每一步都需要遍历词表(32K-128K)判断每个token是否合法，这个操作的时间复杂度与词表大小和语法复杂度相关。
关键要点
- 预编译优化：将语法到token mask的映射预计算为查找表，运行时只需O(1)查表
- 难点在于tokenizer的不确定性：一个字符串可能对应多种tokenization方式
- 嵌套结构（如JSON中的嵌套对象）需要PDA而非FSA，状态空间更大
- 实际开销通常小于5%的额外延迟，主要瓶颈在首次编译而非运行时
加分回答
可以分析OpenAI的JSON Mode和Structured Output的区别：JSON Mode只保证输出是合法JSON，Structured Output还保证符合指定schema。还可以讨论XGrammar项目如何通过将CFG编译为下推自动机并做token前缀匹配来高效实现约束解码，以及与jump-forward优化的结合——当某个位置只有一个合法token时直接跳过采样。
常见踩坑
- 误以为Constrained Decoding会显著降低生成质量——合理的schema约束对质量影响很小
- 忽略了边界情况：max_tokens不够时可能生成不完整的JSON
- 对于复杂嵌套schema，编译时间可能很长，需要缓存编译结果