# CRANE: Reasoning with constrained LLM generation

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 14 of its 40 references that are in the map.
- First posted on arXiv 13 Feb 2025.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

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

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [A Survey on Large Language Models for Code Generation](https://mlsanity.com/paper/2406.00515/) (2024)
- [GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models](https://mlsanity.com/paper/2410.05229/) (2024)
- [LeanDojo: Theorem Proving with Retrieval-Augmented Language Models](https://mlsanity.com/paper/2306.15626/) (2023)
- [Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning](https://mlsanity.com/paper/2305.12295/) (2023)
- [FOLIO: Natural Language Reasoning with First-Order Logic](https://mlsanity.com/paper/2209.00840/) (2022)
- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [Grammar-Aligned Decoding](https://mlsanity.com/paper/2405.21047/) (2024)
- [CoRNStack: High-Quality Contrastive Data for Better Code Retrieval and Reranking](https://mlsanity.com/paper/2412.01007/) (2024)
- [IterGen: Iterative Semantic-aware Structured LLM Generation with Backtracking](https://mlsanity.com/paper/2410.07295/) (2024)
- [Constrained Decoding for Fill-in-the-Middle Code Language Models via Efficient Left and Right Quotienting of Context-Sensitive Grammars](https://mlsanity.com/paper/2402.17988/) (2024)
- [Is The Watermarking Of LLM-Generated Code Robust?](https://mlsanity.com/paper/2403.17983/) (2024)
- [Approximately Aligned Decoding](https://mlsanity.com/paper/2410.01103/) (2024)

## Built on by (most cited first, 30 of 38)

- [Enforcing Temporal Constraints for LLM Agents](https://mlsanity.com/paper/2512.23738/) (2025)
- [Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling](https://mlsanity.com/paper/2504.05410/) (2025)
- [CodeARC: Benchmarking Reasoning Capabilities of LLM Agents for Inductive Program Synthesis](https://mlsanity.com/paper/2503.23145/) (2025)
- [DINGO: Constrained Inference for Diffusion LLMs](https://mlsanity.com/paper/2505.23061/) (2025)
- [SEVerA: Verified Synthesis of Self-Evolving Agents](https://mlsanity.com/paper/2603.25111/) (2026)
- [RefineStat: Efficient Exploration for Probabilistic Program Synthesis](https://mlsanity.com/paper/2509.01082/) (2025)
- [TreeCoder: Systematic Exploration and Optimisation of Decoding and Constraints for LLM Code Generation](https://mlsanity.com/paper/2511.22277/) (2025)
- [Thinking Before Constraining: A Unified Decoding Framework for Large Language Models](https://mlsanity.com/paper/2601.07525/) (2026)
- [MyCulture: Exploring Malaysia's Diverse Culture under Low-Resource Language Constraints](https://mlsanity.com/paper/2508.05429/) (2025)
- [When Large Language Models Know the Table: A Framework for Assessing Data Contamination in Tabular Datasets](https://mlsanity.com/paper/2510.20351/) (2025)
- [UTF-8 Plumbing: Byte-level Tokenizers Unavoidably Enable LLMs to Generate Ill-formed UTF-8](https://mlsanity.com/paper/2511.05578/) (2025)
- [The Format Tax](https://mlsanity.com/paper/2604.03616/) (2026)
- [Typed Decision Models: An Early Evidence Audit and Evaluation Checklist](https://mlsanity.com/paper/2609.32160/) (2026)
- [DiCoRe: Enhancing Zero-shot Event Detection via Divergent-Convergent LLM Reasoning](https://mlsanity.com/paper/2506.05128/) (2025)
- [BEAVER: An Efficient Deterministic LLM Verifier](https://mlsanity.com/paper/2512.05439/) (2025)
- [Verifier-Guided Code Translation via Meta-Step Decoding](https://mlsanity.com/paper/2605.17626/) (2026)
- [KARA: Efficient Reasoning LLM Serving via Sliding-Window KV Cache Compression](https://mlsanity.com/paper/2607.01237/) (2026)
- [Training with Pseudo-Code for Instruction Following](https://mlsanity.com/paper/2505.18011/) (2025)
- [Grading the Unspoken: Evaluating Tacit Reasoning in Quantum Field Theory and String Theory with LLMs](https://mlsanity.com/paper/2604.14188/) (2026)
- [AgentSpec: Understanding Embodied Agent Scaffolds Through Controlled Composition](https://mlsanity.com/paper/2606.14674/) (2026)
- [Improving Procedural Skill Explanations via Constrained Generation: A Symbolic-LLM Hybrid Architecture](https://mlsanity.com/paper/2511.20942/) (2025)
- [From Coverage to Causes: Data-Centric Fuzzing for JavaScript Engines](https://mlsanity.com/paper/2512.18102/) (2025)
- [Suffix-Constrained Greedy Search Algorithms for Causal Language Models](https://mlsanity.com/paper/2603.01243/) (2026)
- [Prompt Complexity Dilutes Structured Reasoning: A Follow-Up Study on the Car Wash Problem](https://mlsanity.com/paper/2603.13351/) (2026)
- [ATLAS-RTC: Closing the Loop on LLM Agent Output with Token-Level Runtime Control](https://mlsanity.com/paper/2603.27905/) (2026)
- [Scientific Knowledge-driven Decoding Constraints Improving the Reliability of LLMs](https://mlsanity.com/paper/2604.06603/) (2026)
- [Improving Quantized Model Performance in Qualitative Analysis with Multi-Pass Prompt Verification](https://mlsanity.com/paper/2605.20193/) (2026)
- [Dynamic Infilling Anchors for Format-Constrained Generation in Diffusion Large Language Models](https://mlsanity.com/paper/2606.04535/) (2026)
- [RECAP: Regression Evaluation for Continual Adaptation of Prompts](https://mlsanity.com/paper/2606.06698/) (2026)
- [GRID: Grammar-Railed Decoding for Enterprise SQL Generation](https://mlsanity.com/paper/2607.11951/) (2026)

## Abstract (arXiv)

Code generation, symbolic math reasoning, and other tasks require LLMs to produce outputs that are both syntactically and semantically correct. Constrained LLM generation is a promising direction to enforce adherence to formal grammar, but prior works have empirically observed that strict enforcement of formal constraints often diminishes the reasoning capabilities of LLMs. In this work, we first provide a theoretical explanation for why constraining LLM outputs to very restrictive grammars that only allow syntactically valid final answers reduces the reasoning capabilities of the model. Second, we demonstrate that by augmenting the output grammar with carefully designed additional rules, it is always possible to preserve the reasoning capabilities of the LLM while ensuring syntactic and semantic correctness in its outputs. Building on these theoretical insights, we propose a reasoning-augmented constrained decoding algorithm, CRANE, which effectively balances the correctness of constrained generation with the flexibility of unconstrained generation. Experiments on multiple open-source LLMs and benchmarks show that CRANE significantly outperforms both state-of-the-art constrained decoding strategies and standard unconstrained decoding, showing up to 10% points accuracy improvement over baselines on challenging symbolic reasoning benchmarks GSM-symbolic and FOLIO.