🤖 machine learning

The Alignment Problem in Constrained Code Generation

This paper reveals that misalignment between language models and incomplete constrained decoders can severely degrade code generation performance by distorting probability distributions and causing timeouts, often making unconstrained decoding more effective for functional correctness.

Original authors: Matteo Biagiola, Jahrim Gabriele Cesario, Luca Di Grazia, George Zakhour, Guido Salvaneschi

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Matteo Biagiola, Jahrim Gabriele Cesario, Luca Di Grazia, George Zakhour, Guido Salvaneschi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: The "Over-Protective Parent" Problem

Imagine you are teaching a very talented but slightly chaotic child (the AI Model) how to write a story (the Code).

Usually, you let the child write whatever they want. Sometimes they make spelling mistakes or use the wrong grammar, but they often get the story right. This is Unconstrained Decoding.

To fix the mistakes, you decide to act as a strict editor (the Constrainer). You tell the child: "You can only write words that fit this specific grammar rule. If you try to write a word that breaks the rule, I will stop you immediately and make you pick a different one."

The paper argues that while this sounds like a great idea to prevent errors, it often backfires. If your editing rules are incomplete (meaning you don't know all the rules of the language, or you block valid ways of writing things), you end up forcing the child to write in a weird, unnatural way just to satisfy your limited rules. The result? The story becomes nonsensical, the child gets frustrated and stops writing early, and the final story is worse than if you had just let them write freely in the first place.

The Three Key Players

The paper identifies three things that need to "get along" for this to work:

The Model (The Child): The AI that generates the code. It has learned a vast amount of how code usually looks from its training data.
The Target (The Goal): The perfect, correct code that we actually want (e.g., valid TypeScript).
The Constrainer (The Editor): The tool that tries to force the AI to follow rules (like checking types or syntax) while it is writing.

The Problem: The "Editor" is often incomplete. It doesn't know every valid way to write code. It might block a valid sentence because it hasn't learned a specific feature yet (like "forward references," where you use a word before defining it).

The "Misalignment" Analogy

Think of the AI's brain as a map of a city it knows very well.

The Target is the destination you want to reach.
The Constrainer is a set of roadblocks you put up to ensure the driver stays on the "correct" roads.

If your roadblocks are perfect, the driver stays on the best roads and gets there safely.
But if your roadblocks are incomplete (you blocked a valid shortcut because you didn't know it existed), the driver is forced to take a detour through a swamp (low-probability areas). They might get stuck in the mud (timeout), run out of gas (run out of tokens), or arrive at a place that looks like the destination but isn't actually the right house (syntax is correct, but the code doesn't work).

What the Researchers Found

The team ran experiments using several AI models and two types of code (TypeScript and TOML). Here is what they discovered:

1. The "Strict Editor" Often Makes Things Worse (RQ0)
When they used a standard "incomplete" editor (one that blocks some valid code), the AI performed worse than when it was allowed to write freely.

The Result: The AI generated code that was technically "safe" (no syntax errors) but didn't actually do what was asked.
The Analogy: It's like forcing a chef to only use ingredients from a tiny, incomplete pantry. The chef might make a dish that looks perfect, but it tastes terrible because they were forced to use weird substitutes.

2. The "Bias" (RQ1)
The researchers found that the "incomplete editor" forces the AI to pick words it would normally never pick.

The Result: The AI starts generating "unlikely" code. It's like forcing a jazz musician to only play notes from a specific scale they hate. The music becomes stiff and unnatural.
The Consequence: The AI often gives up entirely (times out) because it can't find a path that satisfies the editor's incomplete rules.

3. Can We Fix It? (RQ2)
They tried to "teach" the AI to understand the editor's limited rules better by fine-tuning it.

The Result: This helped a little. The AI stopped getting stuck as often, and the code became slightly better.
The Catch: It didn't fully fix the problem. The AI was still fighting against the editor's incomplete rules. It's like teaching the child to be a better writer, but they are still forced to write with a broken pen.

4. The "Perfect Editor" (RQ3)
Finally, they tested what happens if the editor is complete (it knows every valid rule and blocks nothing that is actually correct).

The Result: When the editor was perfect, the AI performed much better than when writing freely.
The Analogy: If you give the child a perfect set of rules that covers everything, they can write a masterpiece.
The Surprise: The researchers found that even tiny, missing details in the rules (like forgetting to allow a space before an equals sign) could cause the AI's performance to crash by up to 97%. The AI is incredibly sensitive to these small gaps.

The Bottom Line

The paper concludes that Constrained Decoding (forcing AI to follow rules while writing) is only a good idea if the rules are perfectly aligned with what the AI already knows and what the final code needs to be.

If the rules are incomplete, they act like a bad filter, distorting the AI's natural ability and making the code worse.
To make this work, we either need to make the rules perfectly complete or retrain the AI to perfectly match the imperfect rules.

In short: Don't put a half-baked filter on a powerful engine; it will just break the car.

Technical Summary: The Alignment Problem in Constrained Code Generation

Problem Statement

Large Language Models (LLMs) have demonstrated strong capabilities in code generation but frequently produce outputs with syntax or type errors, leading to compilation failures. In statically typed languages like TypeScript, approximately 94% of compilation errors stem from type system violations rather than syntax errors. To mitigate this, constrained decoding has been proposed as a technique to enforce formal rules (e.g., syntax grammars, type systems) during token generation, theoretically guaranteeing structural validity.

However, the authors observe a counter-intuitive phenomenon: in preliminary studies, unconstrained decoding often outperforms constrained decoding in terms of functional correctness. The paper posits that this failure is not inherent to the concept of constraints but stems from a critical misalignment between three core entities:

The Model Language ( $L_M$ ): The set of programs the LLM is likely to generate based on its training distribution.
The Target Language ( $L_T$ ): The set of valid programs according to the specification (e.g., TypeScript compiler rules).
The Constrained Language ( $L_C$ ): The set of programs permitted by the user-defined constrainer (e.g., an incremental parser/type-checker) during decoding.

The core thesis is that constrained decoding is detrimental when the constrainer is incomplete (rejecting valid programs in $L_T$ ) or unsound (allowing invalid programs). An incomplete constrainer forces the LLM into low-probability regions of the program space, causing "incompleteness bias," text degeneration, and frequent timeouts, ultimately reducing functional correctness.

Methodology

The authors propose a framework of Alignment to analyze the relationship between $L_M$ , $L_T$ , and $L_C$ . They define alignment as the Jaccard similarity among these three sets. The study is structured around three Research Questions (RQs) to investigate the cost of misalignment and potential mitigations:

RQ0 (Effectiveness): A large-scale empirical study comparing constrained vs. unconstrained decoding across six LLMs (ranging from 2B to 80B parameters), two benchmarks (HumanEval and MBPP), and three temperature settings.
RQ1 (The Cost of Misalignment): Quantifying the "incompleteness bias" by measuring the Normalized Negative Log-Likelihood (NLL) of generated programs. The study analyzes how an incomplete constrainer (specifically a TypeScript type-constrainer that lacks support for forward references and user-defined types) distorts the model's distribution.
RQ2 (Restoring Alignment): Evaluating whether fine-tuning the LLM to comply with the specific constraints of the constrainer can mitigate the bias. The authors use Group Relative Policy Optimization (GRPO) with a reward function based on passing the incremental type checker.
RQ3 (Complete Alignment): Systematically testing the impact of completeness using TOML (a language with a strict, context-free grammar) as a sandbox. They compare a complete syntactic constrainer against variants with specific features removed (e.g., optional spaces, comments, dotted keys) to isolate the sensitivity of models to varying degrees of incompleteness.

Key Results

1. Unconstrained Decoding Often Outperforms Constrained Decoding (RQ0)

Across all configurations (HumanEval and MBPP benchmarks), unconstrained decoding consistently achieved higher Functional Correctness (FC) than type-constrained decoding.

Timeouts: Constrained decoding suffered significantly higher timeout rates (exceeding token or time limits), particularly for smaller models and at lower temperatures.
Type-Syntax vs. Functionality: While constrained decoding improved Type-Syntax Correctness (TSC), this did not translate to better functional correctness. In fact, the constraints often forced the model to generate syntactically valid but functionally incorrect code or caused generation loops.

2. Misalignment Causes Distributional Bias (RQ1)

The study confirmed that incomplete constrainers push LLMs into low-probability regions.

NLL Analysis: Constrained solutions exhibited significantly higher NLL (indicating they are less likely under the model's natural distribution) compared to unconstrained solutions.
Mechanism of Failure: When a model attempts to use a feature unsupported by the constrainer (e.g., a forward reference in TypeScript), the constrainer rejects the token. The model is then forced to select an alternative, often leading to a "low-probability path" where the generated code becomes semantically nonsensical or enters a repetition loop until a timeout occurs.

3. Fine-Tuning Mitigates but Does Not Eliminate Bias (RQ2)

Fine-tuning the LLM to align with the constrainer's distribution (using GRPO) yielded mixed but positive results:

Reduced Timeouts: Fine-tuning reduced timeout rates by 53–73% (token limits) and 74–94% (time limits).
Convergence: In some cases (e.g., Gemma-2-2B on HumanEval), fine-tuning made the functional correctness of constrained and unconstrained decoding equivalent.
Limitations: Despite improved alignment, some incompleteness bias persisted. Constrained decoding still underperformed or only matched unconstrained decoding in functional correctness, suggesting that fine-tuning alone cannot fully compensate for a fundamentally incomplete constrainer.

4. Completeness is Critical (RQ3)

Using TOML, the authors demonstrated that complete constrainers significantly outperform unconstrained decoding, especially for smaller models.

Performance Gains: With a complete constrainer, the 2B model (Gemma-2-2B) saw a 53% increase in exact match scores compared to unconstrained decoding.
Sensitivity to Incompleteness: Removing specific features caused drastic performance drops. For instance, forbidding optional spaces before the equals sign (c-space=) reduced the functional correctness of the 80B model by 97%. This indicates that models attribute significant semantic weight to even minor syntactic constructs like spacing.
Feature Sensitivity: Not all features are equally critical; removing comments or dotted keys had minimal impact, whereas removing spacing options was catastrophic.

Significance and Contributions

The paper makes the following contributions to the community:

Empirical Evidence of Failure: It provides a large-scale study showing that current constrained decoding approaches are consistently outperformed by unconstrained decoding in functional correctness, challenging the assumption that constraints automatically improve code generation.
The Alignment Framework: It introduces the concept of alignment between the model language, target language, and constrained language. This framework explains why constrained decoding fails (incompleteness bias) and provides a theoretical basis for diagnosing these issues.
Quantitative Insights on Mitigation: It demonstrates that while fine-tuning can reduce the negative effects of misalignment (by harmonizing the model distribution with the constrainer), it is not a silver bullet. The most effective solution is ensuring the completeness of the constrainer.
Design Guidelines: The paper offers quantitative insights for designing constrainers, highlighting that even minor syntactic restrictions (like spacing) can have massive negative impacts on generation quality.

Conclusion

The paper concludes that constrained decoding is beneficial only when there is strict alignment between the model, the target, and the constraints. An incomplete constrainer acts as a source of bias that distorts the LLM's distribution, leading to generation failures. To achieve formal guarantees without sacrificing functional correctness, practitioners must either design complete constrainers or align the model's distribution to the constraints through fine-tuning, acknowledging that the latter may not fully recover the performance gap caused by incompleteness.