Research map / Large language models / Language, safety and interpretability
Guiding LLMs The Right Way: Fast, Non-Invasive Constrained 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.
Introduces DOMINO, a constrained decoding algorithm that enforces CFG/regex constraints with subword-aligned, minimally invasive masking using precomputed subterminal trees, opportunistic masking, and count-based speculative decoding.
Problem
Constrained decoding for LLMs often misaligns sub-word tokens with grammar terminals, which distorts the output distribution, hurts task accuracy, and adds inference overhead.
Approach
Precompute vocabulary-aligned subterminal prefix trees for each scanner state, prune them at inference with a parser to get token masks (allowing bridge tokens), and speed up decoding with a count-based speculative predictor conditioned on scanner and parser state.
Key results
- On GSM8K with Mistral 7B, DOMINO (k=inf) reaches 0.418 accuracy vs 0.415 unconstrained, while guidance drops to 0.345.
- DOMINO with speculative decoding reaches up to 1.77x throughput over unconstrained generation on schema-driven JSON (Mistral 7B).
- On CoNLL-2003 with Mistral 7B, DOMINO achieves 2.66x throughput relative to unconstrained decoding while matching unconstrained accuracy (0.21).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DOMINO (k=∞) instead of unconstrained generation | Mistral 7B · GSM8K | accuracy: 0.415 -> 0.418 | Helped |
| Use DOMINO (k=∞) instead of unconstrained generation | Llama-2 13B · GSM8K | accuracy: 0.262 -> 0.262 | No clear effect |
| Use DOMINO (k=∞) instead of unconstrained generation | Mistral 7B · CoNLL2003 | accuracy: 0.21 -> 0.21 | No clear effect |
| Use DOMINO (k=∞) instead of unconstrained generation | Llama-2 13B · CoNLL2003 | accuracy: 0.09 -> 0.09 | No clear effect |
| Use standard template-based Guidance instead of unconstrained generation | Mistral 7B · GSM8K | accuracy: 0.415 -> 0.345 | Hurt |
| Use standard template-based Guidance instead of unconstrained generation | Mistral 7B · CoNLL2003 | accuracy: 0.21 -> 0.098 | Hurt |
| Allow flexible whitespace in Guidance programs | Guidance on GSM8K · GSM8K | accuracy: 0.345 -> 0.403 | Helped |
| Allow flexible whitespace in Guidance programs | Guidance on CoNLL2003 · CoNLL2003 | accuracy: 0.098 -> 0.19 | Helped |
| Use lookahead k=0 instead of k=∞ (ablation) | DOMINO on GSM8K · GSM8K | accuracy: 0.418 -> 0.308; 0.157 -> 0.0 | Hurt |
| Use lookahead k=1 instead of k=∞ (ablation) | DOMINO on GSM8K · GSM8K | accuracy: 0.418 -> 0.1; 0.157 -> 0.036 | Hurt |
Surprising findings
- Naive template-based constraining (guidance) reduces GSM8K accuracy from 41.5% to 30.8% on Mistral 7B, showing token misalignment harms reasoning.
- Lookahead k=0 or k=1 in DOMINO severely degrades accuracy (e.g., 0.1 for Mistral at k=1), since bridge tokens become unavailable.
Limitations
- Offline setting only: grammars must be known ahead of time for precomputation.
- Speculative decoding is ineffective for hard-to-predict grammars such as C code.
Experimental setup
Datasets: GSM8K CoNLL-2003
Benchmarks: GSM8K CoNLL-2003
Metrics: task accuracy well-formed rate perplexity throughput relative to unconstrained
Baselines: guidance guidance WS llama.cpp grammars unconstrained generation
Builds on: Synchromesh Outlines llama.cpp grammar-constrained decoding speculative sampling token healing
Closest papers by meaning
- Grammar-Aligned Decoding (NeurIPS 2024 · similarity 0.88)
- Accelerating LLM Inference with Lossless Speculative Decoding Algorithms for Heterogeneous Vocabularies (ICML 2025 · similarity 0.88)
- Approximately Aligned Decoding (NeurIPS 2025 · similarity 0.88)
- LongWriter: Unleashing 10,000+ Word Generation from Long Context LLMs (ICLR 2025 · similarity 0.87)
- Adaptive Draft-Verification for Efficient Large Language Model Decoding (AAAI 2025 · similarity 0.87)
- Earley-Driven Dynamic Pruning for Efficient Structured Decoding (ICML 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.