M2Medium★ Agent Engineering Essential · Zero Schema FailuresPart M · LLM Eval & RAG/Agent Ops

Constrained JSON Decoding via FSM Logit Masking

⚡Flashcard Drill➔

Mask disallowed vocabulary logits per FSM state prior to Softmax so schema-violating tokens receive zero sampling probability.

⏱️ Time: O(|V|) 位掩码过滤每步
💾 Space: O(|States| * |V|) 预编译允许表
🎯 Interactive Self-Practice Loop (Attempt Before Peeking)
Practice in 4 steps: recall mechanism, complete core lines, check edge cases, and log mastery locally.
Step 1 · Mechanism Recall & Stability Self-Check
Step 2 · Complete Key Implementation Lines
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 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: What is Jump-Forward Decoding and why does it speed up constrained JSON output?
Next: RAG Chunk Boundary Collapse & Overlap Recall Audit →
💡

Core Mental Anchor / Mnemonic

Compile schema to FSM; mask invalid logits to -1e9 before Softmax so illegal syntax has probability zero.

📐 Mathematical Derivation & Core Formula

z~v={zvif v∈Vallowed(st)−∞otherwise\tilde{z}_v = \begin{cases} z_v & \text{if } v \in \mathcal{V}_{\text{allowed}}(s_t) \\ -\infty & \text{otherwise} \end{cases}
### Zeroing Invalid Grammar Branches at Sampling Time
Prompting alone cannot prevent malformed JSON brackets or stray prose. Compiling JSON schemas into a Finite-State Machine (FSM) allows precomputing valid vocabulary masks Vallowed(st)\mathcal{V}_{\text{allowed}}(s_t) for every state sts_t. Setting disallowed logits to -1e9 prior to Softmax strictly guarantees zero sampling mass on syntax-breaking tokens.

🔄 Tensor Dimensions & Shape Flow

state -> valid vocab mask:(|V|,) -> np.where(mask, logits, -1e9) -> Softmax -> sample & transition

🛡️ Numerical Stability & Pitfalls Checklist

  • Assert at least one valid token exists in the mask to avoid vacuous masks.
  • Precompile state-to-token-bitmask lookup tables offline across full BPE subword vocabularies for sub-millisecond inference overhead.

💻 Reference Code Implementation

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

🧪 Runnable Assertions & Validation

Copy and run directly in 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")

🎯 Core Follow-up Inquiries & Reference Answers

Q1:What is Jump-Forward Decoding and why does it speed up constrained JSON output?
When the FSM reaches deterministic literals (such as fixed JSON key names or delimiters where only one valid transition exists), the engine appends those deterministic tokens in one shot instead of running GPU decode steps for every character.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
← Prev: LLM-as-a-Judge Position Swap & Cohen's KappaBack to Part M & All 105Next: RAG Chunk Boundary Collapse & Overlap Recall Audit →