M2Medium★ Agent 工程必考 · 零格式错误Part M · LLM 评测与 Agent/RAG 算子
FSM 状态机结构化约束解码(Logit Masking)
在自回归采样前基于有限状态机屏蔽非法 Token 的 Logits,从数学概率层面保证工具调用与 JSON Schema 100% 合法。
⏱️ 时间复杂度:
O(|V|) 位掩码过滤每步💾 空间复杂度:
O(|States| * |V|) 预编译允许表🎯 免登录实战自测闭环(先做再看答案)
按「机制回忆 → 关键行填空 → 边界反例 → 追问与错题记录」顺序自测,进度自动保存在本地。
Step 1 · 机制口述与数值稳定性自检
Step 2 · 核心代码关键行补全
import numpy as np
def apply_fsm_logit_mask(logits: np.ndarray, state: str, fsm_transitions: dict, token_to_id: dict) -> np.ndarray:
"""
Mask disallowed vocabulary logits to -1e9 according to current FSM state.
Guarantees illegal JSON/schema transitions get 0 probability after Softmax.
"""
allowed_tokens = fsm_transitions.get(state, [])
mask = np.zeros(len(logits), dtype=bool)
for tok in allowed_tokens:
if tok in token_to_id:
mask[token_to_id[tok]] = True
if not np.any(mask):
raise ValueError(f"No valid allowed tokens for FSM state: {state}")
return
def fsm_decode_greedy(step_logits_list: list, fsm_transitions: dict, next_state_fn, token_to_id: dict, id_to_token: list) -> list:
"""
Run deterministic constrained greedy decoding step by step.
"""
state = "START"
out_tokens = []
for raw_logits in step_logits_list:
masked = apply_fsm_logit_mask(raw_logits, state, fsm_transitions, token_to_id)
# Stable softmax probabilities check
shifted = masked - np.max(masked)
probs = np.exp(shifted) / np.sum(np.exp(shifted))
tok_id =
tok = id_to_token[tok_id]
out_tokens.append(tok)
state = next_state_fn(state, tok)
return out_tokens
Step 3 · 反例与边界断言核对
Step 4 · 面试追问盲答与错题记录
Q1: 什么是 Jump-Forward Decoding(前跳压缩解码)?为什么它能加快约束 JSON 输出?
💡
实战一句话记忆口诀
Schema 编译成状态机,合法集合外全掩负无穷,Softmax 后非法概率归零
📐 核心数学公式与机理推导
### Logits 掩码拦截非法语法分支
仅靠 Prompt 要求“请严格输出 JSON”在复杂嵌套或低温度采样时仍有概率产出多余 Markdown 围栏或缺失闭合括号。
Outlines / SGLang / OpenAI Structured Outputs 将 JSON Schema 编译为确定性有限状态机(FSM):
- 根据当前状态 查出允许的后继词表子集 ;
- 在 Softmax 之前,对不在允许子集内的词 logits 全部赋值为 (如
- 经过 Softmax 归一化后,任何破坏语法结构的 Token 选中概率恒为
仅靠 Prompt 要求“请严格输出 JSON”在复杂嵌套或低温度采样时仍有概率产出多余 Markdown 围栏或缺失闭合括号。
Outlines / SGLang / OpenAI Structured Outputs 将 JSON Schema 编译为确定性有限状态机(FSM):
- 根据当前状态 查出允许的后继词表子集 ;
- 在 Softmax 之前,对不在允许子集内的词 logits 全部赋值为 (如
-1e9 / -1e4);- 经过 Softmax 归一化后,任何破坏语法结构的 Token 选中概率恒为
0.0,只保留模型在合法语法集合内的最优语义概率分布。🔄 张量维度与形状流转说明
state -> fsm_transitions[state] -> bool mask:(|V|,) -> np.where(mask, logits, -1e9) -> Softmax/argmax -> next_state
🛡️ 数值稳定性自检与边界要点
- 词表允许掩码若全为 False(状态死锁)必须提前报错诊断,否则全部
-1e9相减做 Softmax 会给出意外均匀分布 - 真实 BPE 分词器中一个 Token 可能跨多个 JSON 字符(如
":),工业界需离线预构建 state × vocab 稀疏掩码索引以实现微秒级查表(Jump-Forward Decoding)
💻 完整参考代码实现
import numpy as np
def apply_fsm_logit_mask(logits: np.ndarray, state: str, fsm_transitions: dict, token_to_id: dict) -> np.ndarray:
"""
Mask disallowed vocabulary logits to -1e9 according to current FSM state.
Guarantees illegal JSON/schema transitions get 0 probability after Softmax.
"""
allowed_tokens = fsm_transitions.get(state, [])
mask = np.zeros(len(logits), dtype=bool)
for tok in allowed_tokens:
if tok in token_to_id:
mask[token_to_id[tok]] = True
if not np.any(mask):
raise ValueError(f"No valid allowed tokens for FSM state: {state}")
return np.where(mask, logits, -1e9)
def fsm_decode_greedy(step_logits_list: list, fsm_transitions: dict, next_state_fn, token_to_id: dict, id_to_token: list) -> list:
"""
Run deterministic constrained greedy decoding step by step.
"""
state = "START"
out_tokens = []
for raw_logits in step_logits_list:
masked = apply_fsm_logit_mask(raw_logits, state, fsm_transitions, token_to_id)
# Stable softmax probabilities check
shifted = masked - np.max(masked)
probs = np.exp(shifted) / np.sum(np.exp(shifted))
tok_id = int(np.argmax(probs))
tok = id_to_token[tok_id]
out_tokens.append(tok)
state = next_state_fn(state, tok)
return out_tokens
🧪 本地测试与正确性断言
可直接复制到本地 Python / Jupyter 验证:
import numpy as np
id_to_tok = ["{", "key", ":", "val", "}", "BAD"]
tok_to_id = {t: i for i, t in enumerate(id_to_tok)}
fsm = {"START": ["{"], "OPEN": ["key"], "KEY": [":"], "COLON": ["val"], "VAL": ["}"]}
trans = {"START": "OPEN", "OPEN": "KEY", "KEY": "COLON", "COLON": "VAL", "VAL": "END"}
# Even when 'BAD' token has huge logit=99.0 at every step, FSM must emit exact valid JSON tokens
logits_seq = [np.array([1.0, 2.0, 0.0, 0.0, 0.0, 99.0]) for _ in range(5)]
seq = fsm_decode_greedy(logits_seq, fsm, lambda s, _t: trans[s], tok_to_id, id_to_tok)
assert seq == ["{", "key", ":", "val", "}"], f"Invalid constrained output: {seq}"
print("✓ Constrained JSON FSM token-mask assertion passed")🎯 核心工程追问与标准应答
Q1:什么是 Jump-Forward Decoding(前跳压缩解码)?为什么它能加快约束 JSON 输出?
在 JSON 固定格式字段(例如固定的键名
"status": " 或语法定界符)处,FSM 当前状态下的合法路径只有唯一确定序列。系统无需让大模型逐 Token 前向推理这十几个固定字符,直接由 CPU 一次性填入整段常量文本再把 KV 前移,能显著减少生成步骤。⚡
想检验本题的肌肉记忆?进入 3 阶闪卡主动回忆盲测
隐藏答案遮罩,自测:审题锚点 ➔ 数理公式机理 ➔ 工业标杆代码与连环追问。3 分钟攻破认知盲区!