約束解碼

Grammar 允許你強制生成結果符合某種模式，例如只輸出數字、固定選項、特定 JSON 形狀、或 regex 風格約束。遮罩會在每一步直接作用在 logit space，因此它能和 greedy sampling、temperature sampling、beam search，以及各種 early-exit 設定自然組合。

公開 API 表面由 tl.Grammar 類別，以及 Model.generate 上的 grammar= kwarg 組成。

快速開始

import numpy as np
import tinyloop_py as tl
from transformers import GPT2TokenizerFast

# 1. 載入模型與 tokenizer。
model = tl.Model("model.tinyloop", max_seq_len=512)
tok = GPT2TokenizerFast.from_pretrained("gpt2")

# 2. 建立 grammar 所需的 token-id → raw-bytes 對照表。
token_bytes = _build_token_bytes(tok)  # 見下方「如何建立 token_bytes」

# 3. 編譯 grammar（regex）。
g = tl.Grammar(r"[0-9]+")
g.set_token_vocabulary(token_bytes)

# 4. 套用 grammar 生成，輸出保證只會是數字。
prompt = np.asarray(tok.encode("Answer:"), dtype=np.int32)
out = model.generate(prompt, grammar=g, max_tokens=16, temperature=0.0)
text = tok.decode(out[len(prompt):])
print(text)  # 例如 "112345678974467"

`tl.Grammar(pattern)`

把 byte-level regex 編譯成一個 NFA。

g = tl.Grammar(r"\{\"name\":\"[a-z]+\"\}")

參數

名稱	型別	說明
`pattern`	`str`	Regex pattern。匹配對象是 raw bytes，不是 Unicode codepoints；見下方支援語法。

回傳

一個已編譯的 tl.Grammar。若 parse 失敗（括號不平衡、character class 未結束、字串尾端有孤立反斜線等），會拋出 ValueError。

支援語法

採用 Thompson NFA construction，只支援刻意收斂的一小部分經典 regex。目標是 constrained decoding，而不是完整 PCRE 相容。

結構	範例	意義
Literal byte	`a`	匹配位元組 `a`
Character class	`[a-z0-9_]`	匹配集合中的任一單一位元組
Negated class	`[^abc]`	匹配不在集合中的任一單一位元組
Any byte	`.`	匹配任一單一位元組（包含 `\n` 與 `\0`）
Alternation	`a\|b`	二選一
Grouping	`(ab\|cd)`	子表達式分組
Kleene star	`a*`	零次或多次
Plus	`a+`	一次或多次
Optional	`a?`	零次或一次
Digit class	`\d` / `\D`	一個數字 / 非數字
Word class	`\w` / `\W`	一個單字字元 / 非單字字元
Whitespace	`\s` / `\S`	一個空白 / 非空白
Escape char	`\.` `\\` `\[` `\]` `\(` `\)` `\|` `\*` `\+` `\?`	將標點視為字面量
Escape newline	`\n` `\t` `\r`	控制位元組

多位元組 UTF-8 之所以能正確處理，是因為匹配是以 byte-level 進行：. 匹配的是單一位元組，而不是 codepoint。若你需要 Unicode-aware matching，請直接用其實際編碼來表達：

# 匹配任一漢字（3-byte UTF-8 範圍 0xE4xx...0xE9xx）
g = tl.Grammar(r"([\xE4-\xE9][\x80-\xBF][\x80-\xBF])+")

可能拋出的錯誤

ValueError：pattern 有 parse error。錯誤訊息會指出字元位置。

`grammar.set_token_vocabulary(token_bytes)`

安裝 tokenizer 的「每個 token id 對應到哪段 byte sequence」映射。必須在把 grammar 傳給 Model.generate 之前呼叫。

參數

名稱	型別	說明
`token_bytes`	`List[bytes]`	每個 token id 對應一個 `bytes` 物件。`token_bytes[i]` 是採樣器選到 token id `i` 時實際會輸出的 raw byte sequence。其長度也會成為 grammar 的 `vocab_size`。

在 BPE 裡，「raw bytes」到底是什麼

多數 BPE tokenizer（GPT-2、Llama 等）內部並不是直接儲存 raw bytes，而是用一種 "bytes-to-unicode" 的 shifted-string 表示法。Grammar 需要看到的是底層真正的 bytes，因此呼叫端必須把這層技巧反推回來。

