Research map / Large language models / Agents, code and math
CRANE: Reasoning with constrained LLM generation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves that strict grammar-constrained decoding can limit LLM reasoning expressivity and proposes CRANE, which alternates unconstrained reasoning with grammar-constrained answer generation via delimiters, improving accuracy on GSM-Symbolic and FOLIO.
Problem
Constrained decoding enforces syntactic validity of LLM outputs but can reduce functional correctness, as restrictive grammars leave no room for intermediate reasoning steps.
Approach
Augment the output grammar as G_a -> R G so that a free-form reasoning segment R precedes the constrained final answer; CRANE switches between unconstrained generation and constrained decoding using start/end delimiters (<< and >>) detected during generation.
Key results
- On GSM-Symbolic, CRANE with Qwen2.5-Math-7B-Instruct reaches 38% accuracy versus 29% for unconstrained CoT and constrained generation.
- On FOLIO, CRANE with Llama-3.1-8B-Instruct reaches 46.31% accuracy versus 32.02% for unconstrained CoT and 39.41% for constrained generation.
- Paper reports up to 10 percentage points accuracy improvement over baselines on GSM-Symbolic and FOLIO.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add reasoning-augmented constrained decoding (CRANE, unconstrained reasoning then constrained answer) over IterGen constrained decoding | Qwen2.5-1.5B-Instruct and other models on GSM-Symbolic · GSM-Symbolic 8-shot | Accuracy (%): +9 pts vs constrained, +5 vs unconstrained CoT (1.5B) | Helped |
| add CRANE reasoning-augmented constrained decoding over unconstrained CoT | Qwen2.5-Math-7B-Instruct · GSM-Symbolic 8-shot | Accuracy (%): 38 vs 29 | Helped |
| add CRANE reasoning-augmented constrained decoding over unconstrained CoT and constrained decoding | Qwen2.5-Coder-14B-Instruct, QwQ-32B and other models on GSM-Symbolic · GSM-Symbolic 8-shot | Accuracy (%): up to +9 pts (DeepSeek-R1-Distill-Llama-8B 21->31 vs CoT) | Helped |
| add CRANE reasoning-augmented constrained decoding over SynCode constrained decoding | Qwen2.5-Math-7B-Instruct, Qwen2.5-7B-Instruct, Llama-3.1-8B-Instruct · FOLIO validation | Accuracy (%): +2.95, +4.92, +6.90 pts | Helped |
| constrained decoding (IterGen) without reasoning vs unconstrained CoT on GSM-Symbolic | Qwen2.5-Coder-7B-Instruct, Qwen2.5-1.5B-Instruct · GSM-Symbolic 8-shot | Accuracy (%): 22 vs 26 (1.5B); 35 vs 37 (Coder-7B) | No clear effect |
| reasoning augmentation with CRANE on GSM-Symbolic across shot counts (ablation) | Qwen2.5-Math-7B-Instruct · GSM-Symbolic 2/4/8 shots | Accuracy (%): 32 vs 26 (2-shot constrained); 37 vs 29 (4-shot) | Helped |
| CRANE reasoning-augmented decoding on FOLIO yields lower compile rate than pure constrained decoding | Qwen2.5-Math-7B-Instruct · FOLIO validation | Compiles (%): 75.86 vs 76.85 (constrained) | Hurt |
| CRANE reasoning-augmented decoding on GSM-Symbolic yields slightly more syntax errors than pure constrained decoding | Qwen models on GSM-Symbolic · GSM-Symbolic 8-shot | Parse (%): e.g., 95 vs 99 (Coder-7B), 88 vs 99 (Math-7B) | Hurt |
Surprising findings
- Under strict constrained decoding, accuracy on GSM-Symbolic is often barely above or equal to unconstrained no-CoT, showing grammar restriction removes reasoning benefits.
- On FOLIO with Qwen2.5-7B-Instruct, CRANE's compile rate equals constrained generation (87.68%) despite higher accuracy.
Limitations
- Expressivity reduction is proven only for finite output languages; infinite grammars remain open.
- Requires access to output logits, so inapplicable to closed models that do not expose logits.
- Can produce more syntax errors than purely constrained generation on some instances.
Experimental setup
Datasets: GSM-Symbolic FOLIO
Benchmarks: GSM-Symbolic FOLIO
Metrics: accuracy parse rate compiles rate average tokens
Baselines: Unconstrained w/o CoT Unconstrained CoT Constrained generation (IterGen) SynCode
Builds on: IterGen SynCode chain-of-thought prompting
Closest papers by meaning
- Enhancing Reasoning Capabilities of LLMs via Principled Synthetic Logic Corpus (NeurIPS 2024 · similarity 0.90)
- GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models (ICLR 2025 · similarity 0.89)
- Reasoning-as-Logic-Units: Scaling Test-Time Reasoning in Large Language Models Through Logic Unit Alignment (ICML 2025 · similarity 0.89)
- ORACLE: Optimizing Reasoning Abilities of Large Language Models via Constraint-Led Synthetic Data Elicitation (AAAI 2026 · similarity 0.89)
- ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning (ICML 2025 · similarity 0.88)
- GSM-$\infty$: How Do your LLMs Behave over Infinitely Increasing Reasoning Complexity and Context Length? (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.