# The Hidden Cost of Structured Generation in LLMs: Draft-Conditioned Constrained Decoding

arXiv: https://arxiv.org/abs/2603.03305 · HTML: https://mlsanity.com/paper/2603.03305/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 33 references that are in the map.
- First posted on arXiv 8 Feb 2026.

## Builds on (most cited first, 16 of 16)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models](https://mlsanity.com/paper/2410.05229/) (2024)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search](https://mlsanity.com/paper/1704.07138/) (2017)
- [Efficient Guided Generation for Large Language Models](https://mlsanity.com/paper/2307.09702/) (2023)
- [Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation](https://mlsanity.com/paper/1804.06609/) (2018)
- [MRKL Systems: A modular, neuro-symbolic architecture that combines large language models, external knowledge sources and discrete reasoning](https://mlsanity.com/paper/2205.00445/) (2022)
- [XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models](https://mlsanity.com/paper/2411.15100/) (2024)
- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [Automata-based constraints for language model decoding](https://mlsanity.com/paper/2407.08103/) (2024)
- [Flexible and Efficient Grammar-Constrained Decoding](https://mlsanity.com/paper/2502.05111/) (2025)
- [IterGen: Iterative Semantic-aware Structured LLM Generation with Backtracking](https://mlsanity.com/paper/2410.07295/) (2024)
- [P-FOLIO: Evaluating and Improving Logical Reasoning with Abundant Human-Written Reasoning Chains](https://mlsanity.com/paper/2410.09207/) (2024)

## Built on by (most cited first, 7 of 7)

- [Repair, Not Improvement: Decomposing Constrained Decoding in Tool-Call Abstention](https://mlsanity.com/paper/2608.13959/) (2026)
- [The Format Tax](https://mlsanity.com/paper/2604.03616/) (2026)
- [Schema-Key Wording as an Instruction Channel in Structured Generation under Constrained Decoding](https://mlsanity.com/paper/2604.14862/) (2026)
- [The Extrapolation Cliff in On-Policy Distillation of Near-Deterministic Structured Outputs](https://mlsanity.com/paper/2605.08737/) (2026)
- [LatticeBridge: Rare-Event Sequential Inference for Faithful Structured Sequence Synthesis](https://mlsanity.com/paper/2606.11203/) (2026)
- [ATLAS-RTC: Closing the Loop on LLM Agent Output with Token-Level Runtime Control](https://mlsanity.com/paper/2603.27905/) (2026)
- [Constrained Decoding Eliminates Structural Failures in Small LLMs but Reveals a Scale-Dependent Semantic Gap](https://mlsanity.com/paper/2609.23742/) (2026)

## Abstract (arXiv)

Large language models (LLMs) are increasingly used to generate executable outputs, JSON objects, and API calls, where a single syntax error can make the output unusable. Constrained decoding enforces validity token-by-token via masking and renormalization, but it can distort generation when the model assigns low probability mass to valid continuations, pushing decoding toward locally valid yet semantically incorrect trajectories. We propose Draft-Conditioned Constrained Decoding (DCCD), a simple two-step, training-free inference procedure that decouples semantic planning from structural enforcement: an unconstrained draft is generated first, and constrained decoding is then applied, conditioned on this draft, to guarantee validity. We analyze DCCD through a KL-projection view, showing that draft conditioning increases feasible mass and reduces the cumulative "projection tax" induced by hard constraints, with an optional best-of-K draft selection. Across structured reasoning benchmarks, DCCD improves strict structured accuracy by up to +24 percentage points over standard constrained decoding (e.g., 15.2% to 39.0% on GSM8K with a 1B model), and enables smaller model pairs to match or exceed much larger constrained baselines, yielding substantial gains in parameter efficiency.