WorksComputer Science
AGDecode: Semantic Attribute Grammar Derivatives for Safety-Constrained Decoding of Large Language Models
Abstract
Large language models (LLMs) are increasingly used for code generation, motivating techniques that guarantee the structural and semantic correctness of generated programs. Constrained decoding enforces correctness during generation by restricting token choices to those that admit at least one valid completion. While existing approaches can enforce syntactic constraints and selected semantic properties such as type safety, they either target specific properties or rely on operational pruning mechanisms that are difficult to generalize to data-dependent, inductive program properties. We present AGDecode, a programmable framework for semantic constrained decoding based on least-fixed-point semantics. AGDecode extends attribute grammars to partially constructed syntax trees, and reduces semantic constrained decoding to a realizability problem over such trees. The framework compiles semantic specifications into systems of relational constraints that are discharged by external verification oracles, such as SMT and CHC solvers, cleanly separating language semantics from constraint-solving machinery. We prove that our approach is sound and complete relative to an ideal verification oracle. In practice, solvers inevitably encounter uncertain queries; conservatively, our system can reject tokens for soundness or speculatively continue to generate until later queries resolve the entire generation. We mechanize the core metatheory in Rocq and evaluate the framework on semantic-constrained generation of C programs, enforcing path-sensitive safety properties including null-pointer safety, division-by-zero freedom, and initialized-variable usage. Our results demonstrate that solver-backed semantic constrained decoding can enforce rich semantic guarantees while incurring modest computational overhead at regular program boundaries.
Introduction
Recent advances in large language models (LLMs) have significantly expanded their applications in structured domains, most notably automated program generation. However, LLMs provide no native guarantees that their generated text conforms to structural or semantic invariants.
To mitigate this limitation, constrained decoding has emerged as a powerful paradigm for enforcing safety properties during generation [5, 25, 28] (Poeta et al. 2022). Constrained decoding ensures that the final output is correct-by-construction by restricting the decoder’s token selection to continuations that admit at least one completion satisfying a given specification. While syntactic enforcement via context-free grammars is well-explored [14, 21, 26], syntax alone is insufficient for guaranteeing deeper properties. Semantic constrained decoding addresses this gap by enforcing static properties such as type safety and variable scoping [19, 20].
Early attempts to enforce semantic constraints have largely relied on ad-hoc or single-property encodings. Most notably, Mündler et al. [ [19] introduce a decoder tailored explicitly for type safety1
Authors’ Contact Information: Rajan Maghera, University of Toronto, Department of Computer Science, Toronto, Canada, [email protected]; Asher Tempest Arya, University of Toronto, Department of Computer Science, Toronto, Canada, [email protected]; Aren A. Babikian, McGill University, Department of Electrical and Computer Engineering, Montreal, Canada, [email protected]; Marsha Chechik, University of Toronto, Department of Computer Science, Toronto, Canada, [email protected]; Maryam Mehri Dehnavi, University of Toronto, Department of Computer Science, Toronto, Canada, [email protected]. by evaluating type-checking logic over a program’s incremental string representation. However, monolithic approaches tied to a single semantic property scale poorly to generalized constraints. Evaluating semantic properties directly on a generated prefix requires the decoder to look ahead and reason about every permissible decoder token continuation.
Motivating example. Consider the task of enforcing selected undefined-behaviour (UB) safety properties on a C program while an LLM generates the program. Consider an incomplete generation:
void foo(int num) { int *x = malloc(sizeof(int)); *x = 16 / num;
This incomplete generation contains two potential UB violations, highlighted in red, that cannot be rectified by generating more of the program. The first UB violation is a null-pointer dereference if , and the second is a divide-by-zero violation if . Semantic constrained decoding must therefore permit the dereference of and the use of as a divisor only when the required non-nullness and non-zero facts can be established.
Programmable semantic constrained decoding frameworks. To provide a generalized solution to semantic constrained decoding, Nagy et al. [ [20] introduce ChopChop, the first programmable framework for semantic constrained decoding. ChopChop addresses the problem of expressivity and programmability of constrained decoders by allowing for a programmable set of semantics. The space of all possible abstract syntax tree (AST) continuations for a given prefix is represented compactly as regular codata, reducing constraint enforcement to a realizability problem solved via coinduction. A user specifies a language grammar and a system of corecursive semantic pruner functions to eliminate invalid ASTs from the program space. While highly expressive, managing program spaces via coinductive coterms and operational pruners introduces fundamental challenges for general program verification:
Representational overhead in non-regular domains. Courcelle’s theorems [Courcelle [12] show that coterms are highly effective for capturing infinite control-flow behaviours or behavioural bisimulations. However, they are ill-suited for modelling data theories, such as bit-precise arithmetic or path conditions. Forcing these complex data states into a structural tree requires a large number of unique symbols, resulting in a state-space explosion.
Coupling of semantics and search. Because ChopChop’s pruners are formulated as operational, total functions over a trace space, they simultaneously define the language’s semantics and the execution oracle. Consequently, these pruners operate as algorithmic black boxes, preventing the underlying framework from performing global logical optimizations.
Many safety properties are inductive. For example, assertion reachability and memory safety are defined over the set of reachable program states, a least fixed point capturing the variable-value tracking required in the motivating example. Traditional program verification uses this structure by reducing a program to a set of relational verification conditions (VCs) and discharging them to efficient Satisfiability Modulo Theories (SMT) and Constrained Horn Clause (CHC) solvers [7, 13]. Proving safety then reduces to a reachability query over that least fixed point, which is the kind of query these solvers are designed to decide. ChopChop instead represents the space of completions as coinductive coterms, whose semantics is a greatest fixed point. This fits inductive properties poorly. A data-dependent inductive invariant has no compact coterm representation, because distinguishing states by their bit-precise values requires a separate structural symbol for each valuation and causes a state-space explosion.
In this paper, we ask:
How can we design a programmable framework that leverages inductive least-fixed-point semantics to integrate automated verification oracles into constrained decoding?
Our approach. To overcome these limitations, we formalize constraint evaluation using Attribute Grammars (AGs) [15]. While traditional AGs evaluate semantic equations over complete syntax trees, constrained decoding demands reasoning over an incomplete token prefix spanning an infinite space of possible completions. Our framework, AGDecode, addresses this challenge via a relational AG formulation that introduces placeholder holes at ungenerated syntax nodes. Rather than executing an operational traversal over a partial tree, AGDecode translates the structural grammar rules into a uniform system of relational constraints and defers the semantic realizability query to an external oracle (e.g., SMT solver) capable of solving recursive rules efficiently. This architecture cleanly decouples the language’s semantic specification from its checking machinery. We prove that our framework is sound and complete with respect to ideal evaluation. In practice, oracles may emit uncertain results. Thus, we show in evaluation that speculatively-generated decoder tokens can be verified in retrospect to ensure soundness.
This paper makes the following contributions:
a novel programmable framework for semantic constrained decoding based on least-fixed-point semantics (§ 3);
a formalization for residual attribute grammars used to represent partially-constructed syntax trees (§ 4);
a formal connection tying semantic constrained decoding to generating the partially-constructed syntax trees (§ 5);
an embedding to compile residual attribute grammar semantics into systems of CHCs. (Sec. 6); and
an evaluation of our framework showcasing the generation of semantically verified programs while incurring small computational overhead (§ 7).
A mechanization of the core meta-theorems of the framework in the Rocq proof assistant is provided as supplementary material2.
Background
Semantic Constrained Decoding
Constrained decoding is implemented by a monitor, a procedure that tracks the decoder tokens generated so far and determines which decoder tokens are permitted to follow [1, 20]. A monitor maintains a state summarizing the generated prefix and exposes an acceptance predicate that, for a candidate next decoder token, reports whether appending it keeps at least one valid completion reachable. At each decoding step the monitor is queried across the vocabulary and the model’s next-token distribution is masked to the accepted set. Consuming a decoder token then advances the monitor’s state. The parsing with derivatives approach handles the partial parse tree formed by a continuous token stream [8, 18]. The derivative of a formal language with respect to a terminal symbol is defined as the set of all strings such that the concatenated string is in [8]. Formally: . In other words, the derivative is the set of strings that are valid continuations of the prefix . In derivative parsing, taking the derivative of a grammar with respect to a character effectively advances the parser’s state. Rather than rebuilding a parse tree from scratch for every new character, the parse tree is modified using a specialized grammar synthesized from the derivative operator. This grammar describes all valid parse trees that can follow the consumed prefix.
Parsing Derivatives for Constrained Decoding. Derivative parsing can be applied to constrained decoding by treating the character stream as successive derivatives of a parse tree. In the case that the derivative would leave the language empty, the last consumed character is invalid. Derivative parsing realizes a syntactic monitor. Its state is the active grammar, and taking the derivative with respect to a character advances that state. A decoder token is accepted when the resulting derivative is nonempty: . The predicate holds exactly when some string in continues the consumed prefix through . A syntactic monitor constrains the shape of the output and nothing further. Semantic constrained decoding keeps this interface and strengthens the acceptance predicate, admitting a token only when a completion exists that also satisfies a semantic specification.
Attribute Grammars
AGs can be used to connect the syntax of a program and its semantic properties. Originally introduced in Knuth [ [15], AGs extend context-free grammars (CFGs) by associating declarative attributes with grammar symbols, such as the type of an expression or the set of variables in scope at a node, and providing semantic rules to compute these values over the parse tree [3]. In this section, we introduce the core mechanics of attribute grammars through a working example.
Synthesized attributes
Consider a minimal language consisting of literal values (integers, floats, strings) and a binary sum operation. A pure CFG dictates the shape of valid expression trees, but it cannot express the context-sensitive constraint that addition is only well-defined for compatible types, nor can it dictate how those types promote. We define the syntax of our example expression language as follows: . To enforce typing rules, we decorate the non-terminal with a synthesized attribute, , which represents the type of the evaluated expression (). Because the type of a parent node in our language depends exclusively on the attributes of its immediate children, this is an instance of an S-attributed grammar [3]. In an S-attributed system, all attributes are synthesized, meaning they can be evaluated strictly bottom-up via a post-order traversal of the parse tree.
We model the type determination by attaching semantic rules to each production. For the base cases (the literals), the type attribute is instantiated directly from the lexemes:
For the recursive addition production, the semantic rule computes the resulting promoted type. In our case, integers get promoted to floats, and strings are not supported at all (i.e., no concatenation). We introduce a partial promotion function, , which maps two operand types to a resulting type.
where the promotion relation is explicitly defined as:
You may expect that the premise for SUM includes a proposition that the type is valid (i.e., ). Indeed, omitting attribute definitions on invalid branches does not constrain invalid behaviour. Since attribute rules must be completely specified for every production, all paths upward must explicitly define how an attribute is transferred, even if it means propagating an explicit Invalid when a promotion is disallowed. Attributes are evaluated with the syntax where is a tree, is the index of the tree and is the attribute. Figure 1 visualizes this flow of information through a parse tree when evaluating for the expression "oops".

Figure 1. Visualization of S-attributed evaluation over the parse tree for "oops". The structural parse tree is connected via solid lines, while the dashed outer edges trace the bottom-up synthesis of type attributes (). At the root node, the evaluation relies on a partial promote function which maps to , explicitly violating the grammar’s semantic constraints and rejecting the program space.
Inherited attributes
While S-attributed grammars elegantly model bottom-up data flow, they lack the capacity to push contextual requirements downward into the tree. To illustrate this limitation, we extend our language to include variable declarations with explicit type annotations:
Consider the base case for the literal. The type of a constant is defined statically by the syntax, but the type of a variable depends on its definition, which is fetched from the symbol table, an attribute that belongs to parent nodes.
To resolve this, contextual information must be passed from the parent nodes down to their children. The inherited attribute, , contains the symbol table and is dictated by the surrounding context. By pairing the synthesized actual type () with the inherited symbol table (), our model transitions into an L-attributed grammar, a specific type of attribute grammar allowing information to flow not only down and up the parse tree, but also from left-to-right for siblings [3].3 The top-level declaration rule is formalized through the injection of the symbol table into the expression’s inherited attribute. This symbol table is used to perform symbol lookups.
where the lookup relation is explicitly defined as
Rules to synthesize type names to their given types are analogous to the constant cases.
The symbol table must be queried and updated when a variable is defined only if the variable hasn’t been defined before. The attribute grammar gives us control over how attributes are passed and in which direction. In this case, the symbol table is passed down through . This rule updates the symbol table, so the new symbol table must be passed up as a synthesized attribute:
where the symbol table update is explicitly defined as
Previous semantic rules must be updated to pass the newly inherited expression down. Because the symbol table is never updated through an expression, the synthesis of a new symbol table is not required.
Finally, statements are chained via the production. Here, the symbol table attribute is passed between siblings from left to right, making this an inherited attribute. The synthesized symbol table from is passed as an inherited attribute to , and then the final symbol table is passed up.
Overview
We introduce Residual Attribute Grammars (RAGs) and their semantic derivatives, lifting attribute evaluation to the incomplete parse trees produced during live LLM generation. Our approach maps incomplete derivations to structured constraint formulas to ensure semantically invalid partial trees are disallowed. In this section, we introduce the core mechanics of RAG and their semantic derivatives using a concrete expression language.
Residual Relational Constraint System
Traditional attribute grammars assume an evaluation context over fully concrete, static syntax trees. When an evaluator encounters an incomplete or partial tree containing unexpanded regions, such as unknown future LLM generations, top-down and bottom-up attribute flows stall, as they are unable to reason about infinite completion spaces.
| Production | Semantic Equation | Relational Rule |
| <br> | <br> | |
| <br> | <br> | |
| <br><br> | <br><br> |
Table 2. Production mapping of several attribute grammar equations. An index of the production maps to local positional terms under a unified sorted signature.
We lift the partial syntax tree into a many-sorted residual relational constraint system4. Syntactic structures and transfer functions are compiled into algebraic terms. Unexpanded structural non-terminals are represented as typed placeholder variables, or holes. Instead of evaluating attributes functionally, we compile local semantic equations of the instantiated productions into a set of baseline term rules.
Consider the following tree with a non-terminal hole of sort :
Our realizability goal is to determine if at least one concrete tree derived from the incomplete tree exists such that (i.e., that the root symbol table is not invalid). Given our incomplete expression , the framework generates a tight residual relational constraint system representing the semantic properties of the given parse tree, which is then used to store and evaluate its attributes. To begin, the framework maps an attribute grammar’s semantic rules to our residual system. Fig. 2 provides the direct mapping from standard semantic rules to their corresponding many-sorted residual relational rewrite system representations. Positions along a syntax tree traversal are tracked as integers , with referring to the starting production.
Traversing and applying the relational rules per production reveals a compiled residual relational constraint system at the index for the top-level production given the prefix :
At position 1.3, the tree recurses into the production, where the unexpanded hole is captured by a placeholder (Figure 3a). The recursive production’s system is denoted as . Attributes whose evaluation paths depend on an unexpanded structural hole are deferred to the residual system. Figure 4a illustrates this: the inherited symbol table is threaded downward into the update node, while the synthesized and , both dependent on the hole , remain symbolic. Given a complete attribute tree, the relational constraint system could be simplified to contain only a final .
!Partial parse trees for str foo = [e] bbox=0.09,0.11,0.91,0.30
Figure 3. Partial parse trees for str foo = [e]: (a) the unexpanded structural hole of sort ; (b, c) its two production choices after the derivative consumes the lexeme "bar", selected by the structural choice variable .

Figure 4. Semantic attribute evaluation over Figure 3: inherited attributes () flowing downward (orange), synthesized attributes (, , , ) upward (blue).
The syntax tree with structural holes represents an infinite number of concrete trees as may expand into any production of . To align with the paradigm of constrained decoding, which restricts a decoder to continuations admitting at least one valid completion, we evaluate these structural holes by asking if there exists at least one concrete tree such that the top-level predicate is met. Consequently, the problem of identifying a valid concrete tree reduces entirely to discovering a single satisfiable computation path within the relational constraint system.
A non-terminal grammar symbol, such as , can realize to one of many production rules. To distinguish between productions on the same non-terminal symbol, our frameworks assigns a set of guarded relational rules whose non-determinism is carried by a structural choice variable . In the case of and the corresponding hole , there are 5 distinct choices, each guarded by via the guard operator :
In these relational rules, the holes are indexed by a placeholder prefix representing a relational position instead of an absolute position prefix. The relational indices allow us to (1) reuse hole definitions regardless of where they exist on a tree, and (2) represent recursive rules.
Solving with oracles. Solving for these relational rules is done through an abstract oracle (e.g., SMT solver). The oracle receives the relational constraint system, and evaluates the predicate. If a valid path exists such that the predicate is met, the relational constraint system, and the tree and prefix it was compiled from, are valid. AGDecode is sound and complete relative to an ideal oracle, however, because solvers may return unknown on complex inductive queries, the implementation must decide how to handle uncertainty. With practical solvers, conservative handling of unknown yields sound but incomplete pruning; our prototype also supports a speculative mode that admits timed-out tokens and later revalidates longer prefixes, trading immediate soundness for progress.
Symbolic Refinement and Rule Transformations
As generation progresses, structural holes are expanded into explicit grammar productions through a state transition relation termed refinement. Refinement is used to systematically narrow holes to represent smaller, more specific tree spaces and continuously transform the residual relational constraint system to represent their semantics. Standard CFG derivatives, extended from Brzozowski [8], can be applied to yield the set of valid string suffixes given a prefix [18]. We lift this process to partial syntax trees.
The process of consuming characters is mapped to the process of refining holes. Suppose we have the tree and the lexeme "bar" is generated. In this case, the system determines that the structural hole is refined into , which is any production of where the leftmost characters are "bar". While some productions of are constant, such as (Figure 3b), the addition production (Figure 3c) could recurse infinitely through . Standard CFG derivative processes rely on thunk-ing and fixed-point algorithms to represent and reason about these recursive properties. [18] In AGDecode, infinite recursion is represented by structural hole placeholders and evaluated through an oracle. During refinement, the relational constraint system undergoes an explicit rule transformation. These rules match the required structural rules for the given replacement as governed by the attribute grammar. Figure 5 demonstrates this expansion. The evaluation oracle then processes . The

Figure 5. Transformation of the residual relational constraint system during a structural refinement step at position . The only valid semantic production is .
structural expansion introduces a deterministic type mismatch; the result of promote will never be String, as our semantics disallow string addition. Thus, the top-level query, which expects an expression of the type String, is unsatisfiable by the oracle, as is the case with the productions for the integer, floating-point, and lookup productions () demonstrated in Figure 4b. However, the string literal production () is semantically valid, allowing the new prefix to be accepted. The semantic validity problem is both existentially and universally quantified, in that we want to prove that there exists at least one valid semantic path (i.e., selections of ) such that no semantic errors can occur.
Partial Lexemes
Evaluating semantic rules over an incomplete lexeme (e.g., a half-typed variable identifier) introduces an infinite search space, as the prefix could theoretically resolve to an infinite number of distinct lexemes. To ensure decidability and monotonic convergence, our framework introduces a strict division between partial lexemes and concrete realized lexemes. We replace unknown lexical synthesized attributes with two distinct structural forms: (1) Lexical Holes (): An over-approximation of the constraint space for an incomplete prefix string , or (2) Solid Terminal Nodes (): The exact, localized constraint compiled once a token boundary is reached and the lexeme is frozen. The grammar enforces a soundness constraint requiring the abstract prefix to logically subsume all possible future concrete completions, expressed as the refinement chain .
Generalizing Semantics as Constrained Horn Clauses
For simple, finite constraint domains, it is entirely feasible to implement bespoke fixed-point solvers or custom abstract interpreters to resolve the relational summaries. However, our design gives us the ability to lift summaries from domain-specific transfers of information into general first- and higher-order logic. We achieve this by lowering the recursive relational summaries of our attribute grammar into CHCs.
A CHC is a fragment of first-order logic [7] taking the form of an implication:
where is a formula in a background theory (e.g., linear integer arithmetic, uninterpreted functions), are uninterpreted relational predicates representing our sub-trees, and is the head predicate. In this CHC-backed formulation, the abstract transfers are expressed as relations. We define an uninterpreted predicate for each non-terminal. For instance, our earlier sum promotion rule translates naturally into a Horn clause, joining the evaluation of its children with the logic of the promote relation:
By utilizing SMT background theories like the Theory of Arrays, Bitvectors, or Datatypes, this architecture can be extended to enforce highly complex semantic properties on the fly.
Declarative Semantics of Incomplete Residual Attribute Grammars
In this section, we formalize a declarative framework for reasoning about semantic attribute constraints over incomplete syntax structures. We begin by augmenting classical attribute grammars with a typed term algebra. (§ 4.1). We introduce partial syntax trees to account for incomplete trees and embed their corresponding semantic configurations into static systems of residual relational constraints (§ 4.2). We provide a global compilation function mapping partial tree geometry. directly to these constraint equations (§ 4.3). Finally, we prove that evaluating satisfiability over these partial constraint spaces is strictly sound and monotonic with respect to traditional evaluation over complete ground trees (§ 4.4). Crucially, this declarative formulation replaces dynamic operational tree-refining with static logical judgments, allowing an automated reasoning oracle to prune semantically invalid search spaces early.
Residual Attribute Grammars
Formally, a CFG is a 4-tuple , where is the finite set of non-terminals, is the set of terminals disjoint from , is the set of productions, and is the start symbol. Let denote the complete vocabulary. We assume a lower-level physical alphabet (e.g., ASCII characters) and a lexical mapping function associating each terminal with a regular language of characters.
An AG [3, 15] is a 4-tuple where is the underlying CFG, associates each symbol with a finite set of attributes , maps each attribute to a domain , and associates each production with a finite set of semantic equations . The set partitions into disjoint subsets: synthesized attributes and inherited attributes . By convention, , and . .
A production takes the form . The set defines the computation of specific attributes within the local context of .
To reason about semantic constraints symbolically, we augment standard AGs with a typed term algebra in place of opaque computable functions, creating a Residual Attribute Grammar (RAG).
Definition 4.1 (Residual Attribute Grammar). A RAG is a 6-tuple , where:
, , mirror the standard AG definitions.
is a many-sorted signature of computation symbols. Each function possesses a strictly defined type , where .
is the expanded algebraic signature including alongside unary attribute projection symbols. For every and , contains a symbol .
maps each production to a finite set of attribute evaluation rules .
Let be a set of typed variables where each has sort . The set computes attributes using the many-sorted term algebra . Each evaluation rule in takes the syntactic form , where:
the target term is uniquely defined by exactly one rule in ,
the target attribute is either a synthesized attribute of the left-hand side () or an inherited attribute of a right-hand side symbol ($1 \leq i \leq n \land a \in I(X_i)$),
is a well-typed term evaluating to the target domain.
The set of all complete syntax trees in RAG is the set of well-defined terms in the term algebra . We address tree nodes uniquely via positions . The root is denoted by the empty sequence , and denotes the -th child of the node at . Let denote the subtree of at position . Attributes on a complete tree are evaluated in a traditional manner.
Definition 4.2 (Semantic Evaluation of a Complete Tree). The evaluation of an attribute at a position on a complete syntax tree , defined as the operation is sound and complete. The codomain of evaluation is strictly .
The definition notably encapsulates some functional definition that correspond to each signature and assumes all are soundly and completely evaluated. This axiom is set up to later ensure that abstract evaluation over incomplete trees are sound and complete. We define the semantic validity of a tree as the evaluated result of some synthesized boolean attribute .
Partial Syntax Trees and Residual Constraint Systems
To represent unexpanded productions and unrealized lexemes, we introduce a family of vocabulary holes as placeholder symbols. For any symbol in our complete vocabulary , the term represents an uninstantiated non-terminal or an unexpanded terminal hole of sort . These are used in both syntactic and semantic representations of a tree.
Syntax: Partial Derivation Trees
Definition 4.3 (Partial Derivation Tree). A Partial Derivation Tree is a well-typed term in the extended term algebra . A tree is complete if it contains no holes (i.e., it is a ground term ). Substitution denotes the replacement of the subtree at position (which must be ) with the term .
To formally ground structural refinement, we define the homomorphic extension of a base substitution by structural induction:
Definition 4.4 (Refinement and Concretization of Partial Derivation Tree). Let . Tree refines , denoted , iff there exists a well-typed substitution such that . The concretization function maps a partial derivation tree to the infinite set of complete, ground trees that refine it:
Semantics: Residual Relational Constraint Systems
To represent the accompanying semantics of incomplete trees, we lift local semantic equations into a unified Residual Relational Constraint System.
Definition 4.5 (Residual Relational Constraint System). A Residual Relational Constraint System is a finite set of sorted term relational constraint rules tracking open relational constraints over attribute paths. Let be the set of all semantic attributes. We define an Attribute Target as a projection coordinate pair , where and is a semantic attribute of . Each attribute has a designated semantic sort/domain . Formally, a well-sorted residual relational constraint system is a relation: where all rules satisfy the invariants that:
the left-hand side is a bare attribute projection path: where and ,
the right-hand side term must ground to the same semantic sort as its target attribute domain: .
The relational constraint system isolates the semantic constraints of unexpanded holes, deferring their evaluation until structural concretization. It acts as a relational semantic interface bounded to the partial syntax tree. The holes in the relational constraint systems represent uninterpreted relational interfaces to all concrete evaluations over a traditional attribute grammar. Just with the syntactical trees, the ruleset can be extended to those without holes through refinement and concretization.
We define the homomorphic rule extension of a well-sorted rule substitution by structural induction over the right-hand side terms of the system. Let be an attribute target:
Definition 4.6 (Refinement and Concretization of Residual Relational Constraint Trees). Let be two residual relational constraint systems. semantically refines , denoted , if and only if there exists a well-sorted rule substitution such that the normalized homomorphic transformation matches exactly:
A residual relational constraint system is complete or ground if and only if it contains no relational placeholder hole terms (i.e., its active set of unresolved placeholders is empty, ). The rule concretization function maps a partial relational constraint system to the bounded set of all complete, ground relational constraint systems that refine it:
A relational constraint system may contain recursive and non-deterministic rules. Thus, we defer the proof of existence to an abstract evaluation oracle . In implementation, this bounds the required behavior without mandating a specific fixed-point mechanism.
Axiom 1 (Abstract Oracle Soundness). Let be a residual relational constraint system. The evaluation oracle is a procedure yielding a judgment in the abstract domain . We denote this evaluation as . The oracle must be strictly sound with respect to the concretization space such that proving a violation (unsat) guarantees no valid concretizations exist:
Definition 4.7 (Ideal Oracle). An oracle is considered ideal if it is complete and never yields unknown. For an ideal oracle, evaluation yields sat if and only if there exists at least one valid concretization:
Compiling Structure to Semantic Constraints
We map the production rules and partial derivation trees to residual relational constraint systems. Then, we prove that the above holds through a state transition system. We begin with individual production mapping functions.
Definition 4.8 (Attribute Grammar Production Mapping). Let be a production rule in the grammar. The attribute grammar populates with functional equations for attributes defining parent synthesis or child inheritance at position . Let be variables representing the production indices. The production mapping function is defined to convert local structural equations into absolute positional constraint rules with their sorts mapping to the attribute grammar domain:
Instantiating at address path generates rules through the coordinate mapping transformation .
Using our individual production mapping function, we define a global compilation function that works over any partial tree.
Definition 4.9 (Global Compilation Function). Let be a partial derivation tree. The global compilation function maps an arbitrary partial derivation tree rooted at coordinate position to its complete residual relational constraint system through structural induction:
Base case. If is an open hole of sort , compile to rules with a relational placeholder representing an unexpanded future boundary.
Inductive case. If is a concrete structural node via production and contains fresh holes representing subtrees .
Core Equivalence and Soundness Meta-Theorems
We now formally prove that our system is equivalent to a traditional evaluator.
Lemma 4.10. The global compilation function distributes homomorphically over structural refinement. For any partial syntax tree and valid substitution :
Theorem 4.11 (Equivalence of Declarative and Traditional Evaluation). Let be a complete, ground syntax tree. The satisfiability of its compiled constraint system under the structural choice variables is strictly equivalent to traditional functional attribute evaluation.
Lemma 4.12 (Monotonicity of Partial Constraints). For any partial syntax tree and any concrete tree that refines it, the compiled constraints of safely over-approximate the semantics of . If the partial constraint system is unsatisfiable, all concretizations are unsatisfiable:
Semantic Constrained Decoding via Language Derivatives
In this section, we lift context-free language derivatives to track the character-by-character construction of lexemes (§ 5.1). We define an inductive relational derivative operator over sequences of structural holes, modeling the progressive consumption of a string prefix (§ 5.2). We conclude by demonstrating that our character-level derivative framework converges monotonically and guarantees both the soundness and completeness of real-time semantic pruning (§ 5.3).
Lexical Hole Semantics and Character Derivatives
During constrained decoding, lexical tokens are not yielded atomically; they are constructed character by character. To evaluate semantic constraints speculatively over an in-progress token, we specialize the representation of terminal holes.
Definition 5.1 (Lexical Holes). Let be the lexical alphabet. During left-to-right decoding, terminal nodes are constructed incrementally. Let be a terminal category. Let denote the set of all prefixes in . We define a Lexical Hole as a stateful placeholder where is the target terminal category and is the accumulated character prefix. A lexical
hole is mathematically well-formed if and only if is a valid prefix of the token’s language: . When the accumulated prefix fully satisfies the lexical definition (), the hole may be concretized into a solid terminal node .
An open lexical hole speculatively accumulates characters as characters are consumed from left-to-right. Consumption terminates upon reaching a designated token boundary. If the completely generated lexeme string legally satisfies the definition of the terminal category (denoted ), the lexical hole may be transitioned to a concrete node. We denote this finalized structural state using a solid terminal node representing the space of a single string . Syntactically, the filled-in placeholder directly equates to a standard singular leaf node within a concrete syntax tree:
The refinement of lexical holes is defined until the upper limit of some concrete lexical token:
Semantic Derivatives of Partial Trees
With the partial tree algebra and abstract lexical contexts defined, we now formally bridge the mechanics of predictive left-to-right parsing with our constraint framework. In standard formal language theory, the Brzozowski derivative yields the set of valid string suffixes given a prefix Brzozowski [8]. This was later extended to Context-Free Languages through caching and fixed point solving Might et al. [18]. Our residual attribute grammar system was designed specifically with the caching mechanism in mind to offload context-free ambiguity onto relational fixed points.
First, we define a structural nullability operator over a placeholder sequence. We denote this using the subscript . This operator checks if a sequence of holes can derive the empty string.
Definition 5.2 (Structural Nullability Operator). Let be a sequence of grammar symbols. The nullability operator statically evaluates whether the sequence can vanish into the empty string :
For a single non-terminal hole , iff there exists a production such that .
We define the derivative operator over a sequence hole , representing the set of valid remaining symbol sequences after the prefix sequence consumes the character .
Definition 5.3 (Derivative of a Sequence Hole). Let be the next consumed character. The derivative of an active lexical hole followed by a remaining syntactic sequence is defined as:
For a single non-terminal hole , the derivative is the union of the derivatives of its productions :
We introduce a control variable for every coordinate in the tree. This variable strictly binds the oracle to a single production choice for all attributes at that node. We introduce the guard operator [condition] Rule, meaning the relational rule is only active if the condition is satisfied.
Definition 5.4 (Guarded Residual Compilation of Derivatives). Let be a non-terminal hole of sort that has consumed prefix . Let be the productions of , where each . We define a domain constraint for the position , dictating that the structural choice variable must map to exactly one valid production index:
The global compilation function for the derivative hole maps to a set of guarded attribute equations:
Definition 5.5 (Global Path Consistency). Let be the set of all structural choice variables introduced in a derivative compilation . The system must generate a global structural well-formedness constraint ensuring that if a parent node at coordinate selects production , then the choice variables for any children are only active if .
The oracle’s evaluation of the residual relational constraint system is strictly conjoined with to prevent the solver from satisfying semantic constraints via topologically disjoint derivations.
Meta-Theorems
Theorem 5.6 (Soundness of Relational Derivative). Let be a generated prefix, and be the next consumed character. Let map to the flat string of a concrete tree . If the constraint system produced by the derivative operator over the new prefix is unsatisfiable, then no complete tree extending exists in the semantic language:
Theorem 5.7 (Completeness of Real-Time Convergence). For any ground truth syntax tree that validly satisfies the top-level specification (), the declarative derivative system remains continuously satisfiable for every step of its yielded character sequence. For any prefix :
Symbolic Encoding and Relational Invariant Synthesis
In this section, we bridge our abstract declarative semantics with an executable verification backend by compiling constraint lattices into first-order logical formulas. We begin by translating our residual relational constraint systems into CHC clauses evaluated over a decidable background theory (§ 6.1). We then detail the inductive compilation of structural rules, flattening tree coordinates and semantic attributes into strict relational predicates (§ 6.2). Finally, we introduce logical cyclic aliasing to soundly memoize infinite derivative unrolling. Ultimately, this encoding reduces the continuous semantic validation of partial generated prefixes to a standard reachability query in an SMT solver. (§ 6.3)
Constrained Horn Clauses and Background Theories
To operationalize the abstract evaluation oracle , we map our residual relational constraint systems CHCs over a first-order background theory .
Definition 6.1 (Compilation to CHCs). Let be a set of uninterpreted relation symbols representing our semantic domains, structural choices , and partial tree attributes. A CHC is a closed first-order logic formula of the form , where is a constraint formulated strictly within the decidable background theory (e.g., linear integer arithmetic, bitvectors, or algebraic datatypes), are uninterpreted relational queries defining the body, and the head is either a relational assertion in or the contradiction symbol .
We map the residual relational constraint system’s elements into flat relational predicates by turning positional coordinates and semantic attributes into predicate arguments. Let be a non-terminal symbol whose associated attribute set is partitioned into inherited attributes and synthesized attributes . We map to a distinct uninterpreted relation . The signature of this predicate is defined by sorting the tree position alongside the semantic domains of its attributes:
where denotes the domain of tree addresses. The core insight of this translation is that positional addresses are treated as explicit symbols or sequence variables within the solver’s background theory, rather than opaque memory references. This formulation allows the CHC engine to track the grammar’s tree topology purely relationally.
Inductive Rule Compilation
Compiling rules to CHCs is a relatively straightforward process which is split into terminal and non-terminal rules.
Terminal nodes , where , acts as our lexical axioms. Its synthesized attributes are statically computable constants derived directly from the lexeme string and the node emits a base fact. For a tree position , this lexical constraint maps directly to the following categorical axiom:
For non-terminal expansions, the structural relational constraint rules in translate into inductive Horn clauses that bind parent relations to the validity of their children which is strictly guarded by the structural choice variable .
Definition 6.2 (Non-Terminal Compilation). Let be a binary production rule. The declarative validity of the parent predicate at coordinate locally depends on the relational satisfiability of both child predicates, the solver’s structural assignment of production index , and the conjunction of the local semantic attribute equations.
Here, represents the background theory constraint over the defunctionalized attribute vectors, mechanically extracted from the original attribute grammar equations . The relational compilation also naturally encodes any valid CFG topology, including left-recursive grammars.
Derivative Memoization
Taking the semantic derivative of recursive rules leads to infinite structural unrolling. In operational parsing, derivative-based frameworks mitigate this by memoizing or "caching" derivative states, compacting the infinite derivation tree into a finite cyclic graph. We map this cyclic topology directly into the CHC system.
Definition 6.3 (Cached Derivative States). Let represent a derivative state at current coordinate that has been structurally identified as identical to a previously encountered ancestor state at coordinate .
The global compilation function halts expansion and emits a relational alias. The current placeholder and the cached ancestor both evaluate the same semantic non-terminal over the same accumulated prefix , so they belong to the same uninterpreted relation . The compilation of the cached symbol simply binds the validity of the current position to the validity of the ancestor position across all semantic attributes :
We inject an explicit logical cycle into the constraint system, so the "cached" constraints are directly and actively managed during string compilation.
Lemma 6.4 (Soundness of Relational Memoization). The injection of the cyclic logical alias safely approximates the infinite derivative unrolling without introducing spurious least-fixed-point models in the background theory .
Queries and Meta-Theorems
Semantic validation is framed as a reachability problem that balance existential and universal quantification. Specifically, we must prove that there exists at least one semantically valid program completion (an existential search over the structural choices, ) such that for all evaluation steps along that path, no semantic errors occur (a universal safety guarantee). CHC rules are emitted by selecting specific structural completions governed by the parameters. For a specific choice path , we encode the top-level semantic specification (the requirement that the synthesized validity attribute at the root evaluates to true, ) as the primary goal clause of the CHC system. This query is formally expressed as a clause attempting to deduce a valid state from an invalid root state:
If the solver determines the system is satisfiable, proving that False is statically unreachable for at least one path of , it guarantees that a valid structural completion of the prefix exists where no emitted CHC constraint evaluates to an invalid state. Consequently, the prefix remains semantically viable. Conversely, if the solver computes that False is reachable for all possible assignments, it demonstrates that no valid structural completion exists. The current prefix deterministically violates the grammar’s attribute constraints, and the decoding engine soundly and immediately prunes this lexical path from the search space.
Unknown SAT result. In the CHC pipeline, the solver may return sat, unsat, or unknown/timeout. The framework is only sound and complete relative to the underlying oracle, so in order to accommodate this, there are one of three execution modes: (1) Ideal oracle mode: sound and complete relative to a complete oracle. (2) Conservative mode: unknown/timeout reject; sound but incomplete. (3) Speculative mode: unknown/timeout accept; progress-oriented, later revalidated, not immediately sound.
We conclude this section by formally grounding the translation from our declarative relational systems to the background logic.
Theorem 6.5 (CHC Translation Soundness). Let be an accumulated token prefix, and let denote the flat set of Constrained Horn Clauses generated by the translation of the partial tree.
logic system possesses a valid least-fixed-point model over the background theory if and only if the declarative derivative system is satisfiable.
Evaluation
In this evaluation, we answer the following research questions:
RQ1) Does AGDecode effectively constrain large language model outputs against safety semantics?
RQ2) What is the computational cost of solving SMT constraints during generation?
Case Study: Safety Constraints for C
In this case study, we use AGDecode to enforce specific safety properties when generating C programs. Many previous type-safety works focus on TypeScript since it is a mainstream language susceptible to type errors in LLM generation [19]. Conversely, small to mid-sized LMs tasked with generating C code [22] are shown to include many semantic safety errors specific to the language, motivating our choice to pick C.
To evaluate the expressivity of AGDecode, we examine a suite of C safety properties governed by path-sensitive data theories. These include the UBs: (1) null pointer dereferences, (2) division-by-zero, and (3) uninitialized variable accesses. Consider the program snippet below which demonstrates all three of these erroneous conditions.
void func(int a) {
int *x, *y, *z; y = malloc(sizeof(int)); z = malloc(sizeof(int)); a = 0;
if (y == NULL || a < 1) return; *x = *z; *y = 10 / a;
}
To prove that this program is free of the specified undefined behaviors, a framework must track values and path conditions. In this scenario, the assignment to the uninitialized pointer *x, the dereference to *z and the division by the variable a should not be allowed.
Mapping grammar rules. For this case study, we map a large subset of C grammar to our framework, including memory logic (pointers, derefs, array subscripting). We focus on checking the properties defined above, thus we do not include a memory model. The semantic rules are modelled using standard verification rules. For example, a division expression maps from attribute grammars to a CHC as the following:
Experimental Setup
In this section, we detail the experimental methodology designed to evaluate the efficacy of AGDecode.
Implementation. The implementation for AGDecode is written in Python. Our framework generates CHCs based on (1) a given input specification in a relational style, and (2) a generated prefix. Relational SMT constraints are compiled using a thunked graph representation in the networkx library. Constraints are then outputted into the SMT-LIB v2 format and solved using the Z3 Spacer [13] (Komuravelli et al. 2014) engine, which is highly optimized for infinite CHCs.
Benchmark and Tasks. We evaluate AGDecode against the HumanEval C++ subset of the MultiPL-E dataset [9] containing 161 LLM code generation problems and corresponding
C++ function declarations. To the best of our knowledge, no widespread LLM evaluation benchmark exists for C because the language lacks the standardized containers that test harnesses rely on to validate outputs. To accommodate, we mapped the C++ functions to equivalent C functions. For example:
C++ original : long sum_squares(std::vector<long> lst)
C test case : long sum_squares(long* lst, unsigned lst_size)
We limited the set of test cases to 77 that focus on memory and pointer accesses and ignored those with floating point types. Our prompt had basic instructions to ensure the output used the C grammar we support and that the output was memory-safe. We also added the instruction that all pointer arguments should be checked before being accessed.
Model, Parameters, Hardware. Test cases are generated against the CodeLLaMA-13B [24] model across 3 temperatures (0.3, 0.5, 0.7). Our experiments are run on a AMD EPYC 9654 (Zen 4) 2.4 GHz CPU with 1 Nvidia H100 SXM for LLM generation.
Procedure. For each test case, we generate a semantic-constrained LLM output while collecting the time required to verify each generation and the number of tries required per decoder token. The experiments will run in speculative mode, so unknown or timeout queries are treated as successful verification. Speculative mode allows for decoder tokens to continue generating under the assumption that a future fast query would validate or invalidate the entire generated prefix. For each SMT query, we imposed a timeout of 5 seconds.
Results
RQ1: Effectiveness
Examining the output shows that the conditions are able to be monitored by our elements, even across multiple paths. Figure 6 demonstrates the prefix of an output that was verified. We verified by removing the first line assert(arr), which would cause the final decoder token emitted [ to fail generating. Some scenarios tend to be harder than others to rectify safety concerns when generated at the decoder-token level, and this is largely dependent on the grammar of the language. For example, we saw that memory access using array subscripting arr[0] could easily revert to arr and produce a simple check like arr == NULL. However, pointer dereferencing *arr in almost all cases lead to doomed generations as reverting to * would require some dereferenceable variable to be generated after the fact.
bool move_one_ball(long* arr, unsigned arr_size) {
assert(arr);
bool swapped = false;
int pos = 0;
long temp;
while (!swapped && (pos < arr_size - 1)) {
swapped = false;
for (int j = 0; j < arr_size - 1 - pos ; ++j) {
if (arr[Figure 6. LLM excerpt output of the HumanEval_109_move_one_ball test case (temp=0.7) constrained in the semantic framework. Removing the assert(arr) line causes the monitor to disallow the final decoder token [.
RQ2: Overhead
Table 1 showcases the median per-decoder-token Z3 solving latency overhead across all three temperatures. About one-fourth (21.7%-25.4%) of queries reached the 5-second timeout. Of the remaining queries, the invalid queries were notably quick (0.532s Q3 at most, median 0.001s-0.002s), while valid queries had a larger range (0.235s Q1 at least to 2.564s Q3 at most). Surprisingly, the CHC queries were not as costly as expected. Spacer is well-optimized for infinite spaces, and performed especially well when proving invalid invariants of tokens.
| Query Result | \multicolumn{4}{c}{CodeLlama-13B ()} | \multicolumn{4}{c}{CodeLlama-13B ()} | \multicolumn{4}{c}{CodeLlama-13B ()} | ||||||||||||
| % | Q1 (s) | Med (s) | Q3 (s) | % | Q1 (s) | Med (s) | Q3 (s) | % | Q1 (s) | Med (s) | Q3 (s) | ||||
| Invalid | 1,803 | 46.1% | 0.001 | 0.001 | 0.153 | 1,580 | 43.9% | 0.001 | 0.002 | 0.532 | 1,668 | 38.9% | 0.001 | 0.001 | 0.133 |
| Valid | 1,196 | 30.6% | 1.169 | 1.806 | 2.564 | 1,108 | 30.8% | 1.419 | 1.950 | 2.479 | 1,692 | 39.4% | 0.235 | 1.124 | 2.137 |
| Timeout | 912 | 23.3% | — | 5.000 | — | 914 | 25.4% | — | 5.000 | — | 931 | 21.7% | — | 5.000 | — |
| Total Checks | 3,911 | 100.0% | — | — | — | 3,602 | 100.0% | — | — | — | 4,291 | 100.0% | — | — | — |
Table 1. Latency distributions across valid and invalid generations.
Observation: Patterns of Verification Latency on Regular Boundaries. The realizability times per token varied wildly, and this typically came down to the structure of what was being queried, not the total length of the program. Figure 7 showcases the query latency as generation progresses for one example, where every valid and timeout decoder token was accepted, increasing the prefix length being verified by successive queries. The timeout decoder tokens were speculatively accepted because a successive verification would verify the entire prefix. The red background indicates the time in which decoder-token generations are speculatively generated before being verified by a future query. This effect on query time is best demonstrated with an example. Consider the generation:

Figure 7. Iterative verification latency during constrained decoding for the HumanEval_122_add_elements example (temp=0.5). Valid and invalid represent cases when the entire prefix till generation was verified per query. Timeout represents a query that did not complete within 5 seconds, allowing an unverified token to generate. The red background represents the uncertain period between unverified and verified generations.
where the first line is LLM output and the second and third lines are the corresponding internal constraint system states at the block level and statement list level. The partially generated array index operator creates the placeholder an exploration for every possible expression that begins lexically with (e.g., , , ) to index the array. This explosion of uniquely generated scenarios is challenging for naive solver and constraint encodings without efficient invariants, which we observed causing the majority of timeouts. By the time that the full statement is realized, the hole is refined to a concrete expression , which amounts to a simple CHC without recursive rules. Additionally, commonly used rules such as are cached by an SMT solver. Scenarios like this highlight that verification time is not universally fast or slow as generation continues (i.e., a longer program is not necessarily slower to verify), but instead the effort depends on the possible valid program constructs. For this reason, while verification at the character or decoder-token level might not be feasible in every scenario, verification at statement boundaries can be.
Beyond constrained decoding, some modern LLM generation techniques allow multiple decoder tokens to be generated and backtracked if the complete generated code contains errors [17]. Thus, an efficient and effective application of AGDecode consists of allowing tokens to be generated when verification queries time out, then backtracking if a later query invalidates previously allowed decoder tokens. If at any point, ambiguous decoder tokens were allowed and the later program verified, then no backtracking is required.
Limitations
While our approach provides strong theoretical guarantees, it is bounded by the provided grammar and specifications. Manually defining comprehensive constraints is complex and highly susceptible to human error. Consequently, our evaluation was restricted to our chosen subset of C and representational ability, which notably omits a full memory model for solving time, and thus cannot enforce robust memory safety across unconstrained C programs. Furthermore, our limitation was severely limited by a lack of a backtracking implementation; in the cases where speculative token generation was later invalidated, any one of the tokens in-between could have been the cause of error, thus a valid implementation would have to consider which one to replace.
Verifying semantic constraints at runtime relies heavily on the underlying solver, which introduces issues of solver incompleteness. Because resolving deep relational queries can be computationally intractable which we remedy with a strict timeout policy. When a query times out, the system must either conservatively reject potentially valid tokens or accept unverified ones. This computational bottleneck results in severe token-level latency, rendering the approach mostly infeasible at the most fine-grained levels of generation.
Finally, our methodology is subject to the broader, systemic challenges of constrained decoding. Enforcing strict grammatical and semantic boundaries inherently distorts the language model’s calibrated probability distribution. By masking out otherwise likely decoder tokens to satisfy the solver’s constraints, the approach risks compromising the natural coherence and generative quality of the LLM output [2].
Contrasting With A Coinductive Approach
ChopChop’s coterm approach characterizes verification as the systematic pruning of non-well-founded program spaces. While this paradigm is elegant for specifying corecursive behaviours (e.g., liveness properties) and trace bisimulations, mapping inductive state-reachability properties (e.g., low-level, bit-precise C semantics) onto structural coterms introduces prohibitive representational overhead. Coinduction relies on finding a greatest fixed point over a finite set of regular behaviours. For example, a coinductive tree attempting to model a loop would have to generate a completely unique structural state for every iteration, resulting in an infinite alphabet of symbols.
In essence, a coinductive pruner must simultaneously serve as both the operational semantic definition and the verification oracle. Because the pruner is formulated as a total function operating over a program space, complex spaces may need to be over- or under-approximated and any algorithmic decisions to do so must be explicitly baked into the pruner’s structural traversal logic. In contrast, AGDecode yields two primary structural advantages:
(1) Global optimization context. Rather than evaluating a lazy, step-by-step pruning function over an unfolded program space, our translation emits a system of relational constraints. This global view allows highly optimized SMT solving engines to exploit full contextual reasoning, leveraging techniques like conflict-driven clause learning and inductive generalization over the entire program state simultaneously.
(2) Decoupled approximation mechanics. Upon reaching a complex space, the choice to over- or under-approximate the valid program space is isolated to the oracle and not hard-coded into the front-end semantics.
Ultimately, our approach chooses incompleteness in the inductive invariant synthesis space to exploit highly optimized, automated data-theory reasoning. The coinductive approach makes the opposite trade-off: it secures completeness in behavioural structural properties at the expense of automated data-theory scalability.
Additionally, we do not provide a direct empirical comparison against ChopChop on the path-sensitive safety properties of our C case study. These properties are defined over reachable states distinguished by bit-precise values, and as argued above such states have no compact coterm representation. Expressing them in ChopChop’s coinductive setting requires a distinct structural symbol for each valuation, so the state space grows too large to make evaluation on this benchmark practical.
Related work
Constrained Decoding enforces structural, syntactic, or semantic constraints at generation time by masking invalid tokens given some rules [20, 21].
Syntactic constrained decoding. The most straightforward constrained decoding methods act at the structural and syntactic levels [5, 14, 20, 21, 25, 28]. These approaches typically consume a valid grammar and build a parser that advances as tokens are consumed. At each step, the valid

Figure 8. Comparison of constraint encodings for path-sensitive semantic decoding. Left: Coinductive approaches attempt to embed specific data environments (e.g., variable states) directly into the structural tree, breaking regularity and triggering an unbounded expansion of states. Right: AGDecode decouples the data domain from the structure using relational attributes, passing complex inductive VCs directly to an off-the-shelf SMT oracle.
next tokens are found through a search of possible constructions in the grammar given a prefix. Syntactic constrained decoding, however, does not constrain on requirements that involve context, complex rules, meaning, or any other semantic constraints. AGDecode goes beyond the syntactic guarantees these methods provide.
Semantic constrained decoding, such as type-level constrained decoding or correctness guarantees, are much more complex and time consuming [1, 19, 20, 23]. Although both semantic and syntactic constrained decoding methods constrain the possible set of next tokens based on some prefix, semantic approaches go much further. Instead of maintaining a basic parse state, semantic approaches check whether a prefix can complete into a program satisfying some property. Mündler et al. [ [19] introduce type-constrained decoding. Their approach addresses the challenge of well-typed coding. This approach maintains a partial abstract syntax tree annotated with type-relevant context, and soundly ensures that all continuations adhere to this context. Although this approach soundly ensures well-typedness, they are limited to a single semantic property. More generally, Nagy et al. [ [20] open semantic constrained decoding to manual constraining. This approach lifts the analysis to a concise representation of all possible abstract trees, and, given a manually-written tree traverser, prunes these trees to find the set of valid continuations. Constraints must thus be encoded as the pruners themselves, strongly coupling the checking and the semantics, and introducing significant representation overhead. AGDecode completely separates these two by delegating the checking to external solvers, such as off-the-shelf SMT solvers, and allows for constraints to be written clearly and concisely in first order logic.
Formal Verification approaches provide correctness guarantees by combining LLM output with machine-checkable proofs or symbolic analysis [4, 6, 11]. Unlike constrained decoding, formal verification approaches typically act post-hoc, requiring complete output, and often require generation iterations with verifier feedback. Instead, we apply formal methods on partial generations to enforce constraint satisfaction during the token generation process.
Repair methods focus on post-hoc fixes through error analysis. This can be execution-based analysis, such as by evaluating execution traces and unit test outputs [10]. A parallel line of work is Automated Program Repair (APR), where LLMs iteratively repair and explore the repair space [29, 30]. Repair methods act post-hoc on already-generated code, whereas AGDecode prevents semantically invalid output from being generated in the first place.
Search. Search-based methods improve correctness by generating multiple candidate programs and selecting or combining the best, rather than constraining or repairing a single output [17, 27, 30]. Search-based methods improve correctness by sampling and selecting among multiple outputs, but do not enforce semantic validity during generation as our pruning approach does.
Conclusion
We present AGDecode, a programmable framework for semantic constrained decoding based on realizability over partially constructed syntax trees. By compiling semantic specifications into relational constraints solved by SMT and CHC backends, AGDecode supports rich inductive program properties while cleanly separating language semantics from verification machinery. We prove that AGDecode is sound and complete relative to an ideal verification oracle. Our experimental evaluation demonstrates that it can effectively enforce path-sensitive safety properties during C program generation. The results demonstrate feasibility but also show that token-level verification has significant tail latency; this motivates batching and speculative validation.
Future Work. We plan to explore the integration of the SMT oracle to actively guide an LLM’s next token choice in order to increase constrained decoding output. Additionally, we plan to explore the integration of backtracking to guide refined iterative generation of sections of LLM outputs.
References
- [1]Lakshya A Agrawal, Aditya Kanade, Navin Goyal, Shuvendu K. Lahiri, and Sriram K. Rajamani. 2023. Monitor-guided decoding of code LMs with static analysis of repository context. In Proceedings of the 37th International Conference on Neural Information Processing Systems (NIPS ’23). Curran Associates Inc., Red Hook, NY, USA, 32270–32298.DOI
- [2]Kareem Ahmed, Kai-Wei Chang, and Guy Van den Broeck. 2025. Controllable Generation via Locally Constrained Resampling. In International Conference on Learning Representations, Y. Yue, A. Garg, N. Peng, F. Sha, and R. (Eds.), Vol. 2025. OpenReview.net, Singapore, 87328–87343. https://proceedings.iclr.cc/paper_files/paper/2025/file/d98ce7a82af78cd02968e97ae3fe8e-Paper-Conference.pdf
- [3]Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. 2006. Compilers: Principles, Techniques, and Tools (2nd Edition). Addison-Wesley Longman Publishing Co., Inc., USA.
- [4]Divyam Anshumaan, Tej Chajed, Varun Chandrasekaran, Alvin Cheung, Sarthak Choudhary, Adwait Godbole, Somesh Jha, Nils Palumbo, Elizabeth Polgreen, Sanjit A. Seshia, and Tianyang Zhou. 2025. LLM-Based Code Translation Needs Formal Compositional Reasoning. Technical Report UCB/EECS-2025-174. EECS Department, University of California, Berkeley, CA, USA. https://eecs.berkeley.edu/?id=wGi8LU2EOF. Position paper.
- [5]Luca Beurer-Kellner, Marc Fischer, and Martin Vechev. 2024. Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation. doi:10.48550/arXiv.2403.06988 arXiv:2403.06988 [cs].DOI
- [6]Sahil Bhatia, Jie Qiu, Niranjan Hasabis, Sanjit A. Seshia, and Alvin Cheung. 2024. Verified Code Transpilation with LLMs. doi:10.48550/arXiv.2406.03003 arXiv:2406.03003 [cs].arxiv.org/abs/2406.03003
- [7]Nikolaj Bjørner, Arie Gurfinkel, Ken McMillan, and Andrey Rybalchenko. 2015. Horn Clause Solvers for Program Verification. In Fields of Logic and Computation II, Lev D. Beklemishev, Andreas Blass, Nachum Dershowitz, Bernd Finkbeiner, and Wolfram Schulte (Eds.). Lecture Notes in Computer Science, Vol. 9300. Springer International Publishing, Cham, 24–51. doi:10.1007/978-3-319-23534-9_2
- [8]Janusz A. Brzozowski. 1964. Derivatives of Regular Expressions. J. ACM 11, 4 (1964), 481–494. doi:10.1145/321239.321249DOI
- [9]Federico Cassano, John Gouar, Daniel Nguyen, Sydney Nguyen, Luna Phipps-Costin, Donald Pinckney, Ming-Ho Yee, Yangtian Zi, Carolyn Jane Anderson, Molly Q. Feldman, Arjun Guha, Michael Greenberg, and Abhinav Jangda. 2023. MultiPL-E: A Scalable and Polyglot Approach to Benchmarking Neural Code Generation. IEEE Transactions on Software Engineering 49, 7 (July 2023), 3675–3691. doi:10.1109/TSE.2023.3267446DOI
- [10]Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. 2023. Teaching Large Language Models to Self-Debug. doi:10.48550/arXiv.2304.05128 arXiv:2304.05128 [cs].DOI
- [11]Aaron Councilman, David J iahao Fu, Aryan Gupta, Chengxiao Wang, David Grove, Yu-Xiong Wang, and Vikram Adve. 2025. Towards Formal Verification of LLM-Generated Code from Natural Language Prompts. doi:10.48550/arXiv.2507.13290 arXiv:2507.13290 [cs].DOI
- [12]Bruno Courcelle. 1983. Fundamental Properties of Infinite Trees. Theoretical Computer Science 25, 2 (1983), 95–169. doi:10.1016/0304-3975(83)90059-2DOI
- [13]Leonardo de Moura and Nikolaj Bjørner. 2008. Z3: An Efficient SMT Solver. In Tools and Algorithms for the Construction and Analysis of Systems, C. R. Ramakrishnan and Jakob Rehof (Eds.). Springer, Berlin, Heidelberg, 337–340. doi:10.1007/978-3-540-78800-3_24DOI
- [14]Saibo Geng, Martin Josifoski, Maxime Peyrard, and Robert West. 2023. Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing (EMNLP). Association for Computational Linguistics, Singapore, 10932–10952. doi:10.18653/v1/2023.emnlp-main.674DOI
- [15]Donald E. Knuth. 1968. Semantics of context-free languages. Mathematical systems theory 2, 2 (June 1968), 127–145. doi:10.1007/BF01692511DOI
- [17]Qingyao Li, Wei Xia, Xinyu Dai, Kounianhua Du, Weiwen Liu, Yasheng Wang, Ruiming Tang, Yong Yu, and Weinan Zhang. 2025. RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code Generation. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, Christos Christodoulopoulos, Tanmoy Chakraborty, Carolyn Rose, and Violet Peng (Eds.). Association for Computational Linguistics, Suzhou, China, 8092–8110. doi:10.18653/v1/2025.emnlp-main.410DOI
- [18]Matthew Might, David Darais, and Daniel Spiewak. 2011. Parsing with Derivatives: A Functional Pearl. In Proceedings of the 16th ACM SIGPLAN International Conference on Functional Programming (ICFP ’11). ACM, New York, NY, USA, 189–195. doi:10.1145/2034773.2034801DOI
- [19]Niels Mündler, Jingxuan He, Hao Wang, Koushik Sen, Dawn Song, and Martin Vechev. 2025. Type-Constrained Code Generation with Language Models. Proc. ACM Program. Lang. 9, PLDI (June 2025), 171:601–171:626. doi:10.1145/3729274
- [20]Shaan Nagy, Timothy Zhou, Nadia Polikarpova, and Loris D’Antoni. 2025. ChopChop: a Programmable Framework for Semantically Constraining the Output of Language Models. doi:10.48550/arXiv.2509.00360 arXiv:2509.00360 [cs].arxiv.org/abs/2509.00360
- [21]Kanghee Park, Jiayu Wang, Taylor Berg-Kirkpatrick, Nadia Polikarpova, and Loris D’Antoni. 2024. Grammar-Aligned Decoding. In Advances in Neural Information Processing Systems 37 (NeurIPS 2024). Curran Associates, Inc., Red Hook, NY, USA. https://proceedings.neurips.cc/paper_files/paper/2024/hash/2bdcc2267d7d01523e2e17aca07a54f3-Abstract-Conference.htmlarxiv.org/abs/2405.21047
- [22]Hammond Pearce, Ba Leeh Ahmad, Benjamin Tan, Brendan Dolan-Gavitt, and Ramesh Karri. 2022. Asleep at the Keyboard? Assessing the Security of GitHub Copilot’s Code Contributions. In 2022 IEEE Symposium on Security and Privacy (SP). IEEE, San Francisco, CA, USA, 754–768. doi:10.1109/SP46214.2022.9833571DOI
- [23]Gabriel Poesia, Oleksandr Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. 2022. Syn-chromesh: Reliable code generation from pre-trained language models. doi:10.48550/arXiv.2201.11227 arXiv:2201.11227 [cs].DOI
- [24]Baptiste Rozière, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Romain Sauvestre, Tal Remez, Jérémy Rapin, Artyom Kozhevnikov, Ivan Evtimov, Joanna Bitton, Manish Bhatt, Cristian Canton Ferrer, Aaron Grattafiori, Wenhan Xiong, Alexandre Défossez, Jade Copet, Faisal Azhar, Hugo Touvron, Louis Martin, Nicolas Usunier, Thomas Scialom, and Gabriel Synnaeve. 2024. Code Llama: Open Foundation Models for Code. arXiv:2308.12950 [cs.CL] https://arxiv.org/abs/2308.12950
- [25]Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. 2021. PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing (EMNLP). Association for Computational Linguistics, Online and Punta Cana, Dominican Republic, 9895–9901. doi:10.18653/v1/2021.emnlp-main.779DOI
- [26]Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gangadeep Singh. 2024. SynCode: LLM Generation with Grammar Augmentation. doi:10.48550/arXiv.2403.01632 arXiv:2403.01632 [cs].DOI
- [27]Shuai Wang, Liang Ding, Li Shen, Yong Luo, Zheng He, Wei Yu, and Dacheng Tao. 2024. USCID: Improving Code Generation of LLMs by Uncertainty-Aware Selective Contrastive Decoding. doi:10.48550/arXiv.2409.05923 arXiv:2409.05923 [cs].
- [28]Brandon T. Willard and Rémi Louf. 2023. Efficient Guided Generation for Large Language Models. doi:10.48550/arXiv.2307.09702 arXiv:2307.09702 [cs].DOI
- [29]Chunqiu Steven Xia and Lingming Zhang. 2022. Less training, more repairing please: revisiting automated program repair via zero-shot learning. In Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/PSE 2022). Association for Computing Machinery, New York, NY, USA, 959–971. doi:10.1145/3540250.3549101
- [30]Tianyi Zhang, Tao Yu, Tatsunori B. Hashimoto, Mike Lewis, Wen-tau Yih, Daniel Fried, and Sida I. Wang. 2022. Coder Reviewer Reranking for Code Generation. doi:10.48550/arXiv.2211.16490 arXiv:2211.16490 [cs].