Semantic Parsing and Meaning Representations › Constrained Generation

A semantic parser can use an autoregressive language model. Such a parser generates a logical form, SQL query, or program one token at a time. The problem is that a language model can generate invalid output. It can produce unbalanced parentheses, a SQL query that references a nonexistent column, or a logical formula with a type error.

Constrained generation can prevent violations of the constraints it actually encodes and soundly enforces at each decoding step. These can include grammatical, schema, and type constraints. The decoder can preserve prefixes that have grammatical completions. A valid completed output also requires an accepted stopping state; a length-truncated prefix is not a successful parse.

Let $x$ be the input utterance and $y = y_1, y_2, \ldots, y_T$ be the output representation. For a completed variable-length output, let the final token $y_T$ be the end-of-sequence marker, EOS. An autoregressive model factorizes its probability as:

$$p(y \mid x) = \prod_{t=1}^{T} p(y_t \mid y_{<t}, x)$$

The input $x$ is the utterance, $y_t$ is the output token at step $t$, $y_{<t}$ is the preceding token sequence, and $T$ includes EOS. Without the EOS event, the product describes a prefix probability rather than the probability of stopping there.

At step $t$, the model produces a logit vector $z_t \in \mathbb{R}^{|\mathcal{V}|}$ over the vocabulary $\mathcal{V}$. A grammar-constrained decoder computes a set of allowed tokens:

$$\mathcal{A}(y_{<t}) \subseteq \mathcal{V}$$

and masks the logits:

$$z'_t(i) = \begin{cases} z_t(i) & \text{if } i \in \mathcal{A}(y_{<t}) \\ -\infty & \text{otherwise} \end{cases}$$

Then it samples or takes the argmax from $\text{softmax}(z'_t)$. To preserve viability, $\mathcal{A}(y_{<t})$ must contain only tokens whose decoded continuation admits some grammatical completion, and the current prefix must already be viable. The allowed set must be nonempty; if all logits are masked, softmax has no normalized distribution and the decoder must report failure. EOS is allowed only after a complete accepted string. These conditions preserve completable prefixes; they do not force termination. For example, a decoder for strings of the form $a^n b$ can keep choosing $a$ indefinitely. A finite output cap must reject such an incomplete result.

The $-\infty$ entries make the probability of disallowed tokens zero after the softmax. The allowed set can depend on the prefix, because different prefixes can have different possible continuations. In a grammar requiring balanced parentheses, an opening parenthesis creates a later closing obligation, and the decoder must track that obligation.

For a context-free grammar $G = (N, \Sigma, R, S)$, $N$ is the set of nonterminals, $\Sigma$ the terminal alphabet, $R$ the production rules, and $S$ the start symbol, as in the earlier grammar chapter. Let $L(G)$ denote the language of complete terminal strings generated by $G$. A prefix $p$ is viable if there exists some suffix $s$ such that $p s \in L(G)$. An incremental parser can compute the allowed next tokens. Possible choices include Earley, LR, and GLR parsing, depending on the grammar and implementation. The parser tracks the set of grammar states consistent with the prefix. The allowed tokens must extend a consistent state toward a productive completion. Merely finding a locally expected terminal is insufficient if its grammar branch can never reach a complete string.

An Earley parser is particularly convenient because it can handle left recursion and ambiguity, and it can report the set of expected terminals at any point. Deterministic LR parsers are often efficient for LR grammars, while Earley and GLR support broader grammar classes. Practical speed depends on the grammar, preprocessing, and implementation. The choice depends on the target language and the latency budget.

This is more subtle than it sounds. A tokenizer may split a grammar terminal into multiple subword tokens, or merge several terminals into one token. The constrained decoder must align the model vocabulary with the grammar. Some systems operate over characters or bytes to avoid this problem. Others precompute a token-level grammar or use a parser that understands subword boundaries. The tokenization issues from Byte Pair Encoding do not disappear when the output is formal.

In practice, the alignment problem is a major source of engineering complexity, and it is easy to get subtly wrong. A decoder that is correct on paper can fail when a keyword is split into two tokens.

Syntax is only the first layer. A SQL query can be syntactically valid and still reference a table that does not exist. A logical formula can be well formed and still have a type error. A program can compile and still be semantically wrong.

Semantic constraints add another layer of masking or checking:

• Schema validity: tables and columns must exist, aliases must be defined, and join conditions must satisfy the application's type and schema policies. SQL joins do not universally require declared foreign keys.
• Type checking: predicates must receive arguments of the right type, and operators must follow the target language's signatures and allowed conversions. Date comparisons need compatible temporal representations.
• Scope and binding: closed sentence outputs have no free variables. Open queries may retain declared answer variables or variables supplied by the evaluation context; unintended free variables are rejected.
• Aggregation rules: HAVING filters aggregate groups, including the single implicit group of an aggregate query without GROUP BY. Aggregate expressions obey the target dialect's rules, including restrictions on their use in WHERE.
• Value grounding: map question mentions to the intended database literals, accounting for case, formatting, and synonyms when needed. A literal absent from the stored rows can still be valid SQL and can correctly produce an empty result.
• Execution checks: for tasks requiring a successful result, reject runtime failures and check the returned result against task-specific expectations.

Execution can supply feedback during text-to-SQL generation or repair. In execution-guided decoding, executing partial candidates can prune faulty continuations. An iterative self-debugging loop can use execution results or error messages to revise a generated candidate.

A schema checker can be thought of as a semantic grammar. It defines which identifiers are in scope and which types are compatible, and the decoder can mask tokens that would violate those constraints.

But execution feedback is not a guarantee of correctness. A query can execute successfully and return the wrong answer. A query can return the right answer for the wrong reason. A repair loop can also overfit to a particular database instance. The system needs semantic checks, not just execution checks.

A system can combine several layers:

• A decoder that enforces its specified grammar on complete accepted outputs.
• A sound schema, scope, and type checker that accepts only candidates satisfying its specified rules.
• An executor that catches runtime errors.
• A result check that applies task-specific plausibility tests.

Constrained generation is powerful, but it is not free.

• Correctness versus coverage: A sound decoder that enforces a grammar and stops in an accepted state guarantees membership in that grammar. Membership does not guarantee the intended answer. If the grammar is too restrictive, it may eliminate the correct answer. If it is too permissive, it may not help.
• Latency: Incremental parsing and masking require work during decoding. Their effect on end-to-end latency depends on implementation, overlap, caching, grammar, and output length, so measure the complete decoder.
• Engineering cost: Grammars, parsers, and schema checkers must be written and maintained. SQL dialects and schema changes can break them.
• Tokenizer mismatch: The model vocabulary and the grammar terminals may not align. This requires careful engineering.
• Over-constraining reasoning: Prompt and output-format choices can change the generated intermediate reasoning steps. Evaluate their effect on the actual task; a system may allow intermediate reasoning and constrain only the final structured artifact.

The practical lesson is to use constraints where they add value:

• Constrain the final output format.
• Validate against the schema.
• Execute when possible.
• Do not assume that syntactic validity is semantic correctness.

It is also worth measuring the cost of constraints. A grammar that reduces invalid outputs by half but doubles latency may not be worth it for an interactive application. The right tradeoff depends on the latency budget, the error tolerance, and the cost of a wrong answer.