GPT-2 的標準函式是 transformers.models.gpt2.tokenization_gpt2 裡的 bytes_to_unicode()；把它反轉後，就能得到 unicode_char → byte 的對照表。以下把它 inline，是為了避免耦合到較慢的 tokenizer class：

def gpt2_bytes_to_unicode():
    bs = (list(range(ord("!"), ord("~") + 1)) +
          list(range(ord("¡"), ord("¬") + 1)) +
          list(range(ord("®"), ord("ÿ") + 1)))
    cs = bs[:]
    n = 0
    for b in range(256):
        if b not in bs:
            bs.append(b); cs.append(256 + n); n += 1
    return dict(zip(bs, (chr(c) for c in cs)))

def _build_token_bytes(tok) -> list[bytes]:
    encoder = gpt2_bytes_to_unicode()
    byte_decoder = {c: b for b, c in encoder.items()}
    vocab_size = len(tok.get_vocab())
    out = []
    for i in range(vocab_size):
        s = tok.convert_ids_to_tokens(i, skip_special_tokens=False)
        try:
            raw = bytes(byte_decoder[c] for c in s)
        except KeyError:
            # Special tokens (<|endoftext|>, etc.) 不在 byte map 中；
            # 給它們一個不可能被 grammar 接受的 byte。
            raw = b"\x00"
        out.append(raw)
    return out

對其他 tokenizer 而言，反推方式取決於詞彙表本身的布局。例如 SentencePiece 會用 sp.id_to_piece(i).replace("▁", " ")，Llama 的 BPE 則有另一套 byte-to-unicode table。Grammar 真正在乎的只有最後得到的 bytes per id；至於怎麼還原，則完全取決於 tokenizer。

`grammar.initial_legal_tokens()`

一個 debug helper，用來回傳 grammar 在初始狀態下允許的 token id 清單。它非常適合拿來檢查 set_token_vocabulary 是否設定正確：

g = tl.Grammar(r"[0-9]+")
g.set_token_vocabulary(token_bytes)
legal = g.initial_legal_tokens()
print(f"{len(legal)} digit-starting tokens in the vocab")
# 對任何像樣的 GPT-2 風格 tokenizer，都應該至少有 10+（0..9 與多位數 token）

屬性

屬性	意義
`grammar.vocab_size`	grammar 綁定的 token 數量（在 `set_token_vocabulary` 之前會是 0）
`grammar.num_states`	NFA 節點數，大致與 regex 複雜度成正比。可拿來做 sanity check，例如 `[0-9]+` 約會編成 4 個 state，而一個 JSON 形狀 regex 約 15 個。

與 `Model.generate` 搭配使用

直接把 grammar 傳進 grammar= kwarg 即可。其他 kwargs（sampling、beam、stop sequences）都能正常組合：

# Greedy + grammar
out = model.generate(prompt, grammar=g, max_tokens=32, temperature=0.0)

# Sampling + grammar
out = model.generate(prompt, grammar=g, max_tokens=32,
                     temperature=0.8, top_k=50)

# Beam search + grammar（內部會為每個 beam 追蹤自己的 parse state）
out = model.generate(prompt, grammar=g, max_tokens=32,
                     beam_size=4, length_penalty=0.7)

在什麼情況下 generation 會停止

套用 grammar 的生成，會在以下任一條件成立時結束：

達到 max_tokens
命中 stop sequence（若有設定 stop_sequences）
Grammar 進入某個 terminal state，且再也沒有任何 token 合法，也就是 grammar 已完整吃完、且不接受任何延續。這是 constrained output 最常見的正常結束方式，例如 (yes|no|maybe) 在輸出 "maybe" 後，grammar 就會拒絕所有下一個 byte。
抽到 EOS token，且該 token 也通過 grammar mask

Grammar 不要求在 max_tokens 命中之前一定抵達 accepting state。也就是說，如果輸出在達到上限時還停留在某個 derivation 中途，它仍會原樣返回。如果你需要「保證輸出完整」，請把終止符寫進 grammar 裡（例如 JSON 要求 "}"、行結構輸出要求 \n），並把 max_tokens 設得明顯大於最長合法推導。

每個 beam 的 grammar state

