LLMs continue to push the boundaries of content generation, but they can struggle when the output needs to follow very strict rules, like writing code, generating formulas, or creating markup languages (like JSON or HTML). This begs the question: how do we generate highly structured outputs that are both grammatically correct and also contextually meaningful?

One common way to handle this is grammar-constrained decoding (GCD), which forces the model to stick to a grammar by blocking invalid options at each step. However, this method has a big problem: it often results in outputs that technically follow the rules but don’t match what the model is really good at generating—leading to awkward or low-quality results. This is because the outputs don’t follow the distribution of the model.

A new approach called Grammar-Aligned Decoding (GAD) aims to fix this. By taking into account not just the next step but how likely the entire output will make sense in the long run, GAD tries to create outputs that are both valid and natural.

What’s the problem with current methods?

Imagine you’re teaching someone to write a sentence in English, and you only let them pick words that follow proper grammar. If you force them to only follow grammar rules without considering whether their sentence makes sense, you might end up with something weird like, “Powerful catnip swim under desks.” It’s valid, but it’s not what you’d expect, and as a result, it doesn’t make any sense. This is how GCD, the current method for enforcing grammar, works: it only lets the model pick “legal” options at each step.

For example, if you’re generating JSON, it might only allow { or whitespace as the first character. If you’re writing a function, it ensures all brackets eventually match.

While this ensures the output is grammatically valid, it doesn’t consider how realistic or meaningful the rest of the sentence (or code) will be.

Enter GAD…

Instead of just enforcing grammar rules step by step, Grammar-Aligned Decoding (GAD) also looks ahead to ensure the full output will make sense and be more aligned with the model’s natural strengths. It does this using a technique called Adaptive Sampling with Approximate Expected Futures (ASAp).

Here’s how it works:

  1. Start like GCD: only generate valid options.
  2. Look ahead: as the model generates more, evaluate the “richness” of possible future completions for each choice.
  3. Refine choices: adjust the probabilities so options that lead to better overall outcomes are more likely to be picked.

This means GAD isn’t just focused on the next step, it’s trying to ensure the entire output makes sense and is higher quality.

Where GAD is useful

This is useful for a variety of applications. The researchers tested GAD on tasks like generating code and parsing text into trees (used in language analysis). Compared to GCD, GAD produced outputs that aligned more closely with what the model was trained to produce and made more sense, meaning they didn’t just compile, but they also did what they were supposed to do.

Beyond the scope of the paper, this technique could be really useful in situations where outputs need to be both valid and meaningful, such as code generation (e.g. writing scripts, functions, or programs that follow syntax and logic), data transformation (e.g. creating structured data like JSON or XML without missing brackets or breaking rules), or parsing language (generating structured representations of sentences in natural language).

Grammar-Aligned Decoding is aimed at making AI-generated outputs both valid and useful. While current methods like GCD are great at enforcing rules, they often miss the big picture. GAD comes along and says, let’s balance grammar with meaning, which could unlock some useful applications.

Criticisms, and why GAD is not perfect

While Grammar-Aligned Decoding (GAD) introduces an innovative way to balance grammatical correctness with meaningful output, it has some issues:

  1. Slowness and computational complexity: Because it looks ahead and refines options by iteratively evaluating the likelihood of entire sequences, not just the next token, GAD takes more time than simpler methods, making it slower. The iterative evaluation process also adds complexity that can make it harder to implement for real-time applications or large-scale tasks where speed is critical. For many use cases (e.g. autocomplete in IDEs), responsiveness is a priority, and complex (or slow) methods might not gain adoption despite their improved quality.
  2. Subtlety of the problem: The GAD technique addresses a very specific problem: ensuring that the distribution of generated outputs aligns with the LLM’s natural distribution, even under grammatical constraints. This holds in cases where developers use constrained generation primarily to prevent basic errors (like typos or mismatched brackets), not to enforce perfect grammar. Models trained well on specific grammar frameworks often output grammatically valid text naturally anyway, so the added complexity of GAD may offer diminishing returns. That said, in tasks with limited training data or where the grammar is highly specialized (e.g., niche programming languages or data formats), GAD’s ability to optimize “rich” completions could make a meaningful difference.
  3. Practical application: In most cases, constrained generation is about avoiding catastrophic failures (like producing malformed JSON or invalid syntax), not necessarily about optimizing the richness of possible completions. For example, GCD may mask out invalid options, but GAD optimizes for long-term coherence. The latter might not be a critical need in most constrained use cases. If the primary goal of constrained generation is just to “nudge” the model to avoid typos, GAD’s richer exploration might be overkill. If high-quality output isn’t critical (e.g., internal scripts, non-production settings), GCD may suffice. However, for use cases like program synthesis, where subtle errors (like API misuse) can cause major downstream issues, GAD’s ability to align with the model’s probabilities could lead to more robust outputs.
  4. Training vs. constraining: Ideally, LLMs should be trained to produce grammatically valid outputs without the need for constrained generation. Using techniques like GAD to enforce grammar may result in “junk” outputs that technically fit the grammar but lack semantic quality. If the model doesn’t naturally understand the grammar, GAD won’t fix the underlying issue—it might just produce valid but meaningless outputs. A better investment might be improving training data or fine-tuning to enhance the model’s intrinsic understanding of the grammar. That said, for edge cases or low-resource grammars where robust training data isn’t available, GAD could provide a much-needed safeguard against invalid outputs.
  5. Limited impact for known grammars: For well-known and widely-used grammars (like JSON, XML, or Python), GAD might be a solution looking for a problem. Existing models, with adequate training data, already handle these cases well. In these scenarios, the cost of implementing GAD might outweigh the benefits, as the outputs would already be high-quality using simpler methods. For new or evolving grammars (e.g., proprietary configuration formats or experimental programming languages), GAD could provide a significant advantage by ensuring valid and coherent outputs without needing extensive retraining.

Pros and cons

While GAD’s approach may seem like over-engineering for common cases, it offers a promising path forward for specialized or high-stakes applications. Its strengths, like aligning grammar with the model’s probabilities and optimizing for richness, could prove useful in scenarios where correctness and coherence are critical, such as code generation in new languages or frameworks, parsing and data transformation in complex domains, or structured output in scientific or regulatory environments.

However, for general-purpose tasks where GCD already suffices, GAD might indeed be a solution in search of a problem. Whether GAD becomes a widely adopted technique will likely depend on its ability to address these criticisms and prove its value in niche but impactful applications.