Research map / Large language models / Language, safety and interpretability
IterGen: Iterative Semantic-aware Structured LLM Generation with Backtracking
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 IterGen, a grammar-symbol-based framework with forward/backward/view operations for iterative, backtracking LLM generation, evaluated on SQL, privacy leakage, and Vega-Lite tasks.
Problem
Grammar-guided LLM decoding is left-to-right with no backtracking and cannot enforce semantic constraints or correct outputs mid-generation, and token-level abstractions are misaligned with grammar syntax.
Approach
Uses grammar symbols (terminals and non-terminals) as navigation abstractions via a symbol-to-position map maintained by an incremental LR parser, exposing forward (generate until a symbol count), backward (backtrack by symbol count), and view operations, with a decoding trace and KV-cache cropping for efficiency.
Key results
- On Spider SQL, IterGen raises average overall accuracy to 41.63% vs 28.90% for Standard and 35.22% for SynCode across models.
- On the Enron privacy task, IterGen reduces leaked emails to 0 across all nine models, versus 45-67 leaks for standard decoding out of 100 prompts.
- On the NLV Vega-Lite corpus, IterGen reaches 30.47% accuracy with Llama-3-8B vs 24.69% for SynCode.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use iterative semantic schema checks and backtracking instead of grammar-only generation | SQL generation · Spider | overall execution accuracy (%): 35.22 -> 41.63 | Helped |
| Use iterative semantic constraints and backtracking instead of SynCode | Vega-Lite generation with Qwen2.5-1.5B · NLV Corpus | accuracy (%): 13.14 -> 15.48 | Helped |
| Use iterative semantic constraints and backtracking instead of SynCode | Vega-Lite generation with Llama-3.2-3B · NLV Corpus | accuracy (%): 31.70 -> 36.01 | Helped |
| Use iterative semantic constraints and backtracking instead of SynCode | Vega-Lite generation with Llama-3-8B · NLV Corpus | accuracy (%): 24.69 -> 30.47 | Helped |
| Backtrack and resample outputs matching private email addresses | Qwen2.5-0.5B on DecodingTrust Enron extraction · DecodingTrust Enron email extraction | leaked emails: 45 -> 0 | Helped |
| Add recurrence penalty with γ=0.3 instead of no penalty (ablation) | IterGen on Qwen2.5-0.5B · Spider (first 400 problems) | execution accuracy (%): 27.8 -> 34.3 | Helped |
| Increase recurrence penalty from γ=0.3 to γ=0.7 (ablation) | IterGen on Qwen2.5-0.5B · Spider (first 400 problems) | execution accuracy (%): 34.3 -> 34.3 | No clear effect |
| Add execution-error feedback to Standard generation (ablation) | Qwen2.5-0.5B · Spider (first 400 problems) | execution accuracy (%): 26.8 -> 32.0 | Helped |
| Add execution-error feedback to SynCode (ablation) | Qwen2.5-0.5B · Spider (first 400 problems) | execution accuracy (%): 27.8 -> 33.3 | Helped |
| Increase max new tokens from 100 to 200 and max_iter from 20 to 30 (ablation) | IterGen on Qwen2.5-0.5B · Spider | execution accuracy (%): 30.9 -> 31 | Helped |
| Increase max new tokens and max_iter (ablation) | IterGen on Qwen2.5-0.5B · Spider | time (s): 0.544 -> 1.016 | Hurt |
Surprising findings
- Rejection-sampling baselines with diverse beam search achieve higher privacy pass rates (up to 98.9-99.71% pass@k) than their pass@1 values would suggest, while pass@5 SynCode outperforms IterGen greedy on SQL (38.97%).
Limitations
- Currently limited to single-sequence generation; no batched multi-sequence support.
- Recurrence penalty heuristic can skew the LLM distribution at the first token.
- Privacy filter is a simple email-matching function, so fragments of private data may still leak.
Experimental setup
Datasets: Spider NLV Corpus DecodingTrust privacy (Enron)
Benchmarks: Spider NLV Corpus DecodingTrust
Metrics: execution accuracy execution success rate leaks perplexity generation time tokens
Baselines: Standard unconstrained generation SynCode
Builds on: SynCode Lark EBNF Hugging Face transformers
Closest papers by meaning
- LongGenBench: Benchmarking Long-Form Generation in Long Context LLMs (ICLR 2025 · similarity 0.86)
- CRANE: Reasoning with constrained LLM generation (ICML 2025 · similarity 0.86)
- DataGen: Unified Synthetic Dataset Generation via Large Language Models (ICLR 2025 · similarity 0.86)
- CodeSteer: Symbolic-Augmented Language Models via Code/Text Guidance (ICML 2025 · similarity 0.85)
- Structure-Guided Large Language Models for Text-to-SQL Generation (ICML 2025 · similarity 0.85)
- LongWriter: Unleashing 10,000+ Word Generation from Long Context LLMs (ICLR 2025 · similarity 0.85)
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.