Make Invalid Tokens Impossible

The model returns:

{"tool":"transfer_funds","amount":1000,"currency":"USD",}

One trailing comma makes the output invalid JSON. The model spent tokens. The user waited. The parser rejects it. The application sends a repair prompt and pays again.

Constrained decoding takes a different approach. Before sampling each token, the runtime asks which vocabulary tokens can still lead to a string accepted by the required grammar. Impossible tokens receive zero probability.

The trailing comma is not repaired. It is never allowed.

That is powerful and narrow. The grammar can ensure that amount is a number. It cannot establish that the amount should be 1,000, that the account has funds, or that this user may transfer them.

Parsing after generation detects failure too late

The common retry pattern is:

generate free-form text
extract a JSON-looking substring
parse
if invalid, append the error and ask again

This is useful as a fallback, but it has three weaknesses.

First, malformed output consumes a full attempt before detection. Second, the repair prompt grows context and can introduce a new error. Third, a permissive extractor may silently “fix” output in a way the model did not intend.

Post-generation validation remains necessary. The mistake is asking it to prevent syntax it can only reject.

Constrained generation inserts the formal language into the decode loop:

state = grammar.start
while not state.accepting:
    logits = model(prefix)
    allowed = grammar.tokens_that_can_extend(state)
    token = sample(mask(logits, allowed))
    state = grammar.advance(state, token)
    prefix.append(token)

Real engines batch requests, cache masks, handle token healing, compile schemas, and integrate with GPU sampling. The loop exposes the invariant: every committed prefix must remain extendable to a valid complete output.

PICARD made the parser part of decoding

PICARD constrains autoregressive text-to-SQL generation through incremental parsing. At each step it rejects tokens that would make the partial SQL inadmissible under its parser mode.

This illustrates a general pattern:

• JSON grammar for structured objects;
• regular expression for bounded lexical formats;
• context-free grammar for nested languages;
• incremental parser for a programming or query language;
• finite set for enums and tool choices.

The constraint should match the actual contract. A regular expression can enforce a simple identifier. Nested arrays and recursive expressions need a richer grammar. SQL syntax may require parser state plus schema-aware checks.

The paper's text-to-SQL results do not imply that constrained SQL is correct SQL. A syntactically valid query can select the wrong table, leak rows, or delete data.

The grammar operates on characters; the model operates on tokens

A model vocabulary is not a character keyboard. One token may represent:

"amount"
": 100"
"},\n"
a partial Unicode sequence
leading whitespace plus a word

The constraint engine must determine whether appending an entire token's decoded bytes or characters can lead to a valid string. Naively allowing only tokens equal to one expected terminal can reject efficient multi-character tokens or permit invalid boundaries.

DOMINO focuses on subword-aligned constrained generation and argues that misalignment can hurt task accuracy as well as speed. It is an author preprint, so its reported overhead results stay scoped to its implementation and experiments.

Tokenizer concerns include:

• byte fallback and invalid intermediate Unicode;
• tokens spanning multiple grammar terminals;
• whitespace encoded with the following token;
• ambiguous prefixes;
• end-of-sequence only when the grammar is accepting;
• stop strings that intersect valid output;
• chat-template tokens outside the generated payload.

Test the compiled grammar against the exact tokenizer and model revision. A schema test that operates on characters alone does not prove token-level completeness.

Masking changes probability, not model knowledge

Suppose the model assigns probability to four next tokens:

Token	Original probability	Grammar status
"USD"	0.45	allowed
"EUR"	0.30	allowed
"dollars"	0.20	invalid enum
null	0.05	invalid type

After masking the invalid tokens, allowed probabilities are renormalized:

P(USD | allowed) = .45 / (.45 + .30) = .60
P(EUR | allowed) = .30 / .75 = .40

The grammar guarantees one allowed currency string. It does not tell the model which currency the user intended. If the evidence is ambiguous, the output will still choose an allowed value unless the schema represents uncertainty or an abstention action.

Design an explicit branch:

{"kind":"need_clarification","field":"currency","question":"Which currency?"}

A schema that has no representation for “unknown” can force a model to lie validly.

Syntax, schema, semantics, authority, and execution are five gates

Use precise names.

1. Syntactic validity

The output belongs to a formal language. It is parseable JSON or SQL.

2. Schema validity

The parsed value has required fields, types, enums, ranges, patterns, and object shape. JSON can be syntactically valid while violating a JSON Schema.

3. Semantic validity

