Source-linked AI summary
The Alignment Problem in Constrained Code Generation
Matteo Biagiola, Jahrim Gabriele Cesario, Luca Di Grazia, George Zakhour, Guido Salvaneschi
TL;DR
The paper studies whether constrained decoding reliably improves code generation when the constrainer, language model, and target language are aligned. It evaluates alignment and mitigation strategies across models, languages, constrainers, and benchmarks, finding that incomplete constraints can make constrained decoding substantially worse than unconstrained decoding. The results support designing complete constrainers or finetuning models to match constraints.
Problem
Constrained decoding is intended to prevent code errors, but prior work gives limited attention to alignment among the constrainer, language model, and target language.
Method
The paper empirically studies alignment, incompleteness, and mitigation through experiments spanning seven LLMs, two target languages, two constrainers, and multiple benchmarks.
Results
Incomplete constraints make unconstrained decoding significantly more functionally correct in the evaluated settings, with functional correctness falling by up to 97% relative to complete-constraining baselines.
Takeaways & Limitations
Constrainer completeness and alignment are central design considerations for constrained code generation with formal guarantees.
Takeaways & Limitations
The evaluation uses a limited set of languages, datasets, and models, including TypeScript and TOML and models ranging from 2B to 80B parameters.
Abstract
from arXiv · showhide
Large Language Models (LLMs) have demonstrated strong capabilities in code generation, but their outputs frequently contain syntax or type errors that result in compilation failures. Constrained decoding has been proposed as a solution to mitigate compilation errors by construction, improving functional correctness as a byproduct. However, previous works overlook a critical aspect of constrained decoding: the alignment between constrainer (e.g., types), language model and the target specification language (e.g., TypeScript). Misalignment is caused by the constrainer being incomplete--rejecting programs that belong to the target--or unsound--allowing programs that are not part of the target. The bias created by incompleteness distorts the language model distribution, and can be detrimental for code generation. We evaluate this hypothesis using seven language models, two target languages, two constrainers, enforcing types and syntax during decoding, and we study how language models react to varying levels of incompleteness. On three benchmarks, when the constrainer is incomplete, unconstrained decoding significantly outperforms constrained decoding in terms of functional correctness. Incompleteness pushes the model into low-probability regions of the program space, causing the generation to frequently time out, and reducing functional correctness by up to 97%. These contributions make the community aware of the negative effects of misalignment in constrained decoding, and provide quantitative insights on how to design constrainers that are beneficial for code generation systems with formal guarantees.
1 Introduction
The paper argues that constrained decoding helps code generation only when the model, target language, and constrainer are aligned. Its experiments show that incomplete constraints can steer models toward unlikely programs, making unconstrained decoding more functionally correct in some settings.
- Significance: Unconstrained decoding significantly outperforms type-constrained decoding in functional correctness across two TypeScript benchmarks, six LLMs, and varied sampling settings.This preliminary result motivates identifying when constrained decoding is effective rather than assuming constraints always improve generation.
- Methodology: Alignment describes the relationship among the model language, target language, and constrained language, and the paper argues that constrained decoding benefits code generation only when these languages align.The proposed framework motivates improving the constrainer or finetuning the model to reduce misalignment.
- The Alignment Problem: Incomplete constrainers can reject valid programs, forcing models into low-probability program regions that cause timeouts, out-of-tokens events, and text degeneration.A TypeScript example shows a valid forward reference rejected after a function signature, illustrating how incompleteness creates this bias.
- Contributions: Finetuning the model on constraint-model data reduces timeouts by 53–73% and out-of-tokens events by 74–94%, narrowing the functional-correctness gap between constrained and unconstrained decoding.The two distributions become equivalent in some cases after alignment through finetuning.
- Contributions: Complete constraints can improve performance by up to 54%, whereas incomplete constraints can reduce functional correctness by up to 97% relative to complete-constraining baselines.These results quantify the importance of constrainer completeness for constrained code generation.
2 Background
The background formalizes programs as languages over strings and language-model generation as token-by-token sampling. It then describes unconstrained and constrained decoding, where incremental parsing and type checking filter candidate continuations during generation.
- 2.1 Token Vocabulary and Language Models: A program language is defined as a subset of strings over a finite character alphabet that satisfy syntactic and semantic rules.The formalization introduces Σ, Σ* and languages L ⊆ Σ* as the basis for reasoning about valid programs.
- 2.1 Token Vocabulary and Language Models: Language models generate token sequences by assigning a conditional distribution to the next token given the preceding prefix, stopping when EOS is emitted.Tokens are finite sequences of alphabet symbols, and decoding samples iteratively from the model distribution.
- Decoding: Unconstrained decoding autoregressively samples tokens from the model using a prompt, temperature, and generation budget until EOS or the budget is reached.Temperature controls sampling randomness, with higher values making less likely tokens more probable to sample.
- Constrained Decoding: Constrained decoding filters token continuations that violate a formal constraint, such as syntactic well-formedness or type correctness.The approach enforces constraints incrementally during generation rather than validating only after completion.
- Constrained Decoding: The type-aware algorithm samples candidate tokens, appends each to the prefix, and retains only prefixes that an incremental parser and type checker deem completable into a valid program.Unconstrained decoding is recovered when these partial checks always return true.
3 Empirical Study
The empirical study compares TypeScript type-constrained and unconstrained decoding across HumanEval and MBPP, using multiple models, temperatures, and repeated runs. Unconstrained decoding generally achieves higher functional correctness, although constrained decoding improves compilation-oriented type-syntax correctness.
- 3 Empirical Study: The study evaluates TypeScript generation on HumanEval and MBPP with six LLMs, three temperatures, repeated runs, and statistical significance and effect-size analyses.
- 3.1.3 Procedure.: Effectiveness is measured by functional correctness, type-syntax correctness, and timeout rate under fixed token or time generation budgets.
- 3.2 Results: Type-constrained decoding generally improves type-syntax correctness, especially for less capable models, but this advantage does not translate into better functional correctness.
- 3.2 Results: Constrained generation loses functional-correctness performance partly because it exceeds token or time budgets, particularly for smaller models and higher temperatures.
- 3.2 Results: Unconstrained decoding consistently achieves the best functional correctness across the evaluated configurations, while type-constrained decoding does not improve functional correctness.
4 The Alignment Problem
The alignment problem concerns how the model, target, and constrained languages overlap during constrained code generation. The paper argues that incompleteness biases generation toward unlikely programs, while soundness and completeness define different routes toward useful alignment.
- 4.1 Model, Target, and Constrained Languages: Prefix-based constraints are required for autoregressive decoding, but complex type systems can prevent a constrainer from being both sound and complete.
- 4.2 Language Misalignment: Alignment links the model language, target language, and constrained language, and the paper frames its improvement as maximizing their shared overlap with the target fixed.
- 4.2 Language Misalignment: The ideal constrainer equals the target language and is simultaneously sound and complete, but such a constrainer often does not exist in practice.
- 4.2 Language Misalignment: When both properties are unrealistic, the paper recommends prioritizing soundness because it preserves constrained-decoding guarantees, while completeness can be supported by aligning the model distribution.
- 4.2 Language Misalignment: An incomplete constrainer rejects valid target programs that the model can generate, forcing decoding toward a reduced feature set and potentially unlikely program regions.
- 4.2 Language Misalignment: An unsound constrainer accepts programs outside the target language, whereas an incomplete constrainer biases generation by excluding target-valid programs.
5 Experimental Evaluation
The evaluation studies how misalignment affects constrained decoding, whether finetuning restores alignment, and how performance changes under complete and deliberately incomplete syntax constraints.
- RQ1: The Cost of Misalignment: RQ1 measures how misalignment between a constrainer and the target language negatively impacts code generation.The study quantifies incompleteness bias as a potential explanation for constrained decoding underperformance.
- RQ2: Restoring Alignment: RQ2 tests whether finetuning the language model to comply with a TypeScript constrainer can recover functional correctness.The intervention targets alignment between the model distribution and the constrainer.
- RQ3: Complete Alignment: RQ3 evaluates complete TOML syntax constraining and progressively removes syntactic or semantic features to quantify sensitivity to incompleteness bias.This design contrasts complete alignment with controlled reductions in constrainer completeness.
- RQ1: The Cost of Misalignment: Table 2 reports the percentage of tasks where constrained decoding has significantly greater, lower, or equivalent average NLL than unconstrained decoding.The comparison is used to characterize decoding bias under RQ1.
5.1 RQ1: The Cost of Misalignment
RQ1 finds that incomplete constraints distort the model’s learned distribution: constrained decoding often yields higher-NLL, low-probability solutions, especially at low temperature, and can reduce functional correctness.
- Results: 35.82% of Gemma-2-2B MBPP instances show significantly higher constrained-decoding NLL at 𝜏=0.1, versus 13.08% at 𝜏=1.0.At 𝜏=1.0, statistically equivalent cases exceed 80% on average, revealing a temperature-dependent bias trade-off.
- Results: Constrained decoding produces higher NLL than unconstrained decoding on Gemma-2-2B HumanEval, particularly for timed-out solutions that are extremely unlikely under the model distribution.Figure 4 illustrates that incomplete constraints can push generation into uncharted, low-probability regions.
- Results: When both strategies produce functionally correct solutions, their NLL distributions are nearly identical, with negligible effect size (Â12 = 0.502).This indicates that the full-dataset bias is largely associated with incomplete constraints forcing a restricted feature set.
- Results: An incremental type checker can block a valid forward reference, forcing a type-safe but functionally incorrect alternative or triggering repeated generation until timeout.The examples show how local constraint enforcement can alter otherwise productive continuations.
- Results: RQ1 concludes that constrainer incompleteness distorts the learned distribution, generates unlikely solutions, and reduces functional correctness.The mechanism links restricted feature support to low-probability generation and degraded outcomes.
5.2 RQ2: Restoring Alignment
RQ2 uses finetuning to align model outputs with the TypeScript constrainer. Alignment improves type-syntax compliance and reduces timeouts, but residual incompleteness bias means constrained decoding still underperforms or only matches unconstrained decoding.
- Procedure: The procedure targets low-alignment instances with GRPO, using a binary reward for passing the incremental type checker and a LoRA adapter to reduce catastrophic forgetting.Hard instances have alignment rates below 10%; selected sets cover roughly 23–25% of benchmark problems across models and datasets.
- Results: After finetuning, constrained and unconstrained functional correctness becomes equivalent for Gemma-2-2B on HumanEval and closer for Qwen2.5-32B.For Qwen2.5-32B, constrained correctness reaches around 77% versus 82% unconstrained; before finetuning, unconstrained decoding leads by 3.7–10 percentage points across models.
- Results: After finetuning, 92% of unconstrained-generated solutions pass the incremental type checker, up from 72%.This increase indicates stronger alignment between the model and the constrainer.
- Results: For Gemma-2-2B and Qwen2.5-32B on MBPP, finetuning raises constrained functional correctness by around 2 and 6 percentage points, respectively, while unconstrained decoding remains significantly better.The unconstrained strategy decreases by around 2 points for Gemma-2-2B and increases by 0.6 points for Qwen2.5-32B.
- Results: Finetuning increases alignment across HumanEval and MBPP, improves type-syntax correctness, and reduces constrained-generation timeouts.The authors report that constrained decoding still underperforms or at best matches unconstrained functional correctness.
5.3 RQ3: Complete Alignment
RQ3 tests syntax constraints in TOML under complete and deliberately incomplete grammars. Complete constraining improves functional correctness, whereas removing even a small syntactic feature can sharply reduce performance.
- Metrics: The complete syntax constrainer prevents grammar violations but does not capture semantic errors such as conflicting keys.Across models, conflicting-key errors remain possible because the grammar does not encode that semantic restriction.
- Procedure: TomlModeEval compares constrained and unconstrained generation across complete and incomplete GGML BNF grammars, using exact match and tree-edit similarity as functional-correctness measures.The benchmark adapts JsonModeEval for TOML generation and evaluates 100 problems with three language models.
- Results: 53% higher exact match and 48% higher similarity are achieved by complete constrained decoding over unconstrained decoding for Gemma-2-2B.Complete constraining also improves Qwen-2.5-32B, while constrained and unconstrained decoding are equivalent for Qwen-3-Coder-Next-80B.
- Results: Removing optional spaces before the equal sign reduces exact match from 48.1% to 28.6% for Gemma-2-2B and by 97% for Qwen-3-Coder-Next-80B.Qwen-2.5-32B remains near 39.7% versus 40.3% unconstrained, although its similarity score still increases.
- Results: Removing comments or dotted keys does not reduce functional correctness relative to complete constrained decoding across the evaluated models.Forbidding all optional spaces is also detrimental, though less than forbidding only spaces before the equal sign.
- Results: RQ3 concludes that constrained decoding outperforms unconstrained decoding under complete alignment, but incompleteness can reduce functional correctness by up to 97%.The results show that models assign behavioral importance to syntactic constructs including optional spacing.
6 Threats to Validity
The evaluation addresses internal validity through uniform experimental conditions and repeated runs with statistical testing, while external validity is limited by the selected languages, datasets, and models.
- The study used uniform hardware and timeout conditions across all strategies, following standard empirical guidelines.
- Ten independent runs per configuration and Wilcoxon signed-rank and Vargha-Delaney Â12 tests addressed LLM nondeterminism.
- The evaluation’s external validity is limited by its use of TypeScript and TOML, selected datasets, and a bounded set of language models.
- The models ranged from 2B to 80B parameters, representing the small-to-medium scale where constrained decoding is most likely to show measurable benefits.
7 Related Work
Prior work constrains generation through grammars, runtime masks, semantic analyses, and type systems, while constrained decoding has also been framed as support for smaller models. The paper adds evidence that misalignment can impose an incompleteness bias, especially for small language models.
- Constrained Decoding using Grammars: Grammar-based methods enforce syntactic validity using context-free grammars, optimized DFA masks, or runtime libraries.
- Complex Constraints: Other frameworks enforce semantic, logical, or type properties through completion engines, static analysis, solver guidance, and TypeScript-aware pruning.
- Small Language Models and Constrained Generation: Prior literature presents constrained decoding as a crutch for smaller models, but the paper finds that misalignment makes small language models suffer most from incompleteness bias.
8 Conclusion
The paper argues that incomplete constraints can harm code generation and analyzes constrained decoding through alignment among the model, constraining rules, and target specification. It validates finetuning the model or completing the constrainer as two ways to improve alignment.
- Incomplete constrainers can be detrimental to code generation, motivating alignment as a lens for analyzing constrained decoding.
- Strict alignment among the language model, constraining rules, and target specification is presented as a prerequisite for successful constrained decoding.
- Finetuning the LLM to the constrainer or making the constrainer complete are empirically validated strategies for improving alignment.