What a grammar can never check

Constrained decoding is the most reassuring feature in the structured-output toolbox. Hand the engine a grammar, and every token the model emits is checked against it before it is sampled, so the output is guaranteed to be valid JSON, to match the schema, to use one of the allowed enum values, to close every bracket it opens. The guarantee is real and it is narrower than it feels. A grammar can guarantee the shape of an output. It cannot guarantee its reference: that a field equals an earlier field, that a quoted span appears verbatim in the source it claims to quote, that an identifier exists in a table that was live at the moment of decoding. The reason is a theorem, not an engineering gap, and the theorem draws a line that every structured-output pipeline has to respect with a second component.

The copy-language wall

The engines that make constrained decoding fast, and the theory I worked with in my parsing research, both run on context-free grammars. XGrammar's central result, in the paper that introduced it, is that for a JSON grammar over a 128,000-token vocabulary, only 1,134 tokens are context-dependent, meaning their validity depends on the full parser stack rather than on the current rule; the other 99 percent can be precomputed at compile time. That is what takes the mask below 40 microseconds per token, and its 2026 successor extends the same machinery to grammars that change within a request. All of it is context-free by construction, because a pushdown automaton is what can be run per token at that speed.

Here is the wall. The language of strings of the form w followed by w, for any w over an alphabet of two or more symbols, is the copy language, and it is not context-free. The pumping lemma for context-free languages proves it: any sufficiently long string in a context-free language can be pumped in two places at once while staying in the language, and a copy of a copy cannot survive that, because pumping one half breaks its match with the other. The consequence for decoding is exact. "This field equals that field" is the copy language. "This quoted span appears verbatim in the passage" is the copy language with the passage as the first half. No context-free grammar recognises either, so no mask built from one can enforce either, at any cost, with any engine.

What lies on each side

It helps to write the constraints down by the formal class they need, because the line between enforceable and not is sharper than intuition suggests.

The rows above the line are the ones the sales pitch is about, and the grammar handles them completely. The rows below are the ones that decide whether the output is useful, and they share a property: each one relates the output to something outside the current grammar state, another part of the output, a document, a database, an arithmetic fact. A pushdown automaton has one stack and no memory of what it popped. It can count nesting; it cannot remember a string to compare against later.

What the theorem does not forbid

The wall is precise, and it is worth being precise about what is on the near side of it, because some constraints that sound like reference are shape in disguise. A field that must equal a fixed constant is a regular language: the constant is written into the grammar. A field that must be one of a set of values known before decoding starts is an enum, and an enum is regular however large, so if the set of valid identifiers for this request is known when the grammar is compiled, membership in it is enforceable; engines that compile a grammar per request, which is what the dynamic machinery in XGrammar-2 exists for, make that practical for sets of a few hundred or a few thousand values. The wall is for the set that is not known at compile time, because it depends on what the model has already generated or on a lookup that happens later, and for equality between two spans the model produces.

The frontier also moves. Work on type-constrained decoding for code generation enforces typing rules during decoding that a context-free grammar cannot express, by giving the decoder a checker with more state than a stack. That is not a refutation of the wall; it is a checker moved inside the loop, and it pays for its extra state per token. The question for any pipeline is the same either way: which constraints are checked by an automaton with a stack, which by something with more memory, and where in the pipeline each one runs.

The gate after the decoder

The architecture that follows is two components rather than one. The decoder runs with the grammar and guarantees shape. A checker runs on the finished output and verifies reference: it compares the fields that must match, searches the source for every quoted span, looks up every identifier, adds up every total. An output that fails the checker is rejected or regenerated, and the checker's failure rate is a number the team has to know, because it is the number the grammar hides.

I call that number the valid-but-wrong rate: the share of outputs that pass the grammar and fail the checker. It is the honest measure of a structured-output system, and it is invisible to anyone who only measures schema validity, which is why teams that adopt constrained decoding often report their error rate going to zero while their users keep finding wrong answers. The errors did not go away. They moved below the line, where the grammar could not see them.

The citation that needed a string match

The case where I met the wall in practice was grounded citations. A helpdesk assistant built on retrieval is expected to quote its sources, and the natural schema has an answer field and a list of citation objects, each with a source identifier and a quoted span. The grammar guarantees that every citation has both fields and that the identifier matches the pattern. It cannot guarantee that the quoted span appears in the retrieved passage, because that is the copy language with the passage as the first half, and it cannot guarantee that the identifier refers to a passage that was actually retrieved for this query, because that is membership in a runtime set. Both had to be checked outside the decoder: a string match of each span against its passage, exact or with whitespace normalised, and a lookup of each identifier against the retrieval results. Citations that failed either check were dropped, and an answer whose citations were all dropped was regenerated.

That checker was a few dozen lines and it was the component that made the citations trustworthy. The grammar made them well-formed. The distinction is the whole post: a well-formed citation to a passage that does not contain the quote is worse than no citation, because it carries the appearance of grounding without the fact of it.

The rule

Write the constraints down and sort them by the line. Everything above it goes in the grammar, where it is enforced per token at negligible cost. Everything below it goes in a checker that runs on the finished output, and the checker's rejection rate is reported next to the schema validity rate, because the second number without the first is a claim that the copy language is context-free, and it is not. The theorem that bounds what a parser can recognise bounds what a mask can enforce. Valid is necessary. The checker is what makes it sufficient.