Values make sense in current domain state. The customer exists, currency matches the account, dates are ordered, cited source supports the claim, and referenced file lies inside the repository.

4. Authorization

The authenticated principal may perform this operation on this object for this purpose within budget and approval policy.

5. Execution validity

The operation commits exactly once or is safely retryable, respects concurrency, and returns a durable receipt. The world may change between validation and execution, so critical rules belong inside the transaction.

Constrained decoding primarily strengthens the first two. Some grammars can encode more, but live database state and identity cannot generally be compiled once into a static token mask.

Schema design is product design

The model can only express choices the schema permits. Bad schemas create forced guesses, ambiguous unions, and dangerous defaults.

Prefer discriminated actions:

{
  "kind": "transfer",
  "from_account_id": "acct_123",
  "to_account_id": "acct_987",
  "amount_minor": 100000,
  "currency": "USD",
  "idempotency_key": "task_456:step_7"
}

over an object where dozens of optional fields imply the action type.

Include:

• explicit unit in the field name;
• enums instead of unconstrained labels;
• string patterns for identifiers, followed by existence checks;
• bounded arrays and lengths;
• additionalProperties: false where supported and appropriate;
• an abstain, clarify, or escalate variant;
• a version field when contracts evolve;
• no executable secrets or hidden defaults.

Avoid schemas that encode policy by description only. If amount must be positive, use a numeric constraint plus a semantic rule. If a field is conditionally required, express the discriminated branch rather than hoping prose is followed.

Smaller schemas reduce compile cost, mask complexity, prompt tokens, and model confusion. Expose only tools eligible for the current workflow state.

Unsupported schema features are a correctness risk

JSON Schema is broad. Serving providers and grammar compilers commonly support subsets. References, recursion, numeric ranges, Unicode patterns, conditionals, defaults, and oneOf semantics may behave differently.

The compiler should return a capability report:

supported exactly
lowered to an equivalent grammar
validated only after generation
unsupported and rejected

Silently ignoring an unsupported constraint is worse than failing compilation. The application believes a property is enforced when it is not.

Version compiled grammar with:

schema_hash, compiler_version, tokenizer_hash,
model_revision, runtime_version, supported_feature_manifest

XGrammar, an author preprint, studies efficient context-free grammar execution by separating tokens that can be prechecked from those requiring runtime interpretation and integrating mask work with inference. Treat performance as a systems implementation question, not a reason to skip compatibility tests.

Retry economics make prevention measurable

Assume an illustrative unconstrained tool call has an 18 percent structural-invalid rate. Each attempt costs $0.006 and takes 900 ms. Under a deliberately simple independent geometric retry model:

expected attempts = 1 / (1 - .18) = 1.2195
expected generation cost = .006 / .82 = $0.007317
expected generation latency = 900 / .82 = 1,097.6 ms

Now assume constrained decoding enforces the supported shape in one attempt and adds 70 ms of compilation/mask overhead:

cost = $0.006
latency = 970 ms

At 100,000 calls, generation-only saving is about:

100000 * (.007317 - .006) = $131.71

The chart uses indexed illustrative amounts, not vendor pricing. If grammar infrastructure costs more, the route is too small, or constraints lower semantic success, the economic ranking changes.

Both paths still need semantic validation. Constrained decoding saves malformed-output work; it does not remove business-rule retries.

Grammar work joins the serving scheduler

Constrained decoding adds CPU-side or accelerator-side work around every token step. The runtime may need to advance parser state, find allowed vocabulary tokens, construct or retrieve a mask, transfer it, and apply it before sampling. Under continuous batching, active sequences can have different grammars and different parser states.

Three workloads behave differently:

1. thousands of requests share one small schema;
2. each tenant has a versioned variant of a medium schema;
3. every agent step constructs a unique grammar from live choices.

The first can amortize compilation and reuse masks. The third can spend more time compiling than decoding short outputs.

Measure separately:

schema normalization and grammar compilation
first-token mask initialization
per-token parser-state advance
allowed-token or mask computation
mask transfer and sampler application
cache lookup, hit, eviction, and memory

Use a grammar cache key that includes normalized schema, compiler, tokenizer, and relevant runtime semantics. A cache keyed only by raw JSON text misses equivalent schemas with reordered fields. A cache that omits tokenizer revision can return an invalid mask program.

Schema cardinality affects memory. If an application dynamically embeds 20,000 customer IDs into an enum, it produces a large changing grammar and leaks business state into the model contract. Prefer a bounded identifier pattern followed by authorized existence validation, unless restricting to a small explicit choice set is the actual user experience.

