Research map / Large language models / Language, safety and interpretability
Grammar-Aligned Decoding
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.
Shows that grammar-constrained decoding distorts the LLM's distribution and proposes ASAp, an adaptive sampling algorithm that iteratively refines expected-future-grammaticality estimates so sampling converges to the LLM distribution conditioned on the grammar.
Problem
Grammar-constrained decoding (GCD) forces LLM outputs to satisfy a CFG but greedily masks tokens, so outputs are grammatical yet have likelihoods not proportional to the LLM's conditional distribution, biasing sampling toward low-quality outputs.
Approach
Formalize grammar-aligned decoding (GAD) as sampling from the LLM distribution restricted to the grammar, and approximate the expected future grammaticality (EFG) by an upper bound built from previously observed samples' next-token probabilities; repeated sampling tightens the bound so the sampler converges to the target distribution.
Key results
- ASAp's KL divergence to the GAD target converges toward 0 on the illustrative example while GCD's does not.
- Sum of squared expectation differences vs. LLM distribution: ASAp 0.802 vs GCD 1.852 on INV-BV4 and ASAp 1.242 vs GCD 2.259 on SLIA.
- ASAp produces correct samples 38% more often than GCD (geomean) across SyGuS tasks where both solve the problem, but 73% less often on SLIA benchmarks both tools solve.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ASAp instead of GCD, updating expected-future-grammaticality estimates from prior samples | Mistral-7B constrained decoding · INV-BV benchmarks | correct samples: ASAp produces correct samples 38% more often than GCD (geomean) | Helped |
| Use ASAp instead of GCD, updating expected-future-grammaticality estimates from prior samples | Mistral-7B constrained decoding · SLIA benchmarks both tools can solve | correct samples: ASAp produces correct samples 73% less often than GCD (geomean) | Hurt |
| Use ASAp instead of GCD | Mistral-7B constrained decoding · SLIA/name-combine-4-long | correct samples: 12 -> 1588 | Helped |
| Use ASAp instead of GCD | Mistral-7B constrained decoding · SLIA/lastname | correct samples: 1526 -> 285 | Hurt |
| Use ASAp instead of GCD | Mistral-7B constrained decoding · INV-BV/find_inv_eq_bvlshr0_4bit | correct samples: 228 -> 635 | Helped |
| Use ASAp instead of GCD | Mistral-7B constrained decoding · INV-BV/find_inv_bvule_bvurem1_4bit | correct samples: 227 -> 143 | Hurt |
| Use ASAp instead of GCD | Mistral-7B constrained decoding · SLIA and INV-BV downstream solution generation | correct samples: ASAp produces correct samples 38% more often than GCD (geomean); 73% less often | Mixed |
| Fine-tune the base model on task-specific datasets before comparing ASAp with GCD | Mistral-7B · INV-BV4 | sum of least squares difference from target expectations: 0.677 -> 0.051 | Helped |
| Fine-tune the base model on task-specific datasets before comparing ASAp with GCD | Mistral-7B · CP | sum of least squares difference from target expectations: 0.278 -> 0.201 | Helped |
Surprising findings
- On SLIA benchmarks both tools solve, ASAp produces correct samples 73% less often than GCD (geomean).
- GCD can have better KL divergence on some benchmarks simply because it is biased toward the most likely outcome.
Limitations
- Slow convergence of ASAp; KL barely improves on some benchmarks even after 2,000 iterations.
- Evaluation on only 36 problems with a single 7B model and no error bars across seeds.
- No strong effect on downstream task correctness overall.
Experimental setup
Datasets: SyGuS SLIA benchmarks SyGuS INV-BV benchmarks Penn TreeBank constituency parsing (CP) problems
Benchmarks: SyGuS SLIA (15 problems) SyGuS INV-BV (15 problems) Constituency parsing (6 problems) Illustrative binary-string example
Metrics: KL divergence to GAD target distribution expectation of distribution vs. LLM expectation number of correct solutions out of 2000 samples
Baselines: GCD (grammar-constrained decoding)
Builds on: grammar-constrained decoding (Geng et al.) Transformers-CFG rejection sampling
Closest papers by meaning
- Flexible and Efficient Grammar-Constrained Decoding (ICML 2025 · similarity 0.92)
- Approximately Aligned Decoding (NeurIPS 2025 · similarity 0.90)
- Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata (NeurIPS 2026 · similarity 0.88)
- Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation (ICML 2024 · similarity 0.88)
- Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective (NeurIPS 2025 · similarity 0.88)
- Alignment of Large Language Models with Constrained Learning (NeurIPS 2025 · similarity 0.87)
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.