Grammar-Constrained Decoding: Test JSON Guarantees

Grammar-constrained decoding can guarantee JSON syntax only when every proposed subword token preserves a prefix that still has a valid completion. This guide builds an independent exhaustive oracle, kills plausible masking mutants, and marks the exact boundary between syntax, supported schema structure, semantics, and truth.

Grammar-constrained decoding starts with a narrow guarantee

Grammar-constrained decoding can guarantee that emitted bytes belong to the grammar you actually implemented. That is narrower than “the model understands the schema,” yet far more useful than hoping a malformed response can be repaired after generation. Write the guarantee as a membership claim: after every accepted token, the accumulated byte prefix must still have at least one completion in a bounded JSON language.

The distinction matters because several promises are often collapsed into one. Parseable JSON is a syntax property. A covered JSON Schema subset adds structural constraints such as required keys and primitive types. Business rules add semantics, and task correctness asks whether the values are true and useful. Only the first two can be enforced by the decoder described here.

The lab fixes a tiny document shape with one required string key and one bounded integer. It also fixes an awkward vocabulary containing punctuation, fragments, complete literals, an invalid escape, and tokens that cross multiple grammar terminals. Those crossing tokens are the point: a character filter can approve the first byte and still conceal an impossible suffix.

This is the operating contract for grammar-constrained decoding: tokenizer identity, grammar identity, parser state, candidate token bytes, masked probability mass, renormalized probabilities, and terminal status travel together. Change any member and the receipt changes. The technique is related to schema-derived agent fuzzing, but fuzzing asks which inputs break a tool while decoding asks which next tokens preserve a possible document.

Align subword tokens with grammar prefixes

A language model samples token IDs, not grammar terminals. One token may contain a quote, key fragment, colon, opening quote, and part of a value. Another may end in the first byte of an escape. The masker therefore cannot ask whether each character is locally legal; it must feed every byte through an incremental parser state and retain the token only when the resulting prefix still has a valid completion. This byte alignment is the first real test of grammar-constrained decoding.

Consider a state expecting the literal "mode" followed by a colon and a string. The token "mode":"fa crosses a key boundary, punctuation, and the start of the value. Rejecting it because it is not one terminal harms coverage. Accepting it because its first quote is legal risks invalid suffixes. Correctness requires whole-token simulation against the same byte convention used by the tokenizer.

The tokenizer ledger records the exact UTF-8 byte sequence for each token. Display strings are not enough: visually similar Unicode sequences can have different bytes, and a replacement character can hide a decoding failure. A production input validator should reject lone surrogates, incomplete escapes at end of stream, and token IDs outside the declared vocabulary; the bounded artifact demonstrates the underlying byte-prefix and identity implications rather than presenting those three cases as separate fixtures.

This alignment is where token masking becomes engineering instead of a diagram and where structured outputs acquire a precise lower-bound guarantee. Cache parser states only under a key that includes the grammar and tokenizer identities. A state cached for a different vocabulary or schema can yield a convincing but false mask. The receipt makes that cache boundary explicit, even though the lab does not claim production-scale cache performance.

Compute a mask and verify it with an independent oracle

The production masker advances an explicit state machine through candidate bytes. Its independent oracle does something structurally different: it enumerates every complete document in the bounded language, converts each to bytes, and asks whether the proposed prefix matches the beginning of at least one member. The oracle is expensive and deliberately tiny, which makes it suitable for tests rather than serving. That separation turns grammar-constrained decoding into a falsifiable implementation claim.

These two paths should agree on every vocabulary entry at every reachable prefix. Agreement means a token is allowed if and only if at least one exhaustive document begins with current-prefix-plus-token. Disagreement is recorded with token ID, byte spelling, production verdict, oracle verdict, and parser state. A single mismatch blocks the receipt.

The approach follows the central concern in automata-based constrained decoding: constraints must operate at model-token granularity while preserving the target language. Recent work on flexible grammar-constrained decoding shows why preprocessing and state transitions matter for practical systems. The lab borrows the proof shape, not their performance claims.

This oracle is intentionally independent of the production transition table. If both paths call the same parser helper, they can agree on the same bug. Enumeration provides a different failure surface: changing a transition may fool the masker, but it cannot silently rewrite the frozen set of complete byte strings.

Renormalize probability without inventing quality

Masking changes the sampling distribution. Start with finite logits, compute a stable softmax, set the probability of rejected tokens to zero, and divide each surviving value by the surviving mass. The sum after renormalization should be one within a declared floating-point tolerance. If no token survives, fail closed with state evidence instead of reviving an illegal candidate.

The ledger should show original probability, allowed status, masked contribution, and renormalized probability. That makes two common bugs visible. First, zeroing illegal tokens without dividing again produces a distribution whose total is below one. Second, normalizing before all filters are applied can reintroduce mass through a later sampling stage.

Renormalization is mechanics, not a quality claim. A perfectly normalized legal set can force dull, biased, or factually wrong output because the grammar says nothing about truth. The comparison with top-k, top-p, and min-p filters is useful: sampling filters alter candidate support for a heuristic quality-diversity tradeoff, while constrained sampling removes tokens that cannot satisfy a declared language. When combined, the order and empty-set policy must be explicit.

The artifact reports masked mass because a near-one value is operationally interesting: the base model strongly preferred illegal continuations. It does not label that value as model quality. Evaluation needs a representative workload, semantic validators, and outcome measures outside this proof.

Handle strings, escapes, Unicode, numbers, and EOS

JSON’s small grammar still has sharp edges. Strings must reject unescaped controls, treat backslash as a state transition, and distinguish a completed escape from an incomplete one. Unicode escape syntax needs exactly four hexadecimal digits per unit; application-level handling of surrogate pairs is a separate semantic decision. The lab keeps its value alphabet bounded so every completion remains enumerable.

Numbers are equally easy to approximate badly. A minus sign, integer zero, nonzero digit sequence, fraction, and exponent have different continuation rules. This study limits the integer field to 0 through 12, then encodes that limit directly in the exhaustive language. It does not pretend that a generic numeric grammar enforces arbitrary minimum and maximum constraints.

End-of-sequence is a token with a grammar condition. EOS is allowed only when the current bytes equal one complete document, not merely when the prefix is syntactically quiet. A premature-EOS mutant demonstrates the difference. Conversely, once a complete document is reached, punctuation or another object must remain forbidden unless the declared language permits a sequence.

Production integrations such as llama.cpp LLGuidance document real schema-to-grammar machinery and its boundaries. This lab stays smaller: it names its supported subset, reports unsupported keywords, and rejects a schema identity claiming features that were not compiled. Honest coverage is safer than a green “valid JSON” badge.

Separate syntax, schema coverage, semantics, and truth

A useful evidence stack has four visible rungs. The first proves parseable JSON. The second proves membership in the implemented JSON Schema grammar subset. The third runs semantic validation such as an allowed product identifier, a date relationship, or authorization rule. The fourth evaluates whether the response accomplished the task and whether factual claims are grounded.

The decoder owns only the lower rungs. For example, a grammar can require {"city": string, "temperature": integer}. It cannot establish that the city exists, that the reading came from a sensor, or that the unit matches the interface. Treating syntax as truth invites tools to execute polished nonsense.

This boundary also clarifies architecture. A resource returned through MCP resources and tool results may carry typed data, but the consumer still needs provenance and authorization. Likewise, prompt caching metrics can measure reuse without proving that the cached instruction describes the current contract. Identities help custody; validators establish different properties.

Put each rung in the release note with its owner. Decoder tests own prefix safety and EOS. Schema compilation tests own keyword coverage. Application code owns semantic constraints. Product evaluation owns task outcomes. The labels prevent a technically accurate result from acquiring a larger marketing claim during handoff.

Mutation-test the decoder and validate its receipt

Happy-path examples are weak evidence because most masker bugs preserve familiar documents. For grammar-constrained decoding, the lab runs named executable mutants: character-only masking, premature EOS, invalid-escape acceptance, ignored unsupported keywords, reused foreign state, missing renormalization, and a receipt hash that omits identities. Each mutant must produce a measurable disagreement with the exhaustive oracle or the reconstruction validator.

The exported JSON is not trusted because it contains a hash. Validation reparses it, checks an exact schema and key set, reconstructs the tokenizer, grammar, documents, prefix, logits, production mask, oracle mask, mass, probabilities, terminal state, and mutation outcomes, then deep-compares the canonical result. A coordinated attacker who changes both a result and its stored hash still fails because reconstruction begins from the bounded inputs.

CSV is a transport envelope around the same canonical JSON rather than a lossy summary. The parser handles quotes, reconstructs the embedded object, and applies the identical validator. Exact-key reconstruction implies rejection of unknown keys, nonfinite or changed logits, out-of-range vocabulary identities, altered grammar identity, reordered token bytes, and forged mutation evidence. Those six cases describe validator consequences; the executable suite directly exercises mask, identity, export, and coordinated-tamper cases rather than claiming six additional named fixtures.

This strict path is intentionally heavier than ordinary analytics export. Its purpose is to make the proof portable. A reviewer can reproduce what was allowed and why without trusting the live page, a screenshot, or a mutable cache.

Decide what a constrained decoder may safely ship

Ship only after the bounded oracle agrees across reachable states, every named mutant dies, unsupported schema features fail visibly, exports reconstruct exactly, and tokenizer plus grammar identities are pinned. In production, add workload-scale tests, latency budgets, cancellation, telemetry for empty masks, schema-version rollouts, and semantic validation before tool execution.

Prefer the smallest promise the evidence supports. “This grammar-constrained decoding path emits documents in grammar G for tokenizer T” is testable. “This feature always returns valid structured output” is incomplete unless valid names the syntax, supported schema subset, semantic checks, and failure behavior. “The model returns correct answers” is a different evaluation entirely.

The artifact is a microscope for one bounded contract, not a provider ranking or universal JSON Schema engine. It uses a tiny vocabulary and exhaustive document set precisely so failure is inspectable. A production compiler may support far more structure, yet the same release logic applies: identify, reconstruct, compare independently, kill plausible mutants, and publish the boundary.

That discipline makes grammar-constrained decoding valuable without mystique. It turns one narrow guarantee into reliable infrastructure while leaving factuality, safe intent, and product quality where they belong: explicit downstream checks. Teams marketing structured outputs should publish this boundary as clearly as their happy-path examples.

Runnable local artifact — The lab proves membership in one implemented bounded grammar and cannot prove factuality, safe tool intent, semantic correctness, model quality, or complete JSON Schema support.

Choose a reachable prefix and inspect whole-token production and exhaustive-oracle masks, probability mass, renormalization, EOS, seven mutation fixtures, and strict JSON/CSV receipts.