← 回首頁

受限解碼（Grammar / DFA-constrained decoding）

你有沒有遇過：叫 LLM「回一段 JSON」，它卻多寫了一句「好的，這是你要的資料：」，或漏了一個引號、括號沒收好， 害你的程式解析失敗？受限解碼就是根治這件事的技術。它的想法很直接：模型每一步吐出下一個字（token）之前， 先問一個「文法規則」——「照目前已經寫出來的內容，接下來哪些 token 合法？」——然後把所有不合法的 token 機率直接歸零（遮罩，mask），只在剩下的合法 token 上重新分配機率再選字。這樣一來，模型物理上不可能寫出 違反文法的輸出，而不是「事後解析失敗再重試」。

「哪些 token 合法」用一個 DFA（有限狀態自動機）來記：節點是「目前寫到哪個狀態」，邊是「這個狀態允許接哪個 token、接了會走到哪個新狀態」。本頁用一個小而具體的文法 a(b|c)d（語言只有兩個合法字串： abd 和 acd）當骨架，詞表是 [a, b, c, d, z]，其中 z 是文法永遠不接受的 干擾 token。我們刻意讓模型的「原始偏好」在每一步都想選非法的 token（q0 最想選 z、q1 最想選 a、q2b 最想 選 z）——正好凸顯：無約束解碼會產生非法輸出，有約束解碼保證合法。

為什麼 AI 時代重要

當你用 LLM 做 function calling、tool use、結構化抽取（要求輸出嚴格的 JSON / XML / SQL）， 「輸出格式偶爾壞掉」是最惱人也最難靠 prompt 根治的問題。受限解碼把它從「機率問題」變成「保證」——OpenAI 的 response_format: json_schema（Structured Outputs）、outlines、llama.cpp 的 GBNF grammar、guidance、vLLM 的 guided decoding，底層都是同一招：在每一步用一個自動機遮罩掉會讓 輸出違反 schema/文法的 token。看懂這頁的「遮罩 → 重新正規化 → 沿 DFA 轉移」三步，就看懂了為什麼這些工具 能「保證合法 JSON」，以及它們的代價（token 與文法符號邊界對齊的複雜度）。

它是自動機（Aho-Corasick）與取樣（nucleus / Top-p）的延伸

「用一個狀態機，依當前狀態決定下一步的合法轉移」正是 Aho-Corasick 自動機 的血緣——AC 用 goto/fail 邊在文本流上 比對多模式，本頁 DFA 用轉移邊在解碼流上約束合法 token，都是「狀態機驅動的逐步決策」。另一條血緣連到 LLM 取樣策略 Temperature / Top-k / Top-p：nucleus 是「先把分佈重塑成 想要的形狀再抽樣」，受限解碼是「先用 DFA 遮罩掉非法 token 再正規化」——兩者都在 softmax 之後、抽樣之前對 機率分佈動手腳，且可以疊加（先文法遮罩、再 Top-p 截尾、最後抽樣）。

受限解碼流程（讀原始分佈 → 算合法集合 → 遮罩 → 重新正規化 → 選字 + DFA 轉移 → 接受）

DFA 狀態圖：橘色（current）= 當前狀態；綠色邊（合法出邊）= 當前狀態允許的 token 轉移； 粗色邊（relaxing）= 這一步剛走過（選中）的邊；綠色節點（finalized）= 到達的接受狀態。 右側對照表逐 token 呈現「遮罩前（原始）→ 遮罩後（未正規化）→ 重新正規化（受約束）」三欄機率，非法 token 被標灰、機率歸零；合法 token 標綠、被選中者整列反白。每一步還同時秀出「無約束 argmax（模型原本想選什麼）」 對照「受約束 argmax（文法逼它選什麼）」——多數步驟兩者不同，正是受限解碼的價值所在。最後一段（line 8） 示範：即使把 argmax 換成固定種子 LCG 抽樣，因非法 token 機率已被歸零，抽樣同樣不可能選到 z。

固定文法 a(b|c)d（語言 = {abd, acd}）；詞表 [a,b,c,d,z]（z 永不合法）；DFA 5 狀態 5 邊；各狀態原始分佈 固定設計為「無約束 argmax 皆非法」；選字用受約束 argmax（決定性）；line 8 抽樣示範用 seed=3（在 q1 抽中 c， 異於 argmax 的 b 但仍合法）。
已執行步數（steps）：0 階段：init 當前狀態：q0 目前輸出：（空）
文法 a(b|c)d 的 DFA：q0 讀 a 到 q1；q1 分岔讀 b 到 q2b 或讀 c 到 q2c；q2b/q2c 讀 d 到 q3（接受，✓）。 任何一步只要當前狀態沒有某 token 的出邊，該 token 就是非法、機率被遮罩歸零。 誠實揭露：真實 LLM 文法引擎（outlines / llama.cpp grammar / guidance）用更完整的下推自動機與 增量式 tokenizer 對齊（token 與文法符號邊界常不對齊、需處理 byte-level BPE 合併），此為教學骨架； 詞表僅 5 個 token、DFA 僅 5 個狀態，為縮尺示範，非真實模型詞表（真實達數萬 token）；選字用 argmax 是 決定性教學簡化，真實推論多半在受約束分佈上抽樣——但無論 argmax 或抽樣，遮罩都保證輸出合法。

遮罩前 vs 遮罩後（逐 token：原始 → 遮罩後未正規化 → 重新正規化）

token遮罩前遮罩後正規化後合法?
（等待解碼步）

當前狀態合法 token 集合（δ）

（空）

抽樣對照（seed=3，即使抽樣仍保證合法）

單步操作紀錄（opLog）

（空）
受限解碼在每一步用 DFA 的轉移邊決定「哪些 token 合法」，這與 Aho-Corasick 自動機 用 goto/fail 邊在文本上逐字元推進狀態 如出一轍——都是「狀態機驅動、依當前狀態決定下一步」的家族，只是一個約束解碼輸出、一個比對文本輸入。
遮罩掉非法 token、重新正規化這件事，發生在 softmax 之後、抽樣之前，正好可以和 LLM 取樣策略 Temperature / Top-k / Top-p 疊加使用：先文法遮罩保證合法、 再 Top-p 截去長尾雜訊、最後抽樣——兩層對機率分佈的「重塑」互不衝突。