在 beam search 下，每個 beam 都會維護自己的 parse state；隨著各 beam 選出不同 next token，狀態自然分岔。這正是你想要的行為：一個已承諾輸出 {"a 的 beam，與另一個已承諾輸出 {"b 的 beam，本來就該位在不同 grammar 位置，並被套用不同遮罩。

成本

Grammar compile time：O(pattern length)。每次 tl.Grammar(pattern) 只做一次。即使是複雜 pattern（例如某個 JSON schema），通常也能在 1 ms 內編完。
Per-step mask cost：最壞情況是 O(vocab_size × avg_token_bytes)，但會受 per-state mask cache 攤銷。同一 parse state 重複出現時，第一次之後就是 O(1)。
Logit mask application：在 host 端做 O(vocab_size) 操作（因為 logits 早已在 scoring 之後位於 host）。

不需要新增任何 GPU kernel；遮罩完全是 host 端邏輯。對 vocab=50257 的設定來說，mask 成本通常只是每步數微秒，和 attention 相比幾乎可忽略。

常見模式

僅允許數字

g = tl.Grammar(r"[0-9]+")

多選一（function-calling、分類）

可以用 grammar_choice 風格的 pattern：

g = tl.Grammar(r"(search|reply|escalate|refuse)")

或者動態組合：

choices = ["search", "reply", "escalate", "refuse"]
pattern = "(" + "|".join(re.escape(c) for c in choices) + ")"
g = tl.Grammar(pattern)

固定 schema 的 JSON

# 最小型：只有一個字串欄位的 object。
g = tl.Grammar(r'\{"name":"[a-z]+"\}')

# 稍微寬鬆：允許標點周圍有空白。
g = tl.Grammar(r'\{\s*"name"\s*:\s*"[a-z ]+"\s*\}')

# 多欄位版本。雖然冗長，但真正支援遞迴 schema 的 GBNF→FSA parser
# 目前仍列在後續工作裡。
g = tl.Grammar(
    r'\{"name":"[a-z]+","age":[0-9]+,"city":"[a-z ]+"\}')

若要完整支援 JSON schema（遞迴 object、array、巢狀結構），路線圖中已有專門的 grammar_json_schema(schema_dict) helper。在那之前，請針對你的實際輸出形狀手寫 regex。

允許開頭有空白（BPE 常見陷阱）

多數 GPT-2 家族 token 都會帶 Ġ（編碼後的空白），因為 tokenizer 偏好選擇「前面帶空白」的 token。當你在 "Answer:" 這種 prompt 之後開始生成一個新片段時，模型自然傾向選擇帶前導空白的 token。

如果你的 grammar 不允許一開始出現空白（例如 [0-9]+），那麼 mask 會拒絕所有帶空白前綴的 token，模型就只能退而求其次選擇不帶空白的 digit token。GPT-2 的確有這類 token（單數字、短數字 token），但通常機率比較低，因此雖然輸出仍符合 grammar，看起來可能不那麼自然。

解法是直接允許前面有一個可選空白：

g = tl.Grammar(r" ?[0-9]+")

Grammar + beam search

g = tl.Grammar(r"(Yes|No|Maybe)\.")
out = model.generate(
    prompt, grammar=g, max_tokens=8,
    beam_size=4, length_penalty=1.0,
)

每個 beam 都有自己的 grammar state。走到死路的 beam 會被視為 "finished" 繼續參與排序，讓全域 top-k 仍能正確評估它們。

錯誤條件

ValueError：regex 解析失敗
RuntimeError：在沒有先呼叫 set_token_vocabulary 的情況下，把 grammar 傳給 Model.generate
RuntimeError：token_bytes 的長度與實際 vocab 不匹配，導致某些 token id 無法被索引

另見

Generation：grammar= 如何與 sampling / beam / early-exit 組合
Scoring：若你想先觀察 logits，再決定是否加上 grammar

快速開始​

tl.Grammar(pattern)​

參數​

回傳​

支援語法​

可能拋出的錯誤​

grammar.set_token_vocabulary(token_bytes)​

參數​

在 BPE 裡，「raw bytes」到底是什麼​

grammar.initial_legal_tokens()​

屬性​

與 Model.generate 搭配使用​

在什麼情況下 generation 會停止​

每個 beam 的 grammar state​

成本​

常見模式​

僅允許數字​

多選一（function-calling、分類）​

固定 schema 的 JSON​

允許開頭有空白（BPE 常見陷阱）​

Grammar + beam search​

錯誤條件​

另見​