# IterGen: Iterative Semantic-aware Structured LLM Generation with Backtracking

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 24 references that are in the map.
- First posted on arXiv 9 Oct 2024.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task](https://mlsanity.com/paper/1809.08887/) (2018)
- [DecodingTrust: A Comprehensive Assessment of Trustworthiness in GPT Models](https://mlsanity.com/paper/2306.11698/) (2023)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [Hallucination is Inevitable: An Innate Limitation of Large Language Models](https://mlsanity.com/paper/2401.11817/) (2024)
- [Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning](https://mlsanity.com/paper/2305.13971/) (2023)
- [Synchromesh: Reliable code generation from pre-trained language models](https://mlsanity.com/paper/2201.11227/) (2022)
- [Prompting Is Programming: A Query Language for Large Language Models](https://mlsanity.com/paper/2212.06094/) (2022)
- [Copiloting the Copilots: Fusing Large Language Models with Completion Engines for Automated Program Repair](https://mlsanity.com/paper/2309.00608/) (2023)
- [Collecting and Characterizing Natural Language Utterances for Specifying Data Visualizations](https://mlsanity.com/paper/2110.00680/) (2021)
- [Exploring Parameter-Efficient Fine-Tuning Techniques for Code Generation with Large Language Models](https://mlsanity.com/paper/2308.10462/) (2023)
- [Guiding Language Models of Code with Global Context using Monitors](https://mlsanity.com/paper/2306.10763/) (2023)
- [A Comparative Study of DSL Code Generation: Fine-Tuning vs. Optimized Retrieval Augmentation](https://mlsanity.com/paper/2407.02742/) (2024)

## Built on by (most cited first, 29 of 29)

- [CRANE: Reasoning with constrained LLM generation](https://mlsanity.com/paper/2502.09061/) (2025)
- [Enforcing Temporal Constraints for LLM Agents](https://mlsanity.com/paper/2512.23738/) (2025)
- [Generate, but Verify: Reducing Hallucination in Vision-Language Models with Retrospective Resampling](https://mlsanity.com/paper/2504.13169/) (2025)
- [A Survey on Parallel Text Generation: From Parallel Decoding to Diffusion Language Models](https://mlsanity.com/paper/2508.08712/) (2025)
- [CodeARC: Benchmarking Reasoning Capabilities of LLM Agents for Inductive Program Synthesis](https://mlsanity.com/paper/2503.23145/) (2025)
- [SEVerA: Verified Synthesis of Self-Evolving Agents](https://mlsanity.com/paper/2603.25111/) (2026)
- [Lookahead-then-Verify: Reliable Constrained Decoding for Diffusion LLMs under Context-Free Grammars](https://mlsanity.com/paper/2602.00612/) (2026)
- [The Hidden Cost of Structured Generation in LLMs: Draft-Conditioned Constrained Decoding](https://mlsanity.com/paper/2603.03305/) (2026)
- [TreeCoder: Systematic Exploration and Optimisation of Decoding and Constraints for LLM Code Generation](https://mlsanity.com/paper/2511.22277/) (2025)
- [Constrained Adaptive Rejection Sampling](https://mlsanity.com/paper/2510.01902/) (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)
- [Semantic Layers for Reliable LLM-Powered Data Analytics: A Paired Benchmark of Accuracy and Hallucination Across Three Frontier Models](https://mlsanity.com/paper/2604.25149/) (2026)
- [BEAVER: An Efficient Deterministic LLM Verifier](https://mlsanity.com/paper/2512.05439/) (2025)
- [Token-Guard: Towards Token-Level Hallucination Control via Self-Checking Decoding](https://mlsanity.com/paper/2601.21969/) (2026)
- [VegaChat: A Robust Framework for LLM-Based Chart Generation and Assessment](https://mlsanity.com/paper/2601.15385/) (2026)
- [TruncProof: A Guardrail for LLM-based JSON Generation under Token-Length Constraints](https://mlsanity.com/paper/2605.13076/) (2026)
- [textttSEM-CTRL: Semantically Controlled Decoding](https://mlsanity.com/paper/2503.01804/) (2025)
- [FASTGEN: Fast and Cost-Effective Synthetic Tabular Data Generation with LLMs](https://mlsanity.com/paper/2507.15839/) (2025)
- [Componentization: Decomposing Monolithic LLM Responses into Manipulable Semantic Units](https://mlsanity.com/paper/2509.08203/) (2025)
- [Story2Proposal: A Scaffold for Structured Scientific Paper Writing](https://mlsanity.com/paper/2603.27065/) (2026)
- [Scientific Knowledge-driven Decoding Constraints Improving the Reliability of LLMs](https://mlsanity.com/paper/2604.06603/) (2026)
- [Generative Compilation: On-the-Fly Compiler Feedback as AI Generates Code](https://mlsanity.com/paper/2607.13921/) (2026)
- [Decode-Time Grammars: Constrained LLM Generation over a Refinement Order of Grammar Fragments](https://mlsanity.com/paper/2607.18357/) (2026)
- [Imprompt: A Language Framework for Prompt Programming](https://mlsanity.com/paper/2607.22683/) (2026)
- [Visualizing Graph-to-Answer Mechanism Recovery in Materials-Science Hypothesis Generation](https://mlsanity.com/paper/2608.04170/) (2026)
- [Parser Transitions Already Reveal Structural Responsibility: KV Persistence for Structured Generation](https://mlsanity.com/paper/2608.28276/) (2026)
- [Semantic Prefix Oracles for LLM Decoding: Contracts and Differential Validation](https://mlsanity.com/paper/2609.35425/) (2026)
- [Structural Automata for Neural Semantic Parsing](https://mlsanity.com/paper/2610.13896/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) are widely used for tasks such as natural language and code generation, but their outputs often suffer from issues like hallucination, toxicity, and incorrect results. Current libraries for structured LLM generation rely on left-to-right decoding without support for backtracking, limiting the ability to correct or refine outputs mid-generation. To address this, we introduce IterGen, a user-friendly library for iterative, grammar-guided LLM generation that enables users to move both forward and backward within the generated output based on grammar symbols. By leveraging a symbol-to-position mapping and maintaining the key-value (KV) cache state, IterGen ensures efficient and structured generation while allowing for corrections during the process. We demonstrate IterGen's effectiveness in two important applications: reducing privacy leakage in LLM outputs and improving the accuracy of LLM-generated SQL and Vega-Lite queries. Our code and additional resources are available at https://structuredllm.com.