Dynamic enum choices are useful for a dozen visible options, such as eligible deployment regions. Include stable IDs and labels, then validate that the choice is still available at execution. Do not use grammar enumeration as a substitute for database access control.

Batch telemetry should include constrained and unconstrained sequences by schema class. A slow grammar worker can stall GPU sampling even when model kernels are fast. If mask construction is asynchronous, ensure the scheduler cannot sample a sequence before its current mask is ready.

Test overload with many distinct schemas, not only one warm grammar. Report:

• compilation p50/p95/p99;
• tokens per second and TPOT by grammar complexity;
• grammar-cache hit rate and bytes;
• scheduler stalls waiting for masks;
• maximum active constrained sequences;
• goodput under valid-output and latency objectives.

A constrained path may emit fewer retries and still reduce raw token throughput. The decision belongs at verified tool outcomes per deadline, where prevented invalid attempts can outweigh mask overhead.

Constraints can make quality worse

A grammar may be formally correct and still fight the model.

• The expected format is unlike training examples.
• The schema forces an answer when evidence is missing.
• An enormous enum leaves little useful probability mass.
• Deep optional nesting creates long fragile paths.
• The tokenizer alignment implementation masks valid high-probability tokens.
• Constraint order causes repetitive but valid structures.
• The model lacks knowledge to populate required fields.

Compare semantic success between constrained and unconstrained-plus-repair paths. Test adversarial and edge values, not only validity rate.

When a grammar reaches a state with no allowed tokens before acceptance, fail closed with diagnostic state. Do not disable constraints mid-generation and return an untrusted suffix.

Agent tools need a two-phase contract

Separate proposal from effect:

1. model emits constrained action proposal
2. validator resolves entities and rules
3. authorizer binds authenticated principal and approvals
4. executor commits with idempotency and transaction checks
5. tool returns immutable receipt
6. agent observes receipt, not its own prediction

For consequential writes, show a human or policy engine the typed proposal after semantic validation and before execution. Approval must bind to the exact normalized action; changing fields invalidates it.

Never let a cached or generated message such as {"status":"paid"} substitute for the executor's receipt. The model describes intent. The tool establishes state.

A builder playbook

1. Measure current failure classes

Separate extraction failure, parse failure, schema failure, semantic failure, authorization denial, execution conflict, and outcome failure. Constrained decoding only targets some of them.

2. Minimize the action language

Use small discriminated schemas with units, bounds, explicit uncertainty, and only eligible tools. Reject unsupported compiler features.

3. Compile against the exact tokenizer

Test every schema with the production model/tokenizer/runtime tuple. Fuzz valid and invalid instances and verify that all valid strings remain generatable while invalid strings do not.

4. Benchmark mask overhead under batching

Report grammar compilation, time per token, TTFT, TPOT, throughput, memory, cache reuse, and SLO goodput across schema complexity and concurrent requests.

5. Evaluate semantic outcomes

Use real tool tasks with entity, range, temporal, permission, and ambiguity cases. Compare constrained, unconstrained, and retry-repair routes on verified completion.

6. Enforce runtime authority

Validate live state, authenticate and authorize, bind approvals, use idempotency keys, execute transactionally, and return receipts.

7. Price the full path

Include failed generations, grammar infrastructure, validator calls, tool attempts, review, latency, and failure loss. A valid JSON rate is not an ROI metric.

The decision

Use constrained decoding whenever a formal output contract is required, the deployed engine supports the needed language faithfully, and structural retries are material. Keep post-generation parsing as defense and compatibility validation.

Then build the gates the grammar cannot: semantics, authorization, idempotent execution, and verified receipts.

The safe tool call is not the one that parses. It is the one whose shape was enforced, meaning was checked, authority was proven, and effect was observed.

References

• PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models, Scholak, Schucher, and Bahdanau, EMNLP 2021. Makes incremental parsing part of token acceptance for text-to-SQL.
• Guiding LLMs the Right Way: Fast, Non-Invasive Constrained Generation, Beurer-Kellner, Fischer, and Vechev, 2024 preprint. Focuses on subword-aligned constraint execution through DOMINO.
• XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models, Dong et al., 2024 preprint. Studies efficient context-free grammar masking integrated with serving.
• Guidance: Control Language Model Output, Microsoft Research. First-party technical material for a structured generation library using selects, regexes, and grammars.

All retry rates, timings, and costs in the worked example are illustrative. Inputs and calculations are retained in the claim ledger.