Distribution Preserving Constrained Decoding for Language Models

This direction is merged into another direction: grammar-constrained decoding. Its last version stays readable and citable here.

Version 1 of 119 papers27 conceptsfrozen 2026-10-04

Large Language Models (LLMs) are increasingly used to generate structured data like JSON, Python code, or chemical formulas. To ensure these outputs are syntactically correct, researchers use Grammar-Constrained Decoding (GCD). The standard approach is simple: at each step, "mask out" any tokens that would violate the grammar, forcing the model to choose from the remaining valid options.

However, a growing body of research shows that this "greedy masking" comes with a hidden cost. By forcing the model to follow rigid rules one token at a time, we often "lobotomize" its reasoning, leading to outputs that are syntactically perfect but semantically nonsensical.

The Trap of Local Masking

The intuition behind standard constrained decoding is that if we prevent the model from making a mistake at step $T$, the final sequence will be correct. While Saibo Geng and Robert West demonstrate that this can guarantee 100% structural validity, it introduces a fundamental mathematical bias.

As Haotian Ye and James Y. Zou explain, local masking does not account for the global probability mass. If the model’s natural intent is to generate a sequence that is ultimately invalid, masking a single token doesn't redirect the model toward a good valid sequence; it often pushes the model into a low-probability "dead end." This is why constrained models frequently get stuck in infinite loops or prematurely terminate by assigning high probability to the end-of-sequence token.

Intent Distortion and the Reasoning Gap

When we distort the probability distribution, we aren't just changing the format; we are changing the model's "intent." Jia Li and Ge Li call this intent distortion. Because the model's learned knowledge is tied to its original distribution, forcing it into low-probability regions of its state space causes it to lose its ability to reason.

Avinash Reddy and Amrit Singh Bedi describe this as a "trajectory bias." In their work on Draft-Conditioned Constrained Decoding, they show that the cumulative divergence from the natural distribution leads to a significant drop in performance on complex tasks. Essentially, the model spends so much "energy" trying to satisfy the grammar that it forgets the actual problem it was trying to solve.

From Masking to Exact Sampling

To fix this, researchers are moving away from simple masking and toward methods that preserve the model's original conditional distribution. The goal is to sample from the distribution $P(\text{sequence} \mid \text{grammar})$, rather than just $P(\text{token} \mid \text{valid tokens})$.

Adaptive Rejection Sampling

Paweł Parys, Taylor Berg-Kirkpatrick, and Loris D'Antoni introduced Constrained Adaptive Rejection Sampling (CARS). Instead of forcing a choice, CARS uses rejection sampling—it lets the model sample naturally and rejects invalid paths. To make this efficient, they use a trie-based approach to "learn" which branches of the search tree are invalid, pruning them in future attempts. This maintains the mathematical "exactness" of the distribution without the extreme slowness of naive rejection sampling.

Importance Sampling and MCMC

Other approaches treat the problem through the lens of classical statistics. Haotian Ye developed DISC (Dynamic Importance Sampling for Constrained Decoding), which uses importance sampling to provide theoretically guaranteed, unbiased outputs. Similarly, Emmanuel Anaya Gonzalez and Sairam Vaidya propose an MCMC perspective, treating constrained decoding as a global sampling problem. By allowing the model to explore and "correct" its path, these methods achieve much higher diversity and accuracy in tasks like software fuzzing.

Adaptive Backtracking

If the model realizes it has entered a low-probability state that can no longer satisfy the grammar fluently, it should be able to "re-think." Jia Li introduced AdapTrack, which uses an adaptive backtracking mechanism. When the model hits a constraint violation or a low-probability bottleneck, it backtracks to an earlier token and tries a different path, ensuring the final output remains aligned with the model's original intent.

Why Distribution Alignment Matters

The shift from "hard constraints" to "aligned sampling" represents a maturing of the field. Early work, such as the MAXORDER constraint by Alexandre Papadopoulos and François Pachet, already hinted that enforcing hard constraints could reduce the authenticity of generated sequences.

Modern research confirms this: when we force an LLM to follow a grammar, we aren't just changing the "skin" of the output; we are interfering with its internal logic. By using techniques like CARS, DISC, and AdapTrack, we can ensure that LLMs remain both structurally valid and intellectually coherent, preserving the "vibes" of the model while enforcing the rules of the machine.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_distribution_preserving_constrained_deco_8a9ca83d,
  title = {Distribution Preserving Constrained Decoding for Language Models},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/distribution-preserving-constrained-decoding-for-language-models/rdr_8a9ca83d5e6347d69d62d78bc58bb003},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_distribution_preserving_constrained_deco_8a9ca83d_v1,
  title = {Distribution Preserving Constrained Decoding for Language Models},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/distribution-preserving-constrained-decoding-for-language-models/rdr_8a9ca83d5e6347d69d62d78bc58bb